alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@906: * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@921: #ifndef LEMON_GRAPH_WRAPPER_H alpar@921: #define LEMON_GRAPH_WRAPPER_H marci@556: marci@556: ///\ingroup gwrappers marci@556: ///\file marci@556: ///\brief Several graph wrappers. marci@556: /// marci@556: ///This file contains several useful graph wrapper functions. marci@556: /// marci@556: ///\author Marton Makai marci@556: alpar@921: #include alpar@921: #include marci@992: #include alpar@921: #include alpar@774: #include marci@556: alpar@921: namespace lemon { marci@556: marci@556: // Graph wrappers marci@556: marci@1004: /*! \addtogroup gwrappers marci@1004: The main parts of LEMON are the different graph structures, marci@1004: generic graph algorithms, graph concepts which couple these, and marci@1004: graph wrappers. While the previous ones are more or less clear, the marci@1004: latter notion needs further explanation. marci@1004: Graph wrappers are graph classes which serve for considering graph marci@1004: structures in different ways. A short example makes the notion much marci@1004: clearer. marci@1004: Suppose that we have an instance \c g of a directed graph marci@1004: type say \c ListGraph and an algorithm marci@1004: \code template int algorithm(const Graph&); \endcode marci@1004: is needed to run on the reversely oriented graph. marci@1004: It may be expensive (in time or in memory usage) to copy marci@1004: \c g with the reverse orientation. marci@1004: Thus, a wrapper class marci@1004: \code template class RevGraphWrapper; \endcode is used. marci@1004: The code looks as follows marci@1004: \code marci@1004: ListGraph g; marci@1004: RevGraphWrapper rgw(g); marci@1004: int result=algorithm(rgw); marci@1004: \endcode marci@1004: After running the algorithm, the original graph \c g marci@1004: remains untouched. Thus the graph wrapper used above is to consider the marci@1004: original graph with reverse orientation. marci@1004: This techniques gives rise to an elegant code, and marci@1004: based on stable graph wrappers, complex algorithms can be marci@1004: implemented easily. marci@1004: In flow, circulation and bipartite matching problems, the residual marci@1004: graph is of particular importance. Combining a wrapper implementing marci@1004: this, shortest path algorithms and minimum mean cycle algorithms, marci@1004: a range of weighted and cardinality optimization algorithms can be marci@1004: obtained. For lack of space, for other examples, marci@1004: the interested user is referred to the detailed documentation of graph marci@1004: wrappers. marci@1004: The behavior of graph wrappers can be very different. Some of them keep marci@1004: capabilities of the original graph while in other cases this would be marci@1004: meaningless. This means that the concepts that they are a model of depend marci@1004: on the graph wrapper, and the wrapped graph(s). marci@1004: If an edge of \c rgw is deleted, this is carried out by marci@1004: deleting the corresponding edge of \c g. But for a residual marci@1004: graph, this operation has no sense. marci@1004: Let we stand one more example here to simplify your work. marci@1004: wrapper class marci@1004: \code template class RevGraphWrapper; \endcode marci@1004: has constructor marci@1004: RevGraphWrapper(Graph& _g). marci@1004: This means that in a situation, marci@1004: when a const ListGraph& reference to a graph is given, marci@1004: then it have to be instantiated with Graph=const ListGraph. marci@1004: \code marci@1004: int algorithm1(const ListGraph& g) { marci@1004: RevGraphWrapper rgw(g); marci@1004: return algorithm2(rgw); marci@1004: } marci@1004: \endcode marci@556: marci@1004: \addtogroup gwrappers marci@1004: @{ marci@556: marci@1004: Base type for the Graph Wrappers marci@556: marci@1004: \warning Graph wrappers are in even more experimental state than the other marci@1004: parts of the lib. Use them at you own risk. marci@1004: marci@1004: This is the base type for most of LEMON graph wrappers. marci@1004: This class implements a trivial graph wrapper i.e. it only wraps the marci@1004: functions and types of the graph. The purpose of this class is to marci@1004: make easier implementing graph wrappers. E.g. if a wrapper is marci@1004: considered which differs from the wrapped graph only in some of its marci@1004: functions or types, then it can be derived from GraphWrapper, and only the marci@1004: differences should be implemented. marci@1004: marci@1004: \author Marton Makai marci@1004: */ marci@970: template marci@970: class GraphWrapperBase { marci@970: public: marci@970: typedef _Graph Graph; marci@970: /// \todo Is it needed? marci@970: typedef Graph BaseGraph; marci@970: typedef Graph ParentGraph; marci@970: marci@556: protected: marci@556: Graph* graph; marci@970: GraphWrapperBase() : graph(0) { } marci@556: void setGraph(Graph& _graph) { graph=&_graph; } marci@556: marci@556: public: marci@970: GraphWrapperBase(Graph& _graph) : graph(&_graph) { } marci@556: alpar@774: typedef typename Graph::Node Node; alpar@774: typedef typename Graph::Edge Edge; marci@556: marci@970: void first(Node& i) const { graph->first(i); } marci@970: void first(Edge& i) const { graph->first(i); } marci@970: void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); } marci@970: void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); } marci@556: marci@970: void next(Node& i) const { graph->next(i); } marci@970: void next(Edge& i) const { graph->next(i); } marci@970: void nextIn(Edge& i) const { graph->nextIn(i); } marci@970: void nextOut(Edge& i) const { graph->nextOut(i); } marci@970: alpar@986: Node source(const Edge& e) const { return graph->source(e); } alpar@986: Node target(const Edge& e) const { return graph->target(e); } marci@556: marci@556: int nodeNum() const { return graph->nodeNum(); } marci@556: int edgeNum() const { return graph->edgeNum(); } marci@556: marci@556: Node addNode() const { return Node(graph->addNode()); } alpar@986: Edge addEdge(const Node& source, const Node& target) const { alpar@986: return Edge(graph->addEdge(source, target)); } marci@556: marci@556: void erase(const Node& i) const { graph->erase(i); } marci@556: void erase(const Edge& i) const { graph->erase(i); } marci@556: marci@556: void clear() const { graph->clear(); } marci@556: alpar@736: bool forward(const Edge& e) const { return graph->forward(e); } alpar@736: bool backward(const Edge& e) const { return graph->backward(e); } marci@739: marci@739: int id(const Node& v) const { return graph->id(v); } marci@739: int id(const Edge& e) const { return graph->id(e); } marci@650: marci@738: Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); } marci@650: marci@970: template marci@970: class NodeMap : public _Graph::template NodeMap<_Value> { marci@970: public: marci@970: typedef typename _Graph::template NodeMap<_Value> Parent; marci@970: NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { } marci@970: NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value) marci@970: : Parent(*gw.graph, value) { } marci@970: }; marci@556: marci@970: template marci@970: class EdgeMap : public _Graph::template EdgeMap<_Value> { marci@970: public: marci@970: typedef typename _Graph::template EdgeMap<_Value> Parent; marci@970: EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { } marci@970: EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value) marci@970: : Parent(*gw.graph, value) { } marci@970: }; deba@877: marci@556: }; marci@556: marci@970: template marci@970: class GraphWrapper : marci@970: public IterableGraphExtender > { marci@970: public: marci@970: typedef _Graph Graph; marci@970: typedef IterableGraphExtender > Parent; marci@970: protected: marci@970: GraphWrapper() : Parent() { } marci@569: marci@970: public: marci@970: GraphWrapper(Graph& _graph) { setGraph(_graph); } marci@970: }; marci@569: marci@997: template marci@997: class RevGraphWrapperBase : public GraphWrapperBase<_Graph> { marci@997: public: marci@997: typedef _Graph Graph; marci@997: typedef GraphWrapperBase<_Graph> Parent; marci@997: protected: marci@997: RevGraphWrapperBase() : Parent() { } marci@997: public: marci@997: typedef typename Parent::Node Node; marci@997: typedef typename Parent::Edge Edge; marci@997: marci@997: using Parent::first; marci@997: void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); } marci@997: void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); } marci@997: marci@997: using Parent::next; marci@997: void nextIn(Edge& i) const { Parent::nextOut(i); } marci@997: void nextOut(Edge& i) const { Parent::nextIn(i); } marci@997: marci@997: Node source(const Edge& e) const { return Parent::target(e); } marci@997: Node target(const Edge& e) const { return Parent::source(e); } marci@997: }; marci@997: marci@997: marci@556: /// A graph wrapper which reverses the orientation of the edges. marci@556: alpar@879: ///\warning Graph wrappers are in even more experimental state than the other alpar@879: ///parts of the lib. Use them at you own risk. alpar@879: /// marci@923: /// Let \f$G=(V, A)\f$ be a directed graph and marci@923: /// suppose that a graph instange \c g of type marci@923: /// \c ListGraph implements \f$G\f$. marci@923: /// \code marci@923: /// ListGraph g; marci@923: /// \endcode marci@923: /// For each directed edge marci@923: /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by marci@923: /// reversing its orientation. marci@923: /// Then RevGraphWrapper implements the graph structure with node-set marci@923: /// \f$V\f$ and edge-set marci@923: /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be marci@923: /// reversing the orientation of its edges. The following code shows how marci@923: /// such an instance can be constructed. marci@923: /// \code marci@923: /// RevGraphWrapper gw(g); marci@923: /// \endcode marci@556: ///\author Marton Makai marci@997: template marci@997: class RevGraphWrapper : marci@997: public IterableGraphExtender > { marci@650: public: marci@997: typedef _Graph Graph; marci@997: typedef IterableGraphExtender< marci@997: RevGraphWrapperBase<_Graph> > Parent; marci@556: protected: marci@997: RevGraphWrapper() { } marci@556: public: marci@997: RevGraphWrapper(_Graph& _graph) { setGraph(_graph); } marci@997: }; marci@556: marci@992: marci@992: template marci@992: class SubGraphWrapperBase : public GraphWrapperBase<_Graph> { marci@992: public: marci@992: typedef _Graph Graph; marci@992: typedef GraphWrapperBase<_Graph> Parent; marci@992: protected: marci@992: NodeFilterMap* node_filter_map; marci@992: EdgeFilterMap* edge_filter_map; marci@992: SubGraphWrapperBase() : Parent(), marci@992: node_filter_map(0), edge_filter_map(0) { } marci@775: marci@992: void setNodeFilterMap(NodeFilterMap& _node_filter_map) { marci@992: node_filter_map=&_node_filter_map; marci@992: } marci@992: void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { marci@992: edge_filter_map=&_edge_filter_map; marci@992: } marci@992: marci@992: public: marci@992: // SubGraphWrapperBase(Graph& _graph, marci@992: // NodeFilterMap& _node_filter_map, marci@992: // EdgeFilterMap& _edge_filter_map) : marci@992: // Parent(&_graph), marci@992: // node_filter_map(&node_filter_map), marci@992: // edge_filter_map(&edge_filter_map) { } marci@992: marci@992: typedef typename Parent::Node Node; marci@992: typedef typename Parent::Edge Edge; marci@992: marci@992: void first(Node& i) const { marci@992: Parent::first(i); marci@992: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); marci@992: } marci@992: void first(Edge& i) const { marci@992: Parent::first(i); marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); marci@992: } marci@992: void firstIn(Edge& i, const Node& n) const { marci@992: Parent::firstIn(i, n); marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); marci@992: } marci@992: void firstOut(Edge& i, const Node& n) const { marci@992: Parent::firstOut(i, n); marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); marci@992: } marci@992: marci@992: void next(Node& i) const { marci@992: Parent::next(i); marci@992: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); marci@992: } marci@992: void next(Edge& i) const { marci@992: Parent::next(i); marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); marci@992: } marci@992: void nextIn(Edge& i) const { marci@992: Parent::nextIn(i); marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); marci@992: } marci@992: void nextOut(Edge& i) const { marci@992: Parent::nextOut(i); marci@992: while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); marci@992: } marci@992: marci@992: /// This function hides \c n in the graph, i.e. the iteration marci@992: /// jumps over it. This is done by simply setting the value of \c n marci@992: /// to be false in the corresponding node-map. marci@992: void hide(const Node& n) const { node_filter_map->set(n, false); } marci@992: marci@992: /// This function hides \c e in the graph, i.e. the iteration marci@992: /// jumps over it. This is done by simply setting the value of \c e marci@992: /// to be false in the corresponding edge-map. marci@992: void hide(const Edge& e) const { edge_filter_map->set(e, false); } marci@992: marci@992: /// The value of \c n is set to be true in the node-map which stores marci@992: /// hide information. If \c n was hidden previuosly, then it is shown marci@992: /// again marci@992: void unHide(const Node& n) const { node_filter_map->set(n, true); } marci@992: marci@992: /// The value of \c e is set to be true in the edge-map which stores marci@992: /// hide information. If \c e was hidden previuosly, then it is shown marci@992: /// again marci@992: void unHide(const Edge& e) const { edge_filter_map->set(e, true); } marci@992: marci@992: /// Returns true if \c n is hidden. marci@992: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } marci@992: marci@992: /// Returns true if \c n is hidden. marci@992: bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } marci@992: marci@992: /// \warning This is a linear time operation and works only if s marci@992: /// \c Graph::NodeIt is defined. marci@992: /// \todo assign tags. marci@992: int nodeNum() const { marci@992: int i=0; marci@992: Node n; marci@992: for (first(n); n!=INVALID; next(n)) ++i; marci@992: return i; marci@992: } marci@992: marci@992: /// \warning This is a linear time operation and works only if marci@992: /// \c Graph::EdgeIt is defined. marci@992: /// \todo assign tags. marci@992: int edgeNum() const { marci@992: int i=0; marci@992: Edge e; marci@992: for (first(e); e!=INVALID; next(e)) ++i; marci@992: return i; marci@992: } marci@992: marci@992: marci@992: }; marci@775: marci@930: /*! \brief A graph wrapper for hiding nodes and edges from a graph. marci@556: marci@930: \warning Graph wrappers are in even more experimental state than the other marci@930: parts of the lib. Use them at you own risk. marci@930: marci@930: This wrapper shows a graph with filtered node-set and marci@930: edge-set. marci@930: Given a bool-valued map on the node-set and one on marci@930: the edge-set of the graph, the iterators show only the objects marci@930: having true value. We have to note that this does not mean that an marci@930: induced subgraph is obtained, the node-iterator cares only the filter marci@930: on the node-set, and the edge-iterators care only the filter on the marci@930: edge-set. marci@930: \code marci@930: typedef SmartGraph Graph; marci@930: Graph g; marci@930: typedef Graph::Node Node; marci@930: typedef Graph::Edge Edge; marci@930: Node u=g.addNode(); //node of id 0 marci@930: Node v=g.addNode(); //node of id 1 marci@930: Node e=g.addEdge(u, v); //edge of id 0 marci@930: Node f=g.addEdge(v, u); //edge of id 1 marci@930: Graph::NodeMap nm(g, true); marci@930: nm.set(u, false); marci@930: Graph::EdgeMap em(g, true); marci@930: em.set(e, false); marci@930: typedef SubGraphWrapper, Graph::EdgeMap > SubGW; marci@930: SubGW gw(g, nm, em); marci@930: for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; marci@930: std::cout << ":-)" << std::endl; marci@930: for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; marci@930: \endcode marci@930: The output of the above code is the following. marci@930: \code marci@930: 1 marci@930: :-) marci@930: 1 marci@930: \endcode marci@930: Note that \c n is of type \c SubGW::NodeIt, but it can be converted to marci@930: \c Graph::Node that is why \c g.id(n) can be applied. marci@930: marci@933: For other examples see also the documentation of NodeSubGraphWrapper and marci@933: EdgeSubGraphWrapper. marci@930: marci@930: \author Marton Makai marci@930: */ marci@992: template marci@992: class SubGraphWrapper : marci@992: public IterableGraphExtender< marci@992: SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > { marci@650: public: marci@992: typedef _Graph Graph; marci@992: typedef IterableGraphExtender< marci@992: SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; marci@556: protected: marci@992: SubGraphWrapper() { } marci@992: public: marci@992: SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map, marci@992: EdgeFilterMap& _edge_filter_map) { marci@992: setGraph(_graph); marci@992: setNodeFilterMap(_node_filter_map); marci@992: setEdgeFilterMap(_edge_filter_map); marci@992: } marci@992: }; marci@556: marci@556: marci@569: marci@933: /*! \brief A wrapper for hiding nodes from a graph. marci@933: marci@933: \warning Graph wrappers are in even more experimental state than the other marci@933: parts of the lib. Use them at you own risk. marci@933: marci@933: A wrapper for hiding nodes from a graph. marci@933: This wrapper specializes SubGraphWrapper in the way that only the node-set marci@933: can be filtered. Note that this does not mean of considering induced marci@933: subgraph, the edge-iterators consider the original edge-set. marci@933: \author Marton Makai marci@933: */ marci@933: template marci@933: class NodeSubGraphWrapper : marci@933: public SubGraphWrapper > { marci@933: public: marci@933: typedef SubGraphWrapper > Parent; marci@933: protected: marci@933: ConstMap const_true_map; marci@933: public: marci@933: NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) : marci@933: Parent(), const_true_map(true) { marci@933: Parent::setGraph(_graph); marci@933: Parent::setNodeFilterMap(_node_filter_map); marci@933: Parent::setEdgeFilterMap(const_true_map); marci@933: } marci@933: }; marci@933: marci@933: marci@932: /*! \brief A wrapper for hiding edges from a graph. marci@932: marci@932: \warning Graph wrappers are in even more experimental state than the other marci@932: parts of the lib. Use them at you own risk. marci@932: marci@932: A wrapper for hiding edges from a graph. marci@932: This wrapper specializes SubGraphWrapper in the way that only the edge-set marci@933: can be filtered. The usefulness of this wrapper is demonstrated in the marci@933: problem of searching a maximum number of edge-disjoint shortest paths marci@933: between marci@933: two nodes \c s and \c t. Shortest here means being shortest w.r.t. marci@933: non-negative edge-lengths. Note that marci@933: the comprehension of the presented solution marci@933: need's some knowledge from elementary combinatorial optimization. marci@933: marci@933: If a single shortest path is to be marci@933: searched between two nodes \c s and \c t, then this can be done easily by marci@933: applying the Dijkstra algorithm class. What happens, if a maximum number of marci@933: edge-disjoint shortest paths is to be computed. It can be proved that an marci@933: edge can be in a shortest path if and only if it is tight with respect to marci@933: the potential function computed by Dijkstra. Moreover, any path containing marci@933: only such edges is a shortest one. Thus we have to compute a maximum number marci@933: of edge-disjoint paths between \c s and \c t in the graph which has edge-set marci@933: all the tight edges. The computation will be demonstrated on the following marci@933: graph, which is read from a dimacs file. marci@933: marci@933: \dot marci@933: digraph lemon_dot_example { marci@933: node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; marci@933: n0 [ label="0 (s)" ]; marci@933: n1 [ label="1" ]; marci@933: n2 [ label="2" ]; marci@933: n3 [ label="3" ]; marci@933: n4 [ label="4" ]; marci@933: n5 [ label="5" ]; marci@933: n6 [ label="6 (t)" ]; marci@933: edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; marci@933: n5 -> n6 [ label="9, length:4" ]; marci@933: n4 -> n6 [ label="8, length:2" ]; marci@933: n3 -> n5 [ label="7, length:1" ]; marci@933: n2 -> n5 [ label="6, length:3" ]; marci@933: n2 -> n6 [ label="5, length:5" ]; marci@933: n2 -> n4 [ label="4, length:2" ]; marci@933: n1 -> n4 [ label="3, length:3" ]; marci@933: n0 -> n3 [ label="2, length:1" ]; marci@933: n0 -> n2 [ label="1, length:2" ]; marci@933: n0 -> n1 [ label="0, length:3" ]; marci@933: } marci@933: \enddot marci@933: marci@933: \code marci@933: Graph g; marci@933: Node s, t; marci@933: LengthMap length(g); marci@933: marci@933: readDimacs(std::cin, g, length, s, t); marci@933: alpar@986: cout << "edges with lengths (of form id, source--length->target): " << endl; marci@933: for(EdgeIt e(g); e!=INVALID; ++e) alpar@986: cout << g.id(e) << ", " << g.id(g.source(e)) << "--" alpar@986: << length[e] << "->" << g.id(g.target(e)) << endl; marci@933: marci@933: cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; marci@933: \endcode marci@933: Next, the potential function is computed with Dijkstra. marci@933: \code marci@933: typedef Dijkstra Dijkstra; marci@933: Dijkstra dijkstra(g, length); marci@933: dijkstra.run(s); marci@933: \endcode marci@933: Next, we consrtruct a map which filters the edge-set to the tight edges. marci@933: \code marci@933: typedef TightEdgeFilterMap marci@933: TightEdgeFilter; marci@933: TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); marci@933: marci@933: typedef EdgeSubGraphWrapper SubGW; marci@933: SubGW gw(g, tight_edge_filter); marci@933: \endcode marci@933: Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed marci@933: with a max flow algorithm Preflow. marci@933: \code marci@933: ConstMap const_1_map(1); marci@933: Graph::EdgeMap flow(g, 0); marci@933: marci@933: Preflow, Graph::EdgeMap > marci@933: preflow(gw, s, t, const_1_map, flow); marci@933: preflow.run(); marci@933: \endcode marci@933: Last, the output is: marci@933: \code marci@933: cout << "maximum number of edge-disjoint shortest path: " marci@933: << preflow.flowValue() << endl; marci@933: cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " marci@933: << endl; marci@933: for(EdgeIt e(g); e!=INVALID; ++e) marci@933: if (flow[e]) alpar@986: cout << " " << g.id(g.source(e)) << "--" alpar@986: << length[e] << "->" << g.id(g.target(e)) << endl; marci@933: \endcode marci@933: The program has the following (expected :-)) output: marci@933: \code alpar@986: edges with lengths (of form id, source--length->target): marci@933: 9, 5--4->6 marci@933: 8, 4--2->6 marci@933: 7, 3--1->5 marci@933: 6, 2--3->5 marci@933: 5, 2--5->6 marci@933: 4, 2--2->4 marci@933: 3, 1--3->4 marci@933: 2, 0--1->3 marci@933: 1, 0--2->2 marci@933: 0, 0--3->1 marci@933: s: 0 t: 6 marci@933: maximum number of edge-disjoint shortest path: 2 marci@933: edges of the maximum number of edge-disjoint shortest s-t paths: marci@933: 9, 5--4->6 marci@933: 8, 4--2->6 marci@933: 7, 3--1->5 marci@933: 4, 2--2->4 marci@933: 2, 0--1->3 marci@933: 1, 0--2->2 marci@933: \endcode marci@933: marci@932: \author Marton Makai marci@932: */ marci@932: template marci@932: class EdgeSubGraphWrapper : marci@932: public SubGraphWrapper, marci@932: EdgeFilterMap> { marci@932: public: marci@932: typedef SubGraphWrapper, marci@932: EdgeFilterMap> Parent; marci@932: protected: marci@932: ConstMap const_true_map; marci@932: public: marci@932: EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) : marci@932: Parent(), const_true_map(true) { marci@932: Parent::setGraph(_graph); marci@932: Parent::setNodeFilterMap(const_true_map); marci@932: Parent::setEdgeFilterMap(_edge_filter_map); marci@932: } marci@932: }; marci@932: marci@569: marci@556: template marci@556: class UndirGraphWrapper : public GraphWrapper { marci@650: public: marci@650: typedef GraphWrapper Parent; marci@556: protected: marci@556: UndirGraphWrapper() : GraphWrapper() { } marci@556: marci@556: public: marci@556: typedef typename GraphWrapper::Node Node; marci@556: typedef typename GraphWrapper::NodeIt NodeIt; marci@556: typedef typename GraphWrapper::Edge Edge; marci@556: typedef typename GraphWrapper::EdgeIt EdgeIt; marci@556: marci@556: UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } marci@556: marci@556: class OutEdgeIt { marci@556: friend class UndirGraphWrapper; marci@556: bool out_or_in; //true iff out marci@556: typename Graph::OutEdgeIt out; marci@556: typename Graph::InEdgeIt in; marci@556: public: marci@556: OutEdgeIt() { } marci@556: OutEdgeIt(const Invalid& i) : Edge(i) { } marci@556: OutEdgeIt(const UndirGraphWrapper& _G, const Node& _n) { marci@556: out_or_in=true; _G.graph->first(out, _n); marci@556: if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } marci@556: } marci@556: operator Edge() const { marci@556: if (out_or_in) return Edge(out); else return Edge(in); marci@556: } marci@556: }; marci@556: marci@556: typedef OutEdgeIt InEdgeIt; marci@556: marci@556: using GraphWrapper::first; marci@556: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@556: i=OutEdgeIt(*this, p); return i; marci@556: } marci@556: marci@556: using GraphWrapper::next; alpar@878: marci@556: OutEdgeIt& next(OutEdgeIt& e) const { marci@556: if (e.out_or_in) { alpar@986: typename Graph::Node n=this->graph->source(e.out); marci@556: this->graph->next(e.out); marci@556: if (!this->graph->valid(e.out)) { marci@556: e.out_or_in=false; this->graph->first(e.in, n); } marci@556: } else { marci@556: this->graph->next(e.in); marci@556: } marci@556: return e; marci@556: } marci@556: marci@556: Node aNode(const OutEdgeIt& e) const { alpar@986: if (e.out_or_in) return this->graph->source(e); else alpar@986: return this->graph->target(e); } marci@556: Node bNode(const OutEdgeIt& e) const { alpar@986: if (e.out_or_in) return this->graph->target(e); else alpar@986: return this->graph->source(e); } deba@877: deba@891: // KEEP_MAPS(Parent, UndirGraphWrapper); deba@877: marci@556: }; marci@556: marci@910: // /// \brief An undirected graph template. marci@910: // /// marci@910: // ///\warning Graph wrappers are in even more experimental state than the other marci@910: // ///parts of the lib. Use them at your own risk. marci@910: // /// marci@910: // /// An undirected graph template. marci@910: // /// This class works as an undirected graph and a directed graph of marci@910: // /// class \c Graph is used for the physical storage. marci@910: // /// \ingroup graphs marci@556: template marci@556: class UndirGraph : public UndirGraphWrapper { marci@556: typedef UndirGraphWrapper Parent; marci@556: protected: marci@556: Graph gr; marci@556: public: marci@556: UndirGraph() : UndirGraphWrapper() { marci@556: Parent::setGraph(gr); marci@556: } deba@877: deba@891: // KEEP_MAPS(Parent, UndirGraph); marci@556: }; marci@556: marci@992: marci@992: template marci@992: class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> { marci@992: public: marci@992: typedef _Graph Graph; marci@992: typedef GraphWrapperBase<_Graph> Parent; marci@992: protected: marci@992: ForwardFilterMap* forward_filter; marci@992: BackwardFilterMap* backward_filter; marci@992: SubBidirGraphWrapperBase() : Parent(), marci@992: forward_filter(0), backward_filter(0) { } marci@992: marci@992: void setForwardFilterMap(ForwardFilterMap& _forward_filter) { marci@992: forward_filter=&_forward_filter; marci@992: } marci@992: void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { marci@992: backward_filter=&_backward_filter; marci@992: } marci@992: marci@992: public: marci@992: // SubGraphWrapperBase(Graph& _graph, marci@992: // NodeFilterMap& _node_filter_map, marci@992: // EdgeFilterMap& _edge_filter_map) : marci@992: // Parent(&_graph), marci@992: // node_filter_map(&node_filter_map), marci@992: // edge_filter_map(&edge_filter_map) { } marci@992: marci@992: typedef typename Parent::Node Node; marci@992: typedef typename _Graph::Edge GraphEdge; marci@992: template class EdgeMap; marci@992: /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from marci@992: /// _Graph::Edge. It contains an extra bool flag which is true marci@992: /// if and only if the marci@992: /// edge is the backward version of the original edge. marci@992: class Edge : public _Graph::Edge { marci@992: friend class SubBidirGraphWrapperBase< marci@992: Graph, ForwardFilterMap, BackwardFilterMap>; marci@992: template friend class EdgeMap; marci@992: protected: marci@992: bool backward; //true, iff backward marci@992: public: marci@992: Edge() { } marci@992: /// \todo =false is needed, or causes problems? marci@992: /// If \c _backward is false, then we get an edge corresponding to the marci@992: /// original one, otherwise its oppositely directed pair is obtained. marci@992: Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : marci@992: _Graph::Edge(e), backward(_backward) { } marci@992: Edge(Invalid i) : _Graph::Edge(i), backward(true) { } marci@992: bool operator==(const Edge& v) const { marci@992: return (this->backward==v.backward && marci@992: static_cast(*this)== marci@992: static_cast(v)); marci@992: } marci@992: bool operator!=(const Edge& v) const { marci@992: return (this->backward!=v.backward || marci@992: static_cast(*this)!= marci@992: static_cast(v)); marci@992: } marci@992: }; marci@992: marci@992: void first(Node& i) const { marci@992: Parent::first(i); marci@992: } marci@992: marci@992: void first(Edge& i) const { marci@992: Parent::first(i); marci@992: i.backward=false; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*forward_filter)[i]) Parent::next(i); marci@992: if (*static_cast(&i)==INVALID) { marci@992: Parent::first(i); marci@992: i.backward=true; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::next(i); marci@992: } marci@992: } marci@992: marci@992: void firstIn(Edge& i, const Node& n) const { marci@992: Parent::firstIn(i, n); marci@992: i.backward=false; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*forward_filter)[i]) Parent::nextOut(i); marci@992: if (*static_cast(&i)==INVALID) { marci@992: Parent::firstOut(i, n); marci@992: i.backward=true; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::nextOut(i); marci@992: } marci@992: } marci@992: marci@992: void firstOut(Edge& i, const Node& n) const { marci@992: Parent::firstOut(i, n); marci@992: i.backward=false; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*forward_filter)[i]) Parent::nextOut(i); marci@992: if (*static_cast(&i)==INVALID) { marci@992: Parent::firstIn(i, n); marci@992: i.backward=true; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::nextIn(i); marci@992: } marci@992: } marci@992: marci@992: void next(Node& i) const { marci@992: Parent::next(i); marci@992: } marci@992: marci@992: void next(Edge& i) const { marci@992: if (!(i.backward)) { marci@992: Parent::next(i); marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*forward_filter)[i]) Parent::next(i); marci@992: if (*static_cast(&i)==INVALID) { marci@992: Parent::first(i); marci@992: i.backward=true; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::next(i); marci@992: } marci@992: } else { marci@992: Parent::next(i); marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::next(i); marci@992: } marci@992: } marci@992: marci@992: void nextIn(Edge& i) const { marci@992: if (!(i.backward)) { marci@992: Node n=Parent::target(i); marci@992: Parent::nextIn(i); marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*forward_filter)[i]) Parent::nextIn(i); marci@992: if (*static_cast(&i)==INVALID) { marci@992: Parent::firstOut(i, n); marci@992: i.backward=true; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::nextOut(i); marci@992: } marci@992: } else { marci@992: Parent::nextOut(i); marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::nextOut(i); marci@992: } marci@992: } marci@992: marci@992: void nextOut(Edge& i) const { marci@992: if (!(i.backward)) { marci@992: Node n=Parent::source(i); marci@992: Parent::nextOut(i); marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*forward_filter)[i]) Parent::nextOut(i); marci@992: if (*static_cast(&i)==INVALID) { marci@992: Parent::firstIn(i, n); marci@992: i.backward=true; marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::nextIn(i); marci@992: } marci@992: } else { marci@992: Parent::nextIn(i); marci@992: while (*static_cast(&i)!=INVALID && marci@992: !(*backward_filter)[i]) Parent::nextIn(i); marci@992: } marci@992: } marci@992: marci@992: Node source(Edge e) const { marci@992: return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); } marci@992: Node target(Edge e) const { marci@992: return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } marci@992: marci@992: /// Gives back the opposite edge. marci@992: Edge opposite(const Edge& e) const { marci@992: Edge f=e; marci@992: f.backward=!f.backward; marci@992: return f; marci@992: } marci@992: marci@992: /// \warning This is a linear time operation and works only if marci@992: /// \c Graph::EdgeIt is defined. marci@992: /// \todo hmm marci@992: int edgeNum() const { marci@992: int i=0; marci@992: Edge e; marci@992: for (first(e); e!=INVALID; next(e)) ++i; marci@992: return i; marci@992: } marci@992: marci@992: bool forward(const Edge& e) const { return !e.backward; } marci@992: bool backward(const Edge& e) const { return e.backward; } marci@992: marci@992: template marci@992: /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two marci@992: /// _Graph::EdgeMap one for the forward edges and marci@992: /// one for the backward edges. marci@992: class EdgeMap { marci@992: template friend class EdgeMap; marci@992: typename _Graph::template EdgeMap forward_map, backward_map; marci@992: public: marci@992: typedef T Value; marci@992: typedef Edge Key; marci@992: marci@992: EdgeMap(const SubBidirGraphWrapperBase<_Graph, marci@992: ForwardFilterMap, BackwardFilterMap>& g) : marci@992: forward_map(*(g.graph)), backward_map(*(g.graph)) { } marci@992: marci@992: EdgeMap(const SubBidirGraphWrapperBase<_Graph, marci@992: ForwardFilterMap, BackwardFilterMap>& g, T a) : marci@992: forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } marci@992: marci@992: void set(Edge e, T a) { marci@992: if (!e.backward) marci@992: forward_map.set(e, a); marci@992: else marci@992: backward_map.set(e, a); marci@992: } marci@992: marci@992: // typename _Graph::template EdgeMap::ConstReference marci@992: // operator[](Edge e) const { marci@992: // if (!e.backward) marci@992: // return forward_map[e]; marci@992: // else marci@992: // return backward_map[e]; marci@992: // } marci@992: marci@992: // typename _Graph::template EdgeMap::Reference marci@1016: T operator[](Edge e) const { marci@992: if (!e.backward) marci@992: return forward_map[e]; marci@992: else marci@992: return backward_map[e]; marci@992: } marci@992: marci@992: void update() { marci@992: forward_map.update(); marci@992: backward_map.update(); marci@992: } marci@992: }; marci@992: marci@992: }; marci@569: marci@650: marci@650: ///\brief A wrapper for composing a subgraph of a marci@792: /// bidirected graph made from a directed one. marci@612: /// alpar@911: /// A wrapper for composing a subgraph of a alpar@911: /// bidirected graph made from a directed one. alpar@911: /// alpar@879: ///\warning Graph wrappers are in even more experimental state than the other alpar@879: ///parts of the lib. Use them at you own risk. alpar@879: /// marci@923: /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge marci@923: /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by marci@923: /// reversing its orientation. We are given moreover two bool valued marci@923: /// maps on the edge-set, marci@923: /// \f$forward\_filter\f$, and \f$backward\_filter\f$. marci@923: /// SubBidirGraphWrapper implements the graph structure with node-set marci@923: /// \f$V\f$ and edge-set marci@923: /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$. marci@792: /// The purpose of writing + instead of union is because parallel marci@923: /// edges can arise. (Similarly, antiparallel edges also can arise). marci@792: /// In other words, a subgraph of the bidirected graph obtained, which marci@792: /// is given by orienting the edges of the original graph in both directions. marci@923: /// As the oppositely directed edges are logically different, marci@923: /// the maps are able to attach different values for them. marci@923: /// marci@923: /// An example for such a construction is \c RevGraphWrapper where the marci@792: /// forward_filter is everywhere false and the backward_filter is marci@792: /// everywhere true. We note that for sake of efficiency, marci@792: /// \c RevGraphWrapper is implemented in a different way. marci@792: /// But BidirGraphWrapper is obtained from marci@792: /// SubBidirGraphWrapper by considering everywhere true marci@910: /// valued maps both for forward_filter and backward_filter. marci@792: /// Finally, one of the most important applications of SubBidirGraphWrapper marci@792: /// is ResGraphWrapper, which stands for the residual graph in directed marci@792: /// flow and circulation problems. marci@792: /// As wrappers usually, the SubBidirGraphWrapper implements the marci@792: /// above mentioned graph structure without its physical storage, marci@923: /// that is the whole stuff is stored in constant memory. marci@992: template marci@992: class SubBidirGraphWrapper : marci@992: public IterableGraphExtender< marci@992: SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { marci@650: public: marci@992: typedef _Graph Graph; marci@992: typedef IterableGraphExtender< marci@992: SubBidirGraphWrapperBase< marci@992: _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; marci@569: protected: marci@992: SubBidirGraphWrapper() { } marci@992: public: marci@992: SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter, marci@992: BackwardFilterMap& _backward_filter) { marci@992: setGraph(_graph); marci@992: setForwardFilterMap(_forward_filter); marci@992: setBackwardFilterMap(_backward_filter); marci@992: } marci@992: }; marci@650: marci@569: marci@650: marci@650: ///\brief A wrapper for composing bidirected graph from a directed one. marci@650: /// alpar@879: ///\warning Graph wrappers are in even more experimental state than the other alpar@879: ///parts of the lib. Use them at you own risk. alpar@879: /// marci@650: /// A wrapper for composing bidirected graph from a directed one. marci@650: /// A bidirected graph is composed over the directed one without physical marci@650: /// storage. As the oppositely directed edges are logically different ones marci@650: /// the maps are able to attach different values for them. marci@650: template marci@650: class BidirGraphWrapper : marci@650: public SubBidirGraphWrapper< marci@650: Graph, marci@650: ConstMap, marci@650: ConstMap > { marci@650: public: marci@650: typedef SubBidirGraphWrapper< marci@650: Graph, marci@650: ConstMap, marci@650: ConstMap > Parent; marci@650: protected: marci@650: ConstMap cm; marci@650: marci@655: BidirGraphWrapper() : Parent(), cm(true) { marci@655: Parent::setForwardFilterMap(cm); marci@655: Parent::setBackwardFilterMap(cm); marci@655: } marci@650: public: marci@650: BidirGraphWrapper(Graph& _graph) : Parent() { marci@650: Parent::setGraph(_graph); marci@650: Parent::setForwardFilterMap(cm); marci@650: Parent::setBackwardFilterMap(cm); marci@650: } marci@738: marci@738: int edgeNum() const { marci@738: return 2*this->graph->edgeNum(); marci@738: } deba@891: // KEEP_MAPS(Parent, BidirGraphWrapper); marci@650: }; marci@650: marci@650: marci@612: /// \brief A bidirected graph template. marci@612: /// alpar@879: ///\warning Graph wrappers are in even more experimental state than the other alpar@879: ///parts of the lib. Use them at you own risk. alpar@879: /// marci@612: /// A bidirected graph template. marci@612: /// Such a bidirected graph stores each pair of oppositely directed edges marci@612: /// ones in the memory, i.e. a directed graph of type marci@612: /// \c Graph is used for that. marci@612: /// As the oppositely directed edges are logically different ones marci@612: /// the maps are able to attach different values for them. marci@612: /// \ingroup graphs marci@612: template marci@612: class BidirGraph : public BidirGraphWrapper { marci@650: public: marci@612: typedef UndirGraphWrapper Parent; marci@612: protected: marci@612: Graph gr; marci@612: public: marci@612: BidirGraph() : BidirGraphWrapper() { marci@612: Parent::setGraph(gr); marci@612: } deba@891: // KEEP_MAPS(Parent, BidirGraph); marci@612: }; marci@569: marci@556: marci@650: marci@650: template marci@658: class ResForwardFilter { marci@658: // const Graph* graph; marci@650: const CapacityMap* capacity; marci@650: const FlowMap* flow; marci@650: public: marci@658: ResForwardFilter(/*const Graph& _graph, */ marci@658: const CapacityMap& _capacity, const FlowMap& _flow) : marci@658: /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } marci@658: ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } marci@656: void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } marci@656: void setFlow(const FlowMap& _flow) { flow=&_flow; } marci@650: bool operator[](const typename Graph::Edge& e) const { marci@738: return (Number((*flow)[e]) < Number((*capacity)[e])); marci@650: } marci@650: }; marci@650: marci@650: template marci@658: class ResBackwardFilter { marci@650: const CapacityMap* capacity; marci@650: const FlowMap* flow; marci@650: public: marci@658: ResBackwardFilter(/*const Graph& _graph,*/ marci@658: const CapacityMap& _capacity, const FlowMap& _flow) : marci@658: /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } marci@658: ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } marci@656: void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } marci@656: void setFlow(const FlowMap& _flow) { flow=&_flow; } marci@650: bool operator[](const typename Graph::Edge& e) const { marci@738: return (Number(0) < Number((*flow)[e])); marci@650: } marci@650: }; marci@650: marci@653: marci@653: /// A wrapper for composing the residual graph for directed flow and circulation problems. marci@650: alpar@879: ///\warning Graph wrappers are in even more experimental state than the other alpar@879: ///parts of the lib. Use them at you own risk. alpar@879: /// marci@653: /// A wrapper for composing the residual graph for directed flow and circulation problems. marci@650: template marci@653: class ResGraphWrapper : marci@650: public SubBidirGraphWrapper< marci@650: Graph, marci@658: ResForwardFilter, marci@658: ResBackwardFilter > { marci@650: public: marci@650: typedef SubBidirGraphWrapper< marci@650: Graph, marci@658: ResForwardFilter, marci@658: ResBackwardFilter > Parent; marci@650: protected: marci@650: const CapacityMap* capacity; marci@650: FlowMap* flow; marci@658: ResForwardFilter forward_filter; marci@658: ResBackwardFilter backward_filter; marci@658: ResGraphWrapper() : Parent(), marci@658: capacity(0), flow(0) { } marci@658: void setCapacityMap(const CapacityMap& _capacity) { marci@658: capacity=&_capacity; marci@658: forward_filter.setCapacity(_capacity); marci@658: backward_filter.setCapacity(_capacity); marci@658: } marci@658: void setFlowMap(FlowMap& _flow) { marci@658: flow=&_flow; marci@658: forward_filter.setFlow(_flow); marci@658: backward_filter.setFlow(_flow); marci@658: } marci@650: public: marci@653: ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, marci@650: FlowMap& _flow) : marci@650: Parent(), capacity(&_capacity), flow(&_flow), marci@658: forward_filter(/*_graph,*/ _capacity, _flow), marci@658: backward_filter(/*_graph,*/ _capacity, _flow) { marci@650: Parent::setGraph(_graph); marci@650: Parent::setForwardFilterMap(forward_filter); marci@650: Parent::setBackwardFilterMap(backward_filter); marci@650: } marci@650: marci@660: typedef typename Parent::Edge Edge; marci@660: marci@660: void augment(const Edge& e, Number a) const { marci@650: if (Parent::forward(e)) marci@650: flow->set(e, (*flow)[e]+a); marci@650: else marci@650: flow->set(e, (*flow)[e]-a); marci@650: } marci@650: marci@660: /// \brief Residual capacity map. marci@660: /// marci@910: /// In generic residual graphs the residual capacity can be obtained marci@910: /// as a map. marci@660: class ResCap { marci@660: protected: marci@660: const ResGraphWrapper* res_graph; marci@660: public: alpar@987: typedef Number Value; alpar@987: typedef Edge Key; marci@888: ResCap(const ResGraphWrapper& marci@888: _res_graph) : res_graph(&_res_graph) { } marci@660: Number operator[](const Edge& e) const { marci@660: if (res_graph->forward(e)) marci@660: return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; marci@660: else marci@660: return (*(res_graph->flow))[e]; marci@660: } marci@660: }; marci@660: deba@891: // KEEP_MAPS(Parent, ResGraphWrapper); marci@650: }; marci@650: marci@650: marci@998: marci@998: template marci@998: class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> { marci@998: public: marci@998: typedef _Graph Graph; marci@998: typedef GraphWrapperBase<_Graph> Parent; marci@998: protected: marci@998: FirstOutEdgesMap* first_out_edges; marci@998: ErasingFirstGraphWrapperBase() : Parent(), marci@998: first_out_edges(0) { } marci@998: marci@998: void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) { marci@998: first_out_edges=&_first_out_edges; marci@998: } marci@998: marci@998: public: marci@998: marci@998: typedef typename Parent::Node Node; marci@998: typedef typename Parent::Edge Edge; marci@998: marci@998: void firstOut(Edge& i, const Node& n) const { marci@998: i=(*first_out_edges)[n]; marci@998: } marci@998: marci@998: void erase(const Edge& e) const { marci@998: Node n=source(e); marci@998: Edge f=e; marci@998: Parent::nextOut(f); marci@998: first_out_edges->set(n, f); marci@998: } marci@998: }; marci@998: marci@998: marci@612: /// For blocking flows. marci@556: alpar@879: ///\warning Graph wrappers are in even more experimental state than the other alpar@879: ///parts of the lib. Use them at you own risk. alpar@879: /// marci@792: /// This graph wrapper is used for on-the-fly marci@792: /// Dinits blocking flow computations. marci@612: /// For each node, an out-edge is stored which is used when the marci@612: /// \code marci@612: /// OutEdgeIt& first(OutEdgeIt&, const Node&) marci@612: /// \endcode marci@612: /// is called. marci@556: /// marci@792: /// \author Marton Makai marci@998: template marci@998: class ErasingFirstGraphWrapper : marci@998: public IterableGraphExtender< marci@998: ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > { marci@650: public: marci@998: typedef _Graph Graph; marci@998: typedef IterableGraphExtender< marci@998: ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent; marci@556: ErasingFirstGraphWrapper(Graph& _graph, marci@998: FirstOutEdgesMap& _first_out_edges) { marci@998: setGraph(_graph); marci@998: setFirstOutEdgesMap(_first_out_edges); marci@998: } marci@1019: marci@998: }; marci@556: marci@556: ///@} marci@556: alpar@921: } //namespace lemon marci@556: alpar@921: #endif //LEMON_GRAPH_WRAPPER_H marci@556: