COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/bfs_test.cc @ 850:54d3c1599d08

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