deba@1866: /* -*- C++ -*-
deba@1866:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1866:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1866:  *
deba@1866:  * Permission to use, modify and distribute this software is granted
deba@1866:  * provided that this copyright notice appears in all copies. For
deba@1866:  * precise terms see the accompanying LICENSE file.
deba@1866:  *
deba@1866:  * This software is provided "AS IS" with no warranty of any kind,
deba@1866:  * express or implied, and with no claim as to its suitability for any
deba@1866:  * purpose.
deba@1866:  *
deba@1866:  */
deba@1866: 
deba@1866: #ifndef LEMON_SUB_GRAPH_H
deba@1866: #define LEMON_SUB_GRAPH_H
deba@1866: 
deba@1866: #include <lemon/graph_adaptor.h>
deba@1990: #include <lemon/bits/graph_adaptor_extender.h>
deba@1990: #include <lemon/bits/default_map.h>
deba@1866: 
deba@2224: /// \ingroup semi_adaptors
deba@2224: /// \file
deba@2224: /// \brief Subgraphs.
deba@2224: ///
deba@2224: /// Graphs with filtered edge and node set.
deba@2224: 
deba@1866: namespace lemon {
deba@1866: 
deba@1866:   /// \brief Base for the SubGraph.
deba@1866:   ///
deba@1866:   /// Base for the SubGraph.
deba@1866:   template <typename _Graph>
deba@1866:   class SubGraphBase : public GraphAdaptorBase<const _Graph> {
deba@1866:   public:
deba@1866:     typedef _Graph Graph;
deba@1866:     typedef SubGraphBase<_Graph> SubGraph;
deba@1866:     typedef GraphAdaptorBase<const _Graph> Parent;
deba@1866:     typedef Parent Base;
deba@1866: 
deba@1866:     typedef typename Parent::Node Node;
deba@1866:     typedef typename Parent::Edge Edge;
deba@1866: 
deba@1866: 
deba@1866:   protected:
deba@1866: 
deba@1866:     class NodesImpl;
deba@1866:     class EdgesImpl;
deba@1866: 
deba@1866:     SubGraphBase() {}
deba@1866: 
deba@1866:     void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
deba@1866:       Parent::setGraph(_graph);
deba@1866:       nodes = &_nodes;
deba@1866:       edges = &_edges;
deba@1866:       firstNode = INVALID;
deba@1866: 
deba@1866:       Node node;
deba@1866:       Parent::first(node);
deba@1866:       while (node != INVALID) {
deba@1866: 	(*nodes)[node].prev = node;
deba@1866: 	(*nodes)[node].firstIn = INVALID;
deba@1866: 	(*nodes)[node].firstOut = INVALID;
deba@1866: 	Parent::next(node);
deba@1866:       }
deba@1866: 
deba@1866:       Edge edge;
deba@1866:       Parent::first(edge);
deba@1866:       while (edge != INVALID) {
deba@1866: 	(*edges)[edge].prevOut = edge;
deba@1866: 	Parent::next(edge);
deba@1866:       }
deba@1866:     }
deba@1866: 
deba@1866:   public:
deba@1866: 
deba@1866:     void first(Node& node) const {
deba@1866:       node = firstNode;
deba@1866:     }
deba@1866:     void next(Node& node) const {
deba@1866:       node = (*nodes)[node].next;
deba@1866:     }
deba@1866: 
deba@1866:     void first(Edge& edge) const {
deba@1866:       Node node = firstNode;
deba@1866:       while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
deba@1866: 	node = (*nodes)[node].next;
deba@1866:       }
deba@1866:       if (node == INVALID) {
deba@1866: 	edge = INVALID;
deba@1866:       } else {
deba@1866: 	edge = (*nodes)[node].firstOut;
deba@1866:       }
deba@1866:     }
deba@1866:     void next(Edge& edge) const {
deba@1866:       if ((*edges)[edge].nextOut != INVALID) {
deba@1866: 	edge = (*edges)[edge].nextOut;
deba@1866:       } else {
deba@1866: 	Node node = (*nodes)[source(edge)].next;
deba@1866: 	while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
deba@1866: 	  node = (*nodes)[node].next;
deba@1866: 	}
deba@1866: 	if (node == INVALID) {
deba@1866: 	  edge = INVALID;
deba@1866: 	} else {
deba@1866: 	  edge = (*nodes)[node].firstOut;
deba@1866: 	}
deba@1866:       }
deba@1866:     }
deba@1866: 
deba@1866:     void firstOut(Edge& edge, const Node& node) const {
deba@1866:       edge = (*nodes)[node].firstOut;
deba@1866:     }
deba@1866:     void nextOut(Edge& edge) const {
deba@1866:       edge = (*edges)[edge].nextOut;
deba@1866:     }
deba@1866: 
deba@1866:     void firstIn(Edge& edge, const Node& node) const {
deba@1866:       edge = (*nodes)[node].firstIn;
deba@1866:     }
deba@1866:     void nextIn(Edge& edge) const {
deba@1866:       edge = (*edges)[edge].nextIn;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Returns true when the given node is hidden.
deba@1866:     ///
deba@1866:     /// Returns true when the given node is hidden.
deba@1866:     bool hidden(const Node& node) const {
deba@1866:       return (*nodes)[node].prev == node;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Hide the given node in the sub-graph.
deba@1866:     ///
deba@1866:     /// Hide the given node in the sub graph. It just lace out from
deba@1866:     /// the linked lists the given node. If there are incoming or outgoing
deba@1866:     /// edges into or from this node then all of these will be hidden.
deba@1866:     void hide(const Node& node) {
deba@1866:       if (hidden(node)) return;
deba@1866:       Edge edge;
deba@1866:       firstOut(edge, node);
deba@1866:       while (edge != INVALID) {
deba@1866: 	hide(edge);
deba@1866: 	firstOut(edge, node);
deba@1866:       }
deba@1866: 
deba@1866:       firstOut(edge, node);
deba@1866:       while (edge != INVALID) {
deba@1866: 	hide(edge);
deba@1866: 	firstOut(edge, node);
deba@1866:       }
deba@1866:       if ((*nodes)[node].prev != INVALID) {
deba@1866: 	(*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
deba@1866:       } else {
deba@1866: 	firstNode = (*nodes)[node].next;
deba@1866:       }
deba@1866:       if ((*nodes)[node].next != INVALID) {
deba@1866: 	(*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
deba@1866:       }
deba@1866:       (*nodes)[node].prev = node;
deba@1866:       (*nodes)[node].firstIn = INVALID;
deba@1866:       (*nodes)[node].firstOut = INVALID;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Unhide the given node in the sub-graph.
deba@1866:     ///
deba@1866:     /// Unhide the given node in the sub graph. It just lace in the given
deba@1866:     /// node into the linked lists.
deba@1866:     void unHide(const Node& node) {
deba@1866:       if (!hidden(node)) return;
deba@1866:       (*nodes)[node].next = firstNode;
deba@1866:       (*nodes)[node].prev = INVALID;
deba@1866:       if ((*nodes)[node].next != INVALID) {
deba@1866: 	(*nodes)[(*nodes)[node].next].prev = node;
deba@1866:       }
deba@1866:       firstNode = node;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Returns true when the given edge is hidden.
deba@1866:     ///
deba@1866:     /// Returns true when the given edge is hidden.
deba@1866:     bool hidden(const Edge& edge) const {
deba@1866:       return (*edges)[edge].prevOut == edge;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Hide the given edge in the sub-graph.
deba@1866:     ///
deba@1866:     /// Hide the given edge in the sub graph. It just lace out from
deba@1866:     /// the linked lists the given edge.
deba@1866:     void hide(const Edge& edge) {
deba@1866:       if (hidden(edge)) return;
deba@1866:       if ((*edges)[edge].prevOut == edge) return;
deba@1866:       if ((*edges)[edge].prevOut != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
deba@1866:       } else {
deba@1866: 	(*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
deba@1866:       }
deba@1866:       if ((*edges)[edge].nextOut != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
deba@1866:       }
deba@1866: 
deba@1866:       if ((*edges)[edge].prevIn != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
deba@1866:       } else {
deba@1866: 	(*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
deba@1866:       }
deba@1866:       if ((*edges)[edge].nextIn != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
deba@1866:       }
deba@1866:       (*edges)[edge].next = edge;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Unhide the given edge in the sub-graph.
deba@1866:     ///
deba@1866:     /// Unhide the given edge in the sub graph. It just lace in the given
deba@1866:     /// edge into the linked lists. If the source or the target of the
deba@1866:     /// node is hidden then it will unhide it.
deba@1866:     void unHide(const Edge& edge) {
deba@1866:       if (!hidden(edge)) return;
deba@1866: 
deba@1866:       Node node;
deba@1866: 
deba@1866:       node = Parent::source(edge);
deba@1866:       unHide(node);
deba@1866:       (*edges)[edge].nextOut = (*nodes)[node].firstOut;
deba@1866:       (*edges)[edge].prevOut = INVALID;
deba@1866:       if ((*edges)[edge].nextOut != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextOut].prevOut = edge;
deba@1866:       }
deba@1866:       (*nodes)[node].firstOut = edge;
deba@1866: 
deba@1866:       node = Parent::target(edge);
deba@1866:       unHide(node);
deba@1866:       (*edges)[edge].nextIn = (*nodes)[node].firstIn;
deba@1866:       (*edges)[edge].prevIn = INVALID;
deba@1866:       if ((*edges)[edge].nextIn != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextIn].prevIn = edge;
deba@1866:       }
deba@1866:       (*nodes)[node].firstIn = edge;      
deba@1866:     }
deba@1866:     
deba@1866:     typedef False NodeNumTag;
deba@1866:     typedef False EdgeNumTag;
deba@1866: 
deba@1866:   protected:
deba@1866:     struct NodeT {
deba@1866:       Node prev, next;
deba@1866:       Edge firstIn, firstOut;
deba@1866:     };
deba@1990:     class NodesImpl : public DefaultMap<Graph, Node, NodeT> {
deba@1866:       friend class SubGraphBase;
deba@1866:     public:
deba@1990:       typedef DefaultMap<Graph, Node, NodeT> Parent;
deba@1866: 
deba@1866:       NodesImpl(SubGraph& _adaptor, const Graph& _graph) 
deba@1866: 	: Parent(_graph), adaptor(_adaptor) {}
deba@1866: 
deba@1866:       virtual ~NodesImpl() {}
deba@1866: 
deba@1866:       virtual void build() {
deba@1866: 	Parent::build();
deba@1866: 	Node node;
deba@1866: 	adaptor.Base::first(node);
deba@1866: 	while (node != INVALID) {
deba@1866: 	  Parent::operator[](node).prev = node;
deba@1866: 	  Parent::operator[](node).firstIn = INVALID;
deba@1866: 	  Parent::operator[](node).firstOut = INVALID;
deba@1866: 	  adaptor.Base::next(node);
deba@1866: 	}
deba@1866:       }
deba@1866: 
deba@1866:       virtual void clear() {
deba@1866: 	adaptor.firstNode = INVALID;
deba@1866: 	Parent::clear();
deba@1866:       }
deba@1866: 
deba@1866:       virtual void add(const Node& node) {
deba@1866: 	Parent::add(node);
deba@1866: 	Parent::operator[](node).prev = node;
deba@1866: 	Parent::operator[](node).firstIn = INVALID;
deba@1866: 	Parent::operator[](node).firstOut = INVALID;
deba@1866:       }
deba@1964: 
deba@1866:       virtual void add(const std::vector<Node>& nodes) {
deba@1866: 	Parent::add(nodes);
deba@1866: 	for (int i = 0; i < (int)nodes.size(); ++i) {
deba@1866: 	  Parent::operator[](nodes[i]).prev = nodes[i];
deba@1866: 	  Parent::operator[](nodes[i]).firstIn = INVALID;
deba@1866: 	  Parent::operator[](nodes[i]).firstOut = INVALID;
deba@1866: 	}
deba@1866:       } 
deba@1866: 
deba@1866:       virtual void erase(const Node& node) {
deba@1866: 	adaptor.hide(node);
deba@1866: 	Parent::erase(node);
deba@1866:       }
deba@1866: 
deba@1866:       virtual void erase(const std::vector<Node>& nodes) {
deba@1866: 	for (int i = 0; i < (int)nodes.size(); ++i) {
deba@1866: 	  adaptor.hide(nodes[i]);
deba@1866: 	}
deba@1866: 	Parent::erase(nodes);
deba@1866:       }
deba@1866: 
deba@1866:     private:
deba@1866:       SubGraph& adaptor;
deba@1866:     };
deba@1866: 
deba@1866:     struct EdgeT {
deba@1866:       Edge prevOut, nextOut;
deba@1866:       Edge prevIn, nextIn;
deba@1866:     };
deba@1990:     class EdgesImpl : public DefaultMap<Graph, Edge, EdgeT> {
deba@1866:       friend class SubGraphBase;
deba@1866:     public:
deba@1990:       typedef DefaultMap<Graph, Edge, EdgeT> Parent;
deba@1866: 
deba@1866:       EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 
deba@1866: 	: Parent(_graph), adaptor(_adaptor) {}
deba@1866: 
deba@1866:       virtual ~EdgesImpl() {}
deba@1866: 
deba@1866:       virtual void build() {
deba@1866: 	Parent::build();
deba@1866: 	Edge edge;
deba@1866: 	adaptor.Base::first(edge);
deba@1866: 	while (edge != INVALID) {
deba@1866: 	  Parent::operator[](edge).prevOut = edge;
deba@1866: 	  adaptor.Base::next(edge);
deba@1866: 	}
deba@1866:       }
deba@1866: 
deba@1866:       virtual void clear() {
deba@1866: 	Node node;
deba@1866: 	adaptor.first(node);
deba@1866: 	while (node != INVALID) {
deba@1866: 	  (*adaptor.nodes).firstIn = INVALID;
deba@1866: 	  (*adaptor.nodes).firstOut = INVALID;
deba@1866: 	  adaptor.next(node);
deba@1866: 	}
deba@1866: 	Parent::clear();
deba@1866:       }
deba@1866: 
deba@1866:       virtual void add(const Edge& edge) {
deba@1866: 	Parent::add(edge);
deba@1866: 	Parent::operator[](edge).prevOut = edge;
deba@1866:       }
deba@1866: 
deba@1866:       virtual void add(const std::vector<Edge>& edges) {
deba@1866: 	Parent::add(edges);
deba@1866: 	for (int i = 0; i < (int)edges.size(); ++i) {
deba@1866: 	  Parent::operator[](edges[i]).prevOut = edges[i];
deba@1866: 	}
deba@1866:       }
deba@1866: 
deba@1866:       virtual void erase(const Edge& edge) {
deba@1866: 	adaptor.hide(edge);
deba@1866: 	Parent::erase(edge);
deba@1866:       }
deba@1866: 
deba@1866:       virtual void erase(const std::vector<Edge>& edges) {
deba@1866: 	for (int i = 0; i < (int)edges.size(); ++i) {
deba@1866: 	  adaptor.hide(edges[i]);
deba@1866: 	}
deba@1964: 	Parent::erase(edges);
deba@1866:       }
deba@1866: 
deba@1866:     private:
deba@1866:       SubGraph& adaptor;
deba@1866:     };
deba@1866: 
deba@1866:     NodesImpl* nodes;
deba@1866:     EdgesImpl* edges;
deba@1866:     Node firstNode;
deba@1866:   };
deba@1866: 
deba@1866:   /// \ingroup semi_adaptors
deba@1866:   ///
alpar@2006:   /// \brief Graph which uses a subset of another graph's nodes and edges.
deba@1866:   ///
alpar@2006:   /// Graph which uses a subset of another graph's nodes and edges. This class
deba@1866:   /// is an alternative to the SubGraphAdaptor which is created for the
deba@1866:   /// same reason. The main difference between the two class that it
deba@1866:   /// makes linked lists on the unhidden nodes and edges what cause that
deba@1866:   /// on sparse subgraphs the algorithms can be more efficient and some times
deba@1866:   /// provide better time complexity. On other way this implemetation is
deba@1866:   /// less efficient in most case when the subgraph filters out only
deba@1866:   /// a few nodes or edges.
deba@1866:   /// 
deba@1866:   /// \see SubGraphAdaptor
deba@1866:   /// \see EdgeSubGraphBase
deba@1866:   template <typename Graph>
deba@1866:   class SubGraph 
deba@1979:     : public GraphAdaptorExtender< SubGraphBase<Graph> > {
deba@1866:   public:
deba@1979:     typedef GraphAdaptorExtender< SubGraphBase<Graph> > Parent;
deba@1866:   public:
deba@1866:     /// \brief Constructor for sub-graph.
deba@1866:     ///
deba@1866:     /// Constructor for sub-graph. Initially all the edges and nodes
deba@1866:     /// are hidden in the graph.
deba@1866:     SubGraph(const Graph& _graph) 
deba@1866:       : Parent(), nodes(*this, _graph), edges(*this, _graph) { 
deba@1866:       Parent::construct(_graph, nodes, edges);
deba@1866:     }
deba@1866:   private:
deba@1866:     typename Parent::NodesImpl nodes;
deba@1866:     typename Parent::EdgesImpl edges;
deba@1866:   };
deba@1866: 
deba@1866:   /// \brief Base for the EdgeSubGraph.
deba@1866:   ///
deba@1866:   /// Base for the EdgeSubGraph.
deba@1866:   template <typename _Graph>
deba@1866:   class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
deba@1866:   public:
deba@1866:     typedef _Graph Graph;
deba@1866:     typedef EdgeSubGraphBase<_Graph> SubGraph;
deba@1866:     typedef GraphAdaptorBase<const _Graph> Parent;
deba@1866:     typedef Parent Base;
deba@1866: 
deba@1866:     typedef typename Parent::Node Node;
deba@1866:     typedef typename Parent::Edge Edge;
deba@1866: 
deba@1866: 
deba@1866:   protected:
deba@1866: 
deba@1866:     class NodesImpl;
deba@1866:     class EdgesImpl;
deba@1866: 
deba@1866:     EdgeSubGraphBase() {}
deba@1866: 
deba@1866:     void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
deba@1866:       Parent::setGraph(_graph);
deba@1866:       nodes = &_nodes;
deba@1866:       edges = &_edges;
deba@1866: 
deba@1866:       Node node;
deba@1866:       Parent::first(node);
deba@1866:       while (node != INVALID) {
deba@1866: 	(*nodes)[node].firstIn = INVALID;
deba@1866: 	(*nodes)[node].firstOut = INVALID;
deba@1866: 	Parent::next(node);
deba@1866:       }
deba@1866: 
deba@1866:       Edge edge;
deba@1866:       Parent::first(edge);
deba@1866:       while (edge != INVALID) {
deba@1866: 	(*edges)[edge].prevOut = edge;
deba@1866: 	Parent::next(edge);
deba@1866:       }
deba@1866:     }
deba@1866: 
deba@1866:   public:
deba@1866: 
deba@1866:     void first(Node& node) const {
deba@1866:       Parent::first(node);
deba@1866:     }
deba@1866:     void next(Node& node) const {
deba@1866:       Parent::next(node);
deba@1866:     }
deba@1866: 
deba@1866:     void first(Edge& edge) const {
deba@1866:       Node node;
deba@1866:       Parent::first(node);
deba@1866:       while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
deba@1866: 	Parent::next(node);
deba@1866:       }
deba@1866:       if (node == INVALID) {
deba@1866: 	edge = INVALID;
deba@1866:       } else {
deba@1866: 	edge = (*nodes)[node].firstOut;
deba@1866:       }
deba@1866:     }
deba@1866:     void next(Edge& edge) const {
deba@1866:       if ((*edges)[edge].nextOut != INVALID) {
deba@1866: 	edge = (*edges)[edge].nextOut;
deba@1866:       } else {
deba@1866: 	Node node = source(edge);
deba@1866: 	Parent::next(node);
deba@1866: 	while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
deba@1866: 	  Parent::next(node);
deba@1866: 	}
deba@1866: 	if (node == INVALID) {
deba@1866: 	  edge = INVALID;
deba@1866: 	} else {
deba@1866: 	  edge = (*nodes)[node].firstOut;
deba@1866: 	}
deba@1866:       }
deba@1866:     }
deba@1866: 
deba@1866:     void firstOut(Edge& edge, const Node& node) const {
deba@1866:       edge = (*nodes)[node].firstOut;
deba@1866:     }
deba@1866:     void nextOut(Edge& edge) const {
deba@1866:       edge = (*edges)[edge].nextOut;
deba@1866:     }
deba@1866: 
deba@1866:     void firstIn(Edge& edge, const Node& node) const {
deba@1866:       edge = (*nodes)[node].firstIn;
deba@1866:     }
deba@1866:     void nextIn(Edge& edge) const {
deba@1866:       edge = (*edges)[edge].nextIn;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Returns true when the given edge is hidden.
deba@1866:     ///
deba@1866:     /// Returns true when the given edge is hidden.
deba@1866:     bool hidden(const Edge& edge) const {
deba@1866:       return (*edges)[edge].prevOut == edge;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Hide the given edge in the sub-graph.
deba@1866:     ///
deba@1866:     /// Hide the given edge in the sub graph. It just lace out from
deba@1866:     /// the linked lists the given edge.
deba@1866:     void hide(const Edge& edge) {
deba@1866:       if (hidden(edge)) return;
deba@1866:       if ((*edges)[edge].prevOut != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
deba@1866:       } else {
deba@1866: 	(*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
deba@1866:       }
deba@1866:       if ((*edges)[edge].nextOut != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
deba@1866:       }
deba@1866: 
deba@1866:       if ((*edges)[edge].prevIn != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
deba@1866:       } else {
deba@1866: 	(*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
deba@1866:       }
deba@1866:       if ((*edges)[edge].nextIn != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
deba@1866:       }
deba@1866:       (*edges)[edge].prevOut = edge;
deba@1866:     }
deba@1866: 
deba@1866:     /// \brief Unhide the given edge in the sub-graph.
deba@1866:     ///
deba@1866:     /// Unhide the given edge in the sub graph. It just lace in the given
deba@1866:     /// edge into the linked lists.
deba@1866:     void unHide(const Edge& edge) {
deba@1866:       if (!hidden(edge)) return;
deba@1866:       Node node;
deba@1866: 
deba@1866:       node = Parent::source(edge);
deba@1866:       (*edges)[edge].nextOut = (*nodes)[node].firstOut;
deba@1866:       (*edges)[edge].prevOut = INVALID;
deba@1866:       if ((*edges)[edge].nextOut != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextOut].prevOut = edge;
deba@1866:       }
deba@1866:       (*nodes)[node].firstOut = edge;
deba@1866: 
deba@1866:       node = Parent::target(edge);
deba@1866:       (*edges)[edge].nextIn = (*nodes)[node].firstIn;
deba@1866:       (*edges)[edge].prevIn = INVALID;
deba@1866:       if ((*edges)[edge].nextIn != INVALID) {
deba@1866: 	(*edges)[(*edges)[edge].nextIn].prevIn = edge;
deba@1866:       }
deba@1866:       (*nodes)[node].firstIn = edge;      
deba@1866:     }
deba@1866:     
deba@1866:   protected:
deba@1866:     struct NodeT {
deba@1866:       Edge firstIn, firstOut;
deba@1866:     };
deba@1990:     class NodesImpl : public DefaultMap<Graph, Node, NodeT> {
deba@1866:       friend class EdgeSubGraphBase;
deba@1866:     public:
deba@1990:       typedef DefaultMap<Graph, Node, NodeT> Parent;
deba@1866: 
deba@1866:       NodesImpl(SubGraph& _adaptor, const Graph& _graph) 
deba@1866: 	: Parent(_graph), adaptor(_adaptor) {}
deba@1866: 
deba@1866:       virtual ~NodesImpl() {}
deba@1866: 
deba@1866:       virtual void build() {
deba@1866: 	Parent::build();
deba@1866: 	Node node;
deba@1866: 	adaptor.Base::first(node);
deba@1866: 	while (node != INVALID) {
deba@1866: 	  Parent::operator[](node).firstIn = INVALID;
deba@1866: 	  Parent::operator[](node).firstOut = INVALID;
deba@1866: 	  adaptor.Base::next(node);
deba@1866: 	}
deba@1866:       }
deba@1866: 
deba@1866:       virtual void add(const Node& node) {
deba@1866: 	Parent::add(node);
deba@1866: 	Parent::operator[](node).firstIn = INVALID;
deba@1866: 	Parent::operator[](node).firstOut = INVALID;
deba@1866:       }
deba@1866: 
deba@1964:       virtual void add(const std::vector<Node>& nodes) {
deba@1964:         Parent::add(nodes);
deba@1964:         for (int i = 0; i < (int)nodes.size(); ++i) {
deba@1964:           Parent::operator[](nodes[i]).firstIn = INVALID;
deba@1964:           Parent::operator[](nodes[i]).firstOut = INVALID;
deba@1964:         }
deba@1964:       }
deba@1964: 
deba@1866:     private:
deba@1866:       SubGraph& adaptor;
deba@1866:     };
deba@1866: 
deba@1866:     struct EdgeT {
deba@1866:       Edge prevOut, nextOut;
deba@1866:       Edge prevIn, nextIn;
deba@1866:     };
deba@1990:     class EdgesImpl : public DefaultMap<Graph, Edge, EdgeT> {
deba@1866:       friend class EdgeSubGraphBase;
deba@1866:     public:
deba@1990:       typedef DefaultMap<Graph, Edge, EdgeT> Parent;
deba@1866: 
deba@1866:       EdgesImpl(SubGraph& _adaptor, const Graph& _graph) 
deba@1866: 	: Parent(_graph), adaptor(_adaptor) {}
deba@1866: 
deba@1866:       virtual ~EdgesImpl() {}
deba@1866: 
deba@1866:       virtual void build() {
deba@1866: 	Parent::build();
deba@1866: 	Edge edge;
deba@1866: 	adaptor.Base::first(edge);
deba@1866: 	while (edge != INVALID) {
deba@1866: 	  Parent::operator[](edge).prevOut = edge;
deba@1866: 	  adaptor.Base::next(edge);
deba@1866: 	}
deba@1866:       }
deba@1866: 
deba@1866:       virtual void clear() {
deba@1866: 	Node node;
deba@1866: 	adaptor.Base::first(node);
deba@1866: 	while (node != INVALID) {
deba@1866: 	  (*adaptor.nodes)[node].firstIn = INVALID;
deba@1866: 	  (*adaptor.nodes)[node].firstOut = INVALID;
deba@1866: 	  adaptor.Base::next(node);
deba@1866: 	}
deba@1866: 	Parent::clear();
deba@1866:       }
deba@1866: 
deba@1866:       virtual void add(const Edge& edge) {
deba@1866: 	Parent::add(edge);
deba@1866: 	Parent::operator[](edge).prevOut = edge;
deba@1866:       }
deba@1866: 
deba@1866:       virtual void add(const std::vector<Edge>& edges) {
deba@1866: 	Parent::add(edges);
deba@1866: 	for (int i = 0; i < (int)edges.size(); ++i) {
deba@1866: 	  Parent::operator[](edges[i]).prevOut = edges[i];
deba@1866: 	}
deba@1866:       }
deba@1866: 
deba@1866:       virtual void erase(const Edge& edge) {
deba@1866: 	adaptor.hide(edge);
deba@1866: 	Parent::erase(edge);
deba@1866:       }
deba@1866: 
deba@1866:       virtual void erase(const std::vector<Edge>& edges) {
deba@1866: 	for (int i = 0; i < (int)edges.size(); ++i) {
deba@1866: 	  adaptor.hide(edges[i]);
deba@1866: 	}
deba@1964: 	Parent::erase(edges);
deba@1866:       }
deba@1866: 
deba@1866:     private:
deba@1866:       SubGraph& adaptor;
deba@1866:     };
deba@1866: 
deba@1866:     NodesImpl* nodes;
deba@1866:     EdgesImpl* edges;
deba@1866:   };
deba@1866: 
deba@1866:   /// \ingroup semi_adaptors
deba@1866:   ///
alpar@2006:   /// \brief Graph which uses a subset of another graph's edges.
deba@1866:   ///
alpar@2006:   /// Graph which uses a subset of another graph's edges. This class
deba@1866:   /// is an alternative to the EdgeSubGraphAdaptor which is created for the
deba@1866:   /// same reason. The main difference between the two class that it
deba@1866:   /// makes linked lists on the unhidden edges what cause that
deba@1866:   /// on sparse subgraphs the algorithms can be more efficient and some times
deba@1866:   /// provide better time complexity. On other way this implemetation is
deba@1866:   /// less efficient in most case when the subgraph filters out only
deba@1866:   /// a few edges.
deba@1866:   /// 
deba@1866:   /// \see EdgeSubGraphAdaptor
deba@1866:   /// \see EdgeSubGraphBase
deba@1866:   template <typename Graph>
deba@1866:   class EdgeSubGraph 
deba@1979:     : public GraphAdaptorExtender< EdgeSubGraphBase<Graph> > {
deba@1866:   public:
deba@1979:     typedef GraphAdaptorExtender< EdgeSubGraphBase<Graph> > Parent;
deba@1866:   public:
deba@1866:     /// \brief Constructor for sub-graph.
deba@1866:     ///
deba@1866:     /// Constructor for sub-graph. Initially all the edges are hidden in the 
deba@1866:     /// graph.
deba@1866:     EdgeSubGraph(const Graph& _graph) 
deba@1866:       : Parent(), nodes(*this, _graph), edges(*this, _graph) { 
deba@1866:       Parent::construct(_graph, nodes, edges);
deba@1866:     }
deba@1866:   private:
deba@1866:     typename Parent::NodesImpl nodes;
deba@1866:     typename Parent::EdgesImpl edges;
deba@1866:   };
deba@1866: 
deba@1866: 
deba@1866: //   template<typename Graph, typename Number, 
deba@1866: // 	   typename CapacityMap, typename FlowMap>
deba@1866: //   class ResGraph
deba@1866: //     : public IterableGraphExtender<EdgeSubGraphBase<
klao@1909: //     UGraphAdaptor<Graph> > > {
deba@1866: //   public:
deba@1866: //     typedef IterableGraphExtender<EdgeSubGraphBase<
klao@1909: //       UGraphAdaptor<Graph> > > Parent;
deba@1866: 
deba@1866: //   protected:
klao@1909: //     UGraphAdaptor<Graph> u;
deba@1866: 
deba@1866: //     const CapacityMap* capacity;
deba@1866: //     FlowMap* flow;
deba@1866: 
deba@1866: //     typename Parent::NodesImpl nodes;
deba@1866: //     typename Parent::EdgesImpl edges;
deba@1866: 
deba@1866: //     void setCapacityMap(const CapacityMap& _capacity) {
deba@1866: //       capacity=&_capacity;
deba@1866: //     }
deba@1866: 
deba@1866: //     void setFlowMap(FlowMap& _flow) {
deba@1866: //       flow=&_flow;
deba@1866: //     }
deba@1866: 
deba@1866: //   public:
deba@1866: 
klao@1909: //     typedef typename UGraphAdaptor<Graph>::Node Node;
klao@1909: //     typedef typename UGraphAdaptor<Graph>::Edge Edge;
klao@1909: //     typedef typename UGraphAdaptor<Graph>::UEdge UEdge;
deba@1866: 
deba@1866: //     ResGraphAdaptor(Graph& _graph, 
deba@1866: // 		    const CapacityMap& _capacity, FlowMap& _flow) 
klao@1909: //       : Parent(), u(_graph), capacity(&_capacity), flow(&_flow),
deba@1866: // 	nodes(*this, _graph), edges(*this, _graph) {
klao@1909: //       Parent::construct(u, nodes, edges);
deba@1866: //       setFlowMap(_flow);
deba@1866: //       setCapacityMap(_capacity);
deba@1866: //       typename Graph::Edge edge; 
deba@1866: //       for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
deba@1866: // 	if ((*flow)[edge] != (*capacity)[edge]) {
deba@1866: // 	  Parent::unHide(direct(edge, true));
deba@1866: // 	}
deba@1866: // 	if ((*flow)[edge] != 0) {
deba@1866: // 	  Parent::unHide(direct(edge, false));
deba@1866: // 	}
deba@1866: //       }
deba@1866: //     }
deba@1866: 
deba@1866: //     void augment(const Edge& e, Number a) {
deba@1866: //       if (direction(e)) {
deba@1866: // 	flow->set(e, (*flow)[e]+a);
deba@1866: //       } else { 
deba@1866: // 	flow->set(e, (*flow)[e]-a);
deba@1866: //       }
deba@1866: //       if ((*flow)[e] == (*capacity)[e]) {
deba@1866: // 	Parent::hide(e);
deba@1866: //       } else {
deba@1866: // 	Parent::unHide(e);
deba@1866: //       }
deba@1866: //       if ((*flow)[e] == 0) {
deba@1866: // 	Parent::hide(oppositeEdge(e));
deba@1866: //       } else {
deba@1866: // 	Parent::unHide(oppositeEdge(e));
deba@1866: //       }
deba@1866: //     }
deba@1866: 
deba@1866: //     Number resCap(const Edge& e) {
deba@1866: //       if (direction(e)) { 
deba@1866: // 	return (*capacity)[e]-(*flow)[e]; 
deba@1866: //       } else { 
deba@1866: // 	return (*flow)[e];
deba@1866: //       }
deba@1866: //     }
deba@1866:     
deba@1866: //     bool direction(const Edge& edge) const {
deba@1866: //       return Parent::getGraph().direction(edge);
deba@1866: //     }
deba@1866: 
klao@1909: //     Edge direct(const UEdge& edge, bool direction) const {
deba@1866: //       return Parent::getGraph().direct(edge, direction);
deba@1866: //     }
deba@1866: 
klao@1909: //     Edge direct(const UEdge& edge, const Node& node) const {
deba@1866: //       return Parent::getGraph().direct(edge, node);
deba@1866: //     }
deba@1866: 
deba@1866: //     Edge oppositeEdge(const Edge& edge) const {
deba@1866: //       return Parent::getGraph().oppositeEdge(edge);
deba@1866: //     }
deba@1866: 
deba@1866: //     /// \brief Residual capacity map.
deba@1866: //     ///
deba@1866: //     /// In generic residual graphs the residual capacity can be obtained 
deba@1866: //     /// as a map. 
deba@1866: //     class ResCap {
deba@1866: //     protected:
deba@1866: //       const ResGraphAdaptor* res_graph;
deba@1866: //     public:
deba@1866: //       typedef Number Value;
deba@1866: //       typedef Edge Key;
deba@1866: //       ResCap(const ResGraphAdaptor& _res_graph) 
deba@1866: // 	: res_graph(&_res_graph) {}
deba@1866: //       Number operator[](const Edge& e) const {
deba@1866: // 	return res_graph->resCap(e);
deba@1866: //       }
deba@1866: //     };
deba@1866: //   };
deba@1866: 
deba@1866: }
deba@1866: 
deba@1866: #endif