alpar@906: /* -*- C++ -*-
ladanyi@1435:  * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
alpar@906:  *
alpar@1164:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@1401: #ifndef LEMON_GRAPH_ADAPTOR_H
alpar@1401: #define LEMON_GRAPH_ADAPTOR_H
marci@556: 
alpar@1401: ///\ingroup graph_adaptors
marci@556: ///\file
alpar@1401: ///\brief Several graph adaptors.
marci@556: ///
alpar@1401: ///This file contains several useful graph adaptor functions.
marci@556: ///
marci@556: ///\author Marton Makai
marci@556: 
alpar@921: #include <lemon/invalid.h>
alpar@921: #include <lemon/maps.h>
deba@1472: #include <lemon/bits/erasable_graph_extender.h>
deba@1472: #include <lemon/bits/clearable_graph_extender.h>
deba@1472: #include <lemon/bits/extendable_graph_extender.h>
deba@1307: #include <lemon/bits/iterable_graph_extender.h>
deba@1472: #include <lemon/bits/alteration_notifier.h>
deba@1472: #include <lemon/bits/default_map.h>
marci@1383: #include <lemon/bits/undir_graph_extender.h>
alpar@774: #include <iostream>
marci@556: 
alpar@921: namespace lemon {
marci@556: 
alpar@1401:   // Graph adaptors
marci@556: 
marci@1172:   /*!
alpar@1401:     \addtogroup graph_adaptors
marci@1004:     @{
marci@1172:    */
marci@556: 
marci@1172:   /*! 
alpar@1401:     Base type for the Graph Adaptors
marci@1242:     
alpar@1401:     \warning Graph adaptors are in even more experimental state than the other
marci@1004:     parts of the lib. Use them at you own risk.
marci@1242:     
alpar@1401:     This is the base type for most of LEMON graph adaptors. 
alpar@1401:     This class implements a trivial graph adaptor i.e. it only wraps the 
marci@1004:     functions and types of the graph. The purpose of this class is to 
alpar@1401:     make easier implementing graph adaptors. E.g. if an adaptor is 
marci@1004:     considered which differs from the wrapped graph only in some of its 
alpar@1401:     functions or types, then it can be derived from GraphAdaptor, and only the 
marci@1004:     differences should be implemented.
marci@1004:   
marci@1004:     \author Marton Makai 
marci@1004:   */
marci@970:   template<typename _Graph>
alpar@1401:   class GraphAdaptorBase {
marci@970:   public:
marci@970:     typedef _Graph Graph;
marci@970:     /// \todo Is it needed?
marci@970:     typedef Graph BaseGraph;
marci@970:     typedef Graph ParentGraph;
marci@970: 
marci@556:   protected:
marci@556:     Graph* graph;
alpar@1401:     GraphAdaptorBase() : graph(0) { }
marci@556:     void setGraph(Graph& _graph) { graph=&_graph; }
marci@556: 
marci@556:   public:
alpar@1401:     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
marci@556:  
alpar@774:     typedef typename Graph::Node Node;
alpar@774:     typedef typename Graph::Edge Edge;
marci@556:    
marci@970:     void first(Node& i) const { graph->first(i); }
marci@970:     void first(Edge& i) const { graph->first(i); }
marci@970:     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
marci@970:     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
marci@556: 
marci@970:     void next(Node& i) const { graph->next(i); }
marci@970:     void next(Edge& i) const { graph->next(i); }
marci@970:     void nextIn(Edge& i) const { graph->nextIn(i); }
marci@970:     void nextOut(Edge& i) const { graph->nextOut(i); }
marci@970: 
alpar@986:     Node source(const Edge& e) const { return graph->source(e); }
alpar@986:     Node target(const Edge& e) const { return graph->target(e); }
marci@556: 
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()); }
alpar@986:     Edge addEdge(const Node& source, const Node& target) const { 
alpar@986:       return Edge(graph->addEdge(source, target)); }
marci@556: 
marci@556:     void erase(const Node& i) const { graph->erase(i); }
marci@556:     void erase(const Edge& i) const { graph->erase(i); }
marci@556:   
marci@556:     void clear() const { graph->clear(); }
marci@556:     
marci@739:     int id(const Node& v) const { return graph->id(v); }
marci@739:     int id(const Edge& e) const { return graph->id(e); }
marci@650:     
deba@1627:     Edge oppositeNode(const Edge& e) const { 
deba@1627:       return Edge(graph->opposite(e)); 
deba@1627:     }
marci@650: 
marci@970:     template <typename _Value>
marci@970:     class NodeMap : public _Graph::template NodeMap<_Value> {
marci@970:     public:
marci@970:       typedef typename _Graph::template NodeMap<_Value> Parent;
alpar@1401:       NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
alpar@1401:       NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
marci@970:       : Parent(*gw.graph, value) { }
marci@970:     };
marci@556: 
marci@970:     template <typename _Value>
marci@970:     class EdgeMap : public _Graph::template EdgeMap<_Value> {
marci@970:     public:
marci@970:       typedef typename _Graph::template EdgeMap<_Value> Parent;
alpar@1401:       EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
alpar@1401:       EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
marci@970:       : Parent(*gw.graph, value) { }
marci@970:     };
deba@877: 
marci@556:   };
marci@556: 
marci@970:   template <typename _Graph>
alpar@1401:   class GraphAdaptor :
alpar@1401:     public IterableGraphExtender<GraphAdaptorBase<_Graph> > { 
marci@970:   public:
marci@970:     typedef _Graph Graph;
alpar@1401:     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
marci@970:   protected:
alpar@1401:     GraphAdaptor() : Parent() { }
marci@569: 
marci@970:   public:
alpar@1401:     GraphAdaptor(Graph& _graph) { setGraph(_graph); }
marci@970:   };
marci@569: 
marci@997:   template <typename _Graph>
alpar@1401:   class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@997:   public:
marci@997:     typedef _Graph Graph;
alpar@1401:     typedef GraphAdaptorBase<_Graph> Parent;
marci@997:   protected:
alpar@1401:     RevGraphAdaptorBase() : Parent() { }
marci@997:   public:
marci@997:     typedef typename Parent::Node Node;
marci@997:     typedef typename Parent::Edge Edge;
marci@997: 
marci@1383:     //    using Parent::first;
marci@997:     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
marci@997:     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
marci@997: 
marci@1383:     //    using Parent::next;
marci@997:     void nextIn(Edge& i) const { Parent::nextOut(i); }
marci@997:     void nextOut(Edge& i) const { Parent::nextIn(i); }
marci@997: 
marci@997:     Node source(const Edge& e) const { return Parent::target(e); }
marci@997:     Node target(const Edge& e) const { return Parent::source(e); }
marci@997:   };
marci@997:     
marci@997: 
alpar@1401:   /// A graph adaptor which reverses the orientation of the edges.
marci@556: 
alpar@1401:   ///\warning Graph adaptors 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. 
alpar@1401:   /// Then RevGraphAdaptor 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
alpar@1401:   /// RevGraphAdaptor<ListGraph> gw(g);
marci@923:   /// \endcode
marci@556:   ///\author Marton Makai
marci@997:   template<typename _Graph>
alpar@1401:   class RevGraphAdaptor : 
alpar@1401:     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
marci@650:   public:
marci@997:     typedef _Graph Graph;
marci@997:     typedef IterableGraphExtender<
alpar@1401:       RevGraphAdaptorBase<_Graph> > Parent;
marci@556:   protected:
alpar@1401:     RevGraphAdaptor() { }
marci@556:   public:
alpar@1401:     RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
marci@997:   };
marci@556: 
marci@992:   
marci@992:   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
alpar@1401:   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992:   public:
marci@992:     typedef _Graph Graph;
alpar@1401:     typedef GraphAdaptorBase<_Graph> Parent;
marci@992:   protected:
marci@992:     NodeFilterMap* node_filter_map;
marci@992:     EdgeFilterMap* edge_filter_map;
alpar@1401:     SubGraphAdaptorBase() : Parent(), 
marci@992: 			    node_filter_map(0), edge_filter_map(0) { }
marci@775: 
marci@992:     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
marci@992:       node_filter_map=&_node_filter_map;
marci@992:     }
marci@992:     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
marci@992:       edge_filter_map=&_edge_filter_map;
marci@992:     }
marci@992: 
marci@992:   public:
alpar@1401: //     SubGraphAdaptorBase(Graph& _graph, 
marci@992: // 			NodeFilterMap& _node_filter_map, 
marci@992: // 			EdgeFilterMap& _edge_filter_map) : 
marci@992: //       Parent(&_graph), 
marci@992: //       node_filter_map(&node_filter_map), 
marci@992: //       edge_filter_map(&edge_filter_map) { }
marci@992: 
marci@992:     typedef typename Parent::Node Node;
marci@992:     typedef typename Parent::Edge Edge;
marci@992: 
marci@992:     void first(Node& i) const { 
marci@992:       Parent::first(i); 
marci@992:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
marci@992:     }
marci@992:     void first(Edge& i) const { 
marci@992:       Parent::first(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
marci@992:     }
marci@992:     void firstIn(Edge& i, const Node& n) const { 
marci@992:       Parent::firstIn(i, n); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
marci@992:     }
marci@992:     void firstOut(Edge& i, const Node& n) const { 
marci@992:       Parent::firstOut(i, n); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
marci@992:     }
marci@992: 
marci@992:     void next(Node& i) const { 
marci@992:       Parent::next(i); 
marci@992:       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
marci@992:     }
marci@992:     void next(Edge& i) const { 
marci@992:       Parent::next(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
marci@992:     }
marci@992:     void nextIn(Edge& i) const { 
marci@992:       Parent::nextIn(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
marci@992:     }
marci@992:     void nextOut(Edge& i) const { 
marci@992:       Parent::nextOut(i); 
marci@992:       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
marci@992:     }
marci@992: 
marci@992:     /// This function hides \c n in the graph, i.e. the iteration 
marci@992:     /// jumps over it. This is done by simply setting the value of \c n  
marci@992:     /// to be false in the corresponding node-map.
marci@992:     void hide(const Node& n) const { node_filter_map->set(n, false); }
marci@992: 
marci@992:     /// This function hides \c e in the graph, i.e. the iteration 
marci@992:     /// jumps over it. This is done by simply setting the value of \c e  
marci@992:     /// to be false in the corresponding edge-map.
marci@992:     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
marci@992: 
marci@992:     /// The value of \c n is set to be true in the node-map which stores 
marci@992:     /// hide information. If \c n was hidden previuosly, then it is shown 
marci@992:     /// again
marci@992:      void unHide(const Node& n) const { node_filter_map->set(n, true); }
marci@992: 
marci@992:     /// The value of \c e is set to be true in the edge-map which stores 
marci@992:     /// hide information. If \c e was hidden previuosly, then it is shown 
marci@992:     /// again
marci@992:     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
marci@992: 
marci@992:     /// Returns true if \c n is hidden.
marci@992:     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
marci@992: 
marci@992:     /// Returns true if \c n is hidden.
marci@992:     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
marci@992: 
marci@992:     /// \warning This is a linear time operation and works only if s
marci@992:     /// \c Graph::NodeIt is defined.
marci@992:     /// \todo assign tags.
marci@992:     int nodeNum() const { 
marci@992:       int i=0;
marci@992:       Node n;
marci@992:       for (first(n); n!=INVALID; next(n)) ++i;
marci@992:       return i; 
marci@992:     }
marci@992: 
marci@992:     /// \warning This is a linear time operation and works only if 
marci@992:     /// \c Graph::EdgeIt is defined.
marci@992:     /// \todo assign tags.
marci@992:     int edgeNum() const { 
marci@992:       int i=0;
marci@992:       Edge e;
marci@992:       for (first(e); e!=INVALID; next(e)) ++i;
marci@992:       return i; 
marci@992:     }
marci@992: 
marci@992: 
marci@992:   };
marci@775: 
alpar@1401:   /*! \brief A graph adaptor for hiding nodes and edges from a graph.
marci@1242:     
alpar@1401:   \warning Graph adaptors are in even more experimental state than the other
marci@930:   parts of the lib. Use them at you own risk.
marci@930:   
alpar@1401:   SubGraphAdaptor shows the graph with filtered node-set and 
marci@930:   edge-set. 
marci@1242:   Let \f$G=(V, A)\f$ be a directed graph 
marci@1242:   and suppose that the graph instance \c g of type ListGraph implements 
marci@1242:   \f$G\f$. 
marci@1242:   Let moreover \f$b_V\f$ and 
marci@1242:   \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set. 
alpar@1401:   SubGraphAdaptor<...>::NodeIt iterates 
marci@1242:   on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and 
alpar@1401:   SubGraphAdaptor<...>::EdgeIt iterates 
marci@1242:   on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly, 
alpar@1401:   SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates 
marci@1242:   only on edges leaving and entering a specific node which have true value.
marci@1242: 
marci@1242:   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@1242:   edge-set. 
marci@930:   \code
marci@1242:   typedef ListGraph 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);
alpar@1401:   typedef SubGraphAdaptor<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: 
alpar@1401:   For other examples see also the documentation of NodeSubGraphAdaptor and 
alpar@1401:   EdgeSubGraphAdaptor.
marci@930: 
marci@930:   \author Marton Makai
marci@930:   */
marci@992:   template<typename _Graph, typename NodeFilterMap, 
marci@556: 	   typename EdgeFilterMap>
alpar@1401:   class SubGraphAdaptor : 
marci@992:     public IterableGraphExtender<
alpar@1401:     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
marci@650:   public:
marci@992:     typedef _Graph Graph;
marci@992:     typedef IterableGraphExtender<
alpar@1401:       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
marci@556:   protected:
alpar@1401:     SubGraphAdaptor() { }
marci@992:   public:
alpar@1401:     SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, 
marci@992: 		    EdgeFilterMap& _edge_filter_map) { 
marci@992:       setGraph(_graph);
marci@992:       setNodeFilterMap(_node_filter_map);
marci@992:       setEdgeFilterMap(_edge_filter_map);
marci@992:     }
marci@992:   };
marci@556: 
marci@556: 
marci@569: 
alpar@1401:   /*! \brief An adaptor for hiding nodes from a graph.
marci@933: 
alpar@1401:   \warning Graph adaptors are in even more experimental state than the other
marci@933:   parts of the lib. Use them at you own risk.
marci@933:   
alpar@1401:   An adaptor for hiding nodes from a graph.
alpar@1401:   This adaptor specializes SubGraphAdaptor 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>
alpar@1401:   class NodeSubGraphAdaptor : 
alpar@1401:     public SubGraphAdaptor<Graph, NodeFilterMap, 
marci@933: 			   ConstMap<typename Graph::Edge,bool> > {
marci@933:   public:
alpar@1401:     typedef SubGraphAdaptor<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:
alpar@1401:     NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
marci@933:       Parent(), const_true_map(true) { 
marci@933:       Parent::setGraph(_graph);
marci@933:       Parent::setNodeFilterMap(_node_filter_map);
marci@933:       Parent::setEdgeFilterMap(const_true_map);
marci@933:     }
marci@933:   };
marci@933: 
marci@933: 
alpar@1401:   /*! \brief An adaptor for hiding edges from a graph.
marci@932: 
alpar@1401:   \warning Graph adaptors are in even more experimental state than the other
marci@932:   parts of the lib. Use them at you own risk.
marci@932:   
alpar@1401:   An adaptor for hiding edges from a graph.
alpar@1401:   This adaptor specializes SubGraphAdaptor in the way that only the edge-set 
alpar@1401:   can be filtered. The usefulness of this adaptor 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@1252:   need's some elementary knowledge from combinatorial optimization. 
marci@933: 
marci@933:   If a single shortest path is to be 
marci@1252:   searched between \c s and \c t, then this can be done easily by 
marci@1252:   applying the Dijkstra algorithm. 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 
alpar@1536:   graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. 
marci@1425:   The full source code is available in \ref sub_graph_adaptor_demo.cc. 
marci@1425:   If you are interested in more demo programs, you can use 
marci@1425:   \ref dim_to_dot.cc to generate .dot files from dimacs files. 
athos@1576:   The .dot file of the following figure was generated by  
marci@1425:   the demo program \ref dim_to_dot.cc.
marci@1425: 
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: 
alpar@986:   cout << "edges with lengths (of form id, source--length->target): " << endl;
marci@933:   for(EdgeIt e(g); e!=INVALID; ++e) 
alpar@986:     cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 
alpar@986:          << length[e] << "->" << g.id(g.target(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:   
alpar@1401:   typedef EdgeSubGraphAdaptor<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])
alpar@986:       cout << " " << g.id(g.source(e)) << "--" 
alpar@986: 	   << length[e] << "->" << g.id(g.target(e)) << endl;
marci@933:   \endcode
marci@933:   The program has the following (expected :-)) output:
marci@933:   \code
alpar@986:   edges with lengths (of form id, source--length->target):
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>
alpar@1401:   class EdgeSubGraphAdaptor : 
alpar@1401:     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
marci@932: 			   EdgeFilterMap> {
marci@932:   public:
alpar@1401:     typedef SubGraphAdaptor<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:
alpar@1401:     EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : 
marci@932:       Parent(), const_true_map(true) { 
marci@932:       Parent::setGraph(_graph);
marci@932:       Parent::setNodeFilterMap(const_true_map);
marci@932:       Parent::setEdgeFilterMap(_edge_filter_map);
marci@932:     }
marci@932:   };
marci@932: 
marci@1383:   template <typename _Graph>
alpar@1401:   class UndirGraphAdaptorBase : 
alpar@1401:     public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
marci@1383:   public:
marci@1383:     typedef _Graph Graph;
alpar@1401:     typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
marci@1383:   protected:
alpar@1401:     UndirGraphAdaptorBase() : Parent() { }
marci@1383:   public:
marci@1383:     typedef typename Parent::UndirEdge UndirEdge;
marci@1383:     typedef typename Parent::Edge Edge;
marci@1383:     
marci@1383:     /// \bug Why cant an edge say that it is forward or not??? 
marci@1383:     /// By this, a pointer to the graph have to be stored
marci@1383:     /// The implementation
marci@1383:     template <typename T>
marci@1383:     class EdgeMap {
marci@1383:     protected:
alpar@1401:       const UndirGraphAdaptorBase<_Graph>* g;
marci@1383:       template <typename TT> friend class EdgeMap;
marci@1383:       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
marci@1383:     public:
marci@1383:       typedef T Value;
marci@1383:       typedef Edge Key;
marci@1383:       
alpar@1401:       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g), 
marci@1383: 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }
marci@569: 
alpar@1401:       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
marci@1383: 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
marci@1383:       
marci@1383:       void set(Edge e, T a) { 
deba@1627: 	if (g->direction(e)) 
marci@1383: 	  forward_map.set(e, a); 
marci@1383: 	else 
marci@1383: 	  backward_map.set(e, a); 
marci@1383:       }
marci@556: 
marci@1383:       T operator[](Edge e) const { 
deba@1627: 	if (g->direction(e)) 
marci@1383: 	  return forward_map[e]; 
marci@1383: 	else 
marci@1383: 	  return backward_map[e]; 
marci@556:       }
marci@556:     };
marci@1383:         
marci@1383:     template <typename T>
marci@1383:     class UndirEdgeMap {
marci@1383:       template <typename TT> friend class UndirEdgeMap;
marci@1383:       typename _Graph::template EdgeMap<T> map; 
marci@1383:     public:
marci@1383:       typedef T Value;
marci@1383:       typedef UndirEdge Key;
marci@1383:       
alpar@1401:       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) : 
marci@1383: 	map(*(g.graph)) { }
marci@556: 
alpar@1401:       UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) : 
marci@1383: 	map(*(g.graph), a) { }
marci@1383:       
marci@1383:       void set(UndirEdge e, T a) { 
marci@1383: 	map.set(e, a); 
marci@1383:       }
marci@556: 
marci@1383:       T operator[](UndirEdge e) const { 
marci@1383: 	return map[e]; 
marci@1383:       }
marci@1383:     };
marci@1383:       
marci@1383:   };
marci@1383: 
alpar@1401:   /// \brief An undirected graph is made from a directed graph by an adaptor
marci@1383:   ///
marci@1383:   /// Undocumented, untested!!!
marci@1383:   /// If somebody knows nice demo application, let's polulate it.
marci@1383:   /// 
marci@1383:   /// \author Marton Makai
marci@1383:   template<typename _Graph>
alpar@1401:   class UndirGraphAdaptor : 
marci@1383:     public IterableUndirGraphExtender<
alpar@1401:     UndirGraphAdaptorBase<_Graph> > {
marci@1383:   public:
marci@1383:     typedef _Graph Graph;
marci@1383:     typedef IterableUndirGraphExtender<
alpar@1401:       UndirGraphAdaptorBase<_Graph> > Parent;
marci@1383:   protected:
alpar@1401:     UndirGraphAdaptor() { }
marci@1383:   public:
alpar@1401:     UndirGraphAdaptor(_Graph& _graph) { 
marci@1383:       setGraph(_graph);
marci@556:     }
marci@556:   };
marci@556: 
marci@992:   
marci@992:   template <typename _Graph, 
marci@992: 	    typename ForwardFilterMap, typename BackwardFilterMap>
alpar@1401:   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@992:   public:
marci@992:     typedef _Graph Graph;
alpar@1401:     typedef GraphAdaptorBase<_Graph> Parent;
marci@992:   protected:
marci@992:     ForwardFilterMap* forward_filter;
marci@992:     BackwardFilterMap* backward_filter;
alpar@1401:     SubBidirGraphAdaptorBase() : Parent(), 
marci@992: 				 forward_filter(0), backward_filter(0) { }
marci@992: 
marci@992:     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
marci@992:       forward_filter=&_forward_filter;
marci@992:     }
marci@992:     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
marci@992:       backward_filter=&_backward_filter;
marci@992:     }
marci@992: 
marci@992:   public:
alpar@1401: //     SubGraphAdaptorBase(Graph& _graph, 
marci@992: // 			NodeFilterMap& _node_filter_map, 
marci@992: // 			EdgeFilterMap& _edge_filter_map) : 
marci@992: //       Parent(&_graph), 
marci@992: //       node_filter_map(&node_filter_map), 
marci@992: //       edge_filter_map(&edge_filter_map) { }
marci@992: 
marci@992:     typedef typename Parent::Node Node;
marci@992:     typedef typename _Graph::Edge GraphEdge;
marci@992:     template <typename T> class EdgeMap;
alpar@1401:     /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from 
marci@992:     /// _Graph::Edge. It contains an extra bool flag which is true 
marci@992:     /// if and only if the 
marci@992:     /// edge is the backward version of the original edge.
marci@992:     class Edge : public _Graph::Edge {
alpar@1401:       friend class SubBidirGraphAdaptorBase<
marci@992: 	Graph, ForwardFilterMap, BackwardFilterMap>;
marci@992:       template<typename T> friend class EdgeMap;
marci@992:     protected:
marci@992:       bool backward; //true, iff backward
marci@992:     public:
marci@992:       Edge() { }
marci@992:       /// \todo =false is needed, or causes problems?
marci@992:       /// If \c _backward is false, then we get an edge corresponding to the 
marci@992:       /// original one, otherwise its oppositely directed pair is obtained.
marci@992:       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : 
marci@992: 	_Graph::Edge(e), backward(_backward) { }
marci@992:       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
marci@992:       bool operator==(const Edge& v) const { 
marci@992: 	return (this->backward==v.backward && 
marci@992: 		static_cast<typename _Graph::Edge>(*this)==
marci@992: 		static_cast<typename _Graph::Edge>(v));
marci@992:       } 
marci@992:       bool operator!=(const Edge& v) const { 
marci@992: 	return (this->backward!=v.backward || 
marci@992: 		static_cast<typename _Graph::Edge>(*this)!=
marci@992: 		static_cast<typename _Graph::Edge>(v));
marci@992:       }
marci@992:     };
marci@992: 
marci@992:     void first(Node& i) const { 
marci@992:       Parent::first(i); 
marci@992:     }
marci@992: 
marci@992:     void first(Edge& i) const { 
marci@992:       Parent::first(i); 
marci@992:       i.backward=false;
marci@992:       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	     !(*forward_filter)[i]) Parent::next(i);
marci@992:       if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: 	Parent::first(i); 
marci@992: 	i.backward=true;
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*backward_filter)[i]) Parent::next(i);
marci@992:       }
marci@992:     }
marci@992: 
marci@992:     void firstIn(Edge& i, const Node& n) const { 
marci@992:       Parent::firstIn(i, n); 
marci@992:       i.backward=false;
marci@992:       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@1269: 	     !(*forward_filter)[i]) Parent::nextIn(i);
marci@992:       if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: 	Parent::firstOut(i, n); 
marci@992: 	i.backward=true;
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*backward_filter)[i]) Parent::nextOut(i);
marci@992:       }
marci@992:     }
marci@992: 
marci@992:     void firstOut(Edge& i, const Node& n) const { 
marci@992:       Parent::firstOut(i, n); 
marci@992:       i.backward=false;
marci@992:       while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	     !(*forward_filter)[i]) Parent::nextOut(i);
marci@992:       if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: 	Parent::firstIn(i, n); 
marci@992: 	i.backward=true;
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*backward_filter)[i]) Parent::nextIn(i);
marci@992:       }
marci@992:     }
marci@992: 
marci@992:     void next(Node& i) const { 
marci@992:       Parent::next(i); 
marci@992:     }
marci@992: 
marci@992:     void next(Edge& i) const { 
marci@992:       if (!(i.backward)) {
marci@992: 	Parent::next(i);
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*forward_filter)[i]) Parent::next(i);
marci@992: 	if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: 	  Parent::first(i); 
marci@992: 	  i.backward=true;
marci@992: 	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 		 !(*backward_filter)[i]) Parent::next(i);
marci@992: 	}
marci@992:       } else {
marci@992: 	Parent::next(i);
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*backward_filter)[i]) Parent::next(i);
marci@992:       }
marci@992:     }
marci@992: 
marci@992:     void nextIn(Edge& i) const { 
marci@992:       if (!(i.backward)) {
marci@992: 	Node n=Parent::target(i);
marci@992: 	Parent::nextIn(i);
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*forward_filter)[i]) Parent::nextIn(i);
marci@992: 	if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: 	  Parent::firstOut(i, n); 
marci@992: 	  i.backward=true;
marci@992: 	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 		 !(*backward_filter)[i]) Parent::nextOut(i);
marci@992: 	}
marci@992:       } else {
marci@992: 	Parent::nextOut(i);
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*backward_filter)[i]) Parent::nextOut(i);
marci@992:       }
marci@992:     }
marci@992: 
marci@992:     void nextOut(Edge& i) const { 
marci@992:       if (!(i.backward)) {
marci@992: 	Node n=Parent::source(i);
marci@992: 	Parent::nextOut(i);
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*forward_filter)[i]) Parent::nextOut(i);
marci@992: 	if (*static_cast<GraphEdge*>(&i)==INVALID) {
marci@992: 	  Parent::firstIn(i, n); 
marci@992: 	  i.backward=true;
marci@992: 	  while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 		 !(*backward_filter)[i]) Parent::nextIn(i);
marci@992: 	}
marci@992:       } else {
marci@992: 	Parent::nextIn(i);
marci@992: 	while (*static_cast<GraphEdge*>(&i)!=INVALID && 
marci@992: 	       !(*backward_filter)[i]) Parent::nextIn(i);
marci@992:       }
marci@992:     }
marci@992: 
marci@992:     Node source(Edge e) const { 
marci@992:       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
marci@992:     Node target(Edge e) const { 
marci@992:       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
marci@992: 
marci@992:     /// Gives back the opposite edge.
marci@992:     Edge opposite(const Edge& e) const { 
marci@992:       Edge f=e;
marci@992:       f.backward=!f.backward;
marci@992:       return f;
marci@992:     }
marci@992: 
marci@992:     /// \warning This is a linear time operation and works only if 
marci@992:     /// \c Graph::EdgeIt is defined.
marci@992:     /// \todo hmm
marci@992:     int edgeNum() const { 
marci@992:       int i=0;
marci@992:       Edge e;
marci@992:       for (first(e); e!=INVALID; next(e)) ++i;
marci@992:       return i; 
marci@992:     }
marci@992: 
marci@992:     bool forward(const Edge& e) const { return !e.backward; }
marci@992:     bool backward(const Edge& e) const { return e.backward; }
marci@992: 
marci@992:     template <typename T>
alpar@1401:     /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two 
marci@992:     /// _Graph::EdgeMap one for the forward edges and 
marci@992:     /// one for the backward edges.
marci@992:     class EdgeMap {
marci@992:       template <typename TT> friend class EdgeMap;
marci@992:       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
marci@992:     public:
marci@992:       typedef T Value;
marci@992:       typedef Edge Key;
marci@992: 
alpar@1401:       EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
marci@992: 	      ForwardFilterMap, BackwardFilterMap>& g) : 
marci@992: 	forward_map(*(g.graph)), backward_map(*(g.graph)) { }
marci@992: 
alpar@1401:       EdgeMap(const SubBidirGraphAdaptorBase<_Graph, 
marci@992: 	      ForwardFilterMap, BackwardFilterMap>& g, T a) : 
marci@992: 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
marci@992:       
marci@992:       void set(Edge e, T a) { 
marci@992: 	if (!e.backward) 
marci@992: 	  forward_map.set(e, a); 
marci@992: 	else 
marci@992: 	  backward_map.set(e, a); 
marci@992:       }
marci@992: 
marci@992: //       typename _Graph::template EdgeMap<T>::ConstReference 
marci@992: //       operator[](Edge e) const { 
marci@992: // 	if (!e.backward) 
marci@992: // 	  return forward_map[e]; 
marci@992: // 	else 
marci@992: // 	  return backward_map[e]; 
marci@992: //       }
marci@992: 
marci@992: //      typename _Graph::template EdgeMap<T>::Reference 
marci@1016:       T operator[](Edge e) const { 
marci@992: 	if (!e.backward) 
marci@992: 	  return forward_map[e]; 
marci@992: 	else 
marci@992: 	  return backward_map[e]; 
marci@992:       }
marci@992: 
marci@992:       void update() { 
marci@992: 	forward_map.update(); 
marci@992: 	backward_map.update();
marci@992:       }
marci@992:     };
marci@992: 
marci@992:   };
marci@569: 
marci@650: 
alpar@1401:   ///\brief An adaptor for composing a subgraph of a 
marci@792:   /// bidirected graph made from a directed one. 
marci@612:   ///
alpar@1401:   /// An adaptor for composing a subgraph of a 
alpar@911:   /// bidirected graph made from a directed one. 
alpar@911:   ///
alpar@1401:   ///\warning Graph adaptors 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$. 
alpar@1401:   /// SubBidirGraphAdaptor 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:   ///
alpar@1401:   /// An example for such a construction is \c RevGraphAdaptor 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, 
alpar@1401:   /// \c RevGraphAdaptor is implemented in a different way. 
alpar@1401:   /// But BidirGraphAdaptor is obtained from 
alpar@1401:   /// SubBidirGraphAdaptor by considering everywhere true 
marci@910:   /// valued maps both for forward_filter and backward_filter. 
marci@1252:   ///
alpar@1401:   /// The most important application of SubBidirGraphAdaptor 
alpar@1401:   /// is ResGraphAdaptor, which stands for the residual graph in directed 
marci@792:   /// flow and circulation problems. 
alpar@1401:   /// As adaptors usually, the SubBidirGraphAdaptor 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@992:   template<typename _Graph, 
marci@650: 	   typename ForwardFilterMap, typename BackwardFilterMap>
alpar@1401:   class SubBidirGraphAdaptor : 
marci@992:     public IterableGraphExtender<
alpar@1401:     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
marci@650:   public:
marci@992:     typedef _Graph Graph;
marci@992:     typedef IterableGraphExtender<
alpar@1401:       SubBidirGraphAdaptorBase<
marci@992:       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
marci@569:   protected:
alpar@1401:     SubBidirGraphAdaptor() { }
marci@992:   public:
alpar@1401:     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, 
marci@992: 			 BackwardFilterMap& _backward_filter) { 
marci@992:       setGraph(_graph);
marci@992:       setForwardFilterMap(_forward_filter);
marci@992:       setBackwardFilterMap(_backward_filter);
marci@992:     }
marci@992:   };
marci@650: 
marci@569: 
marci@650: 
alpar@1401:   ///\brief An adaptor for composing bidirected graph from a directed one. 
marci@650:   ///
alpar@1401:   ///\warning Graph adaptors are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
alpar@1401:   /// An adaptor 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>
alpar@1401:   class BidirGraphAdaptor : 
alpar@1401:     public SubBidirGraphAdaptor<
marci@650:     Graph, 
marci@650:     ConstMap<typename Graph::Edge, bool>, 
marci@650:     ConstMap<typename Graph::Edge, bool> > {
marci@650:   public:
alpar@1401:     typedef  SubBidirGraphAdaptor<
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: 
alpar@1401:     BidirGraphAdaptor() : Parent(), cm(true) { 
marci@655:       Parent::setForwardFilterMap(cm);
marci@655:       Parent::setBackwardFilterMap(cm);
marci@655:     }
marci@650:   public:
alpar@1401:     BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 
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:     }
alpar@1401:     //    KEEP_MAPS(Parent, BidirGraphAdaptor);
marci@650:   };
marci@650: 
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:   
alpar@1401:   /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
marci@650: 
alpar@1401:   An adaptor for composing the residual graph for directed flow and circulation problems. 
marci@1242:   Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a 
marci@1242:   number type. Let moreover 
marci@1242:   \f$f,c:A\to F\f$, be functions on the edge-set. 
alpar@1401:   In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow 
marci@1242:   and \f$c\f$ for a capacity function.   
marci@1242:   Suppose that a graph instange \c g of type 
marci@1242:   \c ListGraph implements \f$G\f$.
marci@1242:   \code
marci@1242:   ListGraph g;
marci@1242:   \endcode
alpar@1401:   Then RevGraphAdaptor implements the graph structure with node-set 
marci@1242:   \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where 
marci@1242:   \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and 
marci@1242:   \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$, 
marci@1242:   i.e. the so called residual graph. 
marci@1242:   When we take the union \f$A_{forward}\cup A_{backward}\f$, 
marci@1242:   multilicities are counted, i.e. if an edge is in both 
alpar@1401:   \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it 
marci@1242:   appears twice. 
marci@1242:   The following code shows how 
marci@1242:   such an instance can be constructed.
marci@1242:   \code
marci@1242:   typedef ListGraph Graph;
marci@1242:   Graph::EdgeMap<int> f(g);
marci@1242:   Graph::EdgeMap<int> c(g);
alpar@1401:   ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
marci@1242:   \endcode
marci@1242:   \author Marton Makai
marci@1242:   */
marci@650:   template<typename Graph, typename Number, 
marci@650: 	   typename CapacityMap, typename FlowMap>
alpar@1401:   class ResGraphAdaptor : 
alpar@1401:     public SubBidirGraphAdaptor< 
marci@650:     Graph, 
marci@658:     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
marci@658:     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
marci@650:   public:
alpar@1401:     typedef SubBidirGraphAdaptor< 
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;
alpar@1401:     ResGraphAdaptor() : 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:
alpar@1401:     ResGraphAdaptor(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:
alpar@1401:       const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
marci@660:     public:
alpar@987:       typedef Number Value;
alpar@987:       typedef Edge Key;
alpar@1401:       ResCap(const ResGraphAdaptor<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: 
alpar@1401:     //    KEEP_MAPS(Parent, ResGraphAdaptor);
marci@650:   };
marci@650: 
marci@650: 
marci@998: 
marci@998:   template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401:   class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
marci@998:   public:
marci@998:     typedef _Graph Graph;
alpar@1401:     typedef GraphAdaptorBase<_Graph> Parent;
marci@998:   protected:
marci@998:     FirstOutEdgesMap* first_out_edges;
alpar@1401:     ErasingFirstGraphAdaptorBase() : Parent(), 
marci@998: 				     first_out_edges(0) { }
marci@998: 
marci@998:     void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
marci@998:       first_out_edges=&_first_out_edges;
marci@998:     }
marci@998: 
marci@998:   public:
marci@998: 
marci@998:     typedef typename Parent::Node Node;
marci@998:     typedef typename Parent::Edge Edge;
marci@998: 
marci@998:     void firstOut(Edge& i, const Node& n) const { 
marci@998:       i=(*first_out_edges)[n];
marci@998:     }
marci@998: 
marci@998:     void erase(const Edge& e) const {
marci@998:       Node n=source(e);
marci@998:       Edge f=e;
marci@998:       Parent::nextOut(f);
marci@998:       first_out_edges->set(n, f);
marci@998:     }    
marci@998:   };
marci@998: 
marci@998: 
marci@612:   /// For blocking flows.
marci@556: 
alpar@1401:   ///\warning Graph adaptors are in even more experimental state than the other
alpar@879:   ///parts of the lib. Use them at you own risk.
alpar@879:   ///
alpar@1401:   /// This graph adaptor 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@998:   template <typename _Graph, typename FirstOutEdgesMap>
alpar@1401:   class ErasingFirstGraphAdaptor : 
marci@998:     public IterableGraphExtender<
alpar@1401:     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
marci@650:   public:
marci@998:     typedef _Graph Graph;
marci@998:     typedef IterableGraphExtender<
alpar@1401:       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
alpar@1401:     ErasingFirstGraphAdaptor(Graph& _graph, 
marci@998: 			     FirstOutEdgesMap& _first_out_edges) { 
marci@998:       setGraph(_graph);
marci@998:       setFirstOutEdgesMap(_first_out_edges);
marci@998:     } 
marci@1019: 
marci@998:   };
marci@556: 
deba@1472:   template <typename _Graph>
deba@1472:   class NewEdgeSetAdaptorBase {
deba@1472:   public:
deba@1472: 
deba@1472:     typedef _Graph Graph;
deba@1472:     typedef typename Graph::Node Node;
deba@1472:     typedef typename Graph::NodeIt NodeIt;
deba@1472: 
deba@1472:   protected:
deba@1472: 
deba@1472:     struct NodeT {
deba@1472:       int first_out, first_in;
deba@1472:       NodeT() : first_out(-1), first_in(-1) {}
deba@1472:     };
deba@1472:     
deba@1472:     class NodesImpl : protected Graph::template NodeMap<NodeT> {
deba@1472: 
deba@1472:       typedef typename Graph::template NodeMap<NodeT> Parent;
deba@1472:       typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
deba@1472: 
deba@1472:       Adaptor& adaptor;
deba@1472: 
deba@1472:     public:
deba@1472: 
deba@1472:       NodesImpl(Adaptor& _adaptor, const Graph& _graph) 
deba@1472: 	: Parent(_graph), adaptor(_adaptor) {}
deba@1472: 
deba@1472:       virtual ~NodesImpl() {}
deba@1472: 
deba@1472:       virtual void build() {
deba@1472: 	Parent::build();
deba@1472:       }
deba@1472: 
deba@1472:       virtual void clear() {
deba@1472: 	adaptor._clear();
deba@1472: 	Parent::clear();
deba@1472:       }
deba@1472:       
deba@1472:       virtual void add(const Node& node) {
deba@1472: 	Parent::add(node);
deba@1472: 	adaptor._add(node);
deba@1472:       }
deba@1472:       
deba@1472:       virtual void erase(const Node& node) {
deba@1472: 	adaptor._erase(node);
deba@1472: 	Parent::erase(node);
deba@1472:       }
deba@1472: 
deba@1472:       NodeT& operator[](const Node& node) {
deba@1472: 	return Parent::operator[](node);
deba@1472:       }
deba@1472: 
deba@1472:       const NodeT& operator[](const Node& node) const {
deba@1472: 	return Parent::operator[](node);
deba@1472:       }
deba@1472:       
deba@1472:     };
deba@1472: 
deba@1472:     NodesImpl* nodes;
deba@1472: 
deba@1472:     struct EdgeT {
deba@1472:       Node source, target;
deba@1472:       int next_out, next_in;
deba@1472:       int prev_out, prev_in;
deba@1472:       EdgeT() : prev_out(-1), prev_in(-1) {}
deba@1472:     };
deba@1472: 
deba@1472:     std::vector<EdgeT> edges;
deba@1472: 
deba@1472:     int first_edge;
deba@1472:     int first_free_edge;
deba@1472: 
deba@1472:     virtual void _clear() = 0;
deba@1472:     virtual void _add(const Node& node) = 0;
deba@1472:     virtual void _erase(const Node& node) = 0;
deba@1472:     
deba@1472:     const Graph* graph;
deba@1472: 
deba@1472:     void initalize(const Graph& _graph, NodesImpl& _nodes) {
deba@1472:       graph = &_graph;
deba@1472:       nodes = &_nodes;
deba@1472:     }
deba@1472:     
deba@1472:   public:
deba@1472: 
deba@1472:     class Edge {
deba@1472:       friend class NewEdgeSetAdaptorBase<Graph>;
deba@1472:     protected:
deba@1472:       Edge(int _id) : id(_id) {}
deba@1472:       int id;
deba@1472:     public:
deba@1472:       Edge() {}
deba@1472:       Edge(Invalid) : id(-1) {}
deba@1472:       bool operator==(const Edge& edge) const { return id == edge.id; }
deba@1472:       bool operator!=(const Edge& edge) const { return id != edge.id; }
deba@1472:       bool operator<(const Edge& edge) const { return id < edge.id; }
deba@1472:     };
deba@1472: 
deba@1472:     NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {} 
deba@1472:     virtual ~NewEdgeSetAdaptorBase() {}
deba@1472: 
deba@1472:     Edge addEdge(const Node& source, const Node& target) {
deba@1472:       int n;
deba@1472:       if (first_free_edge == -1) {
deba@1472: 	n = edges.size();
deba@1472: 	edges.push_back(EdgeT());
deba@1472:       } else {
deba@1472: 	n = first_free_edge;
deba@1472: 	first_free_edge = edges[first_free_edge].next_in;
deba@1472:       }
deba@1472:       edges[n].next_in = (*nodes)[target].first_in;
deba@1472:       (*nodes)[target].first_in = n;
deba@1472:       edges[n].next_out = (*nodes)[source].first_out;
deba@1472:       (*nodes)[source].first_out = n;
deba@1472:       edges[n].source = source;
deba@1472:       edges[n].target = target;
deba@1472:       return Edge(n);
deba@1472:     }
deba@1472: 
deba@1472:     void erase(const Edge& edge) {
deba@1472:       int n = edge.id;
deba@1472:       if (edges[n].prev_in != -1) {
deba@1472: 	edges[edges[n].prev_in].next_in = edges[n].next_in;
deba@1472:       } else {
deba@1472: 	(*nodes)[edges[n].target].first_in = edges[n].next_in;
deba@1472:       }
deba@1472:       if (edges[n].next_in != -1) {
deba@1472: 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
deba@1472:       }
deba@1472: 
deba@1472:       if (edges[n].prev_out != -1) {
deba@1472: 	edges[edges[n].prev_out].next_out = edges[n].next_out;
deba@1472:       } else {
deba@1472: 	(*nodes)[edges[n].source].first_out = edges[n].next_out;
deba@1472:       }
deba@1472:       if (edges[n].next_out != -1) {
deba@1472: 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
deba@1472:       }
deba@1472:            
deba@1472:     }
deba@1472: 
deba@1472:     void first(Node& node) const {
deba@1472:       graph->first(node);
deba@1472:     }
deba@1472: 
deba@1472:     void next(Node& node) const {
deba@1472:       graph->next(node);
deba@1472:     }
deba@1472: 
deba@1472:     void first(Edge& edge) const {
deba@1472:       Node node;
deba@1472:       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
deba@1472: 	   next(node));
deba@1472:       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1472:     }
deba@1472: 
deba@1472:     void next(Edge& edge) const {
deba@1472:       if (edges[edge.id].next_in != -1) {
deba@1472: 	edge.id = edges[edge.id].next_in;
deba@1472:       } else {
deba@1472: 	Node node = edges[edge.id].target;
deba@1472: 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
deba@1472: 	     next(node));
deba@1472: 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1472:       }      
deba@1472:     }
deba@1472: 
deba@1472:     void firstOut(Edge& edge, const Node& node) const {
deba@1472:       edge.id = (*nodes)[node].first_out;    
deba@1472:     }
deba@1472:     
deba@1472:     void nextOut(Edge& edge) const {
deba@1472:       edge.id = edges[edge.id].next_out;        
deba@1472:     }
deba@1472: 
deba@1472:     void firstIn(Edge& edge, const Node& node) const {
deba@1472:       edge.id = (*nodes)[node].first_in;          
deba@1472:     }
deba@1472: 
deba@1472:     void nextIn(Edge& edge) const {
deba@1472:       edge.id = edges[edge.id].next_in;    
deba@1472:     }
deba@1472: 
deba@1472:     int id(const Node& node) const { return graph->id(node); }
deba@1472:     int id(const Edge& edge) const { return edge.id; }
deba@1472: 
deba@1472:     Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
deba@1472:     Edge fromId(int id, Edge) const { return Edge(id); }
deba@1472: 
deba@1472:     int maxId(Node) const { return graph->maxId(Node()); };
deba@1472:     int maxId(Edge) const { return edges.size() - 1; }
deba@1472: 
deba@1472:     Node source(const Edge& edge) const { return edges[edge.id].source;}
deba@1472:     Node target(const Edge& edge) const { return edges[edge.id].target;}
deba@1472: 
deba@1472:   };
deba@1472: 
deba@1538: 
deba@1538:   /// \brief Graph adaptor using a node set of another graph and an
deba@1538:   /// own edge set.
deba@1538:   ///
deba@1538:   /// This structure can be used to establish another graph over a node set
deba@1538:   /// of an existing one. The node iterator will go through the nodes of the
deba@1538:   /// original graph.
deba@1538:   ///
deba@1538:   /// \param _Graph The type of the graph which shares its node set with 
deba@1538:   /// this class. Its interface must conform to the \ref skeleton::StaticGraph
deba@1538:   /// "StaticGraph" concept.
deba@1538:   ///
deba@1538:   /// In the edge extension and removing it conforms to the 
deba@1538:   /// \ref skeleton::ExtendableGraph "ExtendableGraph" concept.
deba@1472:   template <typename _Graph>
deba@1472:   class NewEdgeSetAdaptor :
deba@1472:     public ErasableGraphExtender<
deba@1472:     ClearableGraphExtender<
deba@1472:     ExtendableGraphExtender<
deba@1472:     DefaultMappableGraphExtender<
deba@1472:     IterableGraphExtender<
deba@1472:     AlterableGraphExtender<
deba@1472:     NewEdgeSetAdaptorBase<_Graph> > > > > > > {
deba@1472: 
deba@1472:   public:
deba@1472: 
deba@1472:     typedef ErasableGraphExtender<
deba@1472:       ClearableGraphExtender<
deba@1472:       ExtendableGraphExtender<
deba@1472:       DefaultMappableGraphExtender<
deba@1472:       IterableGraphExtender<
deba@1472:       AlterableGraphExtender<
deba@1472:       NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
deba@1472:     
deba@1472: 
deba@1472:     typedef typename Parent::Node Node;
deba@1472:     typedef typename Parent::Edge Edge;
deba@1472: 
deba@1472:   private:
deba@1472: 
deba@1472:     virtual void _clear() {
deba@1472:       Parent::edges.clear();
deba@1472:       Parent::first_edge = -1;
deba@1472:       Parent::first_free_edge = -1;
deba@1472:       Parent::getNotifier(Edge()).clear();
deba@1472:       Parent::getNotifier(Node()).clear();
deba@1472:     }
deba@1472: 
deba@1472:     virtual void _add(const Node& node) {
deba@1472:       Parent::getNotifier(Node()).add(node);
deba@1472:     }
deba@1472: 
deba@1472:     virtual void _erase(const Node& node) {
deba@1472:       Edge edge;
deba@1472:       Parent::firstOut(edge, node);
deba@1472:       while (edge != INVALID) {
deba@1472: 	Parent::erase(edge);
deba@1472: 	Parent::firstOut(edge, node);
deba@1472:       }
deba@1472: 
deba@1472:       Parent::firstIn(edge, node);
deba@1472:       while (edge != INVALID) {
deba@1472: 	Parent::erase(edge);
deba@1472: 	Parent::firstIn(edge, node);
deba@1472:       }
deba@1472:       
deba@1472:       Parent::getNotifier(Node()).erase(node);
deba@1472:     }
deba@1472: 
deba@1472: 
deba@1472:     typedef typename Parent::NodesImpl NodesImpl;
deba@1472: 
deba@1472:     NodesImpl nodes;
deba@1472:     
deba@1472:   public:
deba@1472: 
deba@1538:     /// \brief Constructor of the adaptor.
deba@1538:     /// 
deba@1538:     /// Constructor of the adaptor.
deba@1472:     NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
deba@1472:       Parent::initalize(_graph, nodes);
deba@1472:     }
deba@1472: 
deba@1472:     void clear() {
deba@1538:       Parent::getNotifier(Edge()).clear();      
deba@1538: 
deba@1472:       Parent::edges.clear();
deba@1472:       Parent::first_edge = -1;
deba@1472:       Parent::first_free_edge = -1;
deba@1538:     }
deba@1538:     
deba@1538:   };
deba@1472: 
deba@1538:   /// \brief Graph adaptor using a node set of another graph and an
deba@1538:   /// own undir edge set.
deba@1538:   ///
deba@1538:   /// This structure can be used to establish another undirected graph over 
deba@1538:   /// a node set of an existing one. The node iterator will go through the 
deba@1538:   /// nodes of the original graph.
deba@1538:   ///
deba@1538:   /// \param _Graph The type of the graph which shares its node set with 
deba@1538:   /// this class. Its interface must conform to the \ref skeleton::StaticGraph
deba@1538:   /// "StaticGraph" concept.
deba@1538:   ///
deba@1538:   /// In the edge extension and removing it conforms to the 
deba@1538:   /// \ref skeleton::ExtendableGraph "ExtendableGraph" concept.
deba@1538:   template <typename _Graph>
deba@1538:   class NewUndirEdgeSetAdaptor :
deba@1538:     public ErasableUndirGraphExtender<
deba@1538:     ClearableUndirGraphExtender<
deba@1538:     ExtendableUndirGraphExtender<
deba@1538:     MappableUndirGraphExtender<
deba@1538:     IterableUndirGraphExtender<
deba@1538:     AlterableUndirGraphExtender<
deba@1538:     UndirGraphExtender<
deba@1538:     NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
deba@1538: 
deba@1538:   public:
deba@1538: 
deba@1538:     typedef ErasableUndirGraphExtender<
deba@1538:       ClearableUndirGraphExtender<
deba@1538:       ExtendableUndirGraphExtender<
deba@1538:       MappableUndirGraphExtender<
deba@1538:       IterableUndirGraphExtender<
deba@1538:       AlterableUndirGraphExtender<
deba@1538:       UndirGraphExtender<
deba@1538:       NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
deba@1538:     
deba@1538: 
deba@1538:     typedef typename Parent::Node Node;
deba@1538:     typedef typename Parent::Edge Edge;
deba@1538:     typedef typename Parent::UndirEdge UndirEdge;
deba@1538: 
deba@1538:   private:
deba@1538: 
deba@1538:     virtual void _clear() {
deba@1538:       Parent::edges.clear();
deba@1538:       Parent::first_edge = -1;
deba@1538:       Parent::first_free_edge = -1;
deba@1538:       Parent::getNotifier(Edge()).clear();
deba@1538:       Parent::getNotifier(Node()).clear();
deba@1538:     }
deba@1538: 
deba@1538:     virtual void _add(const Node& node) {
deba@1538:       Parent::getNotifier(Node()).add(node);
deba@1538:     }
deba@1538: 
deba@1538:     virtual void _erase(const Node& node) {
deba@1538:       Edge edge;
deba@1538:       Parent::firstOut(edge, node);
deba@1538:       while (edge != INVALID) {
deba@1538: 	Parent::erase(edge);
deba@1538: 	Parent::firstOut(edge, node);
deba@1538:       }
deba@1538: 
deba@1538:       Parent::firstIn(edge, node);
deba@1538:       while (edge != INVALID) {
deba@1538: 	Parent::erase(edge);
deba@1538: 	Parent::firstIn(edge, node);
deba@1538:       }
deba@1538:       
deba@1538:       Parent::getNotifier(Node()).erase(node);
deba@1538:     }
deba@1538: 
deba@1538:     typedef typename Parent::NodesImpl NodesImpl;
deba@1538: 
deba@1538:     NodesImpl nodes;
deba@1538:     
deba@1538:   public:
deba@1538: 
deba@1538: 
deba@1538:     /// \brief Constructor of the adaptor.
deba@1538:     /// 
deba@1538:     /// Constructor of the adaptor.
deba@1538:     NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
deba@1538:       Parent::initalize(_graph, nodes);
deba@1538:     }
deba@1538: 
deba@1538:     void clear() {
deba@1472:       Parent::getNotifier(Edge()).clear();      
deba@1538:       Parent::getNotifier(UndirEdge()).clear();      
deba@1538: 
deba@1538:       Parent::edges.clear();
deba@1538:       Parent::first_edge = -1;
deba@1538:       Parent::first_free_edge = -1;
deba@1472:     }
deba@1472:     
deba@1472:   };
deba@1472: 
marci@556:   ///@}
marci@556: 
alpar@921: } //namespace lemon
marci@556: 
alpar@1401: #endif //LEMON_GRAPH_ADAPTOR_H
marci@556: