COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dfs_test.cc @ 793:9cd0aeea47b0

Last change on this file since 793:9cd0aeea47b0 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.5 KB
RevLine 
[780]1#include "test_tools.h"
2#include <hugo/smart_graph.h>
3#include <hugo/dfs.h>
[793]4#include<hugo/skeletons/graph.h>
[780]5
6using namespace hugo;
7
8const int PET_SIZE =5;
9
10
11void check_Dfs_SmartGraph_Compile()
12{
[793]13  typedef skeleton::StaticGraphSkeleton Graph;
[780]14
15  typedef Graph::Edge Edge;
16  typedef Graph::Node Node;
17  typedef Graph::EdgeIt EdgeIt;
18  typedef Graph::NodeIt NodeIt;
19 
[793]20  typedef Dfs<Graph> DType;
[780]21 
22  Graph G;
23  Node n;
24  Edge e;
[793]25  int l;
[780]26  bool b;
[793]27  DType::DistMap d(G);
28  DType::PredMap p(G);
29  DType::PredNodeMap pn(G);
[780]30 
[793]31  DType dfs_test(G);
[780]32 
33  dfs_test.run(n);
34 
35  l  = dfs_test.dist(n);
36  e  = dfs_test.pred(n);
37  n  = dfs_test.predNode(n);
38  d  = dfs_test.distMap();
39  p  = dfs_test.predMap();
40  pn = dfs_test.predNodeMap();
41  b  = dfs_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  Dfs<Graph> dfs_test(G);
64  dfs_test.run(s); 
65 
66  for(NodeIt v(G); v!=INVALID; ++v) {
67    check(dfs_test.reached(v),"Each node should be reached.");
68    if ( dfs_test.pred(v)!=INVALID ) {
69      Edge e=dfs_test.pred(v);
70      Node u=G.tail(e);
71      check(u==dfs_test.predNode(v),"Wrong tree.");
72      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
73            "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
74    }
75  }
76}
77
Note: See TracBrowser for help on using the repository browser.