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 <vector> deba@220: #include <algorithm> deba@220: deba@220: #include <lemon/bits/enable_if.h> deba@220: #include <lemon/bits/traits.h> deba@220: deba@220: ///\file deba@220: ///\brief LEMON core utilities. 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: deba@220: ///Creates convenience typedefs for the digraph types and iterators deba@220: deba@220: ///This \c \#define creates convenience typedefs for the following types deba@220: ///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<bool> BoolNodeMap; \ deba@220: typedef Digraph::NodeMap<int> IntNodeMap; \ deba@220: typedef Digraph::NodeMap<double> DoubleNodeMap; \ deba@220: typedef Digraph::ArcMap<bool> BoolArcMap; \ deba@220: typedef Digraph::ArcMap<int> IntArcMap; \ deba@220: typedef Digraph::ArcMap<double> DoubleArcMap deba@220: deba@220: ///Creates 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<bool> BoolNodeMap; \ deba@220: typedef typename Digraph::template NodeMap<int> IntNodeMap; \ deba@220: typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ deba@220: typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ deba@220: typedef typename Digraph::template ArcMap<int> IntArcMap; \ deba@220: typedef typename Digraph::template ArcMap<double> DoubleArcMap deba@220: deba@220: ///Creates convenience typedefs for the graph types and iterators deba@220: deba@220: ///This \c \#define creates the same convenience typedefs 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 deba@220: ///on a template parameter, then use \c TEMPLATE_DIGRAPH_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<bool> BoolEdgeMap; \ deba@220: typedef Graph::EdgeMap<int> IntEdgeMap; \ deba@220: typedef Graph::EdgeMap<double> DoubleEdgeMap deba@220: deba@220: ///Creates 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<bool> BoolEdgeMap; \ deba@220: typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ deba@220: typedef typename Graph::template EdgeMap<double> DoubleEdgeMap deba@220: deba@220: /// \brief Function to count the items in the graph. deba@220: /// deba@220: /// This function counts the items (nodes, arcs etc) in the graph. deba@220: /// The complexity of the function is O(n) because deba@220: /// it iterates on all of the items. deba@220: template <typename Graph, typename Item> deba@220: inline int countItems(const Graph& g) { deba@220: typedef typename ItemSetTraits<Graph, Item>::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 <typename Graph, typename Enable = void> deba@220: struct CountNodesSelector { deba@220: static int count(const Graph &g) { deba@220: return countItems<Graph, typename Graph::Node>(g); deba@220: } deba@220: }; deba@220: deba@220: template <typename Graph> deba@220: struct CountNodesSelector< deba@220: Graph, typename deba@220: enable_if<typename Graph::NodeNumTag, void>::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. deba@220: /// The complexity of the function is O(n) but for some deba@220: /// graph structures it is specialized to run in O(1). deba@220: /// deba@220: /// If the graph contains a \e nodeNum() member function and a deba@220: /// \e NodeNumTag tag then this function calls directly the member deba@220: /// function to query the cardinality of the node set. deba@220: template <typename Graph> deba@220: inline int countNodes(const Graph& g) { deba@220: return _core_bits::CountNodesSelector<Graph>::count(g); deba@220: } deba@220: deba@220: // Arc counting: deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template <typename Graph, typename Enable = void> deba@220: struct CountArcsSelector { deba@220: static int count(const Graph &g) { deba@220: return countItems<Graph, typename Graph::Arc>(g); deba@220: } deba@220: }; deba@220: deba@220: template <typename Graph> deba@220: struct CountArcsSelector< deba@220: Graph, deba@220: typename enable_if<typename Graph::ArcNumTag, void>::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. deba@220: /// The complexity of the function is O(e) but for some deba@220: /// graph structures it is specialized to run in O(1). deba@220: /// deba@220: /// If the graph contains a \e arcNum() member function and a deba@220: /// \e EdgeNumTag tag then this function calls directly the member deba@220: /// function to query the cardinality of the arc set. deba@220: template <typename Graph> deba@220: inline int countArcs(const Graph& g) { deba@220: return _core_bits::CountArcsSelector<Graph>::count(g); deba@220: } deba@220: deba@220: // Edge counting: deba@220: namespace _core_bits { deba@220: deba@220: template <typename Graph, typename Enable = void> deba@220: struct CountEdgesSelector { deba@220: static int count(const Graph &g) { deba@220: return countItems<Graph, typename Graph::Edge>(g); deba@220: } deba@220: }; deba@220: deba@220: template <typename Graph> deba@220: struct CountEdgesSelector< deba@220: Graph, deba@220: typename enable_if<typename Graph::EdgeNumTag, void>::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. deba@220: /// The complexity of the function is O(m) but for some deba@220: /// graph structures it is specialized to run in O(1). deba@220: /// deba@220: /// If the graph contains a \e edgeNum() member function and a deba@220: /// \e EdgeNumTag tag then this function calls directly the member deba@220: /// function to query the cardinality of the edge set. deba@220: template <typename Graph> deba@220: inline int countEdges(const Graph& g) { deba@220: return _core_bits::CountEdgesSelector<Graph>::count(g); deba@220: deba@220: } deba@220: deba@220: deba@220: template <typename Graph, typename DegIt> 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 deba@220: /// in the graph. deba@220: template <typename Graph> deba@220: inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { deba@220: return countNodeDegree<Graph, typename Graph::OutArcIt>(_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 deba@220: /// in the graph. deba@220: template <typename Graph> deba@220: inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { deba@220: return countNodeDegree<Graph, typename Graph::InArcIt>(_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 deba@220: /// in the graph. deba@220: template <typename Graph> deba@220: inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { deba@220: return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); deba@220: } deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template <typename Digraph, typename Item, typename RefMap> 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 <typename Digraph, typename Item, typename RefMap, deba@220: typename ToMap, typename FromMap> deba@220: class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { deba@220: public: deba@220: deba@220: MapCopy(ToMap& tmap, const FromMap& map) deba@220: : _tmap(tmap), _map(map) {} deba@220: deba@220: virtual void copy(const Digraph& digraph, const RefMap& refMap) { deba@220: typedef typename ItemSetTraits<Digraph, Item>::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: deba@220: ToMap& _tmap; deba@220: const FromMap& _map; deba@220: }; deba@220: deba@220: template <typename Digraph, typename Item, typename RefMap, typename It> deba@220: class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> { deba@220: public: deba@220: deba@220: ItemCopy(It& it, const Item& item) : _it(it), _item(item) {} deba@220: deba@220: virtual void copy(const Digraph&, const RefMap& refMap) { deba@220: _it = refMap[_item]; deba@220: } deba@220: deba@220: private: deba@220: It& _it; deba@220: Item _item; deba@220: }; deba@220: deba@220: template <typename Digraph, typename Item, typename RefMap, typename Ref> deba@220: class RefCopy : public MapCopyBase<Digraph, Item, RefMap> { 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<Digraph, Item>::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 <typename Digraph, typename Item, typename RefMap, deba@220: typename CrossRef> deba@220: class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> { 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<Digraph, Item>::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 <typename Digraph, typename Enable = void> deba@220: struct DigraphCopySelector { deba@220: template <typename From, typename NodeRefMap, typename ArcRefMap> deba@220: static void copy(Digraph &to, const From& from, 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 <typename Digraph> deba@220: struct DigraphCopySelector< deba@220: Digraph, deba@220: typename enable_if<typename Digraph::BuildTag, void>::type> deba@220: { deba@220: template <typename From, typename NodeRefMap, typename ArcRefMap> deba@220: static void copy(Digraph &to, const From& from, deba@220: NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { deba@220: to.build(from, nodeRefMap, arcRefMap); deba@220: } deba@220: }; deba@220: deba@220: template <typename Graph, typename Enable = void> deba@220: struct GraphCopySelector { deba@220: template <typename From, typename NodeRefMap, typename EdgeRefMap> deba@220: static void copy(Graph &to, const From& from, 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 <typename Graph> deba@220: struct GraphCopySelector< deba@220: Graph, deba@220: typename enable_if<typename Graph::BuildTag, void>::type> deba@220: { deba@220: template <typename From, typename NodeRefMap, typename EdgeRefMap> deba@220: static void copy(Graph &to, const From& from, 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 deba@220: /// simplest way of using it is through the \c copyDigraph() function. deba@220: /// deba@220: /// This class not just make a copy of a graph, but it can create deba@220: /// references and cross references between the nodes and arcs of deba@220: /// the two graphs, it can copy maps for use with the newly created deba@220: /// graph and copy nodes and arcs. deba@220: /// deba@220: /// To make a copy from a graph, first an instance of DigraphCopy 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 deba@220: /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); deba@220: /// // create a reference for the nodes deba@220: /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); deba@220: /// dc.nodeRef(nr); deba@220: /// // create a cross reference (inverse) for the arcs deba@220: /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); deba@220: /// dc.arcCrossRef(acr); deba@220: /// // copy an arc map deba@220: /// OrigGraph::ArcMap<double> oamap(orig_graph); deba@220: /// NewGraph::ArcMap<double> namap(new_graph); deba@220: /// dc.arcMap(namap, oamap); deba@220: /// // copy a node deba@220: /// OrigGraph::Node on; deba@220: /// NewGraph::Node nn; deba@220: /// dc.node(nn, on); deba@220: /// // Executions of copy deba@220: /// dc.run(); deba@220: ///\endcode deba@220: template <typename To, typename From> 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<TNode> NodeRefMap; deba@220: typedef typename From::template ArcMap<TArc> ArcRefMap; deba@220: deba@220: deba@220: public: deba@220: deba@220: deba@220: /// \brief Constructor for the DigraphCopy. deba@220: /// deba@220: /// It copies the content of the \c _from digraph into the deba@220: /// \c _to digraph. deba@220: DigraphCopy(To& to, const From& from) deba@220: : _from(from), _to(to) {} deba@220: deba@220: /// \brief Destructor of the DigraphCopy deba@220: /// deba@220: /// Destructor of the 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: deba@220: /// \brief Copies the node references into the given map. deba@220: /// deba@220: /// Copies the node references into the given map. The parameter deba@220: /// should be a map, which key type is the Node type of the source deba@220: /// graph, while the value type is the Node type of the deba@220: /// destination graph. deba@220: template <typename NodeRef> deba@220: DigraphCopy& nodeRef(NodeRef& map) { deba@220: _node_maps.push_back(new _core_bits::RefCopy<From, Node, deba@220: NodeRefMap, NodeRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the node cross references into the given map. deba@220: /// deba@220: /// Copies the node cross references (reverse references) into deba@220: /// the given map. The parameter should be a map, which key type deba@220: /// is the Node type of the destination graph, while the value type is deba@220: /// the Node type of the source graph. deba@220: template <typename NodeCrossRef> deba@220: DigraphCopy& nodeCrossRef(NodeCrossRef& map) { deba@220: _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, deba@220: NodeRefMap, NodeCrossRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make copy of the given map. deba@220: /// deba@220: /// Makes copy of the given map for the newly created digraph. deba@220: /// The new map's key type is the destination graph's node type, deba@220: /// and the copied map's key type is the source graph's node type. deba@220: template <typename ToMap, typename FromMap> deba@220: DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { deba@220: _node_maps.push_back(new _core_bits::MapCopy<From, Node, deba@220: NodeRefMap, ToMap, FromMap>(tmap, map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given node. deba@220: /// deba@220: /// Make a copy of the given node. deba@220: DigraphCopy& node(TNode& tnode, const Node& snode) { deba@220: _node_maps.push_back(new _core_bits::ItemCopy<From, Node, deba@220: NodeRefMap, TNode>(tnode, snode)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the arc references into the given map. deba@220: /// deba@220: /// Copies the arc references into the given map. deba@220: template <typename ArcRef> deba@220: DigraphCopy& arcRef(ArcRef& map) { deba@220: _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, deba@220: ArcRefMap, ArcRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the arc cross references into the given map. deba@220: /// deba@220: /// Copies the arc cross references (reverse references) into deba@220: /// the given map. deba@220: template <typename ArcCrossRef> deba@220: DigraphCopy& arcCrossRef(ArcCrossRef& map) { deba@220: _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, deba@220: ArcRefMap, ArcCrossRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make copy of the given map. deba@220: /// deba@220: /// Makes copy of the given map for the newly created digraph. deba@220: /// The new map's key type is the to digraph's arc type, deba@220: /// and the copied map's key type is the from digraph's arc deba@220: /// type. deba@220: template <typename ToMap, typename FromMap> deba@220: DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { deba@220: _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, deba@220: ArcRefMap, ToMap, FromMap>(tmap, map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given arc. deba@220: /// deba@220: /// Make a copy of the given arc. deba@220: DigraphCopy& arc(TArc& tarc, const Arc& sarc) { deba@220: _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, deba@220: ArcRefMap, TArc>(tarc, sarc)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Executes the copies. deba@220: /// deba@220: /// Executes the copies. deba@220: void run() { deba@220: NodeRefMap nodeRefMap(_from); deba@220: ArcRefMap arcRefMap(_from); deba@220: _core_bits::DigraphCopySelector<To>:: deba@220: copy(_to, _from, 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: deba@220: const From& _from; deba@220: To& _to; deba@220: deba@220: std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > deba@220: _node_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > deba@220: _arc_maps; deba@220: deba@220: }; deba@220: deba@220: /// \brief Copy a digraph to another digraph. deba@220: /// deba@220: /// Copy a digraph to another digraph. The complete usage of the deba@220: /// function is detailed in the DigraphCopy class, but a short deba@220: /// example shows a basic work: deba@220: ///\code deba@220: /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(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 digraph to the nodes of the \c to digraph and deba@220: /// \c ecr 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 deba@220: template <typename To, typename From> deba@220: DigraphCopy<To, From> copyDigraph(To& to, const From& from) { deba@220: return DigraphCopy<To, From>(to, from); 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 deba@220: /// simplest way of using it is through the \c copyGraph() function. deba@220: /// deba@220: /// This class not just make a copy of a graph, but it can create deba@220: /// references and cross references between the nodes, edges and arcs of deba@220: /// the two graphs, it can copy maps for use with the newly created deba@220: /// graph and copy nodes, edges and arcs. 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 deba@220: /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); deba@220: /// // create a reference for the nodes deba@220: /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); deba@220: /// dc.nodeRef(nr); deba@220: /// // create a cross reference (inverse) for the edges deba@220: /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph); deba@220: /// dc.edgeCrossRef(ecr); deba@220: /// // copy an arc map deba@220: /// OrigGraph::ArcMap<double> oamap(orig_graph); deba@220: /// NewGraph::ArcMap<double> namap(new_graph); deba@220: /// dc.arcMap(namap, oamap); deba@220: /// // copy a node deba@220: /// OrigGraph::Node on; deba@220: /// NewGraph::Node nn; deba@220: /// dc.node(nn, on); deba@220: /// // Executions of copy deba@220: /// dc.run(); deba@220: ///\endcode deba@220: template <typename To, typename From> 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<TNode> NodeRefMap; deba@220: typedef typename From::template EdgeMap<TEdge> EdgeRefMap; deba@220: deba@220: struct ArcRefMap { deba@220: ArcRefMap(const To& to, const From& from, deba@220: const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) deba@220: : _to(to), _from(from), 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: deba@220: const To& _to; deba@220: const From& _from; deba@220: const EdgeRefMap& _edge_ref; deba@220: const NodeRefMap& _node_ref; deba@220: }; deba@220: deba@220: deba@220: public: deba@220: deba@220: deba@220: /// \brief Constructor for the GraphCopy. deba@220: /// deba@220: /// It copies the content of the \c _from graph into the deba@220: /// \c _to graph. deba@220: GraphCopy(To& to, const From& from) deba@220: : _from(from), _to(to) {} deba@220: deba@220: /// \brief Destructor of the GraphCopy deba@220: /// deba@220: /// Destructor of the 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: } deba@220: deba@220: /// \brief Copies the node references into the given map. deba@220: /// deba@220: /// Copies the node references into the given map. deba@220: template <typename NodeRef> deba@220: GraphCopy& nodeRef(NodeRef& map) { deba@220: _node_maps.push_back(new _core_bits::RefCopy<From, Node, deba@220: NodeRefMap, NodeRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the node cross references into the given map. deba@220: /// deba@220: /// Copies the node cross references (reverse references) into deba@220: /// the given map. deba@220: template <typename NodeCrossRef> deba@220: GraphCopy& nodeCrossRef(NodeCrossRef& map) { deba@220: _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, deba@220: NodeRefMap, NodeCrossRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make copy of the given map. deba@220: /// deba@220: /// Makes copy of the given map for the newly created graph. deba@220: /// The new map's key type is the to graph's node type, deba@220: /// and the copied map's key type is the from graph's node deba@220: /// type. deba@220: template <typename ToMap, typename FromMap> deba@220: GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { deba@220: _node_maps.push_back(new _core_bits::MapCopy<From, Node, deba@220: NodeRefMap, ToMap, FromMap>(tmap, map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given node. deba@220: /// deba@220: /// Make a copy of the given node. deba@220: GraphCopy& node(TNode& tnode, const Node& snode) { deba@220: _node_maps.push_back(new _core_bits::ItemCopy<From, Node, deba@220: NodeRefMap, TNode>(tnode, snode)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the arc references into the given map. deba@220: /// deba@220: /// Copies the arc references into the given map. deba@220: template <typename ArcRef> deba@220: GraphCopy& arcRef(ArcRef& map) { deba@220: _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, deba@220: ArcRefMap, ArcRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the arc cross references into the given map. deba@220: /// deba@220: /// Copies the arc cross references (reverse references) into deba@220: /// the given map. deba@220: template <typename ArcCrossRef> deba@220: GraphCopy& arcCrossRef(ArcCrossRef& map) { deba@220: _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, deba@220: ArcRefMap, ArcCrossRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make copy of the given map. deba@220: /// deba@220: /// Makes copy of the given map for the newly created graph. deba@220: /// The new map's key type is the to graph's arc type, deba@220: /// and the copied map's key type is the from graph's arc deba@220: /// type. deba@220: template <typename ToMap, typename FromMap> deba@220: GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { deba@220: _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, deba@220: ArcRefMap, ToMap, FromMap>(tmap, map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given arc. deba@220: /// deba@220: /// Make a copy of the given arc. deba@220: GraphCopy& arc(TArc& tarc, const Arc& sarc) { deba@220: _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, deba@220: ArcRefMap, TArc>(tarc, sarc)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the edge references into the given map. deba@220: /// deba@220: /// Copies the edge references into the given map. deba@220: template <typename EdgeRef> deba@220: GraphCopy& edgeRef(EdgeRef& map) { deba@220: _edge_maps.push_back(new _core_bits::RefCopy<From, Edge, deba@220: EdgeRefMap, EdgeRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Copies the edge cross references into the given map. deba@220: /// deba@220: /// Copies the edge cross references (reverse deba@220: /// references) into the given map. deba@220: template <typename EdgeCrossRef> deba@220: GraphCopy& edgeCrossRef(EdgeCrossRef& map) { deba@220: _edge_maps.push_back(new _core_bits::CrossRefCopy<From, deba@220: Edge, EdgeRefMap, EdgeCrossRef>(map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make copy of the given map. deba@220: /// deba@220: /// Makes copy of the given map for the newly created graph. deba@220: /// The new map's key type is the to graph's edge type, deba@220: /// and the copied map's key type is the from graph's edge deba@220: /// type. deba@220: template <typename ToMap, typename FromMap> deba@220: GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { deba@220: _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, deba@220: EdgeRefMap, ToMap, FromMap>(tmap, map)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Make a copy of the given edge. deba@220: /// deba@220: /// Make a copy of the given edge. deba@220: GraphCopy& edge(TEdge& tedge, const Edge& sedge) { deba@220: _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, deba@220: EdgeRefMap, TEdge>(tedge, sedge)); deba@220: return *this; deba@220: } deba@220: deba@220: /// \brief Executes the copies. deba@220: /// deba@220: /// Executes the copies. deba@220: void run() { deba@220: NodeRefMap nodeRefMap(_from); deba@220: EdgeRefMap edgeRefMap(_from); deba@220: ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); deba@220: _core_bits::GraphCopySelector<To>:: deba@220: copy(_to, _from, 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<From, Node, NodeRefMap>* > deba@220: _node_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > deba@220: _arc_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > deba@220: _edge_maps; deba@220: deba@220: }; deba@220: deba@220: /// \brief Copy a graph to another graph. deba@220: /// deba@220: /// Copy a graph to another graph. The complete usage of the deba@220: /// function is detailed in the GraphCopy class, but a short deba@220: /// example shows a basic work: deba@220: ///\code deba@220: /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(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 deba@220: /// \c ecr will contain the mapping from the arcs of the \c to graph deba@220: /// to the arcs of the \c from graph. deba@220: /// deba@220: /// \see GraphCopy deba@220: template <typename To, typename From> deba@220: GraphCopy<To, From> deba@220: copyGraph(To& to, const From& from) { deba@220: return GraphCopy<To, From>(to, from); deba@220: } deba@220: deba@220: namespace _core_bits { deba@220: deba@220: template <typename Graph, typename Enable = void> 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 <typename Graph> deba@220: struct FindArcSelector< deba@220: Graph, deba@220: typename enable_if<typename Graph::FindEdgeTag, void>::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: deba@220: /// \brief Finds an arc between two nodes of a graph. deba@220: /// deba@220: /// Finds an arc from node \c u to node \c v in graph \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 deba@220: /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// deba@220: ///\sa ArcLookUp deba@220: ///\sa AllArcLookUp deba@220: ///\sa DynArcLookUp deba@220: ///\sa ConArcIt deba@220: template <typename Graph> 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<Graph>::find(g, u, v, prev); deba@220: } deba@220: deba@220: /// \brief Iterator for iterating on arcs connected the same nodes. deba@220: /// deba@220: /// Iterator for iterating on arcs connected the same nodes. It is deba@220: /// higher level interface for the findArc() function. You can deba@220: /// use it the following way: deba@220: ///\code deba@220: /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// deba@220: ///\sa findArc() deba@220: ///\sa ArcLookUp deba@220: ///\sa AllArcLookUp deba@220: ///\sa DynArcLookUp deba@220: template <typename _Graph> 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: /// deba@220: /// Construct a new ConArcIt iterating on the arcs which deba@220: /// connects the \c u and \c v node. 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: /// deba@220: /// Construct a new ConArcIt which continues the iterating from deba@220: /// the \c e arc. 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 <typename Graph, typename Enable = void> 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 <typename Graph> deba@220: struct FindEdgeSelector< deba@220: Graph, deba@220: typename enable_if<typename Graph::FindEdgeTag, void>::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: deba@220: /// \brief Finds an edge between two nodes of a graph. deba@220: /// deba@220: /// Finds an edge from node \c u to node \c v in graph \c g. deba@220: /// If the 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 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 deba@220: /// for(Edge e = findEdge(g,u,v); e != INVALID; deba@220: /// e = findEdge(g,u,v,e)) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// deba@220: ///\sa ConEdgeIt deba@220: deba@220: template <typename Graph> 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<Graph>::find(g, u, v, p); deba@220: } deba@220: deba@220: /// \brief Iterator for iterating on edges connected the same nodes. deba@220: /// deba@220: /// Iterator for iterating on edges connected the same nodes. It is deba@220: /// higher level interface for the findEdge() function. You can deba@220: /// use it the following way: deba@220: ///\code deba@220: /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { deba@220: /// ... deba@220: /// } deba@220: ///\endcode deba@220: /// deba@220: ///\sa findEdge() deba@220: template <typename _Graph> 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: /// deba@220: /// Construct a new ConEdgeIt iterating on the edges which deba@220: /// connects the \c u and \c v node. 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: /// deba@220: /// Construct a new ConEdgeIt which continues the iterating from deba@220: /// the \c e edge. 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: deba@220: ///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 deba@220: ///source to a given target in amortized time <em>O(log d)</em>, deba@220: ///where <em>d</em> 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@220: ///the \c findFirst() and \c findNext() members. deba@220: /// deba@220: ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your deba@220: ///digraph is not changed so frequently. deba@220: /// deba@220: ///This class uses a self-adjusting binary search tree, Sleator's deba@220: ///and Tarjan's Splay tree for guarantee the logarithmic amortized deba@220: ///time bound for arc lookups. 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<class G> deba@220: class DynArcLookUp deba@220: : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase deba@220: { deba@220: public: deba@220: typedef typename ItemSetTraits<G, typename G::Arc> 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<G, Node>::template Map<Arc>::Type { deba@220: public: deba@220: deba@220: typedef typename ItemSetTraits<G, Node>::template Map<Arc>::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<Node>& 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<Arc> _parent; deba@220: typename Digraph::template ArcMap<Arc> _left; deba@220: typename Digraph::template ArcMap<Arc> _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)<g.target(b); deba@220: } deba@220: }; deba@220: deba@220: public: deba@220: deba@220: ///Constructor deba@220: deba@220: ///Constructor. deba@220: /// deba@220: ///It builds up the search database. deba@220: DynArcLookUp(const Digraph &g) deba@220: : _g(g),_head(g),_parent(g),_left(g),_right(g) deba@220: { deba@220: Parent::attach(_g.notifier(typename Digraph::Arc())); deba@220: refresh(); deba@220: } deba@220: deba@220: protected: deba@220: deba@220: virtual void add(const Arc& arc) { deba@220: insert(arc); deba@220: } deba@220: deba@220: virtual void add(const std::vector<Arc>& 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<Arc>& 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@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<Arc> &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<Arc> 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: 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@220: ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where deba@220: /// <em>d</em> is the number of outgoing arcs of \c s. deba@220: ///\param s The source node deba@220: ///\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: Arc operator()(Node s, Node t) const deba@220: { deba@220: Arc a = _head[s]; deba@220: while (true) { deba@220: if (_g.target(a) == t) { deba@220: const_cast<DynArcLookUp&>(*this).splay(a); deba@220: return a; deba@220: } else if (t < _g.target(a)) { deba@220: if (_left[a] == INVALID) { deba@220: const_cast<DynArcLookUp&>(*this).splay(a); deba@220: return INVALID; deba@220: } else { deba@220: a = _left[a]; deba@220: } deba@220: } else { deba@220: if (_right[a] == INVALID) { deba@220: const_cast<DynArcLookUp&>(*this).splay(a); deba@220: return INVALID; deba@220: } else { deba@220: a = _right[a]; deba@220: } deba@220: } deba@220: } deba@220: } deba@220: deba@220: ///Find the first arc between two nodes. deba@220: deba@220: ///Find the first arc between two nodes in time deba@220: /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of deba@220: /// outgoing arcs of \c s. deba@220: ///\param s The source node deba@220: ///\param t The target node deba@220: ///\return An arc from \c s to \c t if there exists, \ref INVALID deba@220: /// otherwise. deba@220: Arc findFirst(Node s, Node t) const deba@220: { deba@220: Arc a = _head[s]; deba@220: Arc r = INVALID; deba@220: while (true) { deba@220: if (_g.target(a) < t) { deba@220: if (_right[a] == INVALID) { deba@220: const_cast<DynArcLookUp&>(*this).splay(a); deba@220: return r; deba@220: } else { deba@220: a = _right[a]; deba@220: } deba@220: } else { deba@220: if (_g.target(a) == t) { deba@220: r = a; deba@220: } deba@220: if (_left[a] == INVALID) { deba@220: const_cast<DynArcLookUp&>(*this).splay(a); deba@220: return r; deba@220: } else { deba@220: a = _left[a]; deba@220: } deba@220: } deba@220: } deba@220: } deba@220: deba@220: ///Find the next arc between two nodes. deba@220: deba@220: ///Find the next arc between two nodes in time deba@220: /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of deba@220: /// outgoing arcs of \c s. deba@220: ///\param s The source node deba@220: ///\param t The target node deba@220: ///\return An arc from \c s to \c t if there exists, \ref INVALID deba@220: /// otherwise. deba@220: deba@220: ///\note If \c e is not the result of the previous \c findFirst() deba@220: ///operation then the amorized time bound can not be guaranteed. deba@220: #ifdef DOXYGEN deba@220: Arc findNext(Node s, Node t, Arc a) const deba@220: #else deba@220: Arc findNext(Node, Node t, Arc a) const deba@220: #endif deba@220: { deba@220: if (_right[a] != INVALID) { deba@220: a = _right[a]; deba@220: while (_left[a] != INVALID) { deba@220: a = _left[a]; deba@220: } deba@220: const_cast<DynArcLookUp&>(*this).splay(a); deba@220: } else { deba@220: while (_parent[a] != INVALID && _right[_parent[a]] == a) { deba@220: a = _parent[a]; deba@220: } deba@220: if (_parent[a] == INVALID) { deba@220: return INVALID; deba@220: } else { deba@220: a = _parent[a]; deba@220: const_cast<DynArcLookUp&>(*this).splay(a); deba@220: } deba@220: } deba@220: if (_g.target(a) == t) return a; deba@220: else return INVALID; deba@220: } deba@220: deba@220: }; deba@220: deba@220: ///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 deba@220: ///source to a given target in time <em>O(log d)</em>, deba@220: ///where <em>d</em> 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: /// deba@220: ///\warning This class is static, so you should refresh() (or at least deba@220: ///refresh(Node)) this data structure deba@220: ///whenever the digraph changes. This is a time consuming (superlinearly deba@220: ///proportional (<em>O(m</em>log<em>m)</em>) 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<class G> 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<Arc> _head; deba@220: typename Digraph::template ArcMap<Arc> _left; deba@220: typename Digraph::template ArcMap<Arc> _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)<g.target(b); deba@220: } deba@220: }; deba@220: deba@220: public: deba@220: 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: ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();} deba@220: deba@220: private: deba@220: Arc refreshRec(std::vector<Arc> &v,int a,int b) deba@220: { deba@220: int m=(a+b)/2; deba@220: Arc me=v[m]; deba@220: _left[me] = a<m?refreshRec(v,a,m-1):INVALID; deba@220: _right[me] = m<b?refreshRec(v,m+1,b):INVALID; deba@220: return me; deba@220: } deba@220: public: deba@220: ///Refresh the data structure at a node. deba@220: deba@220: ///Build up the search database of node \c n. deba@220: /// deba@220: ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is deba@220: ///the number of the outgoing arcs of \c n. deba@220: void refresh(Node n) deba@220: { deba@220: std::vector<Arc> 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: /// deba@220: ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is deba@220: ///the number of the arcs of \c n and <em>D</em> is the maximum deba@220: ///out-degree of the digraph. deba@220: 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: deba@220: ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where deba@220: /// <em>d</em> is the number of outgoing arcs of \c s. deba@220: ///\param s The source node deba@220: ///\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 deba@220: ///a single node \c n, then deba@220: ///\ref refresh(Node) "refresh(n)" is enough. deba@220: /// 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: deba@220: ///Fast look up of all arcs between given endpoints. deba@220: deba@220: ///This class is the same as \ref ArcLookUp, with the addition deba@220: ///that it makes it possible to find all arcs between given endpoints. deba@220: /// deba@220: ///\warning This class is static, so you should refresh() (or at least deba@220: ///refresh(Node)) this data structure deba@220: ///whenever the digraph changes. This is a time consuming (superlinearly deba@220: ///proportional (<em>O(m</em>log<em>m)</em>) 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<class G> deba@220: class AllArcLookUp : public ArcLookUp<G> deba@220: { deba@220: using ArcLookUp<G>::_g; deba@220: using ArcLookUp<G>::_right; deba@220: using ArcLookUp<G>::_left; deba@220: using ArcLookUp<G>::_head; deba@220: deba@220: TEMPLATE_DIGRAPH_TYPEDEFS(G); deba@220: typedef G Digraph; deba@220: deba@220: typename Digraph::template ArcMap<Arc> _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; 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>(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: /// deba@220: ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is deba@220: ///the number of the outgoing arcs of \c n. deba@220: deba@220: void refresh(Node n) deba@220: { deba@220: ArcLookUp<G>::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: /// deba@220: ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is deba@220: ///the number of the arcs of \c n and <em>D</em> is the maximum deba@220: ///out-degree of the digraph. deba@220: 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. deba@220: ///\param s The source node deba@220: ///\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<ListDigraph> ae(g); deba@220: ///... deba@220: ///int n=0; deba@220: ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; deba@220: ///\endcode deba@220: /// deba@220: ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where deba@220: /// <em>d</em> 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 deba@220: ///a single node \c n, then deba@220: ///\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<G>::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