Changeset 311:6635b11938fe in lemon0.x
 Timestamp:
 04/06/04 14:00:34 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@429
 Location:
 src/work
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/makefile
r220 r311 1 1 CXX3 := $(shell type p g++3.3  type p g++3.2  type p g++3.0  type p g++3  echo g++) 2 2 CXX2 = g++2.95 3 CXXFLAGS = W Wall ansi pedantic O3 I. I.. I../marci I../alpar I../../include 3 CXX=$(CXX3) 4 CC=$(CXX) 5 INCLUDEDIRS ?= I../../include I.. I../{marci,jacint,alpar,klao,akos,athos} 6 CXXFLAGS = W Wall ansi pedantic O3 $(INCLUDEDIRS) 4 7 LEDAROOT ?= /ledasrc/LEDA4.1 5 8 6 BINARIES = dijkstra prim preflow9 BINARIES = preflow #dijkstra prim 7 10 8 11 all: $(BINARIES) 12 13 .depend dep depend: 14 $(CXX) $(INCLUDEDIRS) M $(BINARIES:=.cc) > .depend #2>/dev/null 9 15 10 16 makefile: .depend 11 17 sinclude .depend 12 18 13 preflow:14 $(CXX3) $(CXXFLAGS) o preflow preflow.cc15 16 dijkstra:17 $(CXX3) $(CXXFLAGS) o dijkstra dijkstra.cc18 19 prim:20 $(CXX3) $(CXXFLAGS) o prim prim.cc19 #preflow: 20 # $(CXX3) $(CXXFLAGS) o preflow preflow.cc 21 # 22 #dijkstra: 23 # $(CXX3) $(CXXFLAGS) o dijkstra dijkstra.cc 24 # 25 #prim: 26 # $(CXX3) $(CXXFLAGS) o prim prim.cc 21 27 22 28 clean: 
src/work/marci/edmonds_karp.h
r303 r311 10 10 #include <invalid.h> 11 11 #include <graph_wrapper.h> 12 #include <maps.h> 12 13 13 14 namespace hugo { … … 354 355 355 356 MG F; 356 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; 357 FilterResGW filter_res_graph(res_graph, dist); 357 ConstMap<typename ResGW::Node, bool> true_map(true); 358 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 359 DistanceMap<ResGW> > FilterResGW; 360 FilterResGW filter_res_graph(res_graph, true_map, dist); 358 361 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); 359 362 { … … 568 571 569 572 //Subgraph containing the edges on some shortest paths 570 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; 571 FilterResGW filter_res_graph(res_graph, dist); 573 ConstMap<typename ResGW::Node, bool> true_map(true); 574 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 575 DistanceMap<ResGW> > FilterResGW; 576 FilterResGW filter_res_graph(res_graph, true_map, dist); 572 577 573 578 //Subgraph, which is able to delete edges which are already … … 592 597 593 598 __augment=false; 594 //computing blocking flow with dfs599 //computing blocking flow with dfs 595 600 typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap; 596 DfsIterator5< ErasingResGW, BlockingReachedMap >597 dfs(erasing_res_graph);601 DfsIterator5< ErasingResGW, BlockingReachedMap > 602 dfs(erasing_res_graph); 598 603 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> 599 604 pred(erasing_res_graph); 600 605 pred.set(s, INVALID); 601 //invalid iterators for sources602 603 typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);606 //invalid iterators for sources 607 608 typename ErasingResGW::NodeMap<Number> free(erasing_res_graph); 604 609 605 610 dfs.pushAndSetReached(s); … … 609 614 /*typename ErasingResGW::OutEdgeIt*/(dfs))) 610 615 { 611 if (dfs.isBNodeNewlyReached()) {616 if (dfs.isBNodeNewlyReached()) { 612 617 613 618 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); … … 626 631 break; 627 632 } 628 } else {629 erasing_res_graph.erase(dfs);633 } else { 634 erasing_res_graph.erase(dfs); 630 635 } 631 636 } 632 637 } 633 638 634 if (__augment) {635 typename ErasingResGW::Node n=t;639 if (__augment) { 640 typename ErasingResGW::Node n=t; 636 641 Number augment_value=free[n]; 637 642 while (erasing_res_graph.valid(pred[n])) { … … 641 646 if (res_graph.resCap(e)==0) 642 647 erasing_res_graph.erase(e); 643 644 648 } 649 } 645 650 646 651 } //while (__augment) 
src/work/marci/edmonds_karp_demo.cc
r305 r311 9 9 #include <time_measure.h> 10 10 //#include <graph_wrapper.h> 11 12 class CM { 13 public: 14 template<typename T> int get(T) const {return 1;} 15 }; 11 #include <preflow.h> 16 12 17 13 using namespace hugo; … … 89 85 // std::cout << "p2:" << cgw.nodeNum() << std::endl; 90 86 91 92 { 93 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; 87 { 88 std::cout << "preflow ..." << std::endl; 89 Graph::EdgeMap<int> flow(G); //0 flow 90 91 Timer ts; 92 ts.reset(); 93 94 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 95 max_flow_test(G, s, t, cap, flow); 96 max_flow_test.run(); 97 // int i=0; 98 // while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 99 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 100 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 101 // } 102 // std::cout<<std::endl; 103 // ++i; 104 // } 105 106 // std::cout << "maximum flow: "<< std::endl; 107 // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 108 // std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 109 // } 110 // std::cout<<std::endl; 111 std::cout << "elapsed time: " << ts << std::endl; 112 // std::cout << "number of augmentation phases: " << i << std::endl; 113 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; 114 } 115 116 { 117 std::cout << "physical blocking flow augmentation ..." << std::endl; 94 118 Graph::EdgeMap<int> flow(G); //0 flow 95 119 … … 119 143 120 144 { 121 std::cout << " edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;145 std::cout << "faster physical blocking flow augmentation ..." << std::endl; 122 146 Graph::EdgeMap<int> flow(G); //0 flow 123 147 … … 147 171 148 172 { 149 std::cout << " edmonds karp demo (onthefly blocking flow augmentation)..." << std::endl;173 std::cout << "onthefly blocking flow augmentation ..." << std::endl; 150 174 Graph::EdgeMap<int> flow(G); //0 flow 151 175 … … 175 199 176 200 { 177 std::cout << " edmonds karp demo (onthefly shortest path augmentation)..." << std::endl;201 std::cout << "onthefly shortest path augmentation ..." << std::endl; 178 202 Graph::EdgeMap<int> flow(G); //0 flow 179 203 
src/work/marci/graph_wrapper.h
r307 r311 13 13 14 14 public: 15 // typedef Graph BaseGraph; 15 16 typedef Graph ParentGraph; 16 17 … … 25 26 NodeIt() { } 26 27 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 28 // NodeIt(const typename BaseGraph::NodeIt& n) : Graph::NodeIt(n) { } 27 29 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 28 30 NodeIt(const TrivGraphWrapper<Graph>& _G) : 29 31 Graph::NodeIt(*(_G.graph)) { } 32 // operator typename BaseGraph::NodeIt() { 33 // return typename BaseGraph::NodeIt(this>Graph::NodeIt); 34 // } 30 35 }; 31 36 typedef typename Graph::Edge Edge; … … 58 63 NodeIt& first(NodeIt& i) const { 59 64 i=NodeIt(*this); 60 return i;61 }62 EdgeIt& first(EdgeIt& i) const {63 i=EdgeIt(*this);64 65 return i; 65 66 } … … 76 77 return i; 77 78 } 79 EdgeIt& first(EdgeIt& i) const { 80 i=EdgeIt(*this); 81 return i; 82 } 78 83 // template<typename I, typename P> I& first(I& i, const P& p) const { 79 84 // i=I(*this, p); … … 83 88 // template<typename I> I getNext(const I& i) const { 84 89 // return graph>getNext(i); } 85 template<typename I> I& next(I &i) const { graph>next(i); return i; } 90 // template<typename I> I& next(I &i) const { graph>next(i); return i; } 91 NodeIt& next(NodeIt& i) const { graph>next(i); return i; } 92 OutEdgeIt& next(OutEdgeIt& i) const { graph>next(i); return i; } 93 InEdgeIt& next(InEdgeIt& i) const { graph>next(i); return i; } 94 EdgeIt& next(EdgeIt& i) const { graph>next(i); return i; } 86 95 87 96 template< typename It > It first() const { … … 158 167 159 168 public: 169 typedef Graph BaseGraph; 160 170 typedef Graph ParentGraph; 161 171 … … 205 215 return i; 206 216 } 207 EdgeIt& first(EdgeIt& i) const {208 i=EdgeIt(*this);209 return i;210 }211 217 // template<typename I> I& first(I& i) const { 212 218 // i=I(*this); … … 221 227 return i; 222 228 } 229 EdgeIt& first(EdgeIt& i) const { 230 i=EdgeIt(*this); 231 return i; 232 } 223 233 // template<typename I, typename P> I& first(I& i, const P& p) const { 224 234 // i=I(*this, p); … … 228 238 // template<typename I> I getNext(const I& i) const { 229 239 // return gw.getNext(i); } 230 template<typename I> I& next(I &i) const { graph>next(i); return i; } 240 // template<typename I> I& next(I &i) const { graph>next(i); return i; } 241 NodeIt& next(NodeIt& i) const { graph>next(i); return i; } 242 OutEdgeIt& next(OutEdgeIt& i) const { graph>next(i); return i; } 243 InEdgeIt& next(InEdgeIt& i) const { graph>next(i); return i; } 244 EdgeIt& next(EdgeIt& i) const { graph>next(i); return i; } 231 245 232 246 template< typename It > It first() const { … … 386 400 387 401 //Subgraph on the same nodeset and partial edgeset 388 template<typename Graph, typename EdgeFilterMap> 402 template<typename Graph, typename NodeFilterMap, 403 typename EdgeFilterMap> 389 404 class SubGraphWrapper : public GraphWrapper<Graph> { 390 405 protected: 391 EdgeFilterMap* filter_map; 406 NodeFilterMap* node_filter_map; 407 EdgeFilterMap* edge_filter_map; 392 408 public: 393 typedef typename GraphWrapper<Graph>::Node Node;394 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;395 typedef typename GraphWrapper<Graph>::Edge Edge;396 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;397 typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;398 typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;399 400 409 // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { } 401 SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) : 402 GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { } 403 404 template<typename I> I& first(I& i) const { 405 graph>first(i); 406 //while (graph>valid(i) && !filter_map>get(i)) { graph>next(i); } 407 while (graph>valid(i) && !(*filter_map)[i]) { graph>next(i); } 408 return i; 409 } 410 template<typename I, typename P> I& first(I& i, const P& p) const { 411 graph>first(i, p); 412 // while (graph>valid(i) && !filter_map>get(i)) { graph>next(i); } 413 while (graph>valid(i) && !(*filter_map)[i]) { graph>next(i); } 414 return i; 415 } 416 410 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 411 EdgeFilterMap& _edge_filter_map) : 412 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 413 edge_filter_map(&_edge_filter_map) { } 414 415 416 typedef typename Graph::Node Node; 417 class NodeIt : public Graph::NodeIt { 418 // typedef typename Graph::NodeIt GraphNodeIt; 419 public: 420 NodeIt() { } 421 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 422 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 423 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 424 Graph::NodeIt(*(_G.graph)) { 425 while (_G.graph>valid((*this)/*.GraphNodeIt*/) && 426 !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) 427 _G.graph>next((*this)/*.GraphNodeIt*/); 428 } 429 }; 430 typedef typename Graph::Edge Edge; 431 class OutEdgeIt : public Graph::OutEdgeIt { 432 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 433 public: 434 OutEdgeIt() { } 435 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 436 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 437 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& 438 _G, const Node& n) : 439 Graph::OutEdgeIt(*(_G.graph), n) { 440 while (_G.graph>valid((*this)/*.GraphOutEdgeIt*/) && 441 !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) 442 _G.graph>next((*this)/*.GraphOutEdgeIt*/); 443 } 444 }; 445 class InEdgeIt : public Graph::InEdgeIt { 446 // typedef typename Graph::InEdgeIt GraphInEdgeIt; 447 public: 448 InEdgeIt() { } 449 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 450 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 451 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 452 const Node& n) : 453 Graph::InEdgeIt(*(_G.graph), n) { 454 while (_G.graph>valid((*this)/*.GraphInEdgeIt*/) && 455 !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) 456 _G.graph>next((*this)/*.GraphInEdgeIt*/); 457 } 458 }; 459 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 460 class EdgeIt : public Graph::EdgeIt { 461 // typedef typename Graph::EdgeIt GraphEdgeIt; 462 public: 463 EdgeIt() { } 464 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 465 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 466 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 467 Graph::EdgeIt(*(_G.graph)) { 468 while (_G.graph>valid((*this)/*.GraphEdgeIt*/) && 469 !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) 470 _G.graph>next((*this)/*.GraphEdgeIt*/); 471 } 472 }; 473 474 NodeIt& first(NodeIt& i) const { 475 i=NodeIt(*this); 476 return i; 477 } 478 OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { 479 i=OutEdgeIt(*this, n); 480 return i; 481 } 482 InEdgeIt& first(InEdgeIt& i, const Node& n) const { 483 i=InEdgeIt(*this, n); 484 return i; 485 } 486 EdgeIt& first(EdgeIt& i) const { 487 i=EdgeIt(*this); 488 return i; 489 } 490 491 // template<typename I> I& first(I& i) const { 492 // graph>first(i); 493 // //while (graph>valid(i) && !filter_map>get(i)) { graph>next(i); } 494 // while (graph>valid(i) && !(*edge_filter_map)[i]) { graph>next(i); } 495 // return i; 496 // } 497 // template<typename I, typename P> I& first(I& i, const P& p) const { 498 // graph>first(i, p); 499 // // while (graph>valid(i) && !filter_map>get(i)) { graph>next(i); } 500 // while (graph>valid(i) && !(*edge_filter_map)[i]) { graph>next(i); } 501 // return i; 502 // } 503 504 NodeIt& next(NodeIt& i) const { 505 graph>next(i); 506 while (graph>valid(i) && !(*node_filter_map)[i]) { graph>next(i); } 507 return i; 508 } 509 OutEdgeIt& next(OutEdgeIt& i) const { 510 graph>next(i); 511 while (graph>valid(i) && !(*edge_filter_map)[i]) { graph>next(i); } 512 return i; 513 } 514 InEdgeIt& next(InEdgeIt& i) const { 515 graph>next(i); 516 while (graph>valid(i) && !(*edge_filter_map)[i]) { graph>next(i); } 517 return i; 518 } 519 EdgeIt& next(EdgeIt& i) const { 520 graph>next(i); 521 while (graph>valid(i) && !(*edge_filter_map)[i]) { graph>next(i); } 522 return i; 523 } 524 417 525 //template<typename I> I getNext(const I& i) const { 418 526 // return gw.getNext(i); 419 527 //} 420 template<typename I> I& next(I &i) const {421 graph>next(i);422 // while (graph>valid(i) && !filter_mapget(i)) { graph>next(i); }423 while (graph>valid(i) && !(*filter_map)[i]) { graph>next(i); }424 return i;425 }528 // template<typename I> I& next(I &i) const { 529 // graph>next(i); 530 // // while (graph>valid(i) && !filter_mapget(i)) { graph>next(i); } 531 // while (graph>valid(i) && !(*edge_filter_map)[i]) { graph>next(i); } 532 // return i; 533 // } 426 534 427 535 template< typename It > It first() const { … … 845 953 846 954 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 847 class ResGraphWrapper : public GraphWrapper<Graph>{ 848 public: 849 typedef typename GraphWrapper<Graph>::Node Node; 850 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 955 class ResGraphWrapper : public GraphWrapper<Graph> { 851 956 protected: 852 957 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; … … 866 971 friend class OutEdgeIt; 867 972 973 typedef typename GraphWrapper<Graph>::Node Node; 974 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 868 975 class Edge { 869 976 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; … … 893 1000 } 894 1001 }; 895 896 897 1002 class OutEdgeIt : public Edge { 898 1003 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; … … 931 1036 932 1037 //FIXME This is just for having InEdgeIt 933 typedef void InEdgeIt;1038 // class InEdgeIt : public Edge { }; 934 1039 935 1040 class EdgeIt : public Edge { … … 994 1099 }; 995 1100 996 NodeIt& first(NodeIt& v) const { graph>first(v); return v; } 997 OutEdgeIt& first(OutEdgeIt& e, Node v) const { 998 e=OutEdgeIt(*this, v); 999 return e; 1000 } 1101 NodeIt& first(NodeIt& i) const { 1102 i=NodeIt(*this); 1103 return i; 1104 } 1105 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1106 i=OutEdgeIt(*this, p); 1107 return i; 1108 } 1109 //FIXME Not yet implemented 1110 //InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1111 //i=InEdgeIt(*this, p); 1112 // return i; 1113 //} 1001 1114 EdgeIt& first(EdgeIt& e) const { 1002 1115 e=EdgeIt(*this); … … 1005 1118 1006 1119 NodeIt& next(NodeIt& n) const { graph>next(n); return n; } 1007 1008 1120 OutEdgeIt& next(OutEdgeIt& e) const { 1009 1121 if (e.out_or_in) { … … 1022 1134 return e; 1023 1135 } 1024 1136 //FIXME Not yet implemented 1137 //InEdgeIt& next(InEdgeIt& e) const { 1138 // return e; 1139 //} 1025 1140 EdgeIt& next(EdgeIt& e) const { 1026 1141 if (e.out_or_in) { … … 1170 1285 FirstOutEdgesMap* first_out_edges; 1171 1286 public: 1172 typedef typename GraphWrapper<Graph>::Node Node;1173 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;1174 typedef typename GraphWrapper<Graph>::Edge Edge;1175 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;1176 typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;1177 typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;1178 1179 1287 ErasingFirstGraphWrapper(Graph& _graph, 1180 1288 FirstOutEdgesMap& _first_out_edges) : 1181 1289 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 1182 1290 1183 template<typename I> I& first(I& i) const { 1184 graph>first(i); 1185 return i; 1186 } 1187 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 1188 // e=first_out_edges>get(n); 1189 e=(*first_out_edges)[n]; 1190 return e; 1191 } 1192 template<typename I, typename P> I& first(I& i, const P& p) const { 1193 graph>first(i, p); 1194 return i; 1195 } 1291 typedef typename Graph::Node Node; 1292 class NodeIt : public Graph::NodeIt { 1293 public: 1294 NodeIt() { } 1295 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 1296 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 1297 NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 1298 Graph::NodeIt(*(_G.graph)) { } 1299 }; 1300 typedef typename Graph::Edge Edge; 1301 class OutEdgeIt : public Graph::OutEdgeIt { 1302 public: 1303 OutEdgeIt() { } 1304 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 1305 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 1306 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 1307 const Node& n) : 1308 Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } 1309 }; 1310 class InEdgeIt : public Graph::InEdgeIt { 1311 public: 1312 InEdgeIt() { } 1313 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 1314 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 1315 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 1316 const Node& n) : 1317 Graph::InEdgeIt(*(_G.graph), n) { } 1318 }; 1319 //typedef typename Graph::SymEdgeIt SymEdgeIt; 1320 class EdgeIt : public Graph::EdgeIt { 1321 public: 1322 EdgeIt() { } 1323 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 1324 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 1325 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 1326 Graph::EdgeIt(*(_G.graph)) { } 1327 }; 1328 1329 NodeIt& first(NodeIt& i) const { 1330 i=NodeIt(*this); 1331 return i; 1332 } 1333 OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { 1334 i=OutEdgeIt(*this, n); 1335 // i=(*first_out_edges)[n]; 1336 return i; 1337 } 1338 InEdgeIt& first(InEdgeIt& i, const Node& n) const { 1339 i=InEdgeIt(*this, n); 1340 return i; 1341 } 1342 EdgeIt& first(EdgeIt& i) const { 1343 i=EdgeIt(*this); 1344 return i; 1345 } 1346 1347 // template<typename I> I& first(I& i) const { 1348 // graph>first(i); 1349 // return i; 1350 // } 1351 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 1352 // // e=first_out_edges>get(n); 1353 // e=(*first_out_edges)[n]; 1354 // return e; 1355 // } 1356 // template<typename I, typename P> I& first(I& i, const P& p) const { 1357 // graph>first(i, p); 1358 // return i; 1359 // } 1196 1360 1197 1361 //template<typename I> I getNext(const I& i) const { 1198 1362 // return gw.getNext(i); 1199 1363 //} 1200 template<typename I> I& next(I &i) const { 1364 1365 1366 NodeIt& next(NodeIt& i) const { 1201 1367 graph>next(i); 1202 1368 return i; 1203 1369 } 1370 OutEdgeIt& next(OutEdgeIt& i) const { 1371 graph>next(i); 1372 return i; 1373 } 1374 InEdgeIt& next(InEdgeIt& i) const { 1375 graph>next(i); 1376 return i; 1377 } 1378 EdgeIt& next(EdgeIt& i) const { 1379 graph>next(i); 1380 return i; 1381 } 1382 1383 // template<typename I> I& next(I &i) const { 1384 // graph>next(i); 1385 // return i; 1386 // } 1204 1387 1205 1388 template< typename It > It first() const {
Note: See TracChangeset
for help on using the changeset viewer.