Some modifications and another testfile.
6 #include <list_graph.h>
7 //#include <smart_graph.h>
9 #include <hugo/graph_wrapper.h>
16 template <typename Graph, typename NodeNameMap>
19 NodeNameMap& node_name_map;
21 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
22 graph(_graph), node_name_map(_node_name_map) { }
23 string operator[](typename Graph::Edge e) const {
25 (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]);
29 int main (int, char*[])
31 //typedef SmartGraph Graph;
32 typedef ListGraph Graph;
34 typedef Graph::Node Node;
35 typedef Graph::Edge Edge;
46 Graph::NodeMap<string> node_name(G);
47 node_name.set(s, "s");
48 node_name.set(v1, "v1");
49 node_name.set(v2, "v2");
50 node_name.set(v3, "v3");
51 node_name.set(v4, "v4");
52 node_name.set(t, "t");
65 cout << " /--> -------------> "<< endl;
66 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
67 cout << " / | | / /-> \\ "<< endl;
68 cout << " / | | / | ^ \\ "<< endl;
69 cout << "s | | / | | \\-> t "<< endl;
70 cout << " \\ | | / | | /-> "<< endl;
71 cout << " \\ | --/ / | | / "<< endl;
72 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
73 cout << " \\--> -------------> "<< endl;
75 // typedef TrivGraphWrapper<const Graph> CGW;
78 // cout << "bfs and dfs demo on the directed graph" << endl;
79 // for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
81 // cout << "out edges: ";
82 // for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
84 // cout << "in edges: ";
85 // for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
91 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
93 cout << "bfs and dfs iterator demo on the directed graph" << endl;
94 for(Graph::NodeIt n(G); G.valid(n); G.next(n)) {
95 cout << node_name[n] << ": ";
96 cout << "out edges: ";
97 for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e))
98 cout << edge_name[e] << " ";
100 for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e))
101 cout << edge_name[e] << " ";
105 cout << "bfs from s ..." << endl;
106 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
107 bfs.pushAndSetReached(s);
108 while (!bfs.finished()) {
111 cout << edge_name[bfs] << /*endl*/", " <<
112 node_name[G.aNode(bfs)] <<
113 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
114 node_name[G.bNode(bfs)] <<
115 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
116 ": is not newly reached.");
118 cout << "invalid" << /*endl*/", " <<
119 node_name[bfs.aNode()] <<
120 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
128 cout << " /--> -------------> "<< endl;
129 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
130 cout << " / | | / /-> \\ "<< endl;
131 cout << " / | | / | ^ \\ "<< endl;
132 cout << "s | | / | | \\-> t "<< endl;
133 cout << " \\ | | / | | /-> "<< endl;
134 cout << " \\ | --/ / | | / "<< endl;
135 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
136 cout << " \\--> -------------> "<< endl;
138 cout << "dfs from s ..." << endl;
139 DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
140 dfs.pushAndSetReached(s);
141 while (!dfs.finished()) {
145 cout << edge_name[dfs] << /*endl*/", " <<
146 node_name[G.aNode(dfs)] <<
147 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
148 node_name[G.bNode(dfs)] <<
149 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
150 ": is not newly reached.");
152 cout << "invalid" << /*endl*/", " <<
153 node_name[dfs.aNode()] <<
154 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
164 typedef RevGraphWrapper<const Graph> GW;
167 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
169 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
170 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
171 cout << node_name[GW::Node(n)] << ": ";
172 cout << "out edges: ";
173 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
174 cout << edge_name[e] << " ";
175 cout << "in edges: ";
176 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
177 cout << edge_name[e] << " ";
181 cout << "bfs from t ..." << endl;
182 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
183 bfs.pushAndSetReached(t);
184 while (!bfs.finished()) {
186 if (gw.valid(GW::OutEdgeIt(bfs))) {
187 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
188 node_name[gw.aNode(bfs)] <<
189 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
190 node_name[gw.bNode(bfs)] <<
191 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
192 ": is not newly reached.");
194 cout << "invalid" << /*endl*/", " <<
195 node_name[bfs.aNode()] <<
196 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
204 cout << " /--> -------------> "<< endl;
205 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
206 cout << " / | | / /-> \\ "<< endl;
207 cout << " / | | / | ^ \\ "<< endl;
208 cout << "s | | / | | \\-> t "<< endl;
209 cout << " \\ | | / | | /-> "<< endl;
210 cout << " \\ | --/ / | | / "<< endl;
211 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
212 cout << " \\--> -------------> "<< endl;
214 cout << "dfs from t ..." << endl;
215 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
216 dfs.pushAndSetReached(t);
217 while (!dfs.finished()) {
220 if (gw.valid(GW::OutEdgeIt(dfs))) {
221 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
222 node_name[gw.aNode(dfs)] <<
223 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
224 node_name[gw.bNode(dfs)] <<
225 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
226 ": is not newly reached.");
228 cout << "invalid" << /*endl*/", " <<
229 node_name[dfs.aNode()] <<
230 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
239 typedef UndirGraphWrapper<const Graph> GW;
242 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
244 cout << "bfs and dfs iterator demo on the undirected graph" << endl;
245 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
246 cout << node_name[GW::Node(n)] << ": ";
247 cout << "out edges: ";
248 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
249 cout << edge_name[e] << " ";
250 cout << "in edges: ";
251 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
252 cout << edge_name[e] << " ";
255 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
256 // cout << edge_name.get(e) << " ";
260 cout << "bfs from t ..." << endl;
261 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
262 bfs.pushAndSetReached(t);
263 while (!bfs.finished()) {
265 if (gw.valid(GW::OutEdgeIt(bfs))) {
266 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
267 node_name[gw.aNode(bfs)] <<
268 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
269 node_name[gw.bNode(bfs)] <<
270 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
271 ": is not newly reached.");
273 cout << "invalid" << /*endl*/", " <<
274 node_name[bfs.aNode()] <<
275 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
283 cout << " /--> -------------> "<< endl;
284 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
285 cout << " / | | / /-> \\ "<< endl;
286 cout << " / | | / | ^ \\ "<< endl;
287 cout << "s | | / | | \\-> t "<< endl;
288 cout << " \\ | | / | | /-> "<< endl;
289 cout << " \\ | --/ / | | / "<< endl;
290 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
291 cout << " \\--> -------------> "<< endl;
293 cout << "dfs from t ..." << endl;
294 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
295 dfs.pushAndSetReached(t);
296 while (!dfs.finished()) {
299 if (gw.valid(GW::OutEdgeIt(dfs))) {
300 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
301 node_name[gw.aNode(dfs)] <<
302 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
303 node_name[gw.bNode(dfs)] <<
304 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
305 ": is not newly reached.");
307 cout << "invalid" << /*endl*/", " <<
308 node_name[dfs.aNode()] <<
309 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
320 typedef BidirGraphWrapper<const Graph> GW;
323 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
325 cout << "bfs and dfs iterator demo on the undirected graph" << endl;
326 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
327 cout << node_name[GW::Node(n)] << ": ";
328 cout << "out edges: ";
329 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
330 cout << edge_name[e] << " ";
331 cout << "in edges: ";
332 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
333 cout << edge_name[e] << " ";
336 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
337 // cout << edge_name.get(e) << " ";
341 cout << "bfs from t ..." << endl;
342 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
343 bfs.pushAndSetReached(t);
344 while (!bfs.finished()) {
346 if (gw.valid(GW::OutEdgeIt(bfs))) {
347 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
348 node_name[gw.aNode(bfs)] <<
349 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
350 node_name[gw.bNode(bfs)] <<
351 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
352 ": is not newly reached.");
354 cout << "invalid" << /*endl*/", " <<
355 node_name[bfs.aNode()] <<
356 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
364 cout << " /--> -------------> "<< endl;
365 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
366 cout << " / | | / /-> \\ "<< endl;
367 cout << " / | | / | ^ \\ "<< endl;
368 cout << "s | | / | | \\-> t "<< endl;
369 cout << " \\ | | / | | /-> "<< endl;
370 cout << " \\ | --/ / | | / "<< endl;
371 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
372 cout << " \\--> -------------> "<< endl;
374 cout << "dfs from t ..." << endl;
375 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
376 dfs.pushAndSetReached(t);
377 while (!dfs.finished()) {
380 if (gw.valid(GW::OutEdgeIt(dfs))) {
381 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
382 node_name[gw.aNode(dfs)] <<
383 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
384 node_name[gw.bNode(dfs)] <<
385 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
386 ": is not newly reached.");
388 cout << "invalid" << /*endl*/", " <<
389 node_name[dfs.aNode()] <<
390 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<