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: 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 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; \ deba@220: typedef Digraph::ArcMap 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 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; \ deba@220: typedef typename Digraph::template ArcMap 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 BoolEdgeMap; \ deba@220: typedef Graph::EdgeMap IntEdgeMap; \ deba@220: typedef Graph::EdgeMap 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 BoolEdgeMap; \ deba@220: typedef typename Graph::template EdgeMap IntEdgeMap; \ deba@220: typedef typename Graph::template EdgeMap 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 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. 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 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. 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 deba@220: inline int countArcs(const Graph& g) { deba@220: return _core_bits::CountArcsSelector::count(g); deba@220: } deba@220: deba@220: // Edge counting: 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. 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 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 deba@220: /// in the graph. deba@220: template deba@220: inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { deba@220: 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 deba@220: /// in the graph. deba@220: template deba@220: inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { deba@220: 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 deba@220: /// in the graph. deba@220: template deba@220: inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { deba@220: 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: 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::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 deba@220: class ItemCopy : public MapCopyBase { 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 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 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 deba@220: struct DigraphCopySelector< deba@220: Digraph, deba@220: typename enable_if::type> deba@220: { deba@220: template 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 deba@220: struct GraphCopySelector { deba@220: template 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 deba@220: struct GraphCopySelector< deba@220: Graph, deba@220: typename enable_if::type> deba@220: { deba@220: template 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 dc(new_graph, orig_graph); deba@220: /// // create a reference for the nodes deba@220: /// OrigGraph::NodeMap nr(orig_graph); deba@220: /// dc.nodeRef(nr); deba@220: /// // create a cross reference (inverse) for the arcs deba@220: /// NewGraph::ArcMap acr(new_graph); deba@220: /// dc.arcCrossRef(acr); deba@220: /// // copy an arc map deba@220: /// OrigGraph::ArcMap oamap(orig_graph); deba@220: /// NewGraph::ArcMap 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 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: 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 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: 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 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: 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 deba@220: DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { deba@220: _node_maps.push_back(new _core_bits::MapCopy(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(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 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: 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 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: 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 deba@220: DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { deba@220: _arc_maps.push_back(new _core_bits::MapCopy(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(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:: 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* > deba@220: _node_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > 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 deba@220: DigraphCopy copyDigraph(To& to, const From& from) { deba@220: return DigraphCopy(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 dc(new_graph, orig_graph); deba@220: /// // create a reference for the nodes deba@220: /// OrigGraph::NodeMap nr(orig_graph); deba@220: /// dc.nodeRef(nr); deba@220: /// // create a cross reference (inverse) for the edges deba@220: /// NewGraph::EdgeMap ecr(new_graph); deba@220: /// dc.edgeCrossRef(ecr); deba@220: /// // copy an arc map deba@220: /// OrigGraph::ArcMap oamap(orig_graph); deba@220: /// NewGraph::ArcMap 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 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 { 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 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: 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 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: 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 deba@220: GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { deba@220: _node_maps.push_back(new _core_bits::MapCopy(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(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 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: 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 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: 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 deba@220: GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { deba@220: _arc_maps.push_back(new _core_bits::MapCopy(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(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 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: 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 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: 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 deba@220: GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { deba@220: _edge_maps.push_back(new _core_bits::MapCopy(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(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:: 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* > deba@220: _node_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > deba@220: _arc_maps; deba@220: deba@220: std::vector<_core_bits::MapCopyBase* > 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 deba@220: GraphCopy deba@220: copyGraph(To& to, const From& from) { deba@220: return GraphCopy(to, from); 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, deba@220: 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: 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 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: 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 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 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 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: 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 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: 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 it(g, src, trg); 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: /// 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@233: ///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: /// 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 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. deba@220: ///\param s The source node deba@220: ///\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: ///... deba@233: ///int n=0; deba@233: ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; deba@233: ///\endcode deba@233: /// deba@233: ///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 deba@233: ///structure is updated after each graph alteration. However, deba@233: ///theoretically this data structure is faster than \c ArcLookUp deba@233: ///or AllEdgeLookup, but it often provides worse performance than deba@233: ///them. deba@233: /// 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: 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 O(log d), 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: /// 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 (O(mlogm)) 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(dlogd), where d is deba@220: ///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: /// deba@220: ///It runs in time O(mlogD), where m is deba@220: ///the number of the arcs of \c n and D 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 O(logd), where deba@220: /// d 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 (O(mlogm)) 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; 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: /// deba@220: ///It runs in time O(dlogd), where d 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::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 O(mlogD), where m is deba@220: ///the number of the arcs of \c n and D 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 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 O(logd) time, where deba@220: /// 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 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::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