COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/bfs_test.cc @ 787:584270fba752

Last change on this file since 787:584270fba752 was 780:e06d0d16595f, checked in by Alpar Juttner, 20 years ago
  • DFS class (bfs.h and bfs_test.cc) added
  • Bugfixes in Dijkstra and Bfs
File size: 1.8 KB
Line 
1#include "test_tools.h"
2#include <hugo/smart_graph.h>
3#include <hugo/bfs.h>
4
5using namespace hugo;
6
7const int PET_SIZE =5;
8
9
10void check_Bfs_SmartGraph_Compile()
11{
12  typedef int VType;
13  typedef SmartGraph Graph;
14
15  typedef Graph::Edge Edge;
16  typedef Graph::Node Node;
17  typedef Graph::EdgeIt EdgeIt;
18  typedef Graph::NodeIt NodeIt;
19  typedef Graph::EdgeMap<VType> LengthMap;
20 
21  typedef Bfs<Graph> BType;
22 
23  Graph G;
24  Node n;
25  Edge e;
26  VType l;
27  bool b;
28  BType::DistMap d(G);
29  BType::PredMap p(G);
30  BType::PredNodeMap pn(G);
31  LengthMap cap(G);
32 
33  BType bfs_test(G);
34 
35  bfs_test.run(n);
36 
37  l  = bfs_test.dist(n);
38  e  = bfs_test.pred(n);
39  n  = bfs_test.predNode(n);
40  d  = bfs_test.distMap();
41  p  = bfs_test.predMap();
42  pn = bfs_test.predNodeMap();
43  b  = bfs_test.reached(n);
44
45}
46
47int main()
48{
49   
50  typedef SmartGraph Graph;
51
52  typedef Graph::Edge Edge;
53  typedef Graph::Node Node;
54  typedef Graph::EdgeIt EdgeIt;
55  typedef Graph::NodeIt NodeIt;
56  typedef Graph::EdgeMap<int> LengthMap;
57
58  Graph G;
59  Node s, t;
60  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
61   
62  s=ps.outer[2];
63  t=ps.inner[0];
64 
65  Bfs<Graph> bfs_test(G);
66  bfs_test.run(s);
67 
68  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
69
70
71  for(EdgeIt e(G); e==INVALID; ++e) {
72    Node u=G.tail(e);
73    Node v=G.head(e);
74    check( !bfs_test.reached(u) ||
75           (bfs_test.dist(v) > bfs_test.dist(u)+1),
76           "Wrong output.");
77  }
78
79  for(NodeIt v(G); v==INVALID; ++v) {
80    check(bfs_test.reached(v),"Each node should be reached.");
81    if ( bfs_test.pred(v)!=INVALID ) {
82      Edge e=bfs_test.pred(v);
83      Node u=G.tail(e);
84      check(u==bfs_test.predNode(v),"Wrong tree.");
85      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
86            "Wrong distance. Difference: "
87            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
88                        - 1));
89    }
90  }
91}
92
Note: See TracBrowser for help on using the repository browser.