/* -*- C++ -*-

  * lemon/sub_graph.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_SUB_GRAPH_H

 #define LEMON_SUB_GRAPH_H

 #include <lemon/graph_adaptor.h>

 namespace lemon {

   /// \brief Base for the SubGraph.

   ///

   /// Base for the SubGraph.

   template <typename _Graph>

   class SubGraphBase : public GraphAdaptorBase<const _Graph> {

   public:

     typedef _Graph Graph;

     typedef SubGraphBase<_Graph> SubGraph;

     typedef GraphAdaptorBase<const _Graph> Parent;

     typedef Parent Base;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   protected:

     class NodesImpl;

     class EdgesImpl;

     SubGraphBase() {}

     void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {

       Parent::setGraph(_graph);

       nodes = &_nodes;

       edges = &_edges;

       firstNode = INVALID;

       Node node;

       Parent::first(node);

       while (node != INVALID) {

 	(*nodes)[node].prev = node;

 	(*nodes)[node].firstIn = INVALID;

 	(*nodes)[node].firstOut = INVALID;

 	Parent::next(node);

       }

       Edge edge;

       Parent::first(edge);

       while (edge != INVALID) {

 	(*edges)[edge].prevOut = edge;

 	Parent::next(edge);

       }

     }

   public:

     void first(Node& node) const {

       node = firstNode;

     }

     void next(Node& node) const {

       node = (*nodes)[node].next;

     }

     void first(Edge& edge) const {

       Node node = firstNode;

       while (node != INVALID && (*nodes)[node].firstOut == INVALID) {

 	node = (*nodes)[node].next;

       }

       if (node == INVALID) {

 	edge = INVALID;

       } else {

 	edge = (*nodes)[node].firstOut;

       }

     }

     void next(Edge& edge) const {

       if ((*edges)[edge].nextOut != INVALID) {

 	edge = (*edges)[edge].nextOut;

       } else {

 	Node node = (*nodes)[source(edge)].next;

 	while (node != INVALID && (*nodes)[node].firstOut == INVALID) {

 	  node = (*nodes)[node].next;

 	}

 	if (node == INVALID) {

 	  edge = INVALID;

 	} else {

 	  edge = (*nodes)[node].firstOut;

 	}

       }

     }

     void firstOut(Edge& edge, const Node& node) const {

       edge = (*nodes)[node].firstOut;

     }

     void nextOut(Edge& edge) const {

       edge = (*edges)[edge].nextOut;

     }

     void firstIn(Edge& edge, const Node& node) const {

       edge = (*nodes)[node].firstIn;

     }

     void nextIn(Edge& edge) const {

       edge = (*edges)[edge].nextIn;

     }

     /// \brief Returns true when the given node is hidden.

     ///

     /// Returns true when the given node is hidden.

     bool hidden(const Node& node) const {

       return (*nodes)[node].prev == node;

     }

     /// \brief Hide the given node in the sub-graph.

     ///

     /// Hide the given node in the sub graph. It just lace out from

     /// the linked lists the given node. If there are incoming or outgoing

     /// edges into or from this node then all of these will be hidden.

     void hide(const Node& node) {

       if (hidden(node)) return;

       Edge edge;

       firstOut(edge, node);

       while (edge != INVALID) {

 	hide(edge);

 	firstOut(edge, node);

       }

       firstOut(edge, node);

       while (edge != INVALID) {

 	hide(edge);

 	firstOut(edge, node);

       }

       if ((*nodes)[node].prev != INVALID) {

 	(*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;

       } else {

 	firstNode = (*nodes)[node].next;

       }

       if ((*nodes)[node].next != INVALID) {

 	(*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;

       }

       (*nodes)[node].prev = node;

       (*nodes)[node].firstIn = INVALID;

       (*nodes)[node].firstOut = INVALID;

     }

     /// \brief Unhide the given node in the sub-graph.

     ///

     /// Unhide the given node in the sub graph. It just lace in the given

     /// node into the linked lists.

     void unHide(const Node& node) {

       if (!hidden(node)) return;

       (*nodes)[node].next = firstNode;

       (*nodes)[node].prev = INVALID;

       if ((*nodes)[node].next != INVALID) {

 	(*nodes)[(*nodes)[node].next].prev = node;

       }

       firstNode = node;

     }

     /// \brief Returns true when the given edge is hidden.

     ///

     /// Returns true when the given edge is hidden.

     bool hidden(const Edge& edge) const {

       return (*edges)[edge].prevOut == edge;

     }

     /// \brief Hide the given edge in the sub-graph.

     ///

     /// Hide the given edge in the sub graph. It just lace out from

     /// the linked lists the given edge.

     void hide(const Edge& edge) {

       if (hidden(edge)) return;

       if ((*edges)[edge].prevOut == edge) return;

       if ((*edges)[edge].prevOut != INVALID) {

 	(*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;

       } else {

 	(*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;

       }

       if ((*edges)[edge].nextOut != INVALID) {

 	(*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;

       }

       if ((*edges)[edge].prevIn != INVALID) {

 	(*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;

       } else {

 	(*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;

       }

       if ((*edges)[edge].nextIn != INVALID) {

 	(*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;

       }

       (*edges)[edge].next = edge;

     }

     /// \brief Unhide the given edge in the sub-graph.

     ///

     /// Unhide the given edge in the sub graph. It just lace in the given

     /// edge into the linked lists. If the source or the target of the

     /// node is hidden then it will unhide it.

     void unHide(const Edge& edge) {

       if (!hidden(edge)) return;

       Node node;

       node = Parent::source(edge);

       unHide(node);

       (*edges)[edge].nextOut = (*nodes)[node].firstOut;

       (*edges)[edge].prevOut = INVALID;

       if ((*edges)[edge].nextOut != INVALID) {

 	(*edges)[(*edges)[edge].nextOut].prevOut = edge;

       }

       (*nodes)[node].firstOut = edge;

       node = Parent::target(edge);

       unHide(node);

       (*edges)[edge].nextIn = (*nodes)[node].firstIn;

       (*edges)[edge].prevIn = INVALID;

       if ((*edges)[edge].nextIn != INVALID) {

 	(*edges)[(*edges)[edge].nextIn].prevIn = edge;

       }

       (*nodes)[node].firstIn = edge;      

     }

     typedef False NodeNumTag;

     typedef False EdgeNumTag;

   protected:

     struct NodeT {

       Node prev, next;

       Edge firstIn, firstOut;

     };

     class NodesImpl : public Graph::template NodeMap<NodeT> {

       friend class SubGraphBase;

     public:

       typedef typename Graph::template NodeMap<NodeT> Parent;

       NodesImpl(SubGraph& _adaptor, const Graph& _graph) 

 	: Parent(_graph), adaptor(_adaptor) {}

       virtual ~NodesImpl() {}

       virtual void build() {

 	Parent::build();

 	Node node;

 	adaptor.Base::first(node);

 	while (node != INVALID) {

 	  Parent::operator[](node).prev = node;

 	  Parent::operator[](node).firstIn = INVALID;

 	  Parent::operator[](node).firstOut = INVALID;

 	  adaptor.Base::next(node);

 	}

       }

       virtual void clear() {

 	adaptor.firstNode = INVALID;

 	Parent::clear();

       }

       virtual void add(const Node& node) {

 	Parent::add(node);

 	Parent::operator[](node).prev = node;

 	Parent::operator[](node).firstIn = INVALID;

 	Parent::operator[](node).firstOut = INVALID;

       }

       virtual void add(const std::vector<Node>& nodes) {

 	Parent::add(nodes);

 	for (int i = 0; i < (int)nodes.size(); ++i) {

 	  Parent::operator[](nodes[i]).prev = nodes[i];

 	  Parent::operator[](nodes[i]).firstIn = INVALID;

 	  Parent::operator[](nodes[i]).firstOut = INVALID;

 	}

       } 

       virtual void erase(const Node& node) {

 	adaptor.hide(node);

 	Parent::erase(node);

       }

       virtual void erase(const std::vector<Node>& nodes) {

 	for (int i = 0; i < (int)nodes.size(); ++i) {

 	  adaptor.hide(nodes[i]);

 	}

 	Parent::erase(nodes);

       }

     private:

       SubGraph& adaptor;

     };

     struct EdgeT {

       Edge prevOut, nextOut;

       Edge prevIn, nextIn;

     };

     class EdgesImpl : public Graph::template EdgeMap<EdgeT> {

       friend class SubGraphBase;

     public:

       typedef typename Graph::template EdgeMap<EdgeT> Parent;

       EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 

 	: Parent(_graph), adaptor(_adaptor) {}

       virtual ~EdgesImpl() {}

       virtual void build() {

 	Parent::build();

 	Edge edge;

 	adaptor.Base::first(edge);

 	while (edge != INVALID) {

 	  Parent::operator[](edge).prevOut = edge;

 	  adaptor.Base::next(edge);

 	}

       }

       virtual void clear() {

 	Node node;

 	adaptor.first(node);

 	while (node != INVALID) {

 	  (*adaptor.nodes).firstIn = INVALID;

 	  (*adaptor.nodes).firstOut = INVALID;

 	  adaptor.next(node);

 	}

 	Parent::clear();

       }

       virtual void add(const Edge& edge) {

 	Parent::add(edge);

 	Parent::operator[](edge).prevOut = edge;

       }

       virtual void add(const std::vector<Edge>& edges) {

 	Parent::add(edges);

 	for (int i = 0; i < (int)edges.size(); ++i) {

 	  Parent::operator[](edges[i]).prevOut = edges[i];

 	}

       }

       virtual void erase(const Edge& edge) {

 	adaptor.hide(edge);

 	Parent::erase(edge);

       }

       virtual void erase(const std::vector<Edge>& edges) {

 	for (int i = 0; i < (int)edges.size(); ++i) {

 	  adaptor.hide(edges[i]);

 	}

 	Parent::erase(edge);

       }

     private:

       SubGraph& adaptor;

     };

     NodesImpl* nodes;

     EdgesImpl* edges;

     Node firstNode;

   };

   /// \ingroup semi_adaptors

   ///

   /// \brief Graph which uses a subset of an other graph's nodes and edges.

   ///

   /// Graph which uses a subset of an other graph's nodes and edges. This class

   /// is an alternative to the SubGraphAdaptor which is created for the

   /// same reason. The main difference between the two class that it

   /// makes linked lists on the unhidden nodes and edges what cause that

   /// on sparse subgraphs the algorithms can be more efficient and some times

   /// provide better time complexity. On other way this implemetation is

   /// less efficient in most case when the subgraph filters out only

   /// a few nodes or edges.

   /// 

   /// \see SubGraphAdaptor

   /// \see EdgeSubGraphBase

   template <typename Graph>

   class SubGraph 

     : public IterableGraphExtender< SubGraphBase<Graph> > {

   public:

     typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;

   public:

     /// \brief Constructor for sub-graph.

     ///

     /// Constructor for sub-graph. Initially all the edges and nodes

     /// are hidden in the graph.

     SubGraph(const Graph& _graph) 

       : Parent(), nodes(*this, _graph), edges(*this, _graph) { 

       Parent::construct(_graph, nodes, edges);

     }

   private:

     typename Parent::NodesImpl nodes;

     typename Parent::EdgesImpl edges;

   };

   /// \brief Base for the EdgeSubGraph.

   ///

   /// Base for the EdgeSubGraph.

   template <typename _Graph>

   class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {

   public:

     typedef _Graph Graph;

     typedef EdgeSubGraphBase<_Graph> SubGraph;

     typedef GraphAdaptorBase<const _Graph> Parent;

     typedef Parent Base;

     typedef typename Parent::Node Node;

     typedef typename Parent::Edge Edge;

   protected:

     class NodesImpl;

     class EdgesImpl;

     EdgeSubGraphBase() {}

     void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {

       Parent::setGraph(_graph);

       nodes = &_nodes;

       edges = &_edges;

       Node node;

       Parent::first(node);

       while (node != INVALID) {

 	(*nodes)[node].firstIn = INVALID;

 	(*nodes)[node].firstOut = INVALID;

 	Parent::next(node);

       }

       Edge edge;

       Parent::first(edge);

       while (edge != INVALID) {

 	(*edges)[edge].prevOut = edge;

 	Parent::next(edge);

       }

     }

   public:

     void first(Node& node) const {

       Parent::first(node);

     }

     void next(Node& node) const {

       Parent::next(node);

     }

     void first(Edge& edge) const {

       Node node;

       Parent::first(node);

       while (node != INVALID && (*nodes)[node].firstOut == INVALID) {

 	Parent::next(node);

       }

       if (node == INVALID) {

 	edge = INVALID;

       } else {

 	edge = (*nodes)[node].firstOut;

       }

     }

     void next(Edge& edge) const {

       if ((*edges)[edge].nextOut != INVALID) {

 	edge = (*edges)[edge].nextOut;

       } else {

 	Node node = source(edge);

 	Parent::next(node);

 	while (node != INVALID && (*nodes)[node].firstOut == INVALID) {

 	  Parent::next(node);

 	}

 	if (node == INVALID) {

 	  edge = INVALID;

 	} else {

 	  edge = (*nodes)[node].firstOut;

 	}

       }

     }

     void firstOut(Edge& edge, const Node& node) const {

       edge = (*nodes)[node].firstOut;

     }

     void nextOut(Edge& edge) const {

       edge = (*edges)[edge].nextOut;

     }

     void firstIn(Edge& edge, const Node& node) const {

       edge = (*nodes)[node].firstIn;

     }

     void nextIn(Edge& edge) const {

       edge = (*edges)[edge].nextIn;

     }

     /// \brief Returns true when the given edge is hidden.

     ///

     /// Returns true when the given edge is hidden.

     bool hidden(const Edge& edge) const {

       return (*edges)[edge].prevOut == edge;

     }

     /// \brief Hide the given edge in the sub-graph.

     ///

     /// Hide the given edge in the sub graph. It just lace out from

     /// the linked lists the given edge.

     void hide(const Edge& edge) {

       if (hidden(edge)) return;

       if ((*edges)[edge].prevOut != INVALID) {

 	(*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;

       } else {

 	(*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;

       }

       if ((*edges)[edge].nextOut != INVALID) {

 	(*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;

       }

       if ((*edges)[edge].prevIn != INVALID) {

 	(*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;

       } else {

 	(*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;

       }

       if ((*edges)[edge].nextIn != INVALID) {

 	(*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;

       }

       (*edges)[edge].prevOut = edge;

     }

     /// \brief Unhide the given edge in the sub-graph.

     ///

     /// Unhide the given edge in the sub graph. It just lace in the given

     /// edge into the linked lists.

     void unHide(const Edge& edge) {

       if (!hidden(edge)) return;

       Node node;

       node = Parent::source(edge);

       (*edges)[edge].nextOut = (*nodes)[node].firstOut;

       (*edges)[edge].prevOut = INVALID;

       if ((*edges)[edge].nextOut != INVALID) {

 	(*edges)[(*edges)[edge].nextOut].prevOut = edge;

       }

       (*nodes)[node].firstOut = edge;

       node = Parent::target(edge);

       (*edges)[edge].nextIn = (*nodes)[node].firstIn;

       (*edges)[edge].prevIn = INVALID;

       if ((*edges)[edge].nextIn != INVALID) {

 	(*edges)[(*edges)[edge].nextIn].prevIn = edge;

       }

       (*nodes)[node].firstIn = edge;      

     }

   protected:

     struct NodeT {

       Edge firstIn, firstOut;

     };

     class NodesImpl : public Graph::template NodeMap<NodeT> {

       friend class EdgeSubGraphBase;

     public:

       typedef typename Graph::template NodeMap<NodeT> Parent;

       NodesImpl(SubGraph& _adaptor, const Graph& _graph) 

 	: Parent(_graph), adaptor(_adaptor) {}

       virtual ~NodesImpl() {}

       virtual void build() {

 	Parent::build();

 	Node node;

 	adaptor.Base::first(node);

 	while (node != INVALID) {

 	  Parent::operator[](node).firstIn = INVALID;

 	  Parent::operator[](node).firstOut = INVALID;

 	  adaptor.Base::next(node);

 	}

       }

       virtual void add(const Node& node) {

 	Parent::add(node);

 	Parent::operator[](node).firstIn = INVALID;

 	Parent::operator[](node).firstOut = INVALID;

       }

     private:

       SubGraph& adaptor;

     };

     struct EdgeT {

       Edge prevOut, nextOut;

       Edge prevIn, nextIn;

     };

     class EdgesImpl : public Graph::template EdgeMap<EdgeT> {

       friend class EdgeSubGraphBase;

     public:

       typedef typename Graph::template EdgeMap<EdgeT> Parent;

       EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 

 	: Parent(_graph), adaptor(_adaptor) {}

       virtual ~EdgesImpl() {}

       virtual void build() {

 	Parent::build();

 	Edge edge;

 	adaptor.Base::first(edge);

 	while (edge != INVALID) {

 	  Parent::operator[](edge).prevOut = edge;

 	  adaptor.Base::next(edge);

 	}

       }

       virtual void clear() {

 	Node node;

 	adaptor.Base::first(node);

 	while (node != INVALID) {

 	  (*adaptor.nodes)[node].firstIn = INVALID;

 	  (*adaptor.nodes)[node].firstOut = INVALID;

 	  adaptor.Base::next(node);

 	}

 	Parent::clear();

       }

       virtual void add(const Edge& edge) {

 	Parent::add(edge);

 	Parent::operator[](edge).prevOut = edge;

       }

       virtual void add(const std::vector<Edge>& edges) {

 	Parent::add(edges);

 	for (int i = 0; i < (int)edges.size(); ++i) {

 	  Parent::operator[](edges[i]).prevOut = edges[i];

 	}

       }

       virtual void erase(const Edge& edge) {

 	adaptor.hide(edge);

 	Parent::erase(edge);

       }

       virtual void erase(const std::vector<Edge>& edges) {

 	for (int i = 0; i < (int)edges.size(); ++i) {

 	  adaptor.hide(edges[i]);

 	}

 	Parent::erase(edge);

       }

     private:

       SubGraph& adaptor;

     };

     NodesImpl* nodes;

     EdgesImpl* edges;

   };

   /// \ingroup semi_adaptors

   ///

   /// \brief Graph which uses a subset of an other graph's edges.

   ///

   /// Graph which uses a subset of an other graph's edges. This class

   /// is an alternative to the EdgeSubGraphAdaptor which is created for the

   /// same reason. The main difference between the two class that it

   /// makes linked lists on the unhidden edges what cause that

   /// on sparse subgraphs the algorithms can be more efficient and some times

   /// provide better time complexity. On other way this implemetation is

   /// less efficient in most case when the subgraph filters out only

   /// a few edges.

   /// 

   /// \see EdgeSubGraphAdaptor

   /// \see EdgeSubGraphBase

   template <typename Graph>

   class EdgeSubGraph 

     : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {

   public:

     typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;

   public:

     /// \brief Constructor for sub-graph.

     ///

     /// Constructor for sub-graph. Initially all the edges are hidden in the 

     /// graph.

     EdgeSubGraph(const Graph& _graph) 

       : Parent(), nodes(*this, _graph), edges(*this, _graph) { 

       Parent::construct(_graph, nodes, edges);

     }

   private:

     typename Parent::NodesImpl nodes;

     typename Parent::EdgesImpl edges;

   };

 //   template<typename Graph, typename Number, 

 // 	   typename CapacityMap, typename FlowMap>

 //   class ResGraph

 //     : public IterableGraphExtender<EdgeSubGraphBase<

 //     UndirGraphAdaptor<Graph> > > {

 //   public:

 //     typedef IterableGraphExtender<EdgeSubGraphBase<

 //       UndirGraphAdaptor<Graph> > > Parent;

 //   protected:

 //     UndirGraphAdaptor<Graph> undir;

 //     const CapacityMap* capacity;

 //     FlowMap* flow;

 //     typename Parent::NodesImpl nodes;

 //     typename Parent::EdgesImpl edges;

 //     void setCapacityMap(const CapacityMap& _capacity) {

 //       capacity=&_capacity;

 //     }

 //     void setFlowMap(FlowMap& _flow) {

 //       flow=&_flow;

 //     }

 //   public:

 //     typedef typename UndirGraphAdaptor<Graph>::Node Node;

 //     typedef typename UndirGraphAdaptor<Graph>::Edge Edge;

 //     typedef typename UndirGraphAdaptor<Graph>::UndirEdge UndirEdge;

 //     ResGraphAdaptor(Graph& _graph, 

 // 		    const CapacityMap& _capacity, FlowMap& _flow) 

 //       : Parent(), undir(_graph), capacity(&_capacity), flow(&_flow),

 // 	nodes(*this, _graph), edges(*this, _graph) {

 //       Parent::construct(undir, nodes, edges);

 //       setFlowMap(_flow);

 //       setCapacityMap(_capacity);

 //       typename Graph::Edge edge; 

 //       for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {

 // 	if ((*flow)[edge] != (*capacity)[edge]) {

 // 	  Parent::unHide(direct(edge, true));

 // 	}

 // 	if ((*flow)[edge] != 0) {

 // 	  Parent::unHide(direct(edge, false));

 // 	}

 //       }

 //     }

 //     void augment(const Edge& e, Number a) {

 //       if (direction(e)) {

 // 	flow->set(e, (*flow)[e]+a);

 //       } else { 

 // 	flow->set(e, (*flow)[e]-a);

 //       }

 //       if ((*flow)[e] == (*capacity)[e]) {

 // 	Parent::hide(e);

 //       } else {

 // 	Parent::unHide(e);

 //       }

 //       if ((*flow)[e] == 0) {

 // 	Parent::hide(oppositeEdge(e));

 //       } else {

 // 	Parent::unHide(oppositeEdge(e));

 //       }

 //     }

 //     Number resCap(const Edge& e) {

 //       if (direction(e)) { 

 // 	return (*capacity)[e]-(*flow)[e]; 

 //       } else { 

 // 	return (*flow)[e];

 //       }

 //     }

 //     bool direction(const Edge& edge) const {

 //       return Parent::getGraph().direction(edge);

 //     }

 //     Edge direct(const UndirEdge& edge, bool direction) const {

 //       return Parent::getGraph().direct(edge, direction);

 //     }

 //     Edge direct(const UndirEdge& edge, const Node& node) const {

 //       return Parent::getGraph().direct(edge, node);

 //     }

 //     Edge oppositeEdge(const Edge& edge) const {

 //       return Parent::getGraph().oppositeEdge(edge);

 //     }

 //     /// \brief Residual capacity map.

 //     ///

 //     /// In generic residual graphs the residual capacity can be obtained 

 //     /// as a map. 

 //     class ResCap {

 //     protected:

 //       const ResGraphAdaptor* res_graph;

 //     public:

 //       typedef Number Value;

 //       typedef Edge Key;

 //       ResCap(const ResGraphAdaptor& _res_graph) 

 // 	: res_graph(&_res_graph) {}

 //       Number operator[](const Edge& e) const {

 // 	return res_graph->resCap(e);

 //       }

 //     };

 //   };

 }

 #endif