Changeset 174:44700ed9ffaa in lemon0.x for src/work/iterator_bfs_demo.cc
 Timestamp:
 03/12/04 10:19:54 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@250
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/iterator_bfs_demo.cc
r158 r174 1 // * c++ * 1 2 #include <iostream> 2 3 #include <vector> 3 4 #include <string> 4 5 5 #include <list_graph.hh> 6 #include <bfs_iterator.hh> 6 #include <list_graph.h> 7 #include <smart_graph.h> 8 #include <bfs_iterator.h> 7 9 #include <graph_wrapper.h> 8 10 … … 19 21 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 20 22 graph(_graph), node_name_map(_node_name_map) { } 21 string get(typename Graph::Edge Ite) const {23 string get(typename Graph::Edge e) const { 22 24 return 23 25 (node_name_map.get(graph.tail(e))+">"+node_name_map.get(graph.head(e))); … … 27 29 int main (int, char*[]) 28 30 { 29 typedef ListGraph::NodeIt NodeIt; 30 typedef ListGraph::EdgeIt EdgeIt; 31 //typedef ListGraph::EachNodeIt EachNodeIt; 32 //typedef ListGraph::EachEdgeIt EachEdgeIt; 33 //typedef ListGraph::OutEdgeIt OutEdgeIt; 34 //typedef ListGraph::InEdgeIt InEdgeIt; 35 //typedef ListGraph::SymEdgeIt SymEdgeIt; 31 //typedef SmartGraph Graph; 32 typedef ListGraph Graph; 33 34 typedef Graph::Node Node; 35 typedef Graph::Edge Edge; 36 //typedef Graph::NodeIt NodeIt; 37 //typedef Graph::EdgeIt EdgeIt; 38 //typedef Graph::OutEdgeIt OutEdgeIt; 39 //typedef Graph::InEdgeIt InEdgeIt; 40 //typedef Graph::SymEdgeIt SymEdgeIt; 36 41 37 ListGraph G;38 39 Node Its=G.addNode();40 Node Itv1=G.addNode();41 Node Itv2=G.addNode();42 Node Itv3=G.addNode();43 Node Itv4=G.addNode();44 Node Itt=G.addNode();42 Graph G; 43 44 Node s=G.addNode(); 45 Node v1=G.addNode(); 46 Node v2=G.addNode(); 47 Node v3=G.addNode(); 48 Node v4=G.addNode(); 49 Node t=G.addNode(); 45 50 46 ListGraph::NodeMap<string> node_name(G);51 Graph::NodeMap<string> node_name(G); 47 52 node_name.set(s, "s"); 48 53 node_name.set(v1, "v1"); … … 73 78 cout << " \\> > "<< endl; 74 79 75 /* 76 { 77 cout << "iterator bfs demo 4 ..." << endl; 78 BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); 79 bfs.pushAndSetReached(s); 80 while (!bfs.finished()) { 81 if (OutEdgeIt(bfs).valid()) { 82 cout << "OutEdgeIt: " << bfs; 83 cout << " aNode: " << G.aNode(bfs); 84 cout << " bNode: " << G.bNode(bfs) << " "; 85 } else { 86 cout << "OutEdgeIt: " << "invalid"; 87 cout << " aNode: " << bfs.aNode(); 88 cout << " bNode: " << "invalid" << " "; 89 } 90 if (bfs.isBNodeNewlyReached()) { 91 cout << "bNodeIsNewlyReached "; 92 } else { 93 cout << "bNodeIsNotNewlyReached "; 94 } 95 if (bfs.isANodeExamined()) { 96 cout << "aNodeIsExamined "; 97 } else { 98 cout << "aNodeIsNotExamined "; 99 } 100 cout << endl; 101 ++bfs; 102 } 103 } 104 105 { 106 cout << "iterator dfs demo 4 ..." << endl; 107 DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G); 108 dfs.pushAndSetReached(s); 109 while (!dfs.finished()) { 110 ++dfs; 111 if (OutEdgeIt(dfs).valid()) { 112 cout << "OutEdgeIt: " << dfs; 113 cout << " aNode: " << G.aNode(dfs); 114 cout << " bNode: " << G.bNode(dfs) << " "; 115 } else { 116 cout << "OutEdgeIt: " << "invalid"; 117 cout << " aNode: " << dfs.aNode(); 118 cout << " bNode: " << "invalid" << " "; 119 } 120 if (dfs.isBNodeNewlyReached()) { 121 cout << "bNodeIsNewlyReached "; 122 } else { 123 cout << "bNodeIsNotNewlyReached "; 124 } 125 if (dfs.isANodeExamined()) { 126 cout << "aNodeIsExamined "; 127 } else { 128 cout << "aNodeIsNotExamined "; 129 } 130 cout << endl; 131 //++dfs; 132 } 133 } 134 */ 135 136 // typedef TrivGraphWrapper<const ListGraph> CGW; 80 // typedef TrivGraphWrapper<const Graph> CGW; 137 81 // CGW wG(G); 138 82 139 83 // cout << "bfs and dfs demo on the directed graph" << endl; 140 // for(CGW:: EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) {84 // for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) { 141 85 // cout << n << ": "; 142 86 // cout << "out edges: "; … … 150 94 151 95 { 152 typedef TrivGraphWrapper<const ListGraph> GW;96 typedef TrivGraphWrapper<const Graph> GW; 153 97 GW wG(G); 154 98 155 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); 156 100 157 101 cout << "bfs and dfs iterator demo on the directed graph" << endl; 158 for(GW:: EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {102 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 159 103 cout << node_name.get(n) << ": "; 160 104 cout << "out edges: "; … … 226 170 227 171 { 228 typedef RevGraphWrapper<const ListGraph> GW;172 typedef RevGraphWrapper<const Graph> GW; 229 173 GW wG(G); 230 174 231 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); 232 176 233 177 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; 234 for(GW:: EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {178 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 235 179 cout << node_name.get(n) << ": "; 236 180 cout << "out edges: "; … … 301 245 302 246 { 303 typedef UndirGraphWrapper<const ListGraph> GW;247 typedef UndirGraphWrapper<const Graph> GW; 304 248 GW wG(G); 305 249 306 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); 307 251 308 252 cout << "bfs and dfs iterator demo on the undirected graph" << endl; 309 for(GW:: EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {253 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 310 254 cout << node_name.get(n) << ": "; 311 255 cout << "out edges: ";
Note: See TracChangeset
for help on using the changeset viewer.