/* -*- C++ -*- * lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef LEMON_GRAPH_UTILS_H #define LEMON_GRAPH_UTILS_H #include #include #include #include #include #include #include ///\ingroup gutils ///\file ///\brief Graph utilities. /// /// namespace lemon { /// \addtogroup gutils /// @{ /// \brief Function to count the items in the graph. /// /// This function counts the items (nodes, edges etc) in the graph. /// The complexity of the function is O(n) because /// it iterates on all of the items. template inline int countItems(const Graph& g) { int num = 0; for (ItemIt it(g); it != INVALID; ++it) { ++num; } return num; } // Node counting: template inline typename enable_if::type _countNodes(const Graph &g) { return g.nodeNum(); } template inline int _countNodes(Wrap w) { return countItems(w.value); } /// \brief Function to count the nodes in the graph. /// /// This function counts the nodes in the graph. /// The complexity of the function is O(n) but for some /// graph structures it is specialized to run in O(1). /// /// \todo refer how to specialize it template inline int countNodes(const Graph& g) { return _countNodes(g); } // Edge counting: template inline typename enable_if::type _countEdges(const Graph &g) { return g.edgeNum(); } template inline int _countEdges(Wrap w) { return countItems(w.value); } /// \brief Function to count the edges in the graph. /// /// This function counts the edges in the graph. /// The complexity of the function is O(e) but for some /// graph structures it is specialized to run in O(1). template inline int countEdges(const Graph& g) { return _countEdges(g); } // Undirected edge counting: template inline typename enable_if::type _countUndirEdges(const Graph &g) { return g.undirEdgeNum(); } template inline int _countUndirEdges(Wrap w) { return countItems(w.value); } /// \brief Function to count the undirected edges in the graph. /// /// This function counts the undirected edges in the graph. /// The complexity of the function is O(e) but for some /// graph structures it is specialized to run in O(1). template inline int countUndirEdges(const Graph& g) { return _countUndirEdges(g); } template inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { int num = 0; for (DegIt it(_g, _n); it != INVALID; ++it) { ++num; } return num; } /// \brief Function to count the number of the out-edges from node \c n. /// /// This function counts the number of the out-edges from node \c n /// in the graph. template inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { return countNodeDegree(_g, _n); } /// \brief Function to count the number of the in-edges to node \c n. /// /// This function counts the number of the in-edges to node \c n /// in the graph. template inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { return countNodeDegree(_g, _n); } template inline typename enable_if::type _findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge prev = INVALID) { return g.findEdge(u, v, prev); } template inline typename Graph::Edge _findEdge(Wrap w, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge prev = INVALID) { const Graph& g = w.value; if (prev == INVALID) { typename Graph::OutEdgeIt e(g, u); while (e != INVALID && g.target(e) != v) ++e; return e; } else { typename Graph::OutEdgeIt e(g, prev); ++e; while (e != INVALID && g.target(e) != v) ++e; return e; } } /// \brief Finds an edge between two nodes of a graph. /// /// Finds an edge from node \c u to node \c v in graph \c g. /// /// If \c prev is \ref INVALID (this is the default value), then /// it finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or \ref INVALID if there is no such an edge. /// /// Thus you can iterate through each edge from \c u to \c v as it follows. /// \code /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { /// ... /// } /// \endcode // /// \todo We may want to use the "GraphBase" // /// interface here... // /// It would not work with the undirected graphs. template inline typename Graph::Edge findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, typename Graph::Edge prev = INVALID) { return _findEdge(g, u, v, prev); } /// \brief Iterator for iterating on edges connected the same nodes. /// /// Iterator for iterating on edges connected the same nodes. It is /// higher level interface for the findEdge() function. You can /// use it the next way: /// \code /// for (ConEdgeIt it(g, src, trg); it != INVALID; ++it) { /// ... /// } /// \endcode /// /// \author Balazs Dezso template class ConEdgeIt : public _Graph::Edge { public: typedef _Graph Graph; typedef typename Graph::Edge Parent; typedef typename Graph::Edge Edge; typedef typename Graph::Node Node; /// \brief Constructor. /// /// Construct a new ConEdgeIt iterating on the edges which /// connects the \c u and \c v node. ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) { Parent::operator=(findEdge(graph, u, v)); } /// \brief Constructor. /// /// Construct a new ConEdgeIt which continues the iterating from /// the \c e edge. ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {} /// \brief Increment operator. /// /// It increments the iterator and gives back the next edge. ConEdgeIt& operator++() { Parent::operator=(findEdge(graph, graph.source(*this), graph.target(*this), *this)); return *this; } private: const Graph& graph; }; /// \brief Copy a map. /// /// This function copies the \c source map to the \c target map. It uses the /// given iterator to iterate on the data structure and it uses the \c ref /// mapping to convert the source's keys to the target's keys. template void copyMap(Target& target, const Source& source, ItemIt it, const Ref& ref) { for (; it != INVALID; ++it) { target[ref[it]] = source[it]; } } /// \brief Copy the source map to the target map. /// /// Copy the \c source map to the \c target map. It uses the given iterator /// to iterate on the data structure. template void copyMap(Target& target, const Source& source, ItemIt it) { for (; it != INVALID; ++it) { target[it] = source[it]; } } /// \brief Class to copy a graph. /// /// Class to copy a graph to an other graph (duplicate a graph). The /// simplest way of using it is through the \c copyGraph() function. template class GraphCopy { public: typedef typename Source::Node Node; typedef typename Source::NodeIt NodeIt; typedef typename Source::Edge Edge; typedef typename Source::EdgeIt EdgeIt; typedef typename Source::template NodeMapNodeRefMap; typedef typename Source::template EdgeMapEdgeRefMap; /// \brief Constructor for the GraphCopy. /// /// It copies the content of the \c _source graph into the /// \c _target graph. It creates also two references, one beetween /// the two nodeset and one beetween the two edgesets. GraphCopy(Target& _target, const Source& _source) : source(_source), target(_target), nodeRefMap(_source), edgeRefMap(_source) { for (NodeIt it(source); it != INVALID; ++it) { nodeRefMap[it] = target.addNode(); } for (EdgeIt it(source); it != INVALID; ++it) { edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], nodeRefMap[source.target(it)]); } } /// \brief Copies the node references into the given map. /// /// Copies the node references into the given map. template const GraphCopy& nodeRef(NodeRef& map) const { for (NodeIt it(source); it != INVALID; ++it) { map.set(it, nodeRefMap[it]); } return *this; } /// \brief Reverse and copies the node references into the given map. /// /// Reverse and copies the node references into the given map. template const GraphCopy& nodeCrossRef(NodeRef& map) const { for (NodeIt it(source); it != INVALID; ++it) { map.set(nodeRefMap[it], it); } return *this; } /// \brief Copies the edge references into the given map. /// /// Copies the edge references into the given map. template const GraphCopy& edgeRef(EdgeRef& map) const { for (EdgeIt it(source); it != INVALID; ++it) { map.set(it, edgeRefMap[it]); } return *this; } /// \brief Reverse and copies the edge references into the given map. /// /// Reverse and copies the edge references into the given map. template const GraphCopy& edgeCrossRef(EdgeRef& map) const { for (EdgeIt it(source); it != INVALID; ++it) { map.set(edgeRefMap[it], it); } return *this; } /// \brief Make copy of the given map. /// /// Makes copy of the given map for the newly created graph. /// The new map's key type is the target graph's node type, /// and the copied map's key type is the source graph's node /// type. template const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const { copyMap(tMap, sMap, NodeIt(source), nodeRefMap); return *this; } /// \brief Make copy of the given map. /// /// Makes copy of the given map for the newly created graph. /// The new map's key type is the target graph's edge type, /// and the copied map's key type is the source graph's edge /// type. template const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const { copyMap(tMap, sMap, EdgeIt(source), edgeRefMap); return *this; } /// \brief Gives back the stored node references. /// /// Gives back the stored node references. const NodeRefMap& nodeRef() const { return nodeRefMap; } /// \brief Gives back the stored edge references. /// /// Gives back the stored edge references. const EdgeRefMap& edgeRef() const { return edgeRefMap; } private: const Source& source; Target& target; NodeRefMap nodeRefMap; EdgeRefMap edgeRefMap; }; /// \brief Copy a graph to an other graph. /// /// Copy a graph to an other graph. /// The usage of the function: /// /// \code /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr); /// \endcode /// /// After the copy the \c nr map will contain the mapping from the /// source graph's nodes to the target graph's nodes and the \c ecr will /// contain the mapping from the target graph's edges to the source's /// edges. template GraphCopy copyGraph(Target& target, const Source& source) { return GraphCopy(target, source); } template class ItemSetTraits {}; template class ItemSetTraits<_Graph, typename _Graph::Node> { public: typedef _Graph Graph; typedef typename Graph::Node Item; typedef typename Graph::NodeIt ItemIt; template class Map : public Graph::template NodeMap<_Value> { public: typedef typename Graph::template NodeMap<_Value> Parent; typedef typename Parent::Value Value; Map(const Graph& _graph) : Parent(_graph) {} Map(const Graph& _graph, const Value& _value) : Parent(_graph, _value) {} }; }; template class ItemSetTraits<_Graph, typename _Graph::Edge> { public: typedef _Graph Graph; typedef typename Graph::Edge Item; typedef typename Graph::EdgeIt ItemIt; template class Map : public Graph::template EdgeMap<_Value> { public: typedef typename Graph::template EdgeMap<_Value> Parent; typedef typename Parent::Value Value; Map(const Graph& _graph) : Parent(_graph) {} Map(const Graph& _graph, const Value& _value) : Parent(_graph, _value) {} }; }; template class ItemSetTraits<_Graph, typename _Graph::UndirEdge> { public: typedef _Graph Graph; typedef typename Graph::UndirEdge Item; typedef typename Graph::UndirEdgeIt ItemIt; template class Map : public Graph::template UndirEdgeMap<_Value> { public: typedef typename Graph::template UndirEdgeMap<_Value> Parent; typedef typename Parent::Value Value; Map(const Graph& _graph) : Parent(_graph) {} Map(const Graph& _graph, const Value& _value) : Parent(_graph, _value) {} }; }; /// @} /// \addtogroup graph_maps /// @{ template struct ReferenceMapTraits { typedef typename Map::Value Value; typedef typename Map::Value& Reference; typedef const typename Map::Value& ConstReference; typedef typename Map::Value* Pointer; typedef const typename Map::Value* ConstPointer; }; template struct ReferenceMapTraits< Map, typename enable_if::type > { typedef typename Map::Value Value; typedef typename Map::Reference Reference; typedef typename Map::ConstReference ConstReference; typedef typename Map::Pointer Pointer; typedef typename Map::ConstPointer ConstPointer; }; /// Provides an immutable and unique id for each item in the graph. /// The IdMap class provides a unique and immutable id for each item of the /// same type (e.g. node) in the graph. This id is
• \b unique: /// different items (nodes) get different ids
• \b immutable: the id of an /// item (node) does not change (even if you delete other nodes).
/// Through this map you get access (i.e. can read) the inner id values of /// the items stored in the graph. This map can be inverted with its member /// class \c InverseMap. /// template class IdMap { public: typedef _Graph Graph; typedef int Value; typedef _Item Item; typedef _Item Key; typedef True NeedCopy; /// \brief Constructor. /// /// Constructor for creating id map. IdMap(const Graph& _graph) : graph(&_graph) {} /// \brief Gives back the \e id of the item. /// /// Gives back the immutable and unique \e id of the map. int operator[](const Item& item) const { return graph->id(item);} private: const Graph* graph; public: /// \brief The class represents the inverse of its owner (IdMap). /// /// The class represents the inverse of its owner (IdMap). /// \see inverse() class InverseMap { public: typedef True NeedCopy; /// \brief Constructor. /// /// Constructor for creating an id-to-item map. InverseMap(const Graph& _graph) : graph(&_graph) {} /// \brief Constructor. /// /// Constructor for creating an id-to-item map. InverseMap(const IdMap& idMap) : graph(idMap.graph) {} /// \brief Gives back the given item from its id. /// /// Gives back the given item from its id. /// Item operator[](int id) const { return graph->fromId(id, Item());} private: const Graph* graph; }; /// \brief Gives back the inverse of the map. /// /// Gives back the inverse of the IdMap. InverseMap inverse() const { return InverseMap(*graph);} }; /// \brief General invertable graph-map type. /// This type provides simple invertable graph-maps. /// The InvertableMap wraps an arbitrary ReadWriteMap /// and if a key is set to a new value then store it /// in the inverse map. /// \param _Graph The graph type. /// \param _Map The map to extend with invertable functionality. template < typename _Graph, typename _Item, typename _Value, typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent > class InvertableMap : protected _Map { public: typedef _Map Map; typedef _Graph Graph; /// The key type of InvertableMap (Node, Edge, UndirEdge). typedef typename _Map::Key Key; /// The value type of the InvertableMap. typedef typename _Map::Value Value; /// \brief Constructor. /// /// Construct a new InvertableMap for the graph. /// InvertableMap(const Graph& graph) : Map(graph) {} /// \brief The setter function of the map. /// /// Sets the mapped value. void set(const Key& key, const Value& val) { Value oldval = Map::operator[](key); typename Container::iterator it = invMap.find(oldval); if (it != invMap.end() && it->second == key) { invMap.erase(it); } invMap.insert(make_pair(val, key)); Map::set(key, val); } /// \brief The getter function of the map. /// /// It gives back the value associated with the key. const Value operator[](const Key& key) const { return Map::operator[](key); } protected: /// \brief Add a new key to the map. /// /// Add a new key to the map. It is called by the /// \c AlterationNotifier. virtual void add(const Key& key) { Map::add(key); } /// \brief Erase the key from the map. /// /// Erase the key to the map. It is called by the /// \c AlterationNotifier. virtual void erase(const Key& key) { Value val = Map::operator[](key); typename Container::iterator it = invMap.find(val); if (it != invMap.end() && it->second == key) { invMap.erase(it); } Map::erase(key); } /// \brief Clear the keys from the map and inverse map. /// /// Clear the keys from the map and inverse map. It is called by the /// \c AlterationNotifier. virtual void clear() { invMap.clear(); Map::clear(); } private: typedef std::map Container; Container invMap; public: /// \brief The inverse map type. /// /// The inverse of this map. The subscript operator of the map /// gives back always the item what was last assigned to the value. class InverseMap { public: /// \brief Constructor of the InverseMap. /// /// Constructor of the InverseMap. InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {} /// The value type of the InverseMap. typedef typename InvertableMap::Key Value; /// The key type of the InverseMap. typedef typename InvertableMap::Value Key; /// \brief Subscript operator. /// /// Subscript operator. It gives back always the item /// what was last assigned to the value. Value operator[](const Key& key) const { typename Container::const_iterator it = inverted.invMap.find(key); return it->second; } private: const InvertableMap& inverted; }; /// \brief It gives back the just readeable inverse map. /// /// It gives back the just readeable inverse map. InverseMap inverse() const { return InverseMap(*this); } }; /// \brief Provides a mutable, continuous and unique descriptor for each /// item in the graph. /// /// The DescriptorMap class provides a unique and continuous (but mutable) /// descriptor (id) for each item of the same type (e.g. node) in the /// graph. This id is
• \b unique: different items (nodes) get /// different ids
• \b continuous: the range of the ids is the set of /// integers between 0 and \c n-1, where \c n is the number of the items of /// this type (e.g. nodes) (so the id of a node can change if you delete an /// other node, i.e. this id is mutable).