Changeset 1951:cb7a6e0573bc in lemon-0.x
- Timestamp:
- 02/03/06 15:07:52 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2526
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_adaptor.h
r1949 r1951 39 39 namespace lemon { 40 40 41 // x\brief Base type for the Graph Adaptors42 // x\ingroup graph_adaptors43 // x44 // xBase type for the Graph Adaptors45 // x46 // x\warning Graph adaptors are in even47 // xmore experimental state than the other48 // xparts of the lib. Use them at you own risk.49 // x50 // xThis is the base type for most of LEMON graph adaptors.51 // xThis class implements a trivial graph adaptor i.e. it only wraps the52 // xfunctions and types of the graph. The purpose of this class is to53 // xmake easier implementing graph adaptors. E.g. if an adaptor is54 // xconsidered which differs from the wrapped graph only in some of its55 // xfunctions or types, then it can be derived from GraphAdaptor,56 // xand only the57 // xdifferences should be implemented.58 // x59 // xauthor Marton Makai41 ///\brief Base type for the Graph Adaptors 42 ///\ingroup graph_adaptors 43 /// 44 ///Base type for the Graph Adaptors 45 /// 46 ///\warning Graph adaptors are in even 47 ///more experimental state than the other 48 ///parts of the lib. Use them at you own risk. 49 /// 50 ///This is the base type for most of LEMON graph adaptors. 51 ///This class implements a trivial graph adaptor i.e. it only wraps the 52 ///functions and types of the graph. The purpose of this class is to 53 ///make easier implementing graph adaptors. E.g. if an adaptor is 54 ///considered which differs from the wrapped graph only in some of its 55 ///functions or types, then it can be derived from GraphAdaptor, 56 ///and only the 57 ///differences should be implemented. 58 /// 59 ///author Marton Makai 60 60 template<typename _Graph> 61 61 class GraphAdaptorBase { … … 281 281 } 282 282 283 // x\e284 285 // xThis function hides \c n in the graph, i.e. the iteration286 // xjumps over it. This is done by simply setting the value of \c n287 // xto be false in the corresponding node-map.283 ///\e 284 285 /// This function hides \c n in the graph, i.e. the iteration 286 /// jumps over it. This is done by simply setting the value of \c n 287 /// to be false in the corresponding node-map. 288 288 void hide(const Node& n) const { node_filter_map->set(n, false); } 289 289 290 // x\e291 292 // xThis function hides \c e in the graph, i.e. the iteration293 // xjumps over it. This is done by simply setting the value of \c e294 // xto be false in the corresponding edge-map.290 ///\e 291 292 /// This function hides \c e in the graph, i.e. the iteration 293 /// jumps over it. This is done by simply setting the value of \c e 294 /// to be false in the corresponding edge-map. 295 295 void hide(const Edge& e) const { edge_filter_map->set(e, false); } 296 296 297 // x\e298 299 // xThe value of \c n is set to be true in the node-map which stores300 // xhide information. If \c n was hidden previuosly, then it is shown301 // xagain297 ///\e 298 299 /// The value of \c n is set to be true in the node-map which stores 300 /// hide information. If \c n was hidden previuosly, then it is shown 301 /// again 302 302 void unHide(const Node& n) const { node_filter_map->set(n, true); } 303 303 304 // x\e305 306 // xThe value of \c e is set to be true in the edge-map which stores307 // xhide information. If \c e was hidden previuosly, then it is shown308 // xagain304 ///\e 305 306 /// The value of \c e is set to be true in the edge-map which stores 307 /// hide information. If \c e was hidden previuosly, then it is shown 308 /// again 309 309 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } 310 310 311 // xReturns true if \c n is hidden.311 /// Returns true if \c n is hidden. 312 312 313 // x\e314 // x313 ///\e 314 /// 315 315 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 316 316 317 // xReturns true if \c n is hidden.317 /// Returns true if \c n is hidden. 318 318 319 // x\e320 // x319 ///\e 320 /// 321 321 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 322 322 … … 387 387 } 388 388 389 // x\e390 391 // xThis function hides \c n in the graph, i.e. the iteration392 // xjumps over it. This is done by simply setting the value of \c n393 // xto be false in the corresponding node-map.389 ///\e 390 391 /// This function hides \c n in the graph, i.e. the iteration 392 /// jumps over it. This is done by simply setting the value of \c n 393 /// to be false in the corresponding node-map. 394 394 void hide(const Node& n) const { node_filter_map->set(n, false); } 395 395 396 // x\e397 398 // xThis function hides \c e in the graph, i.e. the iteration399 // xjumps over it. This is done by simply setting the value of \c e400 // xto be false in the corresponding edge-map.396 ///\e 397 398 /// This function hides \c e in the graph, i.e. the iteration 399 /// jumps over it. This is done by simply setting the value of \c e 400 /// to be false in the corresponding edge-map. 401 401 void hide(const Edge& e) const { edge_filter_map->set(e, false); } 402 402 403 // x\e404 405 // xThe value of \c n is set to be true in the node-map which stores406 // xhide information. If \c n was hidden previuosly, then it is shown407 // xagain403 ///\e 404 405 /// The value of \c n is set to be true in the node-map which stores 406 /// hide information. If \c n was hidden previuosly, then it is shown 407 /// again 408 408 void unHide(const Node& n) const { node_filter_map->set(n, true); } 409 409 410 // x\e411 412 // xThe value of \c e is set to be true in the edge-map which stores413 // xhide information. If \c e was hidden previuosly, then it is shown414 // xagain410 ///\e 411 412 /// The value of \c e is set to be true in the edge-map which stores 413 /// hide information. If \c e was hidden previuosly, then it is shown 414 /// again 415 415 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } 416 416 417 // xReturns true if \c n is hidden.417 /// Returns true if \c n is hidden. 418 418 419 // x\e420 // x419 ///\e 420 /// 421 421 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 422 422 423 // xReturns true if \c n is hidden.423 /// Returns true if \c n is hidden. 424 424 425 // x\e426 // x425 ///\e 426 /// 427 427 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 428 428 … … 431 431 }; 432 432 433 //x\brief A graph adaptor for hiding nodes and edges from a graph. 434 //x\ingroup graph_adaptors 435 //x 436 //x\warning Graph adaptors are in even more experimental 437 //xstate than the other 438 //xparts of the lib. Use them at you own risk. 439 //x 440 //xSubGraphAdaptor shows the graph with filtered node-set and 441 //xedge-set. If the \c checked parameter is true then it filters the edgeset 442 //xto do not get invalid edges without source or target. 443 //xLet \f$G=(V, A)\f$ be a directed graph 444 //xand suppose that the graph instance \c g of type ListGraph implements 445 //x\f$G\f$. 446 //x/Let moreover \f$b_V\f$ and 447 //x\f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set. 448 //xSubGraphAdaptor<...>::NodeIt iterates 449 //xon the node-set \f$\{v\in V : b_V(v)=true\}\f$ and 450 //xSubGraphAdaptor<...>::EdgeIt iterates 451 //xon the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly, 452 //xSubGraphAdaptor<...>::OutEdgeIt and 453 //xSubGraphAdaptor<...>::InEdgeIt iterates 454 //xonly on edges leaving and entering a specific node which have true value. 455 //x 456 //xIf the \c checked template parameter is false then we have to note that 457 //xthe node-iterator cares only the filter on the node-set, and the 458 //xedge-iterator cares only the filter on the edge-set. 459 //xThis way the edge-map 460 //xshould filter all edges which's source or target is filtered by the 461 //xnode-filter. 462 //x\code 463 //xtypedef ListGraph Graph; 464 //xGraph g; 465 //xtypedef Graph::Node Node; 466 //xtypedef Graph::Edge Edge; 467 //xNode u=g.addNode(); //node of id 0 468 //xNode v=g.addNode(); //node of id 1 469 //xNode e=g.addEdge(u, v); //edge of id 0 470 //xNode f=g.addEdge(v, u); //edge of id 1 471 //xGraph::NodeMap<bool> nm(g, true); 472 //xnm.set(u, false); 473 //xGraph::EdgeMap<bool> em(g, true); 474 //xem.set(e, false); 475 //xtypedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW; 476 //xSubGW gw(g, nm, em); 477 //xfor (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 478 //xstd::cout << ":-)" << std::endl; 479 //xfor (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 480 //x\endcode 481 //xThe output of the above code is the following. 482 //x\code 483 //x1 484 //x:-) 485 //x1 486 //x\endcode 487 //xNote that \c n is of type \c SubGW::NodeIt, but it can be converted to 488 //x\c Graph::Node that is why \c g.id(n) can be applied. 489 //x 490 //xFor other examples see also the documentation of NodeSubGraphAdaptor and 491 //xEdgeSubGraphAdaptor. 492 //x 493 //x\author Marton Makai 433 /// \brief A graph adaptor for hiding nodes and edges from a graph. 434 /// \ingroup graph_adaptors 435 /// 436 /// \warning Graph adaptors are in even more experimental state than the 437 /// other parts of the lib. Use them at you own risk. 438 /// 439 /// SubGraphAdaptor shows the graph with filtered node-set and 440 /// edge-set. If the \c checked parameter is true then it filters the edgeset 441 /// to do not get invalid edges without source or target. 442 /// Let \f$ G=(V, A) \f$ be a directed graph 443 /// and suppose that the graph instance \c g of type ListGraph 444 /// implements \f$ G \f$ . 445 /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp. 446 /// on the node-set and edge-set. 447 /// SubGraphAdaptor<...>::NodeIt iterates 448 /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and 449 /// SubGraphAdaptor<...>::EdgeIt iterates 450 /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$ . Similarly, 451 /// SubGraphAdaptor<...>::OutEdgeIt and 452 /// SubGraphAdaptor<...>::InEdgeIt iterates 453 /// only on edges leaving and entering a specific node which have true value. 454 /// 455 /// If the \c checked template parameter is false then we have to note that 456 /// the node-iterator cares only the filter on the node-set, and the 457 /// edge-iterator cares only the filter on the edge-set. 458 /// This way the edge-map 459 /// should filter all edges which's source or target is filtered by the 460 /// node-filter. 461 /// \code 462 /// typedef ListGraph Graph; 463 /// Graph g; 464 /// typedef Graph::Node Node; 465 /// typedef Graph::Edge Edge; 466 /// Node u=g.addNode(); //node of id 0 467 /// Node v=g.addNode(); //node of id 1 468 /// Node e=g.addEdge(u, v); //edge of id 0 469 /// Node f=g.addEdge(v, u); //edge of id 1 470 /// Graph::NodeMap<bool> nm(g, true); 471 /// nm.set(u, false); 472 /// Graph::EdgeMap<bool> em(g, true); 473 /// em.set(e, false); 474 /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW; 475 /// SubGW gw(g, nm, em); 476 /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 477 /// std::cout << ":-)" << std::endl; 478 /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 479 /// \endcode 480 /// The output of the above code is the following. 481 /// \code 482 /// 1 483 /// :-) 484 /// 1 485 /// \endcode 486 /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to 487 /// \c Graph::Node that is why \c g.id(n) can be applied. 488 /// 489 /// For other examples see also the documentation of NodeSubGraphAdaptor and 490 /// EdgeSubGraphAdaptor. 491 /// 492 /// \author Marton Makai 494 493 495 494 template<typename _Graph, typename NodeFilterMap, … … 515 514 516 515 517 // x\brief An adaptor for hiding nodes from a graph.518 // x\ingroup graph_adaptors519 // x520 // x\warning Graph adaptors are in even more experimental state521 // xthan the other522 // xparts of the lib. Use them at you own risk.523 // x524 // xAn adaptor for hiding nodes from a graph.525 // xThis adaptor specializes SubGraphAdaptor in the way that only526 // xthe node-set527 // xcan be filtered. In usual case the checked parameter is true, we get the528 // xinduced subgraph. But if the checked parameter is false then we can only529 // xfilter only isolated nodes.530 // x\author Marton Makai516 ///\brief An adaptor for hiding nodes from a graph. 517 ///\ingroup graph_adaptors 518 /// 519 ///\warning Graph adaptors are in even more experimental state 520 ///than the other 521 ///parts of the lib. Use them at you own risk. 522 /// 523 ///An adaptor for hiding nodes from a graph. 524 ///This adaptor specializes SubGraphAdaptor in the way that only 525 ///the node-set 526 ///can be filtered. In usual case the checked parameter is true, we get the 527 ///induced subgraph. But if the checked parameter is false then we can only 528 ///filter only isolated nodes. 529 ///\author Marton Makai 531 530 template<typename Graph, typename NodeFilterMap, bool checked = true> 532 531 class NodeSubGraphAdaptor : … … 548 547 549 548 550 // x\brief An adaptor for hiding edges from a graph.551 // x552 // x\warning Graph adaptors are in even more experimental state553 // xthan the other parts of the lib. Use them at you own risk.554 // x555 // xAn adaptor for hiding edges from a graph.556 // xThis adaptor specializes SubGraphAdaptor in the way that557 // xonly the edge-set558 // xcan be filtered. The usefulness of this adaptor is demonstrated in the559 // xproblem of searching a maximum number of edge-disjoint shortest paths560 // xbetween561 // xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t.562 // xnon-negative edge-lengths. Note that563 // xthe comprehension of the presented solution564 // xneed's some elementary knowledge from combinatorial optimization.565 // x566 // xIf a single shortest path is to be567 // xsearched between \c s and \c t, then this can be done easily by568 // xapplying the Dijkstra algorithm. What happens, if a maximum number of569 // xedge-disjoint shortest paths is to be computed. It can be proved that an570 // xedge can be in a shortest path if and only571 // xif it is tight with respect to572 // xthe potential function computed by Dijkstra.573 // xMoreover, any path containing574 // xonly such edges is a shortest one.575 // xThus we have to compute a maximum number576 // xof edge-disjoint paths between \c s and \c t in577 // xthe graph which has edge-set578 // xall the tight edges. The computation will be demonstrated579 // xon the following580 // xgraph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.581 // xThe full source code is available in \ref sub_graph_adaptor_demo.cc.582 // xIf you are interested in more demo programs, you can use583 // x\ref dim_to_dot.cc to generate .dot files from dimacs files.584 // xThe .dot file of the following figure was generated by585 // xthe demo program \ref dim_to_dot.cc.586 // x587 // x\dot588 // xdigraph lemon_dot_example {589 // xnode [ shape=ellipse, fontname=Helvetica, fontsize=10 ];590 // xn0 [ label="0 (s)" ];591 // xn1 [ label="1" ];592 // xn2 [ label="2" ];593 // xn3 [ label="3" ];594 // xn4 [ label="4" ];595 // xn5 [ label="5" ];596 // xn6 [ label="6 (t)" ];597 // xedge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];598 // xn5 -> n6 [ label="9, length:4" ];599 // xn4 -> n6 [ label="8, length:2" ];600 // xn3 -> n5 [ label="7, length:1" ];601 // xn2 -> n5 [ label="6, length:3" ];602 // xn2 -> n6 [ label="5, length:5" ];603 // xn2 -> n4 [ label="4, length:2" ];604 // xn1 -> n4 [ label="3, length:3" ];605 // xn0 -> n3 [ label="2, length:1" ];606 // xn0 -> n2 [ label="1, length:2" ];607 // xn0 -> n1 [ label="0, length:3" ];608 // x}609 // x\enddot610 // x611 // x\code612 // xGraph g;613 // xNode s, t;614 // xLengthMap length(g);615 // x616 // xreadDimacs(std::cin, g, length, s, t);617 // x618 // xcout << "edges with lengths (of form id, source--length->target): " << endl;619 // xfor(EdgeIt e(g); e!=INVALID; ++e)620 // xcout << g.id(e) << ", " << g.id(g.source(e)) << "--"621 // x<< length[e] << "->" << g.id(g.target(e)) << endl;622 // x623 // xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl;624 // x\endcode625 // xNext, the potential function is computed with Dijkstra.626 // x\code627 // xtypedef Dijkstra<Graph, LengthMap> Dijkstra;628 // xDijkstra dijkstra(g, length);629 // xdijkstra.run(s);630 // x\endcode631 // xNext, we consrtruct a map which filters the edge-set to the tight edges.632 // x\code633 // xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>634 // xTightEdgeFilter;635 // xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);636 // x637 // xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;638 // xSubGW gw(g, tight_edge_filter);639 // x\endcode640 // xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed641 // xwith a max flow algorithm Preflow.642 // x\code643 // xConstMap<Edge, int> const_1_map(1);644 // xGraph::EdgeMap<int> flow(g, 0);645 // x646 // xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >647 // xpreflow(gw, s, t, const_1_map, flow);648 // xpreflow.run();649 // x\endcode650 // xLast, the output is:651 // x\code652 // xcout << "maximum number of edge-disjoint shortest path: "653 // x<< preflow.flowValue() << endl;654 // xcout << "edges of the maximum number of edge-disjoint shortest s-t paths: "655 // x<< endl;656 // xfor(EdgeIt e(g); e!=INVALID; ++e)657 // xif (flow[e])658 // xcout << " " << g.id(g.source(e)) << "--"659 // x<< length[e] << "->" << g.id(g.target(e)) << endl;660 // x\endcode661 // xThe program has the following (expected :-)) output:662 // x\code663 // xedges with lengths (of form id, source--length->target):664 // x9, 5--4->6665 // x8, 4--2->6666 // x7, 3--1->5667 // x6, 2--3->5668 // x5, 2--5->6669 // x4, 2--2->4670 // x3, 1--3->4671 // x2, 0--1->3672 // x1, 0--2->2673 // x0, 0--3->1674 // xs: 0 t: 6675 // xmaximum number of edge-disjoint shortest path: 2676 // xedges of the maximum number of edge-disjoint shortest s-t paths:677 // x9, 5--4->6678 // x8, 4--2->6679 // x7, 3--1->5680 // x4, 2--2->4681 // x2, 0--1->3682 // x1, 0--2->2683 // x\endcode684 // x685 // x\author Marton Makai549 ///\brief An adaptor for hiding edges from a graph. 550 /// 551 ///\warning Graph adaptors are in even more experimental state 552 ///than the other parts of the lib. Use them at you own risk. 553 /// 554 ///An adaptor for hiding edges from a graph. 555 ///This adaptor specializes SubGraphAdaptor in the way that 556 ///only the edge-set 557 ///can be filtered. The usefulness of this adaptor is demonstrated in the 558 ///problem of searching a maximum number of edge-disjoint shortest paths 559 ///between 560 ///two nodes \c s and \c t. Shortest here means being shortest w.r.t. 561 ///non-negative edge-lengths. Note that 562 ///the comprehension of the presented solution 563 ///need's some elementary knowledge from combinatorial optimization. 564 /// 565 ///If a single shortest path is to be 566 ///searched between \c s and \c t, then this can be done easily by 567 ///applying the Dijkstra algorithm. What happens, if a maximum number of 568 ///edge-disjoint shortest paths is to be computed. It can be proved that an 569 ///edge can be in a shortest path if and only 570 ///if it is tight with respect to 571 ///the potential function computed by Dijkstra. 572 ///Moreover, any path containing 573 ///only such edges is a shortest one. 574 ///Thus we have to compute a maximum number 575 ///of edge-disjoint paths between \c s and \c t in 576 ///the graph which has edge-set 577 ///all the tight edges. The computation will be demonstrated 578 ///on the following 579 ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 580 ///The full source code is available in \ref sub_graph_adaptor_demo.cc. 581 ///If you are interested in more demo programs, you can use 582 ///\ref dim_to_dot.cc to generate .dot files from dimacs files. 583 ///The .dot file of the following figure was generated by 584 ///the demo program \ref dim_to_dot.cc. 585 /// 586 ///\dot 587 ///digraph lemon_dot_example { 588 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 589 ///n0 [ label="0 (s)" ]; 590 ///n1 [ label="1" ]; 591 ///n2 [ label="2" ]; 592 ///n3 [ label="3" ]; 593 ///n4 [ label="4" ]; 594 ///n5 [ label="5" ]; 595 ///n6 [ label="6 (t)" ]; 596 ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 597 ///n5 -> n6 [ label="9, length:4" ]; 598 ///n4 -> n6 [ label="8, length:2" ]; 599 ///n3 -> n5 [ label="7, length:1" ]; 600 ///n2 -> n5 [ label="6, length:3" ]; 601 ///n2 -> n6 [ label="5, length:5" ]; 602 ///n2 -> n4 [ label="4, length:2" ]; 603 ///n1 -> n4 [ label="3, length:3" ]; 604 ///n0 -> n3 [ label="2, length:1" ]; 605 ///n0 -> n2 [ label="1, length:2" ]; 606 ///n0 -> n1 [ label="0, length:3" ]; 607 ///} 608 ///\enddot 609 /// 610 ///\code 611 ///Graph g; 612 ///Node s, t; 613 ///LengthMap length(g); 614 /// 615 ///readDimacs(std::cin, g, length, s, t); 616 /// 617 ///cout << "edges with lengths (of form id, source--length->target): " << endl; 618 ///for(EdgeIt e(g); e!=INVALID; ++e) 619 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 620 /// << length[e] << "->" << g.id(g.target(e)) << endl; 621 /// 622 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; 623 ///\endcode 624 ///Next, the potential function is computed with Dijkstra. 625 ///\code 626 ///typedef Dijkstra<Graph, LengthMap> Dijkstra; 627 ///Dijkstra dijkstra(g, length); 628 ///dijkstra.run(s); 629 ///\endcode 630 ///Next, we consrtruct a map which filters the edge-set to the tight edges. 631 ///\code 632 ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 633 /// TightEdgeFilter; 634 ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); 635 /// 636 ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW; 637 ///SubGW gw(g, tight_edge_filter); 638 ///\endcode 639 ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 640 ///with a max flow algorithm Preflow. 641 ///\code 642 ///ConstMap<Edge, int> const_1_map(1); 643 ///Graph::EdgeMap<int> flow(g, 0); 644 /// 645 ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 646 /// preflow(gw, s, t, const_1_map, flow); 647 ///preflow.run(); 648 ///\endcode 649 ///Last, the output is: 650 ///\code 651 ///cout << "maximum number of edge-disjoint shortest path: " 652 /// << preflow.flowValue() << endl; 653 ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 654 /// << endl; 655 ///for(EdgeIt e(g); e!=INVALID; ++e) 656 /// if (flow[e]) 657 /// cout << " " << g.id(g.source(e)) << "--" 658 /// << length[e] << "->" << g.id(g.target(e)) << endl; 659 ///\endcode 660 ///The program has the following (expected :-)) output: 661 ///\code 662 ///edges with lengths (of form id, source--length->target): 663 /// 9, 5--4->6 664 /// 8, 4--2->6 665 /// 7, 3--1->5 666 /// 6, 2--3->5 667 /// 5, 2--5->6 668 /// 4, 2--2->4 669 /// 3, 1--3->4 670 /// 2, 0--1->3 671 /// 1, 0--2->2 672 /// 0, 0--3->1 673 ///s: 0 t: 6 674 ///maximum number of edge-disjoint shortest path: 2 675 ///edges of the maximum number of edge-disjoint shortest s-t paths: 676 /// 9, 5--4->6 677 /// 8, 4--2->6 678 /// 7, 3--1->5 679 /// 4, 2--2->4 680 /// 2, 0--1->3 681 /// 1, 0--2->2 682 ///\endcode 683 /// 684 ///\author Marton Makai 686 685 template<typename Graph, typename EdgeFilterMap> 687 686 class EdgeSubGraphAdaptor : … … 770 769 }; 771 770 772 // x\brief An undirected graph is made from a directed graph by an adaptor773 // x\ingroup graph_adaptors774 // x775 // xUndocumented, untested!!!776 // xIf somebody knows nice demo application, let's polulate it.777 // x778 // x\author Marton Makai771 ///\brief An undirected graph is made from a directed graph by an adaptor 772 ///\ingroup graph_adaptors 773 /// 774 /// Undocumented, untested!!! 775 /// If somebody knows nice demo application, let's polulate it. 776 /// 777 /// \author Marton Makai 779 778 template<typename _Graph> 780 779 class UGraphAdaptor : … … 962 961 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } 963 962 964 // xGives back the opposite edge.965 966 // x\e967 // x963 /// Gives back the opposite edge. 964 965 ///\e 966 /// 968 967 Edge opposite(const Edge& e) const { 969 968 Edge f=e; … … 972 971 } 973 972 974 // x\e975 976 // x\warning This is a linear time operation and works only if977 // x\c Graph::EdgeIt is defined.978 // x\todo hmm973 ///\e 974 975 /// \warning This is a linear time operation and works only if 976 /// \c Graph::EdgeIt is defined. 977 /// \todo hmm 979 978 int edgeNum() const { 980 979 int i=0; … … 987 986 bool backward(const Edge& e) const { return e.backward; } 988 987 989 // x\e990 991 // x\c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two992 // x_Graph::EdgeMap one for the forward edges and993 // xone for the backward edges.988 ///\e 989 990 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 991 /// _Graph::EdgeMap one for the forward edges and 992 /// one for the backward edges. 994 993 template <typename T> 995 994 class EdgeMap { … … 1040 1039 1041 1040 1042 // x\brief An adaptor for composing a subgraph of a1043 // xbidirected graph made from a directed one.1044 // x\ingroup graph_adaptors1045 // x1046 // xAn adaptor for composing a subgraph of a1047 // xbidirected graph made from a directed one.1048 // x1049 // x\warning Graph adaptors are in even more experimental state1050 // xthan the other1051 // xparts of the lib. Use them at you own risk.1052 // x1053 // x Let \f$G=(V, A)\f$be a directed graph and for each directed edge1054 // x \f$e\in A\f$, let \f$\bar e\f$denote the edge obtained by1055 // xreversing its orientation. We are given moreover two bool valued1056 // xmaps on the edge-set,1057 // x \f$forward\_filter\f$, and \f$backward\_filter\f$.1058 // xSubBidirGraphAdaptor implements the graph structure with node-set1059 // x \f$V\f$and edge-set1060 // x \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.1061 // xThe purpose of writing + instead of union is because parallel1062 // xedges can arise. (Similarly, antiparallel edges also can arise).1063 // xIn other words, a subgraph of the bidirected graph obtained, which1064 // xis given by orienting the edges of the original graph in both directions.1065 // xAs the oppositely directed edges are logically different,1066 // xthe maps are able to attach different values for them.1067 // x1068 // xAn example for such a construction is \c RevGraphAdaptor where the1069 // xforward_filter is everywhere false and the backward_filter is1070 // xeverywhere true. We note that for sake of efficiency,1071 // x\c RevGraphAdaptor is implemented in a different way.1072 // xBut BidirGraphAdaptor is obtained from1073 // xSubBidirGraphAdaptor by considering everywhere true1074 // xvalued maps both for forward_filter and backward_filter.1075 // x1076 // xThe most important application of SubBidirGraphAdaptor1077 // xis ResGraphAdaptor, which stands for the residual graph in directed1078 // xflow and circulation problems.1079 // xAs adaptors usually, the SubBidirGraphAdaptor implements the1080 // xabove mentioned graph structure without its physical storage,1081 // xthat is the whole stuff is stored in constant memory.1041 ///\brief An adaptor for composing a subgraph of a 1042 /// bidirected graph made from a directed one. 1043 ///\ingroup graph_adaptors 1044 /// 1045 /// An adaptor for composing a subgraph of a 1046 /// bidirected graph made from a directed one. 1047 /// 1048 ///\warning Graph adaptors are in even more experimental state 1049 ///than the other 1050 ///parts of the lib. Use them at you own risk. 1051 /// 1052 /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge 1053 /// \f$ e\in A \f$ , let \f$ \bar e \f$ denote the edge obtained by 1054 /// reversing its orientation. We are given moreover two bool valued 1055 /// maps on the edge-set, 1056 /// \f$ forward\_filter \f$ , and \f$ backward\_filter \f$ . 1057 /// SubBidirGraphAdaptor implements the graph structure with node-set 1058 /// \f$ V \f$ and edge-set 1059 /// \f$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} \f$ . 1060 /// The purpose of writing + instead of union is because parallel 1061 /// edges can arise. (Similarly, antiparallel edges also can arise). 1062 /// In other words, a subgraph of the bidirected graph obtained, which 1063 /// is given by orienting the edges of the original graph in both directions. 1064 /// As the oppositely directed edges are logically different, 1065 /// the maps are able to attach different values for them. 1066 /// 1067 /// An example for such a construction is \c RevGraphAdaptor where the 1068 /// forward_filter is everywhere false and the backward_filter is 1069 /// everywhere true. We note that for sake of efficiency, 1070 /// \c RevGraphAdaptor is implemented in a different way. 1071 /// But BidirGraphAdaptor is obtained from 1072 /// SubBidirGraphAdaptor by considering everywhere true 1073 /// valued maps both for forward_filter and backward_filter. 1074 /// 1075 /// The most important application of SubBidirGraphAdaptor 1076 /// is ResGraphAdaptor, which stands for the residual graph in directed 1077 /// flow and circulation problems. 1078 /// As adaptors usually, the SubBidirGraphAdaptor implements the 1079 /// above mentioned graph structure without its physical storage, 1080 /// that is the whole stuff is stored in constant memory. 1082 1081 template<typename _Graph, 1083 1082 typename ForwardFilterMap, typename BackwardFilterMap> … … 1103 1102 1104 1103 1105 // x\brief An adaptor for composing bidirected graph from a directed one.1106 // x\ingroup graph_adaptors1107 // x1108 // x\warning Graph adaptors are in even more experimental state1109 // xthan the other1110 // xparts of the lib. Use them at you own risk.1111 // x1112 // xAn adaptor for composing bidirected graph from a directed one.1113 // xA bidirected graph is composed over the directed one without physical1114 // xstorage. As the oppositely directed edges are logically different ones1115 // xthe maps are able to attach different values for them.1104 ///\brief An adaptor for composing bidirected graph from a directed one. 1105 ///\ingroup graph_adaptors 1106 /// 1107 ///\warning Graph adaptors are in even more experimental state 1108 ///than the other 1109 ///parts of the lib. Use them at you own risk. 1110 /// 1111 /// An adaptor for composing bidirected graph from a directed one. 1112 /// A bidirected graph is composed over the directed one without physical 1113 /// storage. As the oppositely directed edges are logically different ones 1114 /// the maps are able to attach different values for them. 1116 1115 template<typename Graph> 1117 1116 class BidirGraphAdaptor : … … 1181 1180 1182 1181 1183 // x\brief An adaptor for composing the residual1184 // xgraph for directed flow and circulation problems.1185 // x\ingroup graph_adaptors1186 // x1187 // xAn adaptor for composing the residual graph for1188 // xdirected flow and circulation problems.1189 // xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$be a1190 // xnumber type. Let moreover1191 // x\f$f,c:A\to F\f$, be functions on the edge-set.1192 // xIn the appications of ResGraphAdaptor, \f$f\f$usually stands for a flow1193 // xand \f$c\f$for a capacity function.1194 // xSuppose that a graph instange \c g of type1195 // x\c ListGraph implements \f$G\f$.1196 // x\code1197 // xListGraph g;1198 // x\endcode1199 // xThen RevGraphAdaptor implements the graph structure with node-set1200 // x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where1201 // x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$and1202 // x\f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,1203 // xi.e. the so called residual graph.1204 // xWhen we take the union \f$A_{forward}\cup A_{backward}\f$,1205 // xmultilicities are counted, i.e. if an edge is in both1206 // x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it1207 // xappears twice.1208 // xThe following code shows how1209 // xsuch an instance can be constructed.1210 // x\code1211 // xtypedef ListGraph Graph;1212 // xGraph::EdgeMap<int> f(g);1213 // xGraph::EdgeMap<int> c(g);1214 // xResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);1215 // x\endcode1216 // x\author Marton Makai1217 // x1182 ///\brief An adaptor for composing the residual 1183 ///graph for directed flow and circulation problems. 1184 ///\ingroup graph_adaptors 1185 /// 1186 ///An adaptor for composing the residual graph for 1187 ///directed flow and circulation problems. 1188 ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a 1189 ///number type. Let moreover 1190 /// \f$ f,c:A\to F \f$ , be functions on the edge-set. 1191 ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a flow 1192 ///and \f$ c \f$ for a capacity function. 1193 ///Suppose that a graph instange \c g of type 1194 ///\c ListGraph implements \f$ G \f$ . 1195 ///\code 1196 /// ListGraph g; 1197 ///\endcode 1198 ///Then RevGraphAdaptor implements the graph structure with node-set 1199 /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$ , where 1200 /// \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 1201 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$ , 1202 ///i.e. the so called residual graph. 1203 ///When we take the union \f$ A_{forward}\cup A_{backward} \f$ , 1204 ///multilicities are counted, i.e. if an edge is in both 1205 /// \f$ A_{forward} \f$ and \f$ A_{backward} \f$ , then in the adaptor it 1206 ///appears twice. 1207 ///The following code shows how 1208 ///such an instance can be constructed. 1209 ///\code 1210 ///typedef ListGraph Graph; 1211 ///Graph::EdgeMap<int> f(g); 1212 ///Graph::EdgeMap<int> c(g); 1213 ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g); 1214 ///\endcode 1215 ///\author Marton Makai 1216 /// 1218 1217 template<typename Graph, typename Number, 1219 1218 typename CapacityMap, typename FlowMap> … … 1265 1264 } 1266 1265 1267 // x\brief Residual capacity map.1268 // x1269 // xIn generic residual graphs the residual capacity can be obtained1270 // xas a map.1266 /// \brief Residual capacity map. 1267 /// 1268 /// In generic residual graphs the residual capacity can be obtained 1269 /// as a map. 1271 1270 class ResCap { 1272 1271 protected: … … 1322 1321 1323 1322 1324 // x\brief For blocking flows.1325 // x\ingroup graph_adaptors1326 // x1327 // x\warning Graph adaptors are in even more1328 // xexperimental state than the other1329 // xparts of the lib. Use them at you own risk.1330 // x1331 // xThis graph adaptor is used for on-the-fly1332 // xDinits blocking flow computations.1333 // xFor each node, an out-edge is stored which is used when the1334 // x\code1335 // xOutEdgeIt& first(OutEdgeIt&, const Node&)1336 // x\endcode1337 // xis called.1338 // x1339 // x\author Marton Makai1340 // x1323 ///\brief For blocking flows. 1324 ///\ingroup graph_adaptors 1325 /// 1326 ///\warning Graph adaptors are in even more 1327 ///experimental state than the other 1328 ///parts of the lib. Use them at you own risk. 1329 /// 1330 ///This graph adaptor is used for on-the-fly 1331 ///Dinits blocking flow computations. 1332 ///For each node, an out-edge is stored which is used when the 1333 ///\code 1334 ///OutEdgeIt& first(OutEdgeIt&, const Node&) 1335 ///\endcode 1336 ///is called. 1337 /// 1338 ///\author Marton Makai 1339 /// 1341 1340 template <typename _Graph, typename FirstOutEdgesMap> 1342 1341 class ErasingFirstGraphAdaptor : … … 1395 1394 }; 1396 1395 1397 // x\todo May we want VARIANT/union type1396 /// \todo May we want VARIANT/union type 1398 1397 class Edge : public Parent::Edge { 1399 1398 friend class SplitGraphAdaptorBase;
Note: See TracChangeset
for help on using the changeset viewer.