lemon/adaptors.h
branch1.1
changeset 788 98b306776b25
parent 654 cb38ccedd2c1
child 793 8d2e55fac752
equal deleted inserted replaced
19:b4a60e5f5210 20:958e16843379
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2011
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   416       : Parent(), _node_filter(0), _arc_filter(0) { }
   416       : Parent(), _node_filter(0), _arc_filter(0) { }
   417 
   417 
   418     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
   418     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
   419       Parent::initialize(digraph);
   419       Parent::initialize(digraph);
   420       _node_filter = &node_filter;
   420       _node_filter = &node_filter;
   421       _arc_filter = &arc_filter;      
   421       _arc_filter = &arc_filter;
   422     }
   422     }
   423 
   423 
   424   public:
   424   public:
   425 
   425 
   426     typedef typename Parent::Node Node;
   426     typedef typename Parent::Node Node;
   503     }
   503     }
   504 
   504 
   505   public:
   505   public:
   506 
   506 
   507     template <typename V>
   507     template <typename V>
   508     class NodeMap 
   508     class NodeMap
   509       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
   509       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   510 	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
   510               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
   511       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   511       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   512 	LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
   512         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
   513 
   513 
   514     public:
   514     public:
   515       typedef V Value;
   515       typedef V Value;
   516 
   516 
   517       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
   517       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
   530         return *this;
   530         return *this;
   531       }
   531       }
   532     };
   532     };
   533 
   533 
   534     template <typename V>
   534     template <typename V>
   535     class ArcMap 
   535     class ArcMap
   536       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   536       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   537 	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
   537               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
   538       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   538       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   539         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
   539         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
   540 
   540 
   541     public:
   541     public:
   542       typedef V Value;
   542       typedef V Value;
   577       : Parent(), _node_filter(0), _arc_filter(0) { }
   577       : Parent(), _node_filter(0), _arc_filter(0) { }
   578 
   578 
   579     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
   579     void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
   580       Parent::initialize(digraph);
   580       Parent::initialize(digraph);
   581       _node_filter = &node_filter;
   581       _node_filter = &node_filter;
   582       _arc_filter = &arc_filter;      
   582       _arc_filter = &arc_filter;
   583     }
   583     }
   584 
   584 
   585   public:
   585   public:
   586 
   586 
   587     typedef typename Parent::Node Node;
   587     typedef typename Parent::Node Node;
   646       }
   646       }
   647       return arc;
   647       return arc;
   648     }
   648     }
   649 
   649 
   650     template <typename V>
   650     template <typename V>
   651     class NodeMap 
   651     class NodeMap
   652       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   652       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   653           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
   653           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
   654       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
   654       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   655         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
   655         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
   656 
   656 
   657     public:
   657     public:
   658       typedef V Value;
   658       typedef V Value;
   659 
   659 
   673         return *this;
   673         return *this;
   674       }
   674       }
   675     };
   675     };
   676 
   676 
   677     template <typename V>
   677     template <typename V>
   678     class ArcMap 
   678     class ArcMap
   679       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   679       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   680           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
   680           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
   681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   682         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
   682         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
   683 
   683 
  1014       }
  1014       }
  1015       return edge;
  1015       return edge;
  1016     }
  1016     }
  1017 
  1017 
  1018     template <typename V>
  1018     template <typename V>
  1019     class NodeMap 
  1019     class NodeMap
  1020       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1020       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1021           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
  1021           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
  1022       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
  1022       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1023         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
  1023         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
  1024 
  1024 
  1025     public:
  1025     public:
  1026       typedef V Value;
  1026       typedef V Value;
  1027 
  1027 
  1041         return *this;
  1041         return *this;
  1042       }
  1042       }
  1043     };
  1043     };
  1044 
  1044 
  1045     template <typename V>
  1045     template <typename V>
  1046     class ArcMap 
  1046     class ArcMap
  1047       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1047       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1048           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
  1048           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
  1049       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
  1049       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1050         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
  1050         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
  1051 
  1051 
  1052     public:
  1052     public:
  1053       typedef V Value;
  1053       typedef V Value;
  1054 
  1054 
  1068         return *this;
  1068         return *this;
  1069       }
  1069       }
  1070     };
  1070     };
  1071 
  1071 
  1072     template <typename V>
  1072     template <typename V>
  1073     class EdgeMap 
  1073     class EdgeMap
  1074       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1074       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1075         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
  1075         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
  1076       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
  1076       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1077         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
  1077         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
  1078 
  1078 
  1079     public:
  1079     public:
  1080       typedef V Value;
  1080       typedef V Value;
  1081 
  1081 
  1110 
  1110 
  1111     typedef SubGraphBase Adaptor;
  1111     typedef SubGraphBase Adaptor;
  1112   protected:
  1112   protected:
  1113     NF* _node_filter;
  1113     NF* _node_filter;
  1114     EF* _edge_filter;
  1114     EF* _edge_filter;
  1115     SubGraphBase() 
  1115     SubGraphBase()
  1116 	  : Parent(), _node_filter(0), _edge_filter(0) { }
  1116           : Parent(), _node_filter(0), _edge_filter(0) { }
  1117 
  1117 
  1118     void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
  1118     void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
  1119       Parent::initialize(graph);
  1119       Parent::initialize(graph);
  1120       _node_filter = &node_filter;
  1120       _node_filter = &node_filter;
  1121       _edge_filter = &edge_filter;
  1121       _edge_filter = &edge_filter;
  1212       }
  1212       }
  1213       return edge;
  1213       return edge;
  1214     }
  1214     }
  1215 
  1215 
  1216     template <typename V>
  1216     template <typename V>
  1217     class NodeMap 
  1217     class NodeMap
  1218       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1218       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1219           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
  1219           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
  1220       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
  1220       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1221         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
  1221         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
  1222 
  1222 
  1223     public:
  1223     public:
  1224       typedef V Value;
  1224       typedef V Value;
  1225 
  1225 
  1239         return *this;
  1239         return *this;
  1240       }
  1240       }
  1241     };
  1241     };
  1242 
  1242 
  1243     template <typename V>
  1243     template <typename V>
  1244     class ArcMap 
  1244     class ArcMap
  1245       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1245       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1246           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
  1246           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
  1247       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
  1247       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1248         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
  1248         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
  1249 
  1249 
  1250     public:
  1250     public:
  1251       typedef V Value;
  1251       typedef V Value;
  1252 
  1252 
  1266         return *this;
  1266         return *this;
  1267       }
  1267       }
  1268     };
  1268     };
  1269 
  1269 
  1270     template <typename V>
  1270     template <typename V>
  1271     class EdgeMap 
  1271     class EdgeMap
  1272       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1272       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1273         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
  1273         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
  1274       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
  1274       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1275 	LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
  1275         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
  1276 
  1276 
  1277     public:
  1277     public:
  1278       typedef V Value;
  1278       typedef V Value;
  1279 
  1279 
  1280       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1280       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1493     public DigraphAdaptorExtender<
  1493     public DigraphAdaptorExtender<
  1494       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
  1494       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
  1495                      true> > {
  1495                      true> > {
  1496 #endif
  1496 #endif
  1497     typedef DigraphAdaptorExtender<
  1497     typedef DigraphAdaptorExtender<
  1498       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
  1498       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
  1499                      true> > Parent;
  1499                      true> > Parent;
  1500 
  1500 
  1501   public:
  1501   public:
  1502 
  1502 
  1503     typedef GR Digraph;
  1503     typedef GR Digraph;
  1514 
  1514 
  1515     /// \brief Constructor
  1515     /// \brief Constructor
  1516     ///
  1516     ///
  1517     /// Creates a subgraph for the given digraph or graph with the
  1517     /// Creates a subgraph for the given digraph or graph with the
  1518     /// given node filter map.
  1518     /// given node filter map.
  1519     FilterNodes(GR& graph, NF& node_filter) 
  1519     FilterNodes(GR& graph, NF& node_filter)
  1520       : Parent(), const_true_map()
  1520       : Parent(), const_true_map()
  1521     {
  1521     {
  1522       Parent::initialize(graph, node_filter, const_true_map);
  1522       Parent::initialize(graph, node_filter, const_true_map);
  1523     }
  1523     }
  1524 
  1524 
  1552 
  1552 
  1553   template<typename GR, typename NF>
  1553   template<typename GR, typename NF>
  1554   class FilterNodes<GR, NF,
  1554   class FilterNodes<GR, NF,
  1555                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
  1555                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
  1556     public GraphAdaptorExtender<
  1556     public GraphAdaptorExtender<
  1557       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
  1557       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
  1558                    true> > {
  1558                    true> > {
  1559 
  1559 
  1560     typedef GraphAdaptorExtender<
  1560     typedef GraphAdaptorExtender<
  1561       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
  1561       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
  1562                    true> > Parent;
  1562                    true> > Parent;
  1563 
  1563 
  1564   public:
  1564   public:
  1565 
  1565 
  1566     typedef GR Graph;
  1566     typedef GR Graph;
  1640     public DigraphAdaptorExtender<
  1640     public DigraphAdaptorExtender<
  1641       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
  1641       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
  1642                      AF, false> > {
  1642                      AF, false> > {
  1643 #endif
  1643 #endif
  1644     typedef DigraphAdaptorExtender<
  1644     typedef DigraphAdaptorExtender<
  1645       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
  1645       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
  1646                      AF, false> > Parent;
  1646                      AF, false> > Parent;
  1647 
  1647 
  1648   public:
  1648   public:
  1649 
  1649 
  1650     /// The type of the adapted digraph.
  1650     /// The type of the adapted digraph.
  1746 #else
  1746 #else
  1747   template<typename GR,
  1747   template<typename GR,
  1748            typename EF = typename GR::template EdgeMap<bool> >
  1748            typename EF = typename GR::template EdgeMap<bool> >
  1749   class FilterEdges :
  1749   class FilterEdges :
  1750     public GraphAdaptorExtender<
  1750     public GraphAdaptorExtender<
  1751       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
  1751       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
  1752                    EF, false> > {
  1752                    EF, false> > {
  1753 #endif
  1753 #endif
  1754     typedef GraphAdaptorExtender<
  1754     typedef GraphAdaptorExtender<
  1755       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
  1755       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
  1756                    EF, false> > Parent;
  1756                    EF, false> > Parent;
  1757 
  1757 
  1758   public:
  1758   public:
  1759 
  1759 
  1760     /// The type of the adapted graph.
  1760     /// The type of the adapted graph.
  1775 
  1775 
  1776     /// \brief Constructor
  1776     /// \brief Constructor
  1777     ///
  1777     ///
  1778     /// Creates a subgraph for the given graph with the given edge
  1778     /// Creates a subgraph for the given graph with the given edge
  1779     /// filter map.
  1779     /// filter map.
  1780     FilterEdges(GR& graph, EF& edge_filter) 
  1780     FilterEdges(GR& graph, EF& edge_filter)
  1781       : Parent(), const_true_map() {
  1781       : Parent(), const_true_map() {
  1782       Parent::initialize(graph, const_true_map, edge_filter);
  1782       Parent::initialize(graph, const_true_map, edge_filter);
  1783     }
  1783     }
  1784 
  1784 
  1785     /// \brief Sets the status of the given edge
  1785     /// \brief Sets the status of the given edge
  1843       friend class UndirectorBase;
  1843       friend class UndirectorBase;
  1844     protected:
  1844     protected:
  1845       Edge _edge;
  1845       Edge _edge;
  1846       bool _forward;
  1846       bool _forward;
  1847 
  1847 
  1848       Arc(const Edge& edge, bool forward) 
  1848       Arc(const Edge& edge, bool forward)
  1849         : _edge(edge), _forward(forward) {}
  1849         : _edge(edge), _forward(forward) {}
  1850 
  1850 
  1851     public:
  1851     public:
  1852       Arc() {}
  1852       Arc() {}
  1853 
  1853 
  2083 
  2083 
  2084       ArcMapBase(const UndirectorBase<DGR>& adaptor) :
  2084       ArcMapBase(const UndirectorBase<DGR>& adaptor) :
  2085         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
  2085         _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
  2086 
  2086 
  2087       ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
  2087       ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
  2088         : _forward(*adaptor._digraph, value), 
  2088         : _forward(*adaptor._digraph, value),
  2089           _backward(*adaptor._digraph, value) {}
  2089           _backward(*adaptor._digraph, value) {}
  2090 
  2090 
  2091       void set(const Arc& a, const V& value) {
  2091       void set(const Arc& a, const V& value) {
  2092         if (direction(a)) {
  2092         if (direction(a)) {
  2093           _forward.set(a, value);
  2093           _forward.set(a, value);
  2201     typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
  2201     typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
  2202     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
  2202     NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
  2203 
  2203 
  2204     typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
  2204     typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
  2205     EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
  2205     EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
  2206     
  2206 
  2207     typedef EdgeNotifier ArcNotifier;
  2207     typedef EdgeNotifier ArcNotifier;
  2208     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
  2208     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
  2209 
  2209 
  2210   protected:
  2210   protected:
  2211 
  2211 
  2705 #else
  2705 #else
  2706   template<typename DGR,
  2706   template<typename DGR,
  2707            typename CM = typename DGR::template ArcMap<int>,
  2707            typename CM = typename DGR::template ArcMap<int>,
  2708            typename FM = CM,
  2708            typename FM = CM,
  2709            typename TL = Tolerance<typename CM::Value> >
  2709            typename TL = Tolerance<typename CM::Value> >
  2710   class ResidualDigraph 
  2710   class ResidualDigraph
  2711     : public SubDigraph<
  2711     : public SubDigraph<
  2712         Undirector<const DGR>,
  2712         Undirector<const DGR>,
  2713         ConstMap<typename DGR::Node, Const<bool, true> >,
  2713         ConstMap<typename DGR::Node, Const<bool, true> >,
  2714         typename Undirector<const DGR>::template CombinedArcMap<
  2714         typename Undirector<const DGR>::template CombinedArcMap<
  2715           _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
  2715           _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
  2762     ///
  2762     ///
  2763     /// Constructor of the residual digraph adaptor. The parameters are the
  2763     /// Constructor of the residual digraph adaptor. The parameters are the
  2764     /// digraph, the capacity map, the flow map, and a tolerance object.
  2764     /// digraph, the capacity map, the flow map, and a tolerance object.
  2765     ResidualDigraph(const DGR& digraph, const CM& capacity,
  2765     ResidualDigraph(const DGR& digraph, const CM& capacity,
  2766                     FM& flow, const TL& tolerance = Tolerance())
  2766                     FM& flow, const TL& tolerance = Tolerance())
  2767       : Parent(), _capacity(&capacity), _flow(&flow), 
  2767       : Parent(), _capacity(&capacity), _flow(&flow),
  2768         _graph(digraph), _node_filter(),
  2768         _graph(digraph), _node_filter(),
  2769         _forward_filter(capacity, flow, tolerance),
  2769         _forward_filter(capacity, flow, tolerance),
  2770         _backward_filter(capacity, flow, tolerance),
  2770         _backward_filter(capacity, flow, tolerance),
  2771         _arc_filter(_forward_filter, _backward_filter)
  2771         _arc_filter(_forward_filter, _backward_filter)
  2772     {
  2772     {
  2844       typedef Arc Key;
  2844       typedef Arc Key;
  2845       /// The value type of the map
  2845       /// The value type of the map
  2846       typedef typename CapacityMap::Value Value;
  2846       typedef typename CapacityMap::Value Value;
  2847 
  2847 
  2848       /// Constructor
  2848       /// Constructor
  2849       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
  2849       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
  2850         : _adaptor(&adaptor) {}
  2850         : _adaptor(&adaptor) {}
  2851 
  2851 
  2852       /// Returns the value associated with the given residual arc
  2852       /// Returns the value associated with the given residual arc
  2853       Value operator[](const Arc& a) const {
  2853       Value operator[](const Arc& a) const {
  2854         return _adaptor->residualCapacity(a);
  2854         return _adaptor->residualCapacity(a);
  3421     /// \brief Node map combined from two original node maps
  3421     /// \brief Node map combined from two original node maps
  3422     ///
  3422     ///
  3423     /// This map adaptor class adapts two node maps of the original digraph
  3423     /// This map adaptor class adapts two node maps of the original digraph
  3424     /// to get a node map of the split digraph.
  3424     /// to get a node map of the split digraph.
  3425     /// Its value type is inherited from the first node map type (\c IN).
  3425     /// Its value type is inherited from the first node map type (\c IN).
  3426     /// \tparam IN The type of the node map for the in-nodes. 
  3426     /// \tparam IN The type of the node map for the in-nodes.
  3427     /// \tparam OUT The type of the node map for the out-nodes.
  3427     /// \tparam OUT The type of the node map for the out-nodes.
  3428     template <typename IN, typename OUT>
  3428     template <typename IN, typename OUT>
  3429     class CombinedNodeMap {
  3429     class CombinedNodeMap {
  3430     public:
  3430     public:
  3431 
  3431