deba@1866: /* -*- C++ -*- deba@1866: * lemon/sub_graph.h - Part of LEMON, a generic C++ optimization library deba@1866: * alpar@1875: * Copyright (C) 2006 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 deba@1866: deba@1866: namespace lemon { deba@1866: deba@1866: /// \brief Base for the SubGraph. deba@1866: /// deba@1866: /// Base for the SubGraph. deba@1866: template deba@1866: class SubGraphBase : public GraphAdaptorBase { deba@1866: public: deba@1866: typedef _Graph Graph; deba@1866: typedef SubGraphBase<_Graph> SubGraph; deba@1866: typedef GraphAdaptorBase 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@1866: class NodesImpl : public Graph::template NodeMap { deba@1866: friend class SubGraphBase; deba@1866: public: deba@1866: typedef typename Graph::template NodeMap 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@1866: virtual void add(const std::vector& 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& 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@1866: class EdgesImpl : public Graph::template EdgeMap { deba@1866: friend class SubGraphBase; deba@1866: public: deba@1866: typedef typename Graph::template EdgeMap 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& 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& edges) { deba@1866: for (int i = 0; i < (int)edges.size(); ++i) { deba@1866: adaptor.hide(edges[i]); deba@1866: } deba@1866: Parent::erase(edge); 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: /// deba@1866: /// \brief Graph which uses a subset of an other graph's nodes and edges. deba@1866: /// deba@1866: /// Graph which uses a subset of an other 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 deba@1866: class SubGraph deba@1866: : public IterableGraphExtender< SubGraphBase > { deba@1866: public: deba@1866: typedef IterableGraphExtender< SubGraphBase > 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 deba@1866: class EdgeSubGraphBase : public GraphAdaptorBase { deba@1866: public: deba@1866: typedef _Graph Graph; deba@1866: typedef EdgeSubGraphBase<_Graph> SubGraph; deba@1866: typedef GraphAdaptorBase 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@1866: class NodesImpl : public Graph::template NodeMap { deba@1866: friend class EdgeSubGraphBase; deba@1866: public: deba@1866: typedef typename Graph::template NodeMap 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@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@1866: class EdgesImpl : public Graph::template EdgeMap { deba@1866: friend class EdgeSubGraphBase; deba@1866: public: deba@1866: typedef typename Graph::template EdgeMap 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& 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& edges) { deba@1866: for (int i = 0; i < (int)edges.size(); ++i) { deba@1866: adaptor.hide(edges[i]); deba@1866: } deba@1866: Parent::erase(edge); 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: /// deba@1866: /// \brief Graph which uses a subset of an other graph's edges. deba@1866: /// deba@1866: /// Graph which uses a subset of an other 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 deba@1866: class EdgeSubGraph deba@1866: : public IterableGraphExtender< EdgeSubGraphBase > { deba@1866: public: deba@1866: typedef IterableGraphExtender< EdgeSubGraphBase > 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 deba@1866: // class ResGraph deba@1866: // : public IterableGraphExtender > > { deba@1866: // public: deba@1866: // typedef IterableGraphExtender > > Parent; deba@1866: deba@1866: // protected: deba@1866: // UndirGraphAdaptor undir; 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: deba@1866: // typedef typename UndirGraphAdaptor::Node Node; deba@1866: // typedef typename UndirGraphAdaptor::Edge Edge; deba@1866: // typedef typename UndirGraphAdaptor::UndirEdge UndirEdge; deba@1866: deba@1866: // ResGraphAdaptor(Graph& _graph, deba@1866: // const CapacityMap& _capacity, FlowMap& _flow) deba@1866: // : Parent(), undir(_graph), capacity(&_capacity), flow(&_flow), deba@1866: // nodes(*this, _graph), edges(*this, _graph) { deba@1866: // Parent::construct(undir, 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: deba@1866: // Edge direct(const UndirEdge& edge, bool direction) const { deba@1866: // return Parent::getGraph().direct(edge, direction); deba@1866: // } deba@1866: deba@1866: // Edge direct(const UndirEdge& 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