COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/bfs_test.cc @ 1220:20b26ee5812b

Last change on this file since 1220:20b26ee5812b was 1220:20b26ee5812b, checked in by Alpar Juttner, 16 years ago
  • Add compilation tests for the function type interface of BFS/DFS/Dijkstra
  • Fix the bugs covered up by these tests
File size: 2.9 KB
Line 
1/* -*- C++ -*-
2 * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#include "test_tools.h"
18#include <lemon/smart_graph.h>
19#include <lemon/bfs.h>
20#include<lemon/concept/graph.h>
21
22using namespace lemon;
23
24const int PET_SIZE =5;
25
26
27void check_Bfs_Compile()
28{
29  typedef concept::StaticGraph Graph;
30
31  typedef Graph::Edge Edge;
32  typedef Graph::Node Node;
33  typedef Graph::EdgeIt EdgeIt;
34  typedef Graph::NodeIt NodeIt;
35 
36  typedef Bfs<Graph> BType;
37 
38  Graph G;
39  Node n;
40  Edge e;
41  int l;
42  bool b;
43  BType::DistMap d(G);
44  BType::PredMap p(G);
45  //  BType::PredNodeMap pn(G);
46 
47  BType bfs_test(G);
48 
49  bfs_test.run(n);
50 
51  l  = bfs_test.dist(n);
52  e  = bfs_test.pred(n);
53  n  = bfs_test.predNode(n);
54  d  = bfs_test.distMap();
55  p  = bfs_test.predMap();
56  //  pn = bfs_test.predNodeMap();
57  b  = bfs_test.reached(n);
58
59}
60
61void check_Bfs_Function_Compile()
62{
63  typedef int VType;
64  typedef concept::StaticGraph Graph;
65
66  typedef Graph::Edge Edge;
67  typedef Graph::Node Node;
68  typedef Graph::EdgeIt EdgeIt;
69  typedef Graph::NodeIt NodeIt;
70  typedef concept::ReadMap<Edge,VType> LengthMap;
71   
72  bfs(Graph(),Node()).run();
73  bfs(Graph()).source(Node()).run();
74  bfs(Graph())
75    .predMap(concept::WriteMap<Node,Edge>())
76    .distMap(concept::WriteMap<Node,VType>())
77    .reachedMap(concept::ReadWriteMap<Node,bool>())
78    .processedMap(concept::WriteMap<Node,bool>())
79    .run(Node());
80 
81}
82
83int main()
84{
85   
86  typedef SmartGraph Graph;
87
88  typedef Graph::Edge Edge;
89  typedef Graph::Node Node;
90  typedef Graph::EdgeIt EdgeIt;
91  typedef Graph::NodeIt NodeIt;
92  typedef Graph::EdgeMap<int> LengthMap;
93
94  Graph G;
95  Node s, t;
96  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
97   
98  s=ps.outer[2];
99  t=ps.inner[0];
100 
101  Bfs<Graph> bfs_test(G);
102  bfs_test.run(s);
103 
104  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
105
106
107  for(EdgeIt e(G); e==INVALID; ++e) {
108    Node u=G.source(e);
109    Node v=G.target(e);
110    check( !bfs_test.reached(u) ||
111           (bfs_test.dist(v) > bfs_test.dist(u)+1),
112           "Wrong output.");
113  }
114
115  for(NodeIt v(G); v==INVALID; ++v) {
116    check(bfs_test.reached(v),"Each node should be reached.");
117    if ( bfs_test.pred(v)!=INVALID ) {
118      Edge e=bfs_test.pred(v);
119      Node u=G.source(e);
120      check(u==bfs_test.predNode(v),"Wrong tree.");
121      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
122            "Wrong distance. Difference: "
123            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
124                        - 1));
125    }
126  }
127}
128
Note: See TracBrowser for help on using the repository browser.