Changeset 455:5a1e9fdcfd3a in lemon1.2
 Timestamp:
 01/11/09 16:09:53 (11 years ago)
 Branch:
 default
 Children:
 456:aff6888e71c9, 463:a2fd8b8d0b30
 Parents:
 445:75a5df083951 (diff), 454:f599fa651202 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 5 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r440 r455 63 63 64 64 /** 65 @defgroup graph_adaptors Adaptor Classes for graphs65 @defgroup graph_adaptors Adaptor Classes for Graphs 66 66 @ingroup graphs 67 \brief This group contains several adaptor classes for digraphs and graphs 67 \brief Adaptor classes for digraphs and graphs 68 69 This group contains several useful adaptor classes for digraphs and graphs. 68 70 69 71 The main parts of LEMON are the different graph structures, generic 70 graph algorithms, graph concepts which couple these, and graph72 graph algorithms, graph concepts, which couple them, and graph 71 73 adaptors. While the previous notions are more or less clear, the 72 74 latter one needs further explanation. Graph adaptors are graph classes … … 74 76 75 77 A short example makes this much clearer. Suppose that we have an 76 instance \c g of a directed graph type say ListDigraph and an algorithm78 instance \c g of a directed graph type, say ListDigraph and an algorithm 77 79 \code 78 80 template <typename Digraph> … … 82 84 (in time or in memory usage) to copy \c g with the reversed 83 85 arcs. In this case, an adaptor class is used, which (according 84 to LEMON digraph concepts) works as a digraph. The adaptor uses the85 original digraph structure and digraph operations when methods of the 86 reversed oriented graph are called. This means that the adaptor have 87 minor memory usage, and do not perform sophisticated algorithmic86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. 87 The adaptor uses the original digraph structure and digraph operations when 88 methods of the reversed oriented graph are called. This means that the adaptor 89 have minor memory usage, and do not perform sophisticated algorithmic 88 90 actions. The purpose of it is to give a tool for the cases when a 89 91 graph have to be used in a specific alteration. If this alteration is 90 obtained by a usual construction like filtering the arcset or92 obtained by a usual construction like filtering the node or the arc set or 91 93 considering a new orientation, then an adaptor is worthwhile to use. 92 94 To come back to the reverse oriented graph, in this situation … … 97 99 \code 98 100 ListDigraph g; 99 ReverseDigraph<List Graph> rg(g);101 ReverseDigraph<ListDigraph> rg(g); 100 102 int result = algorithm(rg); 101 103 \endcode 102 After running the algorithm, the originalgraph \c g is untouched.103 This techniques give srise to an elegant code, and based on stable104 During running the algorithm, the original digraph \c g is untouched. 105 This techniques give rise to an elegant code, and based on stable 104 106 graph adaptors, complex algorithms can be implemented easily. 105 107 106 In flow, circulation and bipartitematching problems, the residual108 In flow, circulation and matching problems, the residual 107 109 graph is of particular importance. Combining an adaptor implementing 108 this , shortest path algorithms andminimum mean cycle algorithms,110 this with shortest path algorithms or minimum mean cycle algorithms, 109 111 a range of weighted and cardinality optimization algorithms can be 110 112 obtained. For other examples, the interested user is referred to the … … 113 115 The behavior of graph adaptors can be very different. Some of them keep 114 116 capabilities of the original graph while in other cases this would be 115 meaningless. This means that the concepts that they are models of depend 116 on the graph adaptor, and the wrapped graph(s). 117 If an arc of \c rg is deleted, this is carried out by deleting the 118 corresponding arc of \c g, thus the adaptor modifies the original graph. 119 120 But for a residual graph, this operation has no sense. 117 meaningless. This means that the concepts that they meet depend 118 on the graph adaptor, and the wrapped graph. 119 For example, if an arc of a reversed digraph is deleted, this is carried 120 out by deleting the corresponding arc of the original digraph, thus the 121 adaptor modifies the original digraph. 122 However in case of a residual digraph, this operation has no sense. 123 121 124 Let us stand one more example here to simplify your work. 122 Rev GraphAdaptorhas constructor125 ReverseDigraph has constructor 123 126 \code 124 127 ReverseDigraph(Digraph& digraph); 125 128 \endcode 126 This means that in a situation, when a <tt>const ListDigraph&</tt>129 This means that in a situation, when a <tt>const %ListDigraph&</tt> 127 130 reference to a graph is given, then it have to be instantiated with 128 <tt>Digraph=const ListDigraph</tt>.131 <tt>Digraph=const %ListDigraph</tt>. 129 132 \code 130 133 int algorithm1(const ListDigraph& g) { 131 Rev GraphAdaptor<const ListDigraph> rg(g);134 ReverseDigraph<const ListDigraph> rg(g); 132 135 return algorithm2(rg); 133 136 } 
doc/groups.dox
r451 r455 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003200 85 * Copyright (C) 20032009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 
lemon/adaptors.h
r440 r455 22 22 /// \ingroup graph_adaptors 23 23 /// \file 24 /// \brief Several graph adaptors24 /// \brief Adaptor classes for digraphs and graphs 25 25 /// 26 26 /// This file contains several useful adaptors for digraphs and graphs. … … 71 71 int nodeNum() const { return _digraph>nodeNum(); } 72 72 73 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;73 typedef ArcNumTagIndicator<Digraph> ArcNumTag; 74 74 int arcNum() const { return _digraph>arcNum(); } 75 75 76 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;77 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {76 typedef FindArcTagIndicator<Digraph> FindArcTag; 77 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { 78 78 return _digraph>findArc(u, v, prev); 79 79 } … … 82 82 Arc addArc(const Node& u, const Node& v) { return _digraph>addArc(u, v); } 83 83 84 void erase(const Node& n) const{ _digraph>erase(n); }85 void erase(const Arc& a) const{ _digraph>erase(a); }86 87 void clear() const{ _digraph>clear(); }84 void erase(const Node& n) { _digraph>erase(n); } 85 void erase(const Arc& a) { _digraph>erase(a); } 86 87 void clear() { _digraph>clear(); } 88 88 89 89 int id(const Node& n) const { return _digraph>id(n); } … … 199 199 int nodeNum() const { return _graph>nodeNum(); } 200 200 201 typedef ArcNumTagIndicator<Graph> ArcNumTag; 202 int arcNum() const { return _graph>arcNum(); } 203 201 204 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 202 int arcNum() const { return _graph>arcNum(); }203 205 int edgeNum() const { return _graph>edgeNum(); } 204 206 207 typedef FindArcTagIndicator<Graph> FindArcTag; 208 Arc findArc(const Node& u, const Node& v, 209 const Arc& prev = INVALID) const { 210 return _graph>findArc(u, v, prev); 211 } 212 205 213 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 206 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { 207 return _graph>findArc(u, v, prev); 208 } 209 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) { 214 Edge findEdge(const Node& u, const Node& v, 215 const Edge& prev = INVALID) const { 210 216 return _graph>findEdge(u, v, prev); 211 217 } … … 331 337 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } 332 338 333 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;339 typedef FindArcTagIndicator<Digraph> FindArcTag; 334 340 Arc findArc(const Node& u, const Node& v, 335 const Arc& prev = INVALID) {341 const Arc& prev = INVALID) const { 336 342 return Parent::findArc(v, u, prev); 337 343 } … … 341 347 /// \ingroup graph_adaptors 342 348 /// 343 /// \brief A digraph adaptor which reverses the orientation of the arcs. 344 /// 345 /// ReverseDigraph reverses the arcs in the adapted digraph. The 346 /// SubDigraph is conform to the \ref concepts::Digraph 347 /// "Digraph concept". 348 /// 349 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 350 /// "Digraph concept". The type can be specified to be const. 351 template<typename _Digraph> 349 /// \brief Adaptor class for reversing the orientation of the arcs in 350 /// a digraph. 351 /// 352 /// ReverseDigraph can be used for reversing the arcs in a digraph. 353 /// It conforms to the \ref concepts::Digraph "Digraph" concept. 354 /// 355 /// The adapted digraph can also be modified through this adaptor 356 /// by adding or removing nodes or arcs, unless the \c GR template 357 /// parameter is set to be \c const. 358 /// 359 /// \tparam GR The type of the adapted digraph. 360 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 361 /// It can also be specified to be \c const. 362 /// 363 /// \note The \c Node and \c Arc types of this adaptor and the adapted 364 /// digraph are convertible to each other. 365 template<typename GR> 366 #ifdef DOXYGEN 367 class ReverseDigraph { 368 #else 352 369 class ReverseDigraph : 353 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > { 354 public: 355 typedef _Digraph Digraph; 356 typedef DigraphAdaptorExtender< 357 ReverseDigraphBase<_Digraph> > Parent; 370 public DigraphAdaptorExtender<ReverseDigraphBase<GR> > { 371 #endif 372 public: 373 /// The type of the adapted digraph. 374 typedef GR Digraph; 375 typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent; 358 376 protected: 359 377 ReverseDigraph() { } … … 362 380 /// \brief Constructor 363 381 /// 364 /// Creates a reverse digraph adaptor for the given digraph 382 /// Creates a reverse digraph adaptor for the given digraph. 365 383 explicit ReverseDigraph(Digraph& digraph) { 366 384 Parent::setDigraph(digraph); … … 368 386 }; 369 387 370 /// \brief Just gives back a reverse digraph adaptor 371 /// 372 /// Just gives back a reverse digraph adaptor 373 template<typename Digraph> 374 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) { 375 return ReverseDigraph<const Digraph>(digraph); 388 /// \brief Returns a readonly ReverseDigraph adaptor 389 /// 390 /// This function just returns a readonly \ref ReverseDigraph adaptor. 391 /// \ingroup graph_adaptors 392 /// \relates ReverseDigraph 393 template<typename GR> 394 ReverseDigraph<const GR> reverseDigraph(const GR& digraph) { 395 return ReverseDigraph<const GR>(digraph); 376 396 } 397 377 398 378 399 template <typename _Digraph, typename _NodeFilterMap, … … 458 479 } 459 480 460 void hide(const Node& n) const { _node_filter>set(n, false); } 461 void hide(const Arc& a) const { _arc_filter>set(a, false); } 462 463 void unHide(const Node& n) const { _node_filter>set(n, true); } 464 void unHide(const Arc& a) const { _arc_filter>set(a, true); } 465 466 bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 467 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; } 481 void status(const Node& n, bool v) const { _node_filter>set(n, v); } 482 void status(const Arc& a, bool v) const { _arc_filter>set(a, v); } 483 484 bool status(const Node& n) const { return (*_node_filter)[n]; } 485 bool status(const Arc& a) const { return (*_arc_filter)[a]; } 468 486 469 487 typedef False NodeNumTag; 470 typedef False EdgeNumTag;471 472 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;488 typedef False ArcNumTag; 489 490 typedef FindArcTagIndicator<Digraph> FindArcTag; 473 491 Arc findArc(const Node& source, const Node& target, 474 const Arc& prev = INVALID) {492 const Arc& prev = INVALID) const { 475 493 if (!(*_node_filter)[source]  !(*_node_filter)[target]) { 476 494 return INVALID; … … 601 619 } 602 620 603 void hide(const Node& n) const { _node_filter>set(n, false); } 604 void hide(const Arc& e) const { _arc_filter>set(e, false); } 605 606 void unHide(const Node& n) const { _node_filter>set(n, true); } 607 void unHide(const Arc& e) const { _arc_filter>set(e, true); } 608 609 bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 610 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; } 621 void status(const Node& n, bool v) const { _node_filter>set(n, v); } 622 void status(const Arc& a, bool v) const { _arc_filter>set(a, v); } 623 624 bool status(const Node& n) const { return (*_node_filter)[n]; } 625 bool status(const Arc& a) const { return (*_arc_filter)[a]; } 611 626 612 627 typedef False NodeNumTag; 613 typedef False EdgeNumTag;614 615 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;628 typedef False ArcNumTag; 629 630 typedef FindArcTagIndicator<Digraph> FindArcTag; 616 631 Arc findArc(const Node& source, const Node& target, 617 const Arc& prev = INVALID) {632 const Arc& prev = INVALID) const { 618 633 if (!(*_node_filter)[source]  !(*_node_filter)[target]) { 619 634 return INVALID; … … 680 695 /// \ingroup graph_adaptors 681 696 /// 682 /// \brief An adaptor for hiding nodes and arcs in a digraph 683 /// 684 /// SubDigraph hides nodes and arcs in a digraph. A bool node map 685 /// and a bool arc map must be specified, which define the filters 686 /// for nodes and arcs. Just the nodes and arcs with true value are 687 /// shown in the subdigraph. The SubDigraph is conform to the \ref 688 /// concepts::Digraph "Digraph concept". If the \c _checked parameter 689 /// is true, then the arcs incident to filtered nodes are also 690 /// filtered out. 691 /// 692 /// \tparam _Digraph It must be conform to the \ref 693 /// concepts::Digraph "Digraph concept". The type can be specified 694 /// to const. 695 /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph. 696 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph. 697 /// \tparam _checked If the parameter is false then the arc filtering 698 /// is not checked with respect to node filter. Otherwise, each arc 699 /// is automatically filtered, which is incident to a filtered node. 697 /// \brief Adaptor class for hiding nodes and arcs in a digraph 698 /// 699 /// SubDigraph can be used for hiding nodes and arcs in a digraph. 700 /// A \c bool node map and a \c bool arc map must be specified, which 701 /// define the filters for nodes and arcs. 702 /// Only the nodes and arcs with \c true filter value are 703 /// shown in the subdigraph. The arcs that are incident to hidden 704 /// nodes are also filtered out. 705 /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept. 706 /// 707 /// The adapted digraph can also be modified through this adaptor 708 /// by adding or removing nodes or arcs, unless the \c GR template 709 /// parameter is set to be \c const. 710 /// 711 /// \tparam GR The type of the adapted digraph. 712 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 713 /// It can also be specified to be \c const. 714 /// \tparam NF The type of the node filter map. 715 /// It must be a \c bool (or convertible) node map of the 716 /// adapted digraph. The default type is 717 /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>". 718 /// \tparam AF The type of the arc filter map. 719 /// It must be \c bool (or convertible) arc map of the 720 /// adapted digraph. The default type is 721 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>". 722 /// 723 /// \note The \c Node and \c Arc types of this adaptor and the adapted 724 /// digraph are convertible to each other. 700 725 /// 701 726 /// \see FilterNodes 702 727 /// \see FilterArcs 703 template<typename _Digraph, 704 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 705 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 706 bool _checked = true> 707 class SubDigraph 708 : public DigraphAdaptorExtender< 709 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > { 710 public: 711 typedef _Digraph Digraph; 712 typedef _NodeFilterMap NodeFilterMap; 713 typedef _ArcFilterMap ArcFilterMap; 714 715 typedef DigraphAdaptorExtender< 716 SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> > 717 Parent; 728 #ifdef DOXYGEN 729 template<typename GR, typename NF, typename AF> 730 class SubDigraph { 731 #else 732 template<typename GR, 733 typename NF = typename GR::template NodeMap<bool>, 734 typename AF = typename GR::template ArcMap<bool> > 735 class SubDigraph : 736 public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > { 737 #endif 738 public: 739 /// The type of the adapted digraph. 740 typedef GR Digraph; 741 /// The type of the node filter map. 742 typedef NF NodeFilterMap; 743 /// The type of the arc filter map. 744 typedef AF ArcFilterMap; 745 746 typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > 747 Parent; 718 748 719 749 typedef typename Parent::Node Node; … … 726 756 /// \brief Constructor 727 757 /// 728 /// Creates a subdigraph for the given digraph with 729 /// given node and arc map filters.758 /// Creates a subdigraph for the given digraph with the 759 /// given node and arc filter maps. 730 760 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, 731 761 ArcFilterMap& arc_filter) { … … 735 765 } 736 766 737 /// \brief Hides the node of the graph 738 /// 739 /// This function hides \c n in the digraph, i.e. the iteration 740 /// jumps over it. This is done by simply setting the value of \c n 741 /// to be false in the corresponding nodemap. 742 void hide(const Node& n) const { Parent::hide(n); } 743 744 /// \brief Hides the arc of the graph 745 /// 746 /// This function hides \c a in the digraph, i.e. the iteration 747 /// jumps over it. This is done by simply setting the value of \c a 748 /// to be false in the corresponding arcmap. 749 void hide(const Arc& a) const { Parent::hide(a); } 750 751 /// \brief Unhides the node of the graph 752 /// 753 /// The value of \c n is set to be true in the nodemap which stores 754 /// hide information. If \c n was hidden previuosly, then it is shown 755 /// again 756 void unHide(const Node& n) const { Parent::unHide(n); } 757 758 /// \brief Unhides the arc of the graph 759 /// 760 /// The value of \c a is set to be true in the arcmap which stores 761 /// hide information. If \c a was hidden previuosly, then it is shown 762 /// again 763 void unHide(const Arc& a) const { Parent::unHide(a); } 764 765 /// \brief Returns true if \c n is hidden. 766 /// 767 /// Returns true if \c n is hidden. 768 /// 769 bool hidden(const Node& n) const { return Parent::hidden(n); } 770 771 /// \brief Returns true if \c a is hidden. 772 /// 773 /// Returns true if \c a is hidden. 774 /// 775 bool hidden(const Arc& a) const { return Parent::hidden(a); } 767 /// \brief Sets the status of the given node 768 /// 769 /// This function sets the status of the given node. 770 /// It is done by simply setting the assigned value of \c n 771 /// to \c v in the node filter map. 772 void status(const Node& n, bool v) const { Parent::status(n, v); } 773 774 /// \brief Sets the status of the given arc 775 /// 776 /// This function sets the status of the given arc. 777 /// It is done by simply setting the assigned value of \c a 778 /// to \c v in the arc filter map. 779 void status(const Arc& a, bool v) const { Parent::status(a, v); } 780 781 /// \brief Returns the status of the given node 782 /// 783 /// This function returns the status of the given node. 784 /// It is \c true if the given node is enabled (i.e. not hidden). 785 bool status(const Node& n) const { return Parent::status(n); } 786 787 /// \brief Returns the status of the given arc 788 /// 789 /// This function returns the status of the given arc. 790 /// It is \c true if the given arc is enabled (i.e. not hidden). 791 bool status(const Arc& a) const { return Parent::status(a); } 792 793 /// \brief Disables the given node 794 /// 795 /// This function disables the given node in the subdigraph, 796 /// so the iteration jumps over it. 797 /// It is the same as \ref status() "status(n, false)". 798 void disable(const Node& n) const { Parent::status(n, false); } 799 800 /// \brief Disables the given arc 801 /// 802 /// This function disables the given arc in the subdigraph, 803 /// so the iteration jumps over it. 804 /// It is the same as \ref status() "status(a, false)". 805 void disable(const Arc& a) const { Parent::status(a, false); } 806 807 /// \brief Enables the given node 808 /// 809 /// This function enables the given node in the subdigraph. 810 /// It is the same as \ref status() "status(n, true)". 811 void enable(const Node& n) const { Parent::status(n, true); } 812 813 /// \brief Enables the given arc 814 /// 815 /// This function enables the given arc in the subdigraph. 816 /// It is the same as \ref status() "status(a, true)". 817 void enable(const Arc& a) const { Parent::status(a, true); } 776 818 777 819 }; 778 820 779 /// \brief Just gives back a subdigraph 780 /// 781 /// Just gives back a subdigraph 782 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 783 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 784 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) { 785 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 786 (digraph, nfm, afm); 821 /// \brief Returns a readonly SubDigraph adaptor 822 /// 823 /// This function just returns a readonly \ref SubDigraph adaptor. 824 /// \ingroup graph_adaptors 825 /// \relates SubDigraph 826 template<typename GR, typename NF, typename AF> 827 SubDigraph<const GR, NF, AF> 828 subDigraph(const GR& digraph, 829 NF& node_filter_map, AF& arc_filter_map) { 830 return SubDigraph<const GR, NF, AF> 831 (digraph, node_filter_map, arc_filter_map); 787 832 } 788 833 789 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>790 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>791 subDigraph(const Digraph& digraph,792 const N odeFilterMap& nfm, ArcFilterMap& afm) {793 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>794 (digraph, n fm, afm);834 template<typename GR, typename NF, typename AF> 835 SubDigraph<const GR, const NF, AF> 836 subDigraph(const GR& digraph, 837 const NF& node_filter_map, AF& arc_filter_map) { 838 return SubDigraph<const GR, const NF, AF> 839 (digraph, node_filter_map, arc_filter_map); 795 840 } 796 841 797 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>798 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>799 subDigraph(const Digraph& digraph,800 N odeFilterMap& nfm, const ArcFilterMap& afm) {801 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>802 (digraph, n fm, afm);842 template<typename GR, typename NF, typename AF> 843 SubDigraph<const GR, NF, const AF> 844 subDigraph(const GR& digraph, 845 NF& node_filter_map, const AF& arc_filter_map) { 846 return SubDigraph<const GR, NF, const AF> 847 (digraph, node_filter_map, arc_filter_map); 803 848 } 804 849 805 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>806 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>807 subDigraph(const Digraph& digraph,808 const N odeFilterMap& nfm, const ArcFilterMap& afm) {809 return SubDigraph<const Digraph, const NodeFilterMap,810 const ArcFilterMap>(digraph, nfm, afm);850 template<typename GR, typename NF, typename AF> 851 SubDigraph<const GR, const NF, const AF> 852 subDigraph(const GR& digraph, 853 const NF& node_filter_map, const AF& arc_filter_map) { 854 return SubDigraph<const GR, const NF, const AF> 855 (digraph, node_filter_map, arc_filter_map); 811 856 } 812 857 813 858 814 template <typename _Graph, typename NodeFilterMap,815 typename EdgeFilterMap, bool _checked = true>859 template <typename _Graph, typename _NodeFilterMap, 860 typename _EdgeFilterMap, bool _checked = true> 816 861 class SubGraphBase : public GraphAdaptorBase<_Graph> { 817 862 public: 818 863 typedef _Graph Graph; 864 typedef _NodeFilterMap NodeFilterMap; 865 typedef _EdgeFilterMap EdgeFilterMap; 866 819 867 typedef SubGraphBase Adaptor; 820 868 typedef GraphAdaptorBase<_Graph> Parent; … … 926 974 } 927 975 928 void hide(const Node& n) const { _node_filter_map>set(n, false); } 929 void hide(const Edge& e) const { _edge_filter_map>set(e, false); } 930 931 void unHide(const Node& n) const { _node_filter_map>set(n, true); } 932 void unHide(const Edge& e) const { _edge_filter_map>set(e, true); } 933 934 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 935 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 976 void status(const Node& n, bool v) const { _node_filter_map>set(n, v); } 977 void status(const Edge& e, bool v) const { _edge_filter_map>set(e, v); } 978 979 bool status(const Node& n) const { return (*_node_filter_map)[n]; } 980 bool status(const Edge& e) const { return (*_edge_filter_map)[e]; } 936 981 937 982 typedef False NodeNumTag; 983 typedef False ArcNumTag; 938 984 typedef False EdgeNumTag; 939 985 940 typedef Find EdgeTagIndicator<Graph> FindEdgeTag;986 typedef FindArcTagIndicator<Graph> FindArcTag; 941 987 Arc findArc(const Node& u, const Node& v, 942 const Arc& prev = INVALID) {988 const Arc& prev = INVALID) const { 943 989 if (!(*_node_filter_map)[u]  !(*_node_filter_map)[v]) { 944 990 return INVALID; … … 950 996 return arc; 951 997 } 998 999 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 952 1000 Edge findEdge(const Node& u, const Node& v, 953 const Edge& prev = INVALID) {1001 const Edge& prev = INVALID) const { 954 1002 if (!(*_node_filter_map)[u]  !(*_node_filter_map)[v]) { 955 1003 return INVALID; … … 1040 1088 }; 1041 1089 1042 template <typename _Graph, typename NodeFilterMap, typenameEdgeFilterMap>1043 class SubGraphBase<_Graph, NodeFilterMap,EdgeFilterMap, false>1090 template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap> 1091 class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false> 1044 1092 : public GraphAdaptorBase<_Graph> { 1045 1093 public: 1046 1094 typedef _Graph Graph; 1095 typedef _NodeFilterMap NodeFilterMap; 1096 typedef _EdgeFilterMap EdgeFilterMap; 1097 1047 1098 typedef SubGraphBase Adaptor; 1048 1099 typedef GraphAdaptorBase<_Graph> Parent; … … 1122 1173 } 1123 1174 1124 void hide(const Node& n) const { _node_filter_map>set(n, false); } 1125 void hide(const Edge& e) const { _edge_filter_map>set(e, false); } 1126 1127 void unHide(const Node& n) const { _node_filter_map>set(n, true); } 1128 void unHide(const Edge& e) const { _edge_filter_map>set(e, true); } 1129 1130 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 1131 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 1175 void status(const Node& n, bool v) const { _node_filter_map>set(n, v); } 1176 void status(const Edge& e, bool v) const { _edge_filter_map>set(e, v); } 1177 1178 bool status(const Node& n) const { return (*_node_filter_map)[n]; } 1179 bool status(const Edge& e) const { return (*_edge_filter_map)[e]; } 1132 1180 1133 1181 typedef False NodeNumTag; 1182 typedef False ArcNumTag; 1134 1183 typedef False EdgeNumTag; 1135 1184 1136 typedef Find EdgeTagIndicator<Graph> FindEdgeTag;1185 typedef FindArcTagIndicator<Graph> FindArcTag; 1137 1186 Arc findArc(const Node& u, const Node& v, 1138 const Arc& prev = INVALID) {1187 const Arc& prev = INVALID) const { 1139 1188 Arc arc = Parent::findArc(u, v, prev); 1140 1189 while (arc != INVALID && !(*_edge_filter_map)[arc]) { … … 1143 1192 return arc; 1144 1193 } 1194 1195 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 1145 1196 Edge findEdge(const Node& u, const Node& v, 1146 const Edge& prev = INVALID) {1197 const Edge& prev = INVALID) const { 1147 1198 Edge edge = Parent::findEdge(u, v, prev); 1148 1199 while (edge != INVALID && !(*_edge_filter_map)[edge]) { … … 1232 1283 /// \ingroup graph_adaptors 1233 1284 /// 1234 /// \brief A graph adaptor for hiding nodes and edges in an 1235 /// undirected graph. 1236 /// 1237 /// SubGraph hides nodes and edges in a graph. A bool node map and a 1238 /// bool edge map must be specified, which define the filters for 1239 /// nodes and edges. Just the nodes and edges with true value are 1240 /// shown in the subgraph. The SubGraph is conform to the \ref 1241 /// concepts::Graph "Graph concept". If the \c _checked parameter is 1242 /// true, then the edges incident to filtered nodes are also 1243 /// filtered out. 1244 /// 1245 /// \tparam _Graph It must be conform to the \ref 1246 /// concepts::Graph "Graph concept". The type can be specified 1247 /// to const. 1248 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1249 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph. 1250 /// \tparam _checked If the parameter is false then the edge filtering 1251 /// is not checked with respect to node filter. Otherwise, each edge 1252 /// is automatically filtered, which is incident to a filtered node. 1285 /// \brief Adaptor class for hiding nodes and edges in an undirected 1286 /// graph. 1287 /// 1288 /// SubGraph can be used for hiding nodes and edges in a graph. 1289 /// A \c bool node map and a \c bool edge map must be specified, which 1290 /// define the filters for nodes and edges. 1291 /// Only the nodes and edges with \c true filter value are 1292 /// shown in the subgraph. The edges that are incident to hidden 1293 /// nodes are also filtered out. 1294 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. 1295 /// 1296 /// The adapted graph can also be modified through this adaptor 1297 /// by adding or removing nodes or edges, unless the \c GR template 1298 /// parameter is set to be \c const. 1299 /// 1300 /// \tparam GR The type of the adapted graph. 1301 /// It must conform to the \ref concepts::Graph "Graph" concept. 1302 /// It can also be specified to be \c const. 1303 /// \tparam NF The type of the node filter map. 1304 /// It must be a \c bool (or convertible) node map of the 1305 /// adapted graph. The default type is 1306 /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>". 1307 /// \tparam EF The type of the edge filter map. 1308 /// It must be a \c bool (or convertible) edge map of the 1309 /// adapted graph. The default type is 1310 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". 1311 /// 1312 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the 1313 /// adapted graph are convertible to each other. 1253 1314 /// 1254 1315 /// \see FilterNodes 1255 1316 /// \see FilterEdges 1256 template<typename _Graph, typename NodeFilterMap, 1257 typename EdgeFilterMap, bool _checked = true> 1258 class SubGraph 1259 : public GraphAdaptorExtender< 1260 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > { 1261 public: 1262 typedef _Graph Graph; 1263 typedef GraphAdaptorExtender< 1264 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 1317 #ifdef DOXYGEN 1318 template<typename GR, typename NF, typename EF> 1319 class SubGraph { 1320 #else 1321 template<typename GR, 1322 typename NF = typename GR::template NodeMap<bool>, 1323 typename EF = typename GR::template EdgeMap<bool> > 1324 class SubGraph : 1325 public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > { 1326 #endif 1327 public: 1328 /// The type of the adapted graph. 1329 typedef GR Graph; 1330 /// The type of the node filter map. 1331 typedef NF NodeFilterMap; 1332 /// The type of the edge filter map. 1333 typedef EF EdgeFilterMap; 1334 1335 typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> > 1336 Parent; 1265 1337 1266 1338 typedef typename Parent::Node Node; … … 1273 1345 /// \brief Constructor 1274 1346 /// 1275 /// Creates a subgraph for the given graph with given node and1276 /// edge map filters.1277 SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,1347 /// Creates a subgraph for the given graph with the given node 1348 /// and edge filter maps. 1349 SubGraph(Graph& graph, NodeFilterMap& node_filter_map, 1278 1350 EdgeFilterMap& edge_filter_map) { 1279 setGraph( _graph);1351 setGraph(graph); 1280 1352 setNodeFilterMap(node_filter_map); 1281 1353 setEdgeFilterMap(edge_filter_map); 1282 1354 } 1283 1355 1284 /// \brief Hides the node of the graph 1285 /// 1286 /// This function hides \c n in the graph, i.e. the iteration 1287 /// jumps over it. This is done by simply setting the value of \c n 1288 /// to be false in the corresponding nodemap. 1289 void hide(const Node& n) const { Parent::hide(n); } 1290 1291 /// \brief Hides the edge of the graph 1292 /// 1293 /// This function hides \c e in the graph, i.e. the iteration 1294 /// jumps over it. This is done by simply setting the value of \c e 1295 /// to be false in the corresponding edgemap. 1296 void hide(const Edge& e) const { Parent::hide(e); } 1297 1298 /// \brief Unhides the node of the graph 1299 /// 1300 /// The value of \c n is set to be true in the nodemap which stores 1301 /// hide information. If \c n was hidden previuosly, then it is shown 1302 /// again 1303 void unHide(const Node& n) const { Parent::unHide(n); } 1304 1305 /// \brief Unhides the edge of the graph 1306 /// 1307 /// The value of \c e is set to be true in the edgemap which stores 1308 /// hide information. If \c e was hidden previuosly, then it is shown 1309 /// again 1310 void unHide(const Edge& e) const { Parent::unHide(e); } 1311 1312 /// \brief Returns true if \c n is hidden. 1313 /// 1314 /// Returns true if \c n is hidden. 1315 /// 1316 bool hidden(const Node& n) const { return Parent::hidden(n); } 1317 1318 /// \brief Returns true if \c e is hidden. 1319 /// 1320 /// Returns true if \c e is hidden. 1321 /// 1322 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1356 /// \brief Sets the status of the given node 1357 /// 1358 /// This function sets the status of the given node. 1359 /// It is done by simply setting the assigned value of \c n 1360 /// to \c v in the node filter map. 1361 void status(const Node& n, bool v) const { Parent::status(n, v); } 1362 1363 /// \brief Sets the status of the given edge 1364 /// 1365 /// This function sets the status of the given edge. 1366 /// It is done by simply setting the assigned value of \c e 1367 /// to \c v in the edge filter map. 1368 void status(const Edge& e, bool v) const { Parent::status(e, v); } 1369 1370 /// \brief Returns the status of the given node 1371 /// 1372 /// This function returns the status of the given node. 1373 /// It is \c true if the given node is enabled (i.e. not hidden). 1374 bool status(const Node& n) const { return Parent::status(n); } 1375 1376 /// \brief Returns the status of the given edge 1377 /// 1378 /// This function returns the status of the given edge. 1379 /// It is \c true if the given edge is enabled (i.e. not hidden). 1380 bool status(const Edge& e) const { return Parent::status(e); } 1381 1382 /// \brief Disables the given node 1383 /// 1384 /// This function disables the given node in the subdigraph, 1385 /// so the iteration jumps over it. 1386 /// It is the same as \ref status() "status(n, false)". 1387 void disable(const Node& n) const { Parent::status(n, false); } 1388 1389 /// \brief Disables the given edge 1390 /// 1391 /// This function disables the given edge in the subgraph, 1392 /// so the iteration jumps over it. 1393 /// It is the same as \ref status() "status(e, false)". 1394 void disable(const Edge& e) const { Parent::status(e, false); } 1395 1396 /// \brief Enables the given node 1397 /// 1398 /// This function enables the given node in the subdigraph. 1399 /// It is the same as \ref status() "status(n, true)". 1400 void enable(const Node& n) const { Parent::status(n, true); } 1401 1402 /// \brief Enables the given edge 1403 /// 1404 /// This function enables the given edge in the subgraph. 1405 /// It is the same as \ref status() "status(e, true)". 1406 void enable(const Edge& e) const { Parent::status(e, true); } 1407 1323 1408 }; 1324 1409 1325 /// \brief Just gives back a subgraph 1326 /// 1327 /// Just gives back a subgraph 1328 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1329 SubGraph<const Graph, NodeFilterMap, ArcFilterMap> 1330 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) { 1331 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm); 1410 /// \brief Returns a readonly SubGraph adaptor 1411 /// 1412 /// This function just returns a readonly \ref SubGraph adaptor. 1413 /// \ingroup graph_adaptors 1414 /// \relates SubGraph 1415 template<typename GR, typename NF, typename EF> 1416 SubGraph<const GR, NF, EF> 1417 subGraph(const GR& graph, 1418 NF& node_filter_map, EF& edge_filter_map) { 1419 return SubGraph<const GR, NF, EF> 1420 (graph, node_filter_map, edge_filter_map); 1332 1421 } 1333 1422 1334 template<typename G raph, typename NodeFilterMap, typename ArcFilterMap>1335 SubGraph<const G raph, const NodeFilterMap, ArcFilterMap>1336 subGraph(const G raph& graph,1337 const N odeFilterMap& nfm, ArcFilterMap& efm) {1338 return SubGraph<const G raph, const NodeFilterMap, ArcFilterMap>1339 (graph, n fm, efm);1423 template<typename GR, typename NF, typename EF> 1424 SubGraph<const GR, const NF, EF> 1425 subGraph(const GR& graph, 1426 const NF& node_filter_map, EF& edge_filter_map) { 1427 return SubGraph<const GR, const NF, EF> 1428 (graph, node_filter_map, edge_filter_map); 1340 1429 } 1341 1430 1342 template<typename G raph, typename NodeFilterMap, typename ArcFilterMap>1343 SubGraph<const G raph, NodeFilterMap, const ArcFilterMap>1344 subGraph(const G raph& graph,1345 N odeFilterMap& nfm, const ArcFilterMap& efm) {1346 return SubGraph<const G raph, NodeFilterMap, const ArcFilterMap>1347 (graph, n fm, efm);1431 template<typename GR, typename NF, typename EF> 1432 SubGraph<const GR, NF, const EF> 1433 subGraph(const GR& graph, 1434 NF& node_filter_map, const EF& edge_filter_map) { 1435 return SubGraph<const GR, NF, const EF> 1436 (graph, node_filter_map, edge_filter_map); 1348 1437 } 1349 1438 1350 template<typename G raph, typename NodeFilterMap, typename ArcFilterMap>1351 SubGraph<const G raph, const NodeFilterMap, const ArcFilterMap>1352 subGraph(const G raph& graph,1353 const N odeFilterMap& nfm, const ArcFilterMap& efm) {1354 return SubGraph<const G raph, const NodeFilterMap, const ArcFilterMap>1355 (graph, n fm, efm);1439 template<typename GR, typename NF, typename EF> 1440 SubGraph<const GR, const NF, const EF> 1441 subGraph(const GR& graph, 1442 const NF& node_filter_map, const EF& edge_filter_map) { 1443 return SubGraph<const GR, const NF, const EF> 1444 (graph, node_filter_map, edge_filter_map); 1356 1445 } 1357 1446 1447 1358 1448 /// \ingroup graph_adaptors 1359 1449 /// 1360 /// \brief An adaptor for hiding nodes from a digraph or a graph. 1361 /// 1362 /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool 1363 /// node map must be specified, which defines the filters for 1364 /// nodes. Just the unfiltered nodes and the arcs or edges incident 1365 /// to unfiltered nodes are shown in the subdigraph or subgraph. The 1366 /// FilterNodes is conform to the \ref concepts::Digraph 1367 /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending 1368 /// on the \c _Digraph template parameter. If the \c _checked 1369 /// parameter is true, then the arc or edges incident to filtered nodes 1370 /// are also filtered out. 1371 /// 1372 /// \tparam _Digraph It must be conform to the \ref 1373 /// concepts::Digraph "Digraph concept" or \ref concepts::Graph 1374 /// "Graph concept". The type can be specified to be const. 1375 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1376 /// \tparam _checked If the parameter is false then the arc or edge 1377 /// filtering is not checked with respect to node filter. In this 1378 /// case just isolated nodes can be filtered out from the 1379 /// graph. 1450 /// \brief Adaptor class for hiding nodes in a digraph or a graph. 1451 /// 1452 /// FilterNodes adaptor can be used for hiding nodes in a digraph or a 1453 /// graph. A \c bool node map must be specified, which defines the filter 1454 /// for the nodes. Only the nodes with \c true filter value and the 1455 /// arcs/edges incident to nodes both with \c true filter value are shown 1456 /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph 1457 /// "Digraph" concept or the \ref concepts::Graph "Graph" concept 1458 /// depending on the \c GR template parameter. 1459 /// 1460 /// The adapted (di)graph can also be modified through this adaptor 1461 /// by adding or removing nodes or arcs/edges, unless the \c GR template 1462 /// parameter is set to be \c const. 1463 /// 1464 /// \tparam GR The type of the adapted digraph or graph. 1465 /// It must conform to the \ref concepts::Digraph "Digraph" concept 1466 /// or the \ref concepts::Graph "Graph" concept. 1467 /// It can also be specified to be \c const. 1468 /// \tparam NF The type of the node filter map. 1469 /// It must be a \c bool (or convertible) node map of the 1470 /// adapted (di)graph. The default type is 1471 /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>". 1472 /// 1473 /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the 1474 /// adapted (di)graph are convertible to each other. 1380 1475 #ifdef DOXYGEN 1381 template<typename _Digraph, 1382 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1383 bool _checked = true> 1476 template<typename GR, typename NF> 1477 class FilterNodes { 1384 1478 #else 1385 template<typename _Digraph, 1386 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1387 bool _checked = true, 1479 template<typename GR, 1480 typename NF = typename GR::template NodeMap<bool>, 1388 1481 typename Enable = void> 1482 class FilterNodes : 1483 public DigraphAdaptorExtender< 1484 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > { 1389 1485 #endif 1390 class FilterNodes 1391 : public SubDigraph<_Digraph, _NodeFilterMap, 1392 ConstMap<typename _Digraph::Arc, bool>, _checked> { 1393 public: 1394 1395 typedef _Digraph Digraph; 1396 typedef _NodeFilterMap NodeFilterMap; 1397 1398 typedef SubDigraph<Digraph, NodeFilterMap, 1399 ConstMap<typename Digraph::Arc, bool>, _checked> 1400 Parent; 1486 public: 1487 1488 typedef GR Digraph; 1489 typedef NF NodeFilterMap; 1490 1491 typedef DigraphAdaptorExtender< 1492 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > 1493 Parent; 1401 1494 1402 1495 typedef typename Parent::Node Node; … … 1413 1506 /// \brief Constructor 1414 1507 /// 1415 /// Creates a n adaptor for the given digraph or graph with1508 /// Creates a subgraph for the given digraph or graph with the 1416 1509 /// given node filter map. 1417 FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) : 1418 Parent(), const_true_map(true) { 1419 Parent::setDigraph(_digraph); 1510 FilterNodes(GR& graph, NodeFilterMap& node_filter) : 1511 Parent(), const_true_map(true) 1512 { 1513 Parent::setDigraph(graph); 1420 1514 Parent::setNodeFilterMap(node_filter); 1421 1515 Parent::setArcFilterMap(const_true_map); 1422 1516 } 1423 1517 1424 /// \brief Hides the node of the graph 1425 /// 1426 /// This function hides \c n in the digraph or graph, i.e. the iteration 1427 /// jumps over it. This is done by simply setting the value of \c n 1428 /// to be false in the corresponding node map. 1429 void hide(const Node& n) const { Parent::hide(n); } 1430 1431 /// \brief Unhides the node of the graph 1432 /// 1433 /// The value of \c n is set to be true in the nodemap which stores 1434 /// hide information. If \c n was hidden previuosly, then it is shown 1435 /// again 1436 void unHide(const Node& n) const { Parent::unHide(n); } 1437 1438 /// \brief Returns true if \c n is hidden. 1439 /// 1440 /// Returns true if \c n is hidden. 1441 /// 1442 bool hidden(const Node& n) const { return Parent::hidden(n); } 1518 /// \brief Sets the status of the given node 1519 /// 1520 /// This function sets the status of the given node. 1521 /// It is done by simply setting the assigned value of \c n 1522 /// to \c v in the node filter map. 1523 void status(const Node& n, bool v) const { Parent::status(n, v); } 1524 1525 /// \brief Returns the status of the given node 1526 /// 1527 /// This function returns the status of the given node. 1528 /// It is \c true if the given node is enabled (i.e. not hidden). 1529 bool status(const Node& n) const { return Parent::status(n); } 1530 1531 /// \brief Disables the given node 1532 /// 1533 /// This function disables the given node, so the iteration 1534 /// jumps over it. 1535 /// It is the same as \ref status() "status(n, false)". 1536 void disable(const Node& n) const { Parent::status(n, false); } 1537 1538 /// \brief Enables the given node 1539 /// 1540 /// This function enables the given node. 1541 /// It is the same as \ref status() "status(n, true)". 1542 void enable(const Node& n) const { Parent::status(n, true); } 1443 1543 1444 1544 }; 1445 1545 1446 template<typename _Graph, typename _NodeFilterMap, bool _checked> 1447 class FilterNodes<_Graph, _NodeFilterMap, _checked, 1448 typename enable_if<UndirectedTagIndicator<_Graph> >::type> 1449 : public SubGraph<_Graph, _NodeFilterMap, 1450 ConstMap<typename _Graph::Edge, bool>, _checked> { 1451 public: 1452 typedef _Graph Graph; 1453 typedef _NodeFilterMap NodeFilterMap; 1454 typedef SubGraph<Graph, NodeFilterMap, 1455 ConstMap<typename Graph::Edge, bool> > Parent; 1546 template<typename GR, typename NF> 1547 class FilterNodes<GR, NF, 1548 typename enable_if<UndirectedTagIndicator<GR> >::type> : 1549 public GraphAdaptorExtender< 1550 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > { 1551 1552 public: 1553 typedef GR Graph; 1554 typedef NF NodeFilterMap; 1555 typedef GraphAdaptorExtender< 1556 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > 1557 Parent; 1456 1558 1457 1559 typedef typename Parent::Node Node; … … 1472 1574 } 1473 1575 1474 void hide(const Node& n) const { Parent::hide(n); } 1475 void unHide(const Node& n) const { Parent::unHide(n); } 1476 bool hidden(const Node& n) const { return Parent::hidden(n); } 1576 void status(const Node& n, bool v) const { Parent::status(n, v); } 1577 bool status(const Node& n) const { return Parent::status(n); } 1578 void disable(const Node& n) const { Parent::status(n, false); } 1579 void enable(const Node& n) const { Parent::status(n, true); } 1477 1580 1478 1581 }; 1479 1582 1480 1583 1481 /// \brief Just gives back a FilterNodes adaptor 1482 /// 1483 /// Just gives back a FilterNodes adaptor 1484 template<typename Digraph, typename NodeFilterMap> 1485 FilterNodes<const Digraph, NodeFilterMap> 1486 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) { 1487 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm); 1584 /// \brief Returns a readonly FilterNodes adaptor 1585 /// 1586 /// This function just returns a readonly \ref FilterNodes adaptor. 1587 /// \ingroup graph_adaptors 1588 /// \relates FilterNodes 1589 template<typename GR, typename NF> 1590 FilterNodes<const GR, NF> 1591 filterNodes(const GR& graph, NF& node_filter_map) { 1592 return FilterNodes<const GR, NF>(graph, node_filter_map); 1488 1593 } 1489 1594 1490 template<typename Digraph, typename NodeFilterMap>1491 FilterNodes<const Digraph, const NodeFilterMap>1492 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {1493 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);1595 template<typename GR, typename NF> 1596 FilterNodes<const GR, const NF> 1597 filterNodes(const GR& graph, const NF& node_filter_map) { 1598 return FilterNodes<const GR, const NF>(graph, node_filter_map); 1494 1599 } 1495 1600 1496 1601 /// \ingroup graph_adaptors 1497 1602 /// 1498 /// \brief An adaptor for hiding arcs from a digraph. 1499 /// 1500 /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must 1501 /// be specified, which defines the filters for arcs. Just the 1502 /// unfiltered arcs are shown in the subdigraph. The FilterArcs is 1503 /// conform to the \ref concepts::Digraph "Digraph concept". 1504 /// 1505 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 1506 /// "Digraph concept". The type can be specified to be const. 1507 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted 1508 /// graph. 1509 template<typename _Digraph, typename _ArcFilterMap> 1603 /// \brief Adaptor class for hiding arcs in a digraph. 1604 /// 1605 /// FilterArcs adaptor can be used for hiding arcs in a digraph. 1606 /// A \c bool arc map must be specified, which defines the filter for 1607 /// the arcs. Only the arcs with \c true filter value are shown in the 1608 /// subdigraph. This adaptor conforms to the \ref concepts::Digraph 1609 /// "Digraph" concept. 1610 /// 1611 /// The adapted digraph can also be modified through this adaptor 1612 /// by adding or removing nodes or arcs, unless the \c GR template 1613 /// parameter is set to be \c const. 1614 /// 1615 /// \tparam GR The type of the adapted digraph. 1616 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 1617 /// It can also be specified to be \c const. 1618 /// \tparam AF The type of the arc filter map. 1619 /// It must be a \c bool (or convertible) arc map of the 1620 /// adapted digraph. The default type is 1621 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>". 1622 /// 1623 /// \note The \c Node and \c Arc types of this adaptor and the adapted 1624 /// digraph are convertible to each other. 1625 #ifdef DOXYGEN 1626 template<typename GR, 1627 typename AF> 1628 class FilterArcs { 1629 #else 1630 template<typename GR, 1631 typename AF = typename GR::template ArcMap<bool> > 1510 1632 class FilterArcs : 1511 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, 1512 _ArcFilterMap, false> { 1513 public: 1514 typedef _Digraph Digraph; 1515 typedef _ArcFilterMap ArcFilterMap; 1516 1517 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>, 1518 ArcFilterMap, false> Parent; 1633 public DigraphAdaptorExtender< 1634 SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > { 1635 #endif 1636 public: 1637 /// The type of the adapted digraph. 1638 typedef GR Digraph; 1639 /// The type of the arc filter map. 1640 typedef AF ArcFilterMap; 1641 1642 typedef DigraphAdaptorExtender< 1643 SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > 1644 Parent; 1519 1645 1520 1646 typedef typename Parent::Arc Arc; … … 1531 1657 /// \brief Constructor 1532 1658 /// 1533 /// Creates a FilterArcs adaptor for the given graph with1534 /// given arc map filter.1659 /// Creates a subdigraph for the given digraph with the given arc 1660 /// filter map. 1535 1661 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) 1536 1662 : Parent(), const_true_map(true) { … … 1540 1666 } 1541 1667 1542 /// \brief Hides the arc of the graph 1543 /// 1544 /// This function hides \c a in the graph, i.e. the iteration 1545 /// jumps over it. This is done by simply setting the value of \c a 1546 /// to be false in the corresponding arc map. 1547 void hide(const Arc& a) const { Parent::hide(a); } 1548 1549 /// \brief Unhides the arc of the graph 1550 /// 1551 /// The value of \c a is set to be true in the arcmap which stores 1552 /// hide information. If \c a was hidden previuosly, then it is shown 1553 /// again 1554 void unHide(const Arc& a) const { Parent::unHide(a); } 1555 1556 /// \brief Returns true if \c a is hidden. 1557 /// 1558 /// Returns true if \c a is hidden. 1559 /// 1560 bool hidden(const Arc& a) const { return Parent::hidden(a); } 1668 /// \brief Sets the status of the given arc 1669 /// 1670 /// This function sets the status of the given arc. 1671 /// It is done by simply setting the assigned value of \c a 1672 /// to \c v in the arc filter map. 1673 void status(const Arc& a, bool v) const { Parent::status(a, v); } 1674 1675 /// \brief Returns the status of the given arc 1676 /// 1677 /// This function returns the status of the given arc. 1678 /// It is \c true if the given arc is enabled (i.e. not hidden). 1679 bool status(const Arc& a) const { return Parent::status(a); } 1680 1681 /// \brief Disables the given arc 1682 /// 1683 /// This function disables the given arc in the subdigraph, 1684 /// so the iteration jumps over it. 1685 /// It is the same as \ref status() "status(a, false)". 1686 void disable(const Arc& a) const { Parent::status(a, false); } 1687 1688 /// \brief Enables the given arc 1689 /// 1690 /// This function enables the given arc in the subdigraph. 1691 /// It is the same as \ref status() "status(a, true)". 1692 void enable(const Arc& a) const { Parent::status(a, true); } 1561 1693 1562 1694 }; 1563 1695 1564 /// \brief Just gives back an FilterArcs adaptor 1565 /// 1566 /// Just gives back an FilterArcs adaptor 1567 template<typename Digraph, typename ArcFilterMap> 1568 FilterArcs<const Digraph, ArcFilterMap> 1569 filterArcs(const Digraph& digraph, ArcFilterMap& afm) { 1570 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm); 1696 /// \brief Returns a readonly FilterArcs adaptor 1697 /// 1698 /// This function just returns a readonly \ref FilterArcs adaptor. 1699 /// \ingroup graph_adaptors 1700 /// \relates FilterArcs 1701 template<typename GR, typename AF> 1702 FilterArcs<const GR, AF> 1703 filterArcs(const GR& digraph, AF& arc_filter_map) { 1704 return FilterArcs<const GR, AF>(digraph, arc_filter_map); 1571 1705 } 1572 1706 1573 template<typename Digraph, typename ArcFilterMap>1574 FilterArcs<const Digraph, const ArcFilterMap>1575 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {1576 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);1707 template<typename GR, typename AF> 1708 FilterArcs<const GR, const AF> 1709 filterArcs(const GR& digraph, const AF& arc_filter_map) { 1710 return FilterArcs<const GR, const AF>(digraph, arc_filter_map); 1577 1711 } 1578 1712 1579 1713 /// \ingroup graph_adaptors 1580 1714 /// 1581 /// \brief An adaptor for hiding edges from a graph. 1582 /// 1583 /// FilterEdges adaptor hides edges in a digraph. A bool edge map must 1584 /// be specified, which defines the filters for edges. Just the 1585 /// unfiltered edges are shown in the subdigraph. The FilterEdges is 1586 /// conform to the \ref concepts::Graph "Graph concept". 1587 /// 1588 /// \tparam _Graph It must be conform to the \ref concepts::Graph 1589 /// "Graph concept". The type can be specified to be const. 1590 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted 1591 /// graph. 1592 template<typename _Graph, typename _EdgeFilterMap> 1715 /// \brief Adaptor class for hiding edges in a graph. 1716 /// 1717 /// FilterEdges adaptor can be used for hiding edges in a graph. 1718 /// A \c bool edge map must be specified, which defines the filter for 1719 /// the edges. Only the edges with \c true filter value are shown in the 1720 /// subgraph. This adaptor conforms to the \ref concepts::Graph 1721 /// "Graph" concept. 1722 /// 1723 /// The adapted graph can also be modified through this adaptor 1724 /// by adding or removing nodes or edges, unless the \c GR template 1725 /// parameter is set to be \c const. 1726 /// 1727 /// \tparam GR The type of the adapted graph. 1728 /// It must conform to the \ref concepts::Graph "Graph" concept. 1729 /// It can also be specified to be \c const. 1730 /// \tparam EF The type of the edge filter map. 1731 /// It must be a \c bool (or convertible) edge map of the 1732 /// adapted graph. The default type is 1733 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". 1734 /// 1735 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the 1736 /// adapted graph are convertible to each other. 1737 #ifdef DOXYGEN 1738 template<typename GR, 1739 typename EF> 1740 class FilterEdges { 1741 #else 1742 template<typename GR, 1743 typename EF = typename GR::template EdgeMap<bool> > 1593 1744 class FilterEdges : 1594 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, 1595 _EdgeFilterMap, false> { 1596 public: 1597 typedef _Graph Graph; 1598 typedef _EdgeFilterMap EdgeFilterMap; 1599 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>, 1600 EdgeFilterMap, false> Parent; 1745 public GraphAdaptorExtender< 1746 SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > { 1747 #endif 1748 public: 1749 /// The type of the adapted graph. 1750 typedef GR Graph; 1751 /// The type of the edge filter map. 1752 typedef EF EdgeFilterMap; 1753 1754 typedef GraphAdaptorExtender< 1755 SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > 1756 Parent; 1757 1601 1758 typedef typename Parent::Edge Edge; 1759 1602 1760 protected: 1603 1761 ConstMap<typename Graph::Node, bool> const_true_map; … … 1611 1769 /// \brief Constructor 1612 1770 /// 1613 /// Creates a FilterEdges adaptor for the given graph with1614 /// given edge map filters.1615 FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :1771 /// Creates a subgraph for the given graph with the given edge 1772 /// filter map. 1773 FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) : 1616 1774 Parent(), const_true_map(true) { 1617 Parent::setGraph( _graph);1775 Parent::setGraph(graph); 1618 1776 Parent::setNodeFilterMap(const_true_map); 1619 1777 Parent::setEdgeFilterMap(edge_filter_map); 1620 1778 } 1621 1779 1622 /// \brief Hides the edge of the graph 1623 /// 1624 /// This function hides \c e in the graph, i.e. the iteration 1625 /// jumps over it. This is done by simply setting the value of \c e 1626 /// to be false in the corresponding edgemap. 1627 void hide(const Edge& e) const { Parent::hide(e); } 1628 1629 /// \brief Unhides the edge of the graph 1630 /// 1631 /// The value of \c e is set to be true in the edgemap which stores 1632 /// hide information. If \c e was hidden previuosly, then it is shown 1633 /// again 1634 void unHide(const Edge& e) const { Parent::unHide(e); } 1635 1636 /// \brief Returns true if \c e is hidden. 1637 /// 1638 /// Returns true if \c e is hidden. 1639 /// 1640 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1780 /// \brief Sets the status of the given edge 1781 /// 1782 /// This function sets the status of the given edge. 1783 /// It is done by simply setting the assigned value of \c e 1784 /// to \c v in the edge filter map. 1785 void status(const Edge& e, bool v) const { Parent::status(e, v); } 1786 1787 /// \brief Returns the status of the given edge 1788 /// 1789 /// This function returns the status of the given edge. 1790 /// It is \c true if the given edge is enabled (i.e. not hidden). 1791 bool status(const Edge& e) const { return Parent::status(e); } 1792 1793 /// \brief Disables the given edge 1794 /// 1795 /// This function disables the given edge in the subgraph, 1796 /// so the iteration jumps over it. 1797 /// It is the same as \ref status() "status(e, false)". 1798 void disable(const Edge& e) const { Parent::status(e, false); } 1799 1800 /// \brief Enables the given edge 1801 /// 1802 /// This function enables the given edge in the subgraph. 1803 /// It is the same as \ref status() "status(e, true)". 1804 void enable(const Edge& e) const { Parent::status(e, true); } 1641 1805 1642 1806 }; 1643 1807 1644 /// \brief Just gives back a FilterEdges adaptor 1645 /// 1646 /// Just gives back a FilterEdges adaptor 1647 template<typename Graph, typename EdgeFilterMap> 1648 FilterEdges<const Graph, EdgeFilterMap> 1649 filterEdges(const Graph& graph, EdgeFilterMap& efm) { 1650 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm); 1808 /// \brief Returns a readonly FilterEdges adaptor 1809 /// 1810 /// This function just returns a readonly \ref FilterEdges adaptor. 1811 /// \ingroup graph_adaptors 1812 /// \relates FilterEdges 1813 template<typename GR, typename EF> 1814 FilterEdges<const GR, EF> 1815 filterEdges(const GR& graph, EF& edge_filter_map) { 1816 return FilterEdges<const GR, EF>(graph, edge_filter_map); 1651 1817 } 1652 1818 1653 template<typename G raph, typename EdgeFilterMap>1654 FilterEdges<const G raph, const EdgeFilterMap>1655 filterEdges(const G raph& graph, const EdgeFilterMap& efm) {1656 return FilterEdges<const G raph, const EdgeFilterMap>(graph, efm);1819 template<typename GR, typename EF> 1820 FilterEdges<const GR, const EF> 1821 filterEdges(const GR& graph, const EF& edge_filter_map) { 1822 return FilterEdges<const GR, const EF>(graph, edge_filter_map); 1657 1823 } 1824 1658 1825 1659 1826 template <typename _Digraph> … … 1695 1862 } 1696 1863 }; 1697 1698 1699 1864 1700 1865 void first(Node& n) const { … … 1846 2011 1847 2012 typedef NodeNumTagIndicator<Digraph> NodeNumTag; 1848 int nodeNum() const { return 2 * _digraph>arcNum(); } 1849 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 2013 int nodeNum() const { return _digraph>nodeNum(); } 2014 2015 typedef ArcNumTagIndicator<Digraph> ArcNumTag; 1850 2016 int arcNum() const { return 2 * _digraph>arcNum(); } 2017 2018 typedef ArcNumTag EdgeNumTag; 1851 2019 int edgeNum() const { return _digraph>arcNum(); } 1852 2020 1853 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;2021 typedef FindArcTagIndicator<Digraph> FindArcTag; 1854 2022 Arc findArc(Node s, Node t, Arc p = INVALID) const { 1855 2023 if (p == INVALID) { … … 1870 2038 } 1871 2039 2040 typedef FindArcTag FindEdgeTag; 1872 2041 Edge findEdge(Node s, Node t, Edge p = INVALID) const { 1873 2042 if (s != t) { … … 1877 2046 arc = _digraph>findArc(t, s); 1878 2047 if (arc != INVALID) return arc; 1879 } else if (_digraph>s (p) == s) {2048 } else if (_digraph>source(p) == s) { 1880 2049 Edge arc = _digraph>findArc(s, t, p); 1881 2050 if (arc != INVALID) return arc; … … 1906 2075 typedef _Value Value; 1907 2076 typedef Arc Key; 2077 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue; 2078 typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue; 2079 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference; 2080 typedef typename MapTraits<MapImpl>::ReturnValue Reference; 1908 2081 1909 2082 ArcMapBase(const Adaptor& adaptor) : … … 1921 2094 } 1922 2095 1923 typename MapTraits<MapImpl>::ConstReturnValue 1924 operator[](const Arc& a) const { 2096 ConstReturnValue operator[](const Arc& a) const { 1925 2097 if (direction(a)) { 1926 2098 return _forward[a]; … … 1930 2102 } 1931 2103 1932 typename MapTraits<MapImpl>::ReturnValue 1933 operator[](const Arc& a) { 2104 ReturnValue operator[](const Arc& a) { 1934 2105 if (direction(a)) { 1935 2106 return _forward[a]; … … 1981 2152 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 1982 2153 1983 ArcMap(const Adaptor& adaptor)2154 explicit ArcMap(const Adaptor& adaptor) 1984 2155 : Parent(adaptor) {} 1985 2156 … … 2028 2199 NodeNotifier& notifier(Node) const { return _digraph>notifier(Node()); } 2029 2200 2201 typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier; 2202 EdgeNotifier& notifier(Edge) const { return _digraph>notifier(Edge()); } 2203 2030 2204 protected: 2031 2205 … … 2042 2216 /// \ingroup graph_adaptors 2043 2217 /// 2044 /// \brief Undirect the graph 2045 /// 2046 /// This adaptor makes an undirected graph from a directed 2047 /// graph. All arcs of the underlying digraph will be showed in the 2048 /// adaptor as an edge. The Orienter adaptor is conform to the \ref 2049 /// concepts::Graph "Graph concept". 2050 /// 2051 /// \tparam _Digraph It must be conform to the \ref 2052 /// concepts::Digraph "Digraph concept". The type can be specified 2053 /// to const. 2054 template<typename _Digraph> 2055 class Undirector 2056 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > { 2057 public: 2058 typedef _Digraph Digraph; 2059 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent; 2218 /// \brief Adaptor class for viewing a digraph as an undirected graph. 2219 /// 2220 /// Undirector adaptor can be used for viewing a digraph as an undirected 2221 /// graph. All arcs of the underlying digraph are showed in the 2222 /// adaptor as an edge (and also as a pair of arcs, of course). 2223 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. 2224 /// 2225 /// The adapted digraph can also be modified through this adaptor 2226 /// by adding or removing nodes or edges, unless the \c GR template 2227 /// parameter is set to be \c const. 2228 /// 2229 /// \tparam GR The type of the adapted digraph. 2230 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2231 /// It can also be specified to be \c const. 2232 /// 2233 /// \note The \c Node type of this adaptor and the adapted digraph are 2234 /// convertible to each other, moreover the \c Edge type of the adaptor 2235 /// and the \c Arc type of the adapted digraph are also convertible to 2236 /// each other. 2237 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type 2238 /// of the adapted digraph.) 2239 template<typename GR> 2240 #ifdef DOXYGEN 2241 class Undirector { 2242 #else 2243 class Undirector : 2244 public GraphAdaptorExtender<UndirectorBase<GR> > { 2245 #endif 2246 public: 2247 /// The type of the adapted digraph. 2248 typedef GR Digraph; 2249 typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent; 2060 2250 protected: 2061 2251 Undirector() { } … … 2064 2254 /// \brief Constructor 2065 2255 /// 2066 /// Creates a undirected graph from the given digraph2067 Undirector( _Digraph& digraph) {2256 /// Creates an undirected graph from the given digraph. 2257 Undirector(Digraph& digraph) { 2068 2258 setDigraph(digraph); 2069 2259 } 2070 2260 2071 /// \brief ArcMap combined from two original ArcMap 2072 /// 2073 /// This class adapts two original digraph ArcMap to 2074 /// get an arc map on the undirected graph. 2075 template <typename _ForwardMap, typename _BackwardMap> 2261 /// \brief Arc map combined from two original arc maps 2262 /// 2263 /// This map adaptor class adapts two arc maps of the underlying 2264 /// digraph to get an arc map of the undirected graph. 2265 /// Its value type is inherited from the first arc map type 2266 /// (\c %ForwardMap). 2267 template <typename ForwardMap, typename BackwardMap> 2076 2268 class CombinedArcMap { 2077 2269 public: 2078 2270 2079 typedef _ForwardMap ForwardMap; 2080 typedef _BackwardMap BackwardMap; 2271 /// The key type of the map 2272 typedef typename Parent::Arc Key; 2273 /// The value type of the map 2274 typedef typename ForwardMap::Value Value; 2081 2275 2082 2276 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; 2083 2277 2084 typedef typename ForwardMap::ValueValue;2085 typedef typename Parent::Arc Key;2086 2087 /// \brief Constructor2088 /// 2278 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue; 2279 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue; 2280 typedef typename MapTraits<ForwardMap>::ReturnValue Reference; 2281 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference; 2282 2089 2283 /// Constructor 2090 2284 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 2091 2285 : _forward(&forward), _backward(&backward) {} 2092 2286 2093 2094 /// \brief Sets the value associated with a key. 2095 /// 2096 /// Sets the value associated with a key. 2287 /// Sets the value associated with the given key. 2097 2288 void set(const Key& e, const Value& a) { 2098 2289 if (Parent::direction(e)) { … … 2103 2294 } 2104 2295 2105 /// \brief Returns the value associated with a key. 2106 /// 2107 /// Returns the value associated with a key. 2108 typename MapTraits<ForwardMap>::ConstReturnValue 2109 operator[](const Key& e) const { 2296 /// Returns the value associated with the given key. 2297 ConstReturnValue operator[](const Key& e) const { 2110 2298 if (Parent::direction(e)) { 2111 2299 return (*_forward)[e]; … … 2115 2303 } 2116 2304 2117 /// \brief Returns the value associated with a key. 2118 /// 2119 /// Returns the value associated with a key. 2120 typename MapTraits<ForwardMap>::ReturnValue 2121 operator[](const Key& e) { 2305 /// Returns a reference to the value associated with the given key. 2306 ReturnValue operator[](const Key& e) { 2122 2307 if (Parent::direction(e)) { 2123 2308 return (*_forward)[e]; … … 2134 2319 }; 2135 2320 2136 /// \brief Just gives backa combined arc map2137 /// 2138 /// Just gives back a combined arc map2321 /// \brief Returns a combined arc map 2322 /// 2323 /// This function just returns a combined arc map. 2139 2324 template <typename ForwardMap, typename BackwardMap> 2140 2325 static CombinedArcMap<ForwardMap, BackwardMap> … … 2166 2351 }; 2167 2352 2168 /// \brief Just gives back an undirected view of the given digraph 2169 /// 2170 /// Just gives back an undirected view of the given digraph 2171 template<typename Digraph> 2172 Undirector<const Digraph> 2173 undirector(const Digraph& digraph) { 2174 return Undirector<const Digraph>(digraph); 2353 /// \brief Returns a readonly Undirector adaptor 2354 /// 2355 /// This function just returns a readonly \ref Undirector adaptor. 2356 /// \ingroup graph_adaptors 2357 /// \relates Undirector 2358 template<typename GR> 2359 Undirector<const GR> undirector(const GR& digraph) { 2360 return Undirector<const GR>(digraph); 2175 2361 } 2362 2176 2363 2177 2364 template <typename _Graph, typename _DirectionMap> … … 2192 2379 void first(Arc& i) const { _graph>first(i); } 2193 2380 void firstIn(Arc& i, const Node& n) const { 2194 bool d ;2381 bool d = true; 2195 2382 _graph>firstInc(i, d, n); 2196 2383 while (i != INVALID && d == (*_direction)[i]) _graph>nextInc(i, d); 2197 2384 } 2198 2385 void firstOut(Arc& i, const Node& n ) const { 2199 bool d ;2386 bool d = true; 2200 2387 _graph>firstInc(i, d, n); 2201 2388 while (i != INVALID && d != (*_direction)[i]) _graph>nextInc(i, d); … … 2225 2412 int nodeNum() const { return _graph>nodeNum(); } 2226 2413 2227 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;2414 typedef EdgeNumTagIndicator<Graph> ArcNumTag; 2228 2415 int arcNum() const { return _graph>edgeNum(); } 2229 2416 2230 typedef FindEdgeTagIndicator<Graph> Find EdgeTag;2417 typedef FindEdgeTagIndicator<Graph> FindArcTag; 2231 2418 Arc findArc(const Node& u, const Node& v, 2232 const Arc& prev = INVALID) { 2233 Arc arc = prev; 2234 bool d = arc == INVALID ? true : (*_direction)[arc]; 2235 if (d) { 2419 const Arc& prev = INVALID) const { 2420 Arc arc = _graph>findEdge(u, v, prev); 2421 while (arc != INVALID && source(arc) != u) { 2236 2422 arc = _graph>findEdge(u, v, arc); 2237 while (arc != INVALID && !(*_direction)[arc]) {2238 _graph>findEdge(u, v, arc);2239 }2240 if (arc != INVALID) return arc;2241 }2242 _graph>findEdge(v, u, arc);2243 while (arc != INVALID && (*_direction)[arc]) {2244 _graph>findEdge(u, v, arc);2245 2423 } 2246 2424 return arc; … … 2252 2430 2253 2431 Arc addArc(const Node& u, const Node& v) { 2254 Arc arc = _graph>add Arc(u, v);2255 _direction>set(arc, _graph> source(arc) == u);2432 Arc arc = _graph>addEdge(u, v); 2433 _direction>set(arc, _graph>u(arc) == u); 2256 2434 return arc; 2257 2435 } … … 2344 2522 /// \ingroup graph_adaptors 2345 2523 /// 2346 /// \brief Orients the edges of the graph to get a digraph 2347 /// 2348 /// This adaptor orients each edge in the undirected graph. The 2349 /// direction of the arcs stored in an edge node map. The arcs can 2350 /// be easily reverted by the \c reverseArc() member function in the 2351 /// adaptor. The Orienter adaptor is conform to the \ref 2352 /// concepts::Digraph "Digraph concept". 2353 /// 2354 /// \tparam _Graph It must be conform to the \ref concepts::Graph 2355 /// "Graph concept". The type can be specified to be const. 2356 /// \tparam _DirectionMap A bool valued edge map of the the adapted 2357 /// graph. 2358 /// 2359 /// \sa orienter 2360 template<typename _Graph, 2361 typename DirectionMap = typename _Graph::template EdgeMap<bool> > 2524 /// \brief Adaptor class for orienting the edges of a graph to get a digraph 2525 /// 2526 /// Orienter adaptor can be used for orienting the edges of a graph to 2527 /// get a digraph. A \c bool edge map of the underlying graph must be 2528 /// specified, which define the direction of the arcs in the adaptor. 2529 /// The arcs can be easily reversed by the \c reverseArc() member function 2530 /// of the adaptor. 2531 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2532 /// 2533 /// The adapted graph can also be modified through this adaptor 2534 /// by adding or removing nodes or arcs, unless the \c GR template 2535 /// parameter is set to be \c const. 2536 /// 2537 /// \tparam GR The type of the adapted graph. 2538 /// It must conform to the \ref concepts::Graph "Graph" concept. 2539 /// It can also be specified to be \c const. 2540 /// \tparam DM The type of the direction map. 2541 /// It must be a \c bool (or convertible) edge map of the 2542 /// adapted graph. The default type is 2543 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". 2544 /// 2545 /// \note The \c Node type of this adaptor and the adapted graph are 2546 /// convertible to each other, moreover the \c Arc type of the adaptor 2547 /// and the \c Edge type of the adapted graph are also convertible to 2548 /// each other. 2549 #ifdef DOXYGEN 2550 template<typename GR, 2551 typename DM> 2552 class Orienter { 2553 #else 2554 template<typename GR, 2555 typename DM = typename GR::template EdgeMap<bool> > 2362 2556 class Orienter : 2363 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > { 2364 public: 2365 typedef _Graph Graph; 2366 typedef DigraphAdaptorExtender< 2367 OrienterBase<_Graph, DirectionMap> > Parent; 2557 public DigraphAdaptorExtender<OrienterBase<GR, DM> > { 2558 #endif 2559 public: 2560 2561 /// The type of the adapted graph. 2562 typedef GR Graph; 2563 /// The type of the direction edge map. 2564 typedef DM DirectionMap; 2565 2566 typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent; 2368 2567 typedef typename Parent::Arc Arc; 2369 2568 protected: … … 2371 2570 public: 2372 2571 2373 /// \brief Constructor of the adaptor2374 /// 2375 /// Constructor of the adaptor 2572 /// \brief Constructor 2573 /// 2574 /// Constructor of the adaptor. 2376 2575 Orienter(Graph& graph, DirectionMap& direction) { 2377 2576 setGraph(graph); … … 2379 2578 } 2380 2579 2381 /// \brief Reverse arc 2382 /// 2383 /// It reverse the given arc. It simply negate the direction in the map. 2580 /// \brief Reverses the given arc 2581 /// 2582 /// This function reverses the given arc. 2583 /// It is done by simply negate the assigned value of \c a 2584 /// in the direction map. 2384 2585 void reverseArc(const Arc& a) { 2385 2586 Parent::reverseArc(a); … … 2387 2588 }; 2388 2589 2389 /// \brief Just gives back a Orienter 2390 /// 2391 /// Just gives back a Orienter 2392 template<typename Graph, typename DirectionMap> 2393 Orienter<const Graph, DirectionMap> 2394 orienter(const Graph& graph, DirectionMap& dm) { 2395 return Orienter<const Graph, DirectionMap>(graph, dm); 2590 /// \brief Returns a readonly Orienter adaptor 2591 /// 2592 /// This function just returns a readonly \ref Orienter adaptor. 2593 /// \ingroup graph_adaptors 2594 /// \relates Orienter 2595 template<typename GR, typename DM> 2596 Orienter<const GR, DM> 2597 orienter(const GR& graph, DM& direction_map) { 2598 return Orienter<const GR, DM>(graph, direction_map); 2396 2599 } 2397 2600 2398 template<typename G raph, typename DirectionMap>2399 Orienter<const G raph, const DirectionMap>2400 orienter(const G raph& graph, const DirectionMap& dm) {2401 return Orienter<const G raph, const DirectionMap>(graph, dm);2601 template<typename GR, typename DM> 2602 Orienter<const GR, const DM> 2603 orienter(const GR& graph, const DM& direction_map) { 2604 return Orienter<const GR, const DM>(graph, direction_map); 2402 2605 } 2403 2606 2404 2607 namespace _adaptor_bits { 2405 2608 2406 template<typename _Digraph,2407 typename _CapacityMap = typename _Digraph::template ArcMap<int>,2408 typename _FlowMap = _CapacityMap,2409 typename _Tolerance = Tolerance<typename _CapacityMap::Value>>2609 template<typename Digraph, 2610 typename CapacityMap, 2611 typename FlowMap, 2612 typename Tolerance> 2410 2613 class ResForwardFilter { 2411 2614 public: 2412 2413 typedef _Digraph Digraph;2414 typedef _CapacityMap CapacityMap;2415 typedef _FlowMap FlowMap;2416 typedef _Tolerance Tolerance;2417 2615 2418 2616 typedef typename Digraph::Arc Key; … … 2435 2633 }; 2436 2634 2437 template<typename _Digraph,2438 typename _CapacityMap = typename _Digraph::template ArcMap<int>,2439 typename _FlowMap = _CapacityMap,2440 typename _Tolerance = Tolerance<typename _CapacityMap::Value>>2635 template<typename Digraph, 2636 typename CapacityMap, 2637 typename FlowMap, 2638 typename Tolerance> 2441 2639 class ResBackwardFilter { 2442 2640 public: 2443 2444 typedef _Digraph Digraph;2445 typedef _CapacityMap CapacityMap;2446 typedef _FlowMap FlowMap;2447 typedef _Tolerance Tolerance;2448 2641 2449 2642 typedef typename Digraph::Arc Key; … … 2471 2664 /// \ingroup graph_adaptors 2472 2665 /// 2473 /// \brief A n adaptor for composing the residualgraph for directed2666 /// \brief Adaptor class for composing the residual digraph for directed 2474 2667 /// flow and circulation problems. 2475 2668 /// 2476 /// An adaptor for composing the residual graph for directed flow and 2477 /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph 2478 /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$, 2479 /// be functions on the arcset. 2480 /// 2481 /// Then Residual implements the digraph structure with 2482 /// nodeset \f$ V \f$ and arcset \f$ A_{forward}\cup A_{backward} \f$, 2483 /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 2484 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so 2485 /// called residual graph. When we take the union 2486 /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted, 2487 /// i.e. if an arc is in both \f$ A_{forward} \f$ and 2488 /// \f$ A_{backward} \f$, then in the adaptor it appears in both 2489 /// orientation. 2490 /// 2491 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 2492 /// "Digraph concept". The type is implicitly const. 2493 /// \tparam _CapacityMap An arc map of some numeric type, it defines 2494 /// the capacities in the flow problem. The map is implicitly const. 2495 /// \tparam _FlowMap An arc map of some numeric type, it defines 2496 /// the capacities in the flow problem. 2497 /// \tparam _Tolerance Handler for inexact computation. 2498 template<typename _Digraph, 2499 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2500 typename _FlowMap = _CapacityMap, 2501 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2669 /// Residual can be used for composing the \e residual digraph for directed 2670 /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph 2671 /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be 2672 /// functions on the arcs. 2673 /// This adaptor implements a digraph structure with node set \f$ V \f$ 2674 /// and arc set \f$ A_{forward}\cup A_{backward} \f$, 2675 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and 2676 /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so 2677 /// called residual digraph. 2678 /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken, 2679 /// multiplicities are counted, i.e. the adaptor has exactly 2680 /// \f$ A_{forward} + A_{backward}\f$ arcs (it may have parallel 2681 /// arcs). 2682 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2683 /// 2684 /// \tparam GR The type of the adapted digraph. 2685 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2686 /// It is implicitly \c const. 2687 /// \tparam CM The type of the capacity map. 2688 /// It must be an arc map of some numerical type, which defines 2689 /// the capacities in the flow problem. It is implicitly \c const. 2690 /// The default type is 2691 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 2692 /// \tparam FM The type of the flow map. 2693 /// It must be an arc map of some numerical type, which defines 2694 /// the flow values in the flow problem. The default type is \c CM. 2695 /// \tparam TL The tolerance type for handling inexact computation. 2696 /// The default tolerance type depends on the value type of the 2697 /// capacity map. 2698 /// 2699 /// \note This adaptor is implemented using Undirector and FilterArcs 2700 /// adaptors. 2701 /// 2702 /// \note The \c Node type of this adaptor and the adapted digraph are 2703 /// convertible to each other, moreover the \c Arc type of the adaptor 2704 /// is convertible to the \c Arc type of the adapted digraph. 2705 #ifdef DOXYGEN 2706 template<typename GR, typename CM, typename FM, typename TL> 2707 class Residual 2708 #else 2709 template<typename GR, 2710 typename CM = typename GR::template ArcMap<int>, 2711 typename FM = CM, 2712 typename TL = Tolerance<typename CM::Value> > 2502 2713 class Residual : 2503 2714 public FilterArcs< 2504 Undirector<const _Digraph>, 2505 typename Undirector<const _Digraph>::template CombinedArcMap< 2506 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap, 2507 _FlowMap, _Tolerance>, 2508 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap, 2509 _FlowMap, _Tolerance> > > 2715 Undirector<const GR>, 2716 typename Undirector<const GR>::template CombinedArcMap< 2717 _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>, 2718 _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > > 2719 #endif 2510 2720 { 2511 2721 public: 2512 2722 2513 typedef _Digraph Digraph; 2514 typedef _CapacityMap CapacityMap; 2515 typedef _FlowMap FlowMap; 2516 typedef _Tolerance Tolerance; 2723 /// The type of the underlying digraph. 2724 typedef GR Digraph; 2725 /// The type of the capacity map. 2726 typedef CM CapacityMap; 2727 /// The type of the flow map. 2728 typedef FM FlowMap; 2729 /// The tolerance type. 2730 typedef TL Tolerance; 2517 2731 2518 2732 typedef typename CapacityMap::Value Value; … … 2530 2744 2531 2745 typedef typename Undirected:: 2532 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;2746 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 2533 2747 2534 2748 typedef FilterArcs<Undirected, ArcFilter> Parent; … … 2544 2758 public: 2545 2759 2546 /// \brief Constructor of the residual digraph.2547 /// 2548 /// Constructor of the residual graph. The parameters are the digraph,2549 /// the flow map, the capacity mapand a tolerance object.2760 /// \brief Constructor 2761 /// 2762 /// Constructor of the residual digraph adaptor. The parameters are the 2763 /// digraph, the capacity map, the flow map, and a tolerance object. 2550 2764 Residual(const Digraph& digraph, const CapacityMap& capacity, 2551 2765 FlowMap& flow, const Tolerance& tolerance = Tolerance()) … … 2561 2775 typedef typename Parent::Arc Arc; 2562 2776 2563 /// \brief Gives back the residual capacity of thearc.2564 /// 2565 /// Gives back the residual capacity of thearc.2777 /// \brief Returns the residual capacity of the given arc. 2778 /// 2779 /// Returns the residual capacity of the given arc. 2566 2780 Value residualCapacity(const Arc& a) const { 2567 2781 if (Undirected::direction(a)) { … … 2572 2786 } 2573 2787 2574 /// \brief Augment on the given arc in the residualgraph.2575 /// 2576 /// Augment on the given arc in the residual graph. It increase2577 /// or decrease the flow on the original arc depend on the direction2578 /// of the residual arc.2788 /// \brief Augments on the given arc in the residual digraph. 2789 /// 2790 /// Augments on the given arc in the residual digraph. It increases 2791 /// or decreases the flow value on the original arc according to the 2792 /// direction of the residual arc. 2579 2793 void augment(const Arc& a, const Value& v) const { 2580 2794 if (Undirected::direction(a)) { … … 2585 2799 } 2586 2800 2587 /// \brief Returns the direction of the arc. 2588 /// 2589 /// Returns true when the arc is same oriented as the original arc. 2801 /// \brief Returns \c true if the given residual arc is a forward arc. 2802 /// 2803 /// Returns \c true if the given residual arc has the same orientation 2804 /// as the original arc, i.e. it is a so called forward arc. 2590 2805 static bool forward(const Arc& a) { 2591 2806 return Undirected::direction(a); 2592 2807 } 2593 2808 2594 /// \brief Returns the direction of the arc. 2595 /// 2596 /// Returns true when the arc is opposite oriented as the original arc. 2809 /// \brief Returns \c true if the given residual arc is a backward arc. 2810 /// 2811 /// Returns \c true if the given residual arc has the opposite orientation 2812 /// than the original arc, i.e. it is a so called backward arc. 2597 2813 static bool backward(const Arc& a) { 2598 2814 return !Undirected::direction(a); 2599 2815 } 2600 2816 2601 /// \brief Gives back the forward oriented residual arc. 2602 /// 2603 /// Gives back the forward oriented residual arc. 2817 /// \brief Returns the forward oriented residual arc. 2818 /// 2819 /// Returns the forward oriented residual arc related to the given 2820 /// arc of the underlying digraph. 2604 2821 static Arc forward(const typename Digraph::Arc& a) { 2605 2822 return Undirected::direct(a, true); 2606 2823 } 2607 2824 2608 /// \brief Gives back the backward oriented residual arc. 2609 /// 2610 /// Gives back the backward oriented residual arc. 2825 /// \brief Returns the backward oriented residual arc. 2826 /// 2827 /// Returns the backward oriented residual arc related to the given 2828 /// arc of the underlying digraph. 2611 2829 static Arc backward(const typename Digraph::Arc& a) { 2612 2830 return Undirected::direct(a, false); … … 2615 2833 /// \brief Residual capacity map. 2616 2834 /// 2617 /// In generic residual graph the residual capacity can be obtained 2618 /// as a map. 2835 /// This map adaptor class can be used for obtaining the residual 2836 /// capacities as an arc map of the residual digraph. 2837 /// Its value type is inherited from the capacity map. 2619 2838 class ResidualCapacity { 2620 2839 protected: 2621 2840 const Adaptor* _adaptor; 2622 2841 public: 2623 /// The Key type2842 /// The key type of the map 2624 2843 typedef Arc Key; 2625 /// The Value type2626 typedef typename _CapacityMap::Value Value;2844 /// The value type of the map 2845 typedef typename CapacityMap::Value Value; 2627 2846 2628 2847 /// Constructor 2629 2848 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2630 2849 2631 /// \e2850 /// Returns the value associated with the given residual arc 2632 2851 Value operator[](const Arc& a) const { 2633 2852 return _adaptor>residualCapacity(a); … … 2636 2855 }; 2637 2856 2857 /// \brief Returns a residual capacity map 2858 /// 2859 /// This function just returns a residual capacity map. 2860 ResidualCapacity residualCapacity() const { 2861 return ResidualCapacity(*this); 2862 } 2863 2638 2864 }; 2865 2866 /// \brief Returns a (readonly) Residual adaptor 2867 /// 2868 /// This function just returns a (readonly) \ref Residual adaptor. 2869 /// \ingroup graph_adaptors 2870 /// \relates Residual 2871 template<typename GR, typename CM, typename FM> 2872 Residual<GR, CM, FM> residual(const GR& digraph, 2873 const CM& capacity_map, 2874 FM& flow_map) { 2875 return Residual<GR, CM, FM> (digraph, capacity_map, flow_map); 2876 } 2877 2639 2878 2640 2879 template <typename _Digraph> … … 2885 3124 2886 3125 typedef True NodeNumTag; 2887 2888 3126 int nodeNum() const { 2889 3127 return 2 * countNodes(*_digraph); 2890 3128 } 2891 3129 2892 typedef True EdgeNumTag;3130 typedef True ArcNumTag; 2893 3131 int arcNum() const { 2894 3132 return countArcs(*_digraph) + countNodes(*_digraph); 2895 3133 } 2896 3134 2897 typedef True Find EdgeTag;3135 typedef True FindArcTag; 2898 3136 Arc findArc(const Node& u, const Node& v, 2899 3137 const Arc& prev = INVALID) const { 2900 if (inNode(u)) { 2901 if (outNode(v)) { 2902 if (static_cast<const DigraphNode&>(u) == 2903 static_cast<const DigraphNode&>(v) && prev == INVALID) { 2904 return Arc(u); 2905 } 3138 if (inNode(u) && outNode(v)) { 3139 if (static_cast<const DigraphNode&>(u) == 3140 static_cast<const DigraphNode&>(v) && prev == INVALID) { 3141 return Arc(u); 2906 3142 } 2907 } else { 2908 if (inNode(v)) { 2909 return Arc(::lemon::findArc(*_digraph, u, v, prev)); 2910 } 3143 } 3144 else if (outNode(u) && inNode(v)) { 3145 return Arc(::lemon::findArc(*_digraph, u, v, prev)); 2911 3146 } 2912 3147 return INVALID; … … 2922 3157 typedef Node Key; 2923 3158 typedef _Value Value; 3159 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag; 3160 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue; 3161 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue; 3162 typedef typename MapTraits<NodeImpl>::ReturnValue Reference; 3163 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference; 2924 3164 2925 3165 NodeMapBase(const Adaptor& adaptor) … … 2934 3174 } 2935 3175 2936 typename MapTraits<NodeImpl>::ReturnValue 2937 operator[](const Node& key) { 3176 ReturnValue operator[](const Node& key) { 2938 3177 if (Adaptor::inNode(key)) { return _in_map[key]; } 2939 3178 else { return _out_map[key]; } 2940 3179 } 2941 3180 2942 typename MapTraits<NodeImpl>::ConstReturnValue 2943 operator[](const Node& key) const { 3181 ConstReturnValue operator[](const Node& key) const { 2944 3182 if (Adaptor::inNode(key)) { return _in_map[key]; } 2945 3183 else { return _out_map[key]; } … … 2958 3196 typedef Arc Key; 2959 3197 typedef _Value Value; 3198 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag; 3199 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue; 3200 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue; 3201 typedef typename MapTraits<ArcImpl>::ReturnValue Reference; 3202 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference; 2960 3203 2961 3204 ArcMapBase(const Adaptor& adaptor) … … 2973 3216 } 2974 3217 2975 typename MapTraits<ArcImpl>::ReturnValue 2976 operator[](const Arc& key) { 3218 ReturnValue operator[](const Arc& key) { 2977 3219 if (Adaptor::origArc(key)) { 2978 3220 return _arc_map[key._item.first()]; … … 2982 3224 } 2983 3225 2984 typename MapTraits<ArcImpl>::ConstReturnValue 2985 operator[](const Arc& key) const { 3226 ConstReturnValue operator[](const Arc& key) const { 2986 3227 if (Adaptor::origArc(key)) { 2987 3228 return _arc_map[key._item.first()]; … … 3064 3305 /// \ingroup graph_adaptors 3065 3306 /// 3066 /// \brief Split the nodes of a directed graph 3067 /// 3068 /// The SplitNodes adaptor splits each node into an innode and an 3069 /// outnode. Formaly, the adaptor replaces each \f$ u \f$ node in 3070 /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node 3071 /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the 3072 /// original digraph the new target of the arc will be \f$ u_{in} \f$ 3073 /// and similarly the source of the original \f$ (u, v) \f$ arc 3074 /// will be \f$ u_{out} \f$. The adaptor will add for each node in 3075 /// the original digraph an additional arc which connects 3076 /// \f$ (u_{in}, u_{out}) \f$. 3077 /// 3078 /// The aim of this class is to run algorithm with node costs if the 3079 /// algorithm can use directly just arc costs. In this case we should use 3080 /// a \c SplitNodes and set the node cost of the graph to the 3081 /// bind arc in the adapted graph. 3082 /// 3083 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 3084 /// "Digraph concept". The type can be specified to be const. 3085 template <typename _Digraph> 3307 /// \brief Adaptor class for splitting the nodes of a digraph. 3308 /// 3309 /// SplitNodes adaptor can be used for splitting each node into an 3310 /// \e innode and an \e outnode in a digraph. Formaly, the adaptor 3311 /// replaces each node \f$ u \f$ in the digraph with two nodes, 3312 /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$. 3313 /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the 3314 /// new target of the arc will be \f$ u_{in} \f$ and similarly the 3315 /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$. 3316 /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$ 3317 /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph. 3318 /// 3319 /// The aim of this class is running an algorithm with respect to node 3320 /// costs or capacities if the algorithm considers only arc costs or 3321 /// capacities directly. 3322 /// In this case you can use \c SplitNodes adaptor, and set the node 3323 /// costs/capacities of the original digraph to the \e bind \e arcs 3324 /// in the adaptor. 3325 /// 3326 /// \tparam GR The type of the adapted digraph. 3327 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 3328 /// It is implicitly \c const. 3329 /// 3330 /// \note The \c Node type of this adaptor is converible to the \c Node 3331 /// type of the adapted digraph. 3332 template <typename GR> 3333 #ifdef DOXYGEN 3334 class SplitNodes { 3335 #else 3086 3336 class SplitNodes 3087 : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > { 3088 public: 3089 typedef _Digraph Digraph; 3090 typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent; 3337 : public DigraphAdaptorExtender<SplitNodesBase<const GR> > { 3338 #endif 3339 public: 3340 typedef GR Digraph; 3341 typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent; 3091 3342 3092 3343 typedef typename Digraph::Node DigraphNode; … … 3096 3347 typedef typename Parent::Arc Arc; 3097 3348 3098 /// \brief Constructor of the adaptor.3349 /// \brief Constructor 3099 3350 /// 3100 3351 /// Constructor of the adaptor. 3101 SplitNodes( Digraph& g) {3352 SplitNodes(const Digraph& g) { 3102 3353 Parent::setDigraph(g); 3103 3354 } 3104 3355 3105 /// \brief Returns true when the node isinnode.3106 /// 3107 /// Returns true when the node isinnode.3356 /// \brief Returns \c true if the given node is an innode. 3357 /// 3358 /// Returns \c true if the given node is an innode. 3108 3359 static bool inNode(const Node& n) { 3109 3360 return Parent::inNode(n); 3110 3361 } 3111 3362 3112 /// \brief Returns true when the node isoutnode.3113 /// 3114 /// Returns true when the node isoutnode.3363 /// \brief Returns \c true if the given node is an outnode. 3364 /// 3365 /// Returns \c true if the given node is an outnode. 3115 3366 static bool outNode(const Node& n) { 3116 3367 return Parent::outNode(n); 3117 3368 } 3118 3369 3119 /// \brief Returns true when the arc is arc in the original digraph. 3120 /// 3121 /// Returns true when the arc is arc in the original digraph. 3370 /// \brief Returns \c true if the given arc is an original arc. 3371 /// 3372 /// Returns \c true if the given arc is one of the arcs in the 3373 /// original digraph. 3122 3374 static bool origArc(const Arc& a) { 3123 3375 return Parent::origArc(a); 3124 3376 } 3125 3377 3126 /// \brief Returns true when the arc binds an innode and an outnode. 3127 /// 3128 /// Returns true when the arc binds an innode and an outnode. 3378 /// \brief Returns \c true if the given arc is a bind arc. 3379 /// 3380 /// Returns \c true if the given arc is a bind arc, i.e. it connects 3381 /// an innode and an outnode. 3129 3382 static bool bindArc(const Arc& a) { 3130 3383 return Parent::bindArc(a); 3131 3384 } 3132 3385 3133 /// \brief Gives back the innode created from the \cnode.3134 /// 3135 /// Gives back the innode created from the \cnode.3386 /// \brief Returns the innode created from the given original node. 3387 /// 3388 /// Returns the innode created from the given original node. 3136 3389 static Node inNode(const DigraphNode& n) { 3137 3390 return Parent::inNode(n); 3138 3391 } 3139 3392 3140 /// \brief Gives back the outnode created from the \cnode.3141 /// 3142 /// Gives back the outnode created from the \cnode.3393 /// \brief Returns the outnode created from the given original node. 3394 /// 3395 /// Returns the outnode created from the given original node. 3143 3396 static Node outNode(const DigraphNode& n) { 3144 3397 return Parent::outNode(n); 3145 3398 } 3146 3399 3147 /// \brief Gives back the arc binds the two part of the node. 3148 /// 3149 /// Gives back the arc binds the two part of the node. 3400 /// \brief Returns the bind arc that corresponds to the given 3401 /// original node. 3402 /// 3403 /// Returns the bind arc in the adaptor that corresponds to the given 3404 /// original node, i.e. the arc connecting the innode and outnode 3405 /// of \c n. 3150 3406 static Arc arc(const DigraphNode& n) { 3151 3407 return Parent::arc(n); 3152 3408 } 3153 3409 3154 /// \brief Gives back the arc of the original arc. 3155 /// 3156 /// Gives back the arc of the original arc. 3410 /// \brief Returns the arc that corresponds to the given original arc. 3411 /// 3412 /// Returns the arc in the adaptor that corresponds to the given 3413 /// original arc. 3157 3414 static Arc arc(const DigraphArc& a) { 3158 3415 return Parent::arc(a); 3159 3416 } 3160 3417 3161 /// \brief NodeMap combined from two original NodeMap 3162 /// 3163 /// This class adapt two of the original digraph NodeMap to 3164 /// get a node map on the adapted digraph. 3418 /// \brief Node map combined from two original node maps 3419 /// 3420 /// This map adaptor class adapts two node maps of the original digraph 3421 /// to get a node map of the split digraph. 3422 /// Its value type is inherited from the first node map type 3423 /// (\c InNodeMap). 3165 3424 template <typename InNodeMap, typename OutNodeMap> 3166 3425 class CombinedNodeMap { 3167 3426 public: 3168 3427 3428 /// The key type of the map 3169 3429 typedef Node Key; 3430 /// The value type of the map 3170 3431 typedef typename InNodeMap::Value Value; 3171 3432 3172 /// \brief Constructor 3173 /// 3174 /// Constructor. 3433 typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag; 3434 typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue; 3435 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue; 3436 typedef typename MapTraits<InNodeMap>::ReturnValue Reference; 3437 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference; 3438 3439 /// Constructor 3175 3440 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 3176 3441 : _in_map(in_map), _out_map(out_map) {} 3177 3442 3178 /// \brief The subscript operator. 3179 /// 3180 /// The subscript operator. 3443 /// Returns the value associated with the given key. 3444 Value operator[](const Key& key) const { 3445 if (Parent::inNode(key)) { 3446 return _in_map[key]; 3447 } else { 3448 return _out_map[key]; 3449 } 3450 } 3451 3452 /// Returns a reference to the value associated with the given key. 3181 3453 Value& operator[](const Key& key) { 3182 3454 if (Parent::inNode(key)) { … … 3187 3459 } 3188 3460 3189 /// \brief The const subscript operator. 3190 /// 3191 /// The const subscript operator. 3192 Value operator[](const Key& key) const { 3193 if (Parent::inNode(key)) { 3194 return _in_map[key]; 3195 } else { 3196 return _out_map[key]; 3197 } 3198 } 3199 3200 /// \brief The setter function of the map. 3201 /// 3202 /// The setter function of the map. 3461 /// Sets the value associated with the given key. 3203 3462 void set(const Key& key, const Value& value) { 3204 3463 if (Parent::inNode(key)) { … … 3217 3476 3218 3477 3219 /// \brief Just gives backa combined node map3220 /// 3221 /// Just gives back a combined node map3478 /// \brief Returns a combined node map 3479 /// 3480 /// This function just returns a combined node map. 3222 3481 template <typename InNodeMap, typename OutNodeMap> 3223 3482 static CombinedNodeMap<InNodeMap, OutNodeMap> … … 3245 3504 } 3246 3505 3247 /// \brief ArcMap combined from an original ArcMap and a NodeMap 3248 /// 3249 /// This class adapt an original ArcMap and a NodeMap to get an 3250 /// arc map on the adapted digraph 3251 template <typename DigraphArcMap, typename DigraphNodeMap> 3506 /// \brief Arc map combined from an arc map and a node map of the 3507 /// original digraph. 3508 /// 3509 /// This map adaptor class adapts an arc map and a node map of the 3510 /// original digraph to get an arc map of the split digraph. 3511 /// Its value type is inherited from the original arc map type 3512 /// (\c ArcMap). 3513 template <typename ArcMap, typename NodeMap> 3252 3514 class CombinedArcMap { 3253 3515 public: 3254 3516 3517 /// The key type of the map 3255 3518 typedef Arc Key; 3256 typedef typename DigraphArcMap::Value Value; 3257 3258 /// \brief Constructor 3259 /// 3260 /// Constructor. 3261 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 3519 /// The value type of the map 3520 typedef typename ArcMap::Value Value; 3521 3522 typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag; 3523 typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue; 3524 typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue; 3525 typedef typename MapTraits<ArcMap>::ReturnValue Reference; 3526 typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference; 3527 3528 /// Constructor 3529 CombinedArcMap(ArcMap& arc_map, NodeMap& node_map) 3262 3530 : _arc_map(arc_map), _node_map(node_map) {} 3263 3531 3264 /// \brief The subscript operator. 3265 /// 3266 /// The subscript operator. 3532 /// Returns the value associated with the given key. 3533 Value operator[](const Key& arc) const { 3534 if (Parent::origArc(arc)) { 3535 return _arc_map[arc]; 3536 } else { 3537 return _node_map[arc]; 3538 } 3539 } 3540 3541 /// Returns a reference to the value associated with the given key. 3542 Value& operator[](const Key& arc) { 3543 if (Parent::origArc(arc)) { 3544 return _arc_map[arc]; 3545 } else { 3546 return _node_map[arc]; 3547 } 3548 } 3549 3550 /// Sets the value associated with the given key. 3267 3551 void set(const Arc& arc, const Value& val) { 3268 3552 if (Parent::origArc(arc)) { … … 3273 3557 } 3274 3558 3275 /// \brief The const subscript operator.3276 ///3277 /// The const subscript operator.3278 Value operator[](const Key& arc) const {3279 if (Parent::origArc(arc)) {3280 return _arc_map[arc];3281 } else {3282 return _node_map[arc];3283 }3284 }3285 3286 /// \brief The const subscript operator.3287 ///3288 /// The const subscript operator.3289 Value& operator[](const Key& arc) {3290 if (Parent::origArc(arc)) {3291 return _arc_map[arc];3292 } else {3293 return _node_map[arc];3294 }3295 }3296 3297 3559 private: 3298 DigraphArcMap& _arc_map;3299 DigraphNodeMap& _node_map;3560 ArcMap& _arc_map; 3561 NodeMap& _node_map; 3300 3562 }; 3301 3563 3302 /// \brief Just gives back a combined arc map 3303 /// 3304 /// Just gives back a combined arc map 3305 template <typename DigraphArcMap, typename DigraphNodeMap> 3306 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 3307 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 3308 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map); 3309 } 3310 3311 template <typename DigraphArcMap, typename DigraphNodeMap> 3312 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 3313 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 3314 return CombinedArcMap<const DigraphArcMap, 3315 DigraphNodeMap>(arc_map, node_map); 3316 } 3317 3318 template <typename DigraphArcMap, typename DigraphNodeMap> 3319 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 3320 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) { 3321 return CombinedArcMap<DigraphArcMap, 3322 const DigraphNodeMap>(arc_map, node_map); 3323 } 3324 3325 template <typename DigraphArcMap, typename DigraphNodeMap> 3326 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 3327 combinedArcMap(const DigraphArcMap& arc_map, 3328 const DigraphNodeMap& node_map) { 3329 return CombinedArcMap<const DigraphArcMap, 3330 const DigraphNodeMap>(arc_map, node_map); 3564 /// \brief Returns a combined arc map 3565 /// 3566 /// This function just returns a combined arc map. 3567 template <typename ArcMap, typename NodeMap> 3568 static CombinedArcMap<ArcMap, NodeMap> 3569 combinedArcMap(ArcMap& arc_map, NodeMap& node_map) { 3570 return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map); 3571 } 3572 3573 template <typename ArcMap, typename NodeMap> 3574 static CombinedArcMap<const ArcMap, NodeMap> 3575 combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) { 3576 return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map); 3577 } 3578 3579 template <typename ArcMap, typename NodeMap> 3580 static CombinedArcMap<ArcMap, const NodeMap> 3581 combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) { 3582 return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map); 3583 } 3584 3585 template <typename ArcMap, typename NodeMap> 3586 static CombinedArcMap<const ArcMap, const NodeMap> 3587 combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) { 3588 return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map); 3331 3589 } 3332 3590 3333 3591 }; 3334 3592 3335 /// \brief Just gives back a node splitter 3336 /// 3337 /// Just gives back a node splitter 3338 template<typename Digraph> 3339 SplitNodes<Digraph> 3340 splitNodes(const Digraph& digraph) { 3341 return SplitNodes<Digraph>(digraph); 3593 /// \brief Returns a (readonly) SplitNodes adaptor 3594 /// 3595 /// This function just returns a (readonly) \ref SplitNodes adaptor. 3596 /// \ingroup graph_adaptors 3597 /// \relates SplitNodes 3598 template<typename GR> 3599 SplitNodes<GR> 3600 splitNodes(const GR& digraph) { 3601 return SplitNodes<GR>(digraph); 3342 3602 } 3343 3603 3344 3345 3604 } //namespace lemon 3346 3605 
lemon/bits/graph_adaptor_extender.h
r440 r455 174 174 }; 175 175 176 177 /// \ingroup digraphbits178 ///179 /// \brief Extender for the GraphAdaptors180 176 template <typename _Graph> 181 177 class GraphAdaptorExtender : public _Graph { 
lemon/bits/graph_adaptor_extender.h
r453 r455 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003200 85 * Copyright (C) 20032009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset
for help on using the changeset viewer.