Changeset 1949:5db4ff8d69de in lemon-0.x for lemon
- Timestamp:
- 02/03/06 10:18:17 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2524
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_adaptor.h
r1946 r1949 39 39 namespace lemon { 40 40 41 // Graph adaptors 42 43 /*! 44 \addtogroup graph_adaptors 45 @{ 46 */ 47 48 /*! 49 Base type for the Graph Adaptors 50 51 \warning Graph adaptors are in even more experimental state than the other 52 parts of the lib. Use them at you own risk. 53 54 This is the base type for most of LEMON graph adaptors. 55 This class implements a trivial graph adaptor i.e. it only wraps the 56 functions and types of the graph. The purpose of this class is to 57 make easier implementing graph adaptors. E.g. if an adaptor is 58 considered which differs from the wrapped graph only in some of its 59 functions or types, then it can be derived from GraphAdaptor, and only the 60 differences should be implemented. 61 62 \author Marton Makai 63 */ 41 //x\brief Base type for the Graph Adaptors 42 //x\ingroup graph_adaptors 43 //x 44 //xBase type for the Graph Adaptors 45 //x 46 //x\warning Graph adaptors are in even 47 //xmore experimental state than the other 48 //xparts of the lib. Use them at you own risk. 49 //x 50 //xThis is the base type for most of LEMON graph adaptors. 51 //xThis class implements a trivial graph adaptor i.e. it only wraps the 52 //xfunctions and types of the graph. The purpose of this class is to 53 //xmake easier implementing graph adaptors. E.g. if an adaptor is 54 //xconsidered which differs from the wrapped graph only in some of its 55 //xfunctions or types, then it can be derived from GraphAdaptor, 56 //xand only the 57 //xdifferences should be implemented. 58 //x 59 //xauthor Marton Makai 64 60 template<typename _Graph> 65 61 class GraphAdaptorBase { … … 181 177 182 178 183 /// A graph adaptor which reverses the orientation of the edges. 184 185 ///\warning Graph adaptors are in even more experimental state than the other 179 ///\brief A graph adaptor which reverses the orientation of the edges. 180 ///\ingroup graph_adaptors 181 /// 182 ///\warning Graph adaptors are in even more experimental 183 ///state than the other 186 184 ///parts of the lib. Use them at you own risk. 187 185 /// 188 /// Let \f$G=(V, A)\f$ be a directed graph and 189 /// suppose that a graph instange \c g of type 190 /// \c ListGraph implements \f$G\f$. 186 /// If \c g is defined as 191 187 ///\code 192 188 /// ListGraph g; 193 189 ///\endcode 194 /// For each directed edge 195 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 196 /// reversing its orientation. 197 /// Then RevGraphAdaptor implements the graph structure with node-set 198 /// \f$V\f$ and edge-set 199 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 200 /// reversing the orientation of its edges. The following code shows how 201 /// such an instance can be constructed. 190 /// then 202 191 ///\code 203 192 /// RevGraphAdaptor<ListGraph> gw(g); 204 193 ///\endcode 205 ///\author Marton Makai 194 ///implements the graph obtained from \c g by 195 /// reversing the orientation of its edges. 206 196 207 197 template<typename _Graph> … … 291 281 } 292 282 293 /// This function hides \c n in the graph, i.e. the iteration 294 /// jumps over it. This is done by simply setting the value of \c n 295 /// to be false in the corresponding node-map. 283 //x\e 284 285 //x This function hides \c n in the graph, i.e. the iteration 286 //x jumps over it. This is done by simply setting the value of \c n 287 //x to be false in the corresponding node-map. 296 288 void hide(const Node& n) const { node_filter_map->set(n, false); } 297 289 298 /// This function hides \c e in the graph, i.e. the iteration 299 /// jumps over it. This is done by simply setting the value of \c e 300 /// to be false in the corresponding edge-map. 290 //x\e 291 292 //x This function hides \c e in the graph, i.e. the iteration 293 //x jumps over it. This is done by simply setting the value of \c e 294 //x to be false in the corresponding edge-map. 301 295 void hide(const Edge& e) const { edge_filter_map->set(e, false); } 302 296 303 /// The value of \c n is set to be true in the node-map which stores 304 /// hide information. If \c n was hidden previuosly, then it is shown 305 /// again 297 //x\e 298 299 //x The value of \c n is set to be true in the node-map which stores 300 //x hide information. If \c n was hidden previuosly, then it is shown 301 //x again 306 302 void unHide(const Node& n) const { node_filter_map->set(n, true); } 307 303 308 /// The value of \c e is set to be true in the edge-map which stores 309 /// hide information. If \c e was hidden previuosly, then it is shown 310 /// again 304 //x\e 305 306 //x The value of \c e is set to be true in the edge-map which stores 307 //x hide information. If \c e was hidden previuosly, then it is shown 308 //x again 311 309 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } 312 310 313 /// Returns true if \c n is hidden. 311 //x Returns true if \c n is hidden. 312 313 //x\e 314 //x 314 315 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 315 316 316 /// Returns true if \c n is hidden. 317 //x Returns true if \c n is hidden. 318 319 //x\e 320 //x 317 321 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 318 322 … … 383 387 } 384 388 385 /// This function hides \c n in the graph, i.e. the iteration 386 /// jumps over it. This is done by simply setting the value of \c n 387 /// to be false in the corresponding node-map. 389 //x\e 390 391 //x This function hides \c n in the graph, i.e. the iteration 392 //x jumps over it. This is done by simply setting the value of \c n 393 //x to be false in the corresponding node-map. 388 394 void hide(const Node& n) const { node_filter_map->set(n, false); } 389 395 390 /// This function hides \c e in the graph, i.e. the iteration 391 /// jumps over it. This is done by simply setting the value of \c e 392 /// to be false in the corresponding edge-map. 396 //x\e 397 398 //x This function hides \c e in the graph, i.e. the iteration 399 //x jumps over it. This is done by simply setting the value of \c e 400 //x to be false in the corresponding edge-map. 393 401 void hide(const Edge& e) const { edge_filter_map->set(e, false); } 394 402 395 /// The value of \c n is set to be true in the node-map which stores 396 /// hide information. If \c n was hidden previuosly, then it is shown 397 /// again 403 //x\e 404 405 //x The value of \c n is set to be true in the node-map which stores 406 //x hide information. If \c n was hidden previuosly, then it is shown 407 //x again 398 408 void unHide(const Node& n) const { node_filter_map->set(n, true); } 399 409 400 /// The value of \c e is set to be true in the edge-map which stores 401 /// hide information. If \c e was hidden previuosly, then it is shown 402 /// again 410 //x\e 411 412 //x The value of \c e is set to be true in the edge-map which stores 413 //x hide information. If \c e was hidden previuosly, then it is shown 414 //x again 403 415 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } 404 416 405 /// Returns true if \c n is hidden. 417 //x Returns true if \c n is hidden. 418 419 //x\e 420 //x 406 421 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 407 422 408 /// Returns true if \c n is hidden. 423 //x Returns true if \c n is hidden. 424 425 //x\e 426 //x 409 427 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 410 428 … … 413 431 }; 414 432 415 /*! \brief A graph adaptor for hiding nodes and edges from a graph. 416 417 \warning Graph adaptors are in even more experimental state than the other 418 parts of the lib. Use them at you own risk. 419 420 SubGraphAdaptor shows the graph with filtered node-set and 421 edge-set. If the \c checked parameter is true then it filters the edgeset 422 to do not get invalid edges without source or target. 423 Let \f$G=(V, A)\f$ be a directed graph 424 and suppose that the graph instance \c g of type ListGraph implements 425 \f$G\f$. 426 Let moreover \f$b_V\f$ and 427 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set. 428 SubGraphAdaptor<...>::NodeIt iterates 429 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and 430 SubGraphAdaptor<...>::EdgeIt iterates 431 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly, 432 SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates 433 only on edges leaving and entering a specific node which have true value. 434 435 If the \c checked template parameter is false then we have to note that 436 the node-iterator cares only the filter on the node-set, and the 437 edge-iterator cares only the filter on the edge-set. This way the edge-map 438 should filter all edges which's source or target is filtered by the 439 node-filter. 440 \code 441 typedef ListGraph Graph; 442 Graph g; 443 typedef Graph::Node Node; 444 typedef Graph::Edge Edge; 445 Node u=g.addNode(); //node of id 0 446 Node v=g.addNode(); //node of id 1 447 Node e=g.addEdge(u, v); //edge of id 0 448 Node f=g.addEdge(v, u); //edge of id 1 449 Graph::NodeMap<bool> nm(g, true); 450 nm.set(u, false); 451 Graph::EdgeMap<bool> em(g, true); 452 em.set(e, false); 453 typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW; 454 SubGW gw(g, nm, em); 455 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 456 std::cout << ":-)" << std::endl; 457 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 458 \endcode 459 The output of the above code is the following. 460 \code 461 1 462 :-) 463 1 464 \endcode 465 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to 466 \c Graph::Node that is why \c g.id(n) can be applied. 467 468 For other examples see also the documentation of NodeSubGraphAdaptor and 469 EdgeSubGraphAdaptor. 470 471 \author Marton Makai 472 */ 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 494 473 495 template<typename _Graph, typename NodeFilterMap, 474 496 typename EdgeFilterMap, bool checked = true> … … 493 515 494 516 495 /*! \brief An adaptor for hiding nodes from a graph. 496 497 \warning Graph adaptors are in even more experimental state than the other 498 parts of the lib. Use them at you own risk. 499 500 An adaptor for hiding nodes from a graph. 501 This adaptor specializes SubGraphAdaptor in the way that only the node-set 502 can be filtered. In usual case the checked parameter is true, we get the 503 induced subgraph. But if the checked parameter is false then we can only 504 filter only isolated nodes. 505 \author Marton Makai 506 */ 517 //x\brief An adaptor for hiding nodes from a graph. 518 //x\ingroup graph_adaptors 519 //x 520 //x\warning Graph adaptors are in even more experimental state 521 //xthan the other 522 //xparts of the lib. Use them at you own risk. 523 //x 524 //xAn adaptor for hiding nodes from a graph. 525 //xThis adaptor specializes SubGraphAdaptor in the way that only 526 //xthe node-set 527 //xcan be filtered. In usual case the checked parameter is true, we get the 528 //xinduced subgraph. But if the checked parameter is false then we can only 529 //xfilter only isolated nodes. 530 //x\author Marton Makai 507 531 template<typename Graph, typename NodeFilterMap, bool checked = true> 508 532 class NodeSubGraphAdaptor : … … 524 548 525 549 526 /*! \brief An adaptor for hiding edges from a graph. 527 528 \warning Graph adaptors are in even more experimental state than the other 529 parts of the lib. Use them at you own risk. 530 531 An adaptor for hiding edges from a graph. 532 This adaptor specializes SubGraphAdaptor in the way that only the edge-set 533 can be filtered. The usefulness of this adaptor is demonstrated in the 534 problem of searching a maximum number of edge-disjoint shortest paths 535 between 536 two nodes \c s and \c t. Shortest here means being shortest w.r.t. 537 non-negative edge-lengths. Note that 538 the comprehension of the presented solution 539 need's some elementary knowledge from combinatorial optimization. 540 541 If a single shortest path is to be 542 searched between \c s and \c t, then this can be done easily by 543 applying the Dijkstra algorithm. What happens, if a maximum number of 544 edge-disjoint shortest paths is to be computed. It can be proved that an 545 edge can be in a shortest path if and only if it is tight with respect to 546 the potential function computed by Dijkstra. Moreover, any path containing 547 only such edges is a shortest one. Thus we have to compute a maximum number 548 of edge-disjoint paths between \c s and \c t in the graph which has edge-set 549 all the tight edges. The computation will be demonstrated on the following 550 graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 551 The full source code is available in \ref sub_graph_adaptor_demo.cc. 552 If you are interested in more demo programs, you can use 553 \ref dim_to_dot.cc to generate .dot files from dimacs files. 554 The .dot file of the following figure was generated by 555 the demo program \ref dim_to_dot.cc. 556 557 \dot 558 digraph lemon_dot_example { 559 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 560 n0 [ label="0 (s)" ]; 561 n1 [ label="1" ]; 562 n2 [ label="2" ]; 563 n3 [ label="3" ]; 564 n4 [ label="4" ]; 565 n5 [ label="5" ]; 566 n6 [ label="6 (t)" ]; 567 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 568 n5 -> n6 [ label="9, length:4" ]; 569 n4 -> n6 [ label="8, length:2" ]; 570 n3 -> n5 [ label="7, length:1" ]; 571 n2 -> n5 [ label="6, length:3" ]; 572 n2 -> n6 [ label="5, length:5" ]; 573 n2 -> n4 [ label="4, length:2" ]; 574 n1 -> n4 [ label="3, length:3" ]; 575 n0 -> n3 [ label="2, length:1" ]; 576 n0 -> n2 [ label="1, length:2" ]; 577 n0 -> n1 [ label="0, length:3" ]; 578 } 579 \enddot 580 581 \code 582 Graph g; 583 Node s, t; 584 LengthMap length(g); 585 586 readDimacs(std::cin, g, length, s, t); 587 588 cout << "edges with lengths (of form id, source--length->target): " << endl; 589 for(EdgeIt e(g); e!=INVALID; ++e) 590 cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 591 << length[e] << "->" << g.id(g.target(e)) << endl; 592 593 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; 594 \endcode 595 Next, the potential function is computed with Dijkstra. 596 \code 597 typedef Dijkstra<Graph, LengthMap> Dijkstra; 598 Dijkstra dijkstra(g, length); 599 dijkstra.run(s); 600 \endcode 601 Next, we consrtruct a map which filters the edge-set to the tight edges. 602 \code 603 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 604 TightEdgeFilter; 605 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); 606 607 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW; 608 SubGW gw(g, tight_edge_filter); 609 \endcode 610 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 611 with a max flow algorithm Preflow. 612 \code 613 ConstMap<Edge, int> const_1_map(1); 614 Graph::EdgeMap<int> flow(g, 0); 615 616 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 617 preflow(gw, s, t, const_1_map, flow); 618 preflow.run(); 619 \endcode 620 Last, the output is: 621 \code 622 cout << "maximum number of edge-disjoint shortest path: " 623 << preflow.flowValue() << endl; 624 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 625 << endl; 626 for(EdgeIt e(g); e!=INVALID; ++e) 627 if (flow[e]) 628 cout << " " << g.id(g.source(e)) << "--" 629 << length[e] << "->" << g.id(g.target(e)) << endl; 630 \endcode 631 The program has the following (expected :-)) output: 632 \code 633 edges with lengths (of form id, source--length->target): 634 9, 5--4->6 635 8, 4--2->6 636 7, 3--1->5 637 6, 2--3->5 638 5, 2--5->6 639 4, 2--2->4 640 3, 1--3->4 641 2, 0--1->3 642 1, 0--2->2 643 0, 0--3->1 644 s: 0 t: 6 645 maximum number of edge-disjoint shortest path: 2 646 edges of the maximum number of edge-disjoint shortest s-t paths: 647 9, 5--4->6 648 8, 4--2->6 649 7, 3--1->5 650 4, 2--2->4 651 2, 0--1->3 652 1, 0--2->2 653 \endcode 654 655 \author Marton Makai 656 */ 550 //x\brief An adaptor for hiding edges from a graph. 551 //x 552 //x\warning Graph adaptors are in even more experimental state 553 //xthan the other parts of the lib. Use them at you own risk. 554 //x 555 //xAn adaptor for hiding edges from a graph. 556 //xThis adaptor specializes SubGraphAdaptor in the way that 557 //xonly the edge-set 558 //xcan be filtered. The usefulness of this adaptor is demonstrated in the 559 //xproblem of searching a maximum number of edge-disjoint shortest paths 560 //xbetween 561 //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t. 562 //xnon-negative edge-lengths. Note that 563 //xthe comprehension of the presented solution 564 //xneed's some elementary knowledge from combinatorial optimization. 565 //x 566 //xIf a single shortest path is to be 567 //xsearched between \c s and \c t, then this can be done easily by 568 //xapplying the Dijkstra algorithm. What happens, if a maximum number of 569 //xedge-disjoint shortest paths is to be computed. It can be proved that an 570 //xedge can be in a shortest path if and only 571 //xif it is tight with respect to 572 //xthe potential function computed by Dijkstra. 573 //xMoreover, any path containing 574 //xonly such edges is a shortest one. 575 //xThus we have to compute a maximum number 576 //xof edge-disjoint paths between \c s and \c t in 577 //xthe graph which has edge-set 578 //xall the tight edges. The computation will be demonstrated 579 //xon the following 580 //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 use 583 //x\ref dim_to_dot.cc to generate .dot files from dimacs files. 584 //xThe .dot file of the following figure was generated by 585 //xthe demo program \ref dim_to_dot.cc. 586 //x 587 //x\dot 588 //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\enddot 610 //x 611 //x\code 612 //xGraph g; 613 //xNode s, t; 614 //xLengthMap length(g); 615 //x 616 //xreadDimacs(std::cin, g, length, s, t); 617 //x 618 //xcout << "edges with lengths (of form id, source--length->target): " << endl; 619 //xfor(EdgeIt e(g); e!=INVALID; ++e) 620 //x cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 621 //x << length[e] << "->" << g.id(g.target(e)) << endl; 622 //x 623 //xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl; 624 //x\endcode 625 //xNext, the potential function is computed with Dijkstra. 626 //x\code 627 //xtypedef Dijkstra<Graph, LengthMap> Dijkstra; 628 //xDijkstra dijkstra(g, length); 629 //xdijkstra.run(s); 630 //x\endcode 631 //xNext, we consrtruct a map which filters the edge-set to the tight edges. 632 //x\code 633 //xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 634 //x TightEdgeFilter; 635 //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); 636 //x 637 //xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW; 638 //xSubGW gw(g, tight_edge_filter); 639 //x\endcode 640 //xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed 641 //xwith a max flow algorithm Preflow. 642 //x\code 643 //xConstMap<Edge, int> const_1_map(1); 644 //xGraph::EdgeMap<int> flow(g, 0); 645 //x 646 //xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 647 //x preflow(gw, s, t, const_1_map, flow); 648 //xpreflow.run(); 649 //x\endcode 650 //xLast, the output is: 651 //x\code 652 //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 //x if (flow[e]) 658 //x cout << " " << g.id(g.source(e)) << "--" 659 //x << length[e] << "->" << g.id(g.target(e)) << endl; 660 //x\endcode 661 //xThe program has the following (expected :-)) output: 662 //x\code 663 //xedges with lengths (of form id, source--length->target): 664 //x 9, 5--4->6 665 //x 8, 4--2->6 666 //x 7, 3--1->5 667 //x 6, 2--3->5 668 //x 5, 2--5->6 669 //x 4, 2--2->4 670 //x 3, 1--3->4 671 //x 2, 0--1->3 672 //x 1, 0--2->2 673 //x 0, 0--3->1 674 //xs: 0 t: 6 675 //xmaximum number of edge-disjoint shortest path: 2 676 //xedges of the maximum number of edge-disjoint shortest s-t paths: 677 //x 9, 5--4->6 678 //x 8, 4--2->6 679 //x 7, 3--1->5 680 //x 4, 2--2->4 681 //x 2, 0--1->3 682 //x 1, 0--2->2 683 //x\endcode 684 //x 685 //x\author Marton Makai 657 686 template<typename Graph, typename EdgeFilterMap> 658 687 class EdgeSubGraphAdaptor : … … 741 770 }; 742 771 743 /// \brief An undirected graph is made from a directed graph by an adaptor 744 /// 745 /// Undocumented, untested!!! 746 /// If somebody knows nice demo application, let's polulate it. 747 /// 748 /// \author Marton Makai 772 //x\brief An undirected graph is made from a directed graph by an adaptor 773 //x\ingroup graph_adaptors 774 //x 775 //x Undocumented, untested!!! 776 //x If somebody knows nice demo application, let's polulate it. 777 //x 778 //x \author Marton Makai 749 779 template<typename _Graph> 750 780 class UGraphAdaptor : … … 794 824 typedef typename _Graph::Edge GraphEdge; 795 825 template <typename T> class EdgeMap; 796 // /SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from797 // /_Graph::Edge. It contains an extra bool flag which is true798 // /if and only if the799 // /edge is the backward version of the original edge.826 // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 827 // _Graph::Edge. It contains an extra bool flag which is true 828 // if and only if the 829 // edge is the backward version of the original edge. 800 830 class Edge : public _Graph::Edge { 801 831 friend class SubBidirGraphAdaptorBase< … … 806 836 public: 807 837 Edge() { } 808 // /\todo =false is needed, or causes problems?809 // /If \c _backward is false, then we get an edge corresponding to the810 // /original one, otherwise its oppositely directed pair is obtained.838 // \todo =false is needed, or causes problems? 839 // If \c _backward is false, then we get an edge corresponding to the 840 // original one, otherwise its oppositely directed pair is obtained. 811 841 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 812 842 _Graph::Edge(e), backward(_backward) { } … … 932 962 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } 933 963 934 /// Gives back the opposite edge. 964 //x Gives back the opposite edge. 965 966 //x\e 967 //x 935 968 Edge opposite(const Edge& e) const { 936 969 Edge f=e; … … 939 972 } 940 973 941 /// \warning This is a linear time operation and works only if 942 /// \c Graph::EdgeIt is defined. 943 /// \todo hmm 974 //x\e 975 976 //x \warning This is a linear time operation and works only if 977 //x \c Graph::EdgeIt is defined. 978 //x \todo hmm 944 979 int edgeNum() const { 945 980 int i=0; … … 952 987 bool backward(const Edge& e) const { return e.backward; } 953 988 989 //x\e 990 991 //x \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 992 //x _Graph::EdgeMap one for the forward edges and 993 //x one for the backward edges. 954 994 template <typename T> 955 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two956 /// _Graph::EdgeMap one for the forward edges and957 /// one for the backward edges.958 995 class EdgeMap { 959 996 template <typename TT> friend class EdgeMap; … … 1003 1040 1004 1041 1005 ///\brief An adaptor for composing a subgraph of a 1006 /// bidirected graph made from a directed one. 1007 /// 1008 /// An adaptor for composing a subgraph of a 1009 /// bidirected graph made from a directed one. 1010 /// 1011 ///\warning Graph adaptors are in even more experimental state than the other 1012 ///parts of the lib. Use them at you own risk. 1013 /// 1014 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 1015 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 1016 /// reversing its orientation. We are given moreover two bool valued 1017 /// maps on the edge-set, 1018 /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 1019 /// SubBidirGraphAdaptor implements the graph structure with node-set 1020 /// \f$V\f$ and edge-set 1021 /// \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$. 1022 /// The purpose of writing + instead of union is because parallel 1023 /// edges can arise. (Similarly, antiparallel edges also can arise). 1024 /// In other words, a subgraph of the bidirected graph obtained, which 1025 /// is given by orienting the edges of the original graph in both directions. 1026 /// As the oppositely directed edges are logically different, 1027 /// the maps are able to attach different values for them. 1028 /// 1029 /// An example for such a construction is \c RevGraphAdaptor where the 1030 /// forward_filter is everywhere false and the backward_filter is 1031 /// everywhere true. We note that for sake of efficiency, 1032 /// \c RevGraphAdaptor is implemented in a different way. 1033 /// But BidirGraphAdaptor is obtained from 1034 /// SubBidirGraphAdaptor by considering everywhere true 1035 /// valued maps both for forward_filter and backward_filter. 1036 /// 1037 /// The most important application of SubBidirGraphAdaptor 1038 /// is ResGraphAdaptor, which stands for the residual graph in directed 1039 /// flow and circulation problems. 1040 /// As adaptors usually, the SubBidirGraphAdaptor implements the 1041 /// above mentioned graph structure without its physical storage, 1042 /// that is the whole stuff is stored in constant memory. 1042 //x\brief An adaptor for composing a subgraph of a 1043 //x bidirected graph made from a directed one. 1044 //x\ingroup graph_adaptors 1045 //x 1046 //x An adaptor for composing a subgraph of a 1047 //x bidirected graph made from a directed one. 1048 //x 1049 //x\warning Graph adaptors are in even more experimental state 1050 //xthan the other 1051 //xparts of the lib. Use them at you own risk. 1052 //x 1053 //x Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 1054 //x \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 1055 //x reversing its orientation. We are given moreover two bool valued 1056 //x maps on the edge-set, 1057 //x \f$forward\_filter\f$, and \f$backward\_filter\f$. 1058 //x SubBidirGraphAdaptor implements the graph structure with node-set 1059 //x \f$V\f$ and edge-set 1060 //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 //x The purpose of writing + instead of union is because parallel 1062 //x edges can arise. (Similarly, antiparallel edges also can arise). 1063 //x In other words, a subgraph of the bidirected graph obtained, which 1064 //x is given by orienting the edges of the original graph in both directions. 1065 //x As the oppositely directed edges are logically different, 1066 //x the maps are able to attach different values for them. 1067 //x 1068 //x An example for such a construction is \c RevGraphAdaptor where the 1069 //x forward_filter is everywhere false and the backward_filter is 1070 //x everywhere true. We note that for sake of efficiency, 1071 //x \c RevGraphAdaptor is implemented in a different way. 1072 //x But BidirGraphAdaptor is obtained from 1073 //x SubBidirGraphAdaptor by considering everywhere true 1074 //x valued maps both for forward_filter and backward_filter. 1075 //x 1076 //x The most important application of SubBidirGraphAdaptor 1077 //x is ResGraphAdaptor, which stands for the residual graph in directed 1078 //x flow and circulation problems. 1079 //x As adaptors usually, the SubBidirGraphAdaptor implements the 1080 //x above mentioned graph structure without its physical storage, 1081 //x that is the whole stuff is stored in constant memory. 1043 1082 template<typename _Graph, 1044 1083 typename ForwardFilterMap, typename BackwardFilterMap> … … 1064 1103 1065 1104 1066 ///\brief An adaptor for composing bidirected graph from a directed one. 1067 /// 1068 ///\warning Graph adaptors are in even more experimental state than the other 1069 ///parts of the lib. Use them at you own risk. 1070 /// 1071 /// An adaptor for composing bidirected graph from a directed one. 1072 /// A bidirected graph is composed over the directed one without physical 1073 /// storage. As the oppositely directed edges are logically different ones 1074 /// the maps are able to attach different values for them. 1105 //x\brief An adaptor for composing bidirected graph from a directed one. 1106 //x\ingroup graph_adaptors 1107 //x 1108 //x\warning Graph adaptors are in even more experimental state 1109 //xthan the other 1110 //xparts of the lib. Use them at you own risk. 1111 //x 1112 //x An adaptor for composing bidirected graph from a directed one. 1113 //x A bidirected graph is composed over the directed one without physical 1114 //x storage. As the oppositely directed edges are logically different ones 1115 //x the maps are able to attach different values for them. 1075 1116 template<typename Graph> 1076 1117 class BidirGraphAdaptor : … … 1140 1181 1141 1182 1142 /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems. 1143 1144 An adaptor for composing the residual graph for directed flow and circulation problems. 1145 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a 1146 number type. Let moreover 1147 \f$f,c:A\to F\f$, be functions on the edge-set. 1148 In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow 1149 and \f$c\f$ for a capacity function. 1150 Suppose that a graph instange \c g of type 1151 \c ListGraph implements \f$G\f$. 1152 \code 1153 ListGraph g; 1154 \endcode 1155 Then RevGraphAdaptor implements the graph structure with node-set 1156 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where 1157 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and 1158 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$, 1159 i.e. the so called residual graph. 1160 When we take the union \f$A_{forward}\cup A_{backward}\f$, 1161 multilicities are counted, i.e. if an edge is in both 1162 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it 1163 appears twice. 1164 The following code shows how 1165 such an instance can be constructed. 1166 \code 1167 typedef ListGraph Graph; 1168 Graph::EdgeMap<int> f(g); 1169 Graph::EdgeMap<int> c(g); 1170 ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g); 1171 \endcode 1172 \author Marton Makai 1173 */ 1183 //x\brief An adaptor for composing the residual 1184 //xgraph for directed flow and circulation problems. 1185 //x\ingroup graph_adaptors 1186 //x 1187 //xAn adaptor for composing the residual graph for 1188 //xdirected flow and circulation problems. 1189 //xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a 1190 //xnumber type. Let moreover 1191 //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 flow 1193 //xand \f$c\f$ for a capacity function. 1194 //xSuppose that a graph instange \c g of type 1195 //x\c ListGraph implements \f$G\f$ . 1196 //x\code 1197 //x ListGraph g; 1198 //x\endcode 1199 //xThen RevGraphAdaptor implements the graph structure with node-set 1200 //x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where 1201 //x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and 1202 //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 both 1206 //x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it 1207 //xappears twice. 1208 //xThe following code shows how 1209 //xsuch an instance can be constructed. 1210 //x\code 1211 //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\endcode 1216 //x\author Marton Makai 1217 //x 1174 1218 template<typename Graph, typename Number, 1175 1219 typename CapacityMap, typename FlowMap> … … 1221 1265 } 1222 1266 1223 // /\brief Residual capacity map.1224 // /1225 // /In generic residual graphs the residual capacity can be obtained1226 // /as a map.1267 //x \brief Residual capacity map. 1268 //x 1269 //x In generic residual graphs the residual capacity can be obtained 1270 //x as a map. 1227 1271 class ResCap { 1228 1272 protected: … … 1278 1322 1279 1323 1280 /// For blocking flows. 1281 1282 ///\warning Graph adaptors are in even more 1283 ///experimental state than the other 1284 ///parts of the lib. Use them at you own risk. 1285 /// 1286 ///This graph adaptor is used for on-the-fly 1287 ///Dinits blocking flow computations. 1288 ///For each node, an out-edge is stored which is used when the 1289 ///\code OutEdgeIt& first(OutEdgeIt&, const Node&)\endcode 1290 ///is called. 1291 /// 1292 ///\author Marton Makai 1293 /// 1324 //x\brief For blocking flows. 1325 //x\ingroup graph_adaptors 1326 //x 1327 //x\warning Graph adaptors are in even more 1328 //xexperimental state than the other 1329 //xparts of the lib. Use them at you own risk. 1330 //x 1331 //xThis graph adaptor is used for on-the-fly 1332 //xDinits blocking flow computations. 1333 //xFor each node, an out-edge is stored which is used when the 1334 //x\code 1335 //xOutEdgeIt& first(OutEdgeIt&, const Node&) 1336 //x\endcode 1337 //xis called. 1338 //x 1339 //x\author Marton Makai 1340 //x 1294 1341 template <typename _Graph, typename FirstOutEdgesMap> 1295 1342 class ErasingFirstGraphAdaptor : … … 1348 1395 }; 1349 1396 1350 // /\todo May we want VARIANT/union type1397 //x \todo May we want VARIANT/union type 1351 1398 class Edge : public Parent::Edge { 1352 1399 friend class SplitGraphAdaptorBase; … … 1675 1722 }; 1676 1723 1677 ///@}1678 1679 1724 } //namespace lemon 1680 1725
Note: See TracChangeset
for help on using the changeset viewer.