alpar@906: /* -*- C++ -*-
alpar@921:  * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
alpar@906:  *
alpar@906:  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906:  * (Egervary Combinatorial Optimization Research Group, 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@921: #ifndef LEMON_GRAPH_WRAPPER_H
alpar@921: #define LEMON_GRAPH_WRAPPER_H
marci@556: 
marci@556: ///\ingroup gwrappers
marci@556: ///\file
marci@556: ///\brief Several graph wrappers.
marci@556: ///
marci@556: ///This file contains several useful graph wrapper functions.
marci@556: ///
marci@556: ///\author Marton Makai
marci@556: 
alpar@921: #include <lemon/invalid.h>
alpar@921: #include <lemon/maps.h>
alpar@921: #include <lemon/map_defines.h>
alpar@774: #include <iostream>
marci@556: 
alpar@921: namespace lemon {
marci@556: 
marci@556:   // Graph wrappers
marci@556: 
marci@556:   /// \addtogroup gwrappers
marci@923:   /// The main parts of LEMON are the different graph structures, 
marci@556:   /// generic graph algorithms, graph concepts which couple these, and 
marci@556:   /// graph wrappers. While the previous ones are more or less clear, the 
marci@556:   /// latter notion needs further explanation.
marci@556:   /// Graph wrappers are graph classes which serve for considering graph 
marci@556:   /// structures in different ways. A short example makes the notion much 
marci@556:   /// clearer. 
marci@556:   /// Suppose that we have an instance \c g of a directed graph
marci@556:   /// type say \c ListGraph and an algorithm 
marci@556:   /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
marci@556:   /// is needed to run on the reversely oriented graph. 
marci@556:   /// It may be expensive (in time or in memory usage) to copy 
marci@556:   /// \c g with the reverse orientation. 
marci@556:   /// Thus, a wrapper class
marci@556:   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
marci@556:   /// The code looks as follows
marci@556:   /// \code
marci@556:   /// ListGraph g;
marci@556:   /// RevGraphWrapper<ListGraph> rgw(g);
marci@556:   /// int result=algorithm(rgw);
marci@556:   /// \endcode
marci@556:   /// After running the algorithm, the original graph \c g 
marci@556:   /// remains untouched. Thus the graph wrapper used above is to consider the 
marci@556:   /// original graph with reverse orientation. 
marci@556:   /// This techniques gives rise to an elegant code, and 
marci@556:   /// based on stable graph wrappers, complex algorithms can be 
marci@556:   /// implemented easily. 
marci@556:   /// In flow, circulation and bipartite matching problems, the residual 
marci@556:   /// graph is of particular importance. Combining a wrapper implementing 
marci@556:   /// this, shortest path algorithms and minimum mean cycle algorithms, 
marci@556:   /// a range of weighted and cardinality optimization algorithms can be 
marci@556:   /// obtained. For lack of space, for other examples, 
marci@556:   /// the interested user is referred to the detailed documentation of graph 
marci@556:   /// wrappers. 
marci@556:   /// The behavior of graph wrappers can be very different. Some of them keep 
marci@556:   /// capabilities of the original graph while in other cases this would be 
marci@556:   /// meaningless. This means that the concepts that they are a model of depend 
marci@556:   /// on the graph wrapper, and the wrapped graph(s). 
marci@556:   /// If an edge of \c rgw is deleted, this is carried out by 
marci@556:   /// deleting the corresponding edge of \c g. But for a residual 
marci@556:   /// graph, this operation has no sense. 
marci@556:   /// Let we stand one more example here to simplify your work. 
marci@556:   /// wrapper class
marci@556:   /// \code template<typename Graph> class RevGraphWrapper; \endcode 
marci@556:   /// has constructor 
marci@556:   /// <tt> RevGraphWrapper(Graph& _g)</tt>. 
marci@556:   /// This means that in a situation, 
marci@556:   /// when a <tt> const ListGraph& </tt> reference to a graph is given, 
marci@556:   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
marci@556:   /// \code
marci@556:   /// int algorithm1(const ListGraph& g) {
marci@556:   ///   RevGraphWrapper<const ListGraph> rgw(g);
marci@556:   ///   return algorithm2(rgw);
marci@556:   /// }
marci@556:   /// \endcode
marci@556: 
marci@556:   /// \addtogroup gwrappers
marci@556:   /// @{
marci@556: 
marci@556:   ///Base type for the Graph Wrappers
marci@556: 
alpar@879:   ///\warning Graph wrappers are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
marci@923:   /// This is the base type for most of LEMON graph wrappers. 
marci@923:   /// This class implements a trivial graph wrapper i.e. it only wraps the 
marci@923:   /// functions and types of the graph. The purpose of this class is to 
marci@923:   /// make easier implementing graph wrappers. E.g. if a wrapper is 
marci@923:   /// considered which differs from the wrapped graph only in some of its 
marci@923:   /// functions or types, then it can be derived from GraphWrapper, and only the 
marci@923:   /// differences should be implemented.
marci@556:   ///
marci@612:   ///\author Marton Makai 
marci@556:   template<typename Graph>
marci@556:   class GraphWrapper {
marci@556:   protected:
marci@556:     Graph* graph;
marci@556:     GraphWrapper() : graph(0) { }
marci@556:     void setGraph(Graph& _graph) { graph=&_graph; }
marci@556: 
marci@556:   public:
marci@556:     typedef Graph BaseGraph;
marci@556:     typedef Graph ParentGraph;
marci@556: 
marci@556:     GraphWrapper(Graph& _graph) : graph(&_graph) { }
alpar@774:     GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
marci@556:  
alpar@774:     typedef typename Graph::Node Node;
alpar@774:     class NodeIt : public Node { 
alpar@774:       const GraphWrapper<Graph>* gw;
marci@556:       friend class GraphWrapper<Graph>;
marci@556:      public:
marci@556:       NodeIt() { }
alpar@774:       NodeIt(Invalid i) : Node(i) { }
alpar@774:       NodeIt(const GraphWrapper<Graph>& _gw) : 
alpar@774: 	Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
alpar@774:       NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 
alpar@774: 	Node(n), gw(&_gw) { }
alpar@774:       NodeIt& operator++() { 
alpar@774: 	*(static_cast<Node*>(this))=
alpar@774: 	  ++(typename Graph::NodeIt(*(gw->graph), *this));
alpar@774: 	return *this; 
alpar@774:       }
marci@556:     };
alpar@774:     typedef typename Graph::Edge Edge;
alpar@774:     class OutEdgeIt : public Edge { 
alpar@774:       const GraphWrapper<Graph>* gw;
marci@556:       friend class GraphWrapper<Graph>;
alpar@774:      public:
alpar@774:       OutEdgeIt() { }
alpar@774:       OutEdgeIt(Invalid i) : Edge(i) { }
alpar@774:       OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 
alpar@774: 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
alpar@774:       OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 
alpar@774: 	Edge(e), gw(&_gw) { }
alpar@774:       OutEdgeIt& operator++() { 
alpar@774: 	*(static_cast<Edge*>(this))=
alpar@774: 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
alpar@774: 	return *this; 
alpar@774:       }
marci@556:     };
alpar@774:     class InEdgeIt : public Edge { 
alpar@774:       const GraphWrapper<Graph>* gw;
marci@556:       friend class GraphWrapper<Graph>;
alpar@774:      public:
marci@556:       InEdgeIt() { }
alpar@774:       InEdgeIt(Invalid i) : Edge(i) { }
alpar@774:       InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 
alpar@774: 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
alpar@774:       InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 
alpar@774: 	Edge(e), gw(&_gw) { }
alpar@774:       InEdgeIt& operator++() { 
alpar@774: 	*(static_cast<Edge*>(this))=
alpar@774: 	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));
alpar@774: 	return *this; 
alpar@774:       }
marci@556:     };
alpar@774:     class EdgeIt : public Edge { 
alpar@774:       const GraphWrapper<Graph>* gw;
marci@556:       friend class GraphWrapper<Graph>;
alpar@774:      public:
marci@556:       EdgeIt() { }
alpar@774:       EdgeIt(Invalid i) : Edge(i) { }
alpar@774:       EdgeIt(const GraphWrapper<Graph>& _gw) : 
alpar@774: 	Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
alpar@774:       EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 
marci@777: 	Edge(e), gw(&_gw) { }
alpar@774:       EdgeIt& operator++() { 
alpar@774: 	*(static_cast<Edge*>(this))=
alpar@774: 	  ++(typename Graph::EdgeIt(*(gw->graph), *this));
alpar@774: 	return *this; 
alpar@774:       }
marci@556:     };
marci@556:    
marci@556:     NodeIt& first(NodeIt& i) const { 
marci@556:       i=NodeIt(*this); return i;
marci@556:     }
marci@556:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@556:       i=OutEdgeIt(*this, p); return i;
marci@556:     }
marci@556:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@556:       i=InEdgeIt(*this, p); return i;
marci@556:     }
marci@556:     EdgeIt& first(EdgeIt& i) const { 
marci@556:       i=EdgeIt(*this); return i;
marci@556:     }
marci@556: 
marci@556:     Node tail(const Edge& e) const { 
marci@556:       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
marci@556:     Node head(const Edge& e) const { 
marci@556:       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
marci@556: 
marci@556:     int nodeNum() const { return graph->nodeNum(); }
marci@556:     int edgeNum() const { return graph->edgeNum(); }
marci@556:   
marci@556:     Node addNode() const { return Node(graph->addNode()); }
marci@556:     Edge addEdge(const Node& tail, const Node& head) const { 
marci@556:       return Edge(graph->addEdge(tail, head)); }
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:     
alpar@736:     bool forward(const Edge& e) const { return graph->forward(e); }
alpar@736:     bool backward(const Edge& e) const { return graph->backward(e); }
marci@739: 
marci@739:     int id(const Node& v) const { return graph->id(v); }
marci@739:     int id(const Edge& e) const { return graph->id(e); }
marci@650:     
marci@738:     Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
marci@650: 
marci@556: 
deba@877:     IMPORT_NODE_MAP(Graph, *(gw.graph), GraphWrapper, gw);    
deba@877:     IMPORT_EDGE_MAP(Graph, *(gw.graph), GraphWrapper, gw);
deba@877:     
deba@877: 
marci@556:   };
marci@556: 
marci@569: 
marci@569: 
marci@556:   /// A graph wrapper which reverses the orientation of the edges.
marci@556: 
alpar@879:   ///\warning Graph wrappers are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
marci@923:   /// Let \f$G=(V, A)\f$ be a directed graph and 
marci@923:   /// suppose that a graph instange \c g of type 
marci@923:   /// \c ListGraph implements \f$G\f$.
marci@923:   /// \code
marci@923:   /// ListGraph g;
marci@923:   /// \endcode
marci@923:   /// For each directed edge 
marci@923:   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by 
marci@923:   /// reversing its orientation. 
marci@923:   /// Then RevGraphWrapper implements the graph structure with node-set 
marci@923:   /// \f$V\f$ and edge-set 
marci@923:   /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be 
marci@923:   /// reversing the orientation of its edges. The following code shows how 
marci@923:   /// such an instance can be constructed.
marci@923:   /// \code
marci@923:   /// RevGraphWrapper<ListGraph> gw(g);
marci@923:   /// \endcode
marci@556:   ///\author Marton Makai
marci@556:   template<typename Graph>
marci@556:   class RevGraphWrapper : public GraphWrapper<Graph> {
marci@650:   public:
marci@650:     typedef GraphWrapper<Graph> Parent; 
marci@556:   protected:
marci@612:     RevGraphWrapper() : GraphWrapper<Graph>() { }
marci@556:   public:
marci@556:     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
alpar@774:     RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
marci@556: 
marci@556:     typedef typename GraphWrapper<Graph>::Node Node;
marci@556:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@792:     //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
marci@792:     //because this does not work is some of them are not defined in the 
marci@792:     //original graph. The problem with this is that typedef-ed stuff 
marci@792:     //are instantiated in c++.
alpar@774:     class OutEdgeIt : public Edge { 
alpar@774:       const RevGraphWrapper<Graph>* gw;
marci@556:       friend class GraphWrapper<Graph>;
alpar@774:      public:
marci@556:       OutEdgeIt() { }
alpar@774:       OutEdgeIt(Invalid i) : Edge(i) { }
alpar@774:       OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 
alpar@774: 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
alpar@774:       OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 
alpar@774: 	Edge(e), gw(&_gw) { }
alpar@774:       OutEdgeIt& operator++() { 
alpar@774: 	*(static_cast<Edge*>(this))=
alpar@774: 	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));
alpar@774: 	return *this; 
alpar@774:       }
marci@556:     };
alpar@774:     class InEdgeIt : public Edge { 
alpar@774:       const RevGraphWrapper<Graph>* gw;
marci@556:       friend class GraphWrapper<Graph>;
alpar@774:      public:
marci@556:       InEdgeIt() { }
alpar@774:       InEdgeIt(Invalid i) : Edge(i) { }
alpar@774:       InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 
alpar@774: 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
alpar@774:       InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 
alpar@774: 	Edge(e), gw(&_gw) { }
alpar@774:       InEdgeIt& operator++() { 
alpar@774: 	*(static_cast<Edge*>(this))=
alpar@774: 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
alpar@774: 	return *this; 
alpar@774:       }
marci@556:     };
marci@556: 
marci@556:     using GraphWrapper<Graph>::first;
marci@556:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@556:       i=OutEdgeIt(*this, p); return i;
marci@556:     }
marci@556:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@556:       i=InEdgeIt(*this, p); return i;
marci@556:     }
marci@556: 
marci@556:     Node tail(const Edge& e) const { 
marci@556:       return GraphWrapper<Graph>::head(e); }
marci@556:     Node head(const Edge& e) const { 
marci@556:       return GraphWrapper<Graph>::tail(e); }
marci@556: 
deba@891:     //    KEEP_MAPS(Parent, RevGraphWrapper);
deba@877: 
marci@556:   };
marci@556: 
marci@775: 
marci@775: 
marci@930:   /*! \brief A graph wrapper for hiding nodes and edges from a graph.
marci@556:   
marci@930:   \warning Graph wrappers are in even more experimental state than the other
marci@930:   parts of the lib. Use them at you own risk.
marci@930:   
marci@930:   This wrapper shows a graph with filtered node-set and 
marci@930:   edge-set. 
marci@930:   Given a bool-valued map on the node-set and one on 
marci@930:   the edge-set of the graph, the iterators show only the objects 
marci@930:   having true value. We have to note that this does not mean that an 
marci@930:   induced subgraph is obtained, the node-iterator cares only the filter 
marci@930:   on the node-set, and the edge-iterators care only the filter on the 
marci@930:   edge-set.
marci@930:   \code
marci@930:   typedef SmartGraph Graph;
marci@930:   Graph g;
marci@930:   typedef Graph::Node Node;
marci@930:   typedef Graph::Edge Edge;
marci@930:   Node u=g.addNode(); //node of id 0
marci@930:   Node v=g.addNode(); //node of id 1
marci@930:   Node e=g.addEdge(u, v); //edge of id 0
marci@930:   Node f=g.addEdge(v, u); //edge of id 1
marci@930:   Graph::NodeMap<bool> nm(g, true);
marci@930:   nm.set(u, false);
marci@930:   Graph::EdgeMap<bool> em(g, true);
marci@930:   em.set(e, false);
marci@930:   typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
marci@930:   SubGW gw(g, nm, em);
marci@930:   for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
marci@930:   std::cout << ":-)" << std::endl;
marci@930:   for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
marci@930:   \endcode
marci@930:   The output of the above code is the following.
marci@930:   \code
marci@930:   1
marci@930:   :-)
marci@930:   1
marci@930:   \endcode
marci@930:   Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
marci@930:   \c Graph::Node that is why \c g.id(n) can be applied.
marci@930: 
marci@933:   For other examples see also the documentation of NodeSubGraphWrapper and 
marci@933:   EdgeSubGraphWrapper.
marci@930: 
marci@930:   \author Marton Makai
marci@930:   */
marci@556:   template<typename Graph, typename NodeFilterMap, 
marci@556: 	   typename EdgeFilterMap>
marci@556:   class SubGraphWrapper : public GraphWrapper<Graph> {
marci@650:   public:
marci@650:     typedef GraphWrapper<Graph> Parent;
marci@556:   protected:
marci@556:     NodeFilterMap* node_filter_map;
marci@556:     EdgeFilterMap* edge_filter_map;
marci@556: 
marci@612:     SubGraphWrapper() : GraphWrapper<Graph>(), 
marci@556: 			node_filter_map(0), edge_filter_map(0) { }
marci@556:     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@556:       node_filter_map=&_node_filter_map;
marci@556:     }
marci@556:     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@556:       edge_filter_map=&_edge_filter_map;
marci@556:     }
marci@556:     
marci@556:   public:
marci@556:     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
marci@556: 		    EdgeFilterMap& _edge_filter_map) : 
marci@556:       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
marci@556:       edge_filter_map(&_edge_filter_map) { }  
marci@556: 
marci@556:     typedef typename GraphWrapper<Graph>::Node Node;
marci@775:     class NodeIt : public Node { 
marci@775:       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@775:     public:
marci@556:       NodeIt() { }
marci@775:       NodeIt(Invalid i) : Node(i) { }
marci@775:       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 
marci@854: 	Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { 
marci@854: 	while (*static_cast<Node*>(this)!=INVALID && 
marci@861: 	       !(*(gw->node_filter_map))[*this]) 
marci@854: 	  *(static_cast<Node*>(this))=
marci@854: 	    ++(typename Graph::NodeIt(*(gw->graph), *this));
marci@854:       }
marci@775:       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
marci@775: 	     const Node& n) : 
marci@775: 	Node(n), gw(&_gw) { }
marci@775:       NodeIt& operator++() { 
marci@775: 	*(static_cast<Node*>(this))=
marci@775: 	  ++(typename Graph::NodeIt(*(gw->graph), *this));
marci@775: 	while (*static_cast<Node*>(this)!=INVALID && 
marci@775: 	       !(*(gw->node_filter_map))[*this]) 
marci@775: 	  *(static_cast<Node*>(this))=
marci@775: 	    ++(typename Graph::NodeIt(*(gw->graph), *this));
marci@775: 	return *this; 
marci@556:       }
marci@556:     };
marci@556:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@775:     class OutEdgeIt : public Edge { 
marci@775:       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@775:       OutEdgeIt(Invalid i) : Edge(i) { }
marci@775:       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 
marci@854: 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { 
marci@854: 	while (*static_cast<Edge*>(this)!=INVALID && 
marci@854: 	       !(*(gw->edge_filter_map))[*this]) 
marci@854: 	  *(static_cast<Edge*>(this))=
marci@854: 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@854:       }
marci@775:       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
marci@775: 	     const Edge& e) : 
marci@775: 	Edge(e), gw(&_gw) { }
marci@775:       OutEdgeIt& operator++() { 
marci@775: 	*(static_cast<Edge*>(this))=
marci@775: 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@775: 	while (*static_cast<Edge*>(this)!=INVALID && 
marci@775: 	       !(*(gw->edge_filter_map))[*this]) 
marci@775: 	  *(static_cast<Edge*>(this))=
marci@775: 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@775: 	return *this; 
marci@556:       }
marci@556:     };
marci@775:     class InEdgeIt : public Edge { 
marci@775:       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@556:     public:
marci@556:       InEdgeIt() { }
marci@775:       //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
marci@775:       InEdgeIt(Invalid i) : Edge(i) { }
marci@775:       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 
marci@854: 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { 
marci@854: 	while (*static_cast<Edge*>(this)!=INVALID && 
marci@854: 	       !(*(gw->edge_filter_map))[*this]) 
marci@854: 	  *(static_cast<Edge*>(this))=
marci@854: 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@854:       }
marci@775:       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
marci@775: 	     const Edge& e) : 
marci@775: 	Edge(e), gw(&_gw) { }
marci@775:       InEdgeIt& operator++() { 
marci@775: 	*(static_cast<Edge*>(this))=
marci@775: 	  ++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@775: 	while (*static_cast<Edge*>(this)!=INVALID && 
marci@775: 	       !(*(gw->edge_filter_map))[*this]) 
marci@775: 	  *(static_cast<Edge*>(this))=
marci@775: 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@775: 	return *this; 
marci@556:       }
marci@556:     };
marci@775:     class EdgeIt : public Edge { 
marci@775:       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@556:     public:
marci@556:       EdgeIt() { }
marci@775:       EdgeIt(Invalid i) : Edge(i) { }
marci@775:       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 
marci@854: 	Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { 
marci@854: 	while (*static_cast<Edge*>(this)!=INVALID && 
marci@854: 	       !(*(gw->edge_filter_map))[*this]) 
marci@854: 	  *(static_cast<Edge*>(this))=
marci@854: 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@854:       }
marci@775:       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 
marci@775: 	     const Edge& e) : 
marci@775: 	Edge(e), gw(&_gw) { }
marci@775:       EdgeIt& operator++() { 
marci@775: 	*(static_cast<Edge*>(this))=
marci@775: 	  ++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@775: 	while (*static_cast<Edge*>(this)!=INVALID && 
marci@775: 	       !(*(gw->edge_filter_map))[*this]) 
marci@775: 	  *(static_cast<Edge*>(this))=
marci@775: 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@775: 	return *this; 
marci@556:       }
marci@556:     };
marci@556: 
marci@556:     NodeIt& first(NodeIt& i) const { 
marci@556:       i=NodeIt(*this); return i;
marci@556:     }
marci@556:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@556:       i=OutEdgeIt(*this, p); return i;
marci@556:     }
marci@556:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@556:       i=InEdgeIt(*this, p); return i;
marci@556:     }
marci@556:     EdgeIt& first(EdgeIt& i) const { 
marci@556:       i=EdgeIt(*this); return i;
marci@556:     }
marci@556:     
marci@561:     /// This function hides \c n in the graph, i.e. the iteration 
marci@561:     /// jumps over it. This is done by simply setting the value of \c n  
marci@561:     /// to be false in the corresponding node-map.
marci@556:     void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@561: 
marci@561:     /// This function hides \c e in the graph, i.e. the iteration 
marci@561:     /// jumps over it. This is done by simply setting the value of \c e  
marci@561:     /// to be false in the corresponding edge-map.
marci@556:     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@556: 
marci@561:     /// The value of \c n is set to be true in the node-map which stores 
marci@561:     /// hide information. If \c n was hidden previuosly, then it is shown 
marci@561:     /// again
marci@561:      void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@561: 
marci@561:     /// The value of \c e is set to be true in the edge-map which stores 
marci@561:     /// hide information. If \c e was hidden previuosly, then it is shown 
marci@561:     /// again
marci@556:     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@556: 
marci@561:     /// Returns true if \c n is hidden.
marci@561:     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@561: 
marci@561:     /// Returns true if \c n is hidden.
marci@561:     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@593: 
marci@792:     /// \warning This is a linear time operation and works only if 
marci@792:     /// \c Graph::NodeIt is defined.
marci@593:     int nodeNum() const { 
marci@593:       int i=0;
marci@792:       for (NodeIt n(*this); n!=INVALID; ++n) ++i;
marci@593:       return i; 
marci@593:     }
marci@593: 
marci@792:     /// \warning This is a linear time operation and works only if 
marci@792:     /// \c Graph::EdgeIt is defined.
marci@593:     int edgeNum() const { 
marci@593:       int i=0;
marci@792:       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
marci@593:       return i; 
marci@593:     }
marci@593: 
deba@891:     //    KEEP_MAPS(Parent, SubGraphWrapper);
marci@556:   };
marci@556: 
marci@569: 
marci@933:   /*! \brief A wrapper for hiding nodes from a graph.
marci@933: 
marci@933:   \warning Graph wrappers are in even more experimental state than the other
marci@933:   parts of the lib. Use them at you own risk.
marci@933:   
marci@933:   A wrapper for hiding nodes from a graph.
marci@933:   This wrapper specializes SubGraphWrapper in the way that only the node-set 
marci@933:   can be filtered. Note that this does not mean of considering induced 
marci@933:   subgraph, the edge-iterators consider the original edge-set.
marci@933:   \author Marton Makai
marci@933:   */
marci@933:   template<typename Graph, typename NodeFilterMap>
marci@933:   class NodeSubGraphWrapper : 
marci@933:     public SubGraphWrapper<Graph, NodeFilterMap, 
marci@933: 			   ConstMap<typename Graph::Edge,bool> > {
marci@933:   public:
marci@933:     typedef SubGraphWrapper<Graph, NodeFilterMap, 
marci@933: 			    ConstMap<typename Graph::Edge,bool> > Parent;
marci@933:   protected:
marci@933:     ConstMap<typename Graph::Edge, bool> const_true_map;
marci@933:   public:
marci@933:     NodeSubGraphWrapper(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:     }
marci@933:   };
marci@933: 
marci@933: 
marci@932:   /*! \brief A wrapper for hiding edges from a graph.
marci@932: 
marci@932:   \warning Graph wrappers are in even more experimental state than the other
marci@932:   parts of the lib. Use them at you own risk.
marci@932:   
marci@932:   A wrapper for hiding edges from a graph.
marci@932:   This wrapper specializes SubGraphWrapper in the way that only the edge-set 
marci@933:   can be filtered. The usefulness of this wrapper is demonstrated in the 
marci@933:   problem of searching a maximum number of edge-disjoint shortest paths 
marci@933:   between 
marci@933:   two nodes \c s and \c t. Shortest here means being shortest w.r.t. 
marci@933:   non-negative edge-lengths. Note that 
marci@933:   the comprehension of the presented solution 
marci@933:   need's some knowledge from elementary combinatorial optimization. 
marci@933: 
marci@933:   If a single shortest path is to be 
marci@933:   searched between two nodes \c s and \c t, then this can be done easily by 
marci@933:   applying the Dijkstra algorithm class. What happens, if a maximum number of 
marci@933:   edge-disjoint shortest paths is to be computed. It can be proved that an 
marci@933:   edge can be in a shortest path if and only if it is tight with respect to 
marci@933:   the potential function computed by Dijkstra. Moreover, any path containing 
marci@933:   only such edges is a shortest one. Thus we have to compute a maximum number 
marci@933:   of edge-disjoint paths between \c s and \c t in the graph which has edge-set 
marci@933:   all the tight edges. The computation will be demonstrated on the following 
marci@933:   graph, which is read from a dimacs file.
marci@933:   
marci@933:   \dot
marci@933:   digraph lemon_dot_example {
marci@933:   node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933:   n0 [ label="0 (s)" ];
marci@933:   n1 [ label="1" ];
marci@933:   n2 [ label="2" ];
marci@933:   n3 [ label="3" ];
marci@933:   n4 [ label="4" ];
marci@933:   n5 [ label="5" ];
marci@933:   n6 [ label="6 (t)" ];
marci@933:   edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
marci@933:   n5 ->  n6 [ label="9, length:4" ];
marci@933:   n4 ->  n6 [ label="8, length:2" ];
marci@933:   n3 ->  n5 [ label="7, length:1" ];
marci@933:   n2 ->  n5 [ label="6, length:3" ];
marci@933:   n2 ->  n6 [ label="5, length:5" ];
marci@933:   n2 ->  n4 [ label="4, length:2" ];
marci@933:   n1 ->  n4 [ label="3, length:3" ];
marci@933:   n0 ->  n3 [ label="2, length:1" ];
marci@933:   n0 ->  n2 [ label="1, length:2" ];
marci@933:   n0 ->  n1 [ label="0, length:3" ];
marci@933:   }
marci@933:   \enddot
marci@933: 
marci@933:   \code
marci@933:   Graph g;
marci@933:   Node s, t;
marci@933:   LengthMap length(g);
marci@933: 
marci@933:   readDimacs(std::cin, g, length, s, t);
marci@933: 
marci@933:   cout << "edges with lengths (of form id, tail--length->head): " << endl;
marci@933:   for(EdgeIt e(g); e!=INVALID; ++e) 
marci@933:     cout << g.id(e) << ", " << g.id(g.tail(e)) << "--" 
marci@933:          << length[e] << "->" << g.id(g.head(e)) << endl;
marci@933: 
marci@933:   cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
marci@933:   \endcode
marci@933:   Next, the potential function is computed with Dijkstra.
marci@933:   \code
marci@933:   typedef Dijkstra<Graph, LengthMap> Dijkstra;
marci@933:   Dijkstra dijkstra(g, length);
marci@933:   dijkstra.run(s);
marci@933:   \endcode
marci@933:   Next, we consrtruct a map which filters the edge-set to the tight edges.
marci@933:   \code
marci@933:   typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
marci@933:     TightEdgeFilter;
marci@933:   TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
marci@933:   
marci@933:   typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
marci@933:   SubGW gw(g, tight_edge_filter);
marci@933:   \endcode
marci@933:   Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
marci@933:   with a max flow algorithm Preflow.
marci@933:   \code
marci@933:   ConstMap<Edge, int> const_1_map(1);
marci@933:   Graph::EdgeMap<int> flow(g, 0);
marci@933: 
marci@933:   Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
marci@933:     preflow(gw, s, t, const_1_map, flow);
marci@933:   preflow.run();
marci@933:   \endcode
marci@933:   Last, the output is:
marci@933:   \code  
marci@933:   cout << "maximum number of edge-disjoint shortest path: " 
marci@933:        << preflow.flowValue() << endl;
marci@933:   cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
marci@933:        << endl;
marci@933:   for(EdgeIt e(g); e!=INVALID; ++e) 
marci@933:     if (flow[e])
marci@933:       cout << " " << g.id(g.tail(e)) << "--" 
marci@933: 	   << length[e] << "->" << g.id(g.head(e)) << endl;
marci@933:   \endcode
marci@933:   The program has the following (expected :-)) output:
marci@933:   \code
marci@933:   edges with lengths (of form id, tail--length->head):
marci@933:    9, 5--4->6
marci@933:    8, 4--2->6
marci@933:    7, 3--1->5
marci@933:    6, 2--3->5
marci@933:    5, 2--5->6
marci@933:    4, 2--2->4
marci@933:    3, 1--3->4
marci@933:    2, 0--1->3
marci@933:    1, 0--2->2
marci@933:    0, 0--3->1
marci@933:   s: 0 t: 6
marci@933:   maximum number of edge-disjoint shortest path: 2
marci@933:   edges of the maximum number of edge-disjoint shortest s-t paths:
marci@933:    9, 5--4->6
marci@933:    8, 4--2->6
marci@933:    7, 3--1->5
marci@933:    4, 2--2->4
marci@933:    2, 0--1->3
marci@933:    1, 0--2->2
marci@933:   \endcode
marci@933: 
marci@932:   \author Marton Makai
marci@932:   */
marci@932:   template<typename Graph, typename EdgeFilterMap>
marci@932:   class EdgeSubGraphWrapper : 
marci@932:     public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 
marci@932: 			   EdgeFilterMap> {
marci@932:   public:
marci@932:     typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, 
marci@932: 			    EdgeFilterMap> Parent;
marci@932:   protected:
marci@932:     ConstMap<typename Graph::Node, bool> const_true_map;
marci@932:   public:
marci@932:     EdgeSubGraphWrapper(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:     }
marci@932:   };
marci@932: 
marci@569: 
marci@556:   template<typename Graph>
marci@556:   class UndirGraphWrapper : public GraphWrapper<Graph> {
marci@650:   public:
marci@650:     typedef GraphWrapper<Graph> Parent; 
marci@556:   protected:
marci@556:     UndirGraphWrapper() : GraphWrapper<Graph>() { }
marci@556:     
marci@556:   public:
marci@556:     typedef typename GraphWrapper<Graph>::Node Node;
marci@556:     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@556:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@556:     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
marci@556: 
marci@556:     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
marci@556: 
marci@556:     class OutEdgeIt {
marci@556:       friend class UndirGraphWrapper<Graph>;
marci@556:       bool out_or_in; //true iff out
marci@556:       typename Graph::OutEdgeIt out;
marci@556:       typename Graph::InEdgeIt in;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@556:       OutEdgeIt(const Invalid& i) : Edge(i) { }
marci@556:       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
marci@556: 	out_or_in=true; _G.graph->first(out, _n);
marci@556: 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
marci@556:       } 
marci@556:       operator Edge() const { 
marci@556: 	if (out_or_in) return Edge(out); else return Edge(in); 
marci@556:       }
marci@556:     };
marci@556: 
marci@556:     typedef OutEdgeIt InEdgeIt; 
marci@556: 
marci@556:     using GraphWrapper<Graph>::first;
marci@556:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@556:       i=OutEdgeIt(*this, p); return i;
marci@556:     }
marci@556: 
marci@556:     using GraphWrapper<Graph>::next;
alpar@878: 
marci@556:     OutEdgeIt& next(OutEdgeIt& e) const {
marci@556:       if (e.out_or_in) {
marci@556: 	typename Graph::Node n=this->graph->tail(e.out);
marci@556: 	this->graph->next(e.out);
marci@556: 	if (!this->graph->valid(e.out)) { 
marci@556: 	  e.out_or_in=false; this->graph->first(e.in, n); }
marci@556:       } else {
marci@556: 	this->graph->next(e.in);
marci@556:       }
marci@556:       return e;
marci@556:     }
marci@556: 
marci@556:     Node aNode(const OutEdgeIt& e) const { 
marci@556:       if (e.out_or_in) return this->graph->tail(e); else 
marci@556: 	return this->graph->head(e); }
marci@556:     Node bNode(const OutEdgeIt& e) const { 
marci@556:       if (e.out_or_in) return this->graph->head(e); else 
marci@556: 	return this->graph->tail(e); }
deba@877: 
deba@891:     //    KEEP_MAPS(Parent, UndirGraphWrapper);
deba@877: 
marci@556:   };
marci@556:   
marci@910: //   /// \brief An undirected graph template.
marci@910: //   ///
marci@910: //   ///\warning Graph wrappers are in even more experimental state than the other
marci@910: //   ///parts of the lib. Use them at your own risk.
marci@910: //   ///
marci@910: //   /// An undirected graph template.
marci@910: //   /// This class works as an undirected graph and a directed graph of 
marci@910: //   /// class \c Graph is used for the physical storage.
marci@910: //   /// \ingroup graphs
marci@556:   template<typename Graph>
marci@556:   class UndirGraph : public UndirGraphWrapper<Graph> {
marci@556:     typedef UndirGraphWrapper<Graph> Parent;
marci@556:   protected:
marci@556:     Graph gr;
marci@556:   public:
marci@556:     UndirGraph() : UndirGraphWrapper<Graph>() { 
marci@556:       Parent::setGraph(gr); 
marci@556:     }
deba@877: 
deba@891:     //    KEEP_MAPS(Parent, UndirGraph);
marci@556:   };
marci@556: 
marci@569: 
marci@650: 
marci@650:   ///\brief A wrapper for composing a subgraph of a 
marci@792:   /// bidirected graph made from a directed one. 
marci@612:   ///
alpar@911:   /// A wrapper for composing a subgraph of a 
alpar@911:   /// bidirected graph made from a directed one. 
alpar@911:   ///
alpar@879:   ///\warning Graph wrappers are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
marci@923:   /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge 
marci@923:   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
marci@923:   /// reversing its orientation. We are given moreover two bool valued 
marci@923:   /// maps on the edge-set, 
marci@923:   /// \f$forward\_filter\f$, and \f$backward\_filter\f$. 
marci@923:   /// SubBidirGraphWrapper implements the graph structure with node-set 
marci@923:   /// \f$V\f$ and edge-set 
marci@923:   /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$. 
marci@792:   /// The purpose of writing + instead of union is because parallel 
marci@923:   /// edges can arise. (Similarly, antiparallel edges also can arise).
marci@792:   /// In other words, a subgraph of the bidirected graph obtained, which 
marci@792:   /// is given by orienting the edges of the original graph in both directions.
marci@923:   /// As the oppositely directed edges are logically different, 
marci@923:   /// the maps are able to attach different values for them. 
marci@923:   ///
marci@923:   /// An example for such a construction is \c RevGraphWrapper where the 
marci@792:   /// forward_filter is everywhere false and the backward_filter is 
marci@792:   /// everywhere true. We note that for sake of efficiency, 
marci@792:   /// \c RevGraphWrapper is implemented in a different way. 
marci@792:   /// But BidirGraphWrapper is obtained from 
marci@792:   /// SubBidirGraphWrapper by considering everywhere true 
marci@910:   /// valued maps both for forward_filter and backward_filter. 
marci@792:   /// Finally, one of the most important applications of SubBidirGraphWrapper 
marci@792:   /// is ResGraphWrapper, which stands for the residual graph in directed 
marci@792:   /// flow and circulation problems. 
marci@792:   /// As wrappers usually, the SubBidirGraphWrapper implements the 
marci@792:   /// above mentioned graph structure without its physical storage, 
marci@923:   /// that is the whole stuff is stored in constant memory. 
marci@650:   template<typename Graph, 
marci@650: 	   typename ForwardFilterMap, typename BackwardFilterMap>
marci@650:   class SubBidirGraphWrapper : public GraphWrapper<Graph> {
marci@650:   public:
marci@650:     typedef GraphWrapper<Graph> Parent; 
marci@569:   protected:
marci@650:     ForwardFilterMap* forward_filter;
marci@650:     BackwardFilterMap* backward_filter;
marci@650: 
marci@792:     SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
marci@650:     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
marci@650:       forward_filter=&_forward_filter;
marci@650:     }
marci@650:     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
marci@650:       backward_filter=&_backward_filter;
marci@650:     }
marci@569: 
marci@569:   public:
marci@569: 
marci@650:     SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 
marci@650: 			 BackwardFilterMap& _backward_filter) : 
marci@650:       GraphWrapper<Graph>(_graph), 
marci@650:       forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
alpar@774:     SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 
alpar@774: 			 ForwardFilterMap, BackwardFilterMap>& gw) : 
alpar@774:       Parent(gw), 
alpar@774:       forward_filter(gw.forward_filter), 
alpar@774:       backward_filter(gw.backward_filter) { }
marci@569: 
marci@569:     class Edge; 
marci@569:     class OutEdgeIt; 
marci@569:     friend class Edge; 
marci@569:     friend class OutEdgeIt; 
marci@569: 
marci@621:     template<typename T> class EdgeMap;
marci@621: 
marci@569:     typedef typename GraphWrapper<Graph>::Node Node;
marci@621: 
alpar@774:     typedef typename Graph::Edge GraphEdge;
marci@792:     /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from 
marci@910:     /// Graph::Edge. It contains an extra bool flag which is true 
marci@910:     /// if and only if the 
marci@792:     /// edge is the backward version of the original edge.
marci@569:     class Edge : public Graph::Edge {
marci@650:       friend class SubBidirGraphWrapper<Graph, 
marci@650: 					ForwardFilterMap, BackwardFilterMap>;
marci@621:       template<typename T> friend class EdgeMap;
marci@569:     protected:
marci@569:       bool backward; //true, iff backward
marci@569:     public:
marci@569:       Edge() { }
marci@792:       /// \todo =false is needed, or causes problems?
marci@792:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@792:       /// original one, otherwise its oppositely directed pair is obtained.
alpar@774:       Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 
alpar@774: 	Graph::Edge(e), backward(_backward) { }
alpar@774:       Edge(Invalid i) : Graph::Edge(i), backward(true) { }
alpar@774:       bool operator==(const Edge& v) const { 
alpar@774: 	return (this->backward==v.backward && 
alpar@774: 		static_cast<typename Graph::Edge>(*this)==
marci@569: 		static_cast<typename Graph::Edge>(v));
marci@569:       } 
alpar@774:       bool operator!=(const Edge& v) const { 
alpar@774: 	return (this->backward!=v.backward || 
alpar@774: 		static_cast<typename Graph::Edge>(*this)!=
marci@569: 		static_cast<typename Graph::Edge>(v));
alpar@774:       }
marci@569:     };
marci@569: 
alpar@774:     class OutEdgeIt : public Edge {
marci@650:       friend class SubBidirGraphWrapper<Graph, 
marci@650: 					ForwardFilterMap, BackwardFilterMap>;
marci@569:     protected:
alpar@774:       const SubBidirGraphWrapper<Graph, 
alpar@774: 				 ForwardFilterMap, BackwardFilterMap>* gw;
marci@569:     public:
marci@569:       OutEdgeIt() { }
alpar@774:       OutEdgeIt(Invalid i) : Edge(i) { }
marci@650:       OutEdgeIt(const SubBidirGraphWrapper<Graph, 
alpar@774: 		ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 
alpar@774: 	Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 
alpar@774: 	while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 	       !(*(gw->forward_filter))[*this]) 
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@775: 	if (*static_cast<GraphEdge*>(this)==INVALID) {
alpar@774: 	  *static_cast<Edge*>(this)=
alpar@774: 	    Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
marci@775: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
marci@775: 		 !(*(gw->backward_filter))[*this]) 
marci@775: 	    *(static_cast<GraphEdge*>(this))=
marci@775: 	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@775: 	}
alpar@774:       }
alpar@774:       OutEdgeIt(const SubBidirGraphWrapper<Graph, 
alpar@774: 		ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
alpar@774: 	Edge(e), gw(&_gw) { }
alpar@774:       OutEdgeIt& operator++() { 
alpar@774: 	if (!this->backward) {
alpar@774: 	  Node n=gw->tail(*this);
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
alpar@774: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 		 !(*(gw->forward_filter))[*this]) 
alpar@774: 	    *(static_cast<GraphEdge*>(this))=
alpar@774: 	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@775: 	  if (*static_cast<GraphEdge*>(this)==INVALID) {
alpar@774: 	    *static_cast<Edge*>(this)=
alpar@774: 	      Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
marci@775: 	    while (*static_cast<GraphEdge*>(this)!=INVALID && 
marci@775: 		   !(*(gw->backward_filter))[*this]) 
marci@775: 	      *(static_cast<GraphEdge*>(this))=
marci@775: 		++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@775: 	  }
alpar@774: 	} else {
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));
alpar@774: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 		 !(*(gw->backward_filter))[*this]) 
alpar@774: 	    *(static_cast<GraphEdge*>(this))=
alpar@774: 	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@569: 	}
alpar@774: 	return *this;
marci@569:       }
marci@569:     };
marci@569: 
alpar@774:     class InEdgeIt : public Edge {
marci@650:       friend class SubBidirGraphWrapper<Graph, 
marci@650: 					ForwardFilterMap, BackwardFilterMap>;
marci@569:     protected:
alpar@774:       const SubBidirGraphWrapper<Graph, 
alpar@774: 				 ForwardFilterMap, BackwardFilterMap>* gw;
marci@569:     public:
marci@569:       InEdgeIt() { }
alpar@774:       InEdgeIt(Invalid i) : Edge(i) { }
marci@650:       InEdgeIt(const SubBidirGraphWrapper<Graph, 
alpar@774: 	       ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 
alpar@774: 	Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 
alpar@774: 	while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 	       !(*(gw->forward_filter))[*this]) 
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@775: 	if (*static_cast<GraphEdge*>(this)==INVALID) {
alpar@774: 	  *static_cast<Edge*>(this)=
alpar@774: 	    Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
marci@775: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
marci@775: 		 !(*(gw->backward_filter))[*this]) 
marci@775: 	    *(static_cast<GraphEdge*>(this))=
marci@775: 	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@775: 	}
alpar@774:       }
alpar@774:       InEdgeIt(const SubBidirGraphWrapper<Graph, 
alpar@774: 	       ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
alpar@774: 	Edge(e), gw(&_gw) { }
alpar@774:       InEdgeIt& operator++() { 
alpar@774: 	if (!this->backward) {
marci@775: 	  Node n=gw->tail(*this);
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::InEdgeIt(*(gw->graph), *this));
alpar@774: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 		 !(*(gw->forward_filter))[*this]) 
alpar@774: 	    *(static_cast<GraphEdge*>(this))=
alpar@774: 	      ++(typename Graph::InEdgeIt(*(gw->graph), *this));
marci@775: 	  if (*static_cast<GraphEdge*>(this)==INVALID) {
alpar@774: 	    *static_cast<Edge*>(this)=
alpar@774: 	      Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
marci@775: 	    while (*static_cast<GraphEdge*>(this)!=INVALID && 
marci@775: 		   !(*(gw->backward_filter))[*this]) 
marci@775: 	      *(static_cast<GraphEdge*>(this))=
marci@775: 		++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@775: 	  }
alpar@774: 	} else {
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
alpar@774: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 		 !(*(gw->backward_filter))[*this]) 
alpar@774: 	    *(static_cast<GraphEdge*>(this))=
alpar@774: 	      ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@569: 	}
alpar@774: 	return *this;
marci@569:       }
marci@569:     };
marci@569: 
alpar@774:     class EdgeIt : public Edge {
marci@650:       friend class SubBidirGraphWrapper<Graph, 
marci@650: 					ForwardFilterMap, BackwardFilterMap>;
marci@569:     protected:
alpar@774:       const SubBidirGraphWrapper<Graph, 
alpar@774: 				 ForwardFilterMap, BackwardFilterMap>* gw;
marci@569:     public:
marci@569:       EdgeIt() { }
alpar@774:       EdgeIt(Invalid i) : Edge(i) { }
marci@650:       EdgeIt(const SubBidirGraphWrapper<Graph, 
marci@775: 	     ForwardFilterMap, BackwardFilterMap>& _gw) : 
marci@892: 	Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { 
alpar@774: 	while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 	       !(*(gw->forward_filter))[*this]) 
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@775: 	if (*static_cast<GraphEdge*>(this)==INVALID) {
alpar@774: 	  *static_cast<Edge*>(this)=
alpar@774: 	    Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
marci@775: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
marci@775: 		 !(*(gw->backward_filter))[*this]) 
marci@775: 	    *(static_cast<GraphEdge*>(this))=
marci@775: 	      ++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@775: 	}
alpar@774:       }
alpar@774:       EdgeIt(const SubBidirGraphWrapper<Graph, 
alpar@774: 	     ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
alpar@774: 	Edge(e), gw(&_gw) { }
alpar@774:       EdgeIt& operator++() { 
alpar@774: 	if (!this->backward) {
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));
alpar@774: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 		 !(*(gw->forward_filter))[*this]) 
alpar@774: 	    *(static_cast<GraphEdge*>(this))=
alpar@774: 	      ++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@775: 	  if (*static_cast<GraphEdge*>(this)==INVALID) {
alpar@774: 	    *static_cast<Edge*>(this)=
alpar@774: 	      Edge(typename Graph::EdgeIt(*(gw->graph)), true);
marci@775: 	    while (*static_cast<GraphEdge*>(this)!=INVALID && 
marci@775: 		   !(*(gw->backward_filter))[*this]) 
marci@775: 	      *(static_cast<GraphEdge*>(this))=
marci@775: 		++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@775: 	  }
alpar@774: 	} else {
alpar@774: 	  *(static_cast<GraphEdge*>(this))=
alpar@774: 	    ++(typename Graph::EdgeIt(*(gw->graph), *this));
alpar@774: 	  while (*static_cast<GraphEdge*>(this)!=INVALID && 
alpar@774: 		 !(*(gw->backward_filter))[*this]) 
alpar@774: 	    *(static_cast<GraphEdge*>(this))=
alpar@774: 	      ++(typename Graph::EdgeIt(*(gw->graph), *this));
marci@569: 	}
alpar@774: 	return *this;
marci@569:       }
marci@569:     };
marci@569: 
marci@569:     using GraphWrapper<Graph>::first;
marci@569:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@569:       i=OutEdgeIt(*this, p); return i;
marci@569:     }
marci@569:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@569:       i=InEdgeIt(*this, p); return i;
marci@569:     }
marci@569:     EdgeIt& first(EdgeIt& i) const { 
marci@569:       i=EdgeIt(*this); return i;
marci@569:     }
marci@556:   
marci@569: 
marci@569:     Node tail(Edge e) const { 
marci@569:       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
marci@569:     Node head(Edge e) const { 
marci@569:       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
marci@569: 
marci@572:     /// Gives back the opposite edge.
marci@572:     Edge opposite(const Edge& e) const { 
marci@572:       Edge f=e;
marci@572:       f.backward=!f.backward;
marci@572:       return f;
marci@572:     }
marci@572: 
marci@792:     /// \warning This is a linear time operation and works only if 
marci@792:     /// \c Graph::EdgeIt is defined.
marci@792:     int edgeNum() const { 
marci@792:       int i=0;
marci@792:       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
marci@792:       return i; 
marci@792:     }
marci@569: 
marci@569:     bool forward(const Edge& e) const { return !e.backward; }
marci@569:     bool backward(const Edge& e) const { return e.backward; }
marci@569: 
marci@569: 
marci@569:     template <typename T>
marci@792:     /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two 
marci@792:     /// Graph::EdgeMap one for the forward edges and 
marci@792:     /// one for the backward edges.
marci@569:     class EdgeMap {
deba@891:       template <typename TT> friend class EdgeMap;
marci@569:       typename Graph::template EdgeMap<T> forward_map, backward_map; 
marci@569:     public:
marci@623:       typedef T ValueType;
marci@623:       typedef Edge KeyType;
deba@891: 
marci@650:       EdgeMap(const SubBidirGraphWrapper<Graph, 
alpar@774: 	      ForwardFilterMap, BackwardFilterMap>& g) : 
alpar@774: 	forward_map(*(g.graph)), backward_map(*(g.graph)) { }
deba@891: 
marci@650:       EdgeMap(const SubBidirGraphWrapper<Graph, 
alpar@774: 	      ForwardFilterMap, BackwardFilterMap>& g, T a) : 
alpar@774: 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
deba@891: 
deba@891:       template <typename TT>
deba@891:       EdgeMap(const EdgeMap<TT>& copy) 
deba@891: 	: forward_map(copy.forward_map), backward_map(copy.backward_map) {}
deba@891: 
deba@891:       template <typename TT>
deba@891:       EdgeMap& operator=(const EdgeMap<TT>& copy) {
deba@891: 	forward_map = copy.forward_map;
deba@891: 	backward_map = copy.backward_map;
deba@891: 	return *this;
deba@891:       }
deba@891:       
marci@569:       void set(Edge e, T a) { 
marci@569: 	if (!e.backward) 
marci@792: 	  forward_map.set(e, a); 
marci@569: 	else 
marci@792: 	  backward_map.set(e, a); 
marci@569:       }
deba@891: 
deba@891:       typename Graph::template EdgeMap<T>::ConstReferenceType 
deba@891:       operator[](Edge e) const { 
marci@569: 	if (!e.backward) 
marci@792: 	  return forward_map[e]; 
marci@569: 	else 
marci@792: 	  return backward_map[e]; 
marci@569:       }
deba@891: 
deba@891:       typename Graph::template EdgeMap<T>::ReferenceType 
deba@891:       operator[](Edge e) { 
deba@891: 	if (!e.backward) 
deba@891: 	  return forward_map[e]; 
deba@891: 	else 
deba@891: 	  return backward_map[e]; 
deba@891:       }
deba@891: 
marci@625:       void update() { 
marci@625: 	forward_map.update(); 
marci@625: 	backward_map.update();
marci@625:       }
marci@569:     };
deba@877: 
deba@877: 
deba@891:     //    KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
deba@877: 
marci@569:   };
marci@569: 
marci@650: 
marci@650:   ///\brief A wrapper for composing bidirected graph from a directed one. 
marci@650:   ///
alpar@879:   ///\warning Graph wrappers are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
marci@650:   /// A wrapper for composing bidirected graph from a directed one. 
marci@650:   /// A bidirected graph is composed over the directed one without physical 
marci@650:   /// storage. As the oppositely directed edges are logically different ones 
marci@650:   /// the maps are able to attach different values for them.
marci@650:   template<typename Graph>
marci@650:   class BidirGraphWrapper : 
marci@650:     public SubBidirGraphWrapper<
marci@650:     Graph, 
marci@650:     ConstMap<typename Graph::Edge, bool>, 
marci@650:     ConstMap<typename Graph::Edge, bool> > {
marci@650:   public:
marci@650:     typedef  SubBidirGraphWrapper<
marci@650:       Graph, 
marci@650:       ConstMap<typename Graph::Edge, bool>, 
marci@650:       ConstMap<typename Graph::Edge, bool> > Parent; 
marci@650:   protected:
marci@650:     ConstMap<typename Graph::Edge, bool> cm;
marci@650: 
marci@655:     BidirGraphWrapper() : Parent(), cm(true) { 
marci@655:       Parent::setForwardFilterMap(cm);
marci@655:       Parent::setBackwardFilterMap(cm);
marci@655:     }
marci@650:   public:
marci@650:     BidirGraphWrapper(Graph& _graph) : Parent() { 
marci@650:       Parent::setGraph(_graph);
marci@650:       Parent::setForwardFilterMap(cm);
marci@650:       Parent::setBackwardFilterMap(cm);
marci@650:     }
marci@738: 
marci@738:     int edgeNum() const { 
marci@738:       return 2*this->graph->edgeNum();
marci@738:     }
deba@891:     //    KEEP_MAPS(Parent, BidirGraphWrapper);
marci@650:   };
marci@650: 
marci@650: 
marci@612:   /// \brief A bidirected graph template.
marci@612:   ///
alpar@879:   ///\warning Graph wrappers are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
marci@612:   /// A bidirected graph template.
marci@612:   /// Such a bidirected graph stores each pair of oppositely directed edges 
marci@612:   /// ones in the memory, i.e. a directed graph of type 
marci@612:   /// \c Graph is used for that.
marci@612:   /// As the oppositely directed edges are logically different ones 
marci@612:   /// the maps are able to attach different values for them.
marci@612:   /// \ingroup graphs
marci@612:   template<typename Graph>
marci@612:   class BidirGraph : public BidirGraphWrapper<Graph> {
marci@650:   public:
marci@612:     typedef UndirGraphWrapper<Graph> Parent;
marci@612:   protected:
marci@612:     Graph gr;
marci@612:   public:
marci@612:     BidirGraph() : BidirGraphWrapper<Graph>() { 
marci@612:       Parent::setGraph(gr); 
marci@612:     }
deba@891:     //    KEEP_MAPS(Parent, BidirGraph);
marci@612:   };
marci@569: 
marci@556: 
marci@650: 
marci@650:   template<typename Graph, typename Number,
marci@650: 	   typename CapacityMap, typename FlowMap>
marci@658:   class ResForwardFilter {
marci@658:     //    const Graph* graph;
marci@650:     const CapacityMap* capacity;
marci@650:     const FlowMap* flow;
marci@650:   public:
marci@658:     ResForwardFilter(/*const Graph& _graph, */
marci@658: 		     const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658:       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
marci@658:     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
marci@656:     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656:     void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650:     bool operator[](const typename Graph::Edge& e) const {
marci@738:       return (Number((*flow)[e]) < Number((*capacity)[e]));
marci@650:     }
marci@650:   };
marci@650: 
marci@650:   template<typename Graph, typename Number,
marci@650: 	   typename CapacityMap, typename FlowMap>
marci@658:   class ResBackwardFilter {
marci@650:     const CapacityMap* capacity;
marci@650:     const FlowMap* flow;
marci@650:   public:
marci@658:     ResBackwardFilter(/*const Graph& _graph,*/ 
marci@658: 		      const CapacityMap& _capacity, const FlowMap& _flow) :
marci@658:       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
marci@658:     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
marci@656:     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
marci@656:     void setFlow(const FlowMap& _flow) { flow=&_flow; }
marci@650:     bool operator[](const typename Graph::Edge& e) const {
marci@738:       return (Number(0) < Number((*flow)[e]));
marci@650:     }
marci@650:   };
marci@650: 
marci@653:   
marci@653:   /// A wrapper for composing the residual graph for directed flow and circulation problems.
marci@650: 
alpar@879:   ///\warning Graph wrappers are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
marci@653:   /// A wrapper for composing the residual graph for directed flow and circulation problems.
marci@650:   template<typename Graph, typename Number, 
marci@650: 	   typename CapacityMap, typename FlowMap>
marci@653:   class ResGraphWrapper : 
marci@650:     public SubBidirGraphWrapper< 
marci@650:     Graph, 
marci@658:     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
marci@658:     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
marci@650:   public:
marci@650:     typedef SubBidirGraphWrapper< 
marci@650:       Graph, 
marci@658:       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
marci@658:       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
marci@650:   protected:
marci@650:     const CapacityMap* capacity;
marci@650:     FlowMap* flow;
marci@658:     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
marci@658:     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
marci@658:     ResGraphWrapper() : Parent(), 
marci@658:  			capacity(0), flow(0) { }
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:     }
marci@658:     void setFlowMap(FlowMap& _flow) {
marci@658:       flow=&_flow;
marci@658:       forward_filter.setFlow(_flow);
marci@658:       backward_filter.setFlow(_flow);
marci@658:     }
marci@650:   public:
marci@653:     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
marci@650: 		       FlowMap& _flow) : 
marci@650:       Parent(), capacity(&_capacity), flow(&_flow), 
marci@658:       forward_filter(/*_graph,*/ _capacity, _flow), 
marci@658:       backward_filter(/*_graph,*/ _capacity, _flow) {
marci@650:       Parent::setGraph(_graph);
marci@650:       Parent::setForwardFilterMap(forward_filter);
marci@650:       Parent::setBackwardFilterMap(backward_filter);
marci@650:     }
marci@650: 
marci@660:     typedef typename Parent::Edge Edge;
marci@660: 
marci@660:     void augment(const Edge& e, Number a) const {
marci@650:       if (Parent::forward(e))  
marci@650: 	flow->set(e, (*flow)[e]+a);
marci@650:       else  
marci@650: 	flow->set(e, (*flow)[e]-a);
marci@650:     }
marci@650: 
marci@660:     /// \brief Residual capacity map.
marci@660:     ///
marci@910:     /// In generic residual graphs the residual capacity can be obtained 
marci@910:     /// as a map. 
marci@660:     class ResCap {
marci@660:     protected:
marci@660:       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
marci@660:     public:
marci@660:       typedef Number ValueType;
marci@660:       typedef Edge KeyType;
marci@888:       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& 
marci@888: 	     _res_graph) : res_graph(&_res_graph) { }
marci@660:       Number operator[](const Edge& e) const { 
marci@660: 	if (res_graph->forward(e)) 
marci@660: 	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
marci@660: 	else 
marci@660: 	  return (*(res_graph->flow))[e]; 
marci@660:       }
marci@660:     };
marci@660: 
deba@891:     //    KEEP_MAPS(Parent, ResGraphWrapper);
marci@650:   };
marci@650: 
marci@650: 
marci@612:   /// For blocking flows.
marci@556: 
alpar@879:   ///\warning Graph wrappers are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
marci@792:   /// This graph wrapper is used for on-the-fly 
marci@792:   /// Dinits blocking flow computations.
marci@612:   /// For each node, an out-edge is stored which is used when the 
marci@612:   /// \code 
marci@612:   /// OutEdgeIt& first(OutEdgeIt&, const Node&)
marci@612:   /// \endcode
marci@612:   /// is called. 
marci@556:   ///
marci@792:   /// \author Marton Makai
marci@556:   template<typename Graph, typename FirstOutEdgesMap>
marci@556:   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
marci@650:   public:
marci@650:     typedef GraphWrapper<Graph> Parent; 
marci@556:   protected:
marci@556:     FirstOutEdgesMap* first_out_edges;
marci@556:   public:
marci@556:     ErasingFirstGraphWrapper(Graph& _graph, 
marci@556: 			     FirstOutEdgesMap& _first_out_edges) : 
marci@556:       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  
marci@556: 
marci@556:     typedef typename GraphWrapper<Graph>::Node Node;
marci@556:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@777:     class OutEdgeIt : public Edge { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@777:       const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@777:       OutEdgeIt(Invalid i) : Edge(i) { }
marci@777:       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, 
marci@777: 		const Node& n) : 
marci@777: 	Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
marci@777:       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw, 
marci@777: 		const Edge& e) : 
marci@777: 	Edge(e), gw(&_gw) { }
marci@777:       OutEdgeIt& operator++() { 
marci@777: 	*(static_cast<Edge*>(this))=
marci@777: 	  ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
marci@777: 	return *this; 
marci@777:       }
marci@556:     };
marci@556: 
marci@556:     using GraphWrapper<Graph>::first;
marci@556:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@556:       i=OutEdgeIt(*this, p); return i;
marci@556:     }
marci@777:     void erase(const Edge& e) const {
marci@777:       Node n=tail(e);
deba@844:       typename Graph::OutEdgeIt f(*Parent::graph, n);
marci@777:       ++f;
marci@777:       first_out_edges->set(n, f);
marci@556:     }
deba@877: 
deba@891:     //    KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
marci@556:   };
marci@556: 
marci@556:   ///@}
marci@556: 
alpar@921: } //namespace lemon
marci@556: 
alpar@921: #endif //LEMON_GRAPH_WRAPPER_H
marci@556: