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: deba@2037: ///\ingroup graph_adaptors deba@2037: ///\file deba@2037: ///\brief Several graph adaptors. marci@556: /// deba@2037: ///This file contains several useful graph adaptor functions. marci@556: /// deba@2037: ///\author Marton Makai and Balazs Dezso marci@556: deba@1993: #include deba@2177: #include alpar@921: #include deba@1979: deba@1999: #include deba@1979: #include deba@1791: #include deba@1979: deba@2034: #include deba@2034: deba@2079: #include marci@556: alpar@921: namespace lemon { marci@556: klao@1951: ///\brief Base type for the Graph Adaptors klao@1951: /// klao@1951: ///Base type for the Graph Adaptors 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; deba@2031: typedef GraphAdaptorBase Adaptor; 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) { } deba@2034: 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); } deba@1991: deba@2031: Node fromNodeId(int id) const { deba@2031: return graph->fromNodeId(id); deba@2031: } deba@2031: deba@2031: Edge fromEdgeId(int id) const { deba@2031: return graph->fromEdgeId(id); deba@2031: } deba@2031: deba@1991: int maxNodeId() const { deba@1991: return graph->maxNodeId(); deba@1991: } deba@1991: deba@1991: int maxEdgeId() const { deba@1991: return graph->maxEdgeId(); deba@1991: } deba@1991: deba@1991: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@1991: deba@1991: NodeNotifier& getNotifier(Node) const { deba@1991: return graph->getNotifier(Node()); deba@1991: } deba@1991: deba@1991: typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; deba@1991: deba@1991: EdgeNotifier& getNotifier(Edge) const { deba@1991: return graph->getNotifier(Edge()); deba@1991: } marci@650: marci@970: template deba@2031: class NodeMap : public Graph::template NodeMap<_Value> { marci@970: public: deba@2031: deba@2031: typedef typename Graph::template NodeMap<_Value> Parent; deba@2031: deba@2031: explicit NodeMap(const Adaptor& ga) deba@2031: : Parent(*ga.graph) {} deba@2031: deba@2031: NodeMap(const Adaptor& ga, const _Value& value) deba@1991: : Parent(*ga.graph, value) { } deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: marci@970: }; marci@556: marci@970: template deba@2031: class EdgeMap : public Graph::template EdgeMap<_Value> { marci@970: public: deba@2031: deba@2031: typedef typename Graph::template EdgeMap<_Value> Parent; deba@2031: deba@2031: explicit EdgeMap(const Adaptor& ga) deba@2031: : Parent(*ga.graph) {} deba@2031: deba@2031: EdgeMap(const Adaptor& ga, const _Value& value) deba@2031: : Parent(*ga.graph, value) {} deba@2031: deba@2031: EdgeMap& operator=(const EdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: marci@970: }; deba@877: marci@556: }; marci@556: deba@2081: ///\ingroup graph_adaptors deba@2081: /// deba@2081: ///\brief Trivial Graph Adaptor deba@2081: /// deba@2081: /// This class is an adaptor which does not change the adapted graph. deba@2081: /// It can be used only to test the graph adaptors. marci@970: template alpar@1401: class GraphAdaptor : deba@1979: public GraphAdaptorExtender > { marci@970: public: marci@970: typedef _Graph Graph; deba@1979: typedef GraphAdaptorExtender > 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: deba@1991: /// \brief Just gives back a graph adaptor deba@1991: /// deba@1991: /// Just gives back a graph adaptor which deba@1991: /// should be provide original graph deba@1991: template deba@1991: GraphAdaptor deba@1991: graphAdaptor(const Graph& graph) { deba@1991: return GraphAdaptor(graph); deba@1991: } deba@1991: deba@1991: 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); } deba@1991: deba@1991: typedef FindEdgeTagIndicator FindEdgeTag; deba@1991: Edge findEdge(const Node& source, const Node& target, deba@1991: const Edge& prev = INVALID) { deba@1991: return Parent::findEdge(target, source, prev); deba@1991: } deba@1991: marci@997: }; marci@997: marci@997: deba@2081: ///\ingroup graph_adaptors deba@2081: /// alpar@1949: ///\brief A graph adaptor which reverses the orientation of the edges. alpar@1949: /// alpar@1949: /// If \c g is defined as alpar@1946: ///\code marci@923: /// ListGraph g; alpar@1946: ///\endcode alpar@1949: /// then alpar@1946: ///\code deba@1991: /// RevGraphAdaptor ga(g); alpar@1946: ///\endcode deba@2079: /// implements the graph obtained from \c g by alpar@1949: /// reversing the orientation of its edges. deba@2084: /// deba@2084: /// A good example of using RevGraphAdaptor is to decide that the deba@2084: /// directed graph is wheter strongly connected or not. If from one deba@2084: /// node each node is reachable and from each node is reachable this deba@2084: /// node then and just then the graph is strongly connected. Instead of deba@2084: /// this condition we use a little bit different. From one node each node deba@2084: /// ahould be reachable in the graph and in the reversed graph. Now this deba@2084: /// condition can be checked with the Dfs algorithm class and the deba@2084: /// RevGraphAdaptor algorithm class. deba@2084: /// deba@2084: /// And look at the code: deba@2084: /// deba@2084: ///\code deba@2084: /// bool stronglyConnected(const Graph& graph) { deba@2084: /// if (NodeIt(graph) == INVALID) return true; deba@2084: /// Dfs dfs(graph); deba@2084: /// dfs.run(NodeIt(graph)); deba@2084: /// for (NodeIt it(graph); it != INVALID; ++it) { deba@2084: /// if (!dfs.reached(it)) { deba@2084: /// return false; deba@2084: /// } deba@2084: /// } deba@2084: /// typedef RevGraphAdaptor RGraph; deba@2084: /// RGraph rgraph(graph); deba@2084: /// DfsVisit rdfs(rgraph); deba@2084: /// rdfs.run(NodeIt(graph)); deba@2084: /// for (NodeIt it(graph); it != INVALID; ++it) { deba@2084: /// if (!rdfs.reached(it)) { deba@2084: /// return false; deba@2084: /// } deba@2084: /// } deba@2084: /// return true; deba@2084: /// } deba@2084: ///\endcode marci@997: template alpar@1401: class RevGraphAdaptor : deba@1979: public GraphAdaptorExtender > { marci@650: public: marci@997: typedef _Graph Graph; deba@1979: typedef GraphAdaptorExtender< 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: deba@1991: /// \brief Just gives back a reverse graph adaptor deba@1991: /// deba@1991: /// Just gives back a reverse graph adaptor deba@1991: template deba@1991: RevGraphAdaptor deba@1991: revGraphAdaptor(const Graph& graph) { deba@1991: return RevGraphAdaptor(graph); deba@1991: } deba@1991: deba@1681: template alpar@1401: class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> { marci@992: public: marci@992: typedef _Graph Graph; deba@2031: typedef SubGraphAdaptorBase Adaptor; 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@1991: deba@1991: typedef FindEdgeTagIndicator FindEdgeTag; deba@1991: Edge findEdge(const Node& source, const Node& target, deba@1991: const Edge& prev = INVALID) { deba@1991: if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { deba@1991: return INVALID; deba@1991: } deba@1991: Edge edge = Parent::findEdge(source, target, prev); deba@1991: while (edge != INVALID && !(*edge_filter_map)[edge]) { deba@1991: edge = Parent::findEdge(source, target, edge); deba@1991: } deba@1991: return edge; deba@1991: } deba@2031: deba@2031: template deba@2031: class NodeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: NodeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: NodeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: deba@2031: template deba@2031: class EdgeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: EdgeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: EdgeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: EdgeMap& operator=(const EdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: 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@2031: typedef SubGraphAdaptorBase Adaptor; 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; deba@1991: deba@1991: typedef FindEdgeTagIndicator FindEdgeTag; deba@1991: Edge findEdge(const Node& source, const Node& target, deba@1991: const Edge& prev = INVALID) { deba@1991: if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { deba@1991: return INVALID; deba@1991: } deba@1991: Edge edge = Parent::findEdge(source, target, prev); deba@1991: while (edge != INVALID && !(*edge_filter_map)[edge]) { deba@1991: edge = Parent::findEdge(source, target, edge); deba@1991: } deba@1991: return edge; deba@1991: } deba@2031: deba@2031: template deba@2031: class NodeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: NodeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: NodeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: deba@2031: template deba@2031: class EdgeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: EdgeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: EdgeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: EdgeMap& operator=(const EdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: marci@992: }; marci@775: deba@2081: /// \ingroup graph_adaptors deba@2081: /// klao@1951: /// \brief A graph adaptor for hiding nodes and edges from a graph. 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); deba@1991: /// typedef SubGraphAdaptor, Graph::EdgeMap > SubGA; deba@1991: /// SubGA ga(g, nm, em); deba@1991: /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; klao@1951: /// std::cout << ":-)" << std::endl; deba@1991: /// for (SubGA::EdgeIt e(ga); 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 deba@1991: /// Note that \c n is of type \c SubGA::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 : deba@1979: public GraphAdaptorExtender< deba@1681: SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { marci@650: public: marci@992: typedef _Graph Graph; deba@2031: typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap, deba@2031: EdgeFilterMap, checked> > deba@2031: Parent; deba@2031: marci@556: protected: alpar@1401: SubGraphAdaptor() { } marci@992: public: deba@2031: 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: } deba@2031: marci@992: }; marci@556: deba@1991: /// \brief Just gives back a sub graph adaptor deba@1991: /// deba@1991: /// Just gives back a sub graph adaptor deba@1991: template deba@1991: SubGraphAdaptor deba@1991: subGraphAdaptor(const Graph& graph, deba@1991: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1991: return SubGraphAdaptor deba@1991: (graph, nfm, efm); deba@1991: } deba@1991: deba@1991: template deba@1991: SubGraphAdaptor deba@1991: subGraphAdaptor(const Graph& graph, deba@1991: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1991: return SubGraphAdaptor deba@1991: (graph, nfm, efm); deba@1991: } deba@1991: deba@1991: template deba@1991: SubGraphAdaptor deba@1991: subGraphAdaptor(const Graph& graph, deba@1991: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1991: return SubGraphAdaptor deba@1991: (graph, nfm, efm); deba@1991: } deba@1991: deba@1991: template deba@1991: SubGraphAdaptor deba@1991: subGraphAdaptor(const Graph& graph, deba@1991: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1991: return SubGraphAdaptor(graph, nfm, efm); deba@1991: } deba@1991: marci@556: marci@569: deba@2081: ///\ingroup graph_adaptors deba@2081: /// klao@1951: ///\brief An adaptor for hiding nodes from a graph. 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: deba@2031: alpar@1401: typedef SubGraphAdaptor, checked > deba@2031: Parent; deba@2031: marci@933: protected: marci@933: ConstMap const_true_map; deba@1991: deba@1991: NodeSubGraphAdaptor() : const_true_map(true) { deba@1991: Parent::setEdgeFilterMap(const_true_map); deba@1991: } deba@1991: marci@933: public: deba@2031: 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: } deba@2031: marci@933: }; marci@933: marci@933: deba@1991: /// \brief Just gives back a node sub graph adaptor deba@1991: /// deba@1991: /// Just gives back a node sub graph adaptor deba@1991: template deba@1991: NodeSubGraphAdaptor deba@1991: nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) { deba@1991: return NodeSubGraphAdaptor(graph, nfm); deba@1991: } deba@1991: deba@1991: template deba@1991: NodeSubGraphAdaptor deba@1991: nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) { deba@1991: return NodeSubGraphAdaptor(graph, nfm); deba@1991: } deba@1991: deba@2081: ///\ingroup graph_adaptors deba@2081: /// klao@1951: ///\brief An adaptor for hiding edges from a graph. 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: /// deba@1991: ///typedef EdgeSubGraphAdaptor SubGA; deba@1991: ///SubGA ga(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: /// deba@1991: ///Preflow, Graph::EdgeMap > deba@1991: /// preflow(ga, 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; deba@1991: deba@1991: EdgeSubGraphAdaptor() : const_true_map(true) { deba@1991: Parent::setNodeFilterMap(const_true_map); deba@1991: } deba@1991: marci@932: public: deba@2031: 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: } deba@2031: marci@932: }; marci@932: deba@1991: /// \brief Just gives back an edge sub graph adaptor deba@1991: /// deba@1991: /// Just gives back an edge sub graph adaptor deba@1991: template deba@1991: EdgeSubGraphAdaptor deba@1991: edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) { deba@1991: return EdgeSubGraphAdaptor(graph, efm); deba@1991: } deba@1991: deba@1991: template deba@1991: EdgeSubGraphAdaptor deba@1991: edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) { deba@1991: return EdgeSubGraphAdaptor(graph, efm); deba@1991: } deba@1991: deba@2079: template deba@1980: class UndirGraphAdaptorBase : deba@2079: public UndirGraphExtender > { marci@1383: public: marci@1383: typedef _Graph Graph; deba@2031: typedef UndirGraphAdaptorBase Adaptor; deba@2079: typedef UndirGraphExtender > Parent; deba@1991: marci@1383: protected: deba@1991: deba@1991: UndirGraphAdaptorBase() : Parent() {} deba@1991: marci@1383: public: deba@1991: klao@1909: typedef typename Parent::UEdge UEdge; marci@1383: typedef typename Parent::Edge Edge; deba@1991: deba@2031: private: marci@1383: deba@1991: template deba@2031: class EdgeMapBase { deba@1991: private: deba@1991: deba@1991: typedef typename _Graph::template EdgeMap<_Value> MapImpl; deba@1991: marci@1383: public: deba@1991: deba@1991: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; deba@1991: deba@1991: typedef _Value Value; marci@1383: typedef Edge Key; marci@1383: deba@2031: EdgeMapBase(const Adaptor& adaptor) : deba@2031: forward_map(*adaptor.graph), backward_map(*adaptor.graph) {} marci@569: deba@2031: EdgeMapBase(const Adaptor& adaptor, const Value& v) deba@2031: : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {} marci@1383: deba@1991: void set(const Edge& e, const Value& a) { deba@1991: if (Parent::direction(e)) { marci@1383: forward_map.set(e, a); deba@1991: } else { deba@1991: backward_map.set(e, a); deba@1991: } marci@1383: } marci@556: deba@1991: typename MapTraits::ConstReturnValue operator[](Edge e) const { deba@1991: if (Parent::direction(e)) { marci@1383: return forward_map[e]; deba@1991: } else { marci@1383: return backward_map[e]; deba@1991: } marci@556: } deba@1991: deba@1991: typename MapTraits::ReturnValue operator[](Edge e) { deba@1991: if (Parent::direction(e)) { deba@1991: return forward_map[e]; deba@1991: } else { deba@1991: return backward_map[e]; deba@1991: } deba@1991: } deba@1991: deba@1991: protected: deba@1991: deba@1991: MapImpl forward_map, backward_map; deba@1991: marci@556: }; deba@2031: deba@2031: public: deba@2031: deba@2031: template deba@2031: class EdgeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: EdgeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: EdgeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: EdgeMap& operator=(const EdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; marci@1383: deba@1991: template deba@2031: class UEdgeMap : public Graph::template EdgeMap<_Value> { marci@1383: public: deba@2031: deba@2031: typedef typename Graph::template EdgeMap<_Value> Parent; deba@2031: deba@2031: explicit UEdgeMap(const Adaptor& ga) deba@2031: : Parent(*ga.graph) {} deba@1991: deba@2031: UEdgeMap(const Adaptor& ga, const _Value& value) deba@2031: : Parent(*ga.graph, value) {} deba@1991: deba@2031: UEdgeMap& operator=(const UEdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@1991: deba@2031: template deba@2031: UEdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: deba@1991: }; deba@1991: deba@1991: }; marci@556: deba@2079: template deba@2079: class AlterableUndirGraphAdaptor deba@2079: : public UGraphAdaptorExtender > { deba@2079: public: deba@2079: typedef UGraphAdaptorExtender > Parent; deba@2079: deba@2079: protected: deba@2079: deba@2079: AlterableUndirGraphAdaptor() : Parent() {} deba@2079: deba@1991: public: deba@1991: deba@2079: typedef typename Parent::EdgeNotifier UEdgeNotifier; deba@2079: typedef InvalidType EdgeNotifier; deba@2079: deba@2079: }; deba@2079: deba@2079: template deba@2079: class AlterableUndirGraphAdaptor< deba@2079: _Graph, deba@2079: typename enable_if::type > deba@2079: : public UGraphAdaptorExtender > { deba@2079: public: deba@2079: deba@2079: typedef UGraphAdaptorExtender > Parent; deba@1991: typedef _Graph Graph; deba@2079: typedef typename _Graph::Edge GraphEdge; deba@2079: deba@1991: protected: deba@1991: deba@2079: AlterableUndirGraphAdaptor() deba@2079: : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {} deba@1991: deba@1991: void setGraph(_Graph& graph) { deba@1991: Parent::setGraph(graph); deba@2079: edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge())); deba@1991: } deba@1991: deba@1991: public: deba@1991: deba@2079: ~AlterableUndirGraphAdaptor() { deba@1999: edge_notifier.clear(); deba@1999: } deba@1999: deba@1991: typedef typename Parent::UEdge UEdge; deba@1991: typedef typename Parent::Edge Edge; deba@1991: deba@1991: typedef typename Parent::EdgeNotifier UEdgeNotifier; deba@1991: deba@1991: using Parent::getNotifier; deba@1991: deba@2079: typedef AlterationNotifier EdgeNotifier; deba@1991: EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } deba@1991: deba@1991: protected: deba@1991: deba@2079: class NotifierProxy : public Graph::EdgeNotifier::ObserverBase { deba@1991: public: deba@1991: deba@2079: typedef typename Graph::EdgeNotifier::ObserverBase Parent; deba@2079: typedef AlterableUndirGraphAdaptor AdaptorBase; marci@1383: deba@2079: NotifierProxy(const AdaptorBase& _adaptor) deba@2079: : Parent(), adaptor(&_adaptor) { marci@1383: } marci@556: deba@1991: virtual ~NotifierProxy() { deba@1991: if (Parent::attached()) { deba@1991: Parent::detach(); deba@1991: } marci@1383: } deba@1991: deba@2079: void setNotifier(typename Graph::EdgeNotifier& notifier) { deba@2079: Parent::attach(notifier); deba@1991: } deba@1991: deba@1991: deba@1991: protected: deba@1991: deba@2079: virtual void add(const GraphEdge& ge) { deba@1991: std::vector edges; deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge, true)); deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge, false)); deba@2079: adaptor->getNotifier(Edge()).add(edges); deba@1991: } deba@2079: virtual void add(const std::vector& ge) { deba@1991: std::vector edges; deba@2079: for (int i = 0; i < (int)ge.size(); ++i) { deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge[i], true)); deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge[i], false)); deba@1991: } deba@2079: adaptor->getNotifier(Edge()).add(edges); deba@1991: } deba@2079: virtual void erase(const GraphEdge& ge) { deba@1991: std::vector edges; deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge, true)); deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge, false)); deba@2079: adaptor->getNotifier(Edge()).erase(edges); deba@1991: } deba@2079: virtual void erase(const std::vector& ge) { deba@1991: std::vector edges; deba@2079: for (int i = 0; i < (int)ge.size(); ++i) { deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge[i], true)); deba@2079: edges.push_back(AdaptorBase::Parent::direct(ge[i], false)); deba@1991: } deba@2079: adaptor->getNotifier(Edge()).erase(edges); deba@1991: } deba@1991: virtual void build() { deba@2079: adaptor->getNotifier(Edge()).build(); deba@1991: } deba@1991: virtual void clear() { deba@2079: adaptor->getNotifier(Edge()).clear(); deba@1991: } deba@1991: deba@2079: const AdaptorBase* adaptor; deba@1991: }; deba@1991: deba@1991: deba@1991: mutable EdgeNotifier edge_notifier; deba@1991: NotifierProxy edge_notifier_proxy; deba@1991: marci@1383: }; marci@1383: deba@2079: deba@2081: ///\ingroup graph_adaptors deba@2081: /// deba@2079: /// \brief An undirected graph is made from a directed graph by an adaptor klao@1951: /// deba@2251: /// This adaptor makes an undirected graph from a directed deba@2251: /// graph. All edge of the underlying will be showed in the adaptor deba@2251: /// as an undirected edge. Let's see an informal example about using deba@2251: /// this adaptor: deba@2251: /// deba@2251: /// There is a network of the streets of a town. Of course there are deba@2251: /// some one-way street in the town hence the network is a directed deba@2251: /// one. There is a crazy driver who go oppositely in the one-way deba@2251: /// street without moral sense. Of course he can pass this streets deba@2251: /// slower than the regular way, in fact his speed is half of the deba@2251: /// normal speed. How long should he drive to get from a source deba@2251: /// point to the target? Let see the example code which calculate it: deba@2251: /// deba@2251: ///\code deba@2251: /// typedef UndirGraphAdaptor UGraph; deba@2251: /// UGraph ugraph(graph); deba@2251: /// deba@2251: /// typedef SimpleMap FLengthMap; deba@2251: /// FLengthMap flength(length); deba@2251: /// deba@2251: /// typedef ScaleMap RLengthMap; deba@2251: /// RLengthMap rlength(length, 2.0); deba@2251: /// deba@2251: /// typedef UGraph::CombinedEdgeMap ULengthMap; deba@2251: /// ULengthMap ulength(flength, rlength); klao@1951: /// deba@2251: /// Dijkstra dijkstra(ugraph, ulength); deba@2251: /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl; deba@2251: ///\endcode deba@2251: /// deba@2251: /// The combined edge map makes the length map for the undirected deba@2251: /// graph. It is created from a forward and reverse map. The forward deba@2251: /// map is created from the original length map with a SimpleMap deba@2251: /// adaptor which just makes a read-write map from the reference map deba@2251: /// i.e. it forgets that it can be return reference to values. The deba@2251: /// reverse map is just the scaled original map with the ScaleMap deba@2251: /// adaptor. The combination solves that passing the reverse way deba@2251: /// takes double time than the original. To get the driving time we deba@2251: /// run the dijkstra algorithm on the undirected graph. deba@2251: /// deba@2251: /// \author Marton Makai and Balazs Dezso marci@1383: template deba@2079: class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> { marci@1383: public: marci@1383: typedef _Graph Graph; deba@2079: typedef AlterableUndirGraphAdaptor<_Graph> Parent; marci@1383: protected: deba@1980: UndirGraphAdaptor() { } marci@1383: public: deba@2251: deba@2251: /// \brief Constructor deba@2251: /// deba@2251: /// Constructor deba@1980: UndirGraphAdaptor(_Graph& _graph) { marci@1383: setGraph(_graph); marci@556: } marci@556: deba@2251: /// \brief EdgeMap combined from two original EdgeMap deba@2251: /// deba@2251: /// This class adapts two original graph EdgeMap to deba@2251: /// get an edge map on the adaptor. deba@1991: template deba@1991: class CombinedEdgeMap { deba@1991: public: deba@1991: deba@1991: typedef _ForwardMap ForwardMap; deba@1991: typedef _BackwardMap BackwardMap; marci@992: deba@1991: typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; marci@992: deba@1991: typedef typename ForwardMap::Value Value; deba@1991: typedef typename Parent::Edge Key; deba@2251: deba@2251: /// \brief Constructor deba@2251: /// deba@2251: /// Constructor deba@1991: CombinedEdgeMap() : forward_map(0), backward_map(0) {} marci@992: deba@2251: /// \brief Constructor deba@2251: /// deba@2251: /// Constructor deba@1991: CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map) deba@1991: : forward_map(&_forward_map), backward_map(&_backward_map) {} marci@992: deba@2251: deba@2251: /// \brief Sets the value associated with a key. deba@2251: /// deba@2251: /// Sets the value associated with a key. deba@1991: void set(const Key& e, const Value& a) { deba@1991: if (Parent::direction(e)) { deba@1991: forward_map->set(e, a); deba@1991: } else { deba@1991: backward_map->set(e, a); deba@1991: } marci@992: } marci@992: deba@2251: /// \brief Returns the value associated with a key. deba@2251: /// deba@2251: /// Returns the value associated with a key. deba@1991: typename MapTraits::ConstReturnValue deba@1991: operator[](const Key& e) const { deba@1991: if (Parent::direction(e)) { deba@1991: return (*forward_map)[e]; deba@1991: } else { deba@1991: return (*backward_map)[e]; deba@1991: } marci@992: } marci@992: deba@2251: /// \brief Returns the value associated with a key. deba@2251: /// deba@2251: /// Returns the value associated with a key. deba@1991: typename MapTraits::ReturnValue deba@1991: operator[](const Key& e) { deba@1991: if (Parent::direction(e)) { deba@1991: return (*forward_map)[e]; deba@1991: } else { deba@1991: return (*backward_map)[e]; deba@1991: } marci@992: } deba@1991: deba@2251: /// \brief Sets the forward map deba@2251: /// deba@2251: /// Sets the forward map deba@1991: void setForwardMap(ForwardMap& _forward_map) { deba@1991: forward_map = &_forward_map; deba@1991: } deba@1991: deba@2251: /// \brief Sets the backward map deba@2251: /// deba@2251: /// Sets the backward map deba@1991: void setBackwardMap(BackwardMap& _backward_map) { deba@1991: backward_map = &_backward_map; deba@1991: } deba@1991: deba@1991: protected: deba@1991: deba@1991: ForwardMap* forward_map; deba@1991: BackwardMap* backward_map; deba@1991: marci@992: }; marci@992: marci@992: }; marci@569: deba@1991: /// \brief Just gives back an undir graph adaptor klao@1951: /// deba@1991: /// Just gives back an undir graph adaptor marci@650: template deba@1991: UndirGraphAdaptor deba@1991: undirGraphAdaptor(const Graph& graph) { deba@1991: return UndirGraphAdaptor(graph); deba@1991: } marci@650: deba@2034: template > marci@658: class ResForwardFilter { marci@650: const CapacityMap* capacity; marci@650: const FlowMap* flow; deba@2034: Tolerance tolerance; marci@650: public: deba@1991: typedef typename Graph::Edge Key; deba@1991: typedef bool Value; deba@1991: deba@2034: ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow, deba@2034: const Tolerance& _tolerance = Tolerance()) deba@2034: : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { } deba@2034: deba@2034: ResForwardFilter(const Tolerance& _tolerance) deba@2034: : capacity(0), flow(0), tolerance(_tolerance) { } deba@2034: deba@1991: void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; } deba@1991: void setFlow(const FlowMap& _flow) { flow = &_flow; } deba@2034: marci@650: bool operator[](const typename Graph::Edge& e) const { deba@2034: return tolerance.less((*flow)[e], (*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; deba@2034: Tolerance tolerance; marci@650: public: deba@1991: typedef typename Graph::Edge Key; deba@1991: typedef bool Value; deba@1991: deba@2034: ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow, deba@2034: const Tolerance& _tolerance = Tolerance()) deba@2034: : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { } deba@2034: ResBackwardFilter(const Tolerance& _tolerance = Tolerance()) deba@2034: : capacity(0), flow(0), tolerance(_tolerance) { } deba@1991: void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; } deba@1991: void setFlow(const FlowMap& _flow) { flow = &_flow; } marci@650: bool operator[](const typename Graph::Edge& e) const { deba@2034: return tolerance.less(0, Number((*flow)[e])); marci@650: } marci@650: }; marci@650: marci@653: deba@2081: ///\ingroup graph_adaptors deba@2081: /// klao@1951: ///\brief An adaptor for composing the residual klao@1951: ///graph for directed flow and circulation problems. deba@2037: /// deba@2042: ///An adaptor for composing the residual graph for directed flow and deba@2042: ///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph deba@2042: ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$, deba@2042: ///be functions on the edge-set. deba@2042: /// deba@2042: ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands deba@2042: ///for a flow and \f$ c \f$ for a capacity function. Suppose that a deba@2042: ///graph instange \c g of type \c ListGraph implements \f$ G \f$. deba@2042: /// deba@2042: ///\code deba@2042: /// ListGraph g; deba@2042: ///\endcode deba@2042: /// deba@2042: ///Then RevGraphAdaptor implements the graph structure with node-set deba@2042: /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, deba@2042: ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)0\} \f$, i.e. the so called deba@2042: ///residual graph. When we take the union deba@2042: /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e. deba@2042: ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$, deba@2042: ///then in the adaptor it appears twice. The following code shows how deba@2042: ///such an instance can be constructed. deba@2042: /// deba@2042: ///\code deba@2042: /// typedef ListGraph Graph; deba@2042: /// Graph::EdgeMap f(g); deba@2042: /// Graph::EdgeMap c(g); deba@2042: /// ResGraphAdaptor, Graph::EdgeMap > ga(g); deba@2042: ///\endcode deba@2042: ///\author Marton Makai deba@2042: /// marci@650: template > alpar@1401: class ResGraphAdaptor : deba@1991: public EdgeSubGraphAdaptor< deba@2034: UndirGraphAdaptor, deba@2034: typename UndirGraphAdaptor::template CombinedEdgeMap< deba@2034: ResForwardFilter, deba@2034: ResBackwardFilter > > { marci@650: public: deba@1991: deba@2034: typedef UndirGraphAdaptor UGraph; deba@1991: deba@2034: typedef ResForwardFilter deba@1991: ForwardFilter; deba@1991: deba@2034: typedef ResBackwardFilter deba@1991: BackwardFilter; deba@1991: deba@1991: typedef typename UGraph:: deba@1991: template CombinedEdgeMap deba@1991: EdgeFilter; deba@1991: deba@1991: typedef EdgeSubGraphAdaptor Parent; deba@1991: marci@650: protected: deba@1991: marci@650: const CapacityMap* capacity; marci@650: FlowMap* flow; deba@1991: deba@1991: UGraph ugraph; deba@1991: ForwardFilter forward_filter; deba@1991: BackwardFilter backward_filter; deba@1991: EdgeFilter edge_filter; deba@1991: 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: } deba@1991: marci@658: void setFlowMap(FlowMap& _flow) { marci@658: flow=&_flow; marci@658: forward_filter.setFlow(_flow); marci@658: backward_filter.setFlow(_flow); marci@658: } deba@1991: marci@650: public: deba@1991: deba@2034: /// \brief Constructor of the residual graph. deba@2034: /// deba@2034: /// Constructor of the residual graph. The parameters are the graph type, deba@2034: /// the flow map, the capacity map and a tolerance object. deba@2034: ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity, deba@2034: FlowMap& _flow, const Tolerance& _tolerance = Tolerance()) deba@2034: : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph), deba@2034: forward_filter(_capacity, _flow, _tolerance), deba@2034: backward_filter(_capacity, _flow, _tolerance), deba@2034: edge_filter(forward_filter, backward_filter) deba@2034: { deba@1991: Parent::setGraph(ugraph); deba@1991: Parent::setEdgeFilterMap(edge_filter); marci@650: } marci@650: marci@660: typedef typename Parent::Edge Edge; marci@660: deba@2034: /// \brief Gives back the residual capacity of the edge. deba@2034: /// deba@2034: /// Gives back the residual capacity of the edge. deba@2034: Number rescap(const Edge& edge) const { deba@2034: if (UGraph::direction(edge)) { deba@2034: return (*capacity)[edge]-(*flow)[edge]; deba@2034: } else { deba@2034: return (*flow)[edge]; deba@2034: } deba@2034: } deba@2034: deba@2034: /// \brief Augment on the given edge in the residual graph. deba@2034: /// deba@2034: /// Augment on the given edge in the residual graph. It increase deba@2034: /// or decrease the flow on the original edge depend on the direction deba@2034: /// of the residual edge. marci@660: void augment(const Edge& e, Number a) const { deba@1991: if (UGraph::direction(e)) { deba@2034: flow->set(e, (*flow)[e] + a); deba@1991: } else { deba@2034: flow->set(e, (*flow)[e] - a); deba@1991: } marci@650: } marci@650: deba@2034: /// \brief Returns the direction of the edge. deba@2034: /// deba@2034: /// Returns true when the edge is same oriented as the original edge. deba@1991: static bool forward(const Edge& e) { deba@1991: return UGraph::direction(e); deba@1991: } deba@1991: deba@2034: /// \brief Returns the direction of the edge. deba@2034: /// deba@2034: /// Returns true when the edge is opposite oriented as the original edge. deba@1991: static bool backward(const Edge& e) { deba@1991: return !UGraph::direction(e); deba@1991: } deba@1991: deba@2034: /// \brief Gives back the forward oriented residual edge. deba@2034: /// deba@2034: /// Gives back the forward oriented residual edge. deba@1991: static Edge forward(const typename Graph::Edge& e) { deba@1991: return UGraph::direct(e, true); deba@1991: } deba@1991: deba@2034: /// \brief Gives back the backward oriented residual edge. deba@2034: /// deba@2034: /// Gives back the backward oriented residual edge. deba@1991: static Edge backward(const typename Graph::Edge& e) { deba@1991: return UGraph::direct(e, false); deba@1991: } deba@1991: 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: deba@1991: const ResGraphAdaptor* res_graph; marci@660: public: alpar@987: typedef Number Value; alpar@987: typedef Edge Key; deba@1991: ResCap(const ResGraphAdaptor& _res_graph) deba@1991: : res_graph(&_res_graph) {} deba@1991: deba@2034: Number operator[](const Edge& e) const { deba@2034: return res_graph->rescap(e); marci@660: } deba@1991: marci@660: }; marci@660: 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: deba@2081: ///\ingroup graph_adaptors deba@2081: /// klao@1951: ///\brief For blocking flows. 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 : deba@1979: public GraphAdaptorExtender< alpar@1401: ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > { marci@650: public: marci@998: typedef _Graph Graph; deba@1979: typedef GraphAdaptorExtender< 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@2079: /// \brief Base class for split graph adaptor deba@2079: /// deba@2079: /// Base class of split graph adaptor. In most case you do not need to deba@2079: /// use it directly but the documented member functions of this class can deba@2079: /// be used with the SplitGraphAdaptor class. deba@2079: /// \sa SplitGraphAdaptor deba@2079: template deba@2079: class SplitGraphAdaptorBase deba@2079: : public GraphAdaptorBase { deba@2079: public: deba@1697: deba@2079: typedef _Graph Graph; deba@2079: deba@2079: typedef GraphAdaptorBase Parent; deba@2079: deba@2079: typedef typename Graph::Node GraphNode; deba@2079: typedef typename Graph::Edge GraphEdge; deba@2079: deba@2079: class Node; deba@2079: class Edge; deba@2079: deba@2079: template class NodeMap; deba@2079: template class EdgeMap; deba@1697: deba@1697: deba@2079: class Node : public GraphNode { deba@2079: friend class SplitGraphAdaptorBase; deba@2079: template friend class NodeMap; deba@2079: private: deba@1697: deba@2079: bool in_node; deba@2079: Node(GraphNode _node, bool _in_node) deba@2079: : GraphNode(_node), in_node(_in_node) {} deba@1697: deba@2079: public: deba@1697: deba@2079: Node() {} deba@2079: Node(Invalid) : GraphNode(INVALID), in_node(true) {} deba@2079: deba@2079: bool operator==(const Node& node) const { deba@2079: return GraphNode::operator==(node) && in_node == node.in_node; deba@2079: } deba@1697: deba@2079: bool operator!=(const Node& node) const { deba@2079: return !(*this == node); deba@2079: } deba@1697: deba@2079: bool operator<(const Node& node) const { deba@2079: return GraphNode::operator<(node) || deba@2079: (GraphNode::operator==(node) && in_node < node.in_node); deba@2079: } deba@2079: }; deba@1697: deba@2079: class Edge { deba@2079: friend class SplitGraphAdaptorBase; deba@2079: template friend class EdgeMap; deba@2079: private: deba@2079: typedef BiVariant EdgeImpl; deba@1697: deba@2079: explicit Edge(const GraphEdge& edge) : item(edge) {} deba@2079: explicit Edge(const GraphNode& node) : item(node) {} deba@2079: deba@2079: EdgeImpl item; deba@1697: deba@2079: public: deba@2079: Edge() {} deba@2079: Edge(Invalid) : item(GraphEdge(INVALID)) {} deba@2079: deba@2079: bool operator==(const Edge& edge) const { deba@2079: if (item.firstState()) { deba@2079: if (edge.item.firstState()) { deba@2079: return item.first() == edge.item.first(); deba@2079: } deba@2079: } else { deba@2079: if (edge.item.secondState()) { deba@2079: return item.second() == edge.item.second(); deba@2079: } deba@2079: } deba@2079: return false; deba@2079: } deba@1697: deba@2079: bool operator!=(const Edge& edge) const { deba@2079: return !(*this == edge); deba@2079: } deba@1697: deba@2079: bool operator<(const Edge& edge) const { deba@2079: if (item.firstState()) { deba@2079: if (edge.item.firstState()) { deba@2079: return item.first() < edge.item.first(); deba@2079: } deba@2079: return false; deba@2079: } else { deba@2079: if (edge.item.secondState()) { deba@2079: return item.second() < edge.item.second(); deba@2079: } deba@2079: return true; deba@2079: } deba@2079: } deba@1697: deba@2079: operator GraphEdge() const { return item.first(); } deba@2079: operator GraphNode() const { return item.second(); } deba@1697: deba@2079: }; deba@1697: deba@2079: void first(Node& node) const { deba@2079: Parent::first(node); deba@2079: node.in_node = true; deba@2079: } deba@1697: deba@2079: void next(Node& node) const { deba@2079: if (node.in_node) { deba@2079: node.in_node = false; deba@2079: } else { deba@2079: node.in_node = true; deba@2079: Parent::next(node); deba@2079: } deba@2079: } deba@1697: deba@2079: void first(Edge& edge) const { deba@2079: edge.item.setSecond(); deba@2079: Parent::first(edge.item.second()); deba@2079: if (edge.item.second() == INVALID) { deba@2079: edge.item.setFirst(); deba@2079: Parent::first(edge.item.first()); deba@2079: } deba@2079: } deba@1697: deba@2079: void next(Edge& edge) const { deba@2079: if (edge.item.secondState()) { deba@2079: Parent::next(edge.item.second()); deba@2079: if (edge.item.second() == INVALID) { deba@2079: edge.item.setFirst(); deba@2079: Parent::first(edge.item.first()); deba@2079: } deba@2079: } else { deba@2079: Parent::next(edge.item.first()); deba@2079: } deba@2079: } deba@1697: deba@2079: void firstOut(Edge& edge, const Node& node) const { deba@2079: if (node.in_node) { deba@2079: edge.item.setSecond(node); deba@2079: } else { deba@2079: edge.item.setFirst(); deba@2079: Parent::firstOut(edge.item.first(), node); deba@2079: } deba@2079: } deba@1697: deba@2079: void nextOut(Edge& edge) const { deba@2079: if (!edge.item.firstState()) { deba@2079: edge.item.setFirst(INVALID); deba@2079: } else { deba@2079: Parent::nextOut(edge.item.first()); deba@2079: } deba@2079: } deba@1697: deba@2079: void firstIn(Edge& edge, const Node& node) const { deba@2079: if (!node.in_node) { deba@2079: edge.item.setSecond(node); deba@2079: } else { deba@2079: edge.item.setFirst(); deba@2079: Parent::firstIn(edge.item.first(), node); deba@2079: } deba@2079: } deba@1697: deba@2079: void nextIn(Edge& edge) const { deba@2079: if (!edge.item.firstState()) { deba@2079: edge.item.setFirst(INVALID); deba@2079: } else { deba@2079: Parent::nextIn(edge.item.first()); deba@2079: } deba@2079: } deba@1697: deba@2079: Node source(const Edge& edge) const { deba@2079: if (edge.item.firstState()) { deba@2079: return Node(Parent::source(edge.item.first()), false); deba@2079: } else { deba@2079: return Node(edge.item.second(), true); deba@2079: } deba@2079: } deba@1697: deba@2079: Node target(const Edge& edge) const { deba@2079: if (edge.item.firstState()) { deba@2079: return Node(Parent::target(edge.item.first()), true); deba@2079: } else { deba@2079: return Node(edge.item.second(), false); deba@2079: } deba@2079: } deba@1697: deba@2079: int id(const Node& node) const { deba@2079: return (Parent::id(node) << 1) | (node.in_node ? 0 : 1); deba@2079: } deba@2079: Node nodeFromId(int id) const { deba@2079: return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0); deba@2079: } deba@2079: int maxNodeId() const { deba@2079: return 2 * Parent::maxNodeId() + 1; deba@2079: } deba@1697: deba@2079: int id(const Edge& edge) const { deba@2079: if (edge.item.firstState()) { deba@2079: return Parent::id(edge.item.first()) << 1; deba@2079: } else { deba@2079: return (Parent::id(edge.item.second()) << 1) | 1; deba@2079: } deba@2079: } deba@2079: Edge edgeFromId(int id) const { deba@2079: if ((id & 1) == 0) { deba@2079: return Edge(Parent::edgeFromId(id >> 1)); deba@2079: } else { deba@2079: return Edge(Parent::nodeFromId(id >> 1)); deba@2079: } deba@2079: } deba@2079: int maxEdgeId() const { deba@2079: return std::max(Parent::maxNodeId() << 1, deba@2079: (Parent::maxEdgeId() << 1) | 1); deba@2079: } deba@1697: deba@2079: /// \brief Returns true when the node is in-node. deba@2079: /// deba@2079: /// Returns true when the node is in-node. deba@2079: static bool inNode(const Node& node) { deba@2079: return node.in_node; deba@2079: } deba@1697: deba@2079: /// \brief Returns true when the node is out-node. deba@2079: /// deba@2079: /// Returns true when the node is out-node. deba@2079: static bool outNode(const Node& node) { deba@2079: return !node.in_node; deba@2079: } deba@1697: deba@2079: /// \brief Returns true when the edge is edge in the original graph. deba@2079: /// deba@2079: /// Returns true when the edge is edge in the original graph. deba@2079: static bool origEdge(const Edge& edge) { deba@2079: return edge.item.firstState(); deba@2079: } deba@1697: deba@2079: /// \brief Returns true when the edge binds an in-node and an out-node. deba@2079: /// deba@2079: /// Returns true when the edge binds an in-node and an out-node. deba@2079: static bool bindEdge(const Edge& edge) { deba@2079: return edge.item.secondState(); deba@2079: } deba@1697: deba@2079: /// \brief Gives back the in-node created from the \c node. deba@2079: /// deba@2079: /// Gives back the in-node created from the \c node. deba@2079: static Node inNode(const GraphNode& node) { deba@2079: return Node(node, true); deba@2079: } deba@2079: deba@2079: /// \brief Gives back the out-node created from the \c node. deba@2079: /// deba@2079: /// Gives back the out-node created from the \c node. deba@2079: static Node outNode(const GraphNode& node) { deba@2079: return Node(node, false); deba@2079: } deba@2079: deba@2079: /// \brief Gives back the edge binds the two part of the node. deba@2079: /// deba@2079: /// Gives back the edge binds the two part of the node. deba@2079: static Edge edge(const GraphNode& node) { deba@2079: return Edge(node); deba@2079: } deba@2079: deba@2079: /// \brief Gives back the edge of the original edge. deba@2079: /// deba@2079: /// Gives back the edge of the original edge. deba@2079: static Edge edge(const GraphEdge& edge) { deba@2079: return Edge(edge); deba@2079: } deba@2079: deba@2079: typedef True NodeNumTag; deba@2079: deba@2079: int nodeNum() const { deba@2079: return 2 * countNodes(*Parent::graph); deba@2079: } deba@2079: deba@2079: typedef True EdgeNumTag; deba@1697: deba@2079: int edgeNum() const { deba@2079: return countEdges(*Parent::graph) + countNodes(*Parent::graph); deba@2079: } deba@1697: deba@2079: typedef True FindEdgeTag; deba@2079: deba@2079: Edge findEdge(const Node& source, const Node& target, deba@2079: const Edge& prev = INVALID) const { deba@2079: if (inNode(source)) { deba@2079: if (outNode(target)) { deba@2079: if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) { deba@2079: return Edge(source); deba@2079: } deba@2079: } deba@2079: } else { deba@2079: if (inNode(target)) { deba@2079: return Edge(findEdge(*Parent::graph, source, target, prev)); deba@2079: } deba@2079: } deba@2079: return INVALID; deba@2079: } deba@1697: deba@2079: template deba@2079: class NodeMap : public MapBase { deba@2079: typedef typename Parent::template NodeMap NodeImpl; deba@2079: public: deba@2079: NodeMap(const SplitGraphAdaptorBase& _graph) deba@2079: : inNodeMap(_graph), outNodeMap(_graph) {} deba@2079: NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) deba@2079: : inNodeMap(_graph, t), outNodeMap(_graph, t) {} deba@1697: deba@2079: void set(const Node& key, const T& val) { deba@2079: if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); } deba@2079: else {outNodeMap.set(key, val); } deba@2079: } deba@1697: deba@2079: typename MapTraits::ReturnValue deba@2079: operator[](const Node& key) { deba@2079: if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; } deba@2079: else { return outNodeMap[key]; } deba@2079: } deba@1697: deba@2079: typename MapTraits::ConstReturnValue deba@2079: operator[](const Node& key) const { deba@2079: if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; } deba@2079: else { return outNodeMap[key]; } deba@2079: } deba@1697: deba@2079: private: deba@2079: NodeImpl inNodeMap, outNodeMap; deba@2079: }; deba@1697: deba@2079: template deba@2079: class EdgeMap : public MapBase { deba@2079: typedef typename Parent::template EdgeMap EdgeMapImpl; deba@2079: typedef typename Parent::template NodeMap NodeMapImpl; deba@2079: public: deba@2079: deba@2079: EdgeMap(const SplitGraphAdaptorBase& _graph) deba@2079: : edge_map(_graph), node_map(_graph) {} deba@2079: EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) deba@2079: : edge_map(_graph, t), node_map(_graph, t) {} deba@1697: deba@2079: void set(const Edge& key, const T& val) { deba@2079: if (SplitGraphAdaptorBase::origEdge(key)) { deba@2079: edge_map.set(key.item.first(), val); deba@2079: } else { deba@2079: node_map.set(key.item.second(), val); deba@2079: } deba@2079: } deba@1697: deba@2079: typename MapTraits::ReturnValue deba@2079: operator[](const Edge& key) { deba@2079: if (SplitGraphAdaptorBase::origEdge(key)) { deba@2079: return edge_map[key.item.first()]; deba@2079: } else { deba@2079: return node_map[key.item.second()]; deba@2079: } deba@2079: } deba@1697: deba@2079: typename MapTraits::ConstReturnValue deba@2079: operator[](const Edge& key) const { deba@2079: if (SplitGraphAdaptorBase::origEdge(key)) { deba@2079: return edge_map[key.item.first()]; deba@2079: } else { deba@2079: return node_map[key.item.second()]; deba@2079: } deba@2079: } deba@1697: deba@2079: private: deba@2079: typename Parent::template EdgeMap edge_map; deba@2079: typename Parent::template NodeMap node_map; deba@2079: }; deba@1697: deba@1697: deba@2079: }; deba@1697: deba@2079: template deba@2079: class AlterableSplitGraphAdaptor deba@2079: : public GraphAdaptorExtender > { deba@2079: public: deba@1697: deba@2079: typedef GraphAdaptorExtender > Parent; deba@2079: typedef _Graph Graph; deba@1697: deba@2079: typedef typename Graph::Node GraphNode; deba@2079: typedef typename Graph::Node GraphEdge; deba@1697: deba@2079: protected: deba@2079: deba@2079: AlterableSplitGraphAdaptor() : Parent() {} deba@2079: deba@2079: public: deba@2079: deba@2079: typedef InvalidType NodeNotifier; deba@2079: typedef InvalidType EdgeNotifier; deba@2079: deba@2079: }; deba@2079: deba@2079: template deba@2079: class AlterableSplitGraphAdaptor< deba@2079: _Graph, deba@2079: typename enable_if::type, deba@2079: EdgeEnable> deba@2079: : public GraphAdaptorExtender > { deba@2079: public: deba@2079: deba@2079: typedef GraphAdaptorExtender > Parent; deba@2079: typedef _Graph Graph; deba@2079: deba@2079: typedef typename Graph::Node GraphNode; deba@2079: typedef typename Graph::Edge GraphEdge; deba@2079: deba@2079: typedef typename Parent::Node Node; deba@2079: typedef typename Parent::Edge Edge; deba@2079: deba@2079: protected: deba@2079: deba@2079: AlterableSplitGraphAdaptor() deba@2079: : Parent(), node_notifier(*this), node_notifier_proxy(*this) {} deba@2079: deba@2079: void setGraph(_Graph& graph) { deba@2079: Parent::setGraph(graph); deba@2079: node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode())); deba@2079: } deba@2079: deba@2079: public: deba@2079: deba@2079: ~AlterableSplitGraphAdaptor() { deba@2079: node_notifier.clear(); deba@2079: } deba@2079: deba@2079: typedef AlterationNotifier NodeNotifier; deba@2079: typedef InvalidType EdgeNotifier; deba@2079: deba@2079: NodeNotifier& getNotifier(Node) const { return node_notifier; } deba@2079: deba@2079: protected: deba@2079: deba@2079: class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase { deba@2079: public: deba@2079: deba@2079: typedef typename Graph::NodeNotifier::ObserverBase Parent; deba@2079: typedef AlterableSplitGraphAdaptor AdaptorBase; deba@1697: deba@2079: NodeNotifierProxy(const AdaptorBase& _adaptor) deba@2079: : Parent(), adaptor(&_adaptor) { deba@2079: } deba@2079: deba@2079: virtual ~NodeNotifierProxy() { deba@2079: if (Parent::attached()) { deba@2079: Parent::detach(); deba@2079: } deba@2079: } deba@2079: deba@2079: void setNotifier(typename Graph::NodeNotifier& graph_notifier) { deba@2079: Parent::attach(graph_notifier); deba@2079: } deba@2079: deba@1697: deba@2079: protected: deba@2079: deba@2079: virtual void add(const GraphNode& gn) { deba@2079: std::vector nodes; deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn)); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn)); deba@2079: adaptor->getNotifier(Node()).add(nodes); deba@2079: } deba@2079: deba@2079: virtual void add(const std::vector& gn) { deba@2079: std::vector nodes; deba@2079: for (int i = 0; i < (int)gn.size(); ++i) { deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); deba@2079: } deba@2079: adaptor->getNotifier(Node()).add(nodes); deba@2079: } deba@2079: deba@2079: virtual void erase(const GraphNode& gn) { deba@2079: std::vector nodes; deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn)); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn)); deba@2079: adaptor->getNotifier(Node()).erase(nodes); deba@2079: } deba@2079: deba@2079: virtual void erase(const std::vector& gn) { deba@2079: std::vector nodes; deba@2079: for (int i = 0; i < (int)gn.size(); ++i) { deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); deba@2079: } deba@2079: adaptor->getNotifier(Node()).erase(nodes); deba@2079: } deba@2079: virtual void build() { deba@2079: adaptor->getNotifier(Node()).build(); deba@2079: } deba@2079: virtual void clear() { deba@2079: adaptor->getNotifier(Node()).clear(); deba@2079: } deba@2079: deba@2079: const AdaptorBase* adaptor; deba@2079: }; deba@2079: deba@2079: deba@2079: mutable NodeNotifier node_notifier; deba@2079: deba@2079: NodeNotifierProxy node_notifier_proxy; deba@2079: deba@2079: }; deba@2079: deba@2079: template deba@2079: class AlterableSplitGraphAdaptor< deba@2079: _Graph, deba@2079: typename enable_if::type, deba@2079: typename enable_if::type> deba@2079: : public GraphAdaptorExtender > { deba@2079: public: deba@2079: deba@2079: typedef GraphAdaptorExtender > Parent; deba@2079: typedef _Graph Graph; deba@2079: deba@2079: typedef typename Graph::Node GraphNode; deba@2079: typedef typename Graph::Edge GraphEdge; deba@2079: deba@2079: typedef typename Parent::Node Node; deba@2079: typedef typename Parent::Edge Edge; deba@2079: deba@2079: protected: deba@2079: deba@2079: AlterableSplitGraphAdaptor() deba@2079: : Parent(), node_notifier(*this), edge_notifier(*this), deba@2079: node_notifier_proxy(*this), edge_notifier_proxy(*this) {} deba@2079: deba@2079: void setGraph(_Graph& graph) { deba@2079: Parent::setGraph(graph); deba@2079: node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode())); deba@2079: edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge())); deba@2079: } deba@2079: deba@2079: public: deba@2079: deba@2079: ~AlterableSplitGraphAdaptor() { deba@2079: node_notifier.clear(); deba@2079: edge_notifier.clear(); deba@2079: } deba@2079: deba@2079: typedef AlterationNotifier NodeNotifier; deba@2079: typedef AlterationNotifier EdgeNotifier; deba@2079: deba@2079: NodeNotifier& getNotifier(Node) const { return node_notifier; } deba@2079: EdgeNotifier& getNotifier(Edge) const { return edge_notifier; } deba@2079: deba@2079: protected: deba@2079: deba@2079: class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase { deba@2079: public: deba@1697: deba@2079: typedef typename Graph::NodeNotifier::ObserverBase Parent; deba@2079: typedef AlterableSplitGraphAdaptor AdaptorBase; deba@2079: deba@2079: NodeNotifierProxy(const AdaptorBase& _adaptor) deba@2079: : Parent(), adaptor(&_adaptor) { deba@2079: } deba@1697: deba@2079: virtual ~NodeNotifierProxy() { deba@2079: if (Parent::attached()) { deba@2079: Parent::detach(); deba@2079: } deba@2079: } deba@1697: deba@2079: void setNotifier(typename Graph::NodeNotifier& graph_notifier) { deba@2079: Parent::attach(graph_notifier); deba@2079: } deba@1697: deba@2079: deba@2079: protected: deba@1697: deba@2079: virtual void add(const GraphNode& gn) { deba@2079: std::vector nodes; deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn)); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn)); deba@2079: adaptor->getNotifier(Node()).add(nodes); deba@2079: adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn)); deba@2079: } deba@2079: virtual void add(const std::vector& gn) { deba@2079: std::vector nodes; deba@2079: std::vector edges; deba@2079: for (int i = 0; i < (int)gn.size(); ++i) { deba@2079: edges.push_back(AdaptorBase::Parent::edge(gn[i])); deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); deba@2079: } deba@2079: adaptor->getNotifier(Node()).add(nodes); deba@2079: adaptor->getNotifier(Edge()).add(edges); deba@2079: } deba@2079: virtual void erase(const GraphNode& gn) { deba@2079: adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn)); deba@2079: std::vector nodes; deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn)); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn)); deba@2079: adaptor->getNotifier(Node()).erase(nodes); deba@2079: } deba@2079: virtual void erase(const std::vector& gn) { deba@2079: std::vector nodes; deba@2079: std::vector edges; deba@2079: for (int i = 0; i < (int)gn.size(); ++i) { deba@2079: edges.push_back(AdaptorBase::Parent::edge(gn[i])); deba@2079: nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); deba@2079: nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); deba@2079: } deba@2079: adaptor->getNotifier(Edge()).erase(edges); deba@2079: adaptor->getNotifier(Node()).erase(nodes); deba@2079: } deba@2079: virtual void build() { deba@2079: std::vector edges; deba@2079: const typename Parent::Notifier* notifier = Parent::getNotifier(); deba@2079: GraphNode it; deba@2079: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2079: edges.push_back(AdaptorBase::Parent::edge(it)); deba@2079: } deba@2079: adaptor->getNotifier(Node()).build(); deba@2079: adaptor->getNotifier(Edge()).add(edges); deba@2079: } deba@2079: virtual void clear() { deba@2079: std::vector edges; deba@2079: const typename Parent::Notifier* notifier = Parent::getNotifier(); deba@2079: GraphNode it; deba@2079: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2079: edges.push_back(AdaptorBase::Parent::edge(it)); deba@2079: } deba@2079: adaptor->getNotifier(Edge()).erase(edges); deba@2079: adaptor->getNotifier(Node()).clear(); deba@2079: } deba@1697: deba@2079: const AdaptorBase* adaptor; deba@2079: }; deba@1697: deba@2079: class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase { deba@2079: public: deba@2079: deba@2079: typedef typename Graph::EdgeNotifier::ObserverBase Parent; deba@2079: typedef AlterableSplitGraphAdaptor AdaptorBase; deba@1697: deba@2079: EdgeNotifierProxy(const AdaptorBase& _adaptor) deba@2079: : Parent(), adaptor(&_adaptor) { deba@2079: } deba@1697: deba@2079: virtual ~EdgeNotifierProxy() { deba@2079: if (Parent::attached()) { deba@2079: Parent::detach(); deba@2079: } deba@2079: } deba@1697: deba@2079: void setNotifier(typename Graph::EdgeNotifier& graph_notifier) { deba@2079: Parent::attach(graph_notifier); deba@2079: } deba@1697: deba@2079: deba@2079: protected: deba@1697: deba@2079: virtual void add(const GraphEdge& ge) { deba@2079: adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge)); deba@2079: } deba@2079: virtual void add(const std::vector& ge) { deba@2079: std::vector edges; deba@2079: for (int i = 0; i < (int)ge.size(); ++i) { deba@2079: edges.push_back(AdaptorBase::edge(ge[i])); deba@2079: } deba@2079: adaptor->getNotifier(Edge()).add(edges); deba@2079: } deba@2079: virtual void erase(const GraphEdge& ge) { deba@2079: adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge)); deba@2079: } deba@2079: virtual void erase(const std::vector& ge) { deba@2079: std::vector edges; deba@2079: for (int i = 0; i < (int)ge.size(); ++i) { deba@2079: edges.push_back(AdaptorBase::edge(ge[i])); deba@2079: } deba@2079: adaptor->getNotifier(Edge()).erase(edges); deba@2079: } deba@2079: virtual void build() { deba@2079: std::vector edges; deba@2079: const typename Parent::Notifier* notifier = Parent::getNotifier(); deba@2079: GraphEdge it; deba@2079: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2079: edges.push_back(AdaptorBase::Parent::edge(it)); deba@2079: } deba@2079: adaptor->getNotifier(Edge()).add(edges); deba@2079: } deba@2079: virtual void clear() { deba@2079: std::vector edges; deba@2079: const typename Parent::Notifier* notifier = Parent::getNotifier(); deba@2079: GraphEdge it; deba@2079: for (notifier->first(it); it != INVALID; notifier->next(it)) { deba@2079: edges.push_back(AdaptorBase::Parent::edge(it)); deba@2079: } deba@2079: adaptor->getNotifier(Edge()).erase(edges); deba@2079: } deba@1697: deba@2079: const AdaptorBase* adaptor; deba@2079: }; deba@2079: deba@2079: deba@2079: mutable NodeNotifier node_notifier; deba@2079: mutable EdgeNotifier edge_notifier; deba@2079: deba@2079: NodeNotifierProxy node_notifier_proxy; deba@2079: EdgeNotifierProxy edge_notifier_proxy; deba@2079: deba@2079: }; deba@2079: deba@2079: /// \ingroup graph_adaptors deba@2079: /// deba@2081: /// \brief Split graph adaptor class deba@2079: /// deba@2079: /// This is an graph adaptor which splits all node into an in-node deba@2079: /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$ deba@2079: /// node in the graph with two node, \f$ u_{in} \f$ node and deba@2079: /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the deba@2079: /// original graph the new target of the edge will be \f$ u_{in} \f$ and deba@2079: /// similarly the source of the original \f$ (u, v) \f$ edge will be deba@2079: /// \f$ u_{out} \f$. The adaptor will add for each node in the deba@2079: /// original graph an additional edge which will connect deba@2079: /// \f$ (u_{in}, u_{out}) \f$. deba@2079: /// deba@2079: /// The aim of this class is to run algorithm with node costs if the deba@2079: /// algorithm can use directly just edge costs. In this case we should use deba@2079: /// a \c SplitGraphAdaptor and set the node cost of the graph to the deba@2079: /// bind edge in the adapted graph. deba@2079: /// deba@2079: /// By example a maximum flow algoritm can compute how many edge deba@2079: /// disjoint paths are in the graph. But we would like to know how deba@2079: /// many node disjoint paths are in the graph. First we have to deba@2079: /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow deba@2079: /// algorithm on the adapted graph. The bottleneck of the flow will deba@2079: /// be the bind edges which bounds the flow with the count of the deba@2079: /// node disjoint paths. deba@2079: /// deba@2079: ///\code deba@2079: /// deba@2079: /// typedef SplitGraphAdaptor SGraph; deba@2079: /// deba@2079: /// SGraph sgraph(graph); deba@2079: /// deba@2079: /// typedef ConstMap SCapacity; deba@2079: /// SCapacity scapacity(1); deba@2079: /// deba@2079: /// SGraph::EdgeMap sflow(sgraph); deba@2079: /// deba@2079: /// Preflow deba@2079: /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target), deba@2079: /// scapacity, sflow); deba@2079: /// deba@2079: /// spreflow.run(); deba@2079: /// deba@2079: ///\endcode deba@2079: /// deba@2079: /// The result of the mamixum flow on the original graph deba@2079: /// shows the next figure: deba@2079: /// deba@2079: /// \image html edge_disjoint.png deba@2079: /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth deba@2079: /// deba@2079: /// And the maximum flow on the adapted graph: deba@2079: /// deba@2079: /// \image html node_disjoint.png deba@2079: /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth deba@2079: /// deba@2079: /// The second solution contains just 3 disjoint paths while the first 4. deba@2084: /// The full code can be found in the \ref disjoint_paths_demo.cc demo file. deba@2079: /// deba@2079: /// This graph adaptor is fully conform to the alpar@2260: /// \ref concepts::Graph "Graph" concept and deba@2079: /// contains some additional member functions and types. The deba@2079: /// documentation of some member functions may be found just in the deba@2079: /// SplitGraphAdaptorBase class. deba@2079: /// deba@2079: /// \sa SplitGraphAdaptorBase deba@2079: template deba@2079: class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> { deba@2079: public: deba@2079: typedef AlterableSplitGraphAdaptor<_Graph> Parent; deba@2079: deba@2079: typedef typename Parent::Node Node; deba@2079: typedef typename Parent::Edge Edge; deba@2079: deba@2079: /// \brief Constructor of the adaptor. deba@2079: /// deba@2079: /// Constructor of the adaptor. deba@2079: SplitGraphAdaptor(_Graph& graph) { deba@2079: Parent::setGraph(graph); deba@2079: } deba@2079: deba@2079: /// \brief NodeMap combined from two original NodeMap deba@2079: /// deba@2079: /// This class adapt two of the original graph NodeMap to deba@2079: /// get a node map on the adapted graph. deba@2079: template deba@2079: class CombinedNodeMap { deba@2079: public: deba@2079: deba@2079: typedef Node Key; deba@2079: typedef typename InNodeMap::Value Value; deba@2079: deba@2079: /// \brief Constructor deba@2079: /// deba@2079: /// Constructor. deba@2079: CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap) deba@2079: : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {} deba@2079: deba@2079: /// \brief The subscript operator. deba@2079: /// deba@2079: /// The subscript operator. deba@2079: Value& operator[](const Key& key) { deba@2079: if (Parent::inNode(key)) { deba@2079: return inNodeMap[key]; deba@2079: } else { deba@2079: return outNodeMap[key]; deba@2079: } deba@2079: } deba@2079: deba@2079: /// \brief The const subscript operator. deba@2079: /// deba@2079: /// The const subscript operator. deba@2079: Value operator[](const Key& key) const { deba@2079: if (Parent::inNode(key)) { deba@2079: return inNodeMap[key]; deba@2079: } else { deba@2079: return outNodeMap[key]; deba@2079: } deba@2079: } deba@2079: deba@2079: /// \brief The setter function of the map. deba@2079: /// deba@2079: /// The setter function of the map. deba@2079: void set(const Key& key, const Value& value) { deba@2079: if (Parent::inNode(key)) { deba@2079: inNodeMap.set(key, value); deba@2079: } else { deba@2079: outNodeMap.set(key, value); deba@2079: } deba@2079: } deba@2079: deba@2079: private: deba@2079: deba@2079: InNodeMap& inNodeMap; deba@2079: OutNodeMap& outNodeMap; deba@2079: deba@2079: }; deba@2079: deba@2079: deba@2079: /// \brief Just gives back a combined node map. deba@2079: /// deba@2079: /// Just gives back a combined node map. deba@2079: template deba@2079: static CombinedNodeMap deba@2079: combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { deba@2079: return CombinedNodeMap(in_map, out_map); deba@2079: } deba@2079: deba@2079: template deba@2079: static CombinedNodeMap deba@2079: combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { deba@2079: return CombinedNodeMap(in_map, out_map); deba@2079: } deba@2079: deba@2079: template deba@2079: static CombinedNodeMap deba@2079: combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { deba@2079: return CombinedNodeMap(in_map, out_map); deba@2079: } deba@2079: deba@2079: template deba@2079: static CombinedNodeMap deba@2079: combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { deba@2079: return CombinedNodeMap(in_map, out_map); deba@2079: } deba@2079: deba@2079: /// \brief EdgeMap combined from an original EdgeMap and NodeMap deba@2079: /// deba@2079: /// This class adapt an original graph EdgeMap and NodeMap to deba@2079: /// get an edge map on the adapted graph. deba@2079: template deba@2079: class CombinedEdgeMap deba@2079: : public MapBase { deba@2079: public: deba@2079: typedef MapBase Parent; deba@2079: deba@2079: typedef typename Parent::Key Key; deba@2079: typedef typename Parent::Value Value; deba@2079: deba@2079: /// \brief Constructor deba@2079: /// deba@2079: /// Constructor. deba@2079: CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map) deba@2079: : edge_map(_edge_map), node_map(_node_map) {} deba@2079: deba@2079: /// \brief The subscript operator. deba@2079: /// deba@2079: /// The subscript operator. deba@2079: void set(const Edge& edge, const Value& val) { deba@2079: if (Parent::origEdge(edge)) { deba@2079: edge_map.set(edge, val); deba@2079: } else { deba@2079: node_map.set(edge, val); deba@2079: } deba@2079: } deba@2079: deba@2079: /// \brief The const subscript operator. deba@2079: /// deba@2079: /// The const subscript operator. deba@2079: Value operator[](const Key& edge) const { deba@2079: if (Parent::origEdge(edge)) { deba@2079: return edge_map[edge]; deba@2079: } else { deba@2079: return node_map[edge]; deba@2079: } deba@2079: } deba@2079: deba@2079: /// \brief The const subscript operator. deba@2079: /// deba@2079: /// The const subscript operator. deba@2079: Value& operator[](const Key& edge) { deba@2079: if (Parent::origEdge(edge)) { deba@2079: return edge_map[edge]; deba@2079: } else { deba@2079: return node_map[edge]; deba@2079: } deba@2079: } deba@2079: deba@2079: private: deba@2079: GraphEdgeMap& edge_map; deba@2079: GraphNodeMap& node_map; deba@2079: }; deba@2079: deba@2079: /// \brief Just gives back a combined edge map. deba@2079: /// deba@2079: /// Just gives back a combined edge map. deba@2079: template deba@2079: static CombinedEdgeMap deba@2079: combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) { deba@2079: return CombinedEdgeMap(edge_map, node_map); deba@2079: } deba@2079: deba@2079: template deba@2079: static CombinedEdgeMap deba@2079: combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) { deba@2079: return CombinedEdgeMap(edge_map, node_map); deba@2079: } deba@2079: deba@2079: template deba@2079: static CombinedEdgeMap deba@2079: combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) { deba@2079: return CombinedEdgeMap(edge_map, node_map); deba@2079: } deba@2079: deba@2079: template deba@2079: static CombinedEdgeMap deba@2079: combinedEdgeMap(const GraphEdgeMap& edge_map, deba@2079: const GraphNodeMap& node_map) { deba@2079: return CombinedEdgeMap(edge_map, node_map); deba@2079: } deba@2079: deba@2079: }; deba@2079: deba@2084: /// \brief Just gives back a split graph adaptor deba@2084: /// deba@2084: /// Just gives back a split graph adaptor deba@2084: template deba@2084: SplitGraphAdaptor deba@2084: splitGraphAdaptor(const Graph& graph) { deba@2084: return SplitGraphAdaptor(graph); deba@2084: } deba@2084: deba@1697: alpar@921: } //namespace lemon marci@556: alpar@1401: #endif //LEMON_GRAPH_ADAPTOR_H marci@556: