18 Graph& graph; |
18 Graph& graph; |
19 NodeNameMap& node_name_map; |
19 NodeNameMap& node_name_map; |
20 public: |
20 public: |
21 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : |
21 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : |
22 graph(_graph), node_name_map(_node_name_map) { } |
22 graph(_graph), node_name_map(_node_name_map) { } |
23 string get(typename Graph::Edge e) const { |
23 string operator[](typename Graph::Edge e) const { |
24 return |
24 return |
25 (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); |
25 (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]); |
26 } |
26 } |
27 }; |
27 }; |
28 |
28 |
29 int main (int, char*[]) |
29 int main (int, char*[]) |
30 { |
30 { |
93 |
93 |
94 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
94 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
95 |
95 |
96 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
96 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
97 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
97 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
98 cout << node_name.get(n) << ": "; |
98 cout << node_name[n] << ": "; |
99 cout << "out edges: "; |
99 cout << "out edges: "; |
100 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
100 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
101 cout << edge_name.get(e) << " "; |
101 cout << edge_name[e] << " "; |
102 cout << "in edges: "; |
102 cout << "in edges: "; |
103 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
103 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
104 cout << edge_name.get(e) << " "; |
104 cout << edge_name[e] << " "; |
105 cout << endl; |
105 cout << endl; |
106 } |
106 } |
107 |
107 |
108 cout << "bfs from s ..." << endl; |
108 cout << "bfs from s ..." << endl; |
109 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
109 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
110 bfs.pushAndSetReached(s); |
110 bfs.pushAndSetReached(s); |
111 while (!bfs.finished()) { |
111 while (!bfs.finished()) { |
112 //cout << "edge: "; |
112 //cout << "edge: "; |
113 if (gw.valid(bfs)) { |
113 if (gw.valid(bfs)) { |
114 cout << edge_name.get(bfs) << /*endl*/", " << |
114 cout << edge_name[bfs] << /*endl*/", " << |
115 node_name.get(gw.aNode(bfs)) << |
115 node_name[gw.aNode(bfs)] << |
116 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
116 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
117 node_name.get(gw.bNode(bfs)) << |
117 node_name[gw.bNode(bfs)] << |
118 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
118 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
119 ": is not newly reached."); |
119 ": is not newly reached."); |
120 } else { |
120 } else { |
121 cout << "invalid" << /*endl*/", " << |
121 cout << "invalid" << /*endl*/", " << |
122 node_name.get(bfs.aNode()) << |
122 node_name[bfs.aNode()] << |
123 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
123 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
124 |
124 |
125 "invalid."; |
125 "invalid."; |
126 } |
126 } |
127 cout << endl; |
127 cout << endl; |
143 dfs.pushAndSetReached(s); |
143 dfs.pushAndSetReached(s); |
144 while (!dfs.finished()) { |
144 while (!dfs.finished()) { |
145 ++dfs; |
145 ++dfs; |
146 //cout << "edge: "; |
146 //cout << "edge: "; |
147 if (gw.valid(dfs)) { |
147 if (gw.valid(dfs)) { |
148 cout << edge_name.get(dfs) << /*endl*/", " << |
148 cout << edge_name[dfs] << /*endl*/", " << |
149 node_name.get(gw.aNode(dfs)) << |
149 node_name[gw.aNode(dfs)] << |
150 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
150 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
151 node_name.get(gw.bNode(dfs)) << |
151 node_name[gw.bNode(dfs)] << |
152 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
152 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
153 ": is not newly reached."); |
153 ": is not newly reached."); |
154 } else { |
154 } else { |
155 cout << "invalid" << /*endl*/", " << |
155 cout << "invalid" << /*endl*/", " << |
156 node_name.get(dfs.aNode()) << |
156 node_name[dfs.aNode()] << |
157 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
157 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
158 |
158 |
159 "invalid."; |
159 "invalid."; |
160 } |
160 } |
161 cout << endl; |
161 cout << endl; |
169 |
169 |
170 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
170 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
171 |
171 |
172 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
172 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
173 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
173 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
174 cout << node_name.get(n) << ": "; |
174 cout << node_name[n] << ": "; |
175 cout << "out edges: "; |
175 cout << "out edges: "; |
176 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
176 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
177 cout << edge_name.get(e) << " "; |
177 cout << edge_name[e] << " "; |
178 cout << "in edges: "; |
178 cout << "in edges: "; |
179 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
179 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
180 cout << edge_name.get(e) << " "; |
180 cout << edge_name[e] << " "; |
181 cout << endl; |
181 cout << endl; |
182 } |
182 } |
183 |
183 |
184 cout << "bfs from t ..." << endl; |
184 cout << "bfs from t ..." << endl; |
185 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
185 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
186 bfs.pushAndSetReached(t); |
186 bfs.pushAndSetReached(t); |
187 while (!bfs.finished()) { |
187 while (!bfs.finished()) { |
188 //cout << "edge: "; |
188 //cout << "edge: "; |
189 if (gw.valid(bfs)) { |
189 if (gw.valid(bfs)) { |
190 cout << edge_name.get(bfs) << /*endl*/", " << |
190 cout << edge_name[bfs] << /*endl*/", " << |
191 node_name.get(gw.aNode(bfs)) << |
191 node_name[gw.aNode(bfs)] << |
192 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
192 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
193 node_name.get(gw.bNode(bfs)) << |
193 node_name[gw.bNode(bfs)] << |
194 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
194 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
195 ": is not newly reached."); |
195 ": is not newly reached."); |
196 } else { |
196 } else { |
197 cout << "invalid" << /*endl*/", " << |
197 cout << "invalid" << /*endl*/", " << |
198 node_name.get(bfs.aNode()) << |
198 node_name[bfs.aNode()] << |
199 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
199 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
200 |
200 |
201 "invalid."; |
201 "invalid."; |
202 } |
202 } |
203 cout << endl; |
203 cout << endl; |
219 dfs.pushAndSetReached(t); |
219 dfs.pushAndSetReached(t); |
220 while (!dfs.finished()) { |
220 while (!dfs.finished()) { |
221 ++dfs; |
221 ++dfs; |
222 //cout << "edge: "; |
222 //cout << "edge: "; |
223 if (gw.valid(dfs)) { |
223 if (gw.valid(dfs)) { |
224 cout << edge_name.get(dfs) << /*endl*/", " << |
224 cout << edge_name[dfs] << /*endl*/", " << |
225 node_name.get(gw.aNode(dfs)) << |
225 node_name[gw.aNode(dfs)] << |
226 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
226 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
227 node_name.get(gw.bNode(dfs)) << |
227 node_name[gw.bNode(dfs)] << |
228 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
228 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
229 ": is not newly reached."); |
229 ": is not newly reached."); |
230 } else { |
230 } else { |
231 cout << "invalid" << /*endl*/", " << |
231 cout << "invalid" << /*endl*/", " << |
232 node_name.get(dfs.aNode()) << |
232 node_name[dfs.aNode()] << |
233 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
233 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
234 |
234 |
235 "invalid."; |
235 "invalid."; |
236 } |
236 } |
237 cout << endl; |
237 cout << endl; |
245 |
245 |
246 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
246 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
247 |
247 |
248 cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
248 cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
249 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
249 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
250 cout << node_name.get(n) << ": "; |
250 cout << node_name[n] << ": "; |
251 cout << "out edges: "; |
251 cout << "out edges: "; |
252 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
252 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
253 cout << edge_name.get(e) << " "; |
253 cout << edge_name[e] << " "; |
254 cout << "in edges: "; |
254 cout << "in edges: "; |
255 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
255 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
256 cout << edge_name.get(e) << " "; |
256 cout << edge_name[e] << " "; |
257 cout << endl; |
257 cout << endl; |
258 } |
258 } |
259 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
259 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
260 // cout << edge_name.get(e) << " "; |
260 // cout << edge_name.get(e) << " "; |
261 // } |
261 // } |
265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
266 bfs.pushAndSetReached(t); |
266 bfs.pushAndSetReached(t); |
267 while (!bfs.finished()) { |
267 while (!bfs.finished()) { |
268 //cout << "edge: "; |
268 //cout << "edge: "; |
269 if (gw.valid(GW::OutEdgeIt(bfs))) { |
269 if (gw.valid(GW::OutEdgeIt(bfs))) { |
270 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << |
270 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
271 node_name.get(gw.aNode(bfs)) << |
271 node_name[gw.aNode(bfs)] << |
272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
273 node_name.get(gw.bNode(bfs)) << |
273 node_name[gw.bNode(bfs)] << |
274 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
274 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
275 ": is not newly reached."); |
275 ": is not newly reached."); |
276 } else { |
276 } else { |
277 cout << "invalid" << /*endl*/", " << |
277 cout << "invalid" << /*endl*/", " << |
278 node_name.get(bfs.aNode()) << |
278 node_name[bfs.aNode()] << |
279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
280 |
280 |
281 "invalid."; |
281 "invalid."; |
282 } |
282 } |
283 cout << endl; |
283 cout << endl; |
299 dfs.pushAndSetReached(t); |
299 dfs.pushAndSetReached(t); |
300 while (!dfs.finished()) { |
300 while (!dfs.finished()) { |
301 ++dfs; |
301 ++dfs; |
302 //cout << "edge: "; |
302 //cout << "edge: "; |
303 if (gw.valid(GW::OutEdgeIt(dfs))) { |
303 if (gw.valid(GW::OutEdgeIt(dfs))) { |
304 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << |
304 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
305 node_name.get(gw.aNode(dfs)) << |
305 node_name[gw.aNode(dfs)] << |
306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
307 node_name.get(gw.bNode(dfs)) << |
307 node_name[gw.bNode(dfs)] << |
308 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
308 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
309 ": is not newly reached."); |
309 ": is not newly reached."); |
310 } else { |
310 } else { |
311 cout << "invalid" << /*endl*/", " << |
311 cout << "invalid" << /*endl*/", " << |
312 node_name.get(dfs.aNode()) << |
312 node_name[dfs.aNode()] << |
313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
314 |
314 |
315 "invalid."; |
315 "invalid."; |
316 } |
316 } |
317 cout << endl; |
317 cout << endl; |