Completions.
6 #include <sage_graph.h>
7 #include <lemon/smart_graph.h>
9 #include <lemon/graph_wrapper.h>
11 using namespace lemon;
17 template <typename Graph, typename NodeNameMap>
20 NodeNameMap& node_name_map;
22 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
23 graph(_graph), node_name_map(_node_name_map) { }
24 string operator[](typename Graph::Edge e) const {
26 (node_name_map[graph.source(e)]+"->"+node_name_map[graph.target(e)]);
30 int main (int, char*[])
32 typedef SmartGraph Graph;
33 //typedef SageGraph Graph;
35 typedef Graph::Node Node;
36 typedef Graph::Edge Edge;
47 Graph::NodeMap<string> node_name(G);
48 node_name.set(s, "s");
49 node_name.set(v1, "v1");
50 node_name.set(v2, "v2");
51 node_name.set(v3, "v3");
52 node_name.set(v4, "v4");
53 node_name.set(t, "t");
66 cout << " /--> -------------> "<< endl;
67 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
68 cout << " / | | / /-> \\ "<< endl;
69 cout << " / | | / | ^ \\ "<< endl;
70 cout << "s | | / | | \\-> t "<< endl;
71 cout << " \\ | | / | | /-> "<< endl;
72 cout << " \\ | --/ / | | / "<< endl;
73 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
74 cout << " \\--> -------------> "<< endl;
77 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
79 cout << "bfs and dfs iterator demo on the directed graph" << endl;
80 for(Graph::NodeIt n(G); n!=INVALID; ++n) {
81 cout << node_name[n] << ": ";
82 cout << "out edges: ";
83 for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)
84 cout << edge_name[e] << " ";
86 for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e)
87 cout << edge_name[e] << " ";
91 cout << "bfs from s ..." << endl;
92 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
93 bfs.pushAndSetReached(s);
94 while (!bfs.finished()) {
96 if (Graph::Edge(bfs)!=INVALID) {
97 cout << edge_name[bfs] << /*endl*/", " <<
98 node_name[G.source(bfs)] <<
99 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
100 node_name[G.target(bfs)] <<
101 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
102 ": is not newly reached.");
104 cout << "invalid" << /*endl*/", " <<
105 node_name[bfs.source()] <<
106 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
114 cout << " /--> -------------> "<< endl;
115 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
116 cout << " / | | / /-> \\ "<< endl;
117 cout << " / | | / | ^ \\ "<< endl;
118 cout << "s | | / | | \\-> t "<< endl;
119 cout << " \\ | | / | | /-> "<< endl;
120 cout << " \\ | --/ / | | / "<< endl;
121 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
122 cout << " \\--> -------------> "<< endl;
124 cout << "dfs from s ..." << endl;
125 DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
126 dfs.pushAndSetReached(s);
127 while (!dfs.finished()) {
130 if (Graph::Edge(dfs)!=INVALID) {
131 cout << edge_name[dfs] << /*endl*/", " <<
132 node_name[G.source(dfs)] <<
133 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
134 node_name[G.target(dfs)] <<
135 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
136 ": is not newly reached.");
138 cout << "invalid" << /*endl*/", " <<
139 node_name[dfs.source()] <<
140 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
150 typedef RevGraphWrapper<const Graph> GW;
153 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
155 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
156 for(GW::NodeIt n(gw); n!=INVALID; ++n) {
157 cout << node_name[GW::Node(n)] << ": ";
158 cout << "out edges: ";
159 for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
160 cout << edge_name[e] << " ";
161 cout << "in edges: ";
162 for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
163 cout << edge_name[e] << " ";
167 cout << "bfs from t ..." << endl;
168 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
169 bfs.pushAndSetReached(t);
170 while (!bfs.finished()) {
172 if (GW::Edge(bfs)!=INVALID) {
173 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
174 node_name[gw.source(bfs)] <<
175 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
176 node_name[gw.target(bfs)] <<
177 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
178 ": is not newly reached.");
180 cout << "invalid" << /*endl*/", " <<
181 node_name[bfs.source()] <<
182 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
190 cout << " /--> -------------> "<< endl;
191 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
192 cout << " / | | / /-> \\ "<< endl;
193 cout << " / | | / | ^ \\ "<< endl;
194 cout << "s | | / | | \\-> t "<< endl;
195 cout << " \\ | | / | | /-> "<< endl;
196 cout << " \\ | --/ / | | / "<< endl;
197 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
198 cout << " \\--> -------------> "<< endl;
200 cout << "dfs from t ..." << endl;
201 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
202 dfs.pushAndSetReached(t);
203 while (!dfs.finished()) {
206 if (GW::Edge(dfs)!=INVALID) {
207 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
208 node_name[gw.source(dfs)] <<
209 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
210 node_name[gw.target(dfs)] <<
211 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
212 ": is not newly reached.");
214 cout << "invalid" << /*endl*/", " <<
215 node_name[dfs.source()] <<
216 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
225 // typedef UndirGraphWrapper<const Graph> GW;
228 // EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
230 // cout << "bfs and dfs iterator demo on the undirected graph" << endl;
231 // for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
232 // cout << node_name[GW::Node(n)] << ": ";
233 // cout << "out edges: ";
234 // for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
235 // cout << edge_name[e] << " ";
236 // cout << "in edges: ";
237 // for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
238 // cout << edge_name[e] << " ";
241 // // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
242 // // cout << edge_name.get(e) << " ";
246 // cout << "bfs from t ..." << endl;
247 // BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
248 // bfs.pushAndSetReached(t);
249 // while (!bfs.finished()) {
250 // //cout << "edge: ";
251 // if (gw.valid(GW::OutEdgeIt(bfs))) {
252 // cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
253 // node_name[gw.aNode(bfs)] <<
254 // (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
255 // node_name[gw.bNode(bfs)] <<
256 // (bfs.isBNodeNewlyReached() ? ": is newly reached." :
257 // ": is not newly reached.");
259 // cout << "invalid" << /*endl*/", " <<
260 // node_name[bfs.aNode()] <<
261 // (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
269 // cout << " /--> -------------> "<< endl;
270 // cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
271 // cout << " / | | / /-> \\ "<< endl;
272 // cout << " / | | / | ^ \\ "<< endl;
273 // cout << "s | | / | | \\-> t "<< endl;
274 // cout << " \\ | | / | | /-> "<< endl;
275 // cout << " \\ | --/ / | | / "<< endl;
276 // cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
277 // cout << " \\--> -------------> "<< endl;
279 // cout << "dfs from t ..." << endl;
280 // DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
281 // dfs.pushAndSetReached(t);
282 // while (!dfs.finished()) {
284 // //cout << "edge: ";
285 // if (gw.valid(GW::OutEdgeIt(dfs))) {
286 // cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
287 // node_name[gw.aNode(dfs)] <<
288 // (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
289 // node_name[gw.bNode(dfs)] <<
290 // (dfs.isBNodeNewlyReached() ? ": is newly reached." :
291 // ": is not newly reached.");
293 // cout << "invalid" << /*endl*/", " <<
294 // node_name[dfs.aNode()] <<
295 // (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
306 typedef BidirGraphWrapper<const Graph> GW;
309 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
311 cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
312 // for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
313 // cout << node_name[gw.source(e)] << "->" << node_name[gw.target(e)] << " ";
315 for(GW::NodeIt n(gw); n!=INVALID; ++n) {
316 cout << node_name[GW::Node(n)] << ": ";
317 cout << "out edges: ";
318 for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
319 cout << edge_name[e] << " ";
320 cout << "in edges: ";
321 for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
322 cout << edge_name[e] << " ";
325 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
326 // cout << edge_name.get(e) << " ";
330 cout << "bfs from t ..." << endl;
331 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
332 bfs.pushAndSetReached(t);
333 while (!bfs.finished()) {
335 if (GW::Edge(bfs)!=INVALID) {
336 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
337 node_name[gw.source(bfs)] <<
338 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
339 node_name[gw.target(bfs)] <<
340 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
341 ": is not newly reached.");
343 cout << "invalid" << /*endl*/", " <<
344 node_name[bfs.source()] <<
345 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
353 cout << " /--> -------------> "<< endl;
354 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
355 cout << " / | | / /-> \\ "<< endl;
356 cout << " / | | / | ^ \\ "<< endl;
357 cout << "s | | / | | \\-> t "<< endl;
358 cout << " \\ | | / | | /-> "<< endl;
359 cout << " \\ | --/ / | | / "<< endl;
360 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
361 cout << " \\--> -------------> "<< endl;
363 cout << "dfs from t ..." << endl;
364 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
365 dfs.pushAndSetReached(t);
366 while (!dfs.finished()) {
369 if (GW::Edge(dfs)!=INVALID) {
370 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
371 node_name[gw.source(dfs)] <<
372 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
373 node_name[gw.target(dfs)] <<
374 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
375 ": is not newly reached.");
377 cout << "invalid" << /*endl*/", " <<
378 node_name[dfs.source()] <<
379 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<