marci@556: // -*- c++ -*-
marci@556: #ifndef HUGO_GRAPH_WRAPPER_H
marci@556: #define HUGO_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: 
marci@556: #include <hugo/invalid.h>
marci@556: //#include <iter_map.h>
marci@556: 
marci@556: namespace hugo {
marci@556: 
marci@556:   // Graph wrappers
marci@556: 
marci@556:   /// \addtogroup gwrappers
marci@556:   /// A main parts of HUGOlib 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: 
marci@556:   ///This is the base type for the Graph Wrappers.
marci@556:   ///\todo Some more docs... 
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) { }
marci@556: //     Graph& getGraph() const { return *graph; }
marci@556:  
marci@556: //    typedef typename Graph::Node Node;
marci@556:     class Node : public Graph::Node {
marci@556:       friend class GraphWrapper<Graph>;
marci@556:     public:
marci@556:       Node() { }
marci@556:       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
marci@556:       Node(const Invalid& i) : Graph::Node(i) { }
marci@556:     };
marci@556:     class NodeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       typename Graph::NodeIt n;
marci@556:      public:
marci@556:       NodeIt() { }
marci@556:       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
marci@556:       NodeIt(const Invalid& i) : n(i) { }
marci@556:       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
marci@556:       operator Node() const { return Node(typename Graph::Node(n)); }
marci@556:     };
marci@556: //    typedef typename Graph::Edge Edge;
marci@556:     class Edge : public Graph::Edge {
marci@556:       friend class GraphWrapper<Graph>;
marci@556:     public:
marci@556:       Edge() { }
marci@556:       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
marci@556:       Edge(const Invalid& i) : Graph::Edge(i) { }
marci@556:     };
marci@556:     class OutEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       typename Graph::OutEdgeIt e;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@556:       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@556:       OutEdgeIt(const Invalid& i) : e(i) { }
marci@556:       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
marci@556: 	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556:     class InEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       typename Graph::InEdgeIt e;
marci@556:     public:
marci@556:       InEdgeIt() { }
marci@556:       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@556:       InEdgeIt(const Invalid& i) : e(i) { }
marci@556:       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
marci@556: 	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556:     //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@556:     class EdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       typename Graph::EdgeIt e;
marci@556:     public:
marci@556:       EdgeIt() { }
marci@556:       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
marci@556:       EdgeIt(const Invalid& i) : e(i) { }
marci@556:       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
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:     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
marci@556:     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
marci@556:     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
marci@556:     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
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:     bool valid(const Node& n) const { 
marci@556:       return graph->valid(static_cast<typename Graph::Node>(n)); }
marci@556:     bool valid(const Edge& e) const { 
marci@556:       return graph->valid(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 aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@556:     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
marci@556:     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
marci@556:     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
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:     
marci@556:     template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
marci@556:       typedef typename Graph::template NodeMap<T> Parent;
marci@556:     public:
marci@556:       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
marci@556:       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
marci@556:     };
marci@556: 
marci@556:     template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
marci@556:       typedef typename Graph::template EdgeMap<T> Parent;
marci@556:     public:
marci@556:       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
marci@556:       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
marci@556:     };
marci@556:   };
marci@556: 
marci@569: 
marci@569: 
marci@556:   /// A graph wrapper which reverses the orientation of the edges.
marci@556: 
marci@556:   /// A graph wrapper which reverses the orientation of the edges.
marci@612:   /// Thus \c Graph have to be a directed graph type.
marci@556:   ///
marci@556:   ///\author Marton Makai
marci@556:   template<typename Graph>
marci@556:   class RevGraphWrapper : public GraphWrapper<Graph> {
marci@556:   protected:
marci@612:     RevGraphWrapper() : GraphWrapper<Graph>() { }
marci@556:   public:
marci@556:     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
marci@556: 
marci@556:     typedef typename GraphWrapper<Graph>::Node Node;
marci@556:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@556:     //If Graph::OutEdgeIt is not defined
marci@556:     //and we do not want to use RevGraphWrapper::InEdgeIt,
marci@556:     //the typdef techinque does not work.
marci@556:     //Unfortunately all the typedefs are instantiated in templates.
marci@556:     //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
marci@556:     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
marci@556: 
marci@556:     class OutEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class RevGraphWrapper<Graph>;
marci@556:       typename Graph::InEdgeIt e;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@556:       OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@556:       OutEdgeIt(const Invalid& i) : e(i) { }
marci@556:       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
marci@556: 	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556:     class InEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class RevGraphWrapper<Graph>;
marci@556:       typename Graph::OutEdgeIt e;
marci@556:     public:
marci@556:       InEdgeIt() { }
marci@556:       InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@556:       InEdgeIt(const Invalid& i) : e(i) { }
marci@556:       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
marci@556: 	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
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:     using GraphWrapper<Graph>::next;
marci@556:     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@556:     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@556: 
marci@556:     Node aNode(const OutEdgeIt& e) const { 
marci@556:       return Node(this->graph->aNode(e.e)); }
marci@556:     Node aNode(const InEdgeIt& e) const { 
marci@556:       return Node(this->graph->aNode(e.e)); }
marci@556:     Node bNode(const OutEdgeIt& e) const { 
marci@556:       return Node(this->graph->bNode(e.e)); }
marci@556:     Node bNode(const InEdgeIt& e) const { 
marci@556:       return Node(this->graph->bNode(e.e)); }
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: 
marci@556:   };
marci@556: 
marci@569: 
marci@569: 
marci@612:   /// A graph wrapper for hiding nodes and edges from a graph.
marci@556:   
marci@556:   /// This wrapper shows a graph with filtered node-set and 
marci@556:   /// edge-set. The quick brown fox iterator jumps over 
marci@556:   /// the lazy dog nodes or edges if the values for them are false 
marci@556:   /// in the bool maps. 
marci@556:   ///
marci@556:   ///\author Marton Makai
marci@556:   template<typename Graph, typename NodeFilterMap, 
marci@556: 	   typename EdgeFilterMap>
marci@556:   class SubGraphWrapper : public GraphWrapper<Graph> {
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: 
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@556:     class NodeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@556:       typename Graph::NodeIt n;
marci@556:      public:
marci@556:       NodeIt() { }
marci@556:       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
marci@556:       NodeIt(const Invalid& i) : n(i) { }
marci@556:       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
marci@556: 	n(*(_G.graph)) { 
marci@556: 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
marci@556: 	  _G.graph->next(n);
marci@556:       }
marci@556:       operator Node() const { return Node(typename Graph::Node(n)); }
marci@556:     };
marci@556:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@556:     class OutEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@556:       typename Graph::OutEdgeIt e;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@556:       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@556:       OutEdgeIt(const Invalid& i) : e(i) { }
marci@556:       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
marci@556: 		const Node& _n) : 
marci@556: 	e(*(_G.graph), typename Graph::Node(_n)) { 
marci@556:       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
marci@556: 	  _G.graph->next(e);
marci@556:       }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556:     class InEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@556:       typename Graph::InEdgeIt e;
marci@556:     public:
marci@556:       InEdgeIt() { }
marci@556:       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@556:       InEdgeIt(const Invalid& i) : e(i) { }
marci@556:       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
marci@556: 	       const Node& _n) : 
marci@556: 	e(*(_G.graph), typename Graph::Node(_n)) { 
marci@556:       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
marci@556: 	  _G.graph->next(e);
marci@556:       }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556:     //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@556:     class EdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
marci@556:       typename Graph::EdgeIt e;
marci@556:     public:
marci@556:       EdgeIt() { }
marci@556:       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
marci@556:       EdgeIt(const Invalid& i) : e(i) { }
marci@556:       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
marci@556: 	e(*(_G.graph)) { 
marci@556:       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
marci@556: 	  _G.graph->next(e);
marci@556:       }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
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:     NodeIt& next(NodeIt& i) const {
marci@556:       this->graph->next(i.n); 
marci@556:       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
marci@556: 	this->graph->next(i.n); }
marci@556:       return i;
marci@556:     }
marci@556:     OutEdgeIt& next(OutEdgeIt& i) const {
marci@556:       this->graph->next(i.e); 
marci@556:       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
marci@556: 	this->graph->next(i.e); }
marci@556:       return i;
marci@556:     }
marci@556:     InEdgeIt& next(InEdgeIt& i) const {
marci@556:       this->graph->next(i.e); 
marci@556:       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
marci@556: 	this->graph->next(i.e); }
marci@556:       return i;
marci@556:     }
marci@556:     EdgeIt& next(EdgeIt& i) const {
marci@556:       this->graph->next(i.e); 
marci@556:       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
marci@556: 	this->graph->next(i.e); }
marci@556:       return i;
marci@556:     }
marci@556: 
marci@556:     Node aNode(const OutEdgeIt& e) const { 
marci@556:       return Node(this->graph->aNode(e.e)); }
marci@556:     Node aNode(const InEdgeIt& e) const { 
marci@556:       return Node(this->graph->aNode(e.e)); }
marci@556:     Node bNode(const OutEdgeIt& e) const { 
marci@556:       return Node(this->graph->bNode(e.e)); }
marci@556:     Node bNode(const InEdgeIt& e) const { 
marci@556:       return Node(this->graph->bNode(e.e)); }
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: 
alpar@594:     /// This is a linear time operation and works only if 
marci@593:     /// NodeIt is defined.
marci@593:     int nodeNum() const { 
marci@593:       int i=0;
marci@593:       NodeIt n;
marci@593:       for (this->first(n); this->valid(n); this->next(n)) ++i;
marci@593:       return i; 
marci@593:     }
marci@593: 
marci@593:     /// This is a linear time operation and works only if 
marci@593:     /// EdgeIt is defined.
marci@593:     int edgeNum() const { 
marci@593:       int i=0;
marci@593:       EdgeIt e;
marci@593:       for (this->first(e); this->valid(e); this->next(e)) ++i;
marci@593:       return i; 
marci@593:     }
marci@593: 
marci@556:   };
marci@556: 
marci@569: 
marci@569: 
marci@612:   /// \brief A wrapper for forgetting the orientation of a graph.
marci@612:   ///
marci@556:   /// A wrapper for getting an undirected graph by forgetting
marci@556:   /// the orientation of a directed one.
alpar@589:   ///
marci@612:   /// \author Marton Makai
marci@556:   template<typename Graph>
marci@556:   class UndirGraphWrapper : public GraphWrapper<Graph> {
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: //FIXME InEdgeIt
marci@556:     typedef OutEdgeIt InEdgeIt; 
marci@556: 
marci@556:     using GraphWrapper<Graph>::first;
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: //FIXME
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:     using GraphWrapper<Graph>::next;
marci@556: //     NodeIt& next(NodeIt& n) const {
marci@556: //       GraphWrapper<Graph>::next(n);
marci@556: //       return n;
marci@556: //     }
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:     //FIXME InEdgeIt
marci@556: //     EdgeIt& next(EdgeIt& e) const {
marci@556: //       GraphWrapper<Graph>::next(n);
marci@556: // //      graph->next(e.e);
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); }
marci@556:   };
marci@556:   
marci@612:   /// \brief An undirected graph template.
marci@612:   ///
marci@612:   /// An undirected graph template.
marci@612:   /// This class works as an undirected graph and a directed graph of 
marci@612:   /// class \c Graph is used for the physical storage.
marci@612:   /// \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:     }
marci@556:   };
marci@556: 
marci@569: 
marci@612:   ///\brief A wrapper for composing bidirected graph from a directed one. 
marci@612:   /// experimental, for fezso's sake.
marci@612:   ///
marci@576:   /// A wrapper for composing bidirected graph from a directed one. 
marci@576:   /// experimental, for fezso's sake.
marci@612:   /// A bidirected graph is composed over the directed one without physical 
marci@612:   /// storage. As the oppositely directed edges are logically different ones 
marci@612:   /// the maps are able to attach different values for them.
marci@569:   template<typename Graph>
marci@569:   class BidirGraphWrapper : public GraphWrapper<Graph> {
marci@569:   protected:
marci@569:     //const CapacityMap* capacity;
marci@569:     //FlowMap* flow;
marci@569: 
marci@569:     BidirGraphWrapper() : GraphWrapper<Graph>()/*, 
marci@569: 						 capacity(0), flow(0)*/ { }
marci@569: //     void setCapacityMap(const CapacityMap& _capacity) {
marci@569: //       capacity=&_capacity;
marci@569: //     }
marci@569: //     void setFlowMap(FlowMap& _flow) {
marci@569: //       flow=&_flow;
marci@569: //     }
marci@569: 
marci@569:   public:
marci@569: 
marci@569:     BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
marci@569: 				     FlowMap& _flow*/) : 
marci@569:       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
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 NodeMap;    
marci@621:     template<typename T> class EdgeMap;
marci@621: 
marci@569:     typedef typename GraphWrapper<Graph>::Node Node;
marci@569:     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@621: 
marci@569:     class Edge : public Graph::Edge {
marci@569:       friend class BidirGraphWrapper<Graph>;
marci@621:       ///\bug ez nem is kell
marci@621:       //template<typename T> friend class NodeMap;
marci@621:       template<typename T> friend class EdgeMap;
marci@569:     protected:
marci@569:       bool backward; //true, iff backward
marci@569: //      typename Graph::Edge e;
marci@569:     public:
marci@569:       Edge() { }
marci@626:       ///\bug =false kell-e? zsoltnak kell az addEdge miatt
marci@626:       Edge(const typename Graph::Edge& _e, bool _backward=false) : 
marci@569: 	Graph::Edge(_e), backward(_backward) { }
marci@569:       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
marci@569: //the unique invalid iterator
marci@569:       friend bool operator==(const Edge& u, const Edge& v) { 
marci@569: 	return (v.backward==u.backward && 
marci@569: 		static_cast<typename Graph::Edge>(u)==
marci@569: 		static_cast<typename Graph::Edge>(v));
marci@569:       } 
marci@569:       friend bool operator!=(const Edge& u, const Edge& v) { 
marci@569: 	return (v.backward!=u.backward || 
marci@569: 		static_cast<typename Graph::Edge>(u)!=
marci@569: 		static_cast<typename Graph::Edge>(v));
marci@569:       } 
marci@569:     };
marci@569: 
marci@569:     class OutEdgeIt {
marci@569:       friend class BidirGraphWrapper<Graph>;
marci@569:     protected:
marci@569:       typename Graph::OutEdgeIt out;
marci@569:       typename Graph::InEdgeIt in;
marci@569:       bool backward;
marci@569:     public:
marci@569:       OutEdgeIt() { }
marci@569:       //FIXME
marci@569: //      OutEdgeIt(const Edge& e) : Edge(e) { }
marci@569:       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
marci@569: //the unique invalid iterator
marci@569:       OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
marci@569: 	backward=false;
marci@569: 	_G.graph->first(out, v);
marci@569: 	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
marci@569: 	if (!_G.graph->valid(out)) {
marci@569: 	  backward=true;
marci@569: 	  _G.graph->first(in, v);
marci@569: 	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
marci@569: 	}
marci@569:       }
marci@569:       operator Edge() const { 
marci@569: //	Edge e;
marci@569: //	e.forward=this->forward;
marci@569: //	if (this->forward) e=out; else e=in;
marci@569: //	return e;
marci@569: 	if (this->backward) 
marci@569: 	  return Edge(in, this->backward); 
marci@569: 	else 
marci@569: 	  return Edge(out, this->backward);
marci@569:       }
marci@569:     };
marci@569: 
marci@569:     class InEdgeIt {
marci@569:       friend class BidirGraphWrapper<Graph>;
marci@569:     protected:
marci@569:       typename Graph::OutEdgeIt out;
marci@569:       typename Graph::InEdgeIt in;
marci@569:       bool backward;
marci@569:     public:
marci@569:       InEdgeIt() { }
marci@569:       //FIXME
marci@569: //      OutEdgeIt(const Edge& e) : Edge(e) { }
marci@569:       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
marci@569: //the unique invalid iterator
marci@569:       InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
marci@569: 	backward=false;
marci@569: 	_G.graph->first(in, v);
marci@569: 	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
marci@569: 	if (!_G.graph->valid(in)) {
marci@569: 	  backward=true;
marci@569: 	  _G.graph->first(out, v);
marci@569: 	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
marci@569: 	}
marci@569:       }
marci@569:       operator Edge() const { 
marci@569: //	Edge e;
marci@569: //	e.forward=this->forward;
marci@569: //	if (this->forward) e=out; else e=in;
marci@569: //	return e;
marci@569: 	if (this->backward) 
marci@569: 	  return Edge(out, this->backward); 
marci@569: 	else 
marci@569: 	  return Edge(in, this->backward);
marci@569:       }
marci@569:     };
marci@569: 
marci@569:     class EdgeIt {
marci@569:       friend class BidirGraphWrapper<Graph>;
marci@569:     protected:
marci@569:       typename Graph::EdgeIt e;
marci@569:       bool backward;
marci@569:     public:
marci@569:       EdgeIt() { }
marci@569:       EdgeIt(const Invalid& i) : e(i), backward(true) { }
marci@569:       EdgeIt(const BidirGraphWrapper<Graph>& _G) { 
marci@569: 	backward=false;
marci@569: 	_G.graph->first(e);
marci@569: 	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
marci@569: 	if (!_G.graph->valid(e)) {
marci@569: 	  backward=true;
marci@569: 	  _G.graph->first(e);
marci@569: 	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
marci@569: 	}
marci@569:       }
marci@569:       operator Edge() const { 
marci@569: 	return Edge(e, this->backward);
marci@569:       }
marci@569:     };
marci@569: 
marci@569:     using GraphWrapper<Graph>::first;
marci@569: //     NodeIt& first(NodeIt& i) const { 
marci@569: //       i=NodeIt(*this); return i;
marci@569: //     }
marci@569:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@569:       i=OutEdgeIt(*this, p); return i;
marci@569:     }
marci@569: //    FIXME not tested
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:     using GraphWrapper<Graph>::next;
marci@569: //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
marci@569:     OutEdgeIt& next(OutEdgeIt& e) const { 
marci@569:       if (!e.backward) {
marci@569: 	Node v=this->graph->aNode(e.out);
marci@569: 	this->graph->next(e.out);
marci@569: 	while(this->graph->valid(e.out) && !enabled(e)) { 
marci@569: 	  this->graph->next(e.out); }
marci@569: 	if (!this->graph->valid(e.out)) {
marci@569: 	  e.backward=true;
marci@569: 	  this->graph->first(e.in, v); 
marci@569: 	  while(this->graph->valid(e.in) && !enabled(e)) { 
marci@569: 	    this->graph->next(e.in); }
marci@569: 	}
marci@569:       } else {
marci@569: 	this->graph->next(e.in);
marci@569: 	while(this->graph->valid(e.in) && !enabled(e)) { 
marci@569: 	  this->graph->next(e.in); } 
marci@569:       }
marci@569:       return e;
marci@569:     }
marci@569: //     FIXME Not tested
marci@569:     InEdgeIt& next(InEdgeIt& e) const { 
marci@569:       if (!e.backward) {
marci@569: 	Node v=this->graph->aNode(e.in);
marci@569: 	this->graph->next(e.in);
marci@569: 	while(this->graph->valid(e.in) && !enabled(e)) { 
marci@569: 	  this->graph->next(e.in); }
marci@569: 	if (!this->graph->valid(e.in)) {
marci@569: 	  e.backward=true;
marci@569: 	  this->graph->first(e.out, v); 
marci@569: 	  while(this->graph->valid(e.out) && !enabled(e)) { 
marci@569: 	    this->graph->next(e.out); }
marci@569: 	}
marci@569:       } else {
marci@569: 	this->graph->next(e.out);
marci@569: 	while(this->graph->valid(e.out) && !enabled(e)) { 
marci@569: 	  this->graph->next(e.out); } 
marci@569:       }
marci@569:       return e;
marci@569:     }
marci@569:     EdgeIt& next(EdgeIt& e) const {
marci@569:       if (!e.backward) {
marci@569: 	this->graph->next(e.e);
marci@569: 	while(this->graph->valid(e.e) && !enabled(e)) { 
marci@569: 	  this->graph->next(e.e); }
marci@569: 	if (!this->graph->valid(e.e)) {
marci@569: 	  e.backward=true;
marci@569: 	  this->graph->first(e.e); 
marci@569: 	  while(this->graph->valid(e.e) && !enabled(e)) { 
marci@569: 	    this->graph->next(e.e); }
marci@569: 	}
marci@569:       } else {
marci@569: 	this->graph->next(e.e);
marci@569: 	while(this->graph->valid(e.e) && !enabled(e)) { 
marci@569: 	  this->graph->next(e.e); } 
marci@569:       }
marci@569:       return e;
marci@569:     }
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@569:     Node aNode(OutEdgeIt e) const { 
marci@569:       return ((!e.backward) ? this->graph->aNode(e.out) : 
marci@569: 	      this->graph->aNode(e.in)); }
marci@569:     Node bNode(OutEdgeIt e) const { 
marci@569:       return ((!e.backward) ? this->graph->bNode(e.out) : 
marci@569: 	      this->graph->bNode(e.in)); }
marci@569: 
marci@569:     Node aNode(InEdgeIt e) const { 
marci@569:       return ((!e.backward) ? this->graph->aNode(e.in) : 
marci@569: 	      this->graph->aNode(e.out)); }
marci@569:     Node bNode(InEdgeIt e) const { 
marci@569:       return ((!e.backward) ? this->graph->bNode(e.in) : 
marci@569: 	      this->graph->bNode(e.out)); }
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@569: //    int nodeNum() const { return graph->nodeNum(); }
marci@569:     //FIXME
marci@569:     void edgeNum() const { }
marci@569:     //int edgeNum() const { return graph->edgeNum(); }
marci@569: 
marci@569: 
marci@569: //    int id(Node v) const { return graph->id(v); }
marci@569: 
marci@569:     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
marci@569:     bool valid(Edge e) const { 
marci@569:       return this->graph->valid(e);
marci@569: 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
marci@569:     }
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: //     void augment(const Edge& e, Number a) const {
marci@569: //       if (!e.backward)  
marci@569: // // 	flow->set(e.out, flow->get(e.out)+a);
marci@569: // 	flow->set(e, (*flow)[e]+a);
marci@569: //       else  
marci@569: // // 	flow->set(e.in, flow->get(e.in)-a);
marci@569: // 	flow->set(e, (*flow)[e]-a);
marci@569: //     }
marci@569: 
marci@569:     bool enabled(const Edge& e) const { 
marci@569:       if (!e.backward) 
marci@569: //	return (capacity->get(e.out)-flow->get(e.out)); 
marci@569: 	//return ((*capacity)[e]-(*flow)[e]);
marci@569: 	return true;
marci@569:       else 
marci@569: //	return (flow->get(e.in)); 
marci@569: 	//return ((*flow)[e]); 
marci@569: 	return true;
marci@569:     }
marci@569: 
marci@569: //     Number enabled(typename Graph::OutEdgeIt out) const { 
marci@569: // //      return (capacity->get(out)-flow->get(out)); 
marci@569: //       return ((*capacity)[out]-(*flow)[out]); 
marci@569: //     }
marci@569:     
marci@569: //     Number enabled(typename Graph::InEdgeIt in) const { 
marci@569: // //      return (flow->get(in)); 
marci@569: //       return ((*flow)[in]); 
marci@569: //     }
marci@569: 
marci@569:     template <typename T>
marci@569:     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;
marci@569:       EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
marci@569:       EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
marci@569:       void set(Edge e, T a) { 
marci@569: 	if (!e.backward) 
marci@622: 	  forward_map.set(e/*.out*/, a); 
marci@569: 	else 
marci@622: 	  backward_map.set(e/*.in*/, a); 
marci@569:       }
marci@569:       T operator[](Edge e) const { 
marci@569: 	if (!e.backward) 
marci@622: 	  return forward_map[e/*.out*/]; 
marci@569: 	else 
marci@622: 	  return backward_map[e/*.in*/]; 
marci@569:       }
marci@625:       void update() { 
marci@625: 	forward_map.update(); 
marci@625: 	backward_map.update();
marci@625:       }
marci@569: //       T get(Edge e) const { 
marci@569: // 	if (e.out_or_in) 
marci@569: // 	  return forward_map.get(e.out); 
marci@569: // 	else 
marci@569: // 	  return backward_map.get(e.in); 
marci@569: //       }
marci@569:     };
marci@569:   };
marci@569: 
marci@612:   /// \brief A bidirected graph template.
marci@612:   ///
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@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:     }
marci@612:   };
marci@569: 
marci@556: 
marci@556:   /// A wrapper for composing the residual graph for directed flow and circulation problems.
marci@556: 
marci@556:   /// A wrapper for composing the residual graph for directed flow and circulation problems.
marci@556:   template<typename Graph, typename Number, 
marci@556: 	   typename CapacityMap, typename FlowMap>
marci@556:   class ResGraphWrapper : public GraphWrapper<Graph> {
marci@556:   protected:
marci@556:     const CapacityMap* capacity;
marci@556:     FlowMap* flow;
marci@556: 
marci@556:     ResGraphWrapper() : GraphWrapper<Graph>(0), 
marci@556: 			capacity(0), flow(0) { }
marci@560:     void setCapacityMap(const CapacityMap& _capacity) {
marci@560:       capacity=&_capacity;
marci@556:     }
marci@556:     void setFlowMap(FlowMap& _flow) {
marci@556:       flow=&_flow;
marci@556:     }
marci@556: 
marci@556:   public:
marci@556: 
marci@556:     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
marci@556: 		    FlowMap& _flow) : 
marci@556:       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
marci@556: 
marci@556:     class Edge; 
marci@556:     class OutEdgeIt; 
marci@556:     friend class Edge; 
marci@556:     friend class OutEdgeIt; 
marci@556: 
marci@556:     typedef typename GraphWrapper<Graph>::Node Node;
marci@556:     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
marci@556:     class Edge : public Graph::Edge {
marci@556:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@556:     protected:
marci@565:       bool backward; //true, iff backward
marci@556: //      typename Graph::Edge e;
marci@556:     public:
marci@556:       Edge() { }
marci@565:       Edge(const typename Graph::Edge& _e, bool _backward) : 
marci@565: 	Graph::Edge(_e), backward(_backward) { }
marci@565:       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
marci@556: //the unique invalid iterator
marci@556:       friend bool operator==(const Edge& u, const Edge& v) { 
marci@565: 	return (v.backward==u.backward && 
marci@556: 		static_cast<typename Graph::Edge>(u)==
marci@556: 		static_cast<typename Graph::Edge>(v));
marci@556:       } 
marci@556:       friend bool operator!=(const Edge& u, const Edge& v) { 
marci@565: 	return (v.backward!=u.backward || 
marci@556: 		static_cast<typename Graph::Edge>(u)!=
marci@556: 		static_cast<typename Graph::Edge>(v));
marci@556:       } 
marci@556:     };
marci@556: 
marci@556:     class OutEdgeIt {
marci@556:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@556:     protected:
marci@556:       typename Graph::OutEdgeIt out;
marci@556:       typename Graph::InEdgeIt in;
marci@565:       bool backward;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@556:       //FIXME
marci@556: //      OutEdgeIt(const Edge& e) : Edge(e) { }
marci@565:       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
marci@556: //the unique invalid iterator
marci@569:       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
marci@565: 	backward=false;
marci@569: 	_G.graph->first(out, v);
marci@569: 	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
marci@569: 	if (!_G.graph->valid(out)) {
marci@565: 	  backward=true;
marci@569: 	  _G.graph->first(in, v);
marci@569: 	  while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
marci@556: 	}
marci@556:       }
marci@556:       operator Edge() const { 
marci@556: //	Edge e;
marci@556: //	e.forward=this->forward;
marci@556: //	if (this->forward) e=out; else e=in;
marci@556: //	return e;
marci@565: 	if (this->backward) 
marci@565: 	  return Edge(in, this->backward); 
marci@556: 	else 
marci@565: 	  return Edge(out, this->backward);
marci@556:       }
marci@556:     };
marci@556: 
marci@556:     class InEdgeIt {
marci@556:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@556:     protected:
marci@556:       typename Graph::OutEdgeIt out;
marci@556:       typename Graph::InEdgeIt in;
marci@565:       bool backward;
marci@556:     public:
marci@556:       InEdgeIt() { }
marci@556:       //FIXME
marci@556: //      OutEdgeIt(const Edge& e) : Edge(e) { }
marci@565:       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
marci@556: //the unique invalid iterator
marci@569:       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
marci@565: 	backward=false;
marci@569: 	_G.graph->first(in, v);
marci@569: 	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
marci@569: 	if (!_G.graph->valid(in)) {
marci@565: 	  backward=true;
marci@569: 	  _G.graph->first(out, v);
marci@569: 	  while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
marci@556: 	}
marci@556:       }
marci@556:       operator Edge() const { 
marci@556: //	Edge e;
marci@556: //	e.forward=this->forward;
marci@556: //	if (this->forward) e=out; else e=in;
marci@556: //	return e;
marci@565: 	if (this->backward) 
marci@565: 	  return Edge(out, this->backward); 
marci@556: 	else 
marci@565: 	  return Edge(in, this->backward);
marci@556:       }
marci@556:     };
marci@556: 
marci@556:     class EdgeIt {
marci@556:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
marci@556:     protected:
marci@556:       typename Graph::EdgeIt e;
marci@565:       bool backward;
marci@556:     public:
marci@556:       EdgeIt() { }
marci@565:       EdgeIt(const Invalid& i) : e(i), backward(true) { }
marci@569:       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
marci@565: 	backward=false;
marci@569: 	_G.graph->first(e);
marci@569: 	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
marci@569: 	if (!_G.graph->valid(e)) {
marci@565: 	  backward=true;
marci@569: 	  _G.graph->first(e);
marci@569: 	  while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
marci@556: 	}
marci@556:       }
marci@556:       operator Edge() const { 
marci@565: 	return Edge(e, this->backward);
marci@556:       }
marci@556:     };
marci@556: 
marci@556:     using GraphWrapper<Graph>::first;
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: //    FIXME not tested
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:     using GraphWrapper<Graph>::next;
marci@556: //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
marci@556:     OutEdgeIt& next(OutEdgeIt& e) const { 
marci@565:       if (!e.backward) {
marci@556: 	Node v=this->graph->aNode(e.out);
marci@556: 	this->graph->next(e.out);
marci@556: 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
marci@556: 	  this->graph->next(e.out); }
marci@556: 	if (!this->graph->valid(e.out)) {
marci@565: 	  e.backward=true;
marci@556: 	  this->graph->first(e.in, v); 
marci@556: 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
marci@556: 	    this->graph->next(e.in); }
marci@556: 	}
marci@556:       } else {
marci@556: 	this->graph->next(e.in);
marci@556: 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
marci@556: 	  this->graph->next(e.in); } 
marci@556:       }
marci@556:       return e;
marci@556:     }
marci@556: //     FIXME Not tested
marci@556:     InEdgeIt& next(InEdgeIt& e) const { 
marci@565:       if (!e.backward) {
marci@556: 	Node v=this->graph->aNode(e.in);
marci@556: 	this->graph->next(e.in);
marci@556: 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
marci@556: 	  this->graph->next(e.in); }
marci@556: 	if (!this->graph->valid(e.in)) {
marci@565: 	  e.backward=true;
marci@556: 	  this->graph->first(e.out, v); 
marci@556: 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
marci@556: 	    this->graph->next(e.out); }
marci@556: 	}
marci@556:       } else {
marci@556: 	this->graph->next(e.out);
marci@556: 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
marci@556: 	  this->graph->next(e.out); } 
marci@556:       }
marci@556:       return e;
marci@556:     }
marci@556:     EdgeIt& next(EdgeIt& e) const {
marci@565:       if (!e.backward) {
marci@556: 	this->graph->next(e.e);
marci@556: 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
marci@556: 	  this->graph->next(e.e); }
marci@556: 	if (!this->graph->valid(e.e)) {
marci@565: 	  e.backward=true;
marci@556: 	  this->graph->first(e.e); 
marci@556: 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
marci@556: 	    this->graph->next(e.e); }
marci@556: 	}
marci@556:       } else {
marci@556: 	this->graph->next(e.e);
marci@556: 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
marci@556: 	  this->graph->next(e.e); } 
marci@556:       }
marci@556:       return e;
marci@556:     }
marci@556: 
marci@556:     Node tail(Edge e) const { 
marci@565:       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
marci@556:     Node head(Edge e) const { 
marci@565:       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
marci@556: 
marci@556:     Node aNode(OutEdgeIt e) const { 
marci@565:       return ((!e.backward) ? this->graph->aNode(e.out) : 
marci@556: 	      this->graph->aNode(e.in)); }
marci@556:     Node bNode(OutEdgeIt e) const { 
marci@565:       return ((!e.backward) ? this->graph->bNode(e.out) : 
marci@556: 	      this->graph->bNode(e.in)); }
marci@556: 
marci@556:     Node aNode(InEdgeIt e) const { 
marci@565:       return ((!e.backward) ? this->graph->aNode(e.in) : 
marci@556: 	      this->graph->aNode(e.out)); }
marci@556:     Node bNode(InEdgeIt e) const { 
marci@565:       return ((!e.backward) ? this->graph->bNode(e.in) : 
marci@556: 	      this->graph->bNode(e.out)); }
marci@556: 
marci@556: //    int nodeNum() const { return graph->nodeNum(); }
marci@556:     //FIXME
marci@556:     void edgeNum() const { }
marci@556:     //int edgeNum() const { return graph->edgeNum(); }
marci@556: 
marci@556: 
marci@556: //    int id(Node v) const { return graph->id(v); }
marci@556: 
marci@556:     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
marci@556:     bool valid(Edge e) const { 
marci@556:       return this->graph->valid(e);
marci@556: 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
marci@556:     }
marci@556: 
marci@565:     bool forward(const Edge& e) const { return !e.backward; }
marci@565:     bool backward(const Edge& e) const { return e.backward; }
marci@556: 
marci@556:     void augment(const Edge& e, Number a) const {
marci@565:       if (!e.backward)  
marci@556: // 	flow->set(e.out, flow->get(e.out)+a);
marci@556: 	flow->set(e, (*flow)[e]+a);
marci@556:       else  
marci@556: // 	flow->set(e.in, flow->get(e.in)-a);
marci@556: 	flow->set(e, (*flow)[e]-a);
marci@556:     }
marci@556: 
marci@556:     Number resCap(const Edge& e) const { 
marci@565:       if (!e.backward) 
marci@556: //	return (capacity->get(e.out)-flow->get(e.out)); 
marci@556: 	return ((*capacity)[e]-(*flow)[e]); 
marci@556:       else 
marci@556: //	return (flow->get(e.in)); 
marci@556: 	return ((*flow)[e]); 
marci@556:     }
marci@556: 
marci@556: //     Number resCap(typename Graph::OutEdgeIt out) const { 
marci@556: // //      return (capacity->get(out)-flow->get(out)); 
marci@556: //       return ((*capacity)[out]-(*flow)[out]); 
marci@556: //     }
marci@556:     
marci@556: //     Number resCap(typename Graph::InEdgeIt in) const { 
marci@556: // //      return (flow->get(in)); 
marci@556: //       return ((*flow)[in]); 
marci@556: //     }
marci@556: 
marci@556:     template <typename T>
marci@556:     class EdgeMap {
marci@556:       typename Graph::template EdgeMap<T> forward_map, backward_map; 
marci@556:     public:
marci@624:       typedef T ValueType;
marci@624:       typedef Edge KeyType;
marci@556:       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
marci@556:       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
marci@556:       void set(Edge e, T a) { 
marci@565: 	if (!e.backward) 
marci@624: 	  forward_map.set(e/*.out*/, a); 
marci@556: 	else 
marci@624: 	  backward_map.set(e/*.in*/, a); 
marci@556:       }
marci@556:       T operator[](Edge e) const { 
marci@565: 	if (!e.backward) 
marci@624: 	  return forward_map[e/*.out*/]; 
marci@556: 	else 
marci@624: 	  return backward_map[e/*.in*/]; 
marci@556:       }
marci@625:       void update() { 
marci@625: 	forward_map.update(); 
marci@625: 	backward_map.update();
marci@625:       }
marci@556: //       T get(Edge e) const { 
marci@556: // 	if (e.out_or_in) 
marci@556: // 	  return forward_map.get(e.out); 
marci@556: // 	else 
marci@556: // 	  return backward_map.get(e.in); 
marci@556: //       }
marci@556:     };
marci@556:   };
marci@556: 
marci@569: 
marci@569: 
marci@612:   /// For blocking flows.
marci@556: 
marci@612:   /// This graph wrapper is used for 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@556:   ///\author Marton Makai
marci@556:   template<typename Graph, typename FirstOutEdgesMap>
marci@556:   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
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: //     class NodeIt { 
marci@556: //       friend class GraphWrapper<Graph>;
marci@556: //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@556: //       typename Graph::NodeIt n;
marci@556: //      public:
marci@556: //       NodeIt() { }
marci@556: //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
marci@556: //       NodeIt(const Invalid& i) : n(i) { }
marci@556: //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
marci@556: // 	n(*(_G.graph)) { }
marci@556: //       operator Node() const { return Node(typename Graph::Node(n)); }
marci@556: //     };
marci@556:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@556:     class OutEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@556: //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
marci@556:       typename Graph::OutEdgeIt e;
marci@556:     public:
marci@556:       OutEdgeIt() { }
marci@556:       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
marci@556:       OutEdgeIt(const Invalid& i) : e(i) { }
marci@556:       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
marci@556: 		const Node& _n) : 
marci@556: 	e((*_G.first_out_edges)[_n]) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556:     class InEdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@556: //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
marci@556:       typename Graph::InEdgeIt e;
marci@556:     public:
marci@556:       InEdgeIt() { }
marci@556:       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
marci@556:       InEdgeIt(const Invalid& i) : e(i) { }
marci@556:       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
marci@556: 	       const Node& _n) : 
marci@556: 	e(*(_G.graph), typename Graph::Node(_n)) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556:     //typedef typename Graph::SymEdgeIt SymEdgeIt;
marci@556:     class EdgeIt { 
marci@556:       friend class GraphWrapper<Graph>;
marci@556:       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
marci@556: //      typedef typename Graph::EdgeIt GraphEdgeIt;
marci@556:       typename Graph::EdgeIt e;
marci@556:     public:
marci@556:       EdgeIt() { }
marci@556:       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
marci@556:       EdgeIt(const Invalid& i) : e(i) { }
marci@556:       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
marci@556: 	e(*(_G.graph)) { }
marci@556:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@556:     };
marci@556: 
marci@556:     using GraphWrapper<Graph>::first;
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:     using GraphWrapper<Graph>::next;
marci@556: //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
marci@556:     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@556:     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@556:     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
marci@556:     
marci@556:     Node aNode(const OutEdgeIt& e) const { 
marci@556:       return Node(this->graph->aNode(e.e)); }
marci@556:     Node aNode(const InEdgeIt& e) const { 
marci@556:       return Node(this->graph->aNode(e.e)); }
marci@556:     Node bNode(const OutEdgeIt& e) const { 
marci@556:       return Node(this->graph->bNode(e.e)); }
marci@556:     Node bNode(const InEdgeIt& e) const { 
marci@556:       return Node(this->graph->bNode(e.e)); }
marci@556: 
marci@556:     void erase(const OutEdgeIt& e) const {
marci@556:       OutEdgeIt f=e;
marci@556:       this->next(f);
marci@556:       first_out_edges->set(this->tail(e), f.e);
marci@556:     }
marci@556:   };
marci@556: 
marci@556:   ///@}
marci@556: 
marci@556: } //namespace hugo
marci@556: 
marci@556: #endif //HUGO_GRAPH_WRAPPER_H
marci@556: