21 public: |
21 public: |
22 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : |
22 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : |
23 graph(_graph), node_name_map(_node_name_map) { } |
23 graph(_graph), node_name_map(_node_name_map) { } |
24 string operator[](typename Graph::Edge e) const { |
24 string operator[](typename Graph::Edge e) const { |
25 return |
25 return |
26 (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]); |
26 (node_name_map[graph.source(e)]+"->"+node_name_map[graph.target(e)]); |
27 } |
27 } |
28 }; |
28 }; |
29 |
29 |
30 int main (int, char*[]) |
30 int main (int, char*[]) |
31 { |
31 { |
93 bfs.pushAndSetReached(s); |
93 bfs.pushAndSetReached(s); |
94 while (!bfs.finished()) { |
94 while (!bfs.finished()) { |
95 //cout << "edge: "; |
95 //cout << "edge: "; |
96 if (Graph::Edge(bfs)!=INVALID) { |
96 if (Graph::Edge(bfs)!=INVALID) { |
97 cout << edge_name[bfs] << /*endl*/", " << |
97 cout << edge_name[bfs] << /*endl*/", " << |
98 node_name[G.tail(bfs)] << |
98 node_name[G.source(bfs)] << |
99 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
99 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
100 node_name[G.head(bfs)] << |
100 node_name[G.target(bfs)] << |
101 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
101 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
102 ": is not newly reached."); |
102 ": is not newly reached."); |
103 } else { |
103 } else { |
104 cout << "invalid" << /*endl*/", " << |
104 cout << "invalid" << /*endl*/", " << |
105 node_name[bfs.tail()] << |
105 node_name[bfs.source()] << |
106 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
106 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
107 |
107 |
108 "invalid."; |
108 "invalid."; |
109 } |
109 } |
110 cout << endl; |
110 cout << endl; |
127 while (!dfs.finished()) { |
127 while (!dfs.finished()) { |
128 ++dfs; |
128 ++dfs; |
129 //cout << "edge: "; |
129 //cout << "edge: "; |
130 if (Graph::Edge(dfs)!=INVALID) { |
130 if (Graph::Edge(dfs)!=INVALID) { |
131 cout << edge_name[dfs] << /*endl*/", " << |
131 cout << edge_name[dfs] << /*endl*/", " << |
132 node_name[G.tail(dfs)] << |
132 node_name[G.source(dfs)] << |
133 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
133 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
134 node_name[G.head(dfs)] << |
134 node_name[G.target(dfs)] << |
135 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
135 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
136 ": is not newly reached."); |
136 ": is not newly reached."); |
137 } else { |
137 } else { |
138 cout << "invalid" << /*endl*/", " << |
138 cout << "invalid" << /*endl*/", " << |
139 node_name[dfs.tail()] << |
139 node_name[dfs.source()] << |
140 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
140 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
141 |
141 |
142 "invalid."; |
142 "invalid."; |
143 } |
143 } |
144 cout << endl; |
144 cout << endl; |
169 bfs.pushAndSetReached(t); |
169 bfs.pushAndSetReached(t); |
170 while (!bfs.finished()) { |
170 while (!bfs.finished()) { |
171 //cout << "edge: "; |
171 //cout << "edge: "; |
172 if (GW::Edge(bfs)!=INVALID) { |
172 if (GW::Edge(bfs)!=INVALID) { |
173 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << |
173 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << |
174 node_name[gw.tail(bfs)] << |
174 node_name[gw.source(bfs)] << |
175 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
175 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
176 node_name[gw.head(bfs)] << |
176 node_name[gw.target(bfs)] << |
177 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
177 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
178 ": is not newly reached."); |
178 ": is not newly reached."); |
179 } else { |
179 } else { |
180 cout << "invalid" << /*endl*/", " << |
180 cout << "invalid" << /*endl*/", " << |
181 node_name[bfs.tail()] << |
181 node_name[bfs.source()] << |
182 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
182 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
183 |
183 |
184 "invalid."; |
184 "invalid."; |
185 } |
185 } |
186 cout << endl; |
186 cout << endl; |
203 while (!dfs.finished()) { |
203 while (!dfs.finished()) { |
204 ++dfs; |
204 ++dfs; |
205 //cout << "edge: "; |
205 //cout << "edge: "; |
206 if (GW::Edge(dfs)!=INVALID) { |
206 if (GW::Edge(dfs)!=INVALID) { |
207 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << |
207 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << |
208 node_name[gw.tail(dfs)] << |
208 node_name[gw.source(dfs)] << |
209 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
209 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
210 node_name[gw.head(dfs)] << |
210 node_name[gw.target(dfs)] << |
211 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
211 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
212 ": is not newly reached."); |
212 ": is not newly reached."); |
213 } else { |
213 } else { |
214 cout << "invalid" << /*endl*/", " << |
214 cout << "invalid" << /*endl*/", " << |
215 node_name[dfs.tail()] << |
215 node_name[dfs.source()] << |
216 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
216 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
217 |
217 |
218 "invalid."; |
218 "invalid."; |
219 } |
219 } |
220 cout << endl; |
220 cout << endl; |
308 |
308 |
309 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
309 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
310 |
310 |
311 cout << "bfs and dfs iterator demo on the bidirected graph" << endl; |
311 cout << "bfs and dfs iterator demo on the bidirected graph" << endl; |
312 // for(GW::EdgeIt e(gw); e!=INVALID; ++e) { |
312 // for(GW::EdgeIt e(gw); e!=INVALID; ++e) { |
313 // cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " "; |
313 // cout << node_name[gw.source(e)] << "->" << node_name[gw.target(e)] << " "; |
314 // } |
314 // } |
315 for(GW::NodeIt n(gw); n!=INVALID; ++n) { |
315 for(GW::NodeIt n(gw); n!=INVALID; ++n) { |
316 cout << node_name[GW::Node(n)] << ": "; |
316 cout << node_name[GW::Node(n)] << ": "; |
317 cout << "out edges: "; |
317 cout << "out edges: "; |
318 for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) |
318 for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) |
332 bfs.pushAndSetReached(t); |
332 bfs.pushAndSetReached(t); |
333 while (!bfs.finished()) { |
333 while (!bfs.finished()) { |
334 //cout << "edge: "; |
334 //cout << "edge: "; |
335 if (GW::Edge(bfs)!=INVALID) { |
335 if (GW::Edge(bfs)!=INVALID) { |
336 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << |
336 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << |
337 node_name[gw.tail(bfs)] << |
337 node_name[gw.source(bfs)] << |
338 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
338 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
339 node_name[gw.head(bfs)] << |
339 node_name[gw.target(bfs)] << |
340 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
340 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
341 ": is not newly reached."); |
341 ": is not newly reached."); |
342 } else { |
342 } else { |
343 cout << "invalid" << /*endl*/", " << |
343 cout << "invalid" << /*endl*/", " << |
344 node_name[bfs.tail()] << |
344 node_name[bfs.source()] << |
345 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
345 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
346 |
346 |
347 "invalid."; |
347 "invalid."; |
348 } |
348 } |
349 cout << endl; |
349 cout << endl; |
366 while (!dfs.finished()) { |
366 while (!dfs.finished()) { |
367 ++dfs; |
367 ++dfs; |
368 //cout << "edge: "; |
368 //cout << "edge: "; |
369 if (GW::Edge(dfs)!=INVALID) { |
369 if (GW::Edge(dfs)!=INVALID) { |
370 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << |
370 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << |
371 node_name[gw.tail(dfs)] << |
371 node_name[gw.source(dfs)] << |
372 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
372 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
373 node_name[gw.head(dfs)] << |
373 node_name[gw.target(dfs)] << |
374 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
374 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
375 ": is not newly reached."); |
375 ": is not newly reached."); |
376 } else { |
376 } else { |
377 cout << "invalid" << /*endl*/", " << |
377 cout << "invalid" << /*endl*/", " << |
378 node_name[dfs.tail()] << |
378 node_name[dfs.source()] << |
379 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
379 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
380 |
380 |
381 "invalid."; |
381 "invalid."; |
382 } |
382 } |
383 cout << endl; |
383 cout << endl; |