klao@946: /* -*- C++ -*- ladanyi@1435: * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library klao@946: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). klao@946: * klao@946: * Permission to use, modify and distribute this software is granted klao@946: * provided that this copyright notice appears in all copies. For klao@946: * precise terms see the accompanying LICENSE file. klao@946: * klao@946: * This software is provided "AS IS" with no warranty of any kind, klao@946: * express or implied, and with no claim as to its suitability for any klao@946: * purpose. klao@946: * klao@946: */ klao@946: klao@946: #ifndef LEMON_GRAPH_UTILS_H klao@946: #define LEMON_GRAPH_UTILS_H klao@946: klao@946: #include deba@1419: #include alpar@1402: #include deba@1695: #include klao@946: klao@946: #include klao@977: #include deba@1413: #include deba@1720: #include alpar@1459: #include klao@946: alpar@947: ///\ingroup gutils klao@946: ///\file alpar@947: ///\brief Graph utilities. klao@946: /// alpar@964: /// klao@946: klao@946: klao@946: namespace lemon { klao@946: deba@1267: /// \addtogroup gutils deba@1267: /// @{ alpar@947: klao@946: /// \brief Function to count the items in the graph. klao@946: /// athos@1540: /// This function counts the items (nodes, edges etc) in the graph. klao@946: /// The complexity of the function is O(n) because klao@946: /// it iterates on all of the items. klao@946: klao@946: template klao@977: inline int countItems(const Graph& g) { klao@946: int num = 0; klao@977: for (ItemIt it(g); it != INVALID; ++it) { klao@946: ++num; klao@946: } klao@946: return num; klao@946: } klao@946: klao@977: // Node counting: klao@977: klao@977: template klao@977: inline klao@977: typename enable_if::type klao@977: _countNodes(const Graph &g) { klao@977: return g.nodeNum(); klao@977: } klao@977: klao@977: template klao@977: inline int _countNodes(Wrap w) { klao@977: return countItems(w.value); klao@977: } klao@977: klao@946: /// \brief Function to count the nodes in the graph. klao@946: /// klao@946: /// This function counts the nodes in the graph. klao@946: /// The complexity of the function is O(n) but for some athos@1526: /// graph structures it is specialized to run in O(1). klao@977: /// klao@977: /// \todo refer how to specialize it klao@946: klao@946: template klao@977: inline int countNodes(const Graph& g) { klao@977: return _countNodes(g); klao@977: } klao@977: klao@977: // Edge counting: klao@977: klao@977: template klao@977: inline klao@977: typename enable_if::type klao@977: _countEdges(const Graph &g) { klao@977: return g.edgeNum(); klao@977: } klao@977: klao@977: template klao@977: inline int _countEdges(Wrap w) { klao@977: return countItems(w.value); klao@946: } klao@946: klao@946: /// \brief Function to count the edges in the graph. klao@946: /// klao@946: /// This function counts the edges in the graph. klao@946: /// The complexity of the function is O(e) but for some athos@1526: /// graph structures it is specialized to run in O(1). klao@977: klao@946: template klao@977: inline int countEdges(const Graph& g) { klao@977: return _countEdges(g); klao@946: } klao@946: klao@1053: // Undirected edge counting: klao@1053: klao@1053: template klao@1053: inline klao@1053: typename enable_if::type klao@1053: _countUndirEdges(const Graph &g) { klao@1053: return g.undirEdgeNum(); klao@1053: } klao@1053: klao@1053: template klao@1053: inline int _countUndirEdges(Wrap w) { klao@1053: return countItems(w.value); klao@1053: } klao@1053: athos@1526: /// \brief Function to count the undirected edges in the graph. klao@946: /// athos@1526: /// This function counts the undirected edges in the graph. klao@946: /// The complexity of the function is O(e) but for some athos@1540: /// graph structures it is specialized to run in O(1). klao@1053: klao@946: template klao@1053: inline int countUndirEdges(const Graph& g) { klao@1053: return _countUndirEdges(g); klao@946: } klao@946: klao@977: klao@1053: klao@946: template klao@946: inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { klao@946: int num = 0; klao@946: for (DegIt it(_g, _n); it != INVALID; ++it) { klao@946: ++num; klao@946: } klao@946: return num; klao@946: } alpar@967: deba@1531: /// \brief Function to count the number of the out-edges from node \c n. deba@1531: /// deba@1531: /// This function counts the number of the out-edges from node \c n deba@1531: /// in the graph. deba@1531: template deba@1531: inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { deba@1531: return countNodeDegree(_g, _n); deba@1531: } deba@1531: deba@1531: /// \brief Function to count the number of the in-edges to node \c n. deba@1531: /// deba@1531: /// This function counts the number of the in-edges to node \c n deba@1531: /// in the graph. deba@1531: template deba@1531: inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { deba@1531: return countNodeDegree(_g, _n); deba@1531: } deba@1531: deba@1704: /// \brief Function to count the number of the inc-edges to node \c n. deba@1679: /// deba@1704: /// This function counts the number of the inc-edges to node \c n deba@1679: /// in the graph. deba@1679: template deba@1679: inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { deba@1679: return countNodeDegree(_g, _n); deba@1679: } deba@1679: deba@1531: deba@1565: template deba@1565: inline deba@1565: typename enable_if::type deba@1565: _findEdge(const Graph &g, deba@1565: typename Graph::Node u, typename Graph::Node v, deba@1565: typename Graph::Edge prev = INVALID) { deba@1565: return g.findEdge(u, v, prev); deba@1565: } alpar@967: deba@1565: template deba@1565: inline typename Graph::Edge deba@1565: _findEdge(Wrap w, deba@1565: typename Graph::Node u, deba@1565: typename Graph::Node v, deba@1565: typename Graph::Edge prev = INVALID) { deba@1565: const Graph& g = w.value; deba@1565: if (prev == INVALID) { deba@1565: typename Graph::OutEdgeIt e(g, u); deba@1565: while (e != INVALID && g.target(e) != v) ++e; deba@1565: return e; deba@1565: } else { deba@1565: typename Graph::OutEdgeIt e(g, prev); ++e; deba@1565: while (e != INVALID && g.target(e) != v) ++e; deba@1565: return e; deba@1565: } deba@1565: } deba@1565: deba@1565: /// \brief Finds an edge between two nodes of a graph. deba@1565: /// alpar@967: /// Finds an edge from node \c u to node \c v in graph \c g. alpar@967: /// alpar@967: /// If \c prev is \ref INVALID (this is the default value), then alpar@967: /// it finds the first edge from \c u to \c v. Otherwise it looks for alpar@967: /// the next edge from \c u to \c v after \c prev. alpar@967: /// \return The found edge or \ref INVALID if there is no such an edge. alpar@967: /// alpar@967: /// Thus you can iterate through each edge from \c u to \c v as it follows. alpar@967: /// \code alpar@967: /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { alpar@967: /// ... alpar@967: /// } alpar@967: /// \endcode deba@1565: // /// \todo We may want to use the "GraphBase" deba@1565: // /// interface here... alpar@967: template deba@1565: inline typename Graph::Edge findEdge(const Graph &g, deba@1565: typename Graph::Node u, deba@1565: typename Graph::Node v, deba@1565: typename Graph::Edge prev = INVALID) { deba@1565: return _findEdge(g, u, v, prev); alpar@967: } deba@1531: deba@1565: /// \brief Iterator for iterating on edges connected the same nodes. deba@1565: /// deba@1565: /// Iterator for iterating on edges connected the same nodes. It is deba@1565: /// higher level interface for the findEdge() function. You can alpar@1591: /// use it the following way: deba@1565: /// \code deba@1565: /// for (ConEdgeIt it(g, src, trg); it != INVALID; ++it) { deba@1565: /// ... deba@1565: /// } deba@1565: /// \endcode deba@1565: /// deba@1565: /// \author Balazs Dezso deba@1565: template deba@1565: class ConEdgeIt : public _Graph::Edge { deba@1565: public: deba@1565: deba@1565: typedef _Graph Graph; deba@1565: typedef typename Graph::Edge Parent; deba@1565: deba@1565: typedef typename Graph::Edge Edge; deba@1565: typedef typename Graph::Node Node; deba@1565: deba@1565: /// \brief Constructor. deba@1565: /// deba@1565: /// Construct a new ConEdgeIt iterating on the edges which deba@1565: /// connects the \c u and \c v node. deba@1565: ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) { deba@1565: Parent::operator=(findEdge(graph, u, v)); deba@1565: } deba@1565: deba@1565: /// \brief Constructor. deba@1565: /// deba@1565: /// Construct a new ConEdgeIt which continues the iterating from deba@1565: /// the \c e edge. deba@1565: ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {} deba@1565: deba@1565: /// \brief Increment operator. deba@1565: /// deba@1565: /// It increments the iterator and gives back the next edge. deba@1565: ConEdgeIt& operator++() { deba@1565: Parent::operator=(findEdge(graph, graph.source(*this), deba@1565: graph.target(*this), *this)); deba@1565: return *this; deba@1565: } deba@1565: private: deba@1565: const Graph& graph; deba@1565: }; deba@1565: deba@1704: template deba@1704: inline deba@1704: typename enable_if< deba@1704: typename Graph::FindEdgeTag, deba@1704: typename Graph::UndirEdge>::type deba@1704: _findUndirEdge(const Graph &g, deba@1704: typename Graph::Node u, typename Graph::Node v, deba@1704: typename Graph::UndirEdge prev = INVALID) { deba@1704: return g.findUndirEdge(u, v, prev); deba@1704: } deba@1704: deba@1704: template deba@1704: inline typename Graph::UndirEdge deba@1704: _findUndirEdge(Wrap w, deba@1704: typename Graph::Node u, deba@1704: typename Graph::Node v, deba@1704: typename Graph::UndirEdge prev = INVALID) { deba@1704: const Graph& g = w.value; deba@1704: if (prev == INVALID) { deba@1704: typename Graph::OutEdgeIt e(g, u); deba@1704: while (e != INVALID && g.target(e) != v) ++e; deba@1704: return e; deba@1704: } else { deba@1704: typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e; deba@1704: while (e != INVALID && g.target(e) != v) ++e; deba@1704: return e; deba@1704: } deba@1704: } deba@1704: deba@1704: /// \brief Finds an undir edge between two nodes of a graph. deba@1704: /// deba@1704: /// Finds an undir edge from node \c u to node \c v in graph \c g. deba@1704: /// deba@1704: /// If \c prev is \ref INVALID (this is the default value), then deba@1704: /// it finds the first edge from \c u to \c v. Otherwise it looks for deba@1704: /// the next edge from \c u to \c v after \c prev. deba@1704: /// \return The found edge or \ref INVALID if there is no such an edge. deba@1704: /// deba@1704: /// Thus you can iterate through each edge from \c u to \c v as it follows. deba@1704: /// \code deba@1704: /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID; deba@1704: /// e = findUndirEdge(g,u,v,e)) { deba@1704: /// ... deba@1704: /// } deba@1704: /// \endcode deba@1704: // /// \todo We may want to use the "GraphBase" deba@1704: // /// interface here... deba@1704: template deba@1704: inline typename Graph::UndirEdge deba@1704: findUndirEdge(const Graph &g, deba@1704: typename Graph::Node u, deba@1704: typename Graph::Node v, deba@1704: typename Graph::UndirEdge prev = INVALID) { deba@1704: return _findUndirEdge(g, u, v, prev); deba@1704: } deba@1704: deba@1704: /// \brief Iterator for iterating on undir edges connected the same nodes. deba@1704: /// deba@1704: /// Iterator for iterating on undir edges connected the same nodes. It is deba@1704: /// higher level interface for the findUndirEdge() function. You can deba@1704: /// use it the following way: deba@1704: /// \code deba@1704: /// for (ConUndirEdgeIt it(g, src, trg); it != INVALID; ++it) { deba@1704: /// ... deba@1704: /// } deba@1704: /// \endcode deba@1704: /// deba@1704: /// \author Balazs Dezso deba@1704: template deba@1704: class ConUndirEdgeIt : public _Graph::UndirEdge { deba@1704: public: deba@1704: deba@1704: typedef _Graph Graph; deba@1704: typedef typename Graph::UndirEdge Parent; deba@1704: deba@1704: typedef typename Graph::UndirEdge UndirEdge; deba@1704: typedef typename Graph::Node Node; deba@1704: deba@1704: /// \brief Constructor. deba@1704: /// deba@1704: /// Construct a new ConUndirEdgeIt iterating on the edges which deba@1704: /// connects the \c u and \c v node. deba@1704: ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) { deba@1704: Parent::operator=(findUndirEdge(graph, u, v)); deba@1704: } deba@1704: deba@1704: /// \brief Constructor. deba@1704: /// deba@1704: /// Construct a new ConUndirEdgeIt which continues the iterating from deba@1704: /// the \c e edge. deba@1704: ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {} deba@1704: deba@1704: /// \brief Increment operator. deba@1704: /// deba@1704: /// It increments the iterator and gives back the next edge. deba@1704: ConUndirEdgeIt& operator++() { deba@1704: Parent::operator=(findUndirEdge(graph, graph.source(*this), deba@1704: graph.target(*this), *this)); deba@1704: return *this; deba@1704: } deba@1704: private: deba@1704: const Graph& graph; deba@1704: }; deba@1704: athos@1540: /// \brief Copy a map. alpar@964: /// alpar@1547: /// This function copies the \c source map to the \c target map. It uses the athos@1540: /// given iterator to iterate on the data structure and it uses the \c ref athos@1540: /// mapping to convert the source's keys to the target's keys. deba@1531: template deba@1531: void copyMap(Target& target, const Source& source, deba@1531: ItemIt it, const Ref& ref) { deba@1531: for (; it != INVALID; ++it) { deba@1531: target[ref[it]] = source[it]; klao@946: } klao@946: } klao@946: deba@1531: /// \brief Copy the source map to the target map. deba@1531: /// deba@1531: /// Copy the \c source map to the \c target map. It uses the given iterator deba@1531: /// to iterate on the data structure. deba@1531: template deba@1531: void copyMap(Target& target, const Source& source, ItemIt it) { deba@1531: for (; it != INVALID; ++it) { deba@1531: target[it] = source[it]; klao@946: } klao@946: } klao@946: athos@1540: /// \brief Class to copy a graph. deba@1531: /// athos@1540: /// Class to copy a graph to an other graph (duplicate a graph). The athos@1540: /// simplest way of using it is through the \c copyGraph() function. deba@1531: template deba@1267: class GraphCopy { deba@1531: public: deba@1531: typedef typename Source::Node Node; deba@1531: typedef typename Source::NodeIt NodeIt; deba@1531: typedef typename Source::Edge Edge; deba@1531: typedef typename Source::EdgeIt EdgeIt; klao@946: deba@1531: typedef typename Source::template NodeMapNodeRefMap; deba@1531: typedef typename Source::template EdgeMapEdgeRefMap; klao@946: deba@1531: /// \brief Constructor for the GraphCopy. deba@1531: /// deba@1531: /// It copies the content of the \c _source graph into the deba@1531: /// \c _target graph. It creates also two references, one beetween deba@1531: /// the two nodeset and one beetween the two edgesets. deba@1531: GraphCopy(Target& _target, const Source& _source) deba@1531: : source(_source), target(_target), deba@1531: nodeRefMap(_source), edgeRefMap(_source) { deba@1531: for (NodeIt it(source); it != INVALID; ++it) { deba@1531: nodeRefMap[it] = target.addNode(); deba@1531: } deba@1531: for (EdgeIt it(source); it != INVALID; ++it) { deba@1531: edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], deba@1531: nodeRefMap[source.target(it)]); deba@1531: } deba@1267: } klao@946: deba@1531: /// \brief Copies the node references into the given map. deba@1531: /// deba@1531: /// Copies the node references into the given map. deba@1531: template deba@1531: const GraphCopy& nodeRef(NodeRef& map) const { deba@1531: for (NodeIt it(source); it != INVALID; ++it) { deba@1531: map.set(it, nodeRefMap[it]); deba@1531: } deba@1531: return *this; deba@1267: } deba@1531: deba@1531: /// \brief Reverse and copies the node references into the given map. deba@1531: /// deba@1531: /// Reverse and copies the node references into the given map. deba@1531: template deba@1531: const GraphCopy& nodeCrossRef(NodeRef& map) const { deba@1531: for (NodeIt it(source); it != INVALID; ++it) { deba@1531: map.set(nodeRefMap[it], it); deba@1531: } deba@1531: return *this; deba@1531: } deba@1531: deba@1531: /// \brief Copies the edge references into the given map. deba@1531: /// deba@1531: /// Copies the edge references into the given map. deba@1531: template deba@1531: const GraphCopy& edgeRef(EdgeRef& map) const { deba@1531: for (EdgeIt it(source); it != INVALID; ++it) { deba@1531: map.set(it, edgeRefMap[it]); deba@1531: } deba@1531: return *this; deba@1531: } deba@1531: deba@1531: /// \brief Reverse and copies the edge references into the given map. deba@1531: /// deba@1531: /// Reverse and copies the edge references into the given map. deba@1531: template deba@1531: const GraphCopy& edgeCrossRef(EdgeRef& map) const { deba@1531: for (EdgeIt it(source); it != INVALID; ++it) { deba@1531: map.set(edgeRefMap[it], it); deba@1531: } deba@1531: return *this; deba@1531: } deba@1531: deba@1531: /// \brief Make copy of the given map. deba@1531: /// deba@1531: /// Makes copy of the given map for the newly created graph. deba@1531: /// The new map's key type is the target graph's node type, deba@1531: /// and the copied map's key type is the source graph's node deba@1531: /// type. deba@1531: template deba@1531: const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const { deba@1531: copyMap(tMap, sMap, NodeIt(source), nodeRefMap); deba@1531: return *this; deba@1531: } deba@1531: deba@1531: /// \brief Make copy of the given map. deba@1531: /// deba@1531: /// Makes copy of the given map for the newly created graph. deba@1531: /// The new map's key type is the target graph's edge type, deba@1531: /// and the copied map's key type is the source graph's edge deba@1531: /// type. deba@1531: template deba@1531: const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const { deba@1531: copyMap(tMap, sMap, EdgeIt(source), edgeRefMap); deba@1531: return *this; deba@1531: } deba@1531: deba@1531: /// \brief Gives back the stored node references. deba@1531: /// deba@1531: /// Gives back the stored node references. deba@1531: const NodeRefMap& nodeRef() const { deba@1531: return nodeRefMap; deba@1531: } deba@1531: deba@1531: /// \brief Gives back the stored edge references. deba@1531: /// deba@1531: /// Gives back the stored edge references. deba@1531: const EdgeRefMap& edgeRef() const { deba@1531: return edgeRefMap; deba@1531: } deba@1531: deba@1720: void run() {} deba@1720: deba@1531: private: deba@1531: deba@1531: const Source& source; deba@1531: Target& target; deba@1531: deba@1531: NodeRefMap nodeRefMap; deba@1531: EdgeRefMap edgeRefMap; deba@1267: }; klao@946: deba@1531: /// \brief Copy a graph to an other graph. deba@1531: /// deba@1531: /// Copy a graph to an other graph. deba@1531: /// The usage of the function: deba@1531: /// deba@1531: /// \code deba@1531: /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); deba@1531: /// \endcode deba@1531: /// deba@1531: /// After the copy the \c nr map will contain the mapping from the deba@1531: /// source graph's nodes to the target graph's nodes and the \c ecr will athos@1540: /// contain the mapping from the target graph's edges to the source's deba@1531: /// edges. deba@1531: template deba@1531: GraphCopy copyGraph(Target& target, const Source& source) { deba@1531: return GraphCopy(target, source); deba@1531: } klao@946: deba@1720: /// \brief Class to copy an undirected graph. deba@1720: /// deba@1720: /// Class to copy an undirected graph to an other graph (duplicate a graph). deba@1720: /// The simplest way of using it is through the \c copyUndirGraph() function. deba@1720: template deba@1720: class UndirGraphCopy { deba@1720: public: deba@1720: typedef typename Source::Node Node; deba@1720: typedef typename Source::NodeIt NodeIt; deba@1720: typedef typename Source::Edge Edge; deba@1720: typedef typename Source::EdgeIt EdgeIt; deba@1720: typedef typename Source::UndirEdge UndirEdge; deba@1720: typedef typename Source::UndirEdgeIt UndirEdgeIt; deba@1720: deba@1720: typedef typename Source:: deba@1720: template NodeMap NodeRefMap; deba@1720: deba@1720: typedef typename Source:: deba@1720: template UndirEdgeMap UndirEdgeRefMap; deba@1720: deba@1720: private: deba@1720: deba@1720: struct EdgeRefMap { deba@1720: EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {} deba@1720: typedef typename Source::Edge Key; deba@1720: typedef typename Target::Edge Value; deba@1720: deba@1720: Value operator[](const Key& key) { deba@1720: return gc.target.direct(gc.undirEdgeRef[key], deba@1720: gc.target.direction(key)); deba@1720: } deba@1720: deba@1720: UndirGraphCopy& gc; deba@1720: }; deba@1720: deba@1192: public: deba@1720: deba@1720: /// \brief Constructor for the UndirGraphCopy. deba@1720: /// deba@1720: /// It copies the content of the \c _source graph into the deba@1720: /// \c _target graph. It creates also two references, one beetween deba@1720: /// the two nodeset and one beetween the two edgesets. deba@1720: UndirGraphCopy(Target& _target, const Source& _source) deba@1720: : source(_source), target(_target), deba@1720: nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) { deba@1720: for (NodeIt it(source); it != INVALID; ++it) { deba@1720: nodeRefMap[it] = target.addNode(); deba@1720: } deba@1720: for (UndirEdgeIt it(source); it != INVALID; ++it) { deba@1720: undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], deba@1720: nodeRefMap[source.target(it)]); deba@1720: } deba@1720: } deba@1720: deba@1720: /// \brief Copies the node references into the given map. deba@1720: /// deba@1720: /// Copies the node references into the given map. deba@1720: template deba@1720: const UndirGraphCopy& nodeRef(NodeRef& map) const { deba@1720: for (NodeIt it(source); it != INVALID; ++it) { deba@1720: map.set(it, nodeRefMap[it]); deba@1720: } deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Reverse and copies the node references into the given map. deba@1720: /// deba@1720: /// Reverse and copies the node references into the given map. deba@1720: template deba@1720: const UndirGraphCopy& nodeCrossRef(NodeRef& map) const { deba@1720: for (NodeIt it(source); it != INVALID; ++it) { deba@1720: map.set(nodeRefMap[it], it); deba@1720: } deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Copies the edge references into the given map. deba@1720: /// deba@1720: /// Copies the edge references into the given map. deba@1720: template deba@1720: const UndirGraphCopy& edgeRef(EdgeRef& map) const { deba@1720: for (EdgeIt it(source); it != INVALID; ++it) { deba@1720: map.set(edgeRefMap[it], it); deba@1720: } deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Reverse and copies the undirected edge references into the deba@1720: /// given map. deba@1720: /// deba@1720: /// Reverse and copies the undirected edge references into the given map. deba@1720: template deba@1720: const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const { deba@1720: for (EdgeIt it(source); it != INVALID; ++it) { deba@1720: map.set(it, edgeRefMap[it]); deba@1720: } deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Copies the undirected edge references into the given map. deba@1720: /// deba@1720: /// Copies the undirected edge references into the given map. deba@1720: template deba@1720: const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const { deba@1720: for (UndirEdgeIt it(source); it != INVALID; ++it) { deba@1720: map.set(it, undirEdgeRefMap[it]); deba@1720: } deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Reverse and copies the undirected edge references into the deba@1720: /// given map. deba@1720: /// deba@1720: /// Reverse and copies the undirected edge references into the given map. deba@1720: template deba@1720: const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const { deba@1720: for (UndirEdgeIt it(source); it != INVALID; ++it) { deba@1720: map.set(undirEdgeRefMap[it], it); deba@1720: } deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Make copy of the given map. deba@1720: /// deba@1720: /// Makes copy of the given map for the newly created graph. deba@1720: /// The new map's key type is the target graph's node type, deba@1720: /// and the copied map's key type is the source graph's node deba@1720: /// type. deba@1720: template deba@1720: const UndirGraphCopy& nodeMap(TargetMap& tMap, deba@1720: const SourceMap& sMap) const { deba@1720: copyMap(tMap, sMap, NodeIt(source), nodeRefMap); deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Make copy of the given map. deba@1720: /// deba@1720: /// Makes copy of the given map for the newly created graph. deba@1720: /// The new map's key type is the target graph's edge type, deba@1720: /// and the copied map's key type is the source graph's edge deba@1720: /// type. deba@1720: template deba@1720: const UndirGraphCopy& edgeMap(TargetMap& tMap, deba@1720: const SourceMap& sMap) const { deba@1720: copyMap(tMap, sMap, EdgeIt(source), edgeRefMap); deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Make copy of the given map. deba@1720: /// deba@1720: /// Makes copy of the given map for the newly created graph. deba@1720: /// The new map's key type is the target graph's edge type, deba@1720: /// and the copied map's key type is the source graph's edge deba@1720: /// type. deba@1720: template deba@1720: const UndirGraphCopy& undirEdgeMap(TargetMap& tMap, deba@1720: const SourceMap& sMap) const { deba@1720: copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap); deba@1720: return *this; deba@1720: } deba@1720: deba@1720: /// \brief Gives back the stored node references. deba@1720: /// deba@1720: /// Gives back the stored node references. deba@1720: const NodeRefMap& nodeRef() const { deba@1720: return nodeRefMap; deba@1720: } deba@1720: deba@1720: /// \brief Gives back the stored edge references. deba@1720: /// deba@1720: /// Gives back the stored edge references. deba@1720: const EdgeRefMap& edgeRef() const { deba@1720: return edgeRefMap; deba@1720: } deba@1720: deba@1720: /// \brief Gives back the stored undir edge references. deba@1720: /// deba@1720: /// Gives back the stored undir edge references. deba@1720: const UndirEdgeRefMap& undirEdgeRef() const { deba@1720: return undirEdgeRefMap; deba@1720: } deba@1720: deba@1720: void run() {} deba@1720: deba@1720: private: deba@1192: deba@1720: const Source& source; deba@1720: Target& target; alpar@947: deba@1720: NodeRefMap nodeRefMap; deba@1720: EdgeRefMap edgeRefMap; deba@1720: UndirEdgeRefMap undirEdgeRefMap; deba@1192: }; deba@1192: deba@1720: /// \brief Copy a graph to an other graph. deba@1720: /// deba@1720: /// Copy a graph to an other graph. deba@1720: /// The usage of the function: deba@1720: /// deba@1720: /// \code deba@1720: /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); deba@1720: /// \endcode deba@1720: /// deba@1720: /// After the copy the \c nr map will contain the mapping from the deba@1720: /// source graph's nodes to the target graph's nodes and the \c ecr will deba@1720: /// contain the mapping from the target graph's edges to the source's deba@1720: /// edges. deba@1720: template deba@1720: UndirGraphCopy deba@1720: copyUndirGraph(Target& target, const Source& source) { deba@1720: return UndirGraphCopy(target, source); deba@1720: } deba@1192: deba@1192: deba@1192: /// @} alpar@1402: alpar@1402: /// \addtogroup graph_maps alpar@1402: /// @{ alpar@1402: deba@1413: /// Provides an immutable and unique id for each item in the graph. deba@1413: athos@1540: /// The IdMap class provides a unique and immutable id for each item of the athos@1540: /// same type (e.g. node) in the graph. This id is
  • \b unique: athos@1540: /// different items (nodes) get different ids
  • \b immutable: the id of an athos@1540: /// item (node) does not change (even if you delete other nodes).
athos@1540: /// Through this map you get access (i.e. can read) the inner id values of athos@1540: /// the items stored in the graph. This map can be inverted with its member athos@1540: /// class \c InverseMap. deba@1413: /// deba@1413: template deba@1413: class IdMap { deba@1413: public: deba@1413: typedef _Graph Graph; deba@1413: typedef int Value; deba@1413: typedef _Item Item; deba@1413: typedef _Item Key; deba@1413: deba@1413: /// \brief Constructor. deba@1413: /// deba@1413: /// Constructor for creating id map. deba@1413: IdMap(const Graph& _graph) : graph(&_graph) {} deba@1413: deba@1413: /// \brief Gives back the \e id of the item. deba@1413: /// deba@1413: /// Gives back the immutable and unique \e id of the map. deba@1413: int operator[](const Item& item) const { return graph->id(item);} deba@1413: deba@1413: deba@1413: private: deba@1413: const Graph* graph; deba@1413: deba@1413: public: deba@1413: athos@1540: /// \brief The class represents the inverse of its owner (IdMap). deba@1413: /// athos@1540: /// The class represents the inverse of its owner (IdMap). deba@1413: /// \see inverse() deba@1413: class InverseMap { deba@1413: public: deba@1419: deba@1413: /// \brief Constructor. deba@1413: /// deba@1413: /// Constructor for creating an id-to-item map. deba@1413: InverseMap(const Graph& _graph) : graph(&_graph) {} deba@1413: deba@1413: /// \brief Constructor. deba@1413: /// deba@1413: /// Constructor for creating an id-to-item map. deba@1413: InverseMap(const IdMap& idMap) : graph(idMap.graph) {} deba@1413: deba@1413: /// \brief Gives back the given item from its id. deba@1413: /// deba@1413: /// Gives back the given item from its id. deba@1413: /// deba@1413: Item operator[](int id) const { return graph->fromId(id, Item());} deba@1413: private: deba@1413: const Graph* graph; deba@1413: }; deba@1413: deba@1413: /// \brief Gives back the inverse of the map. deba@1413: /// athos@1540: /// Gives back the inverse of the IdMap. deba@1413: InverseMap inverse() const { return InverseMap(*graph);} deba@1413: deba@1413: }; deba@1413: deba@1413: athos@1526: /// \brief General invertable graph-map type. alpar@1402: athos@1540: /// This type provides simple invertable graph-maps. athos@1526: /// The InvertableMap wraps an arbitrary ReadWriteMap athos@1526: /// and if a key is set to a new value then store it alpar@1402: /// in the inverse map. alpar@1402: /// \param _Graph The graph type. athos@1526: /// \param _Map The map to extend with invertable functionality. alpar@1402: template < alpar@1402: typename _Graph, alpar@1402: typename _Item, alpar@1402: typename _Value, alpar@1402: typename _Map deba@1413: = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent alpar@1402: > deba@1413: class InvertableMap : protected _Map { alpar@1402: alpar@1402: public: alpar@1402: alpar@1402: typedef _Map Map; alpar@1402: typedef _Graph Graph; deba@1413: deba@1413: /// The key type of InvertableMap (Node, Edge, UndirEdge). alpar@1402: typedef typename _Map::Key Key; deba@1413: /// The value type of the InvertableMap. alpar@1402: typedef typename _Map::Value Value; alpar@1402: alpar@1402: /// \brief Constructor. alpar@1402: /// deba@1413: /// Construct a new InvertableMap for the graph. alpar@1402: /// deba@1413: InvertableMap(const Graph& graph) : Map(graph) {} alpar@1402: alpar@1402: /// \brief The setter function of the map. alpar@1402: /// deba@1413: /// Sets the mapped value. alpar@1402: void set(const Key& key, const Value& val) { alpar@1402: Value oldval = Map::operator[](key); deba@1413: typename Container::iterator it = invMap.find(oldval); alpar@1402: if (it != invMap.end() && it->second == key) { alpar@1402: invMap.erase(it); alpar@1402: } alpar@1402: invMap.insert(make_pair(val, key)); alpar@1402: Map::set(key, val); alpar@1402: } alpar@1402: alpar@1402: /// \brief The getter function of the map. alpar@1402: /// alpar@1402: /// It gives back the value associated with the key. deba@1720: Value operator[](const Key& key) const { alpar@1402: return Map::operator[](key); alpar@1402: } alpar@1402: deba@1515: protected: deba@1515: alpar@1402: /// \brief Add a new key to the map. alpar@1402: /// alpar@1402: /// Add a new key to the map. It is called by the alpar@1402: /// \c AlterationNotifier. alpar@1402: virtual void add(const Key& key) { alpar@1402: Map::add(key); alpar@1402: } alpar@1402: alpar@1402: /// \brief Erase the key from the map. alpar@1402: /// alpar@1402: /// Erase the key to the map. It is called by the alpar@1402: /// \c AlterationNotifier. alpar@1402: virtual void erase(const Key& key) { alpar@1402: Value val = Map::operator[](key); deba@1413: typename Container::iterator it = invMap.find(val); alpar@1402: if (it != invMap.end() && it->second == key) { alpar@1402: invMap.erase(it); alpar@1402: } alpar@1402: Map::erase(key); alpar@1402: } alpar@1402: alpar@1402: /// \brief Clear the keys from the map and inverse map. alpar@1402: /// alpar@1402: /// Clear the keys from the map and inverse map. It is called by the alpar@1402: /// \c AlterationNotifier. alpar@1402: virtual void clear() { alpar@1402: invMap.clear(); alpar@1402: Map::clear(); alpar@1402: } alpar@1402: deba@1413: private: deba@1413: deba@1413: typedef std::map Container; deba@1413: Container invMap; deba@1413: deba@1413: public: deba@1413: deba@1413: /// \brief The inverse map type. deba@1413: /// deba@1413: /// The inverse of this map. The subscript operator of the map deba@1413: /// gives back always the item what was last assigned to the value. deba@1413: class InverseMap { deba@1413: public: deba@1413: /// \brief Constructor of the InverseMap. deba@1413: /// deba@1413: /// Constructor of the InverseMap. deba@1413: InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {} deba@1413: deba@1413: /// The value type of the InverseMap. deba@1413: typedef typename InvertableMap::Key Value; deba@1413: /// The key type of the InverseMap. deba@1413: typedef typename InvertableMap::Value Key; deba@1413: deba@1413: /// \brief Subscript operator. deba@1413: /// deba@1413: /// Subscript operator. It gives back always the item deba@1413: /// what was last assigned to the value. deba@1413: Value operator[](const Key& key) const { deba@1413: typename Container::const_iterator it = inverted.invMap.find(key); deba@1413: return it->second; deba@1413: } deba@1413: deba@1413: private: deba@1413: const InvertableMap& inverted; deba@1413: }; deba@1413: alpar@1402: /// \brief It gives back the just readeable inverse map. alpar@1402: /// alpar@1402: /// It gives back the just readeable inverse map. deba@1413: InverseMap inverse() const { deba@1413: return InverseMap(*this); alpar@1402: } alpar@1402: alpar@1402: deba@1413: alpar@1402: }; alpar@1402: alpar@1402: /// \brief Provides a mutable, continuous and unique descriptor for each alpar@1402: /// item in the graph. alpar@1402: /// athos@1540: /// The DescriptorMap class provides a unique and continuous (but mutable) athos@1540: /// descriptor (id) for each item of the same type (e.g. node) in the athos@1540: /// graph. This id is
  • \b unique: different items (nodes) get athos@1540: /// different ids
  • \b continuous: the range of the ids is the set of athos@1540: /// integers between 0 and \c n-1, where \c n is the number of the items of athos@1540: /// this type (e.g. nodes) (so the id of a node can change if you delete an athos@1540: /// other node, i.e. this id is mutable).
This map can be inverted athos@1540: /// with its member class \c InverseMap. alpar@1402: /// alpar@1402: /// \param _Graph The graph class the \c DescriptorMap belongs to. alpar@1402: /// \param _Item The Item is the Key of the Map. It may be Node, Edge or alpar@1402: /// UndirEdge. alpar@1402: /// \param _Map A ReadWriteMap mapping from the item type to integer. alpar@1402: template < alpar@1402: typename _Graph, alpar@1402: typename _Item, deba@1413: typename _Map deba@1413: = typename ItemSetTraits<_Graph, _Item>::template Map::Parent alpar@1402: > alpar@1402: class DescriptorMap : protected _Map { alpar@1402: alpar@1402: typedef _Item Item; alpar@1402: typedef _Map Map; alpar@1402: alpar@1402: public: alpar@1402: /// The graph class of DescriptorMap. alpar@1402: typedef _Graph Graph; alpar@1402: alpar@1402: /// The key type of DescriptorMap (Node, Edge, UndirEdge). alpar@1402: typedef typename _Map::Key Key; alpar@1402: /// The value type of DescriptorMap. alpar@1402: typedef typename _Map::Value Value; alpar@1402: alpar@1402: /// \brief Constructor. alpar@1402: /// deba@1413: /// Constructor for descriptor map. alpar@1402: DescriptorMap(const Graph& _graph) : Map(_graph) { alpar@1402: build(); alpar@1402: } alpar@1402: deba@1515: protected: deba@1515: alpar@1402: /// \brief Add a new key to the map. alpar@1402: /// alpar@1402: /// Add a new key to the map. It is called by the alpar@1402: /// \c AlterationNotifier. alpar@1402: virtual void add(const Item& item) { alpar@1402: Map::add(item); alpar@1402: Map::set(item, invMap.size()); alpar@1402: invMap.push_back(item); alpar@1402: } alpar@1402: alpar@1402: /// \brief Erase the key from the map. alpar@1402: /// alpar@1402: /// Erase the key to the map. It is called by the alpar@1402: /// \c AlterationNotifier. alpar@1402: virtual void erase(const Item& item) { alpar@1402: Map::set(invMap.back(), Map::operator[](item)); alpar@1402: invMap[Map::operator[](item)] = invMap.back(); deba@1413: invMap.pop_back(); alpar@1402: Map::erase(item); alpar@1402: } alpar@1402: alpar@1402: /// \brief Build the unique map. alpar@1402: /// alpar@1402: /// Build the unique map. It is called by the alpar@1402: /// \c AlterationNotifier. alpar@1402: virtual void build() { alpar@1402: Map::build(); alpar@1402: Item it; alpar@1402: const typename Map::Graph* graph = Map::getGraph(); alpar@1402: for (graph->first(it); it != INVALID; graph->next(it)) { alpar@1402: Map::set(it, invMap.size()); alpar@1402: invMap.push_back(it); alpar@1402: } alpar@1402: } alpar@1402: alpar@1402: /// \brief Clear the keys from the map. alpar@1402: /// alpar@1402: /// Clear the keys from the map. It is called by the alpar@1402: /// \c AlterationNotifier. alpar@1402: virtual void clear() { alpar@1402: invMap.clear(); alpar@1402: Map::clear(); alpar@1402: } alpar@1402: deba@1538: public: deba@1538: deba@1552: /// \brief Swaps the position of the two items in the map. deba@1552: /// deba@1552: /// Swaps the position of the two items in the map. deba@1552: void swap(const Item& p, const Item& q) { deba@1552: int pi = Map::operator[](p); deba@1552: int qi = Map::operator[](q); deba@1552: Map::set(p, qi); deba@1552: invMap[qi] = p; deba@1552: Map::set(q, pi); deba@1552: invMap[pi] = q; deba@1552: } deba@1552: alpar@1402: /// \brief Gives back the \e descriptor of the item. alpar@1402: /// alpar@1402: /// Gives back the mutable and unique \e descriptor of the map. alpar@1402: int operator[](const Item& item) const { alpar@1402: return Map::operator[](item); alpar@1402: } alpar@1402: deba@1413: private: deba@1413: deba@1413: typedef std::vector Container; deba@1413: Container invMap; deba@1413: deba@1413: public: athos@1540: /// \brief The inverse map type of DescriptorMap. deba@1413: /// athos@1540: /// The inverse map type of DescriptorMap. deba@1413: class InverseMap { deba@1413: public: deba@1413: /// \brief Constructor of the InverseMap. deba@1413: /// deba@1413: /// Constructor of the InverseMap. deba@1413: InverseMap(const DescriptorMap& _inverted) deba@1413: : inverted(_inverted) {} deba@1413: deba@1413: deba@1413: /// The value type of the InverseMap. deba@1413: typedef typename DescriptorMap::Key Value; deba@1413: /// The key type of the InverseMap. deba@1413: typedef typename DescriptorMap::Value Key; deba@1413: deba@1413: /// \brief Subscript operator. deba@1413: /// deba@1413: /// Subscript operator. It gives back the item deba@1413: /// that the descriptor belongs to currently. deba@1413: Value operator[](const Key& key) const { deba@1413: return inverted.invMap[key]; deba@1413: } deba@1470: deba@1470: /// \brief Size of the map. deba@1470: /// deba@1470: /// Returns the size of the map. deba@1552: int size() const { deba@1470: return inverted.invMap.size(); deba@1470: } deba@1413: deba@1413: private: deba@1413: const DescriptorMap& inverted; deba@1413: }; deba@1413: alpar@1402: /// \brief Gives back the inverse of the map. alpar@1402: /// alpar@1402: /// Gives back the inverse of the map. alpar@1402: const InverseMap inverse() const { deba@1413: return InverseMap(*this); alpar@1402: } alpar@1402: }; alpar@1402: alpar@1402: /// \brief Returns the source of the given edge. alpar@1402: /// alpar@1402: /// The SourceMap gives back the source Node of the given edge. alpar@1402: /// \author Balazs Dezso alpar@1402: template alpar@1402: class SourceMap { alpar@1402: public: deba@1419: alpar@1402: typedef typename Graph::Node Value; alpar@1402: typedef typename Graph::Edge Key; alpar@1402: alpar@1402: /// \brief Constructor alpar@1402: /// alpar@1402: /// Constructor alpar@1402: /// \param _graph The graph that the map belongs to. alpar@1402: SourceMap(const Graph& _graph) : graph(_graph) {} alpar@1402: alpar@1402: /// \brief The subscript operator. alpar@1402: /// alpar@1402: /// The subscript operator. alpar@1402: /// \param edge The edge alpar@1402: /// \return The source of the edge deba@1679: Value operator[](const Key& edge) const { alpar@1402: return graph.source(edge); alpar@1402: } alpar@1402: alpar@1402: private: alpar@1402: const Graph& graph; alpar@1402: }; alpar@1402: alpar@1402: /// \brief Returns a \ref SourceMap class alpar@1402: /// alpar@1402: /// This function just returns an \ref SourceMap class. alpar@1402: /// \relates SourceMap alpar@1402: template alpar@1402: inline SourceMap sourceMap(const Graph& graph) { alpar@1402: return SourceMap(graph); alpar@1402: } alpar@1402: alpar@1402: /// \brief Returns the target of the given edge. alpar@1402: /// alpar@1402: /// The TargetMap gives back the target Node of the given edge. alpar@1402: /// \author Balazs Dezso alpar@1402: template alpar@1402: class TargetMap { alpar@1402: public: deba@1419: alpar@1402: typedef typename Graph::Node Value; alpar@1402: typedef typename Graph::Edge Key; alpar@1402: alpar@1402: /// \brief Constructor alpar@1402: /// alpar@1402: /// Constructor alpar@1402: /// \param _graph The graph that the map belongs to. alpar@1402: TargetMap(const Graph& _graph) : graph(_graph) {} alpar@1402: alpar@1402: /// \brief The subscript operator. alpar@1402: /// alpar@1402: /// The subscript operator. alpar@1536: /// \param e The edge alpar@1402: /// \return The target of the edge deba@1679: Value operator[](const Key& e) const { alpar@1536: return graph.target(e); alpar@1402: } alpar@1402: alpar@1402: private: alpar@1402: const Graph& graph; alpar@1402: }; alpar@1402: alpar@1402: /// \brief Returns a \ref TargetMap class deba@1515: /// athos@1540: /// This function just returns a \ref TargetMap class. alpar@1402: /// \relates TargetMap alpar@1402: template alpar@1402: inline TargetMap targetMap(const Graph& graph) { alpar@1402: return TargetMap(graph); alpar@1402: } alpar@1402: athos@1540: /// \brief Returns the "forward" directed edge view of an undirected edge. deba@1419: /// athos@1540: /// Returns the "forward" directed edge view of an undirected edge. deba@1419: /// \author Balazs Dezso deba@1419: template deba@1419: class ForwardMap { deba@1419: public: deba@1419: deba@1419: typedef typename Graph::Edge Value; deba@1419: typedef typename Graph::UndirEdge Key; deba@1419: deba@1419: /// \brief Constructor deba@1419: /// deba@1419: /// Constructor deba@1419: /// \param _graph The graph that the map belongs to. deba@1419: ForwardMap(const Graph& _graph) : graph(_graph) {} deba@1419: deba@1419: /// \brief The subscript operator. deba@1419: /// deba@1419: /// The subscript operator. deba@1419: /// \param key An undirected edge deba@1419: /// \return The "forward" directed edge view of undirected edge deba@1419: Value operator[](const Key& key) const { deba@1627: return graph.direct(key, true); deba@1419: } deba@1419: deba@1419: private: deba@1419: const Graph& graph; deba@1419: }; deba@1419: deba@1419: /// \brief Returns a \ref ForwardMap class deba@1515: /// deba@1419: /// This function just returns an \ref ForwardMap class. deba@1419: /// \relates ForwardMap deba@1419: template deba@1419: inline ForwardMap forwardMap(const Graph& graph) { deba@1419: return ForwardMap(graph); deba@1419: } deba@1419: athos@1540: /// \brief Returns the "backward" directed edge view of an undirected edge. deba@1419: /// athos@1540: /// Returns the "backward" directed edge view of an undirected edge. deba@1419: /// \author Balazs Dezso deba@1419: template deba@1419: class BackwardMap { deba@1419: public: deba@1419: deba@1419: typedef typename Graph::Edge Value; deba@1419: typedef typename Graph::UndirEdge Key; deba@1419: deba@1419: /// \brief Constructor deba@1419: /// deba@1419: /// Constructor deba@1419: /// \param _graph The graph that the map belongs to. deba@1419: BackwardMap(const Graph& _graph) : graph(_graph) {} deba@1419: deba@1419: /// \brief The subscript operator. deba@1419: /// deba@1419: /// The subscript operator. deba@1419: /// \param key An undirected edge deba@1419: /// \return The "backward" directed edge view of undirected edge deba@1419: Value operator[](const Key& key) const { deba@1627: return graph.direct(key, false); deba@1419: } deba@1419: deba@1419: private: deba@1419: const Graph& graph; deba@1419: }; deba@1419: deba@1419: /// \brief Returns a \ref BackwardMap class deba@1419: athos@1540: /// This function just returns a \ref BackwardMap class. deba@1419: /// \relates BackwardMap deba@1419: template deba@1419: inline BackwardMap backwardMap(const Graph& graph) { deba@1419: return BackwardMap(graph); deba@1419: } deba@1419: deba@1695: /// \brief Potential difference map deba@1695: /// deba@1695: /// If there is an potential map on the nodes then we deba@1695: /// can get an edge map as we get the substraction of the deba@1695: /// values of the target and source. deba@1695: template deba@1695: class PotentialDifferenceMap { deba@1515: public: deba@1695: typedef typename Graph::Edge Key; deba@1695: typedef typename NodeMap::Value Value; deba@1695: deba@1695: /// \brief Constructor deba@1695: /// deba@1695: /// Contructor of the map deba@1695: PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential) deba@1695: : graph(_graph), potential(_potential) {} deba@1695: deba@1695: /// \brief Const subscription operator deba@1695: /// deba@1695: /// Const subscription operator deba@1695: Value operator[](const Key& edge) const { deba@1695: return potential[graph.target(edge)] - potential[graph.source(edge)]; deba@1695: } deba@1695: deba@1695: private: deba@1695: const Graph& graph; deba@1695: const NodeMap& potential; deba@1695: }; deba@1695: deba@1695: /// \brief Just returns a PotentialDifferenceMap deba@1695: /// deba@1695: /// Just returns a PotentialDifferenceMap deba@1695: /// \relates PotentialDifferenceMap deba@1695: template deba@1695: PotentialDifferenceMap deba@1695: potentialDifferenceMap(const Graph& graph, const NodeMap& potential) { deba@1695: return PotentialDifferenceMap(graph, potential); deba@1695: } deba@1695: deba@1515: /// \brief Map of the node in-degrees. alpar@1453: /// athos@1540: /// This map returns the in-degree of a node. Once it is constructed, deba@1515: /// the degrees are stored in a standard NodeMap, so each query is done athos@1540: /// in constant time. On the other hand, the values are updated automatically deba@1515: /// whenever the graph changes. deba@1515: /// deba@1515: /// \sa OutDegMap deba@1515: alpar@1453: template deba@1515: class InDegMap deba@1515: : protected AlterationNotifier::ObserverBase { deba@1515: alpar@1453: public: deba@1515: deba@1515: typedef _Graph Graph; alpar@1453: typedef int Value; deba@1515: typedef typename Graph::Node Key; deba@1515: deba@1515: private: deba@1515: deba@1515: class AutoNodeMap : public Graph::template NodeMap { deba@1515: public: deba@1515: deba@1515: typedef typename Graph::template NodeMap Parent; deba@1515: deba@1515: typedef typename Parent::Key Key; deba@1515: typedef typename Parent::Value Value; deba@1515: deba@1515: AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} deba@1515: deba@1515: void add(const Key& key) { deba@1515: Parent::add(key); deba@1515: Parent::set(key, 0); deba@1515: } deba@1515: }; deba@1515: deba@1515: public: alpar@1453: alpar@1453: /// \brief Constructor. alpar@1453: /// alpar@1453: /// Constructor for creating in-degree map. deba@1515: InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) { alpar@1459: AlterationNotifier alpar@1459: ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge())); deba@1515: deba@1515: for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { deba@1515: deg[it] = countInEdges(graph, it); deba@1515: } alpar@1453: } alpar@1453: deba@1515: virtual ~InDegMap() { alpar@1459: AlterationNotifier:: alpar@1453: ObserverBase::detach(); alpar@1453: } alpar@1453: alpar@1459: /// Gives back the in-degree of a Node. deba@1515: int operator[](const Key& key) const { deba@1515: return deg[key]; alpar@1459: } alpar@1453: alpar@1453: protected: deba@1515: deba@1515: typedef typename Graph::Edge Edge; deba@1515: deba@1515: virtual void add(const Edge& edge) { deba@1515: ++deg[graph.target(edge)]; alpar@1453: } alpar@1453: deba@1515: virtual void erase(const Edge& edge) { deba@1515: --deg[graph.target(edge)]; deba@1515: } deba@1515: deba@1720: virtual void signalChange(const Edge& edge) { deba@1720: erase(edge); deba@1720: } deba@1720: deba@1720: virtual void commitChange(const Edge& edge) { deba@1720: add(edge); deba@1720: } deba@1515: deba@1515: virtual void build() { deba@1515: for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { deba@1515: deg[it] = countInEdges(graph, it); deba@1515: } deba@1515: } deba@1515: deba@1515: virtual void clear() { deba@1515: for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { deba@1515: deg[it] = 0; deba@1515: } deba@1515: } deba@1515: private: alpar@1506: deba@1515: const _Graph& graph; deba@1515: AutoNodeMap deg; alpar@1459: }; alpar@1459: deba@1515: /// \brief Map of the node out-degrees. deba@1515: /// athos@1540: /// This map returns the out-degree of a node. Once it is constructed, deba@1515: /// the degrees are stored in a standard NodeMap, so each query is done athos@1540: /// in constant time. On the other hand, the values are updated automatically deba@1515: /// whenever the graph changes. deba@1515: /// alpar@1555: /// \sa InDegMap alpar@1459: alpar@1459: template deba@1515: class OutDegMap deba@1515: : protected AlterationNotifier::ObserverBase { deba@1515: alpar@1459: public: deba@1515: deba@1515: typedef _Graph Graph; alpar@1459: typedef int Value; deba@1515: typedef typename Graph::Node Key; deba@1515: deba@1515: private: deba@1515: deba@1515: class AutoNodeMap : public Graph::template NodeMap { deba@1515: public: deba@1515: deba@1515: typedef typename Graph::template NodeMap Parent; deba@1515: deba@1515: typedef typename Parent::Key Key; deba@1515: typedef typename Parent::Value Value; deba@1515: deba@1515: AutoNodeMap(const Graph& graph) : Parent(graph, 0) {} deba@1515: deba@1515: void add(const Key& key) { deba@1515: Parent::add(key); deba@1515: Parent::set(key, 0); deba@1515: } deba@1515: }; deba@1515: deba@1515: public: alpar@1459: alpar@1459: /// \brief Constructor. alpar@1459: /// alpar@1459: /// Constructor for creating out-degree map. deba@1515: OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) { alpar@1459: AlterationNotifier alpar@1459: ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge())); deba@1515: deba@1515: for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { deba@1515: deg[it] = countOutEdges(graph, it); deba@1515: } alpar@1459: } alpar@1459: deba@1515: virtual ~OutDegMap() { alpar@1459: AlterationNotifier:: alpar@1459: ObserverBase::detach(); alpar@1459: } alpar@1459: alpar@1459: /// Gives back the in-degree of a Node. deba@1515: int operator[](const Key& key) const { deba@1515: return deg[key]; alpar@1459: } alpar@1459: alpar@1459: protected: deba@1515: deba@1515: typedef typename Graph::Edge Edge; deba@1515: deba@1515: virtual void add(const Edge& edge) { deba@1515: ++deg[graph.source(edge)]; alpar@1459: } alpar@1459: deba@1515: virtual void erase(const Edge& edge) { deba@1515: --deg[graph.source(edge)]; deba@1515: } deba@1515: deba@1720: virtual void signalChange(const Edge& edge) { deba@1720: erase(edge); deba@1720: } deba@1720: deba@1720: virtual void commitChange(const Edge& edge) { deba@1720: add(edge); deba@1720: } deba@1720: deba@1515: deba@1515: virtual void build() { deba@1515: for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { deba@1515: deg[it] = countOutEdges(graph, it); deba@1515: } deba@1515: } deba@1515: deba@1515: virtual void clear() { deba@1515: for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) { deba@1515: deg[it] = 0; deba@1515: } deba@1515: } deba@1515: private: alpar@1506: deba@1515: const _Graph& graph; deba@1515: AutoNodeMap deg; alpar@1453: }; alpar@1453: deba@1695: alpar@1402: /// @} alpar@1402: alpar@947: } //END OF NAMESPACE LEMON klao@946: klao@946: #endif