Unionfind changes induced some bugs here. Also some augmentations made.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #include "test_tools.h"
20 #include <lemon/smart_graph.h>
21 #include <lemon/dfs.h>
22 #include <lemon/path.h>
23 #include <lemon/concept/graph.h>
25 using namespace lemon;
27 const int PET_SIZE =5;
30 void check_Dfs_SmartGraph_Compile()
32 typedef concept::StaticGraph Graph;
34 typedef Graph::Edge Edge;
35 typedef Graph::Node Node;
36 typedef Graph::EdgeIt EdgeIt;
37 typedef Graph::NodeIt NodeIt;
39 typedef Dfs<Graph> DType;
48 // DType::PredNodeMap pn(G);
55 e = dfs_test.predEdge(n);
56 n = dfs_test.predNode(n);
57 d = dfs_test.distMap();
58 p = dfs_test.predMap();
59 // pn = dfs_test.predNodeMap();
60 b = dfs_test.reached(n);
63 dfs_test.getPath(pp,n);
67 void check_Dfs_Function_Compile()
70 typedef concept::StaticGraph Graph;
72 typedef Graph::Edge Edge;
73 typedef Graph::Node Node;
74 typedef Graph::EdgeIt EdgeIt;
75 typedef Graph::NodeIt NodeIt;
76 typedef concept::ReadMap<Edge,VType> LengthMap;
78 dfs(Graph(),Node()).run();
79 dfs(Graph()).source(Node()).run();
81 .predMap(concept::WriteMap<Node,Edge>())
82 .distMap(concept::WriteMap<Node,VType>())
83 .reachedMap(concept::ReadWriteMap<Node,bool>())
84 .processedMap(concept::WriteMap<Node,bool>())
92 typedef SmartGraph Graph;
94 typedef Graph::Edge Edge;
95 typedef Graph::Node Node;
96 typedef Graph::EdgeIt EdgeIt;
97 typedef Graph::NodeIt NodeIt;
98 typedef Graph::EdgeMap<int> LengthMap;
102 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
107 Dfs<Graph> dfs_test(G);
111 check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
112 check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
114 for(NodeIt v(G); v!=INVALID; ++v) {
115 check(dfs_test.reached(v),"Each node should be reached.");
116 if ( dfs_test.predEdge(v)!=INVALID ) {
117 Edge e=dfs_test.predEdge(v);
119 check(u==dfs_test.predNode(v),"Wrong tree.");
120 check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
121 "Wrong distance. (" << dfs_test.dist(u) << "->"
122 <<dfs_test.dist(v) << ')');