deba@1866: /* -*- C++ -*-
deba@1866: *
alpar@1956: * This file is a part of LEMON, a generic C++ optimization library
alpar@1956: *
alpar@2391: * Copyright (C) 2003-2007
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