alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, 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@1401: #ifndef LEMON_GRAPH_ADAPTOR_H alpar@1401: #define LEMON_GRAPH_ADAPTOR_H marci@556: alpar@1401: ///\ingroup graph_adaptors marci@556: ///\file alpar@1401: ///\brief Several graph adaptors. marci@556: /// alpar@1401: ///This file contains several useful graph adaptor functions. marci@556: /// marci@556: ///\author Marton Makai marci@556: alpar@921: #include alpar@921: #include deba@1472: #include deba@1472: #include deba@1472: #include deba@1307: #include deba@1472: #include deba@1472: #include deba@1791: #include alpar@774: #include marci@556: alpar@921: namespace lemon { marci@556: klao@1951: ///\brief Base type for the Graph Adaptors klao@1951: ///\ingroup graph_adaptors klao@1951: /// klao@1951: ///Base type for the Graph Adaptors klao@1951: /// klao@1951: ///\warning Graph adaptors are in even klao@1951: ///more experimental state than the other klao@1951: ///parts of the lib. Use them at you own risk. klao@1951: /// klao@1951: ///This is the base type for most of LEMON graph adaptors. klao@1951: ///This class implements a trivial graph adaptor i.e. it only wraps the klao@1951: ///functions and types of the graph. The purpose of this class is to klao@1951: ///make easier implementing graph adaptors. E.g. if an adaptor is klao@1951: ///considered which differs from the wrapped graph only in some of its klao@1951: ///functions or types, then it can be derived from GraphAdaptor, klao@1951: ///and only the klao@1951: ///differences should be implemented. klao@1951: /// klao@1951: ///author Marton Makai marci@970: template alpar@1401: class GraphAdaptorBase { marci@970: public: marci@970: typedef _Graph Graph; marci@970: typedef Graph ParentGraph; marci@970: marci@556: protected: marci@556: Graph* graph; alpar@1401: GraphAdaptorBase() : graph(0) { } marci@556: void setGraph(Graph& _graph) { graph=&_graph; } marci@556: marci@556: public: alpar@1401: GraphAdaptorBase(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: deba@1697: typedef NodeNumTagIndicator NodeNumTag; marci@556: int nodeNum() const { return graph->nodeNum(); } deba@1697: deba@1697: typedef EdgeNumTagIndicator EdgeNumTag; marci@556: int edgeNum() const { return graph->edgeNum(); } deba@1697: deba@1697: typedef FindEdgeTagIndicator FindEdgeTag; deba@1697: Edge findEdge(const Node& source, const Node& target, deba@1697: const Edge& prev = INVALID) { deba@1697: return graph->findEdge(source, target, prev); deba@1697: } marci@556: deba@1697: Node addNode() const { deba@1697: return Node(graph->addNode()); deba@1697: } deba@1697: alpar@986: Edge addEdge(const Node& source, const Node& target) const { deba@1697: return Edge(graph->addEdge(source, target)); deba@1697: } 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: 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: deba@1627: Edge oppositeNode(const Edge& e) const { deba@1627: return Edge(graph->opposite(e)); deba@1627: } 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; deba@1755: explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) deba@1755: : Parent(*gw.graph) { } alpar@1401: NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value) deba@1755: : 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; deba@1755: explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw) deba@1755: : Parent(*gw.graph) { } alpar@1401: EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value) deba@1755: : Parent(*gw.graph, value) { } marci@970: }; deba@877: marci@556: }; marci@556: marci@970: template alpar@1401: class GraphAdaptor : alpar@1401: public IterableGraphExtender > { marci@970: public: marci@970: typedef _Graph Graph; alpar@1401: typedef IterableGraphExtender > Parent; marci@970: protected: alpar@1401: GraphAdaptor() : Parent() { } marci@569: marci@970: public: deba@1755: explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); } marci@970: }; marci@569: marci@997: template alpar@1401: class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> { marci@997: public: marci@997: typedef _Graph Graph; alpar@1401: typedef GraphAdaptorBase<_Graph> Parent; marci@997: protected: alpar@1401: RevGraphAdaptorBase() : Parent() { } marci@997: public: marci@997: typedef typename Parent::Node Node; marci@997: typedef typename Parent::Edge Edge; marci@997: 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: 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: alpar@1949: ///\brief A graph adaptor which reverses the orientation of the edges. alpar@1949: ///\ingroup graph_adaptors alpar@1949: /// alpar@1949: ///\warning Graph adaptors are in even more experimental alpar@1949: ///state than the other alpar@879: ///parts of the lib. Use them at you own risk. alpar@879: /// alpar@1949: /// If \c g is defined as alpar@1946: ///\code marci@923: /// ListGraph g; alpar@1946: ///\endcode alpar@1949: /// then alpar@1946: ///\code alpar@1401: /// RevGraphAdaptor gw(g); alpar@1946: ///\endcode alpar@1949: ///implements the graph obtained from \c g by alpar@1949: /// reversing the orientation of its edges. alpar@1946: marci@997: template alpar@1401: class RevGraphAdaptor : alpar@1401: public IterableGraphExtender > { marci@650: public: marci@997: typedef _Graph Graph; marci@997: typedef IterableGraphExtender< alpar@1401: RevGraphAdaptorBase<_Graph> > Parent; marci@556: protected: alpar@1401: RevGraphAdaptor() { } marci@556: public: deba@1755: explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); } marci@997: }; marci@556: marci@992: deba@1681: template alpar@1401: class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> { marci@992: public: marci@992: typedef _Graph Graph; alpar@1401: typedef GraphAdaptorBase<_Graph> Parent; marci@992: protected: marci@992: NodeFilterMap* node_filter_map; marci@992: EdgeFilterMap* edge_filter_map; alpar@1401: SubGraphAdaptorBase() : 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: 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: } deba@1681: deba@1681: void first(Edge& i) const { deba@1681: Parent::first(i); deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i] deba@1681: || !(*node_filter_map)[Parent::source(i)] deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); deba@1681: } deba@1681: deba@1681: void firstIn(Edge& i, const Node& n) const { deba@1681: Parent::firstIn(i, n); deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i] deba@1681: || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); deba@1681: } deba@1681: deba@1681: void firstOut(Edge& i, const Node& n) const { deba@1681: Parent::firstOut(i, n); deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i] deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); deba@1681: } deba@1681: deba@1681: void next(Node& i) const { deba@1681: Parent::next(i); deba@1681: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); deba@1681: } deba@1681: deba@1681: void next(Edge& i) const { deba@1681: Parent::next(i); deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i] deba@1681: || !(*node_filter_map)[Parent::source(i)] deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); deba@1681: } deba@1681: deba@1681: void nextIn(Edge& i) const { deba@1681: Parent::nextIn(i); deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i] deba@1681: || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); deba@1681: } deba@1681: deba@1681: void nextOut(Edge& i) const { deba@1681: Parent::nextOut(i); deba@1681: while (i!=INVALID && (!(*edge_filter_map)[i] deba@1681: || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); deba@1681: } deba@1681: klao@1951: ///\e alpar@1949: klao@1951: /// This function hides \c n in the graph, i.e. the iteration klao@1951: /// jumps over it. This is done by simply setting the value of \c n klao@1951: /// to be false in the corresponding node-map. deba@1681: void hide(const Node& n) const { node_filter_map->set(n, false); } deba@1681: klao@1951: ///\e alpar@1949: klao@1951: /// This function hides \c e in the graph, i.e. the iteration klao@1951: /// jumps over it. This is done by simply setting the value of \c e klao@1951: /// to be false in the corresponding edge-map. deba@1681: void hide(const Edge& e) const { edge_filter_map->set(e, false); } deba@1681: klao@1951: ///\e alpar@1949: klao@1951: /// The value of \c n is set to be true in the node-map which stores klao@1951: /// hide information. If \c n was hidden previuosly, then it is shown klao@1951: /// again deba@1681: void unHide(const Node& n) const { node_filter_map->set(n, true); } deba@1681: klao@1951: ///\e alpar@1949: klao@1951: /// The value of \c e is set to be true in the edge-map which stores klao@1951: /// hide information. If \c e was hidden previuosly, then it is shown klao@1951: /// again deba@1681: void unHide(const Edge& e) const { edge_filter_map->set(e, true); } deba@1681: klao@1951: /// Returns true if \c n is hidden. alpar@1949: klao@1951: ///\e klao@1951: /// deba@1681: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } deba@1681: klao@1951: /// Returns true if \c n is hidden. alpar@1949: klao@1951: ///\e klao@1951: /// deba@1681: bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } deba@1681: deba@1697: typedef False NodeNumTag; deba@1697: typedef False EdgeNumTag; deba@1681: }; deba@1681: deba@1681: template deba@1681: class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> deba@1681: : public GraphAdaptorBase<_Graph> { deba@1681: public: deba@1681: typedef _Graph Graph; deba@1681: typedef GraphAdaptorBase<_Graph> Parent; deba@1681: protected: deba@1681: NodeFilterMap* node_filter_map; deba@1681: EdgeFilterMap* edge_filter_map; deba@1681: SubGraphAdaptorBase() : Parent(), deba@1681: node_filter_map(0), edge_filter_map(0) { } deba@1681: deba@1681: void setNodeFilterMap(NodeFilterMap& _node_filter_map) { deba@1681: node_filter_map=&_node_filter_map; deba@1681: } deba@1681: void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { deba@1681: edge_filter_map=&_edge_filter_map; deba@1681: } deba@1681: deba@1681: public: deba@1681: deba@1681: typedef typename Parent::Node Node; deba@1681: typedef typename Parent::Edge Edge; deba@1681: deba@1681: void first(Node& i) const { deba@1681: Parent::first(i); deba@1681: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); deba@1681: } deba@1681: 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: } deba@1681: 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: } deba@1681: 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: } deba@1681: 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: klao@1951: ///\e alpar@1949: klao@1951: /// This function hides \c n in the graph, i.e. the iteration klao@1951: /// jumps over it. This is done by simply setting the value of \c n klao@1951: /// to be false in the corresponding node-map. marci@992: void hide(const Node& n) const { node_filter_map->set(n, false); } marci@992: klao@1951: ///\e alpar@1949: klao@1951: /// This function hides \c e in the graph, i.e. the iteration klao@1951: /// jumps over it. This is done by simply setting the value of \c e klao@1951: /// to be false in the corresponding edge-map. marci@992: void hide(const Edge& e) const { edge_filter_map->set(e, false); } marci@992: klao@1951: ///\e alpar@1949: klao@1951: /// The value of \c n is set to be true in the node-map which stores klao@1951: /// hide information. If \c n was hidden previuosly, then it is shown klao@1951: /// again marci@992: void unHide(const Node& n) const { node_filter_map->set(n, true); } marci@992: klao@1951: ///\e alpar@1949: klao@1951: /// The value of \c e is set to be true in the edge-map which stores klao@1951: /// hide information. If \c e was hidden previuosly, then it is shown klao@1951: /// again marci@992: void unHide(const Edge& e) const { edge_filter_map->set(e, true); } marci@992: klao@1951: /// Returns true if \c n is hidden. alpar@1949: klao@1951: ///\e klao@1951: /// marci@992: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } marci@992: klao@1951: /// Returns true if \c n is hidden. alpar@1949: klao@1951: ///\e klao@1951: /// marci@992: bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } marci@992: deba@1697: typedef False NodeNumTag; deba@1697: typedef False EdgeNumTag; marci@992: }; marci@775: klao@1951: /// \brief A graph adaptor for hiding nodes and edges from a graph. klao@1951: /// \ingroup graph_adaptors klao@1951: /// klao@1951: /// \warning Graph adaptors are in even more experimental state than the klao@1951: /// other parts of the lib. Use them at you own risk. klao@1951: /// klao@1951: /// SubGraphAdaptor shows the graph with filtered node-set and klao@1951: /// edge-set. If the \c checked parameter is true then it filters the edgeset klao@1951: /// to do not get invalid edges without source or target. klao@1952: /// Let \f$ G=(V, A) \f$ be a directed graph klao@1951: /// and suppose that the graph instance \c g of type ListGraph klao@1952: /// implements \f$ G \f$. klao@1952: /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp. klao@1951: /// on the node-set and edge-set. klao@1951: /// SubGraphAdaptor<...>::NodeIt iterates klao@1952: /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and klao@1951: /// SubGraphAdaptor<...>::EdgeIt iterates klao@1952: /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly, klao@1951: /// SubGraphAdaptor<...>::OutEdgeIt and klao@1951: /// SubGraphAdaptor<...>::InEdgeIt iterates klao@1951: /// only on edges leaving and entering a specific node which have true value. klao@1951: /// klao@1951: /// If the \c checked template parameter is false then we have to note that klao@1951: /// the node-iterator cares only the filter on the node-set, and the klao@1951: /// edge-iterator cares only the filter on the edge-set. klao@1951: /// This way the edge-map klao@1951: /// should filter all edges which's source or target is filtered by the klao@1951: /// node-filter. alpar@1957: ///\code klao@1951: /// typedef ListGraph Graph; klao@1951: /// Graph g; klao@1951: /// typedef Graph::Node Node; klao@1951: /// typedef Graph::Edge Edge; klao@1951: /// Node u=g.addNode(); //node of id 0 klao@1951: /// Node v=g.addNode(); //node of id 1 klao@1951: /// Node e=g.addEdge(u, v); //edge of id 0 klao@1951: /// Node f=g.addEdge(v, u); //edge of id 1 klao@1951: /// Graph::NodeMap nm(g, true); klao@1951: /// nm.set(u, false); klao@1951: /// Graph::EdgeMap em(g, true); klao@1951: /// em.set(e, false); klao@1951: /// typedef SubGraphAdaptor, Graph::EdgeMap > SubGW; klao@1951: /// SubGW gw(g, nm, em); klao@1951: /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; klao@1951: /// std::cout << ":-)" << std::endl; klao@1951: /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; alpar@1957: ///\endcode klao@1951: /// The output of the above code is the following. alpar@1957: ///\code klao@1951: /// 1 klao@1951: /// :-) klao@1951: /// 1 alpar@1957: ///\endcode klao@1951: /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to klao@1951: /// \c Graph::Node that is why \c g.id(n) can be applied. klao@1951: /// klao@1951: /// For other examples see also the documentation of NodeSubGraphAdaptor and klao@1951: /// EdgeSubGraphAdaptor. klao@1951: /// klao@1951: /// \author Marton Makai marci@1242: marci@992: template alpar@1401: class SubGraphAdaptor : marci@992: public IterableGraphExtender< deba@1681: SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { marci@650: public: marci@992: typedef _Graph Graph; marci@992: typedef IterableGraphExtender< alpar@1401: SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; marci@556: protected: alpar@1401: SubGraphAdaptor() { } marci@992: public: alpar@1401: SubGraphAdaptor(_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: klao@1951: ///\brief An adaptor for hiding nodes from a graph. klao@1951: ///\ingroup graph_adaptors klao@1951: /// klao@1951: ///\warning Graph adaptors are in even more experimental state klao@1951: ///than the other klao@1951: ///parts of the lib. Use them at you own risk. klao@1951: /// klao@1951: ///An adaptor for hiding nodes from a graph. klao@1951: ///This adaptor specializes SubGraphAdaptor in the way that only klao@1951: ///the node-set klao@1951: ///can be filtered. In usual case the checked parameter is true, we get the klao@1951: ///induced subgraph. But if the checked parameter is false then we can only klao@1951: ///filter only isolated nodes. klao@1951: ///\author Marton Makai deba@1681: template alpar@1401: class NodeSubGraphAdaptor : alpar@1401: public SubGraphAdaptor, checked> { marci@933: public: alpar@1401: typedef SubGraphAdaptor > Parent; marci@933: protected: marci@933: ConstMap const_true_map; marci@933: public: alpar@1401: NodeSubGraphAdaptor(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: klao@1951: ///\brief An adaptor for hiding edges from a graph. klao@1951: /// klao@1951: ///\warning Graph adaptors are in even more experimental state klao@1951: ///than the other parts of the lib. Use them at you own risk. klao@1951: /// klao@1951: ///An adaptor for hiding edges from a graph. klao@1951: ///This adaptor specializes SubGraphAdaptor in the way that klao@1951: ///only the edge-set klao@1951: ///can be filtered. The usefulness of this adaptor is demonstrated in the klao@1951: ///problem of searching a maximum number of edge-disjoint shortest paths klao@1951: ///between klao@1951: ///two nodes \c s and \c t. Shortest here means being shortest w.r.t. klao@1951: ///non-negative edge-lengths. Note that klao@1951: ///the comprehension of the presented solution klao@1951: ///need's some elementary knowledge from combinatorial optimization. klao@1951: /// klao@1951: ///If a single shortest path is to be klao@1951: ///searched between \c s and \c t, then this can be done easily by klao@1951: ///applying the Dijkstra algorithm. What happens, if a maximum number of klao@1951: ///edge-disjoint shortest paths is to be computed. It can be proved that an klao@1951: ///edge can be in a shortest path if and only klao@1951: ///if it is tight with respect to klao@1951: ///the potential function computed by Dijkstra. klao@1951: ///Moreover, any path containing klao@1951: ///only such edges is a shortest one. klao@1951: ///Thus we have to compute a maximum number klao@1951: ///of edge-disjoint paths between \c s and \c t in klao@1951: ///the graph which has edge-set klao@1951: ///all the tight edges. The computation will be demonstrated klao@1951: ///on the following klao@1951: ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. klao@1951: ///The full source code is available in \ref sub_graph_adaptor_demo.cc. klao@1951: ///If you are interested in more demo programs, you can use klao@1951: ///\ref dim_to_dot.cc to generate .dot files from dimacs files. klao@1951: ///The .dot file of the following figure was generated by klao@1951: ///the demo program \ref dim_to_dot.cc. klao@1951: /// klao@1951: ///\dot klao@1951: ///digraph lemon_dot_example { klao@1951: ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; klao@1951: ///n0 [ label="0 (s)" ]; klao@1951: ///n1 [ label="1" ]; klao@1951: ///n2 [ label="2" ]; klao@1951: ///n3 [ label="3" ]; klao@1951: ///n4 [ label="4" ]; klao@1951: ///n5 [ label="5" ]; klao@1951: ///n6 [ label="6 (t)" ]; klao@1951: ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; klao@1951: ///n5 -> n6 [ label="9, length:4" ]; klao@1951: ///n4 -> n6 [ label="8, length:2" ]; klao@1951: ///n3 -> n5 [ label="7, length:1" ]; klao@1951: ///n2 -> n5 [ label="6, length:3" ]; klao@1951: ///n2 -> n6 [ label="5, length:5" ]; klao@1951: ///n2 -> n4 [ label="4, length:2" ]; klao@1951: ///n1 -> n4 [ label="3, length:3" ]; klao@1951: ///n0 -> n3 [ label="2, length:1" ]; klao@1951: ///n0 -> n2 [ label="1, length:2" ]; klao@1951: ///n0 -> n1 [ label="0, length:3" ]; klao@1951: ///} klao@1951: ///\enddot klao@1951: /// klao@1951: ///\code klao@1951: ///Graph g; klao@1951: ///Node s, t; klao@1951: ///LengthMap length(g); klao@1951: /// klao@1951: ///readDimacs(std::cin, g, length, s, t); klao@1951: /// klao@1951: ///cout << "edges with lengths (of form id, source--length->target): " << endl; klao@1951: ///for(EdgeIt e(g); e!=INVALID; ++e) klao@1951: /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--" klao@1951: /// << length[e] << "->" << g.id(g.target(e)) << endl; klao@1951: /// klao@1951: ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; klao@1951: ///\endcode klao@1951: ///Next, the potential function is computed with Dijkstra. klao@1951: ///\code klao@1951: ///typedef Dijkstra Dijkstra; klao@1951: ///Dijkstra dijkstra(g, length); klao@1951: ///dijkstra.run(s); klao@1951: ///\endcode klao@1951: ///Next, we consrtruct a map which filters the edge-set to the tight edges. klao@1951: ///\code klao@1951: ///typedef TightEdgeFilterMap klao@1951: /// TightEdgeFilter; klao@1951: ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); klao@1951: /// klao@1951: ///typedef EdgeSubGraphAdaptor SubGW; klao@1951: ///SubGW gw(g, tight_edge_filter); klao@1951: ///\endcode klao@1951: ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed klao@1951: ///with a max flow algorithm Preflow. klao@1951: ///\code klao@1951: ///ConstMap const_1_map(1); klao@1951: ///Graph::EdgeMap flow(g, 0); klao@1951: /// klao@1951: ///Preflow, Graph::EdgeMap > klao@1951: /// preflow(gw, s, t, const_1_map, flow); klao@1951: ///preflow.run(); klao@1951: ///\endcode klao@1951: ///Last, the output is: klao@1951: ///\code klao@1951: ///cout << "maximum number of edge-disjoint shortest path: " klao@1951: /// << preflow.flowValue() << endl; klao@1951: ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " klao@1951: /// << endl; klao@1951: ///for(EdgeIt e(g); e!=INVALID; ++e) klao@1951: /// if (flow[e]) klao@1951: /// cout << " " << g.id(g.source(e)) << "--" klao@1951: /// << length[e] << "->" << g.id(g.target(e)) << endl; klao@1951: ///\endcode klao@1951: ///The program has the following (expected :-)) output: klao@1951: ///\code klao@1951: ///edges with lengths (of form id, source--length->target): klao@1951: /// 9, 5--4->6 klao@1951: /// 8, 4--2->6 klao@1951: /// 7, 3--1->5 klao@1951: /// 6, 2--3->5 klao@1951: /// 5, 2--5->6 klao@1951: /// 4, 2--2->4 klao@1951: /// 3, 1--3->4 klao@1951: /// 2, 0--1->3 klao@1951: /// 1, 0--2->2 klao@1951: /// 0, 0--3->1 klao@1951: ///s: 0 t: 6 klao@1951: ///maximum number of edge-disjoint shortest path: 2 klao@1951: ///edges of the maximum number of edge-disjoint shortest s-t paths: klao@1951: /// 9, 5--4->6 klao@1951: /// 8, 4--2->6 klao@1951: /// 7, 3--1->5 klao@1951: /// 4, 2--2->4 klao@1951: /// 2, 0--1->3 klao@1951: /// 1, 0--2->2 klao@1951: ///\endcode klao@1951: /// klao@1951: ///\author Marton Makai marci@932: template alpar@1401: class EdgeSubGraphAdaptor : alpar@1401: public SubGraphAdaptor, deba@1681: EdgeFilterMap, false> { marci@932: public: alpar@1401: typedef SubGraphAdaptor, deba@1685: EdgeFilterMap, false> Parent; marci@932: protected: marci@932: ConstMap const_true_map; marci@932: public: alpar@1401: EdgeSubGraphAdaptor(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@1383: template klao@1909: class UGraphAdaptorBase : klao@1909: public UGraphExtender > { marci@1383: public: marci@1383: typedef _Graph Graph; klao@1909: typedef UGraphExtender > Parent; marci@1383: protected: klao@1909: UGraphAdaptorBase() : Parent() { } marci@1383: public: klao@1909: typedef typename Parent::UEdge UEdge; marci@1383: typedef typename Parent::Edge Edge; marci@1383: marci@1383: template marci@1383: class EdgeMap { marci@1383: protected: klao@1909: const UGraphAdaptorBase<_Graph>* g; marci@1383: template friend class EdgeMap; marci@1383: typename _Graph::template EdgeMap forward_map, backward_map; marci@1383: public: marci@1383: typedef T Value; marci@1383: typedef Edge Key; marci@1383: klao@1909: EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g), marci@1383: forward_map(*(g->graph)), backward_map(*(g->graph)) { } marci@569: klao@1909: EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), marci@1383: forward_map(*(g->graph), a), backward_map(*(g->graph), a) { } marci@1383: marci@1383: void set(Edge e, T a) { deba@1627: if (g->direction(e)) marci@1383: forward_map.set(e, a); marci@1383: else marci@1383: backward_map.set(e, a); marci@1383: } marci@556: marci@1383: T operator[](Edge e) const { deba@1627: if (g->direction(e)) marci@1383: return forward_map[e]; marci@1383: else marci@1383: return backward_map[e]; marci@556: } marci@556: }; marci@1383: marci@1383: template klao@1909: class UEdgeMap { klao@1909: template friend class UEdgeMap; marci@1383: typename _Graph::template EdgeMap map; marci@1383: public: marci@1383: typedef T Value; klao@1909: typedef UEdge Key; marci@1383: klao@1909: UEdgeMap(const UGraphAdaptorBase<_Graph>& g) : marci@1383: map(*(g.graph)) { } marci@556: klao@1909: UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) : marci@1383: map(*(g.graph), a) { } marci@1383: klao@1909: void set(UEdge e, T a) { marci@1383: map.set(e, a); marci@1383: } marci@556: klao@1909: T operator[](UEdge e) const { marci@1383: return map[e]; marci@1383: } marci@1383: }; marci@1383: marci@1383: }; marci@1383: klao@1951: ///\brief An undirected graph is made from a directed graph by an adaptor klao@1951: ///\ingroup graph_adaptors klao@1951: /// klao@1951: /// Undocumented, untested!!! klao@1951: /// If somebody knows nice demo application, let's polulate it. klao@1951: /// klao@1951: /// \author Marton Makai marci@1383: template klao@1909: class UGraphAdaptor : klao@1909: public IterableUGraphExtender< klao@1909: UGraphAdaptorBase<_Graph> > { marci@1383: public: marci@1383: typedef _Graph Graph; klao@1909: typedef IterableUGraphExtender< klao@1909: UGraphAdaptorBase<_Graph> > Parent; marci@1383: protected: klao@1909: UGraphAdaptor() { } marci@1383: public: klao@1909: UGraphAdaptor(_Graph& _graph) { marci@1383: setGraph(_graph); marci@556: } marci@556: }; marci@556: marci@992: marci@992: template alpar@1401: class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> { marci@992: public: marci@992: typedef _Graph Graph; alpar@1401: typedef GraphAdaptorBase<_Graph> Parent; marci@992: protected: marci@992: ForwardFilterMap* forward_filter; marci@992: BackwardFilterMap* backward_filter; alpar@1401: SubBidirGraphAdaptorBase() : 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: alpar@1401: // SubGraphAdaptorBase(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; alpar@1949: // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from alpar@1949: // _Graph::Edge. It contains an extra bool flag which is true alpar@1949: // if and only if the alpar@1949: // edge is the backward version of the original edge. marci@992: class Edge : public _Graph::Edge { alpar@1401: friend class SubBidirGraphAdaptorBase< 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() { } alpar@1949: // \todo =false is needed, or causes problems? alpar@1949: // If \c _backward is false, then we get an edge corresponding to the alpar@1949: // 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@1269: !(*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: } 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: klao@1951: /// Gives back the opposite edge. alpar@1949: klao@1951: ///\e klao@1951: /// 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: klao@1951: ///\e alpar@1949: klao@1951: /// \warning This is a linear time operation and works only if klao@1951: /// \c Graph::EdgeIt is defined. klao@1951: /// \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: klao@1951: ///\e alpar@1949: klao@1951: /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two klao@1951: /// _Graph::EdgeMap one for the forward edges and klao@1951: /// one for the backward edges. marci@992: template 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: alpar@1401: EdgeMap(const SubBidirGraphAdaptorBase<_Graph, marci@992: ForwardFilterMap, BackwardFilterMap>& g) : marci@992: forward_map(*(g.graph)), backward_map(*(g.graph)) { } marci@992: alpar@1401: EdgeMap(const SubBidirGraphAdaptorBase<_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: klao@1951: ///\brief An adaptor for composing a subgraph of a klao@1951: /// bidirected graph made from a directed one. klao@1951: ///\ingroup graph_adaptors klao@1951: /// klao@1951: /// An adaptor for composing a subgraph of a klao@1951: /// bidirected graph made from a directed one. klao@1951: /// klao@1951: ///\warning Graph adaptors are in even more experimental state klao@1951: ///than the other klao@1951: ///parts of the lib. Use them at you own risk. klao@1951: /// klao@1952: /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge klao@1952: ///\f$ e\in A \f$, let \f$ \bar e \f$ denote the edge obtained by klao@1951: /// reversing its orientation. We are given moreover two bool valued klao@1951: /// maps on the edge-set, klao@1952: ///\f$ forward\_filter \f$, and \f$ backward\_filter \f$. klao@1951: /// SubBidirGraphAdaptor implements the graph structure with node-set klao@1952: ///\f$ V \f$ and edge-set klao@1952: ///\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$. klao@1951: /// The purpose of writing + instead of union is because parallel klao@1951: /// edges can arise. (Similarly, antiparallel edges also can arise). klao@1951: /// In other words, a subgraph of the bidirected graph obtained, which klao@1951: /// is given by orienting the edges of the original graph in both directions. klao@1951: /// As the oppositely directed edges are logically different, klao@1951: /// the maps are able to attach different values for them. klao@1951: /// klao@1951: /// An example for such a construction is \c RevGraphAdaptor where the klao@1951: /// forward_filter is everywhere false and the backward_filter is klao@1951: /// everywhere true. We note that for sake of efficiency, klao@1951: /// \c RevGraphAdaptor is implemented in a different way. klao@1951: /// But BidirGraphAdaptor is obtained from klao@1951: /// SubBidirGraphAdaptor by considering everywhere true klao@1951: /// valued maps both for forward_filter and backward_filter. klao@1951: /// klao@1951: /// The most important application of SubBidirGraphAdaptor klao@1951: /// is ResGraphAdaptor, which stands for the residual graph in directed klao@1951: /// flow and circulation problems. klao@1951: /// As adaptors usually, the SubBidirGraphAdaptor implements the klao@1951: /// above mentioned graph structure without its physical storage, klao@1951: /// that is the whole stuff is stored in constant memory. marci@992: template alpar@1401: class SubBidirGraphAdaptor : marci@992: public IterableGraphExtender< alpar@1401: SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { marci@650: public: marci@992: typedef _Graph Graph; marci@992: typedef IterableGraphExtender< alpar@1401: SubBidirGraphAdaptorBase< marci@992: _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; marci@569: protected: alpar@1401: SubBidirGraphAdaptor() { } marci@992: public: alpar@1401: SubBidirGraphAdaptor(_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: klao@1951: ///\brief An adaptor for composing bidirected graph from a directed one. klao@1951: ///\ingroup graph_adaptors klao@1951: /// klao@1951: ///\warning Graph adaptors are in even more experimental state klao@1951: ///than the other klao@1951: ///parts of the lib. Use them at you own risk. klao@1951: /// klao@1951: /// An adaptor for composing bidirected graph from a directed one. klao@1951: /// A bidirected graph is composed over the directed one without physical klao@1951: /// storage. As the oppositely directed edges are logically different ones klao@1951: /// the maps are able to attach different values for them. marci@650: template alpar@1401: class BidirGraphAdaptor : alpar@1401: public SubBidirGraphAdaptor< marci@650: Graph, marci@650: ConstMap, marci@650: ConstMap > { marci@650: public: alpar@1401: typedef SubBidirGraphAdaptor< marci@650: Graph, marci@650: ConstMap, marci@650: ConstMap > Parent; marci@650: protected: marci@650: ConstMap cm; marci@650: alpar@1401: BidirGraphAdaptor() : Parent(), cm(true) { marci@655: Parent::setForwardFilterMap(cm); marci@655: Parent::setBackwardFilterMap(cm); marci@655: } marci@650: public: alpar@1401: BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { 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: } marci@650: }; marci@650: 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: klao@1951: ///\brief An adaptor for composing the residual klao@1951: ///graph for directed flow and circulation problems. klao@1951: ///\ingroup graph_adaptors klao@1951: /// klao@1951: ///An adaptor for composing the residual graph for klao@1951: ///directed flow and circulation problems. klao@1952: ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a klao@1951: ///number type. Let moreover klao@1952: ///\f$ f,c:A\to F \f$, be functions on the edge-set. klao@1952: ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a flow klao@1952: ///and \f$ c \f$ for a capacity function. klao@1951: ///Suppose that a graph instange \c g of type klao@1952: ///\c ListGraph implements \f$ G \f$. klao@1951: ///\code klao@1951: /// ListGraph g; klao@1951: ///\endcode klao@1951: ///Then RevGraphAdaptor implements the graph structure with node-set klao@1952: ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where klao@1952: ///\f$ A_{forward}=\{uv : uv\in A, f(uv)0\} \f$, klao@1951: ///i.e. the so called residual graph. klao@1952: ///When we take the union \f$ A_{forward}\cup A_{backward} \f$, klao@1951: ///multilicities are counted, i.e. if an edge is in both klao@1952: ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it klao@1951: ///appears twice. klao@1951: ///The following code shows how klao@1951: ///such an instance can be constructed. klao@1951: ///\code klao@1951: ///typedef ListGraph Graph; klao@1951: ///Graph::EdgeMap f(g); klao@1951: ///Graph::EdgeMap c(g); klao@1951: ///ResGraphAdaptor, Graph::EdgeMap > gw(g); klao@1951: ///\endcode klao@1951: ///\author Marton Makai klao@1951: /// marci@650: template alpar@1401: class ResGraphAdaptor : alpar@1401: public SubBidirGraphAdaptor< marci@650: Graph, marci@658: ResForwardFilter, marci@658: ResBackwardFilter > { marci@650: public: alpar@1401: typedef SubBidirGraphAdaptor< 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; alpar@1401: ResGraphAdaptor() : 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: alpar@1401: ResGraphAdaptor(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: klao@1951: /// \brief Residual capacity map. klao@1951: /// klao@1951: /// In generic residual graphs the residual capacity can be obtained klao@1951: /// as a map. marci@660: class ResCap { marci@660: protected: alpar@1401: const ResGraphAdaptor* res_graph; marci@660: public: alpar@987: typedef Number Value; alpar@987: typedef Edge Key; alpar@1401: ResCap(const ResGraphAdaptor& 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: alpar@1401: // KEEP_MAPS(Parent, ResGraphAdaptor); marci@650: }; marci@650: marci@650: marci@998: marci@998: template alpar@1401: class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> { marci@998: public: marci@998: typedef _Graph Graph; alpar@1401: typedef GraphAdaptorBase<_Graph> Parent; marci@998: protected: marci@998: FirstOutEdgesMap* first_out_edges; alpar@1401: ErasingFirstGraphAdaptorBase() : 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: klao@1951: ///\brief For blocking flows. klao@1951: ///\ingroup graph_adaptors klao@1951: /// klao@1951: ///\warning Graph adaptors are in even more klao@1951: ///experimental state than the other klao@1951: ///parts of the lib. Use them at you own risk. klao@1951: /// klao@1951: ///This graph adaptor is used for on-the-fly klao@1951: ///Dinits blocking flow computations. klao@1951: ///For each node, an out-edge is stored which is used when the klao@1951: ///\code klao@1951: ///OutEdgeIt& first(OutEdgeIt&, const Node&) klao@1951: ///\endcode klao@1951: ///is called. klao@1951: /// klao@1951: ///\author Marton Makai klao@1951: /// marci@998: template alpar@1401: class ErasingFirstGraphAdaptor : marci@998: public IterableGraphExtender< alpar@1401: ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > { marci@650: public: marci@998: typedef _Graph Graph; marci@998: typedef IterableGraphExtender< alpar@1401: ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent; alpar@1401: ErasingFirstGraphAdaptor(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: deba@1472: template deba@1697: class SplitGraphAdaptorBase deba@1697: : public GraphAdaptorBase<_Graph> { deba@1697: public: deba@1697: typedef GraphAdaptorBase<_Graph> Parent; deba@1697: deba@1697: class Node; deba@1697: class Edge; deba@1697: template class NodeMap; deba@1697: template class EdgeMap; deba@1697: deba@1697: deba@1697: class Node : public Parent::Node { deba@1697: friend class SplitGraphAdaptorBase; deba@1697: template friend class NodeMap; deba@1697: typedef typename Parent::Node NodeParent; deba@1697: private: deba@1697: deba@1697: bool entry; deba@1697: Node(typename Parent::Node _node, bool _entry) deba@1697: : Parent::Node(_node), entry(_entry) {} deba@1697: deba@1697: public: deba@1697: Node() {} deba@1697: Node(Invalid) : NodeParent(INVALID), entry(true) {} deba@1697: deba@1697: bool operator==(const Node& node) const { deba@1697: return NodeParent::operator==(node) && entry == node.entry; deba@1697: } deba@1697: deba@1697: bool operator!=(const Node& node) const { deba@1697: return !(*this == node); deba@1697: } deba@1697: deba@1697: bool operator<(const Node& node) const { deba@1697: return NodeParent::operator<(node) || deba@1697: (NodeParent::operator==(node) && entry < node.entry); deba@1697: } deba@1697: }; deba@1697: klao@1951: /// \todo May we want VARIANT/union type deba@1697: class Edge : public Parent::Edge { deba@1697: friend class SplitGraphAdaptorBase; deba@1697: template friend class EdgeMap; deba@1697: private: deba@1697: typedef typename Parent::Edge EdgeParent; deba@1697: typedef typename Parent::Node NodeParent; deba@1697: NodeParent bind; deba@1697: deba@1697: Edge(const EdgeParent& edge, const NodeParent& node) deba@1697: : EdgeParent(edge), bind(node) {} deba@1697: public: deba@1697: Edge() {} deba@1697: Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {} deba@1697: deba@1697: bool operator==(const Edge& edge) const { deba@1697: return EdgeParent::operator==(edge) && bind == edge.bind; deba@1697: } deba@1697: deba@1697: bool operator!=(const Edge& edge) const { deba@1697: return !(*this == edge); deba@1697: } deba@1697: deba@1697: bool operator<(const Edge& edge) const { deba@1697: return EdgeParent::operator<(edge) || deba@1697: (EdgeParent::operator==(edge) && bind < edge.bind); deba@1697: } deba@1697: }; deba@1697: deba@1697: void first(Node& node) const { deba@1697: Parent::first(node); deba@1697: node.entry = true; deba@1697: } deba@1697: deba@1697: void next(Node& node) const { deba@1697: if (node.entry) { deba@1697: node.entry = false; deba@1697: } else { deba@1697: node.entry = true; deba@1697: Parent::next(node); deba@1697: } deba@1697: } deba@1697: deba@1697: void first(Edge& edge) const { deba@1697: Parent::first(edge); deba@1697: if ((typename Parent::Edge&)edge == INVALID) { deba@1697: Parent::first(edge.bind); deba@1697: } else { deba@1697: edge.bind = INVALID; deba@1697: } deba@1697: } deba@1697: deba@1697: void next(Edge& edge) const { deba@1697: if ((typename Parent::Edge&)edge != INVALID) { deba@1697: Parent::next(edge); deba@1697: if ((typename Parent::Edge&)edge == INVALID) { deba@1697: Parent::first(edge.bind); deba@1697: } deba@1697: } else { deba@1697: Parent::next(edge.bind); deba@1697: } deba@1697: } deba@1697: deba@1697: void firstIn(Edge& edge, const Node& node) const { deba@1697: if (node.entry) { deba@1697: Parent::firstIn(edge, node); deba@1697: edge.bind = INVALID; deba@1697: } else { deba@1697: (typename Parent::Edge&)edge = INVALID; deba@1697: edge.bind = node; deba@1697: } deba@1697: } deba@1697: deba@1697: void nextIn(Edge& edge) const { deba@1697: if ((typename Parent::Edge&)edge != INVALID) { deba@1697: Parent::nextIn(edge); deba@1697: } else { deba@1697: edge.bind = INVALID; deba@1697: } deba@1697: } deba@1697: deba@1697: void firstOut(Edge& edge, const Node& node) const { deba@1697: if (!node.entry) { deba@1697: Parent::firstOut(edge, node); deba@1697: edge.bind = INVALID; deba@1697: } else { deba@1697: (typename Parent::Edge&)edge = INVALID; deba@1697: edge.bind = node; deba@1697: } deba@1697: } deba@1697: deba@1697: void nextOut(Edge& edge) const { deba@1697: if ((typename Parent::Edge&)edge != INVALID) { deba@1697: Parent::nextOut(edge); deba@1697: } else { deba@1697: edge.bind = INVALID; deba@1697: } deba@1697: } deba@1697: deba@1697: Node source(const Edge& edge) const { deba@1697: if ((typename Parent::Edge&)edge != INVALID) { deba@1697: return Node(Parent::source(edge), false); deba@1697: } else { deba@1697: return Node(edge.bind, true); deba@1697: } deba@1697: } deba@1697: deba@1697: Node target(const Edge& edge) const { deba@1697: if ((typename Parent::Edge&)edge != INVALID) { deba@1697: return Node(Parent::target(edge), true); deba@1697: } else { deba@1697: return Node(edge.bind, false); deba@1697: } deba@1697: } deba@1697: deba@1697: static bool entryNode(const Node& node) { deba@1697: return node.entry; deba@1697: } deba@1697: deba@1697: static bool exitNode(const Node& node) { deba@1697: return !node.entry; deba@1697: } deba@1697: deba@1697: static Node getEntry(const typename Parent::Node& node) { deba@1697: return Node(node, true); deba@1697: } deba@1697: deba@1697: static Node getExit(const typename Parent::Node& node) { deba@1697: return Node(node, false); deba@1697: } deba@1697: deba@1697: static bool originalEdge(const Edge& edge) { deba@1697: return (typename Parent::Edge&)edge != INVALID; deba@1697: } deba@1697: deba@1697: static bool bindingEdge(const Edge& edge) { deba@1697: return edge.bind != INVALID; deba@1697: } deba@1697: deba@1697: static Node getBindedNode(const Edge& edge) { deba@1697: return edge.bind; deba@1697: } deba@1697: deba@1697: int nodeNum() const { deba@1697: return Parent::nodeNum() * 2; deba@1697: } deba@1697: deba@1697: typedef CompileTimeAnd EdgeNumTag; deba@1697: deba@1697: int edgeNum() const { deba@1697: return Parent::edgeNum() + Parent::nodeNum(); deba@1697: } deba@1697: deba@1697: Edge findEdge(const Node& source, const Node& target, deba@1697: const Edge& prev = INVALID) const { deba@1697: if (exitNode(source) && entryNode(target)) { deba@1697: return Parent::findEdge(source, target, prev); deba@1697: } else { deba@1697: if (prev == INVALID && entryNode(source) && exitNode(target) && deba@1697: (typename Parent::Node&)source == (typename Parent::Node&)target) { deba@1697: return Edge(INVALID, source); deba@1697: } else { deba@1697: return INVALID; deba@1697: } deba@1697: } deba@1697: } deba@1697: deba@1697: template deba@1697: class NodeMap : public MapBase { deba@1697: typedef typename Parent::template NodeMap NodeImpl; deba@1697: public: deba@1697: NodeMap(const SplitGraphAdaptorBase& _graph) deba@1697: : entry(_graph), exit(_graph) {} deba@1697: NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) deba@1697: : entry(_graph, t), exit(_graph, t) {} deba@1697: deba@1697: void set(const Node& key, const T& val) { deba@1697: if (key.entry) { entry.set(key, val); } deba@1697: else {exit.set(key, val); } deba@1697: } deba@1697: deba@1725: typename MapTraits::ReturnValue deba@1697: operator[](const Node& key) { deba@1697: if (key.entry) { return entry[key]; } deba@1697: else { return exit[key]; } deba@1697: } deba@1697: deba@1725: typename MapTraits::ConstReturnValue deba@1725: operator[](const Node& key) const { deba@1697: if (key.entry) { return entry[key]; } deba@1697: else { return exit[key]; } deba@1697: } deba@1697: deba@1697: private: deba@1697: NodeImpl entry, exit; deba@1697: }; deba@1697: deba@1697: template deba@1697: class EdgeMap : public MapBase { deba@1697: typedef typename Parent::template NodeMap NodeImpl; deba@1697: typedef typename Parent::template EdgeMap EdgeImpl; deba@1697: public: deba@1697: EdgeMap(const SplitGraphAdaptorBase& _graph) deba@1697: : bind(_graph), orig(_graph) {} deba@1697: EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) deba@1697: : bind(_graph, t), orig(_graph, t) {} deba@1697: deba@1697: void set(const Edge& key, const T& val) { deba@1697: if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); } deba@1697: else {bind.set(key.bind, val); } deba@1697: } deba@1697: deba@1725: typename MapTraits::ReturnValue deba@1697: operator[](const Edge& key) { deba@1697: if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } deba@1697: else {return bind[key.bind]; } deba@1697: } deba@1697: deba@1725: typename MapTraits::ConstReturnValue deba@1725: operator[](const Edge& key) const { deba@1697: if ((typename Parent::Edge&)key != INVALID) { return orig[key]; } deba@1697: else {return bind[key.bind]; } deba@1697: } deba@1697: deba@1697: private: deba@1697: typename Parent::template NodeMap bind; deba@1697: typename Parent::template EdgeMap orig; deba@1697: }; deba@1697: deba@1697: template deba@1697: class CombinedNodeMap : public MapBase { deba@1697: public: deba@1697: typedef MapBase Parent; deba@1697: deba@1697: typedef typename Parent::Key Key; deba@1697: typedef typename Parent::Value Value; deba@1697: deba@1697: CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) deba@1697: : entryMap(_entryMap), exitMap(_exitMap) {} deba@1697: deba@1697: Value& operator[](const Key& key) { deba@1697: if (key.entry) { deba@1697: return entryMap[key]; deba@1697: } else { deba@1697: return exitMap[key]; deba@1697: } deba@1697: } deba@1697: deba@1697: Value operator[](const Key& key) const { deba@1697: if (key.entry) { deba@1697: return entryMap[key]; deba@1697: } else { deba@1697: return exitMap[key]; deba@1697: } deba@1697: } deba@1697: deba@1697: void set(const Key& key, const Value& value) { deba@1697: if (key.entry) { deba@1697: entryMap.set(key, value); deba@1697: } else { deba@1697: exitMap.set(key, value); deba@1697: } deba@1697: } deba@1697: deba@1697: private: deba@1697: deba@1697: EntryMap& entryMap; deba@1697: ExitMap& exitMap; deba@1697: deba@1697: }; deba@1697: deba@1697: template deba@1697: class CombinedEdgeMap : public MapBase { deba@1697: public: deba@1697: typedef MapBase Parent; deba@1697: deba@1697: typedef typename Parent::Key Key; deba@1697: typedef typename Parent::Value Value; deba@1697: deba@1697: CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) deba@1697: : edgeMap(_edgeMap), nodeMap(_nodeMap) {} deba@1697: deba@1697: void set(const Edge& edge, const Value& val) { deba@1697: if (SplitGraphAdaptorBase::originalEdge(edge)) { deba@1697: edgeMap.set(edge, val); deba@1697: } else { deba@1697: nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val); deba@1697: } deba@1697: } deba@1697: deba@1697: Value operator[](const Key& edge) const { deba@1697: if (SplitGraphAdaptorBase::originalEdge(edge)) { deba@1697: return edgeMap[edge]; deba@1697: } else { deba@1697: return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; deba@1697: } deba@1697: } deba@1697: deba@1697: Value& operator[](const Key& edge) { deba@1697: if (SplitGraphAdaptorBase::originalEdge(edge)) { deba@1697: return edgeMap[edge]; deba@1697: } else { deba@1697: return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)]; deba@1697: } deba@1697: } deba@1697: deba@1697: private: deba@1697: EdgeMap& edgeMap; deba@1697: NodeMap& nodeMap; deba@1697: }; deba@1697: deba@1697: }; deba@1697: deba@1697: template deba@1697: class SplitGraphAdaptor deba@1697: : public IterableGraphExtender > { deba@1697: public: deba@1697: typedef IterableGraphExtender > Parent; deba@1697: deba@1697: SplitGraphAdaptor(_Graph& graph) { deba@1697: Parent::setGraph(graph); deba@1697: } deba@1697: deba@1697: deba@1697: }; deba@1697: alpar@921: } //namespace lemon marci@556: alpar@1401: #endif //LEMON_GRAPH_ADAPTOR_H marci@556: