lemon/adaptors.h
changeset 460 76ec7bd57026
parent 440 88ed40ad0d4f
parent 454 f599fa651202
child 464 acfb0f24d178
equal deleted inserted replaced
1:b8e2dc23063f 11:523748220451
    19 #ifndef LEMON_ADAPTORS_H
    19 #ifndef LEMON_ADAPTORS_H
    20 #define LEMON_ADAPTORS_H
    20 #define LEMON_ADAPTORS_H
    21 
    21 
    22 /// \ingroup graph_adaptors
    22 /// \ingroup graph_adaptors
    23 /// \file
    23 /// \file
    24 /// \brief Several graph adaptors
    24 /// \brief Adaptor classes for digraphs and graphs
    25 ///
    25 ///
    26 /// This file contains several useful adaptors for digraphs and graphs.
    26 /// This file contains several useful adaptors for digraphs and graphs.
    27 
    27 
    28 #include <lemon/core.h>
    28 #include <lemon/core.h>
    29 #include <lemon/maps.h>
    29 #include <lemon/maps.h>
    68     Node target(const Arc& a) const { return _digraph->target(a); }
    68     Node target(const Arc& a) const { return _digraph->target(a); }
    69 
    69 
    70     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    70     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    71     int nodeNum() const { return _digraph->nodeNum(); }
    71     int nodeNum() const { return _digraph->nodeNum(); }
    72 
    72 
    73     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
    73     typedef ArcNumTagIndicator<Digraph> ArcNumTag;
    74     int arcNum() const { return _digraph->arcNum(); }
    74     int arcNum() const { return _digraph->arcNum(); }
    75 
    75 
    76     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
    76     typedef FindArcTagIndicator<Digraph> FindArcTag;
    77     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
    77     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const {
    78       return _digraph->findArc(u, v, prev);
    78       return _digraph->findArc(u, v, prev);
    79     }
    79     }
    80 
    80 
    81     Node addNode() { return _digraph->addNode(); }
    81     Node addNode() { return _digraph->addNode(); }
    82     Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
    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); }
    84     void erase(const Node& n) { _digraph->erase(n); }
    85     void erase(const Arc& a) const { _digraph->erase(a); }
    85     void erase(const Arc& a) { _digraph->erase(a); }
    86 
    86 
    87     void clear() const { _digraph->clear(); }
    87     void clear() { _digraph->clear(); }
    88 
    88 
    89     int id(const Node& n) const { return _digraph->id(n); }
    89     int id(const Node& n) const { return _digraph->id(n); }
    90     int id(const Arc& a) const { return _digraph->id(a); }
    90     int id(const Arc& a) const { return _digraph->id(a); }
    91 
    91 
    92     Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
    92     Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
   196     Node target(const Arc& a) const { return _graph->target(a); }
   196     Node target(const Arc& a) const { return _graph->target(a); }
   197 
   197 
   198     typedef NodeNumTagIndicator<Graph> NodeNumTag;
   198     typedef NodeNumTagIndicator<Graph> NodeNumTag;
   199     int nodeNum() const { return _graph->nodeNum(); }
   199     int nodeNum() const { return _graph->nodeNum(); }
   200 
   200 
       
   201     typedef ArcNumTagIndicator<Graph> ArcNumTag;
       
   202     int arcNum() const { return _graph->arcNum(); }
       
   203 
   201     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
   204     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
   202     int arcNum() const { return _graph->arcNum(); }
       
   203     int edgeNum() const { return _graph->edgeNum(); }
   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     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   213     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   206     Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
   214     Edge findEdge(const Node& u, const Node& v,
   207       return _graph->findArc(u, v, prev);
   215                   const Edge& prev = INVALID) const {
   208     }
       
   209     Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
       
   210       return _graph->findEdge(u, v, prev);
   216       return _graph->findEdge(u, v, prev);
   211     }
   217     }
   212 
   218 
   213     Node addNode() { return _graph->addNode(); }
   219     Node addNode() { return _graph->addNode(); }
   214     Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
   220     Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
   328     Node source(const Arc& a) const { return Parent::target(a); }
   334     Node source(const Arc& a) const { return Parent::target(a); }
   329     Node target(const Arc& a) const { return Parent::source(a); }
   335     Node target(const Arc& a) const { return Parent::source(a); }
   330 
   336 
   331     Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
   337     Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
   332 
   338 
   333     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   339     typedef FindArcTagIndicator<Digraph> FindArcTag;
   334     Arc findArc(const Node& u, const Node& v,
   340     Arc findArc(const Node& u, const Node& v,
   335                 const Arc& prev = INVALID) {
   341                 const Arc& prev = INVALID) const {
   336       return Parent::findArc(v, u, prev);
   342       return Parent::findArc(v, u, prev);
   337     }
   343     }
   338 
   344 
   339   };
   345   };
   340 
   346 
   341   /// \ingroup graph_adaptors
   347   /// \ingroup graph_adaptors
   342   ///
   348   ///
   343   /// \brief A digraph adaptor which reverses the orientation of the arcs.
   349   /// \brief Adaptor class for reversing the orientation of the arcs in
   344   ///
   350   /// a digraph.
   345   /// ReverseDigraph reverses the arcs in the adapted digraph. The
   351   ///
   346   /// SubDigraph is conform to the \ref concepts::Digraph
   352   /// ReverseDigraph can be used for reversing the arcs in a digraph.
   347   /// "Digraph concept".
   353   /// It conforms to the \ref concepts::Digraph "Digraph" concept.
   348   ///
   354   ///
   349   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
   355   /// The adapted digraph can also be modified through this adaptor
   350   /// "Digraph concept". The type can be specified to be const.
   356   /// by adding or removing nodes or arcs, unless the \c GR template
   351   template<typename _Digraph>
   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   class ReverseDigraph :
   369   class ReverseDigraph :
   353     public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
   370     public DigraphAdaptorExtender<ReverseDigraphBase<GR> > {
   354   public:
   371 #endif
   355     typedef _Digraph Digraph;
   372   public:
   356     typedef DigraphAdaptorExtender<
   373     /// The type of the adapted digraph.
   357       ReverseDigraphBase<_Digraph> > Parent;
   374     typedef GR Digraph;
       
   375     typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent;
   358   protected:
   376   protected:
   359     ReverseDigraph() { }
   377     ReverseDigraph() { }
   360   public:
   378   public:
   361 
   379 
   362     /// \brief Constructor
   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     explicit ReverseDigraph(Digraph& digraph) {
   383     explicit ReverseDigraph(Digraph& digraph) {
   366       Parent::setDigraph(digraph);
   384       Parent::setDigraph(digraph);
   367     }
   385     }
   368   };
   386   };
   369 
   387 
   370   /// \brief Just gives back a reverse digraph adaptor
   388   /// \brief Returns a read-only ReverseDigraph adaptor
   371   ///
   389   ///
   372   /// Just gives back a reverse digraph adaptor
   390   /// This function just returns a read-only \ref ReverseDigraph adaptor.
   373   template<typename Digraph>
   391   /// \ingroup graph_adaptors
   374   ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
   392   /// \relates ReverseDigraph
   375     return ReverseDigraph<const Digraph>(digraph);
   393   template<typename GR>
       
   394   ReverseDigraph<const GR> reverseDigraph(const GR& digraph) {
       
   395     return ReverseDigraph<const GR>(digraph);
   376   }
   396   }
       
   397 
   377 
   398 
   378   template <typename _Digraph, typename _NodeFilterMap,
   399   template <typename _Digraph, typename _NodeFilterMap,
   379             typename _ArcFilterMap, bool _checked = true>
   400             typename _ArcFilterMap, bool _checked = true>
   380   class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
   401   class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
   381   public:
   402   public:
   455       while (i != INVALID && (!(*_arc_filter)[i]
   476       while (i != INVALID && (!(*_arc_filter)[i]
   456                               || !(*_node_filter)[Parent::target(i)]))
   477                               || !(*_node_filter)[Parent::target(i)]))
   457         Parent::nextOut(i);
   478         Parent::nextOut(i);
   458     }
   479     }
   459 
   480 
   460     void hide(const Node& n) const { _node_filter->set(n, false); }
   481     void status(const Node& n, bool v) const { _node_filter->set(n, v); }
   461     void hide(const Arc& a) const { _arc_filter->set(a, false); }
   482     void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
   462 
   483 
   463     void unHide(const Node& n) const { _node_filter->set(n, true); }
   484     bool status(const Node& n) const { return (*_node_filter)[n]; }
   464     void unHide(const Arc& a) const { _arc_filter->set(a, true); }
   485     bool status(const Arc& a) const { return (*_arc_filter)[a]; }
   465 
       
   466     bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
       
   467     bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
       
   468 
   486 
   469     typedef False NodeNumTag;
   487     typedef False NodeNumTag;
   470     typedef False EdgeNumTag;
   488     typedef False ArcNumTag;
   471 
   489 
   472     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   490     typedef FindArcTagIndicator<Digraph> FindArcTag;
   473     Arc findArc(const Node& source, const Node& target,
   491     Arc findArc(const Node& source, const Node& target,
   474                 const Arc& prev = INVALID) {
   492                 const Arc& prev = INVALID) const {
   475       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   493       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   476         return INVALID;
   494         return INVALID;
   477       }
   495       }
   478       Arc arc = Parent::findArc(source, target, prev);
   496       Arc arc = Parent::findArc(source, target, prev);
   479       while (arc != INVALID && !(*_arc_filter)[arc]) {
   497       while (arc != INVALID && !(*_arc_filter)[arc]) {
   598     void nextOut(Arc& i) const {
   616     void nextOut(Arc& i) const {
   599       Parent::nextOut(i);
   617       Parent::nextOut(i);
   600       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
   618       while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
   601     }
   619     }
   602 
   620 
   603     void hide(const Node& n) const { _node_filter->set(n, false); }
   621     void status(const Node& n, bool v) const { _node_filter->set(n, v); }
   604     void hide(const Arc& e) const { _arc_filter->set(e, false); }
   622     void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
   605 
   623 
   606     void unHide(const Node& n) const { _node_filter->set(n, true); }
   624     bool status(const Node& n) const { return (*_node_filter)[n]; }
   607     void unHide(const Arc& e) const { _arc_filter->set(e, true); }
   625     bool status(const Arc& a) const { return (*_arc_filter)[a]; }
   608 
       
   609     bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
       
   610     bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
       
   611 
   626 
   612     typedef False NodeNumTag;
   627     typedef False NodeNumTag;
   613     typedef False EdgeNumTag;
   628     typedef False ArcNumTag;
   614 
   629 
   615     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
   630     typedef FindArcTagIndicator<Digraph> FindArcTag;
   616     Arc findArc(const Node& source, const Node& target,
   631     Arc findArc(const Node& source, const Node& target,
   617                 const Arc& prev = INVALID) {
   632                 const Arc& prev = INVALID) const {
   618       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   633       if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
   619         return INVALID;
   634         return INVALID;
   620       }
   635       }
   621       Arc arc = Parent::findArc(source, target, prev);
   636       Arc arc = Parent::findArc(source, target, prev);
   622       while (arc != INVALID && !(*_arc_filter)[arc]) {
   637       while (arc != INVALID && !(*_arc_filter)[arc]) {
   677 
   692 
   678   };
   693   };
   679 
   694 
   680   /// \ingroup graph_adaptors
   695   /// \ingroup graph_adaptors
   681   ///
   696   ///
   682   /// \brief An adaptor for hiding nodes and arcs in a digraph
   697   /// \brief Adaptor class for hiding nodes and arcs in a digraph
   683   ///
   698   ///
   684   /// SubDigraph hides nodes and arcs in a digraph. A bool node map
   699   /// SubDigraph can be used for hiding nodes and arcs in a digraph.
   685   /// and a bool arc map must be specified, which define the filters
   700   /// A \c bool node map and a \c bool arc map must be specified, which
   686   /// for nodes and arcs. Just the nodes and arcs with true value are
   701   /// define the filters for nodes and arcs.
   687   /// shown in the subdigraph. The SubDigraph is conform to the \ref
   702   /// Only the nodes and arcs with \c true filter value are
   688   /// concepts::Digraph "Digraph concept". If the \c _checked parameter
   703   /// shown in the subdigraph. The arcs that are incident to hidden
   689   /// is true, then the arcs incident to filtered nodes are also
   704   /// nodes are also filtered out.
   690   /// filtered out.
   705   /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept.
   691   ///
   706   ///
   692   /// \tparam _Digraph It must be conform to the \ref
   707   /// The adapted digraph can also be modified through this adaptor
   693   /// concepts::Digraph "Digraph concept". The type can be specified
   708   /// by adding or removing nodes or arcs, unless the \c GR template
   694   /// to const.
   709   /// parameter is set to be \c const.
   695   /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
   710   ///
   696   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
   711   /// \tparam GR The type of the adapted digraph.
   697   /// \tparam _checked If the parameter is false then the arc filtering
   712   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
   698   /// is not checked with respect to node filter. Otherwise, each arc
   713   /// It can also be specified to be \c const.
   699   /// is automatically filtered, which is incident to a filtered node.
   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   /// \see FilterNodes
   726   /// \see FilterNodes
   702   /// \see FilterArcs
   727   /// \see FilterArcs
   703   template<typename _Digraph,
   728 #ifdef DOXYGEN
   704            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
   729   template<typename GR, typename NF, typename AF>
   705            typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
   730   class SubDigraph {
   706            bool _checked = true>
   731 #else
   707   class SubDigraph
   732   template<typename GR,
   708     : public DigraphAdaptorExtender<
   733            typename NF = typename GR::template NodeMap<bool>,
   709       SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
   734            typename AF = typename GR::template ArcMap<bool> >
   710   public:
   735   class SubDigraph :
   711     typedef _Digraph Digraph;
   736     public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > {
   712     typedef _NodeFilterMap NodeFilterMap;
   737 #endif
   713     typedef _ArcFilterMap ArcFilterMap;
   738   public:
   714 
   739     /// The type of the adapted digraph.
   715     typedef DigraphAdaptorExtender<
   740     typedef GR Digraph;
   716       SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
   741     /// The type of the node filter map.
   717     Parent;
   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     typedef typename Parent::Node Node;
   749     typedef typename Parent::Node Node;
   720     typedef typename Parent::Arc Arc;
   750     typedef typename Parent::Arc Arc;
   721 
   751 
   722   protected:
   752   protected:
   723     SubDigraph() { }
   753     SubDigraph() { }
   724   public:
   754   public:
   725 
   755 
   726     /// \brief Constructor
   756     /// \brief Constructor
   727     ///
   757     ///
   728     /// Creates a subdigraph for the given digraph with
   758     /// Creates a subdigraph for the given digraph with the
   729     /// given node and arc map filters.
   759     /// given node and arc filter maps.
   730     SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
   760     SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
   731                ArcFilterMap& arc_filter) {
   761                ArcFilterMap& arc_filter) {
   732       setDigraph(digraph);
   762       setDigraph(digraph);
   733       setNodeFilterMap(node_filter);
   763       setNodeFilterMap(node_filter);
   734       setArcFilterMap(arc_filter);
   764       setArcFilterMap(arc_filter);
   735     }
   765     }
   736 
   766 
   737     /// \brief Hides the node of the graph
   767     /// \brief Sets the status of the given node
   738     ///
   768     ///
   739     /// This function hides \c n in the digraph, i.e. the iteration
   769     /// This function sets the status of the given node.
   740     /// jumps over it. This is done by simply setting the value of \c n
   770     /// It is done by simply setting the assigned value of \c n
   741     /// to be false in the corresponding node-map.
   771     /// to \c v in the node filter map.
   742     void hide(const Node& n) const { Parent::hide(n); }
   772     void status(const Node& n, bool v) const { Parent::status(n, v); }
   743 
   773 
   744     /// \brief Hides the arc of the graph
   774     /// \brief Sets the status of the given arc
   745     ///
   775     ///
   746     /// This function hides \c a in the digraph, i.e. the iteration
   776     /// This function sets the status of the given arc.
   747     /// jumps over it. This is done by simply setting the value of \c a
   777     /// It is done by simply setting the assigned value of \c a
   748     /// to be false in the corresponding arc-map.
   778     /// to \c v in the arc filter map.
   749     void hide(const Arc& a) const { Parent::hide(a); }
   779     void status(const Arc& a, bool v) const { Parent::status(a, v); }
   750 
   780 
   751     /// \brief Unhides the node of the graph
   781     /// \brief Returns the status of the given node
   752     ///
   782     ///
   753     /// The value of \c n is set to be true in the node-map which stores
   783     /// This function returns the status of the given node.
   754     /// hide information. If \c n was hidden previuosly, then it is shown
   784     /// It is \c true if the given node is enabled (i.e. not hidden).
   755     /// again
   785     bool status(const Node& n) const { return Parent::status(n); }
   756     void unHide(const Node& n) const { Parent::unHide(n); }
   786 
   757 
   787     /// \brief Returns the status of the given arc
   758     /// \brief Unhides the arc of the graph
   788     ///
   759     ///
   789     /// This function returns the status of the given arc.
   760     /// The value of \c a is set to be true in the arc-map which stores
   790     /// It is \c true if the given arc is enabled (i.e. not hidden).
   761     /// hide information. If \c a was hidden previuosly, then it is shown
   791     bool status(const Arc& a) const { return Parent::status(a); }
   762     /// again
   792 
   763     void unHide(const Arc& a) const { Parent::unHide(a); }
   793     /// \brief Disables the given node
   764 
   794     ///
   765     /// \brief Returns true if \c n is hidden.
   795     /// This function disables the given node in the subdigraph,
   766     ///
   796     /// so the iteration jumps over it.
   767     /// Returns true if \c n is hidden.
   797     /// It is the same as \ref status() "status(n, false)".
   768     ///
   798     void disable(const Node& n) const { Parent::status(n, false); }
   769     bool hidden(const Node& n) const { return Parent::hidden(n); }
   799 
   770 
   800     /// \brief Disables the given arc
   771     /// \brief Returns true if \c a is hidden.
   801     ///
   772     ///
   802     /// This function disables the given arc in the subdigraph,
   773     /// Returns true if \c a is hidden.
   803     /// so the iteration jumps over it.
   774     ///
   804     /// It is the same as \ref status() "status(a, false)".
   775     bool hidden(const Arc& a) const { return Parent::hidden(a); }
   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
   821   /// \brief Returns a read-only SubDigraph adaptor
   780   ///
   822   ///
   781   /// Just gives back a subdigraph
   823   /// This function just returns a read-only \ref SubDigraph adaptor.
   782   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   824   /// \ingroup graph_adaptors
   783   SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
   825   /// \relates SubDigraph
   784   subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
   826   template<typename GR, typename NF, typename AF>
   785     return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
   827   SubDigraph<const GR, NF, AF>
   786       (digraph, nfm, afm);
   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>
   834   template<typename GR, typename NF, typename AF>
   790   SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
   835   SubDigraph<const GR, const NF, AF>
   791   subDigraph(const Digraph& digraph,
   836   subDigraph(const GR& digraph,
   792              const NodeFilterMap& nfm, ArcFilterMap& afm) {
   837              const NF& node_filter_map, AF& arc_filter_map) {
   793     return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
   838     return SubDigraph<const GR, const NF, AF>
   794       (digraph, nfm, afm);
   839       (digraph, node_filter_map, arc_filter_map);
   795   }
   840   }
   796 
   841 
   797   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   842   template<typename GR, typename NF, typename AF>
   798   SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
   843   SubDigraph<const GR, NF, const AF>
   799   subDigraph(const Digraph& digraph,
   844   subDigraph(const GR& digraph,
   800              NodeFilterMap& nfm, const ArcFilterMap& afm) {
   845              NF& node_filter_map, const AF& arc_filter_map) {
   801     return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
   846     return SubDigraph<const GR, NF, const AF>
   802       (digraph, nfm, afm);
   847       (digraph, node_filter_map, arc_filter_map);
   803   }
   848   }
   804 
   849 
   805   template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
   850   template<typename GR, typename NF, typename AF>
   806   SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
   851   SubDigraph<const GR, const NF, const AF>
   807   subDigraph(const Digraph& digraph,
   852   subDigraph(const GR& digraph,
   808              const NodeFilterMap& nfm, const ArcFilterMap& afm) {
   853              const NF& node_filter_map, const AF& arc_filter_map) {
   809     return SubDigraph<const Digraph, const NodeFilterMap,
   854     return SubDigraph<const GR, const NF, const AF>
   810       const ArcFilterMap>(digraph, nfm, afm);
   855       (digraph, node_filter_map, arc_filter_map);
   811   }
   856   }
   812 
   857 
   813 
   858 
   814   template <typename _Graph, typename NodeFilterMap,
   859   template <typename _Graph, typename _NodeFilterMap,
   815             typename EdgeFilterMap, bool _checked = true>
   860             typename _EdgeFilterMap, bool _checked = true>
   816   class SubGraphBase : public GraphAdaptorBase<_Graph> {
   861   class SubGraphBase : public GraphAdaptorBase<_Graph> {
   817   public:
   862   public:
   818     typedef _Graph Graph;
   863     typedef _Graph Graph;
       
   864     typedef _NodeFilterMap NodeFilterMap;
       
   865     typedef _EdgeFilterMap EdgeFilterMap;
       
   866 
   819     typedef SubGraphBase Adaptor;
   867     typedef SubGraphBase Adaptor;
   820     typedef GraphAdaptorBase<_Graph> Parent;
   868     typedef GraphAdaptorBase<_Graph> Parent;
   821   protected:
   869   protected:
   822 
   870 
   823     NodeFilterMap* _node_filter_map;
   871     NodeFilterMap* _node_filter_map;
   923                             || !(*_node_filter_map)[Parent::u(i)]
   971                             || !(*_node_filter_map)[Parent::u(i)]
   924                             || !(*_node_filter_map)[Parent::v(i)]))
   972                             || !(*_node_filter_map)[Parent::v(i)]))
   925         Parent::nextInc(i, d);
   973         Parent::nextInc(i, d);
   926     }
   974     }
   927 
   975 
   928     void hide(const Node& n) const { _node_filter_map->set(n, false); }
   976     void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
   929     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
   977     void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
   930 
   978 
   931     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
   979     bool status(const Node& n) const { return (*_node_filter_map)[n]; }
   932     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
   980     bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
   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]; }
       
   936 
   981 
   937     typedef False NodeNumTag;
   982     typedef False NodeNumTag;
       
   983     typedef False ArcNumTag;
   938     typedef False EdgeNumTag;
   984     typedef False EdgeNumTag;
   939 
   985 
   940     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   986     typedef FindArcTagIndicator<Graph> FindArcTag;
   941     Arc findArc(const Node& u, const Node& v,
   987     Arc findArc(const Node& u, const Node& v,
   942                 const Arc& prev = INVALID) {
   988                 const Arc& prev = INVALID) const {
   943       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
   989       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
   944         return INVALID;
   990         return INVALID;
   945       }
   991       }
   946       Arc arc = Parent::findArc(u, v, prev);
   992       Arc arc = Parent::findArc(u, v, prev);
   947       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
   993       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
   948         arc = Parent::findArc(u, v, arc);
   994         arc = Parent::findArc(u, v, arc);
   949       }
   995       }
   950       return arc;
   996       return arc;
   951     }
   997     }
       
   998 
       
   999     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
   952     Edge findEdge(const Node& u, const Node& v,
  1000     Edge findEdge(const Node& u, const Node& v,
   953                   const Edge& prev = INVALID) {
  1001                   const Edge& prev = INVALID) const {
   954       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
  1002       if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
   955         return INVALID;
  1003         return INVALID;
   956       }
  1004       }
   957       Edge edge = Parent::findEdge(u, v, prev);
  1005       Edge edge = Parent::findEdge(u, v, prev);
   958       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
  1006       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
  1037       }
  1085       }
  1038     };
  1086     };
  1039 
  1087 
  1040   };
  1088   };
  1041 
  1089 
  1042   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
  1090   template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
  1043   class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
  1091   class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
  1044     : public GraphAdaptorBase<_Graph> {
  1092     : public GraphAdaptorBase<_Graph> {
  1045   public:
  1093   public:
  1046     typedef _Graph Graph;
  1094     typedef _Graph Graph;
       
  1095     typedef _NodeFilterMap NodeFilterMap;
       
  1096     typedef _EdgeFilterMap EdgeFilterMap;
       
  1097 
  1047     typedef SubGraphBase Adaptor;
  1098     typedef SubGraphBase Adaptor;
  1048     typedef GraphAdaptorBase<_Graph> Parent;
  1099     typedef GraphAdaptorBase<_Graph> Parent;
  1049   protected:
  1100   protected:
  1050     NodeFilterMap* _node_filter_map;
  1101     NodeFilterMap* _node_filter_map;
  1051     EdgeFilterMap* _edge_filter_map;
  1102     EdgeFilterMap* _edge_filter_map;
  1119     void nextInc(Edge& i, bool& d) const {
  1170     void nextInc(Edge& i, bool& d) const {
  1120       Parent::nextInc(i, d);
  1171       Parent::nextInc(i, d);
  1121       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
  1172       while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
  1122     }
  1173     }
  1123 
  1174 
  1124     void hide(const Node& n) const { _node_filter_map->set(n, false); }
  1175     void status(const Node& n, bool v) const { _node_filter_map->set(n, v); }
  1125     void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
  1176     void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); }
  1126 
  1177 
  1127     void unHide(const Node& n) const { _node_filter_map->set(n, true); }
  1178     bool status(const Node& n) const { return (*_node_filter_map)[n]; }
  1128     void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
  1179     bool status(const Edge& e) const { return (*_edge_filter_map)[e]; }
  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]; }
       
  1132 
  1180 
  1133     typedef False NodeNumTag;
  1181     typedef False NodeNumTag;
       
  1182     typedef False ArcNumTag;
  1134     typedef False EdgeNumTag;
  1183     typedef False EdgeNumTag;
  1135 
  1184 
  1136     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
  1185     typedef FindArcTagIndicator<Graph> FindArcTag;
  1137     Arc findArc(const Node& u, const Node& v,
  1186     Arc findArc(const Node& u, const Node& v,
  1138                 const Arc& prev = INVALID) {
  1187                 const Arc& prev = INVALID) const {
  1139       Arc arc = Parent::findArc(u, v, prev);
  1188       Arc arc = Parent::findArc(u, v, prev);
  1140       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
  1189       while (arc != INVALID && !(*_edge_filter_map)[arc]) {
  1141         arc = Parent::findArc(u, v, arc);
  1190         arc = Parent::findArc(u, v, arc);
  1142       }
  1191       }
  1143       return arc;
  1192       return arc;
  1144     }
  1193     }
       
  1194 
       
  1195     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
  1145     Edge findEdge(const Node& u, const Node& v,
  1196     Edge findEdge(const Node& u, const Node& v,
  1146                   const Edge& prev = INVALID) {
  1197                   const Edge& prev = INVALID) const {
  1147       Edge edge = Parent::findEdge(u, v, prev);
  1198       Edge edge = Parent::findEdge(u, v, prev);
  1148       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
  1199       while (edge != INVALID && !(*_edge_filter_map)[edge]) {
  1149         edge = Parent::findEdge(u, v, edge);
  1200         edge = Parent::findEdge(u, v, edge);
  1150       }
  1201       }
  1151       return edge;
  1202       return edge;
  1229 
  1280 
  1230   };
  1281   };
  1231 
  1282 
  1232   /// \ingroup graph_adaptors
  1283   /// \ingroup graph_adaptors
  1233   ///
  1284   ///
  1234   /// \brief A graph adaptor for hiding nodes and edges in an
  1285   /// \brief Adaptor class for hiding nodes and edges in an undirected
  1235   /// undirected graph.
  1286   /// graph.
  1236   ///
  1287   ///
  1237   /// SubGraph hides nodes and edges in a graph. A bool node map and a
  1288   /// SubGraph can be used for hiding nodes and edges in a graph.
  1238   /// bool edge map must be specified, which define the filters for
  1289   /// A \c bool node map and a \c bool edge map must be specified, which
  1239   /// nodes and edges. Just the nodes and edges with true value are
  1290   /// define the filters for nodes and edges.
  1240   /// shown in the subgraph. The SubGraph is conform to the \ref
  1291   /// Only the nodes and edges with \c true filter value are
  1241   /// concepts::Graph "Graph concept". If the \c _checked parameter is
  1292   /// shown in the subgraph. The edges that are incident to hidden
  1242   /// true, then the edges incident to filtered nodes are also
  1293   /// nodes are also filtered out.
  1243   /// filtered out.
  1294   /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
  1244   ///
  1295   ///
  1245   /// \tparam _Graph It must be conform to the \ref
  1296   /// The adapted graph can also be modified through this adaptor
  1246   /// concepts::Graph "Graph concept". The type can be specified
  1297   /// by adding or removing nodes or edges, unless the \c GR template
  1247   /// to const.
  1298   /// parameter is set to be \c const.
  1248   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
  1299   ///
  1249   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
  1300   /// \tparam GR The type of the adapted graph.
  1250   /// \tparam _checked If the parameter is false then the edge filtering
  1301   /// It must conform to the \ref concepts::Graph "Graph" concept.
  1251   /// is not checked with respect to node filter. Otherwise, each edge
  1302   /// It can also be specified to be \c const.
  1252   /// is automatically filtered, which is incident to a filtered node.
  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   /// \see FilterNodes
  1315   /// \see FilterNodes
  1255   /// \see FilterEdges
  1316   /// \see FilterEdges
  1256   template<typename _Graph, typename NodeFilterMap,
  1317 #ifdef DOXYGEN
  1257            typename EdgeFilterMap, bool _checked = true>
  1318   template<typename GR, typename NF, typename EF>
  1258   class SubGraph
  1319   class SubGraph {
  1259     : public GraphAdaptorExtender<
  1320 #else
  1260       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
  1321   template<typename GR,
  1261   public:
  1322            typename NF = typename GR::template NodeMap<bool>,
  1262     typedef _Graph Graph;
  1323            typename EF = typename GR::template EdgeMap<bool> >
  1263     typedef GraphAdaptorExtender<
  1324   class SubGraph :
  1264       SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
  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     typedef typename Parent::Node Node;
  1338     typedef typename Parent::Node Node;
  1267     typedef typename Parent::Edge Edge;
  1339     typedef typename Parent::Edge Edge;
  1268 
  1340 
  1269   protected:
  1341   protected:
  1270     SubGraph() { }
  1342     SubGraph() { }
  1271   public:
  1343   public:
  1272 
  1344 
  1273     /// \brief Constructor
  1345     /// \brief Constructor
  1274     ///
  1346     ///
  1275     /// Creates a subgraph for the given graph with given node and
  1347     /// Creates a subgraph for the given graph with the given node
  1276     /// edge map filters.
  1348     /// and edge filter maps.
  1277     SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
  1349     SubGraph(Graph& graph, NodeFilterMap& node_filter_map,
  1278              EdgeFilterMap& edge_filter_map) {
  1350              EdgeFilterMap& edge_filter_map) {
  1279       setGraph(_graph);
  1351       setGraph(graph);
  1280       setNodeFilterMap(node_filter_map);
  1352       setNodeFilterMap(node_filter_map);
  1281       setEdgeFilterMap(edge_filter_map);
  1353       setEdgeFilterMap(edge_filter_map);
  1282     }
  1354     }
  1283 
  1355 
  1284     /// \brief Hides the node of the graph
  1356     /// \brief Sets the status of the given node
  1285     ///
  1357     ///
  1286     /// This function hides \c n in the graph, i.e. the iteration
  1358     /// This function sets the status of the given node.
  1287     /// jumps over it. This is done by simply setting the value of \c n
  1359     /// It is done by simply setting the assigned value of \c n
  1288     /// to be false in the corresponding node-map.
  1360     /// to \c v in the node filter map.
  1289     void hide(const Node& n) const { Parent::hide(n); }
  1361     void status(const Node& n, bool v) const { Parent::status(n, v); }
  1290 
  1362 
  1291     /// \brief Hides the edge of the graph
  1363     /// \brief Sets the status of the given edge
  1292     ///
  1364     ///
  1293     /// This function hides \c e in the graph, i.e. the iteration
  1365     /// This function sets the status of the given edge.
  1294     /// jumps over it. This is done by simply setting the value of \c e
  1366     /// It is done by simply setting the assigned value of \c e
  1295     /// to be false in the corresponding edge-map.
  1367     /// to \c v in the edge filter map.
  1296     void hide(const Edge& e) const { Parent::hide(e); }
  1368     void status(const Edge& e, bool v) const { Parent::status(e, v); }
  1297 
  1369 
  1298     /// \brief Unhides the node of the graph
  1370     /// \brief Returns the status of the given node
  1299     ///
  1371     ///
  1300     /// The value of \c n is set to be true in the node-map which stores
  1372     /// This function returns the status of the given node.
  1301     /// hide information. If \c n was hidden previuosly, then it is shown
  1373     /// It is \c true if the given node is enabled (i.e. not hidden).
  1302     /// again
  1374     bool status(const Node& n) const { return Parent::status(n); }
  1303     void unHide(const Node& n) const { Parent::unHide(n); }
  1375 
  1304 
  1376     /// \brief Returns the status of the given edge
  1305     /// \brief Unhides the edge of the graph
  1377     ///
  1306     ///
  1378     /// This function returns the status of the given edge.
  1307     /// The value of \c e is set to be true in the edge-map which stores
  1379     /// It is \c true if the given edge is enabled (i.e. not hidden).
  1308     /// hide information. If \c e was hidden previuosly, then it is shown
  1380     bool status(const Edge& e) const { return Parent::status(e); }
  1309     /// again
  1381 
  1310     void unHide(const Edge& e) const { Parent::unHide(e); }
  1382     /// \brief Disables the given node
  1311 
  1383     ///
  1312     /// \brief Returns true if \c n is hidden.
  1384     /// This function disables the given node in the subdigraph,
  1313     ///
  1385     /// so the iteration jumps over it.
  1314     /// Returns true if \c n is hidden.
  1386     /// It is the same as \ref status() "status(n, false)".
  1315     ///
  1387     void disable(const Node& n) const { Parent::status(n, false); }
  1316     bool hidden(const Node& n) const { return Parent::hidden(n); }
  1388 
  1317 
  1389     /// \brief Disables the given edge
  1318     /// \brief Returns true if \c e is hidden.
  1390     ///
  1319     ///
  1391     /// This function disables the given edge in the subgraph,
  1320     /// Returns true if \c e is hidden.
  1392     /// so the iteration jumps over it.
  1321     ///
  1393     /// It is the same as \ref status() "status(e, false)".
  1322     bool hidden(const Edge& e) const { return Parent::hidden(e); }
  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
  1410   /// \brief Returns a read-only SubGraph adaptor
  1326   ///
  1411   ///
  1327   /// Just gives back a subgraph
  1412   /// This function just returns a read-only \ref SubGraph adaptor.
  1328   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
  1413   /// \ingroup graph_adaptors
  1329   SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
  1414   /// \relates SubGraph
  1330   subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
  1415   template<typename GR, typename NF, typename EF>
  1331     return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
  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 Graph, typename NodeFilterMap, typename ArcFilterMap>
  1423   template<typename GR, typename NF, typename EF>
  1335   SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
  1424   SubGraph<const GR, const NF, EF>
  1336   subGraph(const Graph& graph,
  1425   subGraph(const GR& graph,
  1337            const NodeFilterMap& nfm, ArcFilterMap& efm) {
  1426            const NF& node_filter_map, EF& edge_filter_map) {
  1338     return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
  1427     return SubGraph<const GR, const NF, EF>
  1339       (graph, nfm, efm);
  1428       (graph, node_filter_map, edge_filter_map);
  1340   }
  1429   }
  1341 
  1430 
  1342   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
  1431   template<typename GR, typename NF, typename EF>
  1343   SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
  1432   SubGraph<const GR, NF, const EF>
  1344   subGraph(const Graph& graph,
  1433   subGraph(const GR& graph,
  1345            NodeFilterMap& nfm, const ArcFilterMap& efm) {
  1434            NF& node_filter_map, const EF& edge_filter_map) {
  1346     return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
  1435     return SubGraph<const GR, NF, const EF>
  1347       (graph, nfm, efm);
  1436       (graph, node_filter_map, edge_filter_map);
  1348   }
  1437   }
  1349 
  1438 
  1350   template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
  1439   template<typename GR, typename NF, typename EF>
  1351   SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
  1440   SubGraph<const GR, const NF, const EF>
  1352   subGraph(const Graph& graph,
  1441   subGraph(const GR& graph,
  1353            const NodeFilterMap& nfm, const ArcFilterMap& efm) {
  1442            const NF& node_filter_map, const EF& edge_filter_map) {
  1354     return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
  1443     return SubGraph<const GR, const NF, const EF>
  1355       (graph, nfm, efm);
  1444       (graph, node_filter_map, edge_filter_map);
  1356   }
  1445   }
  1357 
  1446 
       
  1447 
  1358   /// \ingroup graph_adaptors
  1448   /// \ingroup graph_adaptors
  1359   ///
  1449   ///
  1360   /// \brief An adaptor for hiding nodes from a digraph or a graph.
  1450   /// \brief Adaptor class for hiding nodes in a digraph or a graph.
  1361   ///
  1451   ///
  1362   /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
  1452   /// FilterNodes adaptor can be used for hiding nodes in a digraph or a
  1363   /// node map must be specified, which defines the filters for
  1453   /// graph. A \c bool node map must be specified, which defines the filter
  1364   /// nodes. Just the unfiltered nodes and the arcs or edges incident
  1454   /// for the nodes. Only the nodes with \c true filter value and the
  1365   /// to unfiltered nodes are shown in the subdigraph or subgraph. The
  1455   /// arcs/edges incident to nodes both with \c true filter value are shown
  1366   /// FilterNodes is conform to the \ref concepts::Digraph
  1456   /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph
  1367   /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
  1457   /// "Digraph" concept or the \ref concepts::Graph "Graph" concept
  1368   /// on the \c _Digraph template parameter. If the \c _checked
  1458   /// depending on the \c GR template parameter.
  1369   /// parameter is true, then the arc or edges incident to filtered nodes
  1459   ///
  1370   /// are also filtered out.
  1460   /// The adapted (di)graph can also be modified through this adaptor
  1371   ///
  1461   /// by adding or removing nodes or arcs/edges, unless the \c GR template
  1372   /// \tparam _Digraph It must be conform to the \ref
  1462   /// parameter is set to be \c const.
  1373   /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
  1463   ///
  1374   /// "Graph concept". The type can be specified to be const.
  1464   /// \tparam GR The type of the adapted digraph or graph.
  1375   /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
  1465   /// It must conform to the \ref concepts::Digraph "Digraph" concept
  1376   /// \tparam _checked If the parameter is false then the arc or edge
  1466   /// or the \ref concepts::Graph "Graph" concept.
  1377   /// filtering is not checked with respect to node filter. In this
  1467   /// It can also be specified to be \c const.
  1378   /// case just isolated nodes can be filtered out from the
  1468   /// \tparam NF The type of the node filter map.
  1379   /// graph.
  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 #ifdef DOXYGEN
  1475 #ifdef DOXYGEN
  1381   template<typename _Digraph,
  1476   template<typename GR, typename NF>
  1382            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
  1477   class FilterNodes {
  1383            bool _checked = true>
       
  1384 #else
  1478 #else
  1385   template<typename _Digraph,
  1479   template<typename GR,
  1386            typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
  1480            typename NF = typename GR::template NodeMap<bool>,
  1387            bool _checked = true,
       
  1388            typename Enable = void>
  1481            typename Enable = void>
       
  1482   class FilterNodes :
       
  1483     public DigraphAdaptorExtender<
       
  1484       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > {
  1389 #endif
  1485 #endif
  1390   class FilterNodes
  1486   public:
  1391     : public SubDigraph<_Digraph, _NodeFilterMap,
  1487 
  1392                         ConstMap<typename _Digraph::Arc, bool>, _checked> {
  1488     typedef GR Digraph;
  1393   public:
  1489     typedef NF NodeFilterMap;
  1394 
  1490 
  1395     typedef _Digraph Digraph;
  1491     typedef DigraphAdaptorExtender<
  1396     typedef _NodeFilterMap NodeFilterMap;
  1492       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >
  1397 
  1493       Parent;
  1398     typedef SubDigraph<Digraph, NodeFilterMap,
       
  1399                        ConstMap<typename Digraph::Arc, bool>, _checked>
       
  1400     Parent;
       
  1401 
  1494 
  1402     typedef typename Parent::Node Node;
  1495     typedef typename Parent::Node Node;
  1403 
  1496 
  1404   protected:
  1497   protected:
  1405     ConstMap<typename Digraph::Arc, bool> const_true_map;
  1498     ConstMap<typename Digraph::Arc, bool> const_true_map;
  1410 
  1503 
  1411   public:
  1504   public:
  1412 
  1505 
  1413     /// \brief Constructor
  1506     /// \brief Constructor
  1414     ///
  1507     ///
  1415     /// Creates an adaptor for the given digraph or graph with
  1508     /// Creates a subgraph for the given digraph or graph with the
  1416     /// given node filter map.
  1509     /// given node filter map.
  1417     FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
  1510     FilterNodes(GR& graph, NodeFilterMap& node_filter) :
  1418       Parent(), const_true_map(true) {
  1511       Parent(), const_true_map(true)
  1419       Parent::setDigraph(_digraph);
  1512     {
       
  1513       Parent::setDigraph(graph);
  1420       Parent::setNodeFilterMap(node_filter);
  1514       Parent::setNodeFilterMap(node_filter);
  1421       Parent::setArcFilterMap(const_true_map);
  1515       Parent::setArcFilterMap(const_true_map);
  1422     }
  1516     }
  1423 
  1517 
  1424     /// \brief Hides the node of the graph
  1518     /// \brief Sets the status of the given node
  1425     ///
  1519     ///
  1426     /// This function hides \c n in the digraph or graph, i.e. the iteration
  1520     /// This function sets the status of the given node.
  1427     /// jumps over it. This is done by simply setting the value of \c n
  1521     /// It is done by simply setting the assigned value of \c n
  1428     /// to be false in the corresponding node map.
  1522     /// to \c v in the node filter map.
  1429     void hide(const Node& n) const { Parent::hide(n); }
  1523     void status(const Node& n, bool v) const { Parent::status(n, v); }
  1430 
  1524 
  1431     /// \brief Unhides the node of the graph
  1525     /// \brief Returns the status of the given node
  1432     ///
  1526     ///
  1433     /// The value of \c n is set to be true in the node-map which stores
  1527     /// This function returns the status of the given node.
  1434     /// hide information. If \c n was hidden previuosly, then it is shown
  1528     /// It is \c true if the given node is enabled (i.e. not hidden).
  1435     /// again
  1529     bool status(const Node& n) const { return Parent::status(n); }
  1436     void unHide(const Node& n) const { Parent::unHide(n); }
  1530 
  1437 
  1531     /// \brief Disables the given node
  1438     /// \brief Returns true if \c n is hidden.
  1532     ///
  1439     ///
  1533     /// This function disables the given node, so the iteration
  1440     /// Returns true if \c n is hidden.
  1534     /// jumps over it.
  1441     ///
  1535     /// It is the same as \ref status() "status(n, false)".
  1442     bool hidden(const Node& n) const { return Parent::hidden(n); }
  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>
  1546   template<typename GR, typename NF>
  1447   class FilterNodes<_Graph, _NodeFilterMap, _checked,
  1547   class FilterNodes<GR, NF,
  1448                     typename enable_if<UndirectedTagIndicator<_Graph> >::type>
  1548                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
  1449     : public SubGraph<_Graph, _NodeFilterMap,
  1549     public GraphAdaptorExtender<
  1450                       ConstMap<typename _Graph::Edge, bool>, _checked> {
  1550       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > {
  1451   public:
  1551 
  1452     typedef _Graph Graph;
  1552   public:
  1453     typedef _NodeFilterMap NodeFilterMap;
  1553     typedef GR Graph;
  1454     typedef SubGraph<Graph, NodeFilterMap,
  1554     typedef NF NodeFilterMap;
  1455                      ConstMap<typename Graph::Edge, bool> > Parent;
  1555     typedef GraphAdaptorExtender<
       
  1556       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >
       
  1557       Parent;
  1456 
  1558 
  1457     typedef typename Parent::Node Node;
  1559     typedef typename Parent::Node Node;
  1458   protected:
  1560   protected:
  1459     ConstMap<typename Graph::Edge, bool> const_true_map;
  1561     ConstMap<typename Graph::Edge, bool> const_true_map;
  1460 
  1562 
  1469       Parent::setGraph(_graph);
  1571       Parent::setGraph(_graph);
  1470       Parent::setNodeFilterMap(node_filter_map);
  1572       Parent::setNodeFilterMap(node_filter_map);
  1471       Parent::setEdgeFilterMap(const_true_map);
  1573       Parent::setEdgeFilterMap(const_true_map);
  1472     }
  1574     }
  1473 
  1575 
  1474     void hide(const Node& n) const { Parent::hide(n); }
  1576     void status(const Node& n, bool v) const { Parent::status(n, v); }
  1475     void unHide(const Node& n) const { Parent::unHide(n); }
  1577     bool status(const Node& n) const { return Parent::status(n); }
  1476     bool hidden(const Node& n) const { return Parent::hidden(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
  1584   /// \brief Returns a read-only FilterNodes adaptor
  1482   ///
  1585   ///
  1483   /// Just gives back a FilterNodes adaptor
  1586   /// This function just returns a read-only \ref FilterNodes adaptor.
  1484   template<typename Digraph, typename NodeFilterMap>
  1587   /// \ingroup graph_adaptors
  1485   FilterNodes<const Digraph, NodeFilterMap>
  1588   /// \relates FilterNodes
  1486   filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
  1589   template<typename GR, typename NF>
  1487     return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
  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>
  1595   template<typename GR, typename NF>
  1491   FilterNodes<const Digraph, const NodeFilterMap>
  1596   FilterNodes<const GR, const NF>
  1492   filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
  1597   filterNodes(const GR& graph, const NF& node_filter_map) {
  1493     return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
  1598     return FilterNodes<const GR, const NF>(graph, node_filter_map);
  1494   }
  1599   }
  1495 
  1600 
  1496   /// \ingroup graph_adaptors
  1601   /// \ingroup graph_adaptors
  1497   ///
  1602   ///
  1498   /// \brief An adaptor for hiding arcs from a digraph.
  1603   /// \brief Adaptor class for hiding arcs in a digraph.
  1499   ///
  1604   ///
  1500   /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
  1605   /// FilterArcs adaptor can be used for hiding arcs in a digraph.
  1501   /// be specified, which defines the filters for arcs. Just the
  1606   /// A \c bool arc map must be specified, which defines the filter for
  1502   /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
  1607   /// the arcs. Only the arcs with \c true filter value are shown in the
  1503   /// conform to the \ref concepts::Digraph "Digraph concept".
  1608   /// subdigraph. This adaptor conforms to the \ref concepts::Digraph
  1504   ///
  1609   /// "Digraph" concept.
  1505   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
  1610   ///
  1506   /// "Digraph concept". The type can be specified to be const.
  1611   /// The adapted digraph can also be modified through this adaptor
  1507   /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
  1612   /// by adding or removing nodes or arcs, unless the \c GR template
  1508   /// graph.
  1613   /// parameter is set to be \c const.
  1509   template<typename _Digraph, typename _ArcFilterMap>
  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   class FilterArcs :
  1632   class FilterArcs :
  1511     public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
  1633     public DigraphAdaptorExtender<
  1512                       _ArcFilterMap, false> {
  1634       SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > {
  1513   public:
  1635 #endif
  1514     typedef _Digraph Digraph;
  1636   public:
  1515     typedef _ArcFilterMap ArcFilterMap;
  1637     /// The type of the adapted digraph.
  1516 
  1638     typedef GR Digraph;
  1517     typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
  1639     /// The type of the arc filter map.
  1518                        ArcFilterMap, false> Parent;
  1640     typedef AF ArcFilterMap;
       
  1641 
       
  1642     typedef DigraphAdaptorExtender<
       
  1643       SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >
       
  1644       Parent;
  1519 
  1645 
  1520     typedef typename Parent::Arc Arc;
  1646     typedef typename Parent::Arc Arc;
  1521 
  1647 
  1522   protected:
  1648   protected:
  1523     ConstMap<typename Digraph::Node, bool> const_true_map;
  1649     ConstMap<typename Digraph::Node, bool> const_true_map;
  1528 
  1654 
  1529   public:
  1655   public:
  1530 
  1656 
  1531     /// \brief Constructor
  1657     /// \brief Constructor
  1532     ///
  1658     ///
  1533     /// Creates a FilterArcs adaptor for the given graph with
  1659     /// Creates a subdigraph for the given digraph with the given arc
  1534     /// given arc map filter.
  1660     /// filter map.
  1535     FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
  1661     FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
  1536       : Parent(), const_true_map(true) {
  1662       : Parent(), const_true_map(true) {
  1537       Parent::setDigraph(digraph);
  1663       Parent::setDigraph(digraph);
  1538       Parent::setNodeFilterMap(const_true_map);
  1664       Parent::setNodeFilterMap(const_true_map);
  1539       Parent::setArcFilterMap(arc_filter);
  1665       Parent::setArcFilterMap(arc_filter);
  1540     }
  1666     }
  1541 
  1667 
  1542     /// \brief Hides the arc of the graph
  1668     /// \brief Sets the status of the given arc
  1543     ///
  1669     ///
  1544     /// This function hides \c a in the graph, i.e. the iteration
  1670     /// This function sets the status of the given arc.
  1545     /// jumps over it. This is done by simply setting the value of \c a
  1671     /// It is done by simply setting the assigned value of \c a
  1546     /// to be false in the corresponding arc map.
  1672     /// to \c v in the arc filter map.
  1547     void hide(const Arc& a) const { Parent::hide(a); }
  1673     void status(const Arc& a, bool v) const { Parent::status(a, v); }
  1548 
  1674 
  1549     /// \brief Unhides the arc of the graph
  1675     /// \brief Returns the status of the given arc
  1550     ///
  1676     ///
  1551     /// The value of \c a is set to be true in the arc-map which stores
  1677     /// This function returns the status of the given arc.
  1552     /// hide information. If \c a was hidden previuosly, then it is shown
  1678     /// It is \c true if the given arc is enabled (i.e. not hidden).
  1553     /// again
  1679     bool status(const Arc& a) const { return Parent::status(a); }
  1554     void unHide(const Arc& a) const { Parent::unHide(a); }
  1680 
  1555 
  1681     /// \brief Disables the given arc
  1556     /// \brief Returns true if \c a is hidden.
  1682     ///
  1557     ///
  1683     /// This function disables the given arc in the subdigraph,
  1558     /// Returns true if \c a is hidden.
  1684     /// so the iteration jumps over it.
  1559     ///
  1685     /// It is the same as \ref status() "status(a, false)".
  1560     bool hidden(const Arc& a) const { return Parent::hidden(a); }
  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
  1696   /// \brief Returns a read-only FilterArcs adaptor
  1565   ///
  1697   ///
  1566   /// Just gives back an FilterArcs adaptor
  1698   /// This function just returns a read-only \ref FilterArcs adaptor.
  1567   template<typename Digraph, typename ArcFilterMap>
  1699   /// \ingroup graph_adaptors
  1568   FilterArcs<const Digraph, ArcFilterMap>
  1700   /// \relates FilterArcs
  1569   filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
  1701   template<typename GR, typename AF>
  1570     return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
  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>
  1707   template<typename GR, typename AF>
  1574   FilterArcs<const Digraph, const ArcFilterMap>
  1708   FilterArcs<const GR, const AF>
  1575   filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
  1709   filterArcs(const GR& digraph, const AF& arc_filter_map) {
  1576     return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
  1710     return FilterArcs<const GR, const AF>(digraph, arc_filter_map);
  1577   }
  1711   }
  1578 
  1712 
  1579   /// \ingroup graph_adaptors
  1713   /// \ingroup graph_adaptors
  1580   ///
  1714   ///
  1581   /// \brief An adaptor for hiding edges from a graph.
  1715   /// \brief Adaptor class for hiding edges in a graph.
  1582   ///
  1716   ///
  1583   /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
  1717   /// FilterEdges adaptor can be used for hiding edges in a graph.
  1584   /// be specified, which defines the filters for edges. Just the
  1718   /// A \c bool edge map must be specified, which defines the filter for
  1585   /// unfiltered edges are shown in the subdigraph. The FilterEdges is
  1719   /// the edges. Only the edges with \c true filter value are shown in the
  1586   /// conform to the \ref concepts::Graph "Graph concept".
  1720   /// subgraph. This adaptor conforms to the \ref concepts::Graph
  1587   ///
  1721   /// "Graph" concept.
  1588   /// \tparam _Graph It must be conform to the \ref concepts::Graph
  1722   ///
  1589   /// "Graph concept". The type can be specified to be const.
  1723   /// The adapted graph can also be modified through this adaptor
  1590   /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
  1724   /// by adding or removing nodes or edges, unless the \c GR template
  1591   /// graph.
  1725   /// parameter is set to be \c const.
  1592   template<typename _Graph, typename _EdgeFilterMap>
  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   class FilterEdges :
  1744   class FilterEdges :
  1594     public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
  1745     public GraphAdaptorExtender<
  1595                     _EdgeFilterMap, false> {
  1746       SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > {
  1596   public:
  1747 #endif
  1597     typedef _Graph Graph;
  1748   public:
  1598     typedef _EdgeFilterMap EdgeFilterMap;
  1749     /// The type of the adapted graph.
  1599     typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
  1750     typedef GR Graph;
  1600                      EdgeFilterMap, false> Parent;
  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     typedef typename Parent::Edge Edge;
  1758     typedef typename Parent::Edge Edge;
       
  1759 
  1602   protected:
  1760   protected:
  1603     ConstMap<typename Graph::Node, bool> const_true_map;
  1761     ConstMap<typename Graph::Node, bool> const_true_map;
  1604 
  1762 
  1605     FilterEdges() : const_true_map(true) {
  1763     FilterEdges() : const_true_map(true) {
  1606       Parent::setNodeFilterMap(const_true_map);
  1764       Parent::setNodeFilterMap(const_true_map);
  1608 
  1766 
  1609   public:
  1767   public:
  1610 
  1768 
  1611     /// \brief Constructor
  1769     /// \brief Constructor
  1612     ///
  1770     ///
  1613     /// Creates a FilterEdges adaptor for the given graph with
  1771     /// Creates a subgraph for the given graph with the given edge
  1614     /// given edge map filters.
  1772     /// filter map.
  1615     FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
  1773     FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) :
  1616       Parent(), const_true_map(true) {
  1774       Parent(), const_true_map(true) {
  1617       Parent::setGraph(_graph);
  1775       Parent::setGraph(graph);
  1618       Parent::setNodeFilterMap(const_true_map);
  1776       Parent::setNodeFilterMap(const_true_map);
  1619       Parent::setEdgeFilterMap(edge_filter_map);
  1777       Parent::setEdgeFilterMap(edge_filter_map);
  1620     }
  1778     }
  1621 
  1779 
  1622     /// \brief Hides the edge of the graph
  1780     /// \brief Sets the status of the given edge
  1623     ///
  1781     ///
  1624     /// This function hides \c e in the graph, i.e. the iteration
  1782     /// This function sets the status of the given edge.
  1625     /// jumps over it. This is done by simply setting the value of \c e
  1783     /// It is done by simply setting the assigned value of \c e
  1626     /// to be false in the corresponding edge-map.
  1784     /// to \c v in the edge filter map.
  1627     void hide(const Edge& e) const { Parent::hide(e); }
  1785     void status(const Edge& e, bool v) const { Parent::status(e, v); }
  1628 
  1786 
  1629     /// \brief Unhides the edge of the graph
  1787     /// \brief Returns the status of the given edge
  1630     ///
  1788     ///
  1631     /// The value of \c e is set to be true in the edge-map which stores
  1789     /// This function returns the status of the given edge.
  1632     /// hide information. If \c e was hidden previuosly, then it is shown
  1790     /// It is \c true if the given edge is enabled (i.e. not hidden).
  1633     /// again
  1791     bool status(const Edge& e) const { return Parent::status(e); }
  1634     void unHide(const Edge& e) const { Parent::unHide(e); }
  1792 
  1635 
  1793     /// \brief Disables the given edge
  1636     /// \brief Returns true if \c e is hidden.
  1794     ///
  1637     ///
  1795     /// This function disables the given edge in the subgraph,
  1638     /// Returns true if \c e is hidden.
  1796     /// so the iteration jumps over it.
  1639     ///
  1797     /// It is the same as \ref status() "status(e, false)".
  1640     bool hidden(const Edge& e) const { return Parent::hidden(e); }
  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
  1808   /// \brief Returns a read-only FilterEdges adaptor
  1645   ///
  1809   ///
  1646   /// Just gives back a FilterEdges adaptor
  1810   /// This function just returns a read-only \ref FilterEdges adaptor.
  1647   template<typename Graph, typename EdgeFilterMap>
  1811   /// \ingroup graph_adaptors
  1648   FilterEdges<const Graph, EdgeFilterMap>
  1812   /// \relates FilterEdges
  1649   filterEdges(const Graph& graph, EdgeFilterMap& efm) {
  1813   template<typename GR, typename EF>
  1650     return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
  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 Graph, typename EdgeFilterMap>
  1819   template<typename GR, typename EF>
  1654   FilterEdges<const Graph, const EdgeFilterMap>
  1820   FilterEdges<const GR, const EF>
  1655   filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
  1821   filterEdges(const GR& graph, const EF& edge_filter_map) {
  1656     return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
  1822     return FilterEdges<const GR, const EF>(graph, edge_filter_map);
  1657   }
  1823   }
       
  1824 
  1658 
  1825 
  1659   template <typename _Digraph>
  1826   template <typename _Digraph>
  1660   class UndirectorBase {
  1827   class UndirectorBase {
  1661   public:
  1828   public:
  1662     typedef _Digraph Digraph;
  1829     typedef _Digraph Digraph;
  1692         return _forward < other._forward ||
  1859         return _forward < other._forward ||
  1693           (_forward == other._forward &&
  1860           (_forward == other._forward &&
  1694            static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
  1861            static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
  1695       }
  1862       }
  1696     };
  1863     };
  1697 
       
  1698 
       
  1699 
  1864 
  1700     void first(Node& n) const {
  1865     void first(Node& n) const {
  1701       _digraph->first(n);
  1866       _digraph->first(n);
  1702     }
  1867     }
  1703 
  1868 
  1843     void erase(const Edge& i) { _digraph->erase(i); }
  2008     void erase(const Edge& i) { _digraph->erase(i); }
  1844 
  2009 
  1845     void clear() { _digraph->clear(); }
  2010     void clear() { _digraph->clear(); }
  1846 
  2011 
  1847     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
  2012     typedef NodeNumTagIndicator<Digraph> NodeNumTag;
  1848     int nodeNum() const { return 2 * _digraph->arcNum(); }
  2013     int nodeNum() const { return _digraph->nodeNum(); }
  1849     typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
  2014 
       
  2015     typedef ArcNumTagIndicator<Digraph> ArcNumTag;
  1850     int arcNum() const { return 2 * _digraph->arcNum(); }
  2016     int arcNum() const { return 2 * _digraph->arcNum(); }
       
  2017 
       
  2018     typedef ArcNumTag EdgeNumTag;
  1851     int edgeNum() const { return _digraph->arcNum(); }
  2019     int edgeNum() const { return _digraph->arcNum(); }
  1852 
  2020 
  1853     typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
  2021     typedef FindArcTagIndicator<Digraph> FindArcTag;
  1854     Arc findArc(Node s, Node t, Arc p = INVALID) const {
  2022     Arc findArc(Node s, Node t, Arc p = INVALID) const {
  1855       if (p == INVALID) {
  2023       if (p == INVALID) {
  1856         Edge arc = _digraph->findArc(s, t);
  2024         Edge arc = _digraph->findArc(s, t);
  1857         if (arc != INVALID) return direct(arc, true);
  2025         if (arc != INVALID) return direct(arc, true);
  1858         arc = _digraph->findArc(t, s);
  2026         arc = _digraph->findArc(t, s);
  1867         if (arc != INVALID) return direct(arc, false);
  2035         if (arc != INVALID) return direct(arc, false);
  1868       }
  2036       }
  1869       return INVALID;
  2037       return INVALID;
  1870     }
  2038     }
  1871 
  2039 
       
  2040     typedef FindArcTag FindEdgeTag;
  1872     Edge findEdge(Node s, Node t, Edge p = INVALID) const {
  2041     Edge findEdge(Node s, Node t, Edge p = INVALID) const {
  1873       if (s != t) {
  2042       if (s != t) {
  1874         if (p == INVALID) {
  2043         if (p == INVALID) {
  1875           Edge arc = _digraph->findArc(s, t);
  2044           Edge arc = _digraph->findArc(s, t);
  1876           if (arc != INVALID) return arc;
  2045           if (arc != INVALID) return arc;
  1877           arc = _digraph->findArc(t, s);
  2046           arc = _digraph->findArc(t, s);
  1878           if (arc != INVALID) return arc;
  2047           if (arc != INVALID) return arc;
  1879         } else if (_digraph->s(p) == s) {
  2048         } else if (_digraph->source(p) == s) {
  1880           Edge arc = _digraph->findArc(s, t, p);
  2049           Edge arc = _digraph->findArc(s, t, p);
  1881           if (arc != INVALID) return arc;
  2050           if (arc != INVALID) return arc;
  1882           arc = _digraph->findArc(t, s);
  2051           arc = _digraph->findArc(t, s);
  1883           if (arc != INVALID) return arc;
  2052           if (arc != INVALID) return arc;
  1884         } else {
  2053         } else {
  1903 
  2072 
  1904       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
  2073       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
  1905 
  2074 
  1906       typedef _Value Value;
  2075       typedef _Value Value;
  1907       typedef Arc Key;
  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       ArcMapBase(const Adaptor& adaptor) :
  2082       ArcMapBase(const Adaptor& adaptor) :
  1910         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
  2083         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
  1911 
  2084 
  1912       ArcMapBase(const Adaptor& adaptor, const Value& v)
  2085       ArcMapBase(const Adaptor& adaptor, const Value& v)
  1918         } else {
  2091         } else {
  1919           _backward.set(a, v);
  2092           _backward.set(a, v);
  1920         }
  2093         }
  1921       }
  2094       }
  1922 
  2095 
  1923       typename MapTraits<MapImpl>::ConstReturnValue
  2096       ConstReturnValue operator[](const Arc& a) const {
  1924       operator[](const Arc& a) const {
       
  1925         if (direction(a)) {
  2097         if (direction(a)) {
  1926           return _forward[a];
  2098           return _forward[a];
  1927         } else {
  2099         } else {
  1928           return _backward[a];
  2100           return _backward[a];
  1929         }
  2101         }
  1930       }
  2102       }
  1931 
  2103 
  1932       typename MapTraits<MapImpl>::ReturnValue
  2104       ReturnValue operator[](const Arc& a) {
  1933       operator[](const Arc& a) {
       
  1934         if (direction(a)) {
  2105         if (direction(a)) {
  1935           return _forward[a];
  2106           return _forward[a];
  1936         } else {
  2107         } else {
  1937           return _backward[a];
  2108           return _backward[a];
  1938         }
  2109         }
  1978     {
  2149     {
  1979     public:
  2150     public:
  1980       typedef _Value Value;
  2151       typedef _Value Value;
  1981       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  2152       typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
  1982 
  2153 
  1983       ArcMap(const Adaptor& adaptor)
  2154       explicit ArcMap(const Adaptor& adaptor)
  1984         : Parent(adaptor) {}
  2155         : Parent(adaptor) {}
  1985 
  2156 
  1986       ArcMap(const Adaptor& adaptor, const Value& value)
  2157       ArcMap(const Adaptor& adaptor, const Value& value)
  1987         : Parent(adaptor, value) {}
  2158         : Parent(adaptor, value) {}
  1988 
  2159 
  2025     };
  2196     };
  2026 
  2197 
  2027     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
  2198     typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
  2028     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
  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   protected:
  2204   protected:
  2031 
  2205 
  2032     UndirectorBase() : _digraph(0) {}
  2206     UndirectorBase() : _digraph(0) {}
  2033 
  2207 
  2034     Digraph* _digraph;
  2208     Digraph* _digraph;
  2039 
  2213 
  2040   };
  2214   };
  2041 
  2215 
  2042   /// \ingroup graph_adaptors
  2216   /// \ingroup graph_adaptors
  2043   ///
  2217   ///
  2044   /// \brief Undirect the graph
  2218   /// \brief Adaptor class for viewing a digraph as an undirected graph.
  2045   ///
  2219   ///
  2046   /// This adaptor makes an undirected graph from a directed
  2220   /// Undirector adaptor can be used for viewing a digraph as an undirected
  2047   /// graph. All arcs of the underlying digraph will be showed in the
  2221   /// graph. All arcs of the underlying digraph are showed in the
  2048   /// adaptor as an edge. The Orienter adaptor is conform to the \ref
  2222   /// adaptor as an edge (and also as a pair of arcs, of course).
  2049   /// concepts::Graph "Graph concept".
  2223   /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
  2050   ///
  2224   ///
  2051   /// \tparam _Digraph It must be conform to the \ref
  2225   /// The adapted digraph can also be modified through this adaptor
  2052   /// concepts::Digraph "Digraph concept". The type can be specified
  2226   /// by adding or removing nodes or edges, unless the \c GR template
  2053   /// to const.
  2227   /// parameter is set to be \c const.
  2054   template<typename _Digraph>
  2228   ///
  2055   class Undirector
  2229   /// \tparam GR The type of the adapted digraph.
  2056     : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
  2230   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2057   public:
  2231   /// It can also be specified to be \c const.
  2058     typedef _Digraph Digraph;
  2232   ///
  2059     typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
  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   protected:
  2250   protected:
  2061     Undirector() { }
  2251     Undirector() { }
  2062   public:
  2252   public:
  2063 
  2253 
  2064     /// \brief Constructor
  2254     /// \brief Constructor
  2065     ///
  2255     ///
  2066     /// Creates a undirected graph from the given digraph
  2256     /// Creates an undirected graph from the given digraph.
  2067     Undirector(_Digraph& digraph) {
  2257     Undirector(Digraph& digraph) {
  2068       setDigraph(digraph);
  2258       setDigraph(digraph);
  2069     }
  2259     }
  2070 
  2260 
  2071     /// \brief ArcMap combined from two original ArcMap
  2261     /// \brief Arc map combined from two original arc maps
  2072     ///
  2262     ///
  2073     /// This class adapts two original digraph ArcMap to
  2263     /// This map adaptor class adapts two arc maps of the underlying
  2074     /// get an arc map on the undirected graph.
  2264     /// digraph to get an arc map of the undirected graph.
  2075     template <typename _ForwardMap, typename _BackwardMap>
  2265     /// Its value type is inherited from the first arc map type
       
  2266     /// (\c %ForwardMap).
       
  2267     template <typename ForwardMap, typename BackwardMap>
  2076     class CombinedArcMap {
  2268     class CombinedArcMap {
  2077     public:
  2269     public:
  2078 
  2270 
  2079       typedef _ForwardMap ForwardMap;
  2271       /// The key type of the map
  2080       typedef _BackwardMap BackwardMap;
  2272       typedef typename Parent::Arc Key;
       
  2273       /// The value type of the map
       
  2274       typedef typename ForwardMap::Value Value;
  2081 
  2275 
  2082       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
  2276       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
  2083 
  2277 
  2084       typedef typename ForwardMap::Value Value;
  2278       typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
  2085       typedef typename Parent::Arc Key;
  2279       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
  2086 
  2280       typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
  2087       /// \brief Constructor
  2281       typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
  2088       ///
  2282 
  2089       /// Constructor
  2283       /// Constructor
  2090       CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
  2284       CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
  2091         : _forward(&forward), _backward(&backward) {}
  2285         : _forward(&forward), _backward(&backward) {}
  2092 
  2286 
  2093 
  2287       /// Sets the value associated with the given key.
  2094       /// \brief Sets the value associated with a key.
       
  2095       ///
       
  2096       /// Sets the value associated with a key.
       
  2097       void set(const Key& e, const Value& a) {
  2288       void set(const Key& e, const Value& a) {
  2098         if (Parent::direction(e)) {
  2289         if (Parent::direction(e)) {
  2099           _forward->set(e, a);
  2290           _forward->set(e, a);
  2100         } else {
  2291         } else {
  2101           _backward->set(e, a);
  2292           _backward->set(e, a);
  2102         }
  2293         }
  2103       }
  2294       }
  2104 
  2295 
  2105       /// \brief Returns the value associated with a key.
  2296       /// Returns the value associated with the given key.
  2106       ///
  2297       ConstReturnValue operator[](const Key& e) const {
  2107       /// Returns the value associated with a key.
       
  2108       typename MapTraits<ForwardMap>::ConstReturnValue
       
  2109       operator[](const Key& e) const {
       
  2110         if (Parent::direction(e)) {
  2298         if (Parent::direction(e)) {
  2111           return (*_forward)[e];
  2299           return (*_forward)[e];
  2112         } else {
  2300         } else {
  2113           return (*_backward)[e];
  2301           return (*_backward)[e];
  2114         }
  2302         }
  2115       }
  2303       }
  2116 
  2304 
  2117       /// \brief Returns the value associated with a key.
  2305       /// Returns a reference to the value associated with the given key.
  2118       ///
  2306       ReturnValue operator[](const Key& e) {
  2119       /// Returns the value associated with a key.
       
  2120       typename MapTraits<ForwardMap>::ReturnValue
       
  2121       operator[](const Key& e) {
       
  2122         if (Parent::direction(e)) {
  2307         if (Parent::direction(e)) {
  2123           return (*_forward)[e];
  2308           return (*_forward)[e];
  2124         } else {
  2309         } else {
  2125           return (*_backward)[e];
  2310           return (*_backward)[e];
  2126         }
  2311         }
  2131       ForwardMap* _forward;
  2316       ForwardMap* _forward;
  2132       BackwardMap* _backward;
  2317       BackwardMap* _backward;
  2133 
  2318 
  2134     };
  2319     };
  2135 
  2320 
  2136     /// \brief Just gives back a combined arc map
  2321     /// \brief Returns a combined arc map
  2137     ///
  2322     ///
  2138     /// Just gives back a combined arc map
  2323     /// This function just returns a combined arc map.
  2139     template <typename ForwardMap, typename BackwardMap>
  2324     template <typename ForwardMap, typename BackwardMap>
  2140     static CombinedArcMap<ForwardMap, BackwardMap>
  2325     static CombinedArcMap<ForwardMap, BackwardMap>
  2141     combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
  2326     combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
  2142       return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
  2327       return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
  2143     }
  2328     }
  2163         const BackwardMap>(forward, backward);
  2348         const BackwardMap>(forward, backward);
  2164     }
  2349     }
  2165 
  2350 
  2166   };
  2351   };
  2167 
  2352 
  2168   /// \brief Just gives back an undirected view of the given digraph
  2353   /// \brief Returns a read-only Undirector adaptor
  2169   ///
  2354   ///
  2170   /// Just gives back an undirected view of the given digraph
  2355   /// This function just returns a read-only \ref Undirector adaptor.
  2171   template<typename Digraph>
  2356   /// \ingroup graph_adaptors
  2172   Undirector<const Digraph>
  2357   /// \relates Undirector
  2173   undirector(const Digraph& digraph) {
  2358   template<typename GR>
  2174     return Undirector<const Digraph>(digraph);
  2359   Undirector<const GR> undirector(const GR& digraph) {
       
  2360     return Undirector<const GR>(digraph);
  2175   }
  2361   }
       
  2362 
  2176 
  2363 
  2177   template <typename _Graph, typename _DirectionMap>
  2364   template <typename _Graph, typename _DirectionMap>
  2178   class OrienterBase {
  2365   class OrienterBase {
  2179   public:
  2366   public:
  2180 
  2367 
  2189     }
  2376     }
  2190 
  2377 
  2191     void first(Node& i) const { _graph->first(i); }
  2378     void first(Node& i) const { _graph->first(i); }
  2192     void first(Arc& i) const { _graph->first(i); }
  2379     void first(Arc& i) const { _graph->first(i); }
  2193     void firstIn(Arc& i, const Node& n) const {
  2380     void firstIn(Arc& i, const Node& n) const {
  2194       bool d;
  2381       bool d = true;
  2195       _graph->firstInc(i, d, n);
  2382       _graph->firstInc(i, d, n);
  2196       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
  2383       while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
  2197     }
  2384     }
  2198     void firstOut(Arc& i, const Node& n ) const {
  2385     void firstOut(Arc& i, const Node& n ) const {
  2199       bool d;
  2386       bool d = true;
  2200       _graph->firstInc(i, d, n);
  2387       _graph->firstInc(i, d, n);
  2201       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
  2388       while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
  2202     }
  2389     }
  2203 
  2390 
  2204     void next(Node& i) const { _graph->next(i); }
  2391     void next(Node& i) const { _graph->next(i); }
  2222     }
  2409     }
  2223 
  2410 
  2224     typedef NodeNumTagIndicator<Graph> NodeNumTag;
  2411     typedef NodeNumTagIndicator<Graph> NodeNumTag;
  2225     int nodeNum() const { return _graph->nodeNum(); }
  2412     int nodeNum() const { return _graph->nodeNum(); }
  2226 
  2413 
  2227     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
  2414     typedef EdgeNumTagIndicator<Graph> ArcNumTag;
  2228     int arcNum() const { return _graph->edgeNum(); }
  2415     int arcNum() const { return _graph->edgeNum(); }
  2229 
  2416 
  2230     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
  2417     typedef FindEdgeTagIndicator<Graph> FindArcTag;
  2231     Arc findArc(const Node& u, const Node& v,
  2418     Arc findArc(const Node& u, const Node& v,
  2232                 const Arc& prev = INVALID) {
  2419                 const Arc& prev = INVALID) const {
  2233       Arc arc = prev;
  2420       Arc arc = _graph->findEdge(u, v, prev);
  2234       bool d = arc == INVALID ? true : (*_direction)[arc];
  2421       while (arc != INVALID && source(arc) != u) {
  2235       if (d) {
       
  2236         arc = _graph->findEdge(u, v, arc);
  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       return arc;
  2424       return arc;
  2247     }
  2425     }
  2248 
  2426 
  2249     Node addNode() {
  2427     Node addNode() {
  2250       return Node(_graph->addNode());
  2428       return Node(_graph->addNode());
  2251     }
  2429     }
  2252 
  2430 
  2253     Arc addArc(const Node& u, const Node& v) {
  2431     Arc addArc(const Node& u, const Node& v) {
  2254       Arc arc = _graph->addArc(u, v);
  2432       Arc arc = _graph->addEdge(u, v);
  2255       _direction->set(arc, _graph->source(arc) == u);
  2433       _direction->set(arc, _graph->u(arc) == u);
  2256       return arc;
  2434       return arc;
  2257     }
  2435     }
  2258 
  2436 
  2259     void erase(const Node& i) { _graph->erase(i); }
  2437     void erase(const Node& i) { _graph->erase(i); }
  2260     void erase(const Arc& i) { _graph->erase(i); }
  2438     void erase(const Arc& i) { _graph->erase(i); }
  2341 
  2519 
  2342   };
  2520   };
  2343 
  2521 
  2344   /// \ingroup graph_adaptors
  2522   /// \ingroup graph_adaptors
  2345   ///
  2523   ///
  2346   /// \brief Orients the edges of the graph to get a digraph
  2524   /// \brief Adaptor class for orienting the edges of a graph to get a digraph
  2347   ///
  2525   ///
  2348   /// This adaptor orients each edge in the undirected graph. The
  2526   /// Orienter adaptor can be used for orienting the edges of a graph to
  2349   /// direction of the arcs stored in an edge node map.  The arcs can
  2527   /// get a digraph. A \c bool edge map of the underlying graph must be
  2350   /// be easily reverted by the \c reverseArc() member function in the
  2528   /// specified, which define the direction of the arcs in the adaptor.
  2351   /// adaptor. The Orienter adaptor is conform to the \ref
  2529   /// The arcs can be easily reversed by the \c reverseArc() member function
  2352   /// concepts::Digraph "Digraph concept".
  2530   /// of the adaptor.
  2353   ///
  2531   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
  2354   /// \tparam _Graph It must be conform to the \ref concepts::Graph
  2532   ///
  2355   /// "Graph concept". The type can be specified to be const.
  2533   /// The adapted graph can also be modified through this adaptor
  2356   /// \tparam _DirectionMap A bool valued edge map of the the adapted
  2534   /// by adding or removing nodes or arcs, unless the \c GR template
  2357   /// graph.
  2535   /// parameter is set to be \c const.
  2358   ///
  2536   ///
  2359   /// \sa orienter
  2537   /// \tparam GR The type of the adapted graph.
  2360   template<typename _Graph,
  2538   /// It must conform to the \ref concepts::Graph "Graph" concept.
  2361            typename DirectionMap = typename _Graph::template EdgeMap<bool> >
  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   class Orienter :
  2556   class Orienter :
  2363     public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
  2557     public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
  2364   public:
  2558 #endif
  2365     typedef _Graph Graph;
  2559   public:
  2366     typedef DigraphAdaptorExtender<
  2560 
  2367       OrienterBase<_Graph, DirectionMap> > Parent;
  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     typedef typename Parent::Arc Arc;
  2567     typedef typename Parent::Arc Arc;
  2369   protected:
  2568   protected:
  2370     Orienter() { }
  2569     Orienter() { }
  2371   public:
  2570   public:
  2372 
  2571 
  2373     /// \brief Constructor of the adaptor
  2572     /// \brief Constructor
  2374     ///
  2573     ///
  2375     /// Constructor of the adaptor
  2574     /// Constructor of the adaptor.
  2376     Orienter(Graph& graph, DirectionMap& direction) {
  2575     Orienter(Graph& graph, DirectionMap& direction) {
  2377       setGraph(graph);
  2576       setGraph(graph);
  2378       setDirectionMap(direction);
  2577       setDirectionMap(direction);
  2379     }
  2578     }
  2380 
  2579 
  2381     /// \brief Reverse arc
  2580     /// \brief Reverses the given arc
  2382     ///
  2581     ///
  2383     /// It reverse the given arc. It simply negate the direction in the map.
  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     void reverseArc(const Arc& a) {
  2585     void reverseArc(const Arc& a) {
  2385       Parent::reverseArc(a);
  2586       Parent::reverseArc(a);
  2386     }
  2587     }
  2387   };
  2588   };
  2388 
  2589 
  2389   /// \brief Just gives back a Orienter
  2590   /// \brief Returns a read-only Orienter adaptor
  2390   ///
  2591   ///
  2391   /// Just gives back a Orienter
  2592   /// This function just returns a read-only \ref Orienter adaptor.
  2392   template<typename Graph, typename DirectionMap>
  2593   /// \ingroup graph_adaptors
  2393   Orienter<const Graph, DirectionMap>
  2594   /// \relates Orienter
  2394   orienter(const Graph& graph, DirectionMap& dm) {
  2595   template<typename GR, typename DM>
  2395     return Orienter<const Graph, DirectionMap>(graph, 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 Graph, typename DirectionMap>
  2601   template<typename GR, typename DM>
  2399   Orienter<const Graph, const DirectionMap>
  2602   Orienter<const GR, const DM>
  2400   orienter(const Graph& graph, const DirectionMap& dm) {
  2603   orienter(const GR& graph, const DM& direction_map) {
  2401     return Orienter<const Graph, const DirectionMap>(graph, dm);
  2604     return Orienter<const GR, const DM>(graph, direction_map);
  2402   }
  2605   }
  2403 
  2606 
  2404   namespace _adaptor_bits {
  2607   namespace _adaptor_bits {
  2405 
  2608 
  2406     template<typename _Digraph,
  2609     template<typename Digraph,
  2407              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
  2610              typename CapacityMap,
  2408              typename _FlowMap = _CapacityMap,
  2611              typename FlowMap,
  2409              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  2612              typename Tolerance>
  2410     class ResForwardFilter {
  2613     class ResForwardFilter {
  2411     public:
  2614     public:
  2412 
       
  2413       typedef _Digraph Digraph;
       
  2414       typedef _CapacityMap CapacityMap;
       
  2415       typedef _FlowMap FlowMap;
       
  2416       typedef _Tolerance Tolerance;
       
  2417 
  2615 
  2418       typedef typename Digraph::Arc Key;
  2616       typedef typename Digraph::Arc Key;
  2419       typedef bool Value;
  2617       typedef bool Value;
  2420 
  2618 
  2421     private:
  2619     private:
  2432       bool operator[](const typename Digraph::Arc& a) const {
  2630       bool operator[](const typename Digraph::Arc& a) const {
  2433         return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
  2631         return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
  2434       }
  2632       }
  2435     };
  2633     };
  2436 
  2634 
  2437     template<typename _Digraph,
  2635     template<typename Digraph,
  2438              typename _CapacityMap = typename _Digraph::template ArcMap<int>,
  2636              typename CapacityMap,
  2439              typename _FlowMap = _CapacityMap,
  2637              typename FlowMap,
  2440              typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  2638              typename Tolerance>
  2441     class ResBackwardFilter {
  2639     class ResBackwardFilter {
  2442     public:
  2640     public:
  2443 
       
  2444       typedef _Digraph Digraph;
       
  2445       typedef _CapacityMap CapacityMap;
       
  2446       typedef _FlowMap FlowMap;
       
  2447       typedef _Tolerance Tolerance;
       
  2448 
  2641 
  2449       typedef typename Digraph::Arc Key;
  2642       typedef typename Digraph::Arc Key;
  2450       typedef bool Value;
  2643       typedef bool Value;
  2451 
  2644 
  2452     private:
  2645     private:
  2468 
  2661 
  2469   }
  2662   }
  2470 
  2663 
  2471   /// \ingroup graph_adaptors
  2664   /// \ingroup graph_adaptors
  2472   ///
  2665   ///
  2473   /// \brief An adaptor for composing the residual graph for directed
  2666   /// \brief Adaptor class for composing the residual digraph for directed
  2474   /// flow and circulation problems.
  2667   /// flow and circulation problems.
  2475   ///
  2668   ///
  2476   /// An adaptor for composing the residual graph for directed flow and
  2669   /// Residual can be used for composing the \e residual digraph for directed
  2477   /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
  2670   /// flow and 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$,
  2671   /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
  2479   /// be functions on the arc-set.
  2672   /// functions on the arcs.
  2480   ///
  2673   /// This adaptor implements a digraph structure with node set \f$ V \f$
  2481   /// Then Residual implements the digraph structure with
  2674   /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
  2482   /// node-set \f$ V \f$ 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
  2483   /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
  2676   /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so
  2484   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
  2677   /// called residual digraph.
  2485   /// called residual graph.  When we take the union
  2678   /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken,
  2486   /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
  2679   /// multiplicities are counted, i.e. the adaptor has exactly
  2487   /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
  2680   /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel
  2488   /// \f$ A_{backward} \f$, then in the adaptor it appears in both
  2681   /// arcs).
  2489   /// orientation.
  2682   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
  2490   ///
  2683   ///
  2491   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
  2684   /// \tparam GR The type of the adapted digraph.
  2492   /// "Digraph concept". The type is implicitly const.
  2685   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  2493   /// \tparam _CapacityMap An arc map of some numeric type, it defines
  2686   /// It is implicitly \c const.
  2494   /// the capacities in the flow problem. The map is implicitly const.
  2687   /// \tparam CM The type of the capacity map.
  2495   /// \tparam _FlowMap An arc map of some numeric type, it defines
  2688   /// It must be an arc map of some numerical type, which defines
  2496   /// the capacities in the flow problem.
  2689   /// the capacities in the flow problem. It is implicitly \c const.
  2497   /// \tparam _Tolerance Handler for inexact computation.
  2690   /// The default type is
  2498   template<typename _Digraph,
  2691   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
  2499            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
  2692   /// \tparam FM The type of the flow map.
  2500            typename _FlowMap = _CapacityMap,
  2693   /// It must be an arc map of some numerical type, which defines
  2501            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
  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   class Residual :
  2713   class Residual :
  2503     public FilterArcs<
  2714     public FilterArcs<
  2504     Undirector<const _Digraph>,
  2715       Undirector<const GR>,
  2505     typename Undirector<const _Digraph>::template CombinedArcMap<
  2716       typename Undirector<const GR>::template CombinedArcMap<
  2506       _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
  2717         _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>,
  2507                                       _FlowMap, _Tolerance>,
  2718         _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > >
  2508       _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
  2719 #endif
  2509                                        _FlowMap, _Tolerance> > >
       
  2510   {
  2720   {
  2511   public:
  2721   public:
  2512 
  2722 
  2513     typedef _Digraph Digraph;
  2723     /// The type of the underlying digraph.
  2514     typedef _CapacityMap CapacityMap;
  2724     typedef GR Digraph;
  2515     typedef _FlowMap FlowMap;
  2725     /// The type of the capacity map.
  2516     typedef _Tolerance Tolerance;
  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     typedef typename CapacityMap::Value Value;
  2732     typedef typename CapacityMap::Value Value;
  2519     typedef Residual Adaptor;
  2733     typedef Residual Adaptor;
  2520 
  2734 
  2521   protected:
  2735   protected:
  2527 
  2741 
  2528     typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
  2742     typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
  2529                                              FlowMap, Tolerance> BackwardFilter;
  2743                                              FlowMap, Tolerance> BackwardFilter;
  2530 
  2744 
  2531     typedef typename Undirected::
  2745     typedef typename Undirected::
  2532     template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
  2746       template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
  2533 
  2747 
  2534     typedef FilterArcs<Undirected, ArcFilter> Parent;
  2748     typedef FilterArcs<Undirected, ArcFilter> Parent;
  2535 
  2749 
  2536     const CapacityMap* _capacity;
  2750     const CapacityMap* _capacity;
  2537     FlowMap* _flow;
  2751     FlowMap* _flow;
  2541     BackwardFilter _backward_filter;
  2755     BackwardFilter _backward_filter;
  2542     ArcFilter _arc_filter;
  2756     ArcFilter _arc_filter;
  2543 
  2757 
  2544   public:
  2758   public:
  2545 
  2759 
  2546     /// \brief Constructor of the residual digraph.
  2760     /// \brief Constructor
  2547     ///
  2761     ///
  2548     /// Constructor of the residual graph. The parameters are the digraph,
  2762     /// Constructor of the residual digraph adaptor. The parameters are the
  2549     /// the flow map, the capacity map and a tolerance object.
  2763     /// digraph, the capacity map, the flow map, and a tolerance object.
  2550     Residual(const Digraph& digraph, const CapacityMap& capacity,
  2764     Residual(const Digraph& digraph, const CapacityMap& capacity,
  2551              FlowMap& flow, const Tolerance& tolerance = Tolerance())
  2765              FlowMap& flow, const Tolerance& tolerance = Tolerance())
  2552       : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
  2766       : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
  2553         _forward_filter(capacity, flow, tolerance),
  2767         _forward_filter(capacity, flow, tolerance),
  2554         _backward_filter(capacity, flow, tolerance),
  2768         _backward_filter(capacity, flow, tolerance),
  2558       Parent::setArcFilterMap(_arc_filter);
  2772       Parent::setArcFilterMap(_arc_filter);
  2559     }
  2773     }
  2560 
  2774 
  2561     typedef typename Parent::Arc Arc;
  2775     typedef typename Parent::Arc Arc;
  2562 
  2776 
  2563     /// \brief Gives back the residual capacity of the arc.
  2777     /// \brief Returns the residual capacity of the given arc.
  2564     ///
  2778     ///
  2565     /// Gives back the residual capacity of the arc.
  2779     /// Returns the residual capacity of the given arc.
  2566     Value residualCapacity(const Arc& a) const {
  2780     Value residualCapacity(const Arc& a) const {
  2567       if (Undirected::direction(a)) {
  2781       if (Undirected::direction(a)) {
  2568         return (*_capacity)[a] - (*_flow)[a];
  2782         return (*_capacity)[a] - (*_flow)[a];
  2569       } else {
  2783       } else {
  2570         return (*_flow)[a];
  2784         return (*_flow)[a];
  2571       }
  2785       }
  2572     }
  2786     }
  2573 
  2787 
  2574     /// \brief Augment on the given arc in the residual graph.
  2788     /// \brief Augments on the given arc in the residual digraph.
  2575     ///
  2789     ///
  2576     /// Augment on the given arc in the residual graph. It increase
  2790     /// Augments on the given arc in the residual digraph. It increases
  2577     /// or decrease the flow on the original arc depend on the direction
  2791     /// or decreases the flow value on the original arc according to the
  2578     /// of the residual arc.
  2792     /// direction of the residual arc.
  2579     void augment(const Arc& a, const Value& v) const {
  2793     void augment(const Arc& a, const Value& v) const {
  2580       if (Undirected::direction(a)) {
  2794       if (Undirected::direction(a)) {
  2581         _flow->set(a, (*_flow)[a] + v);
  2795         _flow->set(a, (*_flow)[a] + v);
  2582       } else {
  2796       } else {
  2583         _flow->set(a, (*_flow)[a] - v);
  2797         _flow->set(a, (*_flow)[a] - v);
  2584       }
  2798       }
  2585     }
  2799     }
  2586 
  2800 
  2587     /// \brief Returns the direction of the arc.
  2801     /// \brief Returns \c true if the given residual arc is a forward arc.
  2588     ///
  2802     ///
  2589     /// Returns true when the arc is same oriented as the original arc.
  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     static bool forward(const Arc& a) {
  2805     static bool forward(const Arc& a) {
  2591       return Undirected::direction(a);
  2806       return Undirected::direction(a);
  2592     }
  2807     }
  2593 
  2808 
  2594     /// \brief Returns the direction of the arc.
  2809     /// \brief Returns \c true if the given residual arc is a backward arc.
  2595     ///
  2810     ///
  2596     /// Returns true when the arc is opposite oriented as the original arc.
  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     static bool backward(const Arc& a) {
  2813     static bool backward(const Arc& a) {
  2598       return !Undirected::direction(a);
  2814       return !Undirected::direction(a);
  2599     }
  2815     }
  2600 
  2816 
  2601     /// \brief Gives back the forward oriented residual arc.
  2817     /// \brief Returns the forward oriented residual arc.
  2602     ///
  2818     ///
  2603     /// Gives back the forward oriented residual arc.
  2819     /// Returns the forward oriented residual arc related to the given
       
  2820     /// arc of the underlying digraph.
  2604     static Arc forward(const typename Digraph::Arc& a) {
  2821     static Arc forward(const typename Digraph::Arc& a) {
  2605       return Undirected::direct(a, true);
  2822       return Undirected::direct(a, true);
  2606     }
  2823     }
  2607 
  2824 
  2608     /// \brief Gives back the backward oriented residual arc.
  2825     /// \brief Returns the backward oriented residual arc.
  2609     ///
  2826     ///
  2610     /// Gives back the backward oriented residual arc.
  2827     /// Returns the backward oriented residual arc related to the given
       
  2828     /// arc of the underlying digraph.
  2611     static Arc backward(const typename Digraph::Arc& a) {
  2829     static Arc backward(const typename Digraph::Arc& a) {
  2612       return Undirected::direct(a, false);
  2830       return Undirected::direct(a, false);
  2613     }
  2831     }
  2614 
  2832 
  2615     /// \brief Residual capacity map.
  2833     /// \brief Residual capacity map.
  2616     ///
  2834     ///
  2617     /// In generic residual graph the residual capacity can be obtained
  2835     /// This map adaptor class can be used for obtaining the residual
  2618     /// as a map.
  2836     /// capacities as an arc map of the residual digraph.
       
  2837     /// Its value type is inherited from the capacity map.
  2619     class ResidualCapacity {
  2838     class ResidualCapacity {
  2620     protected:
  2839     protected:
  2621       const Adaptor* _adaptor;
  2840       const Adaptor* _adaptor;
  2622     public:
  2841     public:
  2623       /// The Key type
  2842       /// The key type of the map
  2624       typedef Arc Key;
  2843       typedef Arc Key;
  2625       /// The Value type
  2844       /// The value type of the map
  2626       typedef typename _CapacityMap::Value Value;
  2845       typedef typename CapacityMap::Value Value;
  2627 
  2846 
  2628       /// Constructor
  2847       /// Constructor
  2629       ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
  2848       ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
  2630 
  2849 
  2631       /// \e
  2850       /// Returns the value associated with the given residual arc
  2632       Value operator[](const Arc& a) const {
  2851       Value operator[](const Arc& a) const {
  2633         return _adaptor->residualCapacity(a);
  2852         return _adaptor->residualCapacity(a);
  2634       }
  2853       }
  2635 
  2854 
  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 (read-only) Residual adaptor
       
  2867   ///
       
  2868   /// This function just returns a (read-only) \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   template <typename _Digraph>
  2879   template <typename _Digraph>
  2641   class SplitNodesBase {
  2880   class SplitNodesBase {
  2642   public:
  2881   public:
  2643 
  2882 
  2882     static Arc arc(const DigraphArc& e) {
  3121     static Arc arc(const DigraphArc& e) {
  2883       return Arc(e);
  3122       return Arc(e);
  2884     }
  3123     }
  2885 
  3124 
  2886     typedef True NodeNumTag;
  3125     typedef True NodeNumTag;
  2887 
       
  2888     int nodeNum() const {
  3126     int nodeNum() const {
  2889       return  2 * countNodes(*_digraph);
  3127       return  2 * countNodes(*_digraph);
  2890     }
  3128     }
  2891 
  3129 
  2892     typedef True EdgeNumTag;
  3130     typedef True ArcNumTag;
  2893     int arcNum() const {
  3131     int arcNum() const {
  2894       return countArcs(*_digraph) + countNodes(*_digraph);
  3132       return countArcs(*_digraph) + countNodes(*_digraph);
  2895     }
  3133     }
  2896 
  3134 
  2897     typedef True FindEdgeTag;
  3135     typedef True FindArcTag;
  2898     Arc findArc(const Node& u, const Node& v,
  3136     Arc findArc(const Node& u, const Node& v,
  2899                 const Arc& prev = INVALID) const {
  3137                 const Arc& prev = INVALID) const {
  2900       if (inNode(u)) {
  3138       if (inNode(u) && outNode(v)) {
  2901         if (outNode(v)) {
  3139         if (static_cast<const DigraphNode&>(u) ==
  2902           if (static_cast<const DigraphNode&>(u) ==
  3140             static_cast<const DigraphNode&>(v) && prev == INVALID) {
  2903               static_cast<const DigraphNode&>(v) && prev == INVALID) {
  3141           return Arc(u);
  2904             return Arc(u);
       
  2905           }
       
  2906         }
  3142         }
  2907       } else {
  3143       }
  2908         if (inNode(v)) {
  3144       else if (outNode(u) && inNode(v)) {
  2909           return Arc(::lemon::findArc(*_digraph, u, v, prev));
  3145         return Arc(::lemon::findArc(*_digraph, u, v, prev));
  2910         }
       
  2911       }
  3146       }
  2912       return INVALID;
  3147       return INVALID;
  2913     }
  3148     }
  2914 
  3149 
  2915   private:
  3150   private:
  2919       : public MapTraits<typename Parent::template NodeMap<_Value> > {
  3154       : public MapTraits<typename Parent::template NodeMap<_Value> > {
  2920       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  3155       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  2921     public:
  3156     public:
  2922       typedef Node Key;
  3157       typedef Node Key;
  2923       typedef _Value Value;
  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       NodeMapBase(const Adaptor& adaptor)
  3165       NodeMapBase(const Adaptor& adaptor)
  2926         : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
  3166         : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
  2927       NodeMapBase(const Adaptor& adaptor, const Value& value)
  3167       NodeMapBase(const Adaptor& adaptor, const Value& value)
  2928         : _in_map(*adaptor._digraph, value),
  3168         : _in_map(*adaptor._digraph, value),
  2931       void set(const Node& key, const Value& val) {
  3171       void set(const Node& key, const Value& val) {
  2932         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
  3172         if (Adaptor::inNode(key)) { _in_map.set(key, val); }
  2933         else {_out_map.set(key, val); }
  3173         else {_out_map.set(key, val); }
  2934       }
  3174       }
  2935 
  3175 
  2936       typename MapTraits<NodeImpl>::ReturnValue
  3176       ReturnValue operator[](const Node& key) {
  2937       operator[](const Node& key) {
       
  2938         if (Adaptor::inNode(key)) { return _in_map[key]; }
  3177         if (Adaptor::inNode(key)) { return _in_map[key]; }
  2939         else { return _out_map[key]; }
  3178         else { return _out_map[key]; }
  2940       }
  3179       }
  2941 
  3180 
  2942       typename MapTraits<NodeImpl>::ConstReturnValue
  3181       ConstReturnValue operator[](const Node& key) const {
  2943       operator[](const Node& key) const {
       
  2944         if (Adaptor::inNode(key)) { return _in_map[key]; }
  3182         if (Adaptor::inNode(key)) { return _in_map[key]; }
  2945         else { return _out_map[key]; }
  3183         else { return _out_map[key]; }
  2946       }
  3184       }
  2947 
  3185 
  2948     private:
  3186     private:
  2955       typedef typename Parent::template ArcMap<_Value> ArcImpl;
  3193       typedef typename Parent::template ArcMap<_Value> ArcImpl;
  2956       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  3194       typedef typename Parent::template NodeMap<_Value> NodeImpl;
  2957     public:
  3195     public:
  2958       typedef Arc Key;
  3196       typedef Arc Key;
  2959       typedef _Value Value;
  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       ArcMapBase(const Adaptor& adaptor)
  3204       ArcMapBase(const Adaptor& adaptor)
  2962         : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
  3205         : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
  2963       ArcMapBase(const Adaptor& adaptor, const Value& value)
  3206       ArcMapBase(const Adaptor& adaptor, const Value& value)
  2964         : _arc_map(*adaptor._digraph, value),
  3207         : _arc_map(*adaptor._digraph, value),
  2970         } else {
  3213         } else {
  2971           _node_map.set(key._item.second(), val);
  3214           _node_map.set(key._item.second(), val);
  2972         }
  3215         }
  2973       }
  3216       }
  2974 
  3217 
  2975       typename MapTraits<ArcImpl>::ReturnValue
  3218       ReturnValue operator[](const Arc& key) {
  2976       operator[](const Arc& key) {
       
  2977         if (Adaptor::origArc(key)) {
  3219         if (Adaptor::origArc(key)) {
  2978           return _arc_map[key._item.first()];
  3220           return _arc_map[key._item.first()];
  2979         } else {
  3221         } else {
  2980           return _node_map[key._item.second()];
  3222           return _node_map[key._item.second()];
  2981         }
  3223         }
  2982       }
  3224       }
  2983 
  3225 
  2984       typename MapTraits<ArcImpl>::ConstReturnValue
  3226       ConstReturnValue operator[](const Arc& key) const {
  2985       operator[](const Arc& key) const {
       
  2986         if (Adaptor::origArc(key)) {
  3227         if (Adaptor::origArc(key)) {
  2987           return _arc_map[key._item.first()];
  3228           return _arc_map[key._item.first()];
  2988         } else {
  3229         } else {
  2989           return _node_map[key._item.second()];
  3230           return _node_map[key._item.second()];
  2990         }
  3231         }
  3061 
  3302 
  3062   };
  3303   };
  3063 
  3304 
  3064   /// \ingroup graph_adaptors
  3305   /// \ingroup graph_adaptors
  3065   ///
  3306   ///
  3066   /// \brief Split the nodes of a directed graph
  3307   /// \brief Adaptor class for splitting the nodes of a digraph.
  3067   ///
  3308   ///
  3068   /// The SplitNodes adaptor splits each node into an in-node and an
  3309   /// SplitNodes adaptor can be used for splitting each node into an
  3069   /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
  3310   /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor
  3070   /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
  3311   /// replaces each node \f$ u \f$ in the digraph with two nodes,
  3071   /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
  3312   /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$.
  3072   /// original digraph the new target of the arc will be \f$ u_{in} \f$
  3313   /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the
  3073   /// and similarly the source of the original \f$ (u, v) \f$ arc
  3314   /// new target of the arc will be \f$ u_{in} \f$ and similarly the
  3074   /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
  3315   /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$.
  3075   /// the original digraph an additional arc which connects
  3316   /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$
  3076   /// \f$ (u_{in}, u_{out}) \f$.
  3317   /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph.
  3077   ///
  3318   ///
  3078   /// The aim of this class is to run algorithm with node costs if the
  3319   /// The aim of this class is running an algorithm with respect to node
  3079   /// algorithm can use directly just arc costs. In this case we should use
  3320   /// costs or capacities if the algorithm considers only arc costs or
  3080   /// a \c SplitNodes and set the node cost of the graph to the
  3321   /// capacities directly.
  3081   /// bind arc in the adapted graph.
  3322   /// In this case you can use \c SplitNodes adaptor, and set the node
  3082   ///
  3323   /// costs/capacities of the original digraph to the \e bind \e arcs
  3083   /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
  3324   /// in the adaptor.
  3084   /// "Digraph concept". The type can be specified to be const.
  3325   ///
  3085   template <typename _Digraph>
  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   class SplitNodes
  3336   class SplitNodes
  3087     : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
  3337     : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {
  3088   public:
  3338 #endif
  3089     typedef _Digraph Digraph;
  3339   public:
  3090     typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
  3340     typedef GR Digraph;
       
  3341     typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;
  3091 
  3342 
  3092     typedef typename Digraph::Node DigraphNode;
  3343     typedef typename Digraph::Node DigraphNode;
  3093     typedef typename Digraph::Arc DigraphArc;
  3344     typedef typename Digraph::Arc DigraphArc;
  3094 
  3345 
  3095     typedef typename Parent::Node Node;
  3346     typedef typename Parent::Node Node;
  3096     typedef typename Parent::Arc Arc;
  3347     typedef typename Parent::Arc Arc;
  3097 
  3348 
  3098     /// \brief Constructor of the adaptor.
  3349     /// \brief Constructor
  3099     ///
  3350     ///
  3100     /// Constructor of the adaptor.
  3351     /// Constructor of the adaptor.
  3101     SplitNodes(Digraph& g) {
  3352     SplitNodes(const Digraph& g) {
  3102       Parent::setDigraph(g);
  3353       Parent::setDigraph(g);
  3103     }
  3354     }
  3104 
  3355 
  3105     /// \brief Returns true when the node is in-node.
  3356     /// \brief Returns \c true if the given node is an in-node.
  3106     ///
  3357     ///
  3107     /// Returns true when the node is in-node.
  3358     /// Returns \c true if the given node is an in-node.
  3108     static bool inNode(const Node& n) {
  3359     static bool inNode(const Node& n) {
  3109       return Parent::inNode(n);
  3360       return Parent::inNode(n);
  3110     }
  3361     }
  3111 
  3362 
  3112     /// \brief Returns true when the node is out-node.
  3363     /// \brief Returns \c true if the given node is an out-node.
  3113     ///
  3364     ///
  3114     /// Returns true when the node is out-node.
  3365     /// Returns \c true if the given node is an out-node.
  3115     static bool outNode(const Node& n) {
  3366     static bool outNode(const Node& n) {
  3116       return Parent::outNode(n);
  3367       return Parent::outNode(n);
  3117     }
  3368     }
  3118 
  3369 
  3119     /// \brief Returns true when the arc is arc in the original digraph.
  3370     /// \brief Returns \c true if the given arc is an original arc.
  3120     ///
  3371     ///
  3121     /// Returns true when the arc is arc in the original digraph.
  3372     /// Returns \c true if the given arc is one of the arcs in the
       
  3373     /// original digraph.
  3122     static bool origArc(const Arc& a) {
  3374     static bool origArc(const Arc& a) {
  3123       return Parent::origArc(a);
  3375       return Parent::origArc(a);
  3124     }
  3376     }
  3125 
  3377 
  3126     /// \brief Returns true when the arc binds an in-node and an out-node.
  3378     /// \brief Returns \c true if the given arc is a bind arc.
  3127     ///
  3379     ///
  3128     /// Returns true when the arc binds an in-node and an out-node.
  3380     /// Returns \c true if the given arc is a bind arc, i.e. it connects
       
  3381     /// an in-node and an out-node.
  3129     static bool bindArc(const Arc& a) {
  3382     static bool bindArc(const Arc& a) {
  3130       return Parent::bindArc(a);
  3383       return Parent::bindArc(a);
  3131     }
  3384     }
  3132 
  3385 
  3133     /// \brief Gives back the in-node created from the \c node.
  3386     /// \brief Returns the in-node created from the given original node.
  3134     ///
  3387     ///
  3135     /// Gives back the in-node created from the \c node.
  3388     /// Returns the in-node created from the given original node.
  3136     static Node inNode(const DigraphNode& n) {
  3389     static Node inNode(const DigraphNode& n) {
  3137       return Parent::inNode(n);
  3390       return Parent::inNode(n);
  3138     }
  3391     }
  3139 
  3392 
  3140     /// \brief Gives back the out-node created from the \c node.
  3393     /// \brief Returns the out-node created from the given original node.
  3141     ///
  3394     ///
  3142     /// Gives back the out-node created from the \c node.
  3395     /// Returns the out-node created from the given original node.
  3143     static Node outNode(const DigraphNode& n) {
  3396     static Node outNode(const DigraphNode& n) {
  3144       return Parent::outNode(n);
  3397       return Parent::outNode(n);
  3145     }
  3398     }
  3146 
  3399 
  3147     /// \brief Gives back the arc binds the two part of the node.
  3400     /// \brief Returns the bind arc that corresponds to the given
  3148     ///
  3401     /// original node.
  3149     /// Gives back the arc binds the two part of the node.
  3402     ///
       
  3403     /// Returns the bind arc in the adaptor that corresponds to the given
       
  3404     /// original node, i.e. the arc connecting the in-node and out-node
       
  3405     /// of \c n.
  3150     static Arc arc(const DigraphNode& n) {
  3406     static Arc arc(const DigraphNode& n) {
  3151       return Parent::arc(n);
  3407       return Parent::arc(n);
  3152     }
  3408     }
  3153 
  3409 
  3154     /// \brief Gives back the arc of the original arc.
  3410     /// \brief Returns the arc that corresponds to the given original arc.
  3155     ///
  3411     ///
  3156     /// Gives back the arc of the original arc.
  3412     /// Returns the arc in the adaptor that corresponds to the given
       
  3413     /// original arc.
  3157     static Arc arc(const DigraphArc& a) {
  3414     static Arc arc(const DigraphArc& a) {
  3158       return Parent::arc(a);
  3415       return Parent::arc(a);
  3159     }
  3416     }
  3160 
  3417 
  3161     /// \brief NodeMap combined from two original NodeMap
  3418     /// \brief Node map combined from two original node maps
  3162     ///
  3419     ///
  3163     /// This class adapt two of the original digraph NodeMap to
  3420     /// This map adaptor class adapts two node maps of the original digraph
  3164     /// get a node map on the adapted 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     template <typename InNodeMap, typename OutNodeMap>
  3424     template <typename InNodeMap, typename OutNodeMap>
  3166     class CombinedNodeMap {
  3425     class CombinedNodeMap {
  3167     public:
  3426     public:
  3168 
  3427 
       
  3428       /// The key type of the map
  3169       typedef Node Key;
  3429       typedef Node Key;
       
  3430       /// The value type of the map
  3170       typedef typename InNodeMap::Value Value;
  3431       typedef typename InNodeMap::Value Value;
  3171 
  3432 
  3172       /// \brief Constructor
  3433       typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
  3173       ///
  3434       typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
  3174       /// Constructor.
  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       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
  3440       CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
  3176         : _in_map(in_map), _out_map(out_map) {}
  3441         : _in_map(in_map), _out_map(out_map) {}
  3177 
  3442 
  3178       /// \brief The subscript operator.
  3443       /// Returns the value associated with the given key.
  3179       ///
  3444       Value operator[](const Key& key) const {
  3180       /// The subscript operator.
  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       Value& operator[](const Key& key) {
  3453       Value& operator[](const Key& key) {
  3182         if (Parent::inNode(key)) {
  3454         if (Parent::inNode(key)) {
  3183           return _in_map[key];
  3455           return _in_map[key];
  3184         } else {
  3456         } else {
  3185           return _out_map[key];
  3457           return _out_map[key];
  3186         }
  3458         }
  3187       }
  3459       }
  3188 
  3460 
  3189       /// \brief The const subscript operator.
  3461       /// Sets the value associated with the given key.
  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.
       
  3203       void set(const Key& key, const Value& value) {
  3462       void set(const Key& key, const Value& value) {
  3204         if (Parent::inNode(key)) {
  3463         if (Parent::inNode(key)) {
  3205           _in_map.set(key, value);
  3464           _in_map.set(key, value);
  3206         } else {
  3465         } else {
  3207           _out_map.set(key, value);
  3466           _out_map.set(key, value);
  3214       OutNodeMap& _out_map;
  3473       OutNodeMap& _out_map;
  3215 
  3474 
  3216     };
  3475     };
  3217 
  3476 
  3218 
  3477 
  3219     /// \brief Just gives back a combined node map
  3478     /// \brief Returns a combined node map
  3220     ///
  3479     ///
  3221     /// Just gives back a combined node map
  3480     /// This function just returns a combined node map.
  3222     template <typename InNodeMap, typename OutNodeMap>
  3481     template <typename InNodeMap, typename OutNodeMap>
  3223     static CombinedNodeMap<InNodeMap, OutNodeMap>
  3482     static CombinedNodeMap<InNodeMap, OutNodeMap>
  3224     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
  3483     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
  3225       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
  3484       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
  3226     }
  3485     }
  3242     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
  3501     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
  3243       return CombinedNodeMap<const InNodeMap,
  3502       return CombinedNodeMap<const InNodeMap,
  3244         const OutNodeMap>(in_map, out_map);
  3503         const OutNodeMap>(in_map, out_map);
  3245     }
  3504     }
  3246 
  3505 
  3247     /// \brief ArcMap combined from an original ArcMap and a NodeMap
  3506     /// \brief Arc map combined from an arc map and a node map of the
  3248     ///
  3507     /// original digraph.
  3249     /// This class adapt an original ArcMap and a NodeMap to get an
  3508     ///
  3250     /// arc map on the adapted digraph
  3509     /// This map adaptor class adapts an arc map and a node map of the
  3251     template <typename DigraphArcMap, typename DigraphNodeMap>
  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     class CombinedArcMap {
  3514     class CombinedArcMap {
  3253     public:
  3515     public:
  3254 
  3516 
       
  3517       /// The key type of the map
  3255       typedef Arc Key;
  3518       typedef Arc Key;
  3256       typedef typename DigraphArcMap::Value Value;
  3519       /// The value type of the map
  3257 
  3520       typedef typename ArcMap::Value Value;
  3258       /// \brief Constructor
  3521 
  3259       ///
  3522       typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
  3260       /// Constructor.
  3523       typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
  3261       CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
  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         : _arc_map(arc_map), _node_map(node_map) {}
  3530         : _arc_map(arc_map), _node_map(node_map) {}
  3263 
  3531 
  3264       /// \brief The subscript operator.
  3532       /// Returns the value associated with the given key.
  3265       ///
  3533       Value operator[](const Key& arc) const {
  3266       /// The subscript operator.
  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       void set(const Arc& arc, const Value& val) {
  3551       void set(const Arc& arc, const Value& val) {
  3268         if (Parent::origArc(arc)) {
  3552         if (Parent::origArc(arc)) {
  3269           _arc_map.set(arc, val);
  3553           _arc_map.set(arc, val);
  3270         } else {
  3554         } else {
  3271           _node_map.set(arc, val);
  3555           _node_map.set(arc, val);
  3272         }
  3556         }
  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     private:
  3559     private:
  3298       DigraphArcMap& _arc_map;
  3560       ArcMap& _arc_map;
  3299       DigraphNodeMap& _node_map;
  3561       NodeMap& _node_map;
  3300     };
  3562     };
  3301 
  3563 
  3302     /// \brief Just gives back a combined arc map
  3564     /// \brief Returns a combined arc map
  3303     ///
  3565     ///
  3304     /// Just gives back a combined arc map
  3566     /// This function just returns a combined arc map.
  3305     template <typename DigraphArcMap, typename DigraphNodeMap>
  3567     template <typename ArcMap, typename NodeMap>
  3306     static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
  3568     static CombinedArcMap<ArcMap, NodeMap>
  3307     combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  3569     combinedArcMap(ArcMap& arc_map, NodeMap& node_map) {
  3308       return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
  3570       return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map);
  3309     }
  3571     }
  3310 
  3572 
  3311     template <typename DigraphArcMap, typename DigraphNodeMap>
  3573     template <typename ArcMap, typename NodeMap>
  3312     static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
  3574     static CombinedArcMap<const ArcMap, NodeMap>
  3313     combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
  3575     combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) {
  3314       return CombinedArcMap<const DigraphArcMap,
  3576       return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map);
  3315         DigraphNodeMap>(arc_map, node_map);
  3577     }
  3316     }
  3578 
  3317 
  3579     template <typename ArcMap, typename NodeMap>
  3318     template <typename DigraphArcMap, typename DigraphNodeMap>
  3580     static CombinedArcMap<ArcMap, const NodeMap>
  3319     static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
  3581     combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) {
  3320     combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
  3582       return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map);
  3321       return CombinedArcMap<DigraphArcMap,
  3583     }
  3322         const DigraphNodeMap>(arc_map, node_map);
  3584 
  3323     }
  3585     template <typename ArcMap, typename NodeMap>
  3324 
  3586     static CombinedArcMap<const ArcMap, const NodeMap>
  3325     template <typename DigraphArcMap, typename DigraphNodeMap>
  3587     combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) {
  3326     static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
  3588       return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map);
  3327     combinedArcMap(const DigraphArcMap& arc_map,
       
  3328                    const DigraphNodeMap& node_map) {
       
  3329       return CombinedArcMap<const DigraphArcMap,
       
  3330         const DigraphNodeMap>(arc_map, node_map);
       
  3331     }
  3589     }
  3332 
  3590 
  3333   };
  3591   };
  3334 
  3592 
  3335   /// \brief Just gives back a node splitter
  3593   /// \brief Returns a (read-only) SplitNodes adaptor
  3336   ///
  3594   ///
  3337   /// Just gives back a node splitter
  3595   /// This function just returns a (read-only) \ref SplitNodes adaptor.
  3338   template<typename Digraph>
  3596   /// \ingroup graph_adaptors
  3339   SplitNodes<Digraph>
  3597   /// \relates SplitNodes
  3340   splitNodes(const Digraph& digraph) {
  3598   template<typename GR>
  3341     return SplitNodes<Digraph>(digraph);
  3599   SplitNodes<GR>
       
  3600   splitNodes(const GR& digraph) {
       
  3601     return SplitNodes<GR>(digraph);
  3342   }
  3602   }
  3343 
  3603 
  3344 
       
  3345 } //namespace lemon
  3604 } //namespace lemon
  3346 
  3605 
  3347 #endif //LEMON_ADAPTORS_H
  3606 #endif //LEMON_ADAPTORS_H