Changeset 234:348f8fd374ee in lemon0.x
 Timestamp:
 03/22/04 17:37:10 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@331
 Location:
 src/work
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/iterator_bfs_demo.cc
r174 r234 79 79 80 80 // typedef TrivGraphWrapper<const Graph> CGW; 81 // CGW wG(G);81 // CGW gw(G); 82 82 83 83 // cout << "bfs and dfs demo on the directed graph" << endl; 84 // for(CGW::NodeIt n= wG.first<CGW::NodeIt>(); n.valid(); ++n) {84 // for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) { 85 85 // cout << n << ": "; 86 86 // cout << "out edges: "; 87 // for(CGW::OutEdgeIt e= wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)87 // for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 88 88 // cout << e << " "; 89 89 // cout << "in edges: "; 90 // for(CGW::InEdgeIt e= wG.first<CGW::InEdgeIt>(n); e.valid(); ++e)90 // for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e) 91 91 // cout << e << " "; 92 92 // cout << endl; … … 95 95 { 96 96 typedef TrivGraphWrapper<const Graph> GW; 97 GW wG(G);98 99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name( wG, node_name);97 GW gw(G); 98 99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 100 100 101 101 cout << "bfs and dfs iterator demo on the directed graph" << endl; 102 for(GW::NodeIt n= wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {102 for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { 103 103 cout << node_name.get(n) << ": "; 104 104 cout << "out edges: "; 105 for(GW::OutEdgeIt e= wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))105 for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) 106 106 cout << edge_name.get(e) << " "; 107 107 cout << "in edges: "; 108 for(GW::InEdgeIt e= wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))108 for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) 109 109 cout << edge_name.get(e) << " "; 110 110 cout << endl; … … 112 112 113 113 cout << "bfs from s ..." << endl; 114 BfsIterator5< GW, GW::NodeMap<bool> > bfs( wG);114 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); 115 115 bfs.pushAndSetReached(s); 116 116 while (!bfs.finished()) { 117 117 //cout << "edge: "; 118 if ( wG.valid(bfs)) {118 if (gw.valid(bfs)) { 119 119 cout << edge_name.get(bfs) << /*endl*/", " << 120 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<121 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 122 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<120 node_name.get(gw.aNode(bfs)) << 121 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 122 node_name.get(gw.bNode(bfs)) << 123 123 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 124 124 ": is not newly reached."); 125 125 } else { 126 126 cout << "invalid" << /*endl*/", " << 127 /*" aNode: " <<*/node_name.get(bfs.aNode()) <<128 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 129 /*" bNode: " <<*/127 node_name.get(bfs.aNode()) << 128 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 129 130 130 "invalid."; 131 131 } … … 145 145 146 146 cout << "dfs from s ..." << endl; 147 DfsIterator5< GW, GW::NodeMap<bool> > dfs( wG);147 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); 148 148 dfs.pushAndSetReached(s); 149 149 while (!dfs.finished()) { 150 150 ++dfs; 151 151 //cout << "edge: "; 152 if ( wG.valid(dfs)) {152 if (gw.valid(dfs)) { 153 153 cout << edge_name.get(dfs) << /*endl*/", " << 154 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<155 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 156 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<154 node_name.get(gw.aNode(dfs)) << 155 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 156 node_name.get(gw.bNode(dfs)) << 157 157 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 158 158 ": is not newly reached."); 159 159 } else { 160 160 cout << "invalid" << /*endl*/", " << 161 /*" aNode: " <<*/node_name.get(dfs.aNode()) <<162 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 163 /*" bNode: " <<*/161 node_name.get(dfs.aNode()) << 162 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 163 164 164 "invalid."; 165 165 } … … 170 170 171 171 { 172 typedef RevGraphWrapper<const Graph> GW;173 GW wG(G);174 175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name( wG, node_name);172 typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW; 173 GW gw(G); 174 175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 176 176 177 177 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; 178 for(GW::NodeIt n= wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {178 for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { 179 179 cout << node_name.get(n) << ": "; 180 180 cout << "out edges: "; 181 for(GW::OutEdgeIt e= wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))181 for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) 182 182 cout << edge_name.get(e) << " "; 183 183 cout << "in edges: "; 184 for(GW::InEdgeIt e= wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))184 for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) 185 185 cout << edge_name.get(e) << " "; 186 186 cout << endl; … … 188 188 189 189 cout << "bfs from t ..." << endl; 190 BfsIterator5< GW, GW::NodeMap<bool> > bfs( wG);190 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); 191 191 bfs.pushAndSetReached(t); 192 192 while (!bfs.finished()) { 193 193 //cout << "edge: "; 194 if ( wG.valid(bfs)) {194 if (gw.valid(bfs)) { 195 195 cout << edge_name.get(bfs) << /*endl*/", " << 196 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<197 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 198 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<196 node_name.get(gw.aNode(bfs)) << 197 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 198 node_name.get(gw.bNode(bfs)) << 199 199 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 200 200 ": is not newly reached."); 201 201 } else { 202 202 cout << "invalid" << /*endl*/", " << 203 /*" aNode: " <<*/node_name.get(bfs.aNode()) <<204 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 205 /*" bNode: " <<*/203 node_name.get(bfs.aNode()) << 204 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 205 206 206 "invalid."; 207 207 } … … 221 221 222 222 cout << "dfs from t ..." << endl; 223 DfsIterator5< GW, GW::NodeMap<bool> > dfs( wG);223 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); 224 224 dfs.pushAndSetReached(t); 225 225 while (!dfs.finished()) { 226 226 ++dfs; 227 227 //cout << "edge: "; 228 if ( wG.valid(dfs)) {228 if (gw.valid(dfs)) { 229 229 cout << edge_name.get(dfs) << /*endl*/", " << 230 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<231 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 232 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<230 node_name.get(gw.aNode(dfs)) << 231 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 232 node_name.get(gw.bNode(dfs)) << 233 233 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 234 234 ": is not newly reached."); 235 235 } else { 236 236 cout << "invalid" << /*endl*/", " << 237 /*" aNode: " <<*/node_name.get(dfs.aNode()) <<238 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 239 /*" bNode: " <<*/237 node_name.get(dfs.aNode()) << 238 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 239 240 240 "invalid."; 241 241 } … … 246 246 { 247 247 typedef UndirGraphWrapper<const Graph> GW; 248 GW wG(G);249 250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name( wG, node_name);248 GW gw(G); 249 250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 251 251 252 252 cout << "bfs and dfs iterator demo on the undirected graph" << endl; 253 for(GW::NodeIt n= wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {253 for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { 254 254 cout << node_name.get(n) << ": "; 255 255 cout << "out edges: "; 256 for(GW::OutEdgeIt e= wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))256 for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) 257 257 cout << edge_name.get(e) << " "; 258 258 cout << "in edges: "; 259 for(GW::InEdgeIt e= wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))259 for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) 260 260 cout << edge_name.get(e) << " "; 261 261 cout << endl; … … 263 263 264 264 cout << "bfs from t ..." << endl; 265 BfsIterator5< GW, GW::NodeMap<bool> > bfs( wG);265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); 266 266 bfs.pushAndSetReached(t); 267 267 while (!bfs.finished()) { 268 268 //cout << "edge: "; 269 if ( wG.valid(GW::OutEdgeIt(bfs))) {269 if (gw.valid(GW::OutEdgeIt(bfs))) { 270 270 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << 271 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 273 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<271 node_name.get(gw.aNode(bfs)) << 272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 273 node_name.get(gw.bNode(bfs)) << 274 274 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 275 275 ": is not newly reached."); 276 276 } else { 277 277 cout << "invalid" << /*endl*/", " << 278 /*" aNode: " <<*/node_name.get(bfs.aNode()) <<279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 280 /*" bNode: " <<*/278 node_name.get(bfs.aNode()) << 279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 280 281 281 "invalid."; 282 282 } … … 296 296 297 297 cout << "dfs from t ..." << endl; 298 DfsIterator5< GW, GW::NodeMap<bool> > dfs( wG);298 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); 299 299 dfs.pushAndSetReached(t); 300 300 while (!dfs.finished()) { 301 301 ++dfs; 302 302 //cout << "edge: "; 303 if ( wG.valid(GW::OutEdgeIt(dfs))) {303 if (gw.valid(GW::OutEdgeIt(dfs))) { 304 304 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << 305 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 307 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<305 node_name.get(gw.aNode(dfs)) << 306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 307 node_name.get(gw.bNode(dfs)) << 308 308 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 309 309 ": is not newly reached."); 310 310 } else { 311 311 cout << "invalid" << /*endl*/", " << 312 /*" aNode: " <<*/node_name.get(dfs.aNode()) <<313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 314 /*" bNode: " <<*/312 node_name.get(dfs.aNode()) << 313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 314 315 315 "invalid."; 316 316 } 
src/work/marci/graph_wrapper.h
r231 r234 241 241 // }; 242 242 243 template<typename Graph> 243 template<typename /*Graph*/GraphWrapper 244 /*=typename GraphWrapperSkeleton< TrivGraphWrapper<Graph>*/ > 244 245 class RevGraphWrapper : 245 public GraphWrapper Skeleton< TrivGraphWrapper<Graph> >{246 public GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/ { 246 247 protected: 247 248 //Graph* graph; … … 254 255 255 256 //typedef typename Graph::Edge Edge; 256 typedef typename GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::OutEdgeIt InEdgeIt;257 typedef typename GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::InEdgeIt OutEdgeIt;257 typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::OutEdgeIt InEdgeIt; 258 typedef typename GraphWrapper/*typename GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/::InEdgeIt OutEdgeIt; 258 259 //typedef typename Graph::SymEdgeIt SymEdgeIt; 259 260 //typedef typename Graph::EdgeIt EdgeIt; 260 261 261 262 //RevGraphWrapper() : graph(0) { } 262 RevGraphWrapper(Graph & _graph) : GraphWrapperSkeleton< TrivGraphWrapper<Graph> >(TrivGraphWrapper<Graph>(_graph)) { }263 RevGraphWrapper(GraphWrapper _gw/*BaseGraph& _graph*/) : GraphWrapper/*GraphWrapperSkeleton< TrivGraphWrapper<Graph> >*/(_gw/*TrivGraphWrapper<Graph>(_graph)*/) { } 263 264 264 265 //void setGraph(Graph& _graph) { graph = &_graph; } … … 305 306 306 307 template<typename T> class NodeMap : 307 public GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::NodeMap<T>308 public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T> 308 309 { 309 310 public: 310 NodeMap(const RevGraphWrapper<Graph >& _G) :311 GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::NodeMap<T>(_G) { }312 NodeMap(const RevGraphWrapper<Graph >& _G, T a) :313 GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::NodeMap<T>(_G, a) { }311 NodeMap(const RevGraphWrapper<GraphWrapper>& _gw) : 312 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw) { } 313 NodeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) : 314 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::NodeMap<T>(_gw, a) { } 314 315 }; 315 316 316 317 template<typename T> class EdgeMap : 317 public GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::EdgeMap<T> {318 public: 319 EdgeMap(const RevGraphWrapper<Graph >& _G) :320 GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::EdgeMap<T>(_G) { }321 EdgeMap(const RevGraphWrapper<Graph >& _G, T a) :322 GraphWrapper Skeleton< TrivGraphWrapper<Graph> >::EdgeMap<T>(_G, a) { }318 public GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T> { 319 public: 320 EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw) : 321 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw) { } 322 EdgeMap(const RevGraphWrapper<GraphWrapper>& _gw, T a) : 323 GraphWrapper/*Skeleton< TrivGraphWrapper<Graph> >*/::EdgeMap<T>(_gw, a) { } 323 324 }; 324 325 };
Note: See TracChangeset
for help on using the changeset viewer.