Heap concept moved to namespace concept.
6 #include <LEDA/graph.h>
8 #include <list_graph.h>
9 #include <smart_graph.h>
10 #include <bfs_iterator.h>
11 #include <graph_wrapper.h>
12 #include <leda_graph_wrapper.h>
14 using namespace lemon;
19 template <typename Graph, typename NodeNameMap>
22 NodeNameMap& node_name_map;
24 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
25 graph(_graph), node_name_map(_node_name_map) { }
26 string get(typename Graph::Edge e) const {
28 (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e)));
32 int main (int, char*[])
36 //typedef SmartGraph Graph;
37 //typedef ListGraph Graph;
38 typedef LedaGraphWrapper<leda::graph> Graph;
40 typedef Graph::Node Node;
41 typedef Graph::NodeIt NodeIt;
42 typedef Graph::Edge Edge;
43 typedef Graph::EdgeIt EdgeIt;
44 typedef Graph::OutEdgeIt OutEdgeIt;
45 typedef Graph::InEdgeIt InEdgeIt;
58 Graph::NodeMap<string> node_name(G);
59 node_name.set(s, "s");
60 node_name.set(v1, "v1");
61 node_name.set(v2, "v2");
62 node_name.set(v3, "v3");
63 node_name.set(v4, "v4");
64 node_name.set(t, "t");
77 cout << " /--> -------------> "<< endl;
78 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
79 cout << " / | | / /-> \\ "<< endl;
80 cout << " / | | / | ^ \\ "<< endl;
81 cout << "s | | / | | \\-> t "<< endl;
82 cout << " \\ | | / | | /-> "<< endl;
83 cout << " \\ | --/ / | | / "<< endl;
84 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
85 cout << " \\--> -------------> "<< endl;
87 // typedef TrivGraphWrapper<const Graph> CGW;
90 // cout << "bfs and dfs demo on the directed graph" << endl;
91 // for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) {
93 // cout << "out edges: ";
94 // for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
96 // cout << "in edges: ";
97 // for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e)
103 typedef TrivGraphWrapper<const Graph> GW;
106 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
108 cout << "bfs and dfs iterator demo on the directed graph" << endl;
109 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
110 cout << node_name.get(n) << ": ";
111 cout << "out edges: ";
112 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
113 cout << edge_name.get(e) << " ";
114 cout << "in edges: ";
115 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
116 cout << edge_name.get(e) << " ";
120 cout << "bfs from s ..." << endl;
121 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
122 bfs.pushAndSetReached(s);
123 while (!bfs.finished()) {
126 cout << edge_name.get(bfs) << /*endl*/", " <<
127 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
128 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
129 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
130 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
131 ": is not newly reached.");
133 cout << "invalid" << /*endl*/", " <<
134 /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
135 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
143 cout << " /--> -------------> "<< endl;
144 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
145 cout << " / | | / /-> \\ "<< endl;
146 cout << " / | | / | ^ \\ "<< endl;
147 cout << "s | | / | | \\-> t "<< endl;
148 cout << " \\ | | / | | /-> "<< endl;
149 cout << " \\ | --/ / | | / "<< endl;
150 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
151 cout << " \\--> -------------> "<< endl;
153 cout << "dfs from s ..." << endl;
154 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
155 dfs.pushAndSetReached(s);
156 while (!dfs.finished()) {
160 cout << edge_name.get(dfs) << /*endl*/", " <<
161 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
162 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
163 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
164 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
165 ": is not newly reached.");
167 cout << "invalid" << /*endl*/", " <<
168 /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
169 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
179 typedef RevGraphWrapper<const Graph> GW;
182 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
184 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
185 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
186 cout << node_name.get(n) << ": ";
187 cout << "out edges: ";
188 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
189 cout << edge_name.get(e) << " ";
190 cout << "in edges: ";
191 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
192 cout << edge_name.get(e) << " ";
196 cout << "bfs from t ..." << endl;
197 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
198 bfs.pushAndSetReached(t);
199 while (!bfs.finished()) {
202 cout << edge_name.get(bfs) << /*endl*/", " <<
203 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
204 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
205 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
206 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
207 ": is not newly reached.");
209 cout << "invalid" << /*endl*/", " <<
210 /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
211 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
219 cout << " /--> -------------> "<< endl;
220 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
221 cout << " / | | / /-> \\ "<< endl;
222 cout << " / | | / | ^ \\ "<< endl;
223 cout << "s | | / | | \\-> t "<< endl;
224 cout << " \\ | | / | | /-> "<< endl;
225 cout << " \\ | --/ / | | / "<< endl;
226 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
227 cout << " \\--> -------------> "<< endl;
229 cout << "dfs from t ..." << endl;
230 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
231 dfs.pushAndSetReached(t);
232 while (!dfs.finished()) {
236 cout << edge_name.get(dfs) << /*endl*/", " <<
237 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
238 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
239 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
240 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
241 ": is not newly reached.");
243 cout << "invalid" << /*endl*/", " <<
244 /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
245 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
254 typedef UndirGraphWrapper<const Graph> GW;
257 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
259 cout << "bfs and dfs iterator demo on the undirected graph" << endl;
260 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
261 cout << node_name.get(n) << ": ";
262 cout << "out edges: ";
263 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
264 cout << edge_name.get(e) << " ";
265 cout << "in edges: ";
266 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
267 cout << edge_name.get(e) << " ";
271 cout << "bfs from t ..." << endl;
272 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
273 bfs.pushAndSetReached(t);
274 while (!bfs.finished()) {
276 if (wG.valid(GW::OutEdgeIt(bfs))) {
277 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
278 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
280 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
281 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
282 ": is not newly reached.");
284 cout << "invalid" << /*endl*/", " <<
285 /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
286 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
294 cout << " /--> -------------> "<< endl;
295 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
296 cout << " / | | / /-> \\ "<< endl;
297 cout << " / | | / | ^ \\ "<< endl;
298 cout << "s | | / | | \\-> t "<< endl;
299 cout << " \\ | | / | | /-> "<< endl;
300 cout << " \\ | --/ / | | / "<< endl;
301 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
302 cout << " \\--> -------------> "<< endl;
304 cout << "dfs from t ..." << endl;
305 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
306 dfs.pushAndSetReached(t);
307 while (!dfs.finished()) {
310 if (wG.valid(GW::OutEdgeIt(dfs))) {
311 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
312 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
314 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
315 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
316 ": is not newly reached.");
318 cout << "invalid" << /*endl*/", " <<
319 /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
320 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<