alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@1401: #ifndef LEMON_GRAPH_ADAPTOR_H
alpar@1401: #define LEMON_GRAPH_ADAPTOR_H
marci@556: 
deba@2037: ///\ingroup graph_adaptors
deba@2037: ///\file
deba@2037: ///\brief Several graph adaptors.
marci@556: ///
deba@2037: ///This file contains several useful graph adaptor functions.
marci@556: ///
deba@2037: ///\author Marton Makai and Balazs Dezso
marci@556: 
deba@1993: #include <lemon/bits/invalid.h>
deba@2177: #include <lemon/bits/variant.h>
alpar@921: #include <lemon/maps.h>
deba@1979: 
deba@1999: #include <lemon/bits/base_extender.h>
deba@1979: #include <lemon/bits/graph_adaptor_extender.h>
deba@1791: #include <lemon/bits/graph_extender.h>
deba@1979: 
deba@2034: #include <lemon/tolerance.h>
deba@2034: 
deba@2079: #include <algorithm>
marci@556: 
alpar@921: namespace lemon {
marci@556: 
klao@1951:   ///\brief Base type for the Graph Adaptors
klao@1951:   ///
klao@1951:   ///Base type for the Graph Adaptors
klao@1951:   ///
klao@1951:   ///This is the base type for most of LEMON graph adaptors. 
klao@1951:   ///This class implements a trivial graph adaptor i.e. it only wraps the 
klao@1951:   ///functions and types of the graph. The purpose of this class is to 
klao@1951:   ///make easier implementing graph adaptors. E.g. if an adaptor is 
klao@1951:   ///considered which differs from the wrapped graph only in some of its 
klao@1951:   ///functions or types, then it can be derived from GraphAdaptor,
klao@1951:   ///and only the 
klao@1951:   ///differences should be implemented.
klao@1951:   ///
klao@1951:   ///author Marton Makai 
marci@970:   template<typename _Graph>
alpar@1401:   class GraphAdaptorBase {
marci@970:   public:
marci@970:     typedef _Graph Graph;
deba@2031:     typedef GraphAdaptorBase Adaptor;
marci@970:     typedef Graph ParentGraph;
marci@970: 
marci@556:   protected:
marci@556:     Graph* graph;
alpar@1401:     GraphAdaptorBase() : graph(0) { }
marci@556:     void setGraph(Graph& _graph) { graph=&_graph; }
marci@556: 
marci@556:   public:
alpar@1401:     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
deba@2034: 
alpar@774:     typedef typename Graph::Node Node;
alpar@774:     typedef typename Graph::Edge Edge;
marci@556:    
marci@970:     void first(Node& i) const { graph->first(i); }
marci@970:     void first(Edge& i) const { graph->first(i); }
marci@970:     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
marci@970:     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
marci@556: 
marci@970:     void next(Node& i) const { graph->next(i); }
marci@970:     void next(Edge& i) const { graph->next(i); }
marci@970:     void nextIn(Edge& i) const { graph->nextIn(i); }
marci@970:     void nextOut(Edge& i) const { graph->nextOut(i); }
marci@970: 
alpar@986:     Node source(const Edge& e) const { return graph->source(e); }
alpar@986:     Node target(const Edge& e) const { return graph->target(e); }
marci@556: 
deba@1697:     typedef NodeNumTagIndicator<Graph> NodeNumTag;
marci@556:     int nodeNum() const { return graph->nodeNum(); }
deba@1697:     
deba@1697:     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
marci@556:     int edgeNum() const { return graph->edgeNum(); }
deba@1697: 
deba@1697:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1697:     Edge findEdge(const Node& source, const Node& target, 
deba@1697: 		  const Edge& prev = INVALID) {
deba@1697:       return graph->findEdge(source, target, prev);
deba@1697:     }
marci@556:   
deba@1697:     Node addNode() const { 
deba@1697:       return Node(graph->addNode()); 
deba@1697:     }
deba@1697: 
alpar@986:     Edge addEdge(const Node& source, const Node& target) const { 
deba@1697:       return Edge(graph->addEdge(source, target)); 
deba@1697:     }
marci@556: 
marci@556:     void erase(const Node& i) const { graph->erase(i); }
marci@556:     void erase(const Edge& i) const { graph->erase(i); }
marci@556:   
marci@556:     void clear() const { graph->clear(); }
marci@556:     
marci@739:     int id(const Node& v) const { return graph->id(v); }
marci@739:     int id(const Edge& e) const { return graph->id(e); }
deba@1991: 
deba@2031:     Node fromNodeId(int id) const {
deba@2031:       return graph->fromNodeId(id);
deba@2031:     }
deba@2031: 
deba@2031:     Edge fromEdgeId(int id) const {
deba@2031:       return graph->fromEdgeId(id);
deba@2031:     }
deba@2031: 
deba@1991:     int maxNodeId() const {
deba@1991:       return graph->maxNodeId();
deba@1991:     }
deba@1991: 
deba@1991:     int maxEdgeId() const {
deba@1991:       return graph->maxEdgeId();
deba@1991:     }
deba@1991: 
deba@1991:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@1991: 
deba@1991:     NodeNotifier& getNotifier(Node) const {
deba@1991:       return graph->getNotifier(Node());
deba@1991:     } 
deba@1991: 
deba@1991:     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@1991: 
deba@1991:     EdgeNotifier& getNotifier(Edge) const {
deba@1991:       return graph->getNotifier(Edge());
deba@1991:     } 
marci@650:     
marci@970:     template <typename _Value>
deba@2031:     class NodeMap : public Graph::template NodeMap<_Value> {
marci@970:     public:
deba@2031: 
deba@2031:       typedef typename Graph::template NodeMap<_Value> Parent;
deba@2031: 
deba@2031:       explicit NodeMap(const Adaptor& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031: 
deba@2031:       NodeMap(const Adaptor& ga, const _Value& value)
deba@1991: 	: Parent(*ga.graph, value) { }
deba@2031: 
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031:         return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@2031:       }
deba@2031:       
marci@970:     };
marci@556: 
marci@970:     template <typename _Value>
deba@2031:     class EdgeMap : public Graph::template EdgeMap<_Value> {
marci@970:     public:
deba@2031:       
deba@2031:       typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031:       
deba@2031:       explicit EdgeMap(const Adaptor& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@2031: 
deba@2031:       EdgeMap(const Adaptor& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@2031: 
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031:         return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@2031:       }
deba@2031: 
marci@970:     };
deba@877: 
marci@556:   };
marci@556: 
deba@2081:   ///\ingroup graph_adaptors
deba@2081:   ///
deba@2081:   ///\brief Trivial Graph Adaptor
deba@2081:   /// 
deba@2081:   /// This class is an adaptor which does not change the adapted graph.
deba@2081:   /// It can be used only to test the graph adaptors.
marci@970:   template <typename _Graph>
alpar@1401:   class GraphAdaptor :
deba@1979:     public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > { 
marci@970:   public:
marci@970:     typedef _Graph Graph;
deba@1979:     typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
marci@970:   protected:
alpar@1401:     GraphAdaptor() : Parent() { }
marci@569: 
marci@970:   public:
deba@1755:     explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
marci@970:   };
marci@569: 
deba@1991:   /// \brief Just gives back a graph adaptor
deba@1991:   ///
deba@1991:   /// Just gives back a graph adaptor which 
deba@1991:   /// should be provide original graph
deba@1991:   template<typename Graph>
deba@1991:   GraphAdaptor<const Graph>
deba@1991:   graphAdaptor(const Graph& graph) {
deba@1991:     return GraphAdaptor<const Graph>(graph);
deba@1991:   }
deba@1991: 
deba@1991: 
marci@997:   template <typename _Graph>
alpar@1401:   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@997:   public:
marci@997:     typedef _Graph Graph;
alpar@1401:     typedef GraphAdaptorBase<_Graph> Parent;
marci@997:   protected:
alpar@1401:     RevGraphAdaptorBase() : Parent() { }
marci@997:   public:
marci@997:     typedef typename Parent::Node Node;
marci@997:     typedef typename Parent::Edge Edge;
marci@997: 
marci@997:     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
marci@997:     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
marci@997: 
marci@997:     void nextIn(Edge& i) const { Parent::nextOut(i); }
marci@997:     void nextOut(Edge& i) const { Parent::nextIn(i); }
marci@997: 
marci@997:     Node source(const Edge& e) const { return Parent::target(e); }
marci@997:     Node target(const Edge& e) const { return Parent::source(e); }
deba@1991: 
deba@1991:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991:     Edge findEdge(const Node& source, const Node& target, 
deba@1991: 		  const Edge& prev = INVALID) {
deba@1991:       return Parent::findEdge(target, source, prev);
deba@1991:     }
deba@1991: 
marci@997:   };
marci@997:     
marci@997: 
deba@2081:   ///\ingroup graph_adaptors
deba@2081:   ///
alpar@1949:   ///\brief A graph adaptor which reverses the orientation of the edges.
alpar@1949:   ///
alpar@1949:   /// If \c g is defined as
alpar@1946:   ///\code
marci@923:   /// ListGraph g;
alpar@1946:   ///\endcode
alpar@1949:   /// then
alpar@1946:   ///\code
deba@1991:   /// RevGraphAdaptor<ListGraph> ga(g);
alpar@1946:   ///\endcode
deba@2079:   /// implements the graph obtained from \c g by 
alpar@1949:   /// reversing the orientation of its edges.
deba@2084:   ///
deba@2084:   /// A good example of using RevGraphAdaptor is to decide that the
deba@2084:   /// directed graph is wheter strongly connected or not. If from one
deba@2084:   /// node each node is reachable and from each node is reachable this
deba@2084:   /// node then and just then the graph is strongly connected. Instead of
deba@2084:   /// this condition we use a little bit different. From one node each node
deba@2084:   /// ahould be reachable in the graph and in the reversed graph. Now this
deba@2084:   /// condition can be checked with the Dfs algorithm class and the
deba@2084:   /// RevGraphAdaptor algorithm class.
deba@2084:   ///
deba@2084:   /// And look at the code:
deba@2084:   ///
deba@2084:   ///\code
deba@2084:   /// bool stronglyConnected(const Graph& graph) {
deba@2084:   ///   if (NodeIt(graph) == INVALID) return true;
deba@2084:   ///   Dfs<Graph> dfs(graph);
deba@2084:   ///   dfs.run(NodeIt(graph));
deba@2084:   ///   for (NodeIt it(graph); it != INVALID; ++it) {
deba@2084:   ///     if (!dfs.reached(it)) {
deba@2084:   ///       return false;
deba@2084:   ///     }
deba@2084:   ///   }
deba@2084:   ///   typedef RevGraphAdaptor<const Graph> RGraph;
deba@2084:   ///   RGraph rgraph(graph);
deba@2084:   ///   DfsVisit<RGraph> rdfs(rgraph);
deba@2084:   ///   rdfs.run(NodeIt(graph));
deba@2084:   ///   for (NodeIt it(graph); it != INVALID; ++it) {
deba@2084:   ///     if (!rdfs.reached(it)) {
deba@2084:   ///       return false;
deba@2084:   ///     }
deba@2084:   ///   }
deba@2084:   ///   return true;
deba@2084:   /// }
deba@2084:   ///\endcode
marci@997:   template<typename _Graph>
alpar@1401:   class RevGraphAdaptor : 
deba@1979:     public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
marci@650:   public:
marci@997:     typedef _Graph Graph;
deba@1979:     typedef GraphAdaptorExtender<
alpar@1401:       RevGraphAdaptorBase<_Graph> > Parent;
marci@556:   protected:
alpar@1401:     RevGraphAdaptor() { }
marci@556:   public:
deba@1755:     explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
marci@997:   };
marci@556: 
deba@1991:   /// \brief Just gives back a reverse graph adaptor
deba@1991:   ///
deba@1991:   /// Just gives back a reverse graph adaptor
deba@1991:   template<typename Graph>
deba@1991:   RevGraphAdaptor<const Graph>
deba@1991:   revGraphAdaptor(const Graph& graph) {
deba@1991:     return RevGraphAdaptor<const Graph>(graph);
deba@1991:   }
deba@1991: 
deba@1681:   template <typename _Graph, typename NodeFilterMap, 
deba@1681: 	    typename EdgeFilterMap, bool checked = true>
alpar@1401:   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992:   public:
marci@992:     typedef _Graph Graph;
deba@2031:     typedef SubGraphAdaptorBase Adaptor;
alpar@1401:     typedef GraphAdaptorBase<_Graph> Parent;
marci@992:   protected:
marci@992:     NodeFilterMap* node_filter_map;
marci@992:     EdgeFilterMap* edge_filter_map;
alpar@1401:     SubGraphAdaptorBase() : Parent(), 
marci@992: 			    node_filter_map(0), edge_filter_map(0) { }
marci@775: 
marci@992:     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@992:       node_filter_map=&_node_filter_map;
marci@992:     }
marci@992:     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@992:       edge_filter_map=&_edge_filter_map;
marci@992:     }
marci@992: 
marci@992:   public:
marci@992: 
marci@992:     typedef typename Parent::Node Node;
marci@992:     typedef typename Parent::Edge Edge;
marci@992: 
marci@992:     void first(Node& i) const { 
marci@992:       Parent::first(i); 
marci@992:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
marci@992:     }
deba@1681: 
deba@1681:     void first(Edge& i) const { 
deba@1681:       Parent::first(i); 
deba@1681:       while (i!=INVALID && (!(*edge_filter_map)[i] 
deba@1681: 	     || !(*node_filter_map)[Parent::source(i)]
deba@1681: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@1681:     }
deba@1681: 
deba@1681:     void firstIn(Edge& i, const Node& n) const { 
deba@1681:       Parent::firstIn(i, n); 
deba@1681:       while (i!=INVALID && (!(*edge_filter_map)[i] 
deba@1681: 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
deba@1681:     }
deba@1681: 
deba@1681:     void firstOut(Edge& i, const Node& n) const { 
deba@1681:       Parent::firstOut(i, n); 
deba@1681:       while (i!=INVALID && (!(*edge_filter_map)[i] 
deba@1681: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
deba@1681:     }
deba@1681: 
deba@1681:     void next(Node& i) const { 
deba@1681:       Parent::next(i); 
deba@1681:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
deba@1681:     }
deba@1681: 
deba@1681:     void next(Edge& i) const { 
deba@1681:       Parent::next(i); 
deba@1681:       while (i!=INVALID && (!(*edge_filter_map)[i] 
deba@1681: 	     || !(*node_filter_map)[Parent::source(i)]
deba@1681: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
deba@1681:     }
deba@1681: 
deba@1681:     void nextIn(Edge& i) const { 
deba@1681:       Parent::nextIn(i); 
deba@1681:       while (i!=INVALID && (!(*edge_filter_map)[i] 
deba@1681: 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
deba@1681:     }
deba@1681: 
deba@1681:     void nextOut(Edge& i) const { 
deba@1681:       Parent::nextOut(i); 
deba@1681:       while (i!=INVALID && (!(*edge_filter_map)[i] 
deba@1681: 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
deba@1681:     }
deba@1681: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// This function hides \c n in the graph, i.e. the iteration 
klao@1951:     /// jumps over it. This is done by simply setting the value of \c n  
klao@1951:     /// to be false in the corresponding node-map.
deba@1681:     void hide(const Node& n) const { node_filter_map->set(n, false); }
deba@1681: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// This function hides \c e in the graph, i.e. the iteration 
klao@1951:     /// jumps over it. This is done by simply setting the value of \c e  
klao@1951:     /// to be false in the corresponding edge-map.
deba@1681:     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
deba@1681: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// The value of \c n is set to be true in the node-map which stores 
klao@1951:     /// hide information. If \c n was hidden previuosly, then it is shown 
klao@1951:     /// again
deba@1681:      void unHide(const Node& n) const { node_filter_map->set(n, true); }
deba@1681: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// The value of \c e is set to be true in the edge-map which stores 
klao@1951:     /// hide information. If \c e was hidden previuosly, then it is shown 
klao@1951:     /// again
deba@1681:     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
deba@1681: 
klao@1951:     /// Returns true if \c n is hidden.
alpar@1949:     
klao@1951:     ///\e
klao@1951:     ///
deba@1681:     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1681: 
klao@1951:     /// Returns true if \c n is hidden.
alpar@1949:     
klao@1951:     ///\e
klao@1951:     ///
deba@1681:     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
deba@1681: 
deba@1697:     typedef False NodeNumTag;
deba@1697:     typedef False EdgeNumTag;
deba@1991: 
deba@1991:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991:     Edge findEdge(const Node& source, const Node& target, 
deba@1991: 		  const Edge& prev = INVALID) {
deba@1991:       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
deba@1991:         return INVALID;
deba@1991:       }
deba@1991:       Edge edge = Parent::findEdge(source, target, prev);
deba@1991:       while (edge != INVALID && !(*edge_filter_map)[edge]) {
deba@1991:         edge = Parent::findEdge(source, target, edge);
deba@1991:       }
deba@1991:       return edge;
deba@1991:     }
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class NodeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template NodeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template NodeMap<_Value> > Parent;
deba@2031:     
deba@2031:       NodeMap(const Graph& graph) 
deba@2031: 	: Parent(graph) {}
deba@2031:       NodeMap(const Graph& graph, const _Value& value) 
deba@2031: 	: Parent(graph, value) {}
deba@2031:     
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031: 	return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class EdgeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template EdgeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template EdgeMap<_Value> > Parent;
deba@2031:     
deba@2031:       EdgeMap(const Graph& graph) 
deba@2031: 	: Parent(graph) {}
deba@2031:       EdgeMap(const Graph& graph, const _Value& value) 
deba@2031: 	: Parent(graph, value) {}
deba@2031:     
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031: 	return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@1681:   };
deba@1681: 
deba@1681:   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1681:   class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 
deba@1681:     : public GraphAdaptorBase<_Graph> {
deba@1681:   public:
deba@1681:     typedef _Graph Graph;
deba@2031:     typedef SubGraphAdaptorBase Adaptor;
deba@1681:     typedef GraphAdaptorBase<_Graph> Parent;
deba@1681:   protected:
deba@1681:     NodeFilterMap* node_filter_map;
deba@1681:     EdgeFilterMap* edge_filter_map;
deba@1681:     SubGraphAdaptorBase() : Parent(), 
deba@1681: 			    node_filter_map(0), edge_filter_map(0) { }
deba@1681: 
deba@1681:     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
deba@1681:       node_filter_map=&_node_filter_map;
deba@1681:     }
deba@1681:     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
deba@1681:       edge_filter_map=&_edge_filter_map;
deba@1681:     }
deba@1681: 
deba@1681:   public:
deba@1681: 
deba@1681:     typedef typename Parent::Node Node;
deba@1681:     typedef typename Parent::Edge Edge;
deba@1681: 
deba@1681:     void first(Node& i) const { 
deba@1681:       Parent::first(i); 
deba@1681:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
deba@1681:     }
deba@1681: 
marci@992:     void first(Edge& i) const { 
marci@992:       Parent::first(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
marci@992:     }
deba@1681: 
marci@992:     void firstIn(Edge& i, const Node& n) const { 
marci@992:       Parent::firstIn(i, n); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
marci@992:     }
deba@1681: 
marci@992:     void firstOut(Edge& i, const Node& n) const { 
marci@992:       Parent::firstOut(i, n); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
marci@992:     }
marci@992: 
marci@992:     void next(Node& i) const { 
marci@992:       Parent::next(i); 
marci@992:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
marci@992:     }
marci@992:     void next(Edge& i) const { 
marci@992:       Parent::next(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
marci@992:     }
marci@992:     void nextIn(Edge& i) const { 
marci@992:       Parent::nextIn(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
marci@992:     }
deba@1681: 
marci@992:     void nextOut(Edge& i) const { 
marci@992:       Parent::nextOut(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
marci@992:     }
marci@992: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// This function hides \c n in the graph, i.e. the iteration 
klao@1951:     /// jumps over it. This is done by simply setting the value of \c n  
klao@1951:     /// to be false in the corresponding node-map.
marci@992:     void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@992: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// This function hides \c e in the graph, i.e. the iteration 
klao@1951:     /// jumps over it. This is done by simply setting the value of \c e  
klao@1951:     /// to be false in the corresponding edge-map.
marci@992:     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@992: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// The value of \c n is set to be true in the node-map which stores 
klao@1951:     /// hide information. If \c n was hidden previuosly, then it is shown 
klao@1951:     /// again
marci@992:      void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@992: 
klao@1951:     ///\e
alpar@1949: 
klao@1951:     /// The value of \c e is set to be true in the edge-map which stores 
klao@1951:     /// hide information. If \c e was hidden previuosly, then it is shown 
klao@1951:     /// again
marci@992:     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@992: 
klao@1951:     /// Returns true if \c n is hidden.
alpar@1949:     
klao@1951:     ///\e
klao@1951:     ///
marci@992:     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@992: 
klao@1951:     /// Returns true if \c n is hidden.
alpar@1949:     
klao@1951:     ///\e
klao@1951:     ///
marci@992:     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@992: 
deba@1697:     typedef False NodeNumTag;
deba@1697:     typedef False EdgeNumTag;
deba@1991: 
deba@1991:     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
deba@1991:     Edge findEdge(const Node& source, const Node& target, 
deba@1991: 		  const Edge& prev = INVALID) {
deba@1991:       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
deba@1991:         return INVALID;
deba@1991:       }
deba@1991:       Edge edge = Parent::findEdge(source, target, prev);
deba@1991:       while (edge != INVALID && !(*edge_filter_map)[edge]) {
deba@1991:         edge = Parent::findEdge(source, target, edge);
deba@1991:       }
deba@1991:       return edge;
deba@1991:     }
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class NodeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template NodeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template NodeMap<_Value> > Parent;
deba@2031:     
deba@2031:       NodeMap(const Graph& graph) 
deba@2031: 	: Parent(graph) {}
deba@2031:       NodeMap(const Graph& graph, const _Value& value) 
deba@2031: 	: Parent(graph, value) {}
deba@2031:     
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031: 	return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class EdgeMap 
deba@2031:       : public SubMapExtender<Adaptor, 
deba@2031:                               typename Parent::template EdgeMap<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, typename Parent::
deba@2031:                              template EdgeMap<_Value> > Parent;
deba@2031:     
deba@2031:       EdgeMap(const Graph& graph) 
deba@2031: 	: Parent(graph) {}
deba@2031:       EdgeMap(const Graph& graph, const _Value& value) 
deba@2031: 	: Parent(graph, value) {}
deba@2031:     
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031: 	return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
deba@2031: 
marci@992:   };
marci@775: 
deba@2081:   /// \ingroup graph_adaptors
deba@2081:   ///
klao@1951:   /// \brief A graph adaptor for hiding nodes and edges from a graph.
klao@1951:   /// 
klao@1951:   /// SubGraphAdaptor shows the graph with filtered node-set and 
klao@1951:   /// edge-set. If the \c checked parameter is true then it filters the edgeset
klao@1951:   /// to do not get invalid edges without source or target.
klao@1952:   /// Let \f$ G=(V, A) \f$ be a directed graph
klao@1951:   /// and suppose that the graph instance \c g of type ListGraph
klao@1952:   /// implements \f$ G \f$.
klao@1952:   /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
klao@1951:   /// on the node-set and edge-set.
klao@1951:   /// SubGraphAdaptor<...>::NodeIt iterates 
klao@1952:   /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and 
klao@1951:   /// SubGraphAdaptor<...>::EdgeIt iterates 
klao@1952:   /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly, 
klao@1951:   /// SubGraphAdaptor<...>::OutEdgeIt and
klao@1951:   /// SubGraphAdaptor<...>::InEdgeIt iterates 
klao@1951:   /// only on edges leaving and entering a specific node which have true value.
klao@1951:   /// 
klao@1951:   /// If the \c checked template parameter is false then we have to note that 
klao@1951:   /// the node-iterator cares only the filter on the node-set, and the 
klao@1951:   /// edge-iterator cares only the filter on the edge-set.
klao@1951:   /// This way the edge-map
klao@1951:   /// should filter all edges which's source or target is filtered by the 
klao@1951:   /// node-filter.
alpar@1957:   ///\code
klao@1951:   /// typedef ListGraph Graph;
klao@1951:   /// Graph g;
klao@1951:   /// typedef Graph::Node Node;
klao@1951:   /// typedef Graph::Edge Edge;
klao@1951:   /// Node u=g.addNode(); //node of id 0
klao@1951:   /// Node v=g.addNode(); //node of id 1
klao@1951:   /// Node e=g.addEdge(u, v); //edge of id 0
klao@1951:   /// Node f=g.addEdge(v, u); //edge of id 1
klao@1951:   /// Graph::NodeMap<bool> nm(g, true);
klao@1951:   /// nm.set(u, false);
klao@1951:   /// Graph::EdgeMap<bool> em(g, true);
klao@1951:   /// em.set(e, false);
deba@1991:   /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
deba@1991:   /// SubGA ga(g, nm, em);
deba@1991:   /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
klao@1951:   /// std::cout << ":-)" << std::endl;
deba@1991:   /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
alpar@1957:   ///\endcode
klao@1951:   /// The output of the above code is the following.
alpar@1957:   ///\code
klao@1951:   /// 1
klao@1951:   /// :-)
klao@1951:   /// 1
alpar@1957:   ///\endcode
deba@1991:   /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
klao@1951:   /// \c Graph::Node that is why \c g.id(n) can be applied.
klao@1951:   /// 
klao@1951:   /// For other examples see also the documentation of NodeSubGraphAdaptor and 
klao@1951:   /// EdgeSubGraphAdaptor.
klao@1951:   /// 
klao@1951:   /// \author Marton Makai
marci@1242: 
marci@992:   template<typename _Graph, typename NodeFilterMap, 
deba@1681: 	   typename EdgeFilterMap, bool checked = true>
alpar@1401:   class SubGraphAdaptor : 
deba@1979:     public GraphAdaptorExtender<
deba@1681:     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
marci@650:   public:
marci@992:     typedef _Graph Graph;
deba@2031:     typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap, 
deba@2031:                                                       EdgeFilterMap, checked> >
deba@2031:     Parent;
deba@2031: 
marci@556:   protected:
alpar@1401:     SubGraphAdaptor() { }
marci@992:   public:
deba@2031: 
alpar@1401:     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, 
marci@992: 		    EdgeFilterMap& _edge_filter_map) { 
marci@992:       setGraph(_graph);
marci@992:       setNodeFilterMap(_node_filter_map);
marci@992:       setEdgeFilterMap(_edge_filter_map);
marci@992:     }
deba@2031: 
marci@992:   };
marci@556: 
deba@1991:   /// \brief Just gives back a sub graph adaptor
deba@1991:   ///
deba@1991:   /// Just gives back a sub graph adaptor
deba@1991:   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991:   SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
deba@1991:   subGraphAdaptor(const Graph& graph, 
deba@1991:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991:     return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
deba@1991:       (graph, nfm, efm);
deba@1991:   }
deba@1991: 
deba@1991:   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991:   SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
deba@1991:   subGraphAdaptor(const Graph& graph, 
deba@1991:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991:     return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
deba@1991:       (graph, nfm, efm);
deba@1991:   }
deba@1991: 
deba@1991:   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991:   SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
deba@1991:   subGraphAdaptor(const Graph& graph, 
deba@1991:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991:     return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
deba@1991:       (graph, nfm, efm);
deba@1991:   }
deba@1991: 
deba@1991:   template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1991:   SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
deba@1991:   subGraphAdaptor(const Graph& graph, 
deba@1991:                    NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1991:     return SubGraphAdaptor<const Graph, const NodeFilterMap, 
deba@1991:       const EdgeFilterMap>(graph, nfm, efm);
deba@1991:   }
deba@1991: 
marci@556: 
marci@569: 
deba@2081:   ///\ingroup graph_adaptors
deba@2081:   ///
klao@1951:   ///\brief An adaptor for hiding nodes from a graph.
klao@1951:   ///
klao@1951:   ///An adaptor for hiding nodes from a graph.
klao@1951:   ///This adaptor specializes SubGraphAdaptor in the way that only
klao@1951:   ///the node-set 
klao@1951:   ///can be filtered. In usual case the checked parameter is true, we get the
klao@1951:   ///induced subgraph. But if the checked parameter is false then we can only
klao@1951:   ///filter only isolated nodes.
klao@1951:   ///\author Marton Makai
deba@1681:   template<typename Graph, typename NodeFilterMap, bool checked = true>
alpar@1401:   class NodeSubGraphAdaptor : 
alpar@1401:     public SubGraphAdaptor<Graph, NodeFilterMap, 
deba@1681: 			   ConstMap<typename Graph::Edge,bool>, checked> {
marci@933:   public:
deba@2031: 
alpar@1401:     typedef SubGraphAdaptor<Graph, NodeFilterMap, 
deba@2031: 			    ConstMap<typename Graph::Edge,bool>, checked > 
deba@2031:     Parent;
deba@2031: 
marci@933:   protected:
marci@933:     ConstMap<typename Graph::Edge, bool> const_true_map;
deba@1991: 
deba@1991:     NodeSubGraphAdaptor() : const_true_map(true) {
deba@1991:       Parent::setEdgeFilterMap(const_true_map);
deba@1991:     }
deba@1991: 
marci@933:   public:
deba@2031: 
alpar@1401:     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
marci@933:       Parent(), const_true_map(true) { 
marci@933:       Parent::setGraph(_graph);
marci@933:       Parent::setNodeFilterMap(_node_filter_map);
marci@933:       Parent::setEdgeFilterMap(const_true_map);
marci@933:     }
deba@2031: 
marci@933:   };
marci@933: 
marci@933: 
deba@1991:   /// \brief Just gives back a node sub graph adaptor
deba@1991:   ///
deba@1991:   /// Just gives back a node sub graph adaptor
deba@1991:   template<typename Graph, typename NodeFilterMap>
deba@1991:   NodeSubGraphAdaptor<const Graph, NodeFilterMap>
deba@1991:   nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
deba@1991:     return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
deba@1991:   }
deba@1991: 
deba@1991:   template<typename Graph, typename NodeFilterMap>
deba@1991:   NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
deba@1991:   nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
deba@1991:     return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
deba@1991:   }
deba@1991: 
deba@2081:   ///\ingroup graph_adaptors
deba@2081:   ///
klao@1951:   ///\brief An adaptor for hiding edges from a graph.
klao@1951:   ///
klao@1951:   ///An adaptor for hiding edges from a graph.
klao@1951:   ///This adaptor specializes SubGraphAdaptor in the way that
klao@1951:   ///only the edge-set 
klao@1951:   ///can be filtered. The usefulness of this adaptor is demonstrated in the 
klao@1951:   ///problem of searching a maximum number of edge-disjoint shortest paths 
klao@1951:   ///between 
klao@1951:   ///two nodes \c s and \c t. Shortest here means being shortest w.r.t. 
klao@1951:   ///non-negative edge-lengths. Note that 
klao@1951:   ///the comprehension of the presented solution 
klao@1951:   ///need's some elementary knowledge from combinatorial optimization. 
klao@1951:   ///
klao@1951:   ///If a single shortest path is to be 
klao@1951:   ///searched between \c s and \c t, then this can be done easily by 
klao@1951:   ///applying the Dijkstra algorithm. What happens, if a maximum number of 
klao@1951:   ///edge-disjoint shortest paths is to be computed. It can be proved that an 
klao@1951:   ///edge can be in a shortest path if and only
klao@1951:   ///if it is tight with respect to 
klao@1951:   ///the potential function computed by Dijkstra.
klao@1951:   ///Moreover, any path containing 
klao@1951:   ///only such edges is a shortest one.
klao@1951:   ///Thus we have to compute a maximum number 
klao@1951:   ///of edge-disjoint paths between \c s and \c t in
klao@1951:   ///the graph which has edge-set 
klao@1951:   ///all the tight edges. The computation will be demonstrated
klao@1951:   ///on the following 
klao@1951:   ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 
klao@1951:   ///The full source code is available in \ref sub_graph_adaptor_demo.cc. 
klao@1951:   ///If you are interested in more demo programs, you can use 
klao@1951:   ///\ref dim_to_dot.cc to generate .dot files from dimacs files. 
klao@1951:   ///The .dot file of the following figure was generated by  
klao@1951:   ///the demo program \ref dim_to_dot.cc.
klao@1951:   ///
klao@1951:   ///\dot
klao@1951:   ///digraph lemon_dot_example {
klao@1951:   ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
klao@1951:   ///n0 [ label="0 (s)" ];
klao@1951:   ///n1 [ label="1" ];
klao@1951:   ///n2 [ label="2" ];
klao@1951:   ///n3 [ label="3" ];
klao@1951:   ///n4 [ label="4" ];
klao@1951:   ///n5 [ label="5" ];
klao@1951:   ///n6 [ label="6 (t)" ];
klao@1951:   ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
klao@1951:   ///n5 ->  n6 [ label="9, length:4" ];
klao@1951:   ///n4 ->  n6 [ label="8, length:2" ];
klao@1951:   ///n3 ->  n5 [ label="7, length:1" ];
klao@1951:   ///n2 ->  n5 [ label="6, length:3" ];
klao@1951:   ///n2 ->  n6 [ label="5, length:5" ];
klao@1951:   ///n2 ->  n4 [ label="4, length:2" ];
klao@1951:   ///n1 ->  n4 [ label="3, length:3" ];
klao@1951:   ///n0 ->  n3 [ label="2, length:1" ];
klao@1951:   ///n0 ->  n2 [ label="1, length:2" ];
klao@1951:   ///n0 ->  n1 [ label="0, length:3" ];
klao@1951:   ///}
klao@1951:   ///\enddot
klao@1951:   ///
klao@1951:   ///\code
klao@1951:   ///Graph g;
klao@1951:   ///Node s, t;
klao@1951:   ///LengthMap length(g);
klao@1951:   ///
klao@1951:   ///readDimacs(std::cin, g, length, s, t);
klao@1951:   ///
klao@1951:   ///cout << "edges with lengths (of form id, source--length->target): " << endl;
klao@1951:   ///for(EdgeIt e(g); e!=INVALID; ++e) 
klao@1951:   ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 
klao@1951:   ///       << length[e] << "->" << g.id(g.target(e)) << endl;
klao@1951:   ///
klao@1951:   ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
klao@1951:   ///\endcode
klao@1951:   ///Next, the potential function is computed with Dijkstra.
klao@1951:   ///\code
klao@1951:   ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
klao@1951:   ///Dijkstra dijkstra(g, length);
klao@1951:   ///dijkstra.run(s);
klao@1951:   ///\endcode
klao@1951:   ///Next, we consrtruct a map which filters the edge-set to the tight edges.
klao@1951:   ///\code
klao@1951:   ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
klao@1951:   ///  TightEdgeFilter;
klao@1951:   ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
klao@1951:   ///
deba@1991:   ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
deba@1991:   ///SubGA ga(g, tight_edge_filter);
klao@1951:   ///\endcode
klao@1951:   ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
klao@1951:   ///with a max flow algorithm Preflow.
klao@1951:   ///\code
klao@1951:   ///ConstMap<Edge, int> const_1_map(1);
klao@1951:   ///Graph::EdgeMap<int> flow(g, 0);
klao@1951:   ///
deba@1991:   ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
deba@1991:   ///  preflow(ga, s, t, const_1_map, flow);
klao@1951:   ///preflow.run();
klao@1951:   ///\endcode
klao@1951:   ///Last, the output is:
klao@1951:   ///\code  
klao@1951:   ///cout << "maximum number of edge-disjoint shortest path: " 
klao@1951:   ///     << preflow.flowValue() << endl;
klao@1951:   ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
klao@1951:   ///     << endl;
klao@1951:   ///for(EdgeIt e(g); e!=INVALID; ++e) 
klao@1951:   ///  if (flow[e])
klao@1951:   ///    cout << " " << g.id(g.source(e)) << "--"
klao@1951:   ///         << length[e] << "->" << g.id(g.target(e)) << endl;
klao@1951:   ///\endcode
klao@1951:   ///The program has the following (expected :-)) output:
klao@1951:   ///\code
klao@1951:   ///edges with lengths (of form id, source--length->target):
klao@1951:   /// 9, 5--4->6
klao@1951:   /// 8, 4--2->6
klao@1951:   /// 7, 3--1->5
klao@1951:   /// 6, 2--3->5
klao@1951:   /// 5, 2--5->6
klao@1951:   /// 4, 2--2->4
klao@1951:   /// 3, 1--3->4
klao@1951:   /// 2, 0--1->3
klao@1951:   /// 1, 0--2->2
klao@1951:   /// 0, 0--3->1
klao@1951:   ///s: 0 t: 6
klao@1951:   ///maximum number of edge-disjoint shortest path: 2
klao@1951:   ///edges of the maximum number of edge-disjoint shortest s-t paths:
klao@1951:   /// 9, 5--4->6
klao@1951:   /// 8, 4--2->6
klao@1951:   /// 7, 3--1->5
klao@1951:   /// 4, 2--2->4
klao@1951:   /// 2, 0--1->3
klao@1951:   /// 1, 0--2->2
klao@1951:   ///\endcode
klao@1951:   ///
klao@1951:   ///\author Marton Makai
marci@932:   template<typename Graph, typename EdgeFilterMap>
alpar@1401:   class EdgeSubGraphAdaptor : 
alpar@1401:     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
deba@1681: 			   EdgeFilterMap, false> {
marci@932:   public:
alpar@1401:     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
deba@1685: 			    EdgeFilterMap, false> Parent;
marci@932:   protected:
marci@932:     ConstMap<typename Graph::Node, bool> const_true_map;
deba@1991: 
deba@1991:     EdgeSubGraphAdaptor() : const_true_map(true) {
deba@1991:       Parent::setNodeFilterMap(const_true_map);
deba@1991:     }
deba@1991: 
marci@932:   public:
deba@2031: 
alpar@1401:     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
marci@932:       Parent(), const_true_map(true) { 
marci@932:       Parent::setGraph(_graph);
marci@932:       Parent::setNodeFilterMap(const_true_map);
marci@932:       Parent::setEdgeFilterMap(_edge_filter_map);
marci@932:     }
deba@2031: 
marci@932:   };
marci@932: 
deba@1991:   /// \brief Just gives back an edge sub graph adaptor
deba@1991:   ///
deba@1991:   /// Just gives back an edge sub graph adaptor
deba@1991:   template<typename Graph, typename EdgeFilterMap>
deba@1991:   EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
deba@1991:   edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
deba@1991:     return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
deba@1991:   }
deba@1991: 
deba@1991:   template<typename Graph, typename EdgeFilterMap>
deba@1991:   EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
deba@1991:   edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
deba@1991:     return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
deba@1991:   }
deba@1991: 
deba@2079:   template <typename _Graph>
deba@1980:   class UndirGraphAdaptorBase : 
deba@2079:     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
marci@1383:   public:
marci@1383:     typedef _Graph Graph;
deba@2031:     typedef UndirGraphAdaptorBase Adaptor;
deba@2079:     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
deba@1991: 
marci@1383:   protected:
deba@1991: 
deba@1991:     UndirGraphAdaptorBase() : Parent() {}
deba@1991: 
marci@1383:   public:
deba@1991: 
klao@1909:     typedef typename Parent::UEdge UEdge;
marci@1383:     typedef typename Parent::Edge Edge;
deba@1991: 
deba@2031:   private:
marci@1383:     
deba@1991:     template <typename _Value>
deba@2031:     class EdgeMapBase {
deba@1991:     private:
deba@1991:       
deba@1991:       typedef typename _Graph::template EdgeMap<_Value> MapImpl;
deba@1991:       
marci@1383:     public:
deba@1991: 
deba@1991:       typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
deba@1991: 
deba@1991:       typedef _Value Value;
marci@1383:       typedef Edge Key;
marci@1383:       
deba@2031:       EdgeMapBase(const Adaptor& adaptor) :
deba@2031: 	forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
marci@569: 
deba@2031:       EdgeMapBase(const Adaptor& adaptor, const Value& v) 
deba@2031:         : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
marci@1383:       
deba@1991:       void set(const Edge& e, const Value& a) { 
deba@1991: 	if (Parent::direction(e)) {
marci@1383: 	  forward_map.set(e, a); 
deba@1991:         } else { 
deba@1991: 	  backward_map.set(e, a);
deba@1991:         } 
marci@1383:       }
marci@556: 
deba@1991:       typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const { 
deba@1991: 	if (Parent::direction(e)) {
marci@1383: 	  return forward_map[e]; 
deba@1991: 	} else { 
marci@1383: 	  return backward_map[e]; 
deba@1991:         }
marci@556:       }
deba@1991: 
deba@1991:       typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) { 
deba@1991: 	if (Parent::direction(e)) {
deba@1991: 	  return forward_map[e]; 
deba@1991: 	} else { 
deba@1991: 	  return backward_map[e]; 
deba@1991:         }
deba@1991:       }
deba@1991: 
deba@1991:     protected:
deba@1991: 
deba@1991:       MapImpl forward_map, backward_map; 
deba@1991: 
marci@556:     };
deba@2031: 
deba@2031:   public:
deba@2031: 
deba@2031:     template <typename _Value>
deba@2031:     class EdgeMap 
deba@2031:       : public SubMapExtender<Adaptor, EdgeMapBase<_Value> > 
deba@2031:     {
deba@2031:     public:
deba@2031:       typedef Adaptor Graph;
deba@2031:       typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
deba@2031:     
deba@2031:       EdgeMap(const Graph& graph) 
deba@2031: 	: Parent(graph) {}
deba@2031:       EdgeMap(const Graph& graph, const _Value& value) 
deba@2031: 	: Parent(graph, value) {}
deba@2031:     
deba@2031:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@2031: 	return operator=<EdgeMap>(cmap);
deba@2031:       }
deba@2031:     
deba@2031:       template <typename CMap>
deba@2031:       EdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031: 	return *this;
deba@2031:       }
deba@2031:     };
marci@1383:         
deba@1991:     template <typename _Value>
deba@2031:     class UEdgeMap : public Graph::template EdgeMap<_Value> {
marci@1383:     public:
deba@2031:       
deba@2031:       typedef typename Graph::template EdgeMap<_Value> Parent;
deba@2031:       
deba@2031:       explicit UEdgeMap(const Adaptor& ga) 
deba@2031: 	: Parent(*ga.graph) {}
deba@1991: 
deba@2031:       UEdgeMap(const Adaptor& ga, const _Value& value)
deba@2031: 	: Parent(*ga.graph, value) {}
deba@1991: 
deba@2031:       UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@2031:         return operator=<UEdgeMap>(cmap);
deba@2031:       }
deba@1991: 
deba@2031:       template <typename CMap>
deba@2031:       UEdgeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@2031:       }
deba@2031: 
deba@1991:     };
deba@1991:       
deba@1991:   };
marci@556: 
deba@2079:   template <typename _Graph, typename Enable = void>
deba@2079:   class AlterableUndirGraphAdaptor 
deba@2079:     : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
deba@2079:   public:
deba@2079:     typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
deba@2079:     
deba@2079:   protected:
deba@2079: 
deba@2079:     AlterableUndirGraphAdaptor() : Parent() {}
deba@2079: 
deba@1991:   public:
deba@1991: 
deba@2079:     typedef typename Parent::EdgeNotifier UEdgeNotifier;
deba@2079:     typedef InvalidType EdgeNotifier;
deba@2079: 
deba@2079:   };
deba@2079: 
deba@2079:   template <typename _Graph>
deba@2079:   class AlterableUndirGraphAdaptor<
deba@2079:     _Graph, 
deba@2079:     typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type > 
deba@2079:     : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
deba@2079:   public:
deba@2079: 
deba@2079:     typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
deba@1991:     typedef _Graph Graph;
deba@2079:     typedef typename _Graph::Edge GraphEdge;
deba@2079:     
deba@1991:   protected:
deba@1991: 
deba@2079:     AlterableUndirGraphAdaptor() 
deba@2079:       : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
deba@1991: 
deba@1991:     void setGraph(_Graph& graph) {
deba@1991:       Parent::setGraph(graph);
deba@2079:       edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
deba@1991:     }
deba@1991: 
deba@1991:   public:
deba@1991: 
deba@2079:     ~AlterableUndirGraphAdaptor() {
deba@1999:       edge_notifier.clear();
deba@1999:     }
deba@1999: 
deba@1991:     typedef typename Parent::UEdge UEdge;
deba@1991:     typedef typename Parent::Edge Edge;
deba@1991: 
deba@1991:     typedef typename Parent::EdgeNotifier UEdgeNotifier;
deba@1991: 
deba@1991:     using Parent::getNotifier;
deba@1991: 
deba@2079:     typedef AlterationNotifier<AlterableUndirGraphAdaptor, 
deba@2079:                                Edge> EdgeNotifier;
deba@1991:     EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
deba@1991: 
deba@1991:   protected:
deba@1991: 
deba@2079:     class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
deba@1991:     public:
deba@1991: 
deba@2079:       typedef typename Graph::EdgeNotifier::ObserverBase Parent;
deba@2079:       typedef AlterableUndirGraphAdaptor AdaptorBase;
marci@1383:       
deba@2079:       NotifierProxy(const AdaptorBase& _adaptor)
deba@2079:         : Parent(), adaptor(&_adaptor) {
marci@1383:       }
marci@556: 
deba@1991:       virtual ~NotifierProxy() {
deba@1991:         if (Parent::attached()) {
deba@1991:           Parent::detach();
deba@1991:         }
marci@1383:       }
deba@1991: 
deba@2079:       void setNotifier(typename Graph::EdgeNotifier& notifier) {
deba@2079:         Parent::attach(notifier);
deba@1991:       }
deba@1991: 
deba@1991:       
deba@1991:     protected:
deba@1991: 
deba@2079:       virtual void add(const GraphEdge& ge) {
deba@1991:         std::vector<Edge> edges;
deba@2079:         edges.push_back(AdaptorBase::Parent::direct(ge, true));
deba@2079:         edges.push_back(AdaptorBase::Parent::direct(ge, false));
deba@2079:         adaptor->getNotifier(Edge()).add(edges);
deba@1991:       }
deba@2079:       virtual void add(const std::vector<GraphEdge>& ge) {
deba@1991:         std::vector<Edge> edges;
deba@2079:         for (int i = 0; i < (int)ge.size(); ++i) { 
deba@2079:           edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
deba@2079:           edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
deba@1991:         }
deba@2079:         adaptor->getNotifier(Edge()).add(edges);
deba@1991:       }
deba@2079:       virtual void erase(const GraphEdge& ge) {
deba@1991:         std::vector<Edge> edges;
deba@2079:         edges.push_back(AdaptorBase::Parent::direct(ge, true));
deba@2079:         edges.push_back(AdaptorBase::Parent::direct(ge, false));
deba@2079:         adaptor->getNotifier(Edge()).erase(edges);
deba@1991:       }
deba@2079:       virtual void erase(const std::vector<GraphEdge>& ge) {
deba@1991:         std::vector<Edge> edges;
deba@2079:         for (int i = 0; i < (int)ge.size(); ++i) { 
deba@2079:           edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
deba@2079:           edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
deba@1991:         }
deba@2079:         adaptor->getNotifier(Edge()).erase(edges);
deba@1991:       }
deba@1991:       virtual void build() {
deba@2079:         adaptor->getNotifier(Edge()).build();
deba@1991:       }
deba@1991:       virtual void clear() {
deba@2079:         adaptor->getNotifier(Edge()).clear();
deba@1991:       }
deba@1991: 
deba@2079:       const AdaptorBase* adaptor;
deba@1991:     };
deba@1991: 
deba@1991: 
deba@1991:     mutable EdgeNotifier edge_notifier;
deba@1991:     NotifierProxy edge_notifier_proxy;
deba@1991: 
marci@1383:   };
marci@1383: 
deba@2079: 
deba@2081:   ///\ingroup graph_adaptors
deba@2081:   ///
deba@2079:   /// \brief An undirected graph is made from a directed graph by an adaptor
klao@1951:   ///
deba@2251:   /// This adaptor makes an undirected graph from a directed
deba@2251:   /// graph. All edge of the underlying will be showed in the adaptor
deba@2251:   /// as an undirected edge. Let's see an informal example about using
deba@2251:   /// this adaptor:
deba@2251:   ///
deba@2251:   /// There is a network of the streets of a town. Of course there are
deba@2251:   /// some one-way street in the town hence the network is a directed
deba@2251:   /// one. There is a crazy driver who go oppositely in the one-way
deba@2251:   /// street without moral sense. Of course he can pass this streets
deba@2251:   /// slower than the regular way, in fact his speed is half of the
deba@2251:   /// normal speed. How long should he drive to get from a source
deba@2251:   /// point to the target? Let see the example code which calculate it:
deba@2251:   ///
deba@2251:   ///\code
deba@2251:   /// typedef UndirGraphAdaptor<Graph> UGraph;
deba@2251:   /// UGraph ugraph(graph);
deba@2251:   ///
deba@2251:   /// typedef SimpleMap<LengthMap> FLengthMap;
deba@2251:   /// FLengthMap flength(length);
deba@2251:   ///
deba@2251:   /// typedef ScaleMap<LengthMap> RLengthMap;
deba@2251:   /// RLengthMap rlength(length, 2.0);
deba@2251:   ///
deba@2251:   /// typedef UGraph::CombinedEdgeMap<FLengthMap, RLengthMap > ULengthMap;
deba@2251:   /// ULengthMap ulength(flength, rlength);
klao@1951:   /// 
deba@2251:   /// Dijkstra<UGraph, ULengthMap> dijkstra(ugraph, ulength);
deba@2251:   /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
deba@2251:   ///\endcode
deba@2251:   ///
deba@2251:   /// The combined edge map makes the length map for the undirected
deba@2251:   /// graph. It is created from a forward and reverse map. The forward
deba@2251:   /// map is created from the original length map with a SimpleMap
deba@2251:   /// adaptor which just makes a read-write map from the reference map
deba@2251:   /// i.e. it forgets that it can be return reference to values. The
deba@2251:   /// reverse map is just the scaled original map with the ScaleMap
deba@2251:   /// adaptor. The combination solves that passing the reverse way
deba@2251:   /// takes double time than the original. To get the driving time we
deba@2251:   /// run the dijkstra algorithm on the undirected graph.
deba@2251:   ///
deba@2251:   /// \author Marton Makai and Balazs Dezso
marci@1383:   template<typename _Graph>
deba@2079:   class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
marci@1383:   public:
marci@1383:     typedef _Graph Graph;
deba@2079:     typedef AlterableUndirGraphAdaptor<_Graph> Parent;
marci@1383:   protected:
deba@1980:     UndirGraphAdaptor() { }
marci@1383:   public:
deba@2251: 
deba@2251:     /// \brief Constructor
deba@2251:     ///
deba@2251:     /// Constructor
deba@1980:     UndirGraphAdaptor(_Graph& _graph) { 
marci@1383:       setGraph(_graph);
marci@556:     }
marci@556: 
deba@2251:     /// \brief EdgeMap combined from two original EdgeMap
deba@2251:     ///
deba@2251:     /// This class adapts two original graph EdgeMap to
deba@2251:     /// get an edge map on the adaptor.
deba@1991:     template <typename _ForwardMap, typename _BackwardMap>
deba@1991:     class CombinedEdgeMap {
deba@1991:     public:
deba@1991:       
deba@1991:       typedef _ForwardMap ForwardMap;
deba@1991:       typedef _BackwardMap BackwardMap;
marci@992: 
deba@1991:       typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
marci@992: 
deba@1991:       typedef typename ForwardMap::Value Value;
deba@1991:       typedef typename Parent::Edge Key;
deba@2251: 
deba@2251:       /// \brief Constructor      
deba@2251:       ///
deba@2251:       /// Constructor      
deba@1991:       CombinedEdgeMap() : forward_map(0), backward_map(0) {}
marci@992: 
deba@2251:       /// \brief Constructor      
deba@2251:       ///
deba@2251:       /// Constructor      
deba@1991:       CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map) 
deba@1991:         : forward_map(&_forward_map), backward_map(&_backward_map) {}
marci@992:       
deba@2251: 
deba@2251:       /// \brief Sets the value associated with a key.
deba@2251:       ///
deba@2251:       /// Sets the value associated with a key.
deba@1991:       void set(const Key& e, const Value& a) { 
deba@1991: 	if (Parent::direction(e)) {
deba@1991: 	  forward_map->set(e, a); 
deba@1991:         } else { 
deba@1991: 	  backward_map->set(e, a);
deba@1991:         } 
marci@992:       }
marci@992: 
deba@2251:       /// \brief Returns the value associated with a key.
deba@2251:       ///
deba@2251:       /// Returns the value associated with a key.
deba@1991:       typename MapTraits<ForwardMap>::ConstReturnValue 
deba@1991:       operator[](const Key& e) const { 
deba@1991: 	if (Parent::direction(e)) {
deba@1991: 	  return (*forward_map)[e]; 
deba@1991: 	} else { 
deba@1991: 	  return (*backward_map)[e]; 
deba@1991:         }
marci@992:       }
marci@992: 
deba@2251:       /// \brief Returns the value associated with a key.
deba@2251:       ///
deba@2251:       /// Returns the value associated with a key.
deba@1991:       typename MapTraits<ForwardMap>::ReturnValue 
deba@1991:       operator[](const Key& e) { 
deba@1991: 	if (Parent::direction(e)) {
deba@1991: 	  return (*forward_map)[e]; 
deba@1991: 	} else { 
deba@1991: 	  return (*backward_map)[e]; 
deba@1991:         }
marci@992:       }
deba@1991: 
deba@2251:       /// \brief Sets the forward map
deba@2251:       ///
deba@2251:       /// Sets the forward map
deba@1991:       void setForwardMap(ForwardMap& _forward_map) {
deba@1991:         forward_map = &_forward_map;
deba@1991:       }
deba@1991: 
deba@2251:       /// \brief Sets the backward map
deba@2251:       ///
deba@2251:       /// Sets the backward map
deba@1991:       void setBackwardMap(BackwardMap& _backward_map) {
deba@1991:         backward_map = &_backward_map;
deba@1991:       }
deba@1991: 
deba@1991:     protected:
deba@1991: 
deba@1991:       ForwardMap* forward_map;
deba@1991:       BackwardMap* backward_map; 
deba@1991: 
marci@992:     };
marci@992: 
marci@992:   };
marci@569: 
deba@1991:   /// \brief Just gives back an undir graph adaptor
klao@1951:   ///
deba@1991:   /// Just gives back an undir graph adaptor
marci@650:   template<typename Graph>
deba@1991:   UndirGraphAdaptor<const Graph>
deba@1991:   undirGraphAdaptor(const Graph& graph) {
deba@1991:     return UndirGraphAdaptor<const Graph>(graph);
deba@1991:   }
marci@650: 
deba@2034:   template<typename Graph, typename Number,  
deba@2034:            typename CapacityMap, typename FlowMap, 
alpar@2277:            typename Tol = Tolerance<Number> >
marci@658:   class ResForwardFilter {
marci@650:     const CapacityMap* capacity;
marci@650:     const FlowMap* flow;
alpar@2277:     Tol tolerance;
marci@650:   public:
deba@1991:     typedef typename Graph::Edge Key;
deba@1991:     typedef bool Value;
deba@1991: 
deba@2034:     ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
alpar@2277:                      const Tol& _tolerance = Tol()) 
deba@2034:       : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
deba@2034: 
alpar@2277:     ResForwardFilter(const Tol& _tolerance) 
deba@2034:       : capacity(0), flow(0), tolerance(_tolerance)  { }
deba@2034: 
deba@1991:     void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
deba@1991:     void setFlow(const FlowMap& _flow) { flow = &_flow; }
deba@2034: 
marci@650:     bool operator[](const typename Graph::Edge& e) const {
deba@2340:       return tolerance.positive((*capacity)[e] - (*flow)[e]);
marci@650:     }
marci@650:   };
marci@650: 
marci@650:   template<typename Graph, typename Number,
deba@2034: 	   typename CapacityMap, typename FlowMap,
alpar@2277:            typename Tol = Tolerance<Number> >
marci@658:   class ResBackwardFilter {
marci@650:     const CapacityMap* capacity;
marci@650:     const FlowMap* flow;
alpar@2277:     Tol tolerance;
marci@650:   public:
deba@1991:     typedef typename Graph::Edge Key;
deba@1991:     typedef bool Value;
deba@1991: 
deba@2034:     ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
alpar@2277:                       const Tol& _tolerance = Tol())
deba@2034:       : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
alpar@2277:     ResBackwardFilter(const Tol& _tolerance = Tol())
deba@2034:       : capacity(0), flow(0), tolerance(_tolerance) { }
deba@1991:     void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
deba@1991:     void setFlow(const FlowMap& _flow) { flow = &_flow; }
marci@650:     bool operator[](const typename Graph::Edge& e) const {
deba@2340:       return tolerance.positive((*flow)[e]);
marci@650:     }
marci@650:   };
marci@650: 
marci@653:   
deba@2081:   ///\ingroup graph_adaptors
deba@2081:   ///
klao@1951:   ///\brief An adaptor for composing the residual
klao@1951:   ///graph for directed flow and circulation problems.
deba@2037:   ///
deba@2042:   ///An adaptor for composing the residual graph for directed flow and
deba@2042:   ///circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
deba@2042:   ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
deba@2042:   ///be functions on the edge-set.
deba@2042:   ///
deba@2042:   ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
deba@2042:   ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
deba@2042:   ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
deba@2042:   ///
deba@2042:   ///\code 
deba@2042:   ///  ListGraph g;
deba@2042:   ///\endcode 
deba@2042:   ///
deba@2042:   ///Then RevGraphAdaptor implements the graph structure with node-set
deba@2042:   /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
deba@2042:   ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 
deba@2042:   /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so called
deba@2042:   ///residual graph.  When we take the union 
deba@2042:   /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e. 
deba@2042:   ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$, 
deba@2042:   ///then in the adaptor it appears twice. The following code shows how 
deba@2042:   ///such an instance can be constructed.
deba@2042:   ///
deba@2042:   ///\code 
deba@2042:   ///  typedef ListGraph Graph; 
deba@2042:   ///  Graph::EdgeMap<int> f(g);
deba@2042:   ///  Graph::EdgeMap<int> c(g); 
deba@2042:   ///  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g); 
deba@2042:   ///\endcode
deba@2042:   ///\author Marton Makai
deba@2042:   ///
marci@650:   template<typename Graph, typename Number, 
deba@2034: 	   typename CapacityMap, typename FlowMap,
alpar@2277:            typename Tol = Tolerance<Number> >
alpar@1401:   class ResGraphAdaptor : 
deba@1991:     public EdgeSubGraphAdaptor< 
deba@2034:     UndirGraphAdaptor<const Graph>, 
deba@2034:     typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
deba@2034:     ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,  
deba@2034:     ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
marci@650:   public:
deba@1991: 
deba@2034:     typedef UndirGraphAdaptor<const Graph> UGraph;
deba@1991: 
deba@2034:     typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap> 
deba@1991:     ForwardFilter;
deba@1991: 
deba@2034:     typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> 
deba@1991:     BackwardFilter;
deba@1991: 
deba@1991:     typedef typename UGraph::
deba@1991:     template CombinedEdgeMap<ForwardFilter, BackwardFilter>
deba@1991:     EdgeFilter;
deba@1991: 
deba@1991:     typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
deba@1991: 
marci@650:   protected:
deba@1991: 
marci@650:     const CapacityMap* capacity;
marci@650:     FlowMap* flow;
deba@1991: 
deba@1991:     UGraph ugraph;
deba@1991:     ForwardFilter forward_filter;
deba@1991:     BackwardFilter backward_filter;
deba@1991:     EdgeFilter edge_filter;
deba@1991: 
marci@658:     void setCapacityMap(const CapacityMap& _capacity) {
marci@658:       capacity=&_capacity;
marci@658:       forward_filter.setCapacity(_capacity);
marci@658:       backward_filter.setCapacity(_capacity);
marci@658:     }
deba@1991: 
marci@658:     void setFlowMap(FlowMap& _flow) {
marci@658:       flow=&_flow;
marci@658:       forward_filter.setFlow(_flow);
marci@658:       backward_filter.setFlow(_flow);
marci@658:     }
deba@1991: 
marci@650:   public:
deba@1991: 
deba@2034:     /// \brief Constructor of the residual graph.
deba@2034:     ///
deba@2034:     /// Constructor of the residual graph. The parameters are the graph type,
deba@2034:     /// the flow map, the capacity map and a tolerance object.
deba@2034:     ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity, 
alpar@2277:                     FlowMap& _flow, const Tol& _tolerance = Tol()) 
deba@2034:       : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
deba@2034:         forward_filter(_capacity, _flow, _tolerance), 
deba@2034:         backward_filter(_capacity, _flow, _tolerance),
deba@2034:         edge_filter(forward_filter, backward_filter)
deba@2034:     {
deba@1991:       Parent::setGraph(ugraph);
deba@1991:       Parent::setEdgeFilterMap(edge_filter);
marci@650:     }
marci@650: 
marci@660:     typedef typename Parent::Edge Edge;
marci@660: 
deba@2034:     /// \brief Gives back the residual capacity of the edge.
deba@2034:     ///
deba@2034:     /// Gives back the residual capacity of the edge.
deba@2034:     Number rescap(const Edge& edge) const {
deba@2034:       if (UGraph::direction(edge)) {
deba@2034:         return (*capacity)[edge]-(*flow)[edge]; 
deba@2034:       } else {
deba@2034:         return (*flow)[edge];
deba@2034:       }
deba@2034:     } 
deba@2034: 
deba@2034:     /// \brief Augment on the given edge in the residual graph.
deba@2034:     ///
deba@2034:     /// Augment on the given edge in the residual graph. It increase
deba@2034:     /// or decrease the flow on the original edge depend on the direction
deba@2034:     /// of the residual edge.
marci@660:     void augment(const Edge& e, Number a) const {
deba@1991:       if (UGraph::direction(e)) {
deba@2034:         flow->set(e, (*flow)[e] + a);
deba@1991:       } else {  
deba@2034:         flow->set(e, (*flow)[e] - a);
deba@1991:       }
marci@650:     }
marci@650: 
deba@2034:     /// \brief Returns the direction of the edge.
deba@2034:     ///
deba@2034:     /// Returns true when the edge is same oriented as the original edge.
deba@1991:     static bool forward(const Edge& e) {
deba@1991:       return UGraph::direction(e);
deba@1991:     }
deba@1991: 
deba@2034:     /// \brief Returns the direction of the edge.
deba@2034:     ///
deba@2034:     /// Returns true when the edge is opposite oriented as the original edge.
deba@1991:     static bool backward(const Edge& e) {
deba@1991:       return !UGraph::direction(e);
deba@1991:     }
deba@1991: 
deba@2034:     /// \brief Gives back the forward oriented residual edge.
deba@2034:     ///
deba@2034:     /// Gives back the forward oriented residual edge.
deba@1991:     static Edge forward(const typename Graph::Edge& e) {
deba@1991:       return UGraph::direct(e, true);
deba@1991:     }
deba@1991: 
deba@2034:     /// \brief Gives back the backward oriented residual edge.
deba@2034:     ///
deba@2034:     /// Gives back the backward oriented residual edge.
deba@1991:     static Edge backward(const typename Graph::Edge& e) {
deba@1991:       return UGraph::direct(e, false);
deba@1991:     }
deba@1991: 
klao@1951:     /// \brief Residual capacity map.
klao@1951:     ///
klao@1951:     /// In generic residual graphs the residual capacity can be obtained 
klao@1951:     /// as a map. 
marci@660:     class ResCap {
marci@660:     protected:
deba@1991:       const ResGraphAdaptor* res_graph;
marci@660:     public:
alpar@987:       typedef Number Value;
alpar@987:       typedef Edge Key;
deba@1991:       ResCap(const ResGraphAdaptor& _res_graph) 
deba@1991:         : res_graph(&_res_graph) {}
deba@1991:       
deba@2034:       Number operator[](const Edge& e) const {
deba@2034:         return res_graph->rescap(e);
marci@660:       }
deba@1991:       
marci@660:     };
marci@660: 
marci@650:   };
marci@650: 
marci@650: 
marci@998: 
marci@998:   template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401:   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@998:   public:
marci@998:     typedef _Graph Graph;
alpar@1401:     typedef GraphAdaptorBase<_Graph> Parent;
marci@998:   protected:
marci@998:     FirstOutEdgesMap* first_out_edges;
alpar@1401:     ErasingFirstGraphAdaptorBase() : Parent(), 
marci@998: 				     first_out_edges(0) { }
marci@998: 
marci@998:     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
marci@998:       first_out_edges=&_first_out_edges;
marci@998:     }
marci@998: 
marci@998:   public:
marci@998: 
marci@998:     typedef typename Parent::Node Node;
marci@998:     typedef typename Parent::Edge Edge;
marci@998: 
marci@998:     void firstOut(Edge& i, const Node& n) const { 
marci@998:       i=(*first_out_edges)[n];
marci@998:     }
marci@998: 
marci@998:     void erase(const Edge& e) const {
marci@998:       Node n=source(e);
marci@998:       Edge f=e;
marci@998:       Parent::nextOut(f);
marci@998:       first_out_edges->set(n, f);
marci@998:     }    
marci@998:   };
marci@998: 
marci@998: 
deba@2081:   ///\ingroup graph_adaptors
deba@2081:   ///
klao@1951:   ///\brief For blocking flows.
klao@1951:   ///
klao@1951:   ///This graph adaptor is used for on-the-fly 
klao@1951:   ///Dinits blocking flow computations.
klao@1951:   ///For each node, an out-edge is stored which is used when the 
klao@1951:   ///\code
klao@1951:   ///OutEdgeIt& first(OutEdgeIt&, const Node&)
klao@1951:   ///\endcode
klao@1951:   ///is called. 
klao@1951:   ///
klao@1951:   ///\author Marton Makai
klao@1951:   ///
marci@998:   template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401:   class ErasingFirstGraphAdaptor : 
deba@1979:     public GraphAdaptorExtender<
alpar@1401:     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
marci@650:   public:
marci@998:     typedef _Graph Graph;
deba@1979:     typedef GraphAdaptorExtender<
alpar@1401:       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
alpar@1401:     ErasingFirstGraphAdaptor(Graph& _graph, 
marci@998: 			     FirstOutEdgesMap& _first_out_edges) { 
marci@998:       setGraph(_graph);
marci@998:       setFirstOutEdgesMap(_first_out_edges);
marci@998:     } 
marci@1019: 
marci@998:   };
marci@556: 
deba@2079:   /// \brief Base class for split graph adaptor
deba@2079:   ///
deba@2079:   /// Base class of split graph adaptor. In most case you do not need to
deba@2079:   /// use it directly but the documented member functions of this class can 
deba@2079:   /// be used with the SplitGraphAdaptor class.
deba@2079:   /// \sa SplitGraphAdaptor
deba@2079:   template <typename _Graph>
deba@2079:   class SplitGraphAdaptorBase 
deba@2079:     : public GraphAdaptorBase<const _Graph> {
deba@2079:   public:
deba@1697: 
deba@2079:     typedef _Graph Graph;
deba@2079: 
deba@2079:     typedef GraphAdaptorBase<const _Graph> Parent;
deba@2079: 
deba@2079:     typedef typename Graph::Node GraphNode;
deba@2079:     typedef typename Graph::Edge GraphEdge;
deba@2079: 
deba@2079:     class Node;
deba@2079:     class Edge;
deba@2079: 
deba@2079:     template <typename T> class NodeMap;
deba@2079:     template <typename T> class EdgeMap;
deba@1697:     
deba@1697: 
deba@2079:     class Node : public GraphNode {
deba@2079:       friend class SplitGraphAdaptorBase;
deba@2079:       template <typename T> friend class NodeMap;
deba@2079:     private:
deba@1697: 
deba@2079:       bool in_node;
deba@2079:       Node(GraphNode _node, bool _in_node)
deba@2079: 	: GraphNode(_node), in_node(_in_node) {}
deba@1697:       
deba@2079:     public:
deba@1697: 
deba@2079:       Node() {}
deba@2079:       Node(Invalid) : GraphNode(INVALID), in_node(true) {}
deba@2079: 
deba@2079:       bool operator==(const Node& node) const {
deba@2079: 	return GraphNode::operator==(node) && in_node == node.in_node;
deba@2079:       }
deba@1697:       
deba@2079:       bool operator!=(const Node& node) const {
deba@2079: 	return !(*this == node);
deba@2079:       }
deba@1697:       
deba@2079:       bool operator<(const Node& node) const {
deba@2079: 	return GraphNode::operator<(node) || 
deba@2079: 	  (GraphNode::operator==(node) && in_node < node.in_node);
deba@2079:       }
deba@2079:     };
deba@1697: 
deba@2079:     class Edge {
deba@2079:       friend class SplitGraphAdaptorBase;
deba@2079:       template <typename T> friend class EdgeMap;
deba@2079:     private:
deba@2079:       typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
deba@1697: 
deba@2079:       explicit Edge(const GraphEdge& edge) : item(edge) {}
deba@2079:       explicit Edge(const GraphNode& node) : item(node) {}
deba@2079:       
deba@2079:       EdgeImpl item;
deba@1697: 
deba@2079:     public:
deba@2079:       Edge() {}
deba@2079:       Edge(Invalid) : item(GraphEdge(INVALID)) {}
deba@2079: 
deba@2079:       bool operator==(const Edge& edge) const {
deba@2079:         if (item.firstState()) {
deba@2079:           if (edge.item.firstState()) {
deba@2079:             return item.first() == edge.item.first();
deba@2079:           }
deba@2079:         } else {
deba@2079:           if (edge.item.secondState()) {
deba@2079:             return item.second() == edge.item.second();
deba@2079:           }
deba@2079:         }
deba@2079:         return false;
deba@2079:       }
deba@1697:       
deba@2079:       bool operator!=(const Edge& edge) const {
deba@2079: 	return !(*this == edge);
deba@2079:       }
deba@1697:       
deba@2079:       bool operator<(const Edge& edge) const {
deba@2079:         if (item.firstState()) {
deba@2079:           if (edge.item.firstState()) {
deba@2079:             return item.first() < edge.item.first();
deba@2079:           }
deba@2079:           return false;
deba@2079:         } else {
deba@2079:           if (edge.item.secondState()) {
deba@2079:             return item.second() < edge.item.second();
deba@2079:           }
deba@2079:           return true;
deba@2079:         }
deba@2079:       }
deba@1697: 
deba@2079:       operator GraphEdge() const { return item.first(); }
deba@2079:       operator GraphNode() const { return item.second(); }
deba@1697: 
deba@2079:     };
deba@1697: 
deba@2079:     void first(Node& node) const {
deba@2079:       Parent::first(node);
deba@2079:       node.in_node = true;
deba@2079:     }
deba@1697: 
deba@2079:     void next(Node& node) const {
deba@2079:       if (node.in_node) {
deba@2079: 	node.in_node = false;
deba@2079:       } else {
deba@2079: 	node.in_node = true;
deba@2079: 	Parent::next(node);
deba@2079:       }
deba@2079:     }
deba@1697: 
deba@2079:     void first(Edge& edge) const {
deba@2079:       edge.item.setSecond();
deba@2079:       Parent::first(edge.item.second());
deba@2079:       if (edge.item.second() == INVALID) {
deba@2079:         edge.item.setFirst();
deba@2079: 	Parent::first(edge.item.first());
deba@2079:       }
deba@2079:     }
deba@1697: 
deba@2079:     void next(Edge& edge) const {
deba@2079:       if (edge.item.secondState()) {
deba@2079: 	Parent::next(edge.item.second());
deba@2079:         if (edge.item.second() == INVALID) {
deba@2079:           edge.item.setFirst();
deba@2079:           Parent::first(edge.item.first());
deba@2079:         }
deba@2079:       } else {
deba@2079: 	Parent::next(edge.item.first());
deba@2079:       }      
deba@2079:     }
deba@1697: 
deba@2079:     void firstOut(Edge& edge, const Node& node) const {
deba@2079:       if (node.in_node) {
deba@2079:         edge.item.setSecond(node);
deba@2079:       } else {
deba@2079:         edge.item.setFirst();
deba@2079: 	Parent::firstOut(edge.item.first(), node);
deba@2079:       }
deba@2079:     }
deba@1697: 
deba@2079:     void nextOut(Edge& edge) const {
deba@2079:       if (!edge.item.firstState()) {
deba@2079: 	edge.item.setFirst(INVALID);
deba@2079:       } else {
deba@2079: 	Parent::nextOut(edge.item.first());
deba@2079:       }      
deba@2079:     }
deba@1697: 
deba@2079:     void firstIn(Edge& edge, const Node& node) const {
deba@2079:       if (!node.in_node) {
deba@2079:         edge.item.setSecond(node);        
deba@2079:       } else {
deba@2079:         edge.item.setFirst();
deba@2079: 	Parent::firstIn(edge.item.first(), node);
deba@2079:       }
deba@2079:     }
deba@1697: 
deba@2079:     void nextIn(Edge& edge) const {
deba@2079:       if (!edge.item.firstState()) {
deba@2079: 	edge.item.setFirst(INVALID);
deba@2079:       } else {
deba@2079: 	Parent::nextIn(edge.item.first());
deba@2079:       }
deba@2079:     }
deba@1697: 
deba@2079:     Node source(const Edge& edge) const {
deba@2079:       if (edge.item.firstState()) {
deba@2079: 	return Node(Parent::source(edge.item.first()), false);
deba@2079:       } else {
deba@2079: 	return Node(edge.item.second(), true);
deba@2079:       }
deba@2079:     }
deba@1697: 
deba@2079:     Node target(const Edge& edge) const {
deba@2079:       if (edge.item.firstState()) {
deba@2079: 	return Node(Parent::target(edge.item.first()), true);
deba@2079:       } else {
deba@2079: 	return Node(edge.item.second(), false);
deba@2079:       }
deba@2079:     }
deba@1697: 
deba@2079:     int id(const Node& node) const {
deba@2079:       return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
deba@2079:     }
deba@2079:     Node nodeFromId(int id) const {
deba@2079:       return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
deba@2079:     }
deba@2079:     int maxNodeId() const {
deba@2079:       return 2 * Parent::maxNodeId() + 1;
deba@2079:     }
deba@1697: 
deba@2079:     int id(const Edge& edge) const {
deba@2079:       if (edge.item.firstState()) {
deba@2079:         return Parent::id(edge.item.first()) << 1;
deba@2079:       } else {
deba@2079:         return (Parent::id(edge.item.second()) << 1) | 1;
deba@2079:       }
deba@2079:     }
deba@2079:     Edge edgeFromId(int id) const {
deba@2079:       if ((id & 1) == 0) {
deba@2079:         return Edge(Parent::edgeFromId(id >> 1));
deba@2079:       } else {
deba@2079:         return Edge(Parent::nodeFromId(id >> 1));
deba@2079:       }
deba@2079:     }
deba@2079:     int maxEdgeId() const {
deba@2079:       return std::max(Parent::maxNodeId() << 1, 
deba@2079:                       (Parent::maxEdgeId() << 1) | 1);
deba@2079:     }
deba@1697: 
deba@2079:     /// \brief Returns true when the node is in-node.
deba@2079:     ///
deba@2079:     /// Returns true when the node is in-node.
deba@2079:     static bool inNode(const Node& node) {
deba@2079:       return node.in_node;
deba@2079:     }
deba@1697: 
deba@2079:     /// \brief Returns true when the node is out-node.
deba@2079:     ///
deba@2079:     /// Returns true when the node is out-node.
deba@2079:     static bool outNode(const Node& node) {
deba@2079:       return !node.in_node;
deba@2079:     }
deba@1697: 
deba@2079:     /// \brief Returns true when the edge is edge in the original graph.
deba@2079:     ///
deba@2079:     /// Returns true when the edge is edge in the original graph.
deba@2079:     static bool origEdge(const Edge& edge) {
deba@2079:       return edge.item.firstState();
deba@2079:     }
deba@1697: 
deba@2079:     /// \brief Returns true when the edge binds an in-node and an out-node.
deba@2079:     ///
deba@2079:     /// Returns true when the edge binds an in-node and an out-node.
deba@2079:     static bool bindEdge(const Edge& edge) {
deba@2079:       return edge.item.secondState();
deba@2079:     }
deba@1697: 
deba@2079:     /// \brief Gives back the in-node created from the \c node.
deba@2079:     ///
deba@2079:     /// Gives back the in-node created from the \c node.
deba@2079:     static Node inNode(const GraphNode& node) {
deba@2079:       return Node(node, true);
deba@2079:     }
deba@2079: 
deba@2079:     /// \brief Gives back the out-node created from the \c node.
deba@2079:     ///
deba@2079:     /// Gives back the out-node created from the \c node.
deba@2079:     static Node outNode(const GraphNode& node) {
deba@2079:       return Node(node, false);
deba@2079:     }
deba@2079: 
deba@2079:     /// \brief Gives back the edge binds the two part of the node.
deba@2079:     /// 
deba@2079:     /// Gives back the edge binds the two part of the node.
deba@2079:     static Edge edge(const GraphNode& node) {
deba@2079:       return Edge(node);
deba@2079:     }
deba@2079: 
deba@2079:     /// \brief Gives back the edge of the original edge.
deba@2079:     /// 
deba@2079:     /// Gives back the edge of the original edge.
deba@2079:     static Edge edge(const GraphEdge& edge) {
deba@2079:       return Edge(edge);
deba@2079:     }
deba@2079: 
deba@2079:     typedef True NodeNumTag;
deba@2079: 
deba@2079:     int nodeNum() const {
deba@2079:       return  2 * countNodes(*Parent::graph);
deba@2079:     }
deba@2079: 
deba@2079:     typedef True EdgeNumTag;
deba@1697:     
deba@2079:     int edgeNum() const {
deba@2079:       return countEdges(*Parent::graph) + countNodes(*Parent::graph);
deba@2079:     }
deba@1697: 
deba@2079:     typedef True FindEdgeTag;
deba@2079: 
deba@2079:     Edge findEdge(const Node& source, const Node& target, 
deba@2079: 		  const Edge& prev = INVALID) const {
deba@2079:       if (inNode(source)) {
deba@2079:         if (outNode(target)) {
deba@2079:           if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
deba@2079:             return Edge(source);
deba@2079:           }
deba@2079:         }
deba@2079:       } else {
deba@2079:         if (inNode(target)) {
deba@2079:           return Edge(findEdge(*Parent::graph, source, target, prev));
deba@2079:         }
deba@2079:       }
deba@2079:       return INVALID;
deba@2079:     }
deba@1697:     
deba@2079:     template <typename T>
deba@2079:     class NodeMap : public MapBase<Node, T> {
deba@2079:       typedef typename Parent::template NodeMap<T> NodeImpl;
deba@2079:     public:
deba@2079:       NodeMap(const SplitGraphAdaptorBase& _graph) 
deba@2079: 	: inNodeMap(_graph), outNodeMap(_graph) {}
deba@2079:       NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
deba@2079: 	: inNodeMap(_graph, t), outNodeMap(_graph, t) {}
deba@1697:       
deba@2079:       void set(const Node& key, const T& val) {
deba@2079: 	if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
deba@2079: 	else {outNodeMap.set(key, val); }
deba@2079:       }
deba@1697:       
deba@2079:       typename MapTraits<NodeImpl>::ReturnValue 
deba@2079:       operator[](const Node& key) {
deba@2079: 	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
deba@2079: 	else { return outNodeMap[key]; }
deba@2079:       }
deba@1697: 
deba@2079:       typename MapTraits<NodeImpl>::ConstReturnValue
deba@2079:       operator[](const Node& key) const {
deba@2079: 	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
deba@2079: 	else { return outNodeMap[key]; }
deba@2079:       }
deba@1697: 
deba@2079:     private:
deba@2079:       NodeImpl inNodeMap, outNodeMap;
deba@2079:     };
deba@1697: 
deba@2079:     template <typename T>
deba@2079:     class EdgeMap : public MapBase<Edge, T> {
deba@2079:       typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
deba@2079:       typedef typename Parent::template NodeMap<T> NodeMapImpl;
deba@2079:     public:
deba@2079: 
deba@2079:       EdgeMap(const SplitGraphAdaptorBase& _graph) 
deba@2079: 	: edge_map(_graph), node_map(_graph) {}
deba@2079:       EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
deba@2079: 	: edge_map(_graph, t), node_map(_graph, t) {}
deba@1697:       
deba@2079:       void set(const Edge& key, const T& val) {
deba@2079: 	if (SplitGraphAdaptorBase::origEdge(key)) { 
deba@2079:           edge_map.set(key.item.first(), val); 
deba@2079:         } else {
deba@2079:           node_map.set(key.item.second(), val); 
deba@2079:         }
deba@2079:       }
deba@1697:       
deba@2079:       typename MapTraits<EdgeMapImpl>::ReturnValue
deba@2079:       operator[](const Edge& key) {
deba@2079: 	if (SplitGraphAdaptorBase::origEdge(key)) { 
deba@2079:           return edge_map[key.item.first()];
deba@2079:         } else {
deba@2079:           return node_map[key.item.second()];
deba@2079:         }
deba@2079:       }
deba@1697: 
deba@2079:       typename MapTraits<EdgeMapImpl>::ConstReturnValue
deba@2079:       operator[](const Edge& key) const {
deba@2079: 	if (SplitGraphAdaptorBase::origEdge(key)) { 
deba@2079:           return edge_map[key.item.first()];
deba@2079:         } else {
deba@2079:           return node_map[key.item.second()];
deba@2079:         }
deba@2079:       }
deba@1697: 
deba@2079:     private:
deba@2079:       typename Parent::template EdgeMap<T> edge_map;
deba@2079:       typename Parent::template NodeMap<T> node_map;
deba@2079:     };
deba@1697: 
deba@1697: 
deba@2079:   };
deba@1697: 
deba@2079:   template <typename _Graph, typename NodeEnable = void, 
deba@2079:             typename EdgeEnable = void>
deba@2079:   class AlterableSplitGraphAdaptor 
deba@2079:     : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
deba@2079:   public:
deba@1697: 
deba@2079:     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@2079:     typedef _Graph Graph;
deba@1697: 
deba@2079:     typedef typename Graph::Node GraphNode;
deba@2079:     typedef typename Graph::Node GraphEdge;
deba@1697: 
deba@2079:   protected:
deba@2079: 
deba@2079:     AlterableSplitGraphAdaptor() : Parent() {}
deba@2079: 
deba@2079:   public:
deba@2079:     
deba@2079:     typedef InvalidType NodeNotifier;
deba@2079:     typedef InvalidType EdgeNotifier;
deba@2079: 
deba@2079:   };
deba@2079: 
deba@2079:   template <typename _Graph, typename EdgeEnable>
deba@2079:   class AlterableSplitGraphAdaptor<
deba@2079:     _Graph,
deba@2079:     typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
deba@2079:     EdgeEnable> 
deba@2079:       : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
deba@2079:   public:
deba@2079: 
deba@2079:     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@2079:     typedef _Graph Graph;
deba@2079: 
deba@2079:     typedef typename Graph::Node GraphNode;
deba@2079:     typedef typename Graph::Edge GraphEdge;
deba@2079: 
deba@2079:     typedef typename Parent::Node Node;
deba@2079:     typedef typename Parent::Edge Edge;
deba@2079:  
deba@2079:   protected:
deba@2079: 
deba@2079:     AlterableSplitGraphAdaptor() 
deba@2079:       : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
deba@2079: 
deba@2079:     void setGraph(_Graph& graph) {
deba@2079:       Parent::setGraph(graph);
deba@2079:       node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
deba@2079:     }
deba@2079: 
deba@2079:   public:
deba@2079: 
deba@2079:     ~AlterableSplitGraphAdaptor() {
deba@2079:       node_notifier.clear();
deba@2079:     }
deba@2079: 
deba@2079:     typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
deba@2079:     typedef InvalidType EdgeNotifier;
deba@2079: 
deba@2079:     NodeNotifier& getNotifier(Node) const { return node_notifier; }
deba@2079: 
deba@2079:   protected:
deba@2079: 
deba@2079:     class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
deba@2079:     public:
deba@2079: 
deba@2079:       typedef typename Graph::NodeNotifier::ObserverBase Parent;
deba@2079:       typedef AlterableSplitGraphAdaptor AdaptorBase;
deba@1697:       
deba@2079:       NodeNotifierProxy(const AdaptorBase& _adaptor)
deba@2079:         : Parent(), adaptor(&_adaptor) {
deba@2079:       }
deba@2079: 
deba@2079:       virtual ~NodeNotifierProxy() {
deba@2079:         if (Parent::attached()) {
deba@2079:           Parent::detach();
deba@2079:         }
deba@2079:       }
deba@2079: 
deba@2079:       void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
deba@2079:         Parent::attach(graph_notifier);
deba@2079:       }
deba@2079: 
deba@1697:       
deba@2079:     protected:
deba@2079: 
deba@2079:       virtual void add(const GraphNode& gn) {
deba@2079:         std::vector<Node> nodes;
deba@2079:         nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079:         nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079:         adaptor->getNotifier(Node()).add(nodes);
deba@2079:       }
deba@2079: 
deba@2079:       virtual void add(const std::vector<GraphNode>& gn) {
deba@2079:         std::vector<Node> nodes;
deba@2079:         for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079:           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079:           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Node()).add(nodes);
deba@2079:       }
deba@2079: 
deba@2079:       virtual void erase(const GraphNode& gn) {
deba@2079:         std::vector<Node> nodes;
deba@2079:         nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079:         nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079:         adaptor->getNotifier(Node()).erase(nodes);
deba@2079:       }
deba@2079: 
deba@2079:       virtual void erase(const std::vector<GraphNode>& gn) {
deba@2079:         std::vector<Node> nodes;
deba@2079:         for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079:           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079:           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Node()).erase(nodes);
deba@2079:       }
deba@2079:       virtual void build() {
deba@2079:         adaptor->getNotifier(Node()).build();
deba@2079:       }
deba@2079:       virtual void clear() {
deba@2079:         adaptor->getNotifier(Node()).clear();
deba@2079:       }
deba@2079: 
deba@2079:       const AdaptorBase* adaptor;
deba@2079:     };
deba@2079: 
deba@2079: 
deba@2079:     mutable NodeNotifier node_notifier;
deba@2079: 
deba@2079:     NodeNotifierProxy node_notifier_proxy;
deba@2079: 
deba@2079:   };
deba@2079: 
deba@2079:   template <typename _Graph>
deba@2079:   class AlterableSplitGraphAdaptor<
deba@2079:     _Graph,
deba@2079:     typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
deba@2079:     typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type> 
deba@2079:       : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
deba@2079:   public:
deba@2079: 
deba@2079:     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
deba@2079:     typedef _Graph Graph;
deba@2079: 
deba@2079:     typedef typename Graph::Node GraphNode;
deba@2079:     typedef typename Graph::Edge GraphEdge;
deba@2079: 
deba@2079:     typedef typename Parent::Node Node;
deba@2079:     typedef typename Parent::Edge Edge;
deba@2079:  
deba@2079:   protected:
deba@2079:     
deba@2079:     AlterableSplitGraphAdaptor() 
deba@2079:       : Parent(), node_notifier(*this), edge_notifier(*this), 
deba@2079:         node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
deba@2079:     
deba@2079:     void setGraph(_Graph& graph) {
deba@2079:       Parent::setGraph(graph);
deba@2079:       node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
deba@2079:       edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
deba@2079:     }
deba@2079: 
deba@2079:   public:
deba@2079: 
deba@2079:     ~AlterableSplitGraphAdaptor() {
deba@2079:       node_notifier.clear();
deba@2079:       edge_notifier.clear();
deba@2079:     }
deba@2079: 
deba@2079:     typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
deba@2079:     typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
deba@2079: 
deba@2079:     NodeNotifier& getNotifier(Node) const { return node_notifier; }
deba@2079:     EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
deba@2079: 
deba@2079:   protected:
deba@2079: 
deba@2079:     class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
deba@2079:     public:
deba@1697:       
deba@2079:       typedef typename Graph::NodeNotifier::ObserverBase Parent;
deba@2079:       typedef AlterableSplitGraphAdaptor AdaptorBase;
deba@2079:       
deba@2079:       NodeNotifierProxy(const AdaptorBase& _adaptor)
deba@2079:         : Parent(), adaptor(&_adaptor) {
deba@2079:       }
deba@1697: 
deba@2079:       virtual ~NodeNotifierProxy() {
deba@2079:         if (Parent::attached()) {
deba@2079:           Parent::detach();
deba@2079:         }
deba@2079:       }
deba@1697: 
deba@2079:       void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
deba@2079:         Parent::attach(graph_notifier);
deba@2079:       }
deba@1697: 
deba@2079:       
deba@2079:     protected:
deba@1697: 
deba@2079:       virtual void add(const GraphNode& gn) {
deba@2079:         std::vector<Node> nodes;
deba@2079:         nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079:         nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079:         adaptor->getNotifier(Node()).add(nodes);
deba@2079:         adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
deba@2079:       }
deba@2079:       virtual void add(const std::vector<GraphNode>& gn) {
deba@2079:         std::vector<Node> nodes;
deba@2079:         std::vector<Edge> edges;
deba@2079:         for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079:           edges.push_back(AdaptorBase::Parent::edge(gn[i]));
deba@2079:           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079:           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Node()).add(nodes);
deba@2079:         adaptor->getNotifier(Edge()).add(edges);
deba@2079:       }
deba@2079:       virtual void erase(const GraphNode& gn) {
deba@2079:         adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
deba@2079:         std::vector<Node> nodes;
deba@2079:         nodes.push_back(AdaptorBase::Parent::inNode(gn));
deba@2079:         nodes.push_back(AdaptorBase::Parent::outNode(gn));
deba@2079:         adaptor->getNotifier(Node()).erase(nodes);
deba@2079:       }
deba@2079:       virtual void erase(const std::vector<GraphNode>& gn) {
deba@2079:         std::vector<Node> nodes;
deba@2079:         std::vector<Edge> edges;
deba@2079:         for (int i = 0; i < (int)gn.size(); ++i) {
deba@2079:           edges.push_back(AdaptorBase::Parent::edge(gn[i]));
deba@2079:           nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
deba@2079:           nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Edge()).erase(edges);
deba@2079:         adaptor->getNotifier(Node()).erase(nodes);
deba@2079:       }
deba@2079:       virtual void build() {
deba@2079:         std::vector<Edge> edges;
deba@2079:         const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079:         GraphNode it;
deba@2079:         for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079:           edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Node()).build();
deba@2079:         adaptor->getNotifier(Edge()).add(edges);        
deba@2079:       }
deba@2079:       virtual void clear() {
deba@2079:         std::vector<Edge> edges;
deba@2079:         const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079:         GraphNode it;
deba@2079:         for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079:           edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Edge()).erase(edges);        
deba@2079:         adaptor->getNotifier(Node()).clear();
deba@2079:       }
deba@1697: 
deba@2079:       const AdaptorBase* adaptor;
deba@2079:     };
deba@1697: 
deba@2079:     class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
deba@2079:     public:
deba@2079: 
deba@2079:       typedef typename Graph::EdgeNotifier::ObserverBase Parent;
deba@2079:       typedef AlterableSplitGraphAdaptor AdaptorBase;
deba@1697:       
deba@2079:       EdgeNotifierProxy(const AdaptorBase& _adaptor)
deba@2079:         : Parent(), adaptor(&_adaptor) {
deba@2079:       }
deba@1697: 
deba@2079:       virtual ~EdgeNotifierProxy() {
deba@2079:         if (Parent::attached()) {
deba@2079:           Parent::detach();
deba@2079:         }
deba@2079:       }
deba@1697: 
deba@2079:       void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
deba@2079:         Parent::attach(graph_notifier);
deba@2079:       }
deba@1697: 
deba@2079:       
deba@2079:     protected:
deba@1697: 
deba@2079:       virtual void add(const GraphEdge& ge) {
deba@2079:         adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
deba@2079:       }
deba@2079:       virtual void add(const std::vector<GraphEdge>& ge) {
deba@2079:         std::vector<Edge> edges;
deba@2079:         for (int i = 0; i < (int)ge.size(); ++i) {
deba@2079:           edges.push_back(AdaptorBase::edge(ge[i]));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Edge()).add(edges);
deba@2079:       }
deba@2079:       virtual void erase(const GraphEdge& ge) {
deba@2079:         adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
deba@2079:       }
deba@2079:       virtual void erase(const std::vector<GraphEdge>& ge) {
deba@2079:         std::vector<Edge> edges;
deba@2079:         for (int i = 0; i < (int)ge.size(); ++i) {
deba@2079:           edges.push_back(AdaptorBase::edge(ge[i]));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Edge()).erase(edges);
deba@2079:       }
deba@2079:       virtual void build() {
deba@2079:         std::vector<Edge> edges;
deba@2079:         const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079:         GraphEdge it;
deba@2079:         for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079:           edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Edge()).add(edges);
deba@2079:       }
deba@2079:       virtual void clear() {
deba@2079:         std::vector<Edge> edges;
deba@2079:         const typename Parent::Notifier* notifier = Parent::getNotifier();
deba@2079:         GraphEdge it;
deba@2079:         for (notifier->first(it); it != INVALID; notifier->next(it)) {
deba@2079:           edges.push_back(AdaptorBase::Parent::edge(it));
deba@2079:         }
deba@2079:         adaptor->getNotifier(Edge()).erase(edges);
deba@2079:       }
deba@1697: 
deba@2079:       const AdaptorBase* adaptor;
deba@2079:     };
deba@2079: 
deba@2079: 
deba@2079:     mutable NodeNotifier node_notifier;
deba@2079:     mutable EdgeNotifier edge_notifier;
deba@2079: 
deba@2079:     NodeNotifierProxy node_notifier_proxy;
deba@2079:     EdgeNotifierProxy edge_notifier_proxy;
deba@2079: 
deba@2079:   };
deba@2079: 
deba@2079:   /// \ingroup graph_adaptors
deba@2079:   ///
deba@2081:   /// \brief Split graph adaptor class
deba@2079:   /// 
deba@2079:   /// This is an graph adaptor which splits all node into an in-node
deba@2079:   /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
deba@2079:   /// node in the graph with two node, \f$ u_{in} \f$ node and 
deba@2079:   /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the 
deba@2079:   /// original graph the new target of the edge will be \f$ u_{in} \f$ and
deba@2079:   /// similarly the source of the original \f$ (u, v) \f$ edge will be
deba@2079:   /// \f$ u_{out} \f$.  The adaptor will add for each node in the 
deba@2079:   /// original graph an additional edge which will connect 
deba@2079:   /// \f$ (u_{in}, u_{out}) \f$.
deba@2079:   ///
deba@2079:   /// The aim of this class is to run algorithm with node costs if the 
deba@2079:   /// algorithm can use directly just edge costs. In this case we should use
deba@2079:   /// a \c SplitGraphAdaptor and set the node cost of the graph to the
deba@2079:   /// bind edge in the adapted graph.
deba@2079:   /// 
deba@2079:   /// By example a maximum flow algoritm can compute how many edge
deba@2079:   /// disjoint paths are in the graph. But we would like to know how
deba@2079:   /// many node disjoint paths are in the graph. First we have to
deba@2079:   /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
deba@2079:   /// algorithm on the adapted graph. The bottleneck of the flow will
deba@2079:   /// be the bind edges which bounds the flow with the count of the
deba@2079:   /// node disjoint paths.
deba@2079:   ///
deba@2079:   ///\code
deba@2079:   ///
deba@2079:   /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
deba@2079:   ///
deba@2079:   /// SGraph sgraph(graph);
deba@2079:   ///
deba@2079:   /// typedef ConstMap<SGraph::Edge, int> SCapacity;
deba@2079:   /// SCapacity scapacity(1);
deba@2079:   ///
deba@2079:   /// SGraph::EdgeMap<int> sflow(sgraph);
deba@2079:   ///
deba@2079:   /// Preflow<SGraph, int, SCapacity> 
deba@2079:   ///   spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),  
deba@2079:   ///            scapacity, sflow);
deba@2079:   ///                                            
deba@2079:   /// spreflow.run();
deba@2079:   ///
deba@2079:   ///\endcode
deba@2079:   ///
deba@2079:   /// The result of the mamixum flow on the original graph
deba@2079:   /// shows the next figure:
deba@2079:   ///
deba@2079:   /// \image html edge_disjoint.png
deba@2079:   /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
deba@2079:   /// 
deba@2079:   /// And the maximum flow on the adapted graph:
deba@2079:   ///
deba@2079:   /// \image html node_disjoint.png
deba@2079:   /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
deba@2079:   ///
deba@2079:   /// The second solution contains just 3 disjoint paths while the first 4.
deba@2084:   /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
deba@2079:   ///
deba@2079:   /// This graph adaptor is fully conform to the 
alpar@2260:   /// \ref concepts::Graph "Graph" concept and
deba@2079:   /// contains some additional member functions and types. The 
deba@2079:   /// documentation of some member functions may be found just in the
deba@2079:   /// SplitGraphAdaptorBase class.
deba@2079:   ///
deba@2079:   /// \sa SplitGraphAdaptorBase
deba@2079:   template <typename _Graph>
deba@2079:   class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
deba@2079:   public:
deba@2079:     typedef AlterableSplitGraphAdaptor<_Graph> Parent;
deba@2079: 
deba@2079:     typedef typename Parent::Node Node;
deba@2079:     typedef typename Parent::Edge Edge;
deba@2079: 
deba@2079:     /// \brief Constructor of the adaptor.
deba@2079:     ///
deba@2079:     /// Constructor of the adaptor.
deba@2079:     SplitGraphAdaptor(_Graph& graph) {
deba@2079:       Parent::setGraph(graph);
deba@2079:     }
deba@2079: 
deba@2079:     /// \brief NodeMap combined from two original NodeMap
deba@2079:     ///
deba@2079:     /// This class adapt two of the original graph NodeMap to
deba@2079:     /// get a node map on the adapted graph.
deba@2079:     template <typename InNodeMap, typename OutNodeMap>
deba@2079:     class CombinedNodeMap {
deba@2079:     public:
deba@2079: 
deba@2079:       typedef Node Key;
deba@2079:       typedef typename InNodeMap::Value Value;
deba@2079: 
deba@2079:       /// \brief Constructor
deba@2079:       ///
deba@2079:       /// Constructor.
deba@2079:       CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap) 
deba@2079: 	: inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
deba@2079: 
deba@2079:       /// \brief The subscript operator.
deba@2079:       ///
deba@2079:       /// The subscript operator.
deba@2079:       Value& operator[](const Key& key) {
deba@2079: 	if (Parent::inNode(key)) {
deba@2079: 	  return inNodeMap[key];
deba@2079: 	} else {
deba@2079: 	  return outNodeMap[key];
deba@2079: 	}
deba@2079:       }
deba@2079: 
deba@2079:       /// \brief The const subscript operator.
deba@2079:       ///
deba@2079:       /// The const subscript operator.
deba@2079:       Value operator[](const Key& key) const {
deba@2079: 	if (Parent::inNode(key)) {
deba@2079: 	  return inNodeMap[key];
deba@2079: 	} else {
deba@2079: 	  return outNodeMap[key];
deba@2079: 	}
deba@2079:       }
deba@2079: 
deba@2079:       /// \brief The setter function of the map.
deba@2079:       /// 
deba@2079:       /// The setter function of the map.
deba@2079:       void set(const Key& key, const Value& value) {
deba@2079: 	if (Parent::inNode(key)) {
deba@2079: 	  inNodeMap.set(key, value);
deba@2079: 	} else {
deba@2079: 	  outNodeMap.set(key, value);
deba@2079: 	}
deba@2079:       }
deba@2079:       
deba@2079:     private:
deba@2079:       
deba@2079:       InNodeMap& inNodeMap;
deba@2079:       OutNodeMap& outNodeMap;
deba@2079:       
deba@2079:     };
deba@2079: 
deba@2079: 
deba@2079:     /// \brief Just gives back a combined node map.
deba@2079:     /// 
deba@2079:     /// Just gives back a combined node map.
deba@2079:     template <typename InNodeMap, typename OutNodeMap>
deba@2079:     static CombinedNodeMap<InNodeMap, OutNodeMap> 
deba@2079:     combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
deba@2079:       return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
deba@2079:     }
deba@2079: 
deba@2079:     template <typename InNodeMap, typename OutNodeMap>
deba@2079:     static CombinedNodeMap<const InNodeMap, OutNodeMap> 
deba@2079:     combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
deba@2079:       return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
deba@2079:     }
deba@2079: 
deba@2079:     template <typename InNodeMap, typename OutNodeMap>
deba@2079:     static CombinedNodeMap<InNodeMap, const OutNodeMap> 
deba@2079:     combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
deba@2079:       return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
deba@2079:     }
deba@2079: 
deba@2079:     template <typename InNodeMap, typename OutNodeMap>
deba@2079:     static CombinedNodeMap<const InNodeMap, const OutNodeMap> 
deba@2079:     combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
deba@2079:       return CombinedNodeMap<const InNodeMap, 
deba@2079:         const OutNodeMap>(in_map, out_map);
deba@2079:     }
deba@2079: 
deba@2079:     /// \brief EdgeMap combined from an original EdgeMap and NodeMap
deba@2079:     ///
deba@2079:     /// This class adapt an original graph EdgeMap and NodeMap to
deba@2079:     /// get an edge map on the adapted graph.
deba@2079:     template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079:     class CombinedEdgeMap 
deba@2079:       : public MapBase<Edge, typename GraphEdgeMap::Value> {
deba@2079:     public:
deba@2079:       typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
deba@2079: 
deba@2079:       typedef typename Parent::Key Key;
deba@2079:       typedef typename Parent::Value Value;
deba@2079: 
deba@2079:       /// \brief Constructor
deba@2079:       ///
deba@2079:       /// Constructor.
deba@2079:       CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map) 
deba@2079: 	: edge_map(_edge_map), node_map(_node_map) {}
deba@2079: 
deba@2079:       /// \brief The subscript operator.
deba@2079:       ///
deba@2079:       /// The subscript operator.
deba@2079:       void set(const Edge& edge, const Value& val) {
deba@2079: 	if (Parent::origEdge(edge)) {
deba@2079: 	  edge_map.set(edge, val);
deba@2079: 	} else {
deba@2079: 	  node_map.set(edge, val);
deba@2079: 	}
deba@2079:       }
deba@2079: 
deba@2079:       /// \brief The const subscript operator.
deba@2079:       ///
deba@2079:       /// The const subscript operator.
deba@2079:       Value operator[](const Key& edge) const {
deba@2079: 	if (Parent::origEdge(edge)) {
deba@2079: 	  return edge_map[edge];
deba@2079: 	} else {
deba@2079: 	  return node_map[edge];
deba@2079: 	}
deba@2079:       }      
deba@2079: 
deba@2079:       /// \brief The const subscript operator.
deba@2079:       ///
deba@2079:       /// The const subscript operator.
deba@2079:       Value& operator[](const Key& edge) {
deba@2079: 	if (Parent::origEdge(edge)) {
deba@2079: 	  return edge_map[edge];
deba@2079: 	} else {
deba@2079: 	  return node_map[edge];
deba@2079: 	}
deba@2079:       }      
deba@2079:       
deba@2079:     private:
deba@2079:       GraphEdgeMap& edge_map;
deba@2079:       GraphNodeMap& node_map;
deba@2079:     };
deba@2079:                     
deba@2079:     /// \brief Just gives back a combined edge map.
deba@2079:     /// 
deba@2079:     /// Just gives back a combined edge map.
deba@2079:     template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079:     static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap> 
deba@2079:     combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
deba@2079:       return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
deba@2079:     }
deba@2079: 
deba@2079:     template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079:     static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap> 
deba@2079:     combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
deba@2079:       return CombinedEdgeMap<const GraphEdgeMap, 
deba@2079:         GraphNodeMap>(edge_map, node_map);
deba@2079:     }
deba@2079: 
deba@2079:     template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079:     static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap> 
deba@2079:     combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
deba@2079:       return CombinedEdgeMap<GraphEdgeMap, 
deba@2079:         const GraphNodeMap>(edge_map, node_map);
deba@2079:     }
deba@2079: 
deba@2079:     template <typename GraphEdgeMap, typename GraphNodeMap>
deba@2079:     static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap> 
deba@2079:     combinedEdgeMap(const GraphEdgeMap& edge_map, 
deba@2079:                     const GraphNodeMap& node_map) {
deba@2079:       return CombinedEdgeMap<const GraphEdgeMap, 
deba@2079:         const GraphNodeMap>(edge_map, node_map);
deba@2079:     }
deba@2079: 
deba@2079:   };
deba@2079: 
deba@2084:   /// \brief Just gives back a split graph adaptor
deba@2084:   ///
deba@2084:   /// Just gives back a split graph adaptor
deba@2084:   template<typename Graph>
deba@2084:   SplitGraphAdaptor<Graph>
deba@2084:   splitGraphAdaptor(const Graph& graph) {
deba@2084:     return SplitGraphAdaptor<Graph>(graph);
deba@2084:   }
deba@2084: 
deba@1697: 
alpar@921: } //namespace lemon
marci@556: 
alpar@1401: #endif //LEMON_GRAPH_ADAPTOR_H
marci@556: