Changeset 158:4f54d89fa9d2 in lemon-0.x for src
- Timestamp:
- 03/08/04 13:29:07 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@223
- Location:
- src/work
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/bfs_iterator.hh
r148 r158 624 624 625 625 626 template <typename GraphWrapper, typename OutEdgeIt,626 template <typename GraphWrapper, /*typename OutEdgeIt,*/ 627 627 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > 628 628 class BfsIterator5 { 629 629 typedef typename GraphWrapper::NodeIt NodeIt; 630 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 630 631 GraphWrapper G; 631 632 std::queue<NodeIt> bfs_queue; … … 641 642 G(_G), reached(*(new ReachedMap(G /*, false*/))), 642 643 own_reached_map(true) { } 644 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G, 645 // ReachedMap& _reached) : 646 // G(_G), reached(_reached), 647 // own_reached_map(false) { } 648 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : 649 // G(_G), reached(*(new ReachedMap(G /*, false*/))), 650 // own_reached_map(true) { } 643 651 ~BfsIterator5() { if (own_reached_map) delete &reached; } 644 652 void pushAndSetReached(NodeIt s) { … … 661 669 } 662 670 } 663 BfsIterator5<GraphWrapper, OutEdgeIt,ReachedMap>&671 BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 664 672 operator++() { 665 673 if (G.valid(actual_edge)/*.valid()*/) { … … 759 767 }; 760 768 761 template <typename GraphWrapper, typename OutEdgeIt,769 template <typename GraphWrapper, /*typename OutEdgeIt,*/ 762 770 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > 763 771 class DfsIterator5 { 764 772 typedef typename GraphWrapper::NodeIt NodeIt; 773 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 765 774 GraphWrapper G; 766 775 std::stack<OutEdgeIt> dfs_stack; … … 783 792 dfs_stack.push(G.template first<OutEdgeIt>(s)); 784 793 } 785 DfsIterator5<GraphWrapper, OutEdgeIt,ReachedMap>&794 DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 786 795 operator++() { 787 796 actual_edge=dfs_stack.top(); -
src/work/iterator_bfs_demo.cc
r107 r158 8 8 9 9 using namespace hugo; 10 using std::cout; 11 using std::endl; 12 using std::string; 13 14 template <typename Graph, typename NodeNameMap> 15 class EdgeNameMap { 16 Graph& graph; 17 NodeNameMap& node_name_map; 18 public: 19 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 20 graph(_graph), node_name_map(_node_name_map) { } 21 string get(typename Graph::EdgeIt e) const { 22 return 23 (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); 24 } 25 }; 10 26 11 27 int main (int, char*[]) … … 13 29 typedef ListGraph::NodeIt NodeIt; 14 30 typedef ListGraph::EdgeIt EdgeIt; 15 typedef ListGraph::EachNodeIt EachNodeIt;16 typedef ListGraph::EachEdgeIt EachEdgeIt;17 typedef ListGraph::OutEdgeIt OutEdgeIt;18 typedef ListGraph::InEdgeIt InEdgeIt;19 typedef ListGraph::SymEdgeIt SymEdgeIt;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; 20 36 21 37 ListGraph G; … … 28 44 NodeIt t=G.addNode(); 29 45 46 ListGraph::NodeMap<string> node_name(G); 47 node_name.set(s, "s"); 48 node_name.set(v1, "v1"); 49 node_name.set(v2, "v2"); 50 node_name.set(v3, "v3"); 51 node_name.set(v4, "v4"); 52 node_name.set(t, "t"); 53 30 54 G.addEdge(s, v1); 31 55 G.addEdge(s, v2); … … 39 63 G.addEdge(v4, t); 40 64 41 std::cout << "bfs and dfs demo on the directed graph" << std::endl; 42 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 43 std::cout << i << ": "; 44 std::cout << "out edges: "; 45 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) 46 std::cout << j << " "; 47 std::cout << "in edges: "; 48 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) 49 std::cout << j << " "; 50 std::cout << std::endl; 51 } 65 cout << " /--> -------------> "<< endl; 66 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 67 cout << " / | | / /-> \\ "<< endl; 68 cout << " / | | / | ^ \\ "<< endl; 69 cout << "s | | / | | \\-> t "<< endl; 70 cout << " \\ | | / | | /-> "<< endl; 71 cout << " \\ | --/ / | | / "<< endl; 72 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 73 cout << " \\--> -------------> "<< endl; 52 74 53 { 54 std::cout << "iterator bfs demo 4 ..." << std::endl; 55 BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); 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; 137 // CGW wG(G); 138 139 // cout << "bfs and dfs demo on the directed graph" << endl; 140 // for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) { 141 // cout << n << ": "; 142 // cout << "out edges: "; 143 // for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 144 // cout << e << " "; 145 // cout << "in edges: "; 146 // for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e) 147 // cout << e << " "; 148 // cout << endl; 149 // } 150 151 { 152 typedef TrivGraphWrapper<const ListGraph> GW; 153 GW wG(G); 154 155 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); 156 157 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)) { 159 cout << node_name.get(n) << ": "; 160 cout << "out edges: "; 161 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 162 cout << edge_name.get(e) << " "; 163 cout << "in edges: "; 164 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 165 cout << edge_name.get(e) << " "; 166 cout << endl; 167 } 168 169 cout << "bfs from s ..." << endl; 170 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); 56 171 bfs.pushAndSetReached(s); 57 172 while (!bfs.finished()) { 58 if (OutEdgeIt(bfs).valid()) { 59 std::cout << "OutEdgeIt: " << bfs; 60 std::cout << " aNode: " << G.aNode(bfs); 61 std::cout << " bNode: " << G.bNode(bfs) << " "; 62 } else { 63 std::cout << "OutEdgeIt: " << "invalid"; 64 std::cout << " aNode: " << bfs.aNode(); 65 std::cout << " bNode: " << "invalid" << " "; 66 } 67 if (bfs.isBNodeNewlyReached()) { 68 std::cout << "bNodeIsNewlyReached "; 69 } else { 70 std::cout << "bNodeIsNotNewlyReached "; 71 } 72 if (bfs.isANodeExamined()) { 73 std::cout << "aNodeIsExamined "; 74 } else { 75 std::cout << "aNodeIsNotExamined "; 76 } 77 std::cout<<std::endl; 173 //cout << "edge: "; 174 if (wG.valid(bfs)) { 175 cout << edge_name.get(bfs) << /*endl*/", " << 176 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 177 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 178 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 179 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 180 ": is not newly reached."); 181 } else { 182 cout << "invalid" << /*endl*/", " << 183 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 184 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 185 /*" bNode: " <<*/ 186 "invalid."; 187 } 188 cout << endl; 78 189 ++bfs; 79 190 } 80 } 81 82 { 83 std::cout << "iterator dfs demo 4 ..." << std::endl; 84 DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G); 191 192 cout << " /--> -------------> "<< endl; 193 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 194 cout << " / | | / /-> \\ "<< endl; 195 cout << " / | | / | ^ \\ "<< endl; 196 cout << "s | | / | | \\-> t "<< endl; 197 cout << " \\ | | / | | /-> "<< endl; 198 cout << " \\ | --/ / | | / "<< endl; 199 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 200 cout << " \\--> -------------> "<< endl; 201 202 cout << "dfs from s ..." << endl; 203 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); 85 204 dfs.pushAndSetReached(s); 86 205 while (!dfs.finished()) { 87 206 ++dfs; 88 if (OutEdgeIt(dfs).valid()) { 89 std::cout << "OutEdgeIt: " << dfs; 90 std::cout << " aNode: " << G.aNode(dfs); 91 std::cout << " bNode: " << G.bNode(dfs) << " "; 92 } else { 93 std::cout << "OutEdgeIt: " << "invalid"; 94 std::cout << " aNode: " << dfs.aNode(); 95 std::cout << " bNode: " << "invalid" << " "; 96 } 97 if (dfs.isBNodeNewlyReached()) { 98 std::cout << "bNodeIsNewlyReached "; 99 } else { 100 std::cout << "bNodeIsNotNewlyReached "; 101 } 102 if (dfs.isANodeExamined()) { 103 std::cout << "aNodeIsExamined "; 104 } else { 105 std::cout << "aNodeIsNotExamined "; 106 } 107 std::cout<<std::endl; 108 //++dfs; 109 } 110 } 111 112 113 typedef ConstTrivGraphWrapper<ListGraph> CTGW; 114 CTGW wG(G); 115 116 std::cout << "bfs and dfs demo on the directed graph" << std::endl; 117 for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { 118 std::cout << i << ": "; 119 std::cout << "out edges: "; 120 for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) 121 std::cout << j << " "; 122 std::cout << "in edges: "; 123 for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) 124 std::cout << j << " "; 125 std::cout << std::endl; 126 } 127 128 129 { 130 std::cout << "iterator bfs demo 5 ..." << std::endl; 131 BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG); 132 bfs.pushAndSetReached(s); 207 //cout << "edge: "; 208 if (wG.valid(dfs)) { 209 cout << edge_name.get(dfs) << /*endl*/", " << 210 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 211 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 212 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 213 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 214 ": is not newly reached."); 215 } else { 216 cout << "invalid" << /*endl*/", " << 217 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 218 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 219 /*" bNode: " <<*/ 220 "invalid."; 221 } 222 cout << endl; 223 } 224 } 225 226 227 { 228 typedef RevGraphWrapper<const ListGraph> GW; 229 GW wG(G); 230 231 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); 232 233 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)) { 235 cout << node_name.get(n) << ": "; 236 cout << "out edges: "; 237 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 238 cout << edge_name.get(e) << " "; 239 cout << "in edges: "; 240 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 241 cout << edge_name.get(e) << " "; 242 cout << endl; 243 } 244 245 cout << "bfs from t ..." << endl; 246 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); 247 bfs.pushAndSetReached(t); 133 248 while (!bfs.finished()) { 134 if (OutEdgeIt(bfs).valid()) { 135 std::cout << "OutEdgeIt: " << bfs; 136 std::cout << " aNode: " << wG.aNode(bfs); 137 std::cout << " bNode: " << wG.bNode(bfs) << " "; 138 } else { 139 std::cout << "OutEdgeIt: " << "invalid"; 140 std::cout << " aNode: " << bfs.aNode(); 141 std::cout << " bNode: " << "invalid" << " "; 142 } 143 if (bfs.isBNodeNewlyReached()) { 144 std::cout << "bNodeIsNewlyReached "; 145 } else { 146 std::cout << "bNodeIsNotNewlyReached "; 147 } 148 if (bfs.isANodeExamined()) { 149 std::cout << "aNodeIsExamined "; 150 } else { 151 std::cout << "aNodeIsNotExamined "; 152 } 153 std::cout<<std::endl; 249 //cout << "edge: "; 250 if (wG.valid(bfs)) { 251 cout << edge_name.get(bfs) << /*endl*/", " << 252 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 253 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 254 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 255 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 256 ": is not newly reached."); 257 } else { 258 cout << "invalid" << /*endl*/", " << 259 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 260 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 261 /*" bNode: " <<*/ 262 "invalid."; 263 } 264 cout << endl; 154 265 ++bfs; 155 266 } 156 } 157 267 268 cout << " /--> -------------> "<< endl; 269 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 270 cout << " / | | / /-> \\ "<< endl; 271 cout << " / | | / | ^ \\ "<< endl; 272 cout << "s | | / | | \\-> t "<< endl; 273 cout << " \\ | | / | | /-> "<< endl; 274 cout << " \\ | --/ / | | / "<< endl; 275 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 276 cout << " \\--> -------------> "<< endl; 277 278 cout << "dfs from t ..." << endl; 279 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); 280 dfs.pushAndSetReached(t); 281 while (!dfs.finished()) { 282 ++dfs; 283 //cout << "edge: "; 284 if (wG.valid(dfs)) { 285 cout << edge_name.get(dfs) << /*endl*/", " << 286 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 287 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 288 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 289 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 290 ": is not newly reached."); 291 } else { 292 cout << "invalid" << /*endl*/", " << 293 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 294 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 295 /*" bNode: " <<*/ 296 "invalid."; 297 } 298 cout << endl; 299 } 300 } 301 302 { 303 typedef UndirGraphWrapper<const ListGraph> GW; 304 GW wG(G); 305 306 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); 307 308 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)) { 310 cout << node_name.get(n) << ": "; 311 cout << "out edges: "; 312 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 313 cout << edge_name.get(e) << " "; 314 cout << "in edges: "; 315 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 316 cout << edge_name.get(e) << " "; 317 cout << endl; 318 } 319 320 cout << "bfs from t ..." << endl; 321 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); 322 bfs.pushAndSetReached(t); 323 while (!bfs.finished()) { 324 //cout << "edge: "; 325 if (wG.valid(GW::OutEdgeIt(bfs))) { 326 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << 327 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 328 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 329 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 330 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 331 ": is not newly reached."); 332 } else { 333 cout << "invalid" << /*endl*/", " << 334 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 335 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 336 /*" bNode: " <<*/ 337 "invalid."; 338 } 339 cout << endl; 340 ++bfs; 341 } 342 343 cout << " /--> -------------> "<< endl; 344 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 345 cout << " / | | / /-> \\ "<< endl; 346 cout << " / | | / | ^ \\ "<< endl; 347 cout << "s | | / | | \\-> t "<< endl; 348 cout << " \\ | | / | | /-> "<< endl; 349 cout << " \\ | --/ / | | / "<< endl; 350 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 351 cout << " \\--> -------------> "<< endl; 352 353 cout << "dfs from t ..." << endl; 354 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); 355 dfs.pushAndSetReached(t); 356 while (!dfs.finished()) { 357 ++dfs; 358 //cout << "edge: "; 359 if (wG.valid(GW::OutEdgeIt(dfs))) { 360 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << 361 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 362 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 363 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 364 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 365 ": is not newly reached."); 366 } else { 367 cout << "invalid" << /*endl*/", " << 368 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 369 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 370 /*" bNode: " <<*/ 371 "invalid."; 372 } 373 cout << endl; 374 } 375 } 158 376 159 377 return 0; -
src/work/marci/graph_wrapper.h
r156 r158 63 63 public: 64 64 NodeMap(const TrivGraphWrapper<Graph>& _G) : 65 Graph::NodeMap<T>( *(_G.G)) { }65 Graph::NodeMap<T>(_G.getGraph()) { } 66 66 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 67 Graph::NodeMap<T>( *(_G.G), a) { }67 Graph::NodeMap<T>(_G.getGraph(), a) { } 68 68 }; 69 69 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 70 70 public: 71 71 EdgeMap(const TrivGraphWrapper<Graph>& _G) : 72 Graph::EdgeMap<T>( *(_G.G)) { }72 Graph::EdgeMap<T>(_G.getGraph()) { } 73 73 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : 74 Graph::EdgeMap<T>( *(_G.G), a) { }74 Graph::EdgeMap<T>(_G.getGraph(), a) { } 75 75 }; 76 76 … … 141 141 public: 142 142 NodeMap(const RevGraphWrapper<Graph>& _G) : 143 Graph::NodeMap<T>( *(_G.G)) { }143 Graph::NodeMap<T>(_G.getGraph()) { } 144 144 NodeMap(const RevGraphWrapper<Graph>& _G, T a) : 145 Graph::NodeMap<T>( *(_G.G), a) { }145 Graph::NodeMap<T>(_G.getGraph(), a) { } 146 146 }; 147 147 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 148 148 public: 149 149 EdgeMap(const RevGraphWrapper<Graph>& _G) : 150 Graph::EdgeMap<T>( *(_G.G)) { }150 Graph::EdgeMap<T>(_G.getGraph()) { } 151 151 EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : 152 Graph::EdgeMap<T>( *(_G.G), a) { }152 Graph::EdgeMap<T>(_G.getGraph(), a) { } 153 153 }; 154 154 … … 159 159 RevGraphWrapper(Graph& _graph) : graph(&_graph) { } 160 160 }; 161 162 163 template<typename Graph> 164 class UndirGraphWrapper { 165 Graph* graph; 166 167 public: 168 typedef Graph BaseGraph; 169 170 typedef typename Graph::NodeIt NodeIt; 171 typedef typename Graph::EachNodeIt EachNodeIt; 172 173 //typedef typename Graph::EdgeIt EdgeIt; 174 //typedef typename Graph::OutEdgeIt OutEdgeIt; 175 //typedef typename Graph::InEdgeIt InEdgeIt; 176 //typedef typename Graph::SymEdgeIt SymEdgeIt; 177 //typedef typename Graph::EachEdgeIt EachEdgeIt; 178 179 //private: 180 typedef typename Graph::EdgeIt GraphEdgeIt; 181 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 182 typedef typename Graph::InEdgeIt GraphInEdgeIt; 183 //public: 184 185 class EdgeIt { 186 friend class UndirGraphWrapper<Graph>; 187 bool out_or_in; //true iff out 188 GraphOutEdgeIt out; 189 GraphInEdgeIt in; 190 public: 191 EdgeIt() : out_or_in(true), out(), in() { } 192 operator GraphEdgeIt() const { 193 if (out_or_in) return(out); else return(in); 194 } 195 }; 196 197 class OutEdgeIt : public EdgeIt { 198 friend class UndirGraphWrapper<Graph>; 199 //bool out_or_in; //true iff out 200 //GraphOutEdgeIt out; 201 //GraphInEdgeIt in; 202 public: 203 OutEdgeIt() : EdgeIt() { } 204 OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() { 205 _G.graph->getFirst(out, n); 206 if (!(_G.graph->valid(out))) { 207 out_or_in=false; 208 _G.graph->getFirst(in, n); 209 } 210 } 211 }; 212 213 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { 214 e.out_or_in=true; 215 graph->getFirst(e.out, n); 216 if (!(graph->valid(e.out))) { 217 e.out_or_in=false; 218 graph->getFirst(e.in, n); 219 } 220 return e; 221 } 222 223 OutEdgeIt& next(OutEdgeIt& e) const { 224 if (e.out_or_in) { 225 NodeIt n=graph->tail(e.out); 226 graph->next(e.out); 227 if (!graph->valid(e.out)) { 228 e.out_or_in=false; 229 graph->getFirst(e.in, n); 230 } 231 } else { 232 graph->next(e.in); 233 } 234 return e; 235 } 236 237 NodeIt aNode(const OutEdgeIt& e) const { 238 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } 239 NodeIt bNode(const OutEdgeIt& e) const { 240 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } 241 242 typedef OutEdgeIt InEdgeIt; 243 244 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); } 245 // template<typename I, typename P> I& getFirst(I& i, const P& p) const { 246 // return graph->getFirst(i, p); } 247 248 template<typename I> I getNext(const I& i) const { 249 return graph->getNext(i); } 250 template<typename I> I& next(I &i) const { return graph->next(i); } 251 252 template< typename It > It first() const { 253 It e; getFirst(e); return e; } 254 255 template< typename It > It first(const NodeIt& v) const { 256 It e; getFirst(e, v); return e; } 257 258 NodeIt head(const EdgeIt& e) const { return graph->head(e); } 259 NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } 260 261 template<typename I> bool valid(const I& i) const 262 { return graph->valid(i); } 263 264 //template<typename I> void setInvalid(const I &i); 265 //{ return graph->setInvalid(i); } 266 267 int nodeNum() const { return graph->nodeNum(); } 268 int edgeNum() const { return graph->edgeNum(); } 269 270 // template<typename I> NodeIt aNode(const I& e) const { 271 // return graph->aNode(e); } 272 // template<typename I> NodeIt bNode(const I& e) const { 273 // return graph->bNode(e); } 274 275 NodeIt addNode() const { return graph->addNode(); } 276 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 277 return graph->addEdge(tail, head); } 278 279 template<typename I> void erase(const I& i) const { graph->erase(i); } 280 281 void clear() const { graph->clear(); } 282 283 template<typename T> class NodeMap : public Graph::NodeMap<T> { 284 public: 285 NodeMap(const UndirGraphWrapper<Graph>& _G) : 286 Graph::NodeMap<T>(_G.getGraph()) { } 287 NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : 288 Graph::NodeMap<T>(_G.getGraph(), a) { } 289 }; 290 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 291 public: 292 EdgeMap(const UndirGraphWrapper<Graph>& _G) : 293 Graph::EdgeMap<T>(_G.getGraph()) { } 294 EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) : 295 Graph::EdgeMap<T>(_G.getGraph(), a) { } 296 }; 297 298 void setGraph(Graph& _graph) { graph = &_graph; } 299 Graph& getGraph() const { return (*graph); } 300 301 //TrivGraphWrapper() : graph(0) { } 302 UndirGraphWrapper(Graph& _graph) : graph(&_graph) { } 303 }; 304 161 305 162 306 … … 248 392 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 249 393 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { } 394 void setGraph(Graph& _graph) { graph = &_graph; } 395 Graph& getGraph() const { return (*graph); } 250 396 class EdgeIt; 251 397 class OutEdgeIt; … … 500 646 public: 501 647 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) 502 : Graph::NodeMap<T>( *(_G.G)) { }648 : Graph::NodeMap<T>(_G.getGraph()) { } 503 649 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, 504 T a) : Graph::NodeMap<T>( *(_G.G), a) { }650 T a) : Graph::NodeMap<T>(_G.getGraph(), a) { } 505 651 }; 506 652 … … 519 665 typename Graph::EdgeMap<T> forward_map, backward_map; 520 666 public: 521 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map( *(_G.G)), backward_map(*(_G.G)) { }522 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map( *(_G.G), a), backward_map(*(_G.G), a) { }667 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { } 668 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { } 523 669 void set(EdgeIt e, T a) { 524 670 if (e.out_or_in)
Note: See TracChangeset
for help on using the changeset viewer.