86 // cout << e << " "; |
86 // cout << e << " "; |
87 // cout << endl; |
87 // cout << endl; |
88 // } |
88 // } |
89 |
89 |
90 { |
90 { |
91 typedef TrivGraphWrapper<const Graph> GW; |
91 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name); |
92 GW gw(G); |
|
93 |
|
94 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
|
95 |
92 |
96 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
93 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
97 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
94 for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { |
98 cout << node_name[n] << ": "; |
95 cout << node_name[n] << ": "; |
99 cout << "out edges: "; |
96 cout << "out edges: "; |
100 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
97 for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) |
101 cout << edge_name[e] << " "; |
98 cout << edge_name[e] << " "; |
102 cout << "in edges: "; |
99 cout << "in edges: "; |
103 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
100 for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e)) |
104 cout << edge_name[e] << " "; |
101 cout << edge_name[e] << " "; |
105 cout << endl; |
102 cout << endl; |
106 } |
103 } |
107 |
104 |
108 cout << "bfs from s ..." << endl; |
105 cout << "bfs from s ..." << endl; |
109 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
106 BfsIterator5< Graph, Graph::NodeMap<bool> > bfs(G); |
110 bfs.pushAndSetReached(s); |
107 bfs.pushAndSetReached(s); |
111 while (!bfs.finished()) { |
108 while (!bfs.finished()) { |
112 //cout << "edge: "; |
109 //cout << "edge: "; |
113 if (gw.valid(bfs)) { |
110 if (G.valid(bfs)) { |
114 cout << edge_name[bfs] << /*endl*/", " << |
111 cout << edge_name[bfs] << /*endl*/", " << |
115 node_name[gw.aNode(bfs)] << |
112 node_name[G.aNode(bfs)] << |
116 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
113 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
117 node_name[gw.bNode(bfs)] << |
114 node_name[G.bNode(bfs)] << |
118 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
115 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
119 ": is not newly reached."); |
116 ": is not newly reached."); |
120 } else { |
117 } else { |
121 cout << "invalid" << /*endl*/", " << |
118 cout << "invalid" << /*endl*/", " << |
122 node_name[bfs.aNode()] << |
119 node_name[bfs.aNode()] << |
137 cout << " \\ | --/ / | | / "<< endl; |
134 cout << " \\ | --/ / | | / "<< endl; |
138 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
135 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
139 cout << " \\--> -------------> "<< endl; |
136 cout << " \\--> -------------> "<< endl; |
140 |
137 |
141 cout << "dfs from s ..." << endl; |
138 cout << "dfs from s ..." << endl; |
142 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
139 DfsIterator5< Graph, Graph::NodeMap<bool> > dfs(G); |
143 dfs.pushAndSetReached(s); |
140 dfs.pushAndSetReached(s); |
144 while (!dfs.finished()) { |
141 while (!dfs.finished()) { |
145 ++dfs; |
142 ++dfs; |
146 //cout << "edge: "; |
143 //cout << "edge: "; |
147 if (gw.valid(dfs)) { |
144 if (G.valid(dfs)) { |
148 cout << edge_name[dfs] << /*endl*/", " << |
145 cout << edge_name[dfs] << /*endl*/", " << |
149 node_name[gw.aNode(dfs)] << |
146 node_name[G.aNode(dfs)] << |
150 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
147 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
151 node_name[gw.bNode(dfs)] << |
148 node_name[G.bNode(dfs)] << |
152 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
149 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
153 ": is not newly reached."); |
150 ": is not newly reached."); |
154 } else { |
151 } else { |
155 cout << "invalid" << /*endl*/", " << |
152 cout << "invalid" << /*endl*/", " << |
156 node_name[dfs.aNode()] << |
153 node_name[dfs.aNode()] << |