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