deba@220: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@220: * deba@220: * This file is a part of LEMON, a generic C++ optimization library. deba@220: * deba@220: * Copyright (C) 2003-2008 deba@220: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@220: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@220: * deba@220: * Permission to use, modify and distribute this software is granted deba@220: * provided that this copyright notice appears in all copies. For deba@220: * precise terms see the accompanying LICENSE file. deba@220: * deba@220: * This software is provided "AS IS" with no warranty of any kind, deba@220: * express or implied, and with no claim as to its suitability for any deba@220: * purpose. deba@220: * deba@220: */ deba@220: deba@220: #ifndef LEMON_CORE_H deba@220: #define LEMON_CORE_H deba@220: deba@220: #include deba@220: #include deba@220: deba@220: #include deba@220: #include deba@220: deba@220: ///\file deba@220: ///\brief LEMON core utilities. kpeter@229: /// kpeter@229: ///This header file contains core utilities for LEMON. deba@233: ///It is automatically included by all graph types, therefore it usually kpeter@229: ///do not have to be included directly. deba@220: deba@220: namespace lemon { deba@220: deba@220: /// \brief Dummy type to make it easier to create invalid iterators. deba@220: /// deba@220: /// Dummy type to make it easier to create invalid iterators. deba@220: /// See \ref INVALID for the usage. deba@220: struct Invalid { deba@220: public: deba@220: bool operator==(Invalid) { return true; } deba@220: bool operator!=(Invalid) { return false; } deba@220: bool operator< (Invalid) { return false; } deba@220: }; deba@220: deba@220: /// \brief Invalid iterators. deba@220: /// deba@220: /// \ref Invalid is a global type that converts to each iterator deba@220: /// in such a way that the value of the target iterator will be invalid. deba@220: #ifdef LEMON_ONLY_TEMPLATES deba@220: const Invalid INVALID = Invalid(); deba@220: #else deba@220: extern const Invalid INVALID; deba@220: #endif deba@220: deba@220: /// \addtogroup gutils deba@220: /// @{ deba@220: kpeter@304: ///Create convenience typedefs for the digraph types and iterators deba@220: kpeter@282: ///This \c \#define creates convenient type definitions for the following kpeter@282: ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, deba@220: ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, deba@220: ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. deba@220: /// deba@220: ///\note If the graph type is a dependent type, ie. the graph type depend deba@220: ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() deba@220: ///macro. deba@220: #define DIGRAPH_TYPEDEFS(Digraph) \ deba@220: typedef Digraph::Node Node; \ deba@220: typedef Digraph::NodeIt NodeIt; \ deba@220: typedef Digraph::Arc Arc; \ deba@220: typedef Digraph::ArcIt ArcIt; \ deba@220: typedef Digraph::InArcIt InArcIt; \ deba@220: typedef Digraph::OutArcIt OutArcIt; \ deba@220: typedef Digraph::NodeMap BoolNodeMap; \ deba@220: typedef Digraph::NodeMap IntNodeMap; \ deba@220: typedef Digraph::NodeMap DoubleNodeMap; \ deba@220: typedef Digraph::ArcMap BoolArcMap; \ deba@220: typedef Digraph::ArcMap IntArcMap; \ kpeter@304: typedef Digraph::ArcMap DoubleArcMap deba@220: kpeter@304: ///Create convenience typedefs for the digraph types and iterators deba@220: deba@220: ///\see DIGRAPH_TYPEDEFS deba@220: /// deba@220: ///\note Use this macro, if the graph type is a dependent type, deba@220: ///ie. the graph type depend on a template parameter. deba@220: #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ deba@220: typedef typename Digraph::Node Node; \ deba@220: typedef typename Digraph::NodeIt NodeIt; \ deba@220: typedef typename Digraph::Arc Arc; \ deba@220: typedef typename Digraph::ArcIt ArcIt; \ deba@220: typedef typename Digraph::InArcIt InArcIt; \ deba@220: typedef typename Digraph::OutArcIt OutArcIt; \ deba@220: typedef typename Digraph::template NodeMap BoolNodeMap; \ deba@220: typedef typename Digraph::template NodeMap IntNodeMap; \ deba@220: typedef typename Digraph::template NodeMap DoubleNodeMap; \ deba@220: typedef typename Digraph::template ArcMap BoolArcMap; \ deba@220: typedef typename Digraph::template ArcMap IntArcMap; \ kpeter@304: typedef typename Digraph::template ArcMap DoubleArcMap deba@220: kpeter@304: ///Create convenience typedefs for the graph types and iterators deba@220: kpeter@282: ///This \c \#define creates the same convenient type definitions as defined deba@220: ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates deba@220: ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, deba@220: ///\c DoubleEdgeMap. deba@220: /// deba@220: ///\note If the graph type is a dependent type, ie. the graph type depend kpeter@282: ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS() deba@220: ///macro. deba@220: #define GRAPH_TYPEDEFS(Graph) \ deba@220: DIGRAPH_TYPEDEFS(Graph); \ deba@220: typedef Graph::Edge Edge; \ deba@220: typedef Graph::EdgeIt EdgeIt; \ deba@220: typedef Graph::IncEdgeIt IncEdgeIt; \ deba@220: typedef Graph::EdgeMap BoolEdgeMap; \ deba@220: typedef Graph::EdgeMap IntEdgeMap; \ kpeter@304: typedef Graph::EdgeMap DoubleEdgeMap deba@220: kpeter@304: ///Create convenience typedefs for the graph types and iterators deba@220: deba@220: ///\see GRAPH_TYPEDEFS deba@220: /// deba@220: ///\note Use this macro, if the graph type is a dependent type, deba@220: ///ie. the graph type depend on a template parameter. deba@220: #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ deba@220: TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ deba@220: typedef typename Graph::Edge Edge; \ deba@220: typedef typename Graph::EdgeIt EdgeIt; \ deba@220: typedef typename Graph::IncEdgeIt IncEdgeIt; \ deba@220: typedef typename Graph::template EdgeMap BoolEdgeMap; \ deba@220: typedef typename Graph::template EdgeMap IntEdgeMap; \ kpeter@304: typedef typename Graph::template EdgeMap DoubleEdgeMap deba@220: kpeter@282: /// \brief Function to count the items in a graph. deba@220: /// kpeter@282: /// This function counts the items (nodes, arcs etc.) in a graph. kpeter@282: /// The complexity of the function is linear because deba@220: /// it iterates on all of the items. deba@220: template deba@220: inline int countItems(const Graph& g) { deba@220: typedef typename ItemSetTraits::ItemIt ItemIt; deba@220: int num = 0; deba@220: for (ItemIt it(g); it != INVALID; ++it) { deba@220: ++num; deba@220: } deba@220: return num; deba@220: } deba@220: deba@220: // Node counting: deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template deba@220: struct CountNodesSelector { deba@220: static int count(const Graph &g) { deba@220: return countItems(g); deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct CountNodesSelector< deba@220: Graph, typename deba@220: enable_if::type> deba@220: { deba@220: static int count(const Graph &g) { deba@220: return g.nodeNum(); deba@220: } deba@220: }; deba@220: } deba@220: deba@220: /// \brief Function to count the nodes in the graph. deba@220: /// deba@220: /// This function counts the nodes in the graph. kpeter@282: /// The complexity of the function is O(n), but for some kpeter@282: /// graph structures it is specialized to run in O(1). deba@220: /// kpeter@282: /// \note If the graph contains a \c nodeNum() member function and a kpeter@282: /// \c NodeNumTag tag then this function calls directly the member deba@220: /// function to query the cardinality of the node set. deba@220: template deba@220: inline int countNodes(const Graph& g) { deba@220: return _core_bits::CountNodesSelector::count(g); deba@220: } deba@220: deba@220: // Arc counting: deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template deba@220: struct CountArcsSelector { deba@220: static int count(const Graph &g) { deba@220: return countItems(g); deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct CountArcsSelector< deba@220: Graph, deba@220: typename enable_if::type> deba@220: { deba@220: static int count(const Graph &g) { deba@220: return g.arcNum(); deba@220: } deba@220: }; deba@220: } deba@220: deba@220: /// \brief Function to count the arcs in the graph. deba@220: /// deba@220: /// This function counts the arcs in the graph. kpeter@282: /// The complexity of the function is O(m), but for some kpeter@282: /// graph structures it is specialized to run in O(1). deba@220: /// kpeter@282: /// \note If the graph contains a \c arcNum() member function and a kpeter@282: /// \c ArcNumTag tag then this function calls directly the member deba@220: /// function to query the cardinality of the arc set. deba@220: template deba@220: inline int countArcs(const Graph& g) { deba@220: return _core_bits::CountArcsSelector::count(g); deba@220: } deba@220: deba@220: // Edge counting: kpeter@282: deba@220: namespace _core_bits { deba@220: deba@220: template deba@220: struct CountEdgesSelector { deba@220: static int count(const Graph &g) { deba@220: return countItems(g); deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct CountEdgesSelector< deba@220: Graph, deba@220: typename enable_if::type> deba@220: { deba@220: static int count(const Graph &g) { deba@220: return g.edgeNum(); deba@220: } deba@220: }; deba@220: } deba@220: deba@220: /// \brief Function to count the edges in the graph. deba@220: /// deba@220: /// This function counts the edges in the graph. kpeter@282: /// The complexity of the function is O(m), but for some kpeter@282: /// graph structures it is specialized to run in O(1). deba@220: /// kpeter@282: /// \note If the graph contains a \c edgeNum() member function and a kpeter@282: /// \c EdgeNumTag tag then this function calls directly the member deba@220: /// function to query the cardinality of the edge set. deba@220: template deba@220: inline int countEdges(const Graph& g) { deba@220: return _core_bits::CountEdgesSelector::count(g); deba@220: deba@220: } deba@220: deba@220: deba@220: template deba@220: inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { deba@220: int num = 0; deba@220: for (DegIt it(_g, _n); it != INVALID; ++it) { deba@220: ++num; deba@220: } deba@220: return num; deba@220: } deba@220: deba@220: /// \brief Function to count the number of the out-arcs from node \c n. deba@220: /// deba@220: /// This function counts the number of the out-arcs from node \c n kpeter@282: /// in the graph \c g. deba@220: template kpeter@282: inline int countOutArcs(const Graph& g, const typename Graph::Node& n) { kpeter@282: return countNodeDegree(g, n); deba@220: } deba@220: deba@220: /// \brief Function to count the number of the in-arcs to node \c n. deba@220: /// deba@220: /// This function counts the number of the in-arcs to node \c n kpeter@282: /// in the graph \c g. deba@220: template kpeter@282: inline int countInArcs(const Graph& g, const typename Graph::Node& n) { kpeter@282: return countNodeDegree(g, n); deba@220: } deba@220: deba@220: /// \brief Function to count the number of the inc-edges to node \c n. deba@220: /// deba@220: /// This function counts the number of the inc-edges to node \c n kpeter@282: /// in the undirected graph \c g. deba@220: template kpeter@282: inline int countIncEdges(const Graph& g, const typename Graph::Node& n) { kpeter@282: return countNodeDegree(g, n); deba@220: } deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template deba@220: class MapCopyBase { deba@220: public: deba@220: virtual void copy(const Digraph& from, const RefMap& refMap) = 0; deba@220: deba@220: virtual ~MapCopyBase() {} deba@220: }; deba@220: deba@220: template deba@220: class MapCopy : public MapCopyBase { deba@220: public: deba@220: kpeter@282: MapCopy(const FromMap& map, ToMap& tmap) kpeter@282: : _map(map), _tmap(tmap) {} deba@220: deba@220: virtual void copy(const Digraph& digraph, const RefMap& refMap) { deba@220: typedef typename ItemSetTraits::ItemIt ItemIt; deba@220: for (ItemIt it(digraph); it != INVALID; ++it) { deba@220: _tmap.set(refMap[it], _map[it]); deba@220: } deba@220: } deba@220: deba@220: private: kpeter@282: const FromMap& _map; deba@220: ToMap& _tmap; deba@220: }; deba@220: deba@220: template deba@220: class ItemCopy : public MapCopyBase { deba@220: public: deba@220: kpeter@282: ItemCopy(const Item& item, It& it) : _item(item), _it(it) {} deba@220: deba@220: virtual void copy(const Digraph&, const RefMap& refMap) { deba@220: _it = refMap[_item]; deba@220: } deba@220: deba@220: private: kpeter@282: Item _item; deba@220: It& _it; deba@220: }; deba@220: deba@220: template deba@220: class RefCopy : public MapCopyBase { deba@220: public: deba@220: deba@220: RefCopy(Ref& map) : _map(map) {} deba@220: deba@220: virtual void copy(const Digraph& digraph, const RefMap& refMap) { deba@220: typedef typename ItemSetTraits::ItemIt ItemIt; deba@220: for (ItemIt it(digraph); it != INVALID; ++it) { deba@220: _map.set(it, refMap[it]); deba@220: } deba@220: } deba@220: deba@220: private: deba@220: Ref& _map; deba@220: }; deba@220: deba@220: template deba@220: class CrossRefCopy : public MapCopyBase { deba@220: public: deba@220: deba@220: CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {} deba@220: deba@220: virtual void copy(const Digraph& digraph, const RefMap& refMap) { deba@220: typedef typename ItemSetTraits::ItemIt ItemIt; deba@220: for (ItemIt it(digraph); it != INVALID; ++it) { deba@220: _cmap.set(refMap[it], it); deba@220: } deba@220: } deba@220: deba@220: private: deba@220: CrossRef& _cmap; deba@220: }; deba@220: deba@220: template deba@220: struct DigraphCopySelector { deba@220: template kpeter@282: static void copy(const From& from, Digraph &to, deba@220: NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { deba@220: for (typename From::NodeIt it(from); it != INVALID; ++it) { deba@220: nodeRefMap[it] = to.addNode(); deba@220: } deba@220: for (typename From::ArcIt it(from); it != INVALID; ++it) { deba@220: arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], deba@220: nodeRefMap[from.target(it)]); deba@220: } deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct DigraphCopySelector< deba@220: Digraph, deba@220: typename enable_if::type> deba@220: { deba@220: template kpeter@282: static void copy(const From& from, Digraph &to, deba@220: NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { deba@220: to.build(from, nodeRefMap, arcRefMap); deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct GraphCopySelector { deba@220: template kpeter@282: static void copy(const From& from, Graph &to, deba@220: NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { deba@220: for (typename From::NodeIt it(from); it != INVALID; ++it) { deba@220: nodeRefMap[it] = to.addNode(); deba@220: } deba@220: for (typename From::EdgeIt it(from); it != INVALID; ++it) { deba@220: edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], deba@220: nodeRefMap[from.v(it)]); deba@220: } deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct GraphCopySelector< deba@220: Graph, deba@220: typename enable_if::type> deba@220: { deba@220: template kpeter@282: static void copy(const From& from, Graph &to, deba@220: NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { deba@220: to.build(from, nodeRefMap, edgeRefMap); deba@220: } deba@220: }; deba@220: deba@220: } deba@220: deba@220: /// \brief Class to copy a digraph. deba@220: /// deba@220: /// Class to copy a digraph to another digraph (duplicate a digraph). The kpeter@282: /// simplest way of using it is through the \c digraphCopy() function. deba@220: /// kpeter@282: /// This class not only make a copy of a digraph, but it can create deba@220: /// references and cross references between the nodes and arcs of kpeter@282: /// the two digraphs, and it can copy maps to use with the newly created kpeter@282: /// digraph. deba@220: /// kpeter@282: /// To make a copy from a digraph, first an instance of DigraphCopy kpeter@282: /// should be created, then the data belongs to the digraph should deba@220: /// assigned to copy. In the end, the \c run() member should be deba@220: /// called. deba@220: /// kpeter@282: /// The next code copies a digraph with several data: deba@220: ///\code kpeter@282: /// DigraphCopy cg(orig_graph, new_graph); kpeter@282: /// // Create references for the nodes deba@220: /// OrigGraph::NodeMap nr(orig_graph); kpeter@282: /// cg.nodeRef(nr); kpeter@282: /// // Create cross references (inverse) for the arcs deba@220: /// NewGraph::ArcMap acr(new_graph); kpeter@282: /// cg.arcCrossRef(acr); kpeter@282: /// // Copy an arc map deba@220: /// OrigGraph::ArcMap oamap(orig_graph); deba@220: /// NewGraph::ArcMap namap(new_graph); kpeter@282: /// cg.arcMap(oamap, namap); kpeter@282: /// // Copy a node deba@220: /// OrigGraph::Node on; deba@220: /// NewGraph::Node nn; kpeter@282: /// cg.node(on, nn); kpeter@282: /// // Execute copying kpeter@282: /// cg.run(); deba@220: ///\endcode kpeter@282: template deba@220: class DigraphCopy { deba@220: private: deba@220: deba@220: typedef typename From::Node Node; deba@220: typedef typename From::NodeIt NodeIt; deba@220: typedef typename From::Arc Arc; deba@220: typedef typename From::ArcIt ArcIt; deba@220: deba@220: typedef typename To::Node TNode; deba@220: typedef typename To::Arc TArc; deba@220: deba@220: typedef typename From::template NodeMap NodeRefMap; deba@220: typedef typename From::template ArcMap ArcRefMap; deba@220: deba@220: public: deba@220: kpeter@282: /// \brief Constructor of DigraphCopy. deba@220: /// kpeter@282: /// Constructor of DigraphCopy for copying the content of the kpeter@282: /// \c from digraph into the \c to digraph. kpeter@282: DigraphCopy(const From& from, To& to) deba@220: : _from(from), _to(to) {} deba@220: kpeter@282: /// \brief Destructor of DigraphCopy deba@220: /// kpeter@282: /// Destructor of DigraphCopy. deba@220: ~DigraphCopy() { deba@220: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@220: delete _node_maps[i]; deba@220: } deba@220: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@220: delete _arc_maps[i]; deba@220: } deba@220: deba@220: } deba@220: kpeter@282: /// \brief Copy the node references into the given map. deba@220: /// kpeter@282: /// This function copies the node references into the given map. kpeter@282: /// The parameter should be a map, whose key type is the Node type of kpeter@282: /// the source digraph, while the value type is the Node type of the kpeter@282: /// destination digraph. deba@220: template deba@220: DigraphCopy& nodeRef(NodeRef& map) { deba@220: _node_maps.push_back(new _core_bits::RefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the node cross references into the given map. deba@220: /// kpeter@282: /// This function copies the node cross references (reverse references) kpeter@282: /// into the given map. The parameter should be a map, whose key type kpeter@282: /// is the Node type of the destination digraph, while the value type is kpeter@282: /// the Node type of the source digraph. deba@220: template deba@220: DigraphCopy& nodeCrossRef(NodeCrossRef& map) { deba@220: _node_maps.push_back(new _core_bits::CrossRefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Make a copy of the given node map. deba@220: /// kpeter@282: /// This function makes a copy of the given node map for the newly kpeter@282: /// created digraph. kpeter@282: /// The key type of the new map \c tmap should be the Node type of the kpeter@282: /// destination digraph, and the key type of the original map \c map kpeter@282: /// should be the Node type of the source digraph. kpeter@282: template kpeter@282: DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { deba@220: _node_maps.push_back(new _core_bits::MapCopy(map, tmap)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given node. deba@220: /// kpeter@282: /// This function makes a copy of the given node. kpeter@282: DigraphCopy& node(const Node& node, TNode& tnode) { deba@220: _node_maps.push_back(new _core_bits::ItemCopy(node, tnode)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the arc references into the given map. deba@220: /// kpeter@282: /// This function copies the arc references into the given map. kpeter@282: /// The parameter should be a map, whose key type is the Arc type of kpeter@282: /// the source digraph, while the value type is the Arc type of the kpeter@282: /// destination digraph. deba@220: template deba@220: DigraphCopy& arcRef(ArcRef& map) { deba@220: _arc_maps.push_back(new _core_bits::RefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the arc cross references into the given map. deba@220: /// kpeter@282: /// This function copies the arc cross references (reverse references) kpeter@282: /// into the given map. The parameter should be a map, whose key type kpeter@282: /// is the Arc type of the destination digraph, while the value type is kpeter@282: /// the Arc type of the source digraph. deba@220: template deba@220: DigraphCopy& arcCrossRef(ArcCrossRef& map) { deba@220: _arc_maps.push_back(new _core_bits::CrossRefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Make a copy of the given arc map. deba@220: /// kpeter@282: /// This function makes a copy of the given arc map for the newly kpeter@282: /// created digraph. kpeter@282: /// The key type of the new map \c tmap should be the Arc type of the kpeter@282: /// destination digraph, and the key type of the original map \c map kpeter@282: /// should be the Arc type of the source digraph. kpeter@282: template kpeter@282: DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) { deba@220: _arc_maps.push_back(new _core_bits::MapCopy(map, tmap)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given arc. deba@220: /// kpeter@282: /// This function makes a copy of the given arc. kpeter@282: DigraphCopy& arc(const Arc& arc, TArc& tarc) { deba@220: _arc_maps.push_back(new _core_bits::ItemCopy(arc, tarc)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Execute copying. deba@220: /// kpeter@282: /// This function executes the copying of the digraph along with the kpeter@282: /// copying of the assigned data. deba@220: void run() { deba@220: NodeRefMap nodeRefMap(_from); deba@220: ArcRefMap arcRefMap(_from); deba@220: _core_bits::DigraphCopySelector:: kpeter@282: copy(_from, _to, nodeRefMap, arcRefMap); deba@220: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@220: _node_maps[i]->copy(_from, nodeRefMap); deba@220: } deba@220: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@220: _arc_maps[i]->copy(_from, arcRefMap); deba@220: } deba@220: } deba@220: deba@220: protected: deba@220: deba@220: const From& _from; deba@220: To& _to; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > kpeter@282: _node_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > kpeter@282: _arc_maps; deba@220: deba@220: }; deba@220: deba@220: /// \brief Copy a digraph to another digraph. deba@220: /// kpeter@282: /// This function copies a digraph to another digraph. kpeter@282: /// The complete usage of it is detailed in the DigraphCopy class, but kpeter@282: /// a short example shows a basic work: deba@220: ///\code kpeter@282: /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run(); deba@220: ///\endcode deba@220: /// deba@220: /// After the copy the \c nr map will contain the mapping from the deba@220: /// nodes of the \c from digraph to the nodes of the \c to digraph and kpeter@282: /// \c acr will contain the mapping from the arcs of the \c to digraph deba@220: /// to the arcs of the \c from digraph. deba@220: /// deba@220: /// \see DigraphCopy kpeter@282: template kpeter@282: DigraphCopy digraphCopy(const From& from, To& to) { kpeter@282: return DigraphCopy(from, to); deba@220: } deba@220: deba@220: /// \brief Class to copy a graph. deba@220: /// deba@220: /// Class to copy a graph to another graph (duplicate a graph). The kpeter@282: /// simplest way of using it is through the \c graphCopy() function. deba@220: /// kpeter@282: /// This class not only make a copy of a graph, but it can create deba@220: /// references and cross references between the nodes, edges and arcs of kpeter@282: /// the two graphs, and it can copy maps for using with the newly created kpeter@282: /// graph. deba@220: /// deba@220: /// To make a copy from a graph, first an instance of GraphCopy deba@220: /// should be created, then the data belongs to the graph should deba@220: /// assigned to copy. In the end, the \c run() member should be deba@220: /// called. deba@220: /// deba@220: /// The next code copies a graph with several data: deba@220: ///\code kpeter@282: /// GraphCopy cg(orig_graph, new_graph); kpeter@282: /// // Create references for the nodes deba@220: /// OrigGraph::NodeMap nr(orig_graph); kpeter@282: /// cg.nodeRef(nr); kpeter@282: /// // Create cross references (inverse) for the edges kpeter@282: /// NewGraph::EdgeMap ecr(new_graph); kpeter@282: /// cg.edgeCrossRef(ecr); kpeter@282: /// // Copy an edge map kpeter@282: /// OrigGraph::EdgeMap oemap(orig_graph); kpeter@282: /// NewGraph::EdgeMap nemap(new_graph); kpeter@282: /// cg.edgeMap(oemap, nemap); kpeter@282: /// // Copy a node deba@220: /// OrigGraph::Node on; deba@220: /// NewGraph::Node nn; kpeter@282: /// cg.node(on, nn); kpeter@282: /// // Execute copying kpeter@282: /// cg.run(); deba@220: ///\endcode kpeter@282: template deba@220: class GraphCopy { deba@220: private: deba@220: deba@220: typedef typename From::Node Node; deba@220: typedef typename From::NodeIt NodeIt; deba@220: typedef typename From::Arc Arc; deba@220: typedef typename From::ArcIt ArcIt; deba@220: typedef typename From::Edge Edge; deba@220: typedef typename From::EdgeIt EdgeIt; deba@220: deba@220: typedef typename To::Node TNode; deba@220: typedef typename To::Arc TArc; deba@220: typedef typename To::Edge TEdge; deba@220: deba@220: typedef typename From::template NodeMap NodeRefMap; deba@220: typedef typename From::template EdgeMap EdgeRefMap; deba@220: deba@220: struct ArcRefMap { kpeter@282: ArcRefMap(const From& from, const To& to, deba@220: const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) kpeter@282: : _from(from), _to(to), deba@220: _edge_ref(edge_ref), _node_ref(node_ref) {} deba@220: deba@220: typedef typename From::Arc Key; deba@220: typedef typename To::Arc Value; deba@220: deba@220: Value operator[](const Key& key) const { deba@220: bool forward = _from.u(key) != _from.v(key) ? deba@220: _node_ref[_from.source(key)] == deba@220: _to.source(_to.direct(_edge_ref[key], true)) : deba@220: _from.direction(key); deba@220: return _to.direct(_edge_ref[key], forward); deba@220: } deba@220: kpeter@282: const From& _from; deba@220: const To& _to; deba@220: const EdgeRefMap& _edge_ref; deba@220: const NodeRefMap& _node_ref; deba@220: }; deba@220: deba@220: public: deba@220: kpeter@282: /// \brief Constructor of GraphCopy. deba@220: /// kpeter@282: /// Constructor of GraphCopy for copying the content of the kpeter@282: /// \c from graph into the \c to graph. kpeter@282: GraphCopy(const From& from, To& to) deba@220: : _from(from), _to(to) {} deba@220: kpeter@282: /// \brief Destructor of GraphCopy deba@220: /// kpeter@282: /// Destructor of GraphCopy. deba@220: ~GraphCopy() { deba@220: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@220: delete _node_maps[i]; deba@220: } deba@220: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@220: delete _arc_maps[i]; deba@220: } deba@220: for (int i = 0; i < int(_edge_maps.size()); ++i) { deba@220: delete _edge_maps[i]; deba@220: } deba@220: } deba@220: kpeter@282: /// \brief Copy the node references into the given map. deba@220: /// kpeter@282: /// This function copies the node references into the given map. kpeter@282: /// The parameter should be a map, whose key type is the Node type of kpeter@282: /// the source graph, while the value type is the Node type of the kpeter@282: /// destination graph. deba@220: template deba@220: GraphCopy& nodeRef(NodeRef& map) { deba@220: _node_maps.push_back(new _core_bits::RefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the node cross references into the given map. deba@220: /// kpeter@282: /// This function copies the node cross references (reverse references) kpeter@282: /// into the given map. The parameter should be a map, whose key type kpeter@282: /// is the Node type of the destination graph, while the value type is kpeter@282: /// the Node type of the source graph. deba@220: template deba@220: GraphCopy& nodeCrossRef(NodeCrossRef& map) { deba@220: _node_maps.push_back(new _core_bits::CrossRefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Make a copy of the given node map. deba@220: /// kpeter@282: /// This function makes a copy of the given node map for the newly kpeter@282: /// created graph. kpeter@282: /// The key type of the new map \c tmap should be the Node type of the kpeter@282: /// destination graph, and the key type of the original map \c map kpeter@282: /// should be the Node type of the source graph. kpeter@282: template kpeter@282: GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { deba@220: _node_maps.push_back(new _core_bits::MapCopy(map, tmap)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given node. deba@220: /// kpeter@282: /// This function makes a copy of the given node. kpeter@282: GraphCopy& node(const Node& node, TNode& tnode) { deba@220: _node_maps.push_back(new _core_bits::ItemCopy(node, tnode)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the arc references into the given map. deba@220: /// kpeter@282: /// This function copies the arc references into the given map. kpeter@282: /// The parameter should be a map, whose key type is the Arc type of kpeter@282: /// the source graph, while the value type is the Arc type of the kpeter@282: /// destination graph. deba@220: template deba@220: GraphCopy& arcRef(ArcRef& map) { deba@220: _arc_maps.push_back(new _core_bits::RefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the arc cross references into the given map. deba@220: /// kpeter@282: /// This function copies the arc cross references (reverse references) kpeter@282: /// into the given map. The parameter should be a map, whose key type kpeter@282: /// is the Arc type of the destination graph, while the value type is kpeter@282: /// the Arc type of the source graph. deba@220: template deba@220: GraphCopy& arcCrossRef(ArcCrossRef& map) { deba@220: _arc_maps.push_back(new _core_bits::CrossRefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Make a copy of the given arc map. deba@220: /// kpeter@282: /// This function makes a copy of the given arc map for the newly kpeter@282: /// created graph. kpeter@282: /// The key type of the new map \c tmap should be the Arc type of the kpeter@282: /// destination graph, and the key type of the original map \c map kpeter@282: /// should be the Arc type of the source graph. kpeter@282: template kpeter@282: GraphCopy& arcMap(const FromMap& map, ToMap& tmap) { deba@220: _arc_maps.push_back(new _core_bits::MapCopy(map, tmap)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given arc. deba@220: /// kpeter@282: /// This function makes a copy of the given arc. kpeter@282: GraphCopy& arc(const Arc& arc, TArc& tarc) { deba@220: _arc_maps.push_back(new _core_bits::ItemCopy(arc, tarc)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the edge references into the given map. deba@220: /// kpeter@282: /// This function copies the edge references into the given map. kpeter@282: /// The parameter should be a map, whose key type is the Edge type of kpeter@282: /// the source graph, while the value type is the Edge type of the kpeter@282: /// destination graph. deba@220: template deba@220: GraphCopy& edgeRef(EdgeRef& map) { deba@220: _edge_maps.push_back(new _core_bits::RefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Copy the edge cross references into the given map. deba@220: /// kpeter@282: /// This function copies the edge cross references (reverse references) kpeter@282: /// into the given map. The parameter should be a map, whose key type kpeter@282: /// is the Edge type of the destination graph, while the value type is kpeter@282: /// the Edge type of the source graph. deba@220: template deba@220: GraphCopy& edgeCrossRef(EdgeCrossRef& map) { deba@220: _edge_maps.push_back(new _core_bits::CrossRefCopy(map)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Make a copy of the given edge map. deba@220: /// kpeter@282: /// This function makes a copy of the given edge map for the newly kpeter@282: /// created graph. kpeter@282: /// The key type of the new map \c tmap should be the Edge type of the kpeter@282: /// destination graph, and the key type of the original map \c map kpeter@282: /// should be the Edge type of the source graph. kpeter@282: template kpeter@282: GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { deba@220: _edge_maps.push_back(new _core_bits::MapCopy(map, tmap)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given edge. deba@220: /// kpeter@282: /// This function makes a copy of the given edge. kpeter@282: GraphCopy& edge(const Edge& edge, TEdge& tedge) { deba@220: _edge_maps.push_back(new _core_bits::ItemCopy(edge, tedge)); deba@220: return *this; deba@220: } deba@220: kpeter@282: /// \brief Execute copying. deba@220: /// kpeter@282: /// This function executes the copying of the graph along with the kpeter@282: /// copying of the assigned data. deba@220: void run() { deba@220: NodeRefMap nodeRefMap(_from); deba@220: EdgeRefMap edgeRefMap(_from); kpeter@282: ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap); deba@220: _core_bits::GraphCopySelector:: kpeter@282: copy(_from, _to, nodeRefMap, edgeRefMap); deba@220: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@220: _node_maps[i]->copy(_from, nodeRefMap); deba@220: } deba@220: for (int i = 0; i < int(_edge_maps.size()); ++i) { deba@220: _edge_maps[i]->copy(_from, edgeRefMap); deba@220: } deba@220: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@220: _arc_maps[i]->copy(_from, arcRefMap); deba@220: } deba@220: } deba@220: deba@220: private: deba@220: deba@220: const From& _from; deba@220: To& _to; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > kpeter@282: _node_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > kpeter@282: _arc_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > kpeter@282: _edge_maps; deba@220: deba@220: }; deba@220: deba@220: /// \brief Copy a graph to another graph. deba@220: /// kpeter@282: /// This function copies a graph to another graph. kpeter@282: /// The complete usage of it is detailed in the GraphCopy class, kpeter@282: /// but a short example shows a basic work: deba@220: ///\code kpeter@282: /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); deba@220: ///\endcode deba@220: /// deba@220: /// After the copy the \c nr map will contain the mapping from the deba@220: /// nodes of the \c from graph to the nodes of the \c to graph and kpeter@282: /// \c ecr will contain the mapping from the edges of the \c to graph kpeter@282: /// to the edges of the \c from graph. deba@220: /// deba@220: /// \see GraphCopy kpeter@282: template kpeter@282: GraphCopy kpeter@282: graphCopy(const From& from, To& to) { kpeter@282: return GraphCopy(from, to); deba@220: } deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template deba@220: struct FindArcSelector { deba@220: typedef typename Graph::Node Node; deba@220: typedef typename Graph::Arc Arc; deba@220: static Arc find(const Graph &g, Node u, Node v, Arc e) { deba@220: if (e == INVALID) { deba@220: g.firstOut(e, u); deba@220: } else { deba@220: g.nextOut(e); deba@220: } deba@220: while (e != INVALID && g.target(e) != v) { deba@220: g.nextOut(e); deba@220: } deba@220: return e; deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct FindArcSelector< deba@220: Graph, kpeter@282: typename enable_if::type> deba@220: { deba@220: typedef typename Graph::Node Node; deba@220: typedef typename Graph::Arc Arc; deba@220: static Arc find(const Graph &g, Node u, Node v, Arc prev) { deba@220: return g.findArc(u, v, prev); deba@220: } deba@220: }; deba@220: } deba@220: kpeter@282: /// \brief Find an arc between two nodes of a digraph. deba@220: /// kpeter@282: /// This function finds an arc from node \c u to node \c v in the kpeter@282: /// digraph \c g. deba@220: /// deba@220: /// If \c prev is \ref INVALID (this is the default value), then deba@220: /// it finds the first arc from \c u to \c v. Otherwise it looks for deba@220: /// the next arc from \c u to \c v after \c prev. deba@220: /// \return The found arc or \ref INVALID if there is no such an arc. deba@220: /// deba@220: /// Thus you can iterate through each arc from \c u to \c v as it follows. deba@220: ///\code kpeter@282: /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// kpeter@282: /// \note \ref ConArcIt provides iterator interface for the same kpeter@282: /// functionality. kpeter@282: /// deba@220: ///\sa ConArcIt kpeter@282: ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp deba@220: template deba@220: inline typename Graph::Arc deba@220: findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, deba@220: typename Graph::Arc prev = INVALID) { deba@220: return _core_bits::FindArcSelector::find(g, u, v, prev); deba@220: } deba@220: kpeter@282: /// \brief Iterator for iterating on parallel arcs connecting the same nodes. deba@220: /// kpeter@282: /// Iterator for iterating on parallel arcs connecting the same nodes. It is kpeter@282: /// a higher level interface for the \ref findArc() function. You can deba@220: /// use it the following way: deba@220: ///\code deba@220: /// for (ConArcIt it(g, src, trg); it != INVALID; ++it) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// deba@220: ///\sa findArc() kpeter@282: ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp deba@220: template deba@220: class ConArcIt : public _Graph::Arc { deba@220: public: deba@220: deba@220: typedef _Graph Graph; deba@220: typedef typename Graph::Arc Parent; deba@220: deba@220: typedef typename Graph::Arc Arc; deba@220: typedef typename Graph::Node Node; deba@220: deba@220: /// \brief Constructor. deba@220: /// kpeter@282: /// Construct a new ConArcIt iterating on the arcs that kpeter@282: /// connects nodes \c u and \c v. deba@220: ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { deba@220: Parent::operator=(findArc(_graph, u, v)); deba@220: } deba@220: deba@220: /// \brief Constructor. deba@220: /// kpeter@282: /// Construct a new ConArcIt that continues the iterating from arc \c a. deba@220: ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} deba@220: deba@220: /// \brief Increment operator. deba@220: /// deba@220: /// It increments the iterator and gives back the next arc. deba@220: ConArcIt& operator++() { deba@220: Parent::operator=(findArc(_graph, _graph.source(*this), deba@220: _graph.target(*this), *this)); deba@220: return *this; deba@220: } deba@220: private: deba@220: const Graph& _graph; deba@220: }; deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template deba@220: struct FindEdgeSelector { deba@220: typedef typename Graph::Node Node; deba@220: typedef typename Graph::Edge Edge; deba@220: static Edge find(const Graph &g, Node u, Node v, Edge e) { deba@220: bool b; deba@220: if (u != v) { deba@220: if (e == INVALID) { deba@220: g.firstInc(e, b, u); deba@220: } else { deba@220: b = g.u(e) == u; deba@220: g.nextInc(e, b); deba@220: } deba@220: while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) { deba@220: g.nextInc(e, b); deba@220: } deba@220: } else { deba@220: if (e == INVALID) { deba@220: g.firstInc(e, b, u); deba@220: } else { deba@220: b = true; deba@220: g.nextInc(e, b); deba@220: } deba@220: while (e != INVALID && (!b || g.v(e) != v)) { deba@220: g.nextInc(e, b); deba@220: } deba@220: } deba@220: return e; deba@220: } deba@220: }; deba@220: deba@220: template deba@220: struct FindEdgeSelector< deba@220: Graph, deba@220: typename enable_if::type> deba@220: { deba@220: typedef typename Graph::Node Node; deba@220: typedef typename Graph::Edge Edge; deba@220: static Edge find(const Graph &g, Node u, Node v, Edge prev) { deba@220: return g.findEdge(u, v, prev); deba@220: } deba@220: }; deba@220: } deba@220: kpeter@282: /// \brief Find an edge between two nodes of a graph. deba@220: /// kpeter@282: /// This function finds an edge from node \c u to node \c v in graph \c g. kpeter@282: /// If node \c u and node \c v is equal then each loop edge deba@220: /// will be enumerated once. deba@220: /// deba@220: /// If \c prev is \ref INVALID (this is the default value), then kpeter@282: /// it finds the first edge from \c u to \c v. Otherwise it looks for kpeter@282: /// the next edge from \c u to \c v after \c prev. kpeter@282: /// \return The found edge or \ref INVALID if there is no such an edge. deba@220: /// kpeter@282: /// Thus you can iterate through each edge between \c u and \c v kpeter@282: /// as it follows. deba@220: ///\code kpeter@282: /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// kpeter@282: /// \note \ref ConEdgeIt provides iterator interface for the same kpeter@282: /// functionality. kpeter@282: /// deba@220: ///\sa ConEdgeIt deba@220: template deba@220: inline typename Graph::Edge deba@220: findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, deba@220: typename Graph::Edge p = INVALID) { deba@220: return _core_bits::FindEdgeSelector::find(g, u, v, p); deba@220: } deba@220: kpeter@282: /// \brief Iterator for iterating on parallel edges connecting the same nodes. deba@220: /// kpeter@282: /// Iterator for iterating on parallel edges connecting the same nodes. kpeter@282: /// It is a higher level interface for the findEdge() function. You can deba@220: /// use it the following way: deba@220: ///\code kpeter@282: /// for (ConEdgeIt it(g, u, v); it != INVALID; ++it) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// deba@220: ///\sa findEdge() deba@220: template deba@220: class ConEdgeIt : public _Graph::Edge { deba@220: public: deba@220: deba@220: typedef _Graph Graph; deba@220: typedef typename Graph::Edge Parent; deba@220: deba@220: typedef typename Graph::Edge Edge; deba@220: typedef typename Graph::Node Node; deba@220: deba@220: /// \brief Constructor. deba@220: /// kpeter@282: /// Construct a new ConEdgeIt iterating on the edges that kpeter@282: /// connects nodes \c u and \c v. deba@220: ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { deba@220: Parent::operator=(findEdge(_graph, u, v)); deba@220: } deba@220: deba@220: /// \brief Constructor. deba@220: /// kpeter@282: /// Construct a new ConEdgeIt that continues iterating from edge \c e. deba@220: ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} deba@220: deba@220: /// \brief Increment operator. deba@220: /// deba@220: /// It increments the iterator and gives back the next edge. deba@220: ConEdgeIt& operator++() { deba@220: Parent::operator=(findEdge(_graph, _graph.u(*this), deba@220: _graph.v(*this), *this)); deba@220: return *this; deba@220: } deba@220: private: deba@220: const Graph& _graph; deba@220: }; deba@220: deba@220: kpeter@282: ///Dynamic arc look-up between given endpoints. deba@220: deba@220: ///Using this class, you can find an arc in a digraph from a given kpeter@282: ///source to a given target in amortized time O(logd), deba@220: ///where d is the out-degree of the source node. deba@220: /// deba@220: ///It is possible to find \e all parallel arcs between two nodes with deba@233: ///the \c operator() member. deba@220: /// kpeter@282: ///This is a dynamic data structure. Consider to use \ref ArcLookUp or kpeter@282: ///\ref AllArcLookUp if your digraph is not changed so frequently. deba@220: /// kpeter@282: ///This class uses a self-adjusting binary search tree, the Splay tree kpeter@282: ///of Sleator and Tarjan to guarantee the logarithmic amortized kpeter@282: ///time bound for arc look-ups. This class also guarantees the deba@220: ///optimal time bound in a constant factor for any distribution of deba@220: ///queries. deba@220: /// deba@220: ///\tparam G The type of the underlying digraph. deba@220: /// deba@220: ///\sa ArcLookUp deba@220: ///\sa AllArcLookUp deba@220: template deba@220: class DynArcLookUp deba@220: : protected ItemSetTraits::ItemNotifier::ObserverBase deba@220: { deba@220: public: deba@220: typedef typename ItemSetTraits deba@220: ::ItemNotifier::ObserverBase Parent; deba@220: deba@220: TEMPLATE_DIGRAPH_TYPEDEFS(G); deba@220: typedef G Digraph; deba@220: deba@220: protected: deba@220: deba@220: class AutoNodeMap : public ItemSetTraits::template Map::Type { deba@220: public: deba@220: deba@220: typedef typename ItemSetTraits::template Map::Type Parent; deba@220: deba@220: AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {} deba@220: deba@220: virtual void add(const Node& node) { deba@220: Parent::add(node); deba@220: Parent::set(node, INVALID); deba@220: } deba@220: deba@220: virtual void add(const std::vector& nodes) { deba@220: Parent::add(nodes); deba@220: for (int i = 0; i < int(nodes.size()); ++i) { deba@220: Parent::set(nodes[i], INVALID); deba@220: } deba@220: } deba@220: deba@220: virtual void build() { deba@220: Parent::build(); deba@220: Node it; deba@220: typename Parent::Notifier* nf = Parent::notifier(); deba@220: for (nf->first(it); it != INVALID; nf->next(it)) { deba@220: Parent::set(it, INVALID); deba@220: } deba@220: } deba@220: }; deba@220: deba@220: const Digraph &_g; deba@220: AutoNodeMap _head; deba@220: typename Digraph::template ArcMap _parent; deba@220: typename Digraph::template ArcMap _left; deba@220: typename Digraph::template ArcMap _right; deba@220: deba@220: class ArcLess { deba@220: const Digraph &g; deba@220: public: deba@220: ArcLess(const Digraph &_g) : g(_g) {} deba@220: bool operator()(Arc a,Arc b) const deba@220: { deba@220: return g.target(a)& arcs) { deba@220: for (int i = 0; i < int(arcs.size()); ++i) { deba@220: insert(arcs[i]); deba@220: } deba@220: } deba@220: deba@220: virtual void erase(const Arc& arc) { deba@220: remove(arc); deba@220: } deba@220: deba@220: virtual void erase(const std::vector& arcs) { deba@220: for (int i = 0; i < int(arcs.size()); ++i) { deba@220: remove(arcs[i]); deba@220: } deba@220: } deba@220: deba@220: virtual void build() { deba@220: refresh(); deba@220: } deba@220: deba@220: virtual void clear() { deba@220: for(NodeIt n(_g);n!=INVALID;++n) { deba@220: _head.set(n, INVALID); deba@220: } deba@220: } deba@220: deba@220: void insert(Arc arc) { deba@220: Node s = _g.source(arc); deba@220: Node t = _g.target(arc); deba@220: _left.set(arc, INVALID); deba@220: _right.set(arc, INVALID); deba@220: deba@220: Arc e = _head[s]; deba@220: if (e == INVALID) { deba@220: _head.set(s, arc); deba@220: _parent.set(arc, INVALID); deba@220: return; deba@220: } deba@220: while (true) { deba@220: if (t < _g.target(e)) { deba@220: if (_left[e] == INVALID) { deba@220: _left.set(e, arc); deba@220: _parent.set(arc, e); deba@220: splay(arc); deba@220: return; deba@220: } else { deba@220: e = _left[e]; deba@220: } deba@220: } else { deba@220: if (_right[e] == INVALID) { deba@220: _right.set(e, arc); deba@220: _parent.set(arc, e); deba@220: splay(arc); deba@220: return; deba@220: } else { deba@220: e = _right[e]; deba@220: } deba@220: } deba@220: } deba@220: } deba@220: deba@220: void remove(Arc arc) { deba@220: if (_left[arc] == INVALID) { deba@220: if (_right[arc] != INVALID) { deba@220: _parent.set(_right[arc], _parent[arc]); deba@220: } deba@220: if (_parent[arc] != INVALID) { deba@220: if (_left[_parent[arc]] == arc) { deba@220: _left.set(_parent[arc], _right[arc]); deba@220: } else { deba@220: _right.set(_parent[arc], _right[arc]); deba@220: } deba@220: } else { deba@220: _head.set(_g.source(arc), _right[arc]); deba@220: } deba@220: } else if (_right[arc] == INVALID) { deba@220: _parent.set(_left[arc], _parent[arc]); deba@220: if (_parent[arc] != INVALID) { deba@220: if (_left[_parent[arc]] == arc) { deba@220: _left.set(_parent[arc], _left[arc]); deba@220: } else { deba@220: _right.set(_parent[arc], _left[arc]); deba@220: } deba@220: } else { deba@220: _head.set(_g.source(arc), _left[arc]); deba@220: } deba@220: } else { deba@220: Arc e = _left[arc]; deba@220: if (_right[e] != INVALID) { deba@220: e = _right[e]; deba@220: while (_right[e] != INVALID) { deba@220: e = _right[e]; deba@220: } deba@220: Arc s = _parent[e]; deba@220: _right.set(_parent[e], _left[e]); deba@220: if (_left[e] != INVALID) { deba@220: _parent.set(_left[e], _parent[e]); deba@220: } deba@220: deba@220: _left.set(e, _left[arc]); deba@220: _parent.set(_left[arc], e); deba@220: _right.set(e, _right[arc]); deba@220: _parent.set(_right[arc], e); deba@220: deba@220: _parent.set(e, _parent[arc]); deba@220: if (_parent[arc] != INVALID) { deba@220: if (_left[_parent[arc]] == arc) { deba@220: _left.set(_parent[arc], e); deba@220: } else { deba@220: _right.set(_parent[arc], e); deba@220: } deba@220: } deba@220: splay(s); deba@220: } else { deba@220: _right.set(e, _right[arc]); deba@220: _parent.set(_right[arc], e); deba@232: _parent.set(e, _parent[arc]); deba@220: deba@220: if (_parent[arc] != INVALID) { deba@220: if (_left[_parent[arc]] == arc) { deba@220: _left.set(_parent[arc], e); deba@220: } else { deba@220: _right.set(_parent[arc], e); deba@220: } deba@220: } else { deba@220: _head.set(_g.source(arc), e); deba@220: } deba@220: } deba@220: } deba@220: } deba@220: deba@220: Arc refreshRec(std::vector &v,int a,int b) deba@220: { deba@220: int m=(a+b)/2; deba@220: Arc me=v[m]; deba@220: if (a < m) { deba@220: Arc left = refreshRec(v,a,m-1); deba@220: _left.set(me, left); deba@220: _parent.set(left, me); deba@220: } else { deba@220: _left.set(me, INVALID); deba@220: } deba@220: if (m < b) { deba@220: Arc right = refreshRec(v,m+1,b); deba@220: _right.set(me, right); deba@220: _parent.set(right, me); deba@220: } else { deba@220: _right.set(me, INVALID); deba@220: } deba@220: return me; deba@220: } deba@220: deba@220: void refresh() { deba@220: for(NodeIt n(_g);n!=INVALID;++n) { deba@220: std::vector v; deba@233: for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a); deba@233: if (!v.empty()) { deba@220: std::sort(v.begin(),v.end(),ArcLess(_g)); deba@220: Arc head = refreshRec(v,0,v.size()-1); deba@220: _head.set(n, head); deba@220: _parent.set(head, INVALID); deba@220: } deba@220: else _head.set(n, INVALID); deba@220: } deba@220: } deba@220: deba@220: void zig(Arc v) { deba@220: Arc w = _parent[v]; deba@220: _parent.set(v, _parent[w]); deba@220: _parent.set(w, v); deba@220: _left.set(w, _right[v]); deba@220: _right.set(v, w); deba@220: if (_parent[v] != INVALID) { deba@220: if (_right[_parent[v]] == w) { deba@220: _right.set(_parent[v], v); deba@220: } else { deba@220: _left.set(_parent[v], v); deba@220: } deba@220: } deba@220: if (_left[w] != INVALID){ deba@220: _parent.set(_left[w], w); deba@220: } deba@220: } deba@220: deba@220: void zag(Arc v) { deba@220: Arc w = _parent[v]; deba@220: _parent.set(v, _parent[w]); deba@220: _parent.set(w, v); deba@220: _right.set(w, _left[v]); deba@220: _left.set(v, w); deba@220: if (_parent[v] != INVALID){ deba@220: if (_left[_parent[v]] == w) { deba@220: _left.set(_parent[v], v); deba@220: } else { deba@220: _right.set(_parent[v], v); deba@220: } deba@220: } deba@220: if (_right[w] != INVALID){ deba@220: _parent.set(_right[w], w); deba@220: } deba@220: } deba@220: deba@220: void splay(Arc v) { deba@220: while (_parent[v] != INVALID) { deba@220: if (v == _left[_parent[v]]) { deba@220: if (_parent[_parent[v]] == INVALID) { deba@220: zig(v); deba@220: } else { deba@220: if (_parent[v] == _left[_parent[_parent[v]]]) { deba@220: zig(_parent[v]); deba@220: zig(v); deba@220: } else { deba@220: zig(v); deba@220: zag(v); deba@220: } deba@220: } deba@220: } else { deba@220: if (_parent[_parent[v]] == INVALID) { deba@220: zag(v); deba@220: } else { deba@220: if (_parent[v] == _left[_parent[_parent[v]]]) { deba@220: zag(v); deba@220: zig(v); deba@220: } else { deba@220: zag(_parent[v]); deba@220: zag(v); deba@220: } deba@220: } deba@220: } deba@220: } deba@220: _head[_g.source(v)] = v; deba@220: } deba@220: deba@220: deba@220: public: deba@220: deba@220: ///Find an arc between two nodes. deba@220: deba@233: ///Find an arc between two nodes. kpeter@282: ///\param s The source node. kpeter@282: ///\param t The target node. deba@233: ///\param p The previous arc between \c s and \c t. It it is INVALID or deba@233: ///not given, the operator finds the first appropriate arc. deba@233: ///\return An arc from \c s to \c t after \c p or deba@233: ///\ref INVALID if there is no more. deba@233: /// deba@233: ///For example, you can count the number of arcs from \c u to \c v in the deba@233: ///following way. deba@233: ///\code deba@233: ///DynArcLookUp ae(g); deba@233: ///... kpeter@282: ///int n = 0; kpeter@282: ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++; deba@233: ///\endcode deba@233: /// kpeter@282: ///Finding the arcs take at most O(logd) deba@233: ///amortized time, specifically, the time complexity of the lookups deba@233: ///is equal to the optimal search tree implementation for the deba@233: ///current query distribution in a constant factor. deba@233: /// deba@233: ///\note This is a dynamic data structure, therefore the data kpeter@282: ///structure is updated after each graph alteration. Thus although kpeter@282: ///this data structure is theoretically faster than \ref ArcLookUp kpeter@317: ///and \ref AllArcLookUp, it often provides worse performance than deba@233: ///them. deba@233: Arc operator()(Node s, Node t, Arc p = INVALID) const { deba@233: if (p == INVALID) { deba@233: Arc a = _head[s]; deba@233: if (a == INVALID) return INVALID; deba@233: Arc r = INVALID; deba@233: while (true) { deba@233: if (_g.target(a) < t) { deba@233: if (_right[a] == INVALID) { deba@233: const_cast(*this).splay(a); deba@233: return r; deba@233: } else { deba@233: a = _right[a]; deba@233: } deba@233: } else { deba@233: if (_g.target(a) == t) { deba@233: r = a; deba@233: } deba@233: if (_left[a] == INVALID) { deba@233: const_cast(*this).splay(a); deba@233: return r; deba@233: } else { deba@233: a = _left[a]; deba@233: } deba@233: } deba@233: } deba@233: } else { deba@233: Arc a = p; deba@233: if (_right[a] != INVALID) { deba@233: a = _right[a]; deba@233: while (_left[a] != INVALID) { deba@233: a = _left[a]; deba@233: } deba@220: const_cast(*this).splay(a); deba@233: } else { deba@233: while (_parent[a] != INVALID && _right[_parent[a]] == a) { deba@233: a = _parent[a]; deba@233: } deba@233: if (_parent[a] == INVALID) { deba@220: return INVALID; deba@220: } else { deba@233: a = _parent[a]; deba@220: const_cast(*this).splay(a); deba@220: } deba@220: } deba@233: if (_g.target(a) == t) return a; deba@233: else return INVALID; deba@220: } deba@220: } deba@220: deba@220: }; deba@220: kpeter@282: ///Fast arc look-up between given endpoints. deba@220: deba@220: ///Using this class, you can find an arc in a digraph from a given kpeter@282: ///source to a given target in time O(logd), deba@220: ///where d is the out-degree of the source node. deba@220: /// deba@220: ///It is not possible to find \e all parallel arcs between two nodes. deba@220: ///Use \ref AllArcLookUp for this purpose. deba@220: /// kpeter@282: ///\warning This class is static, so you should call refresh() (or at kpeter@282: ///least refresh(Node)) to refresh this data structure whenever the kpeter@282: ///digraph changes. This is a time consuming (superlinearly proportional kpeter@282: ///(O(m logm)) to the number of arcs). deba@220: /// deba@220: ///\tparam G The type of the underlying digraph. deba@220: /// deba@220: ///\sa DynArcLookUp deba@220: ///\sa AllArcLookUp deba@220: template deba@220: class ArcLookUp deba@220: { deba@220: public: deba@220: TEMPLATE_DIGRAPH_TYPEDEFS(G); deba@220: typedef G Digraph; deba@220: deba@220: protected: deba@220: const Digraph &_g; deba@220: typename Digraph::template NodeMap _head; deba@220: typename Digraph::template ArcMap _left; deba@220: typename Digraph::template ArcMap _right; deba@220: deba@220: class ArcLess { deba@220: const Digraph &g; deba@220: public: deba@220: ArcLess(const Digraph &_g) : g(_g) {} deba@220: bool operator()(Arc a,Arc b) const deba@220: { deba@220: return g.target(a) &v,int a,int b) deba@220: { deba@220: int m=(a+b)/2; deba@220: Arc me=v[m]; deba@220: _left[me] = aO(d logd), where d kpeter@282: ///is the number of the outgoing arcs of \c n. deba@220: void refresh(Node n) deba@220: { deba@220: std::vector v; deba@220: for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); deba@220: if(v.size()) { deba@220: std::sort(v.begin(),v.end(),ArcLess(_g)); deba@220: _head[n]=refreshRec(v,0,v.size()-1); deba@220: } deba@220: else _head[n]=INVALID; deba@220: } deba@220: ///Refresh the full data structure. deba@220: deba@220: ///Build up the full search database. In fact, it simply calls deba@220: ///\ref refresh(Node) "refresh(n)" for each node \c n. deba@220: /// kpeter@282: ///It runs in time O(m logD), where m is kpeter@282: ///the number of the arcs in the digraph and D is the maximum deba@220: ///out-degree of the digraph. deba@220: void refresh() deba@220: { deba@220: for(NodeIt n(_g);n!=INVALID;++n) refresh(n); deba@220: } deba@220: deba@220: ///Find an arc between two nodes. deba@220: kpeter@317: ///Find an arc between two nodes in time O(logd), kpeter@317: ///where d is the number of outgoing arcs of \c s. kpeter@282: ///\param s The source node. kpeter@282: ///\param t The target node. deba@220: ///\return An arc from \c s to \c t if there exists, deba@220: ///\ref INVALID otherwise. deba@220: /// deba@220: ///\warning If you change the digraph, refresh() must be called before using deba@220: ///this operator. If you change the outgoing arcs of kpeter@282: ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. deba@220: Arc operator()(Node s, Node t) const deba@220: { deba@220: Arc e; deba@220: for(e=_head[s]; deba@220: e!=INVALID&&_g.target(e)!=t; deba@220: e = t < _g.target(e)?_left[e]:_right[e]) ; deba@220: return e; deba@220: } deba@220: deba@220: }; deba@220: kpeter@282: ///Fast look-up of all arcs between given endpoints. deba@220: deba@220: ///This class is the same as \ref ArcLookUp, with the addition kpeter@282: ///that it makes it possible to find all parallel arcs between given kpeter@282: ///endpoints. deba@220: /// kpeter@282: ///\warning This class is static, so you should call refresh() (or at kpeter@282: ///least refresh(Node)) to refresh this data structure whenever the kpeter@282: ///digraph changes. This is a time consuming (superlinearly proportional kpeter@282: ///(O(m logm)) to the number of arcs). deba@220: /// deba@220: ///\tparam G The type of the underlying digraph. deba@220: /// deba@220: ///\sa DynArcLookUp deba@220: ///\sa ArcLookUp deba@220: template deba@220: class AllArcLookUp : public ArcLookUp deba@220: { deba@220: using ArcLookUp::_g; deba@220: using ArcLookUp::_right; deba@220: using ArcLookUp::_left; deba@220: using ArcLookUp::_head; deba@220: deba@220: TEMPLATE_DIGRAPH_TYPEDEFS(G); deba@220: typedef G Digraph; deba@220: deba@220: typename Digraph::template ArcMap _next; deba@220: deba@220: Arc refreshNext(Arc head,Arc next=INVALID) deba@220: { deba@220: if(head==INVALID) return next; deba@220: else { deba@220: next=refreshNext(_right[head],next); deba@220: _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) deba@220: ? next : INVALID; deba@220: return refreshNext(_left[head],head); deba@220: } deba@220: } deba@220: deba@220: void refreshNext() deba@220: { deba@220: for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]); deba@220: } deba@220: deba@220: public: deba@220: ///Constructor deba@220: deba@220: ///Constructor. deba@220: /// deba@220: ///It builds up the search database, which remains valid until the digraph deba@220: ///changes. deba@220: AllArcLookUp(const Digraph &g) : ArcLookUp(g), _next(g) {refreshNext();} deba@220: deba@220: ///Refresh the data structure at a node. deba@220: deba@220: ///Build up the search database of node \c n. deba@220: /// kpeter@282: ///It runs in time O(d logd), where d is deba@220: ///the number of the outgoing arcs of \c n. deba@220: void refresh(Node n) deba@220: { deba@220: ArcLookUp::refresh(n); deba@220: refreshNext(_head[n]); deba@220: } deba@220: deba@220: ///Refresh the full data structure. deba@220: deba@220: ///Build up the full search database. In fact, it simply calls deba@220: ///\ref refresh(Node) "refresh(n)" for each node \c n. deba@220: /// kpeter@282: ///It runs in time O(m logD), where m is kpeter@282: ///the number of the arcs in the digraph and D is the maximum deba@220: ///out-degree of the digraph. deba@220: void refresh() deba@220: { deba@220: for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]); deba@220: } deba@220: deba@220: ///Find an arc between two nodes. deba@220: deba@220: ///Find an arc between two nodes. kpeter@282: ///\param s The source node. kpeter@282: ///\param t The target node. deba@220: ///\param prev The previous arc between \c s and \c t. It it is INVALID or deba@220: ///not given, the operator finds the first appropriate arc. deba@220: ///\return An arc from \c s to \c t after \c prev or deba@220: ///\ref INVALID if there is no more. deba@220: /// deba@220: ///For example, you can count the number of arcs from \c u to \c v in the deba@220: ///following way. deba@220: ///\code deba@220: ///AllArcLookUp ae(g); deba@220: ///... kpeter@282: ///int n = 0; kpeter@282: ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++; deba@220: ///\endcode deba@220: /// kpeter@317: ///Finding the first arc take O(logd) time, kpeter@317: ///where d is the number of outgoing arcs of \c s. Then the deba@220: ///consecutive arcs are found in constant time. deba@220: /// deba@220: ///\warning If you change the digraph, refresh() must be called before using deba@220: ///this operator. If you change the outgoing arcs of kpeter@282: ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. deba@220: /// deba@220: #ifdef DOXYGEN deba@220: Arc operator()(Node s, Node t, Arc prev=INVALID) const {} deba@220: #else deba@220: using ArcLookUp::operator() ; deba@220: Arc operator()(Node s, Node t, Arc prev) const deba@220: { deba@220: return prev==INVALID?(*this)(s,t):_next[prev]; deba@220: } deba@220: #endif deba@220: deba@220: }; deba@220: deba@220: /// @} deba@220: deba@220: } //namespace lemon deba@220: deba@220: #endif