Changeset 455:5a1e9fdcfd3a in lemon1.2 for lemon
 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
 Location:
 lemon
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

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.