alpar@100: /* -*- C++ -*- alpar@100: * alpar@100: * This file is a part of LEMON, a generic C++ optimization library alpar@100: * alpar@100: * Copyright (C) 2003-2008 alpar@100: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@100: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@100: * alpar@100: * Permission to use, modify and distribute this software is granted alpar@100: * provided that this copyright notice appears in all copies. For alpar@100: * precise terms see the accompanying LICENSE file. alpar@100: * alpar@100: * This software is provided "AS IS" with no warranty of any kind, alpar@100: * express or implied, and with no claim as to its suitability for any alpar@100: * purpose. alpar@100: * alpar@100: */ alpar@100: alpar@100: #ifndef LEMON_GRAPH_UTILS_H alpar@100: #define LEMON_GRAPH_UTILS_H alpar@100: alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: #include alpar@100: alpar@100: #include alpar@100: #include alpar@100: alpar@100: ///\ingroup gutils alpar@100: ///\file deba@139: ///\brief Graph utilities. alpar@100: alpar@100: namespace lemon { alpar@100: alpar@100: /// \addtogroup gutils alpar@100: /// @{ alpar@100: alpar@100: ///Creates convenience typedefs for the digraph types and iterators alpar@100: alpar@100: ///This \c \#define creates convenience typedefs for the following types alpar@100: ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, deba@139: ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, deba@148: ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. deba@148: /// deba@148: ///\note If the graph type is a dependent type, ie. the graph type depend deba@148: ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() deba@148: ///macro. deba@139: #define DIGRAPH_TYPEDEFS(Digraph) \ deba@148: typedef Digraph::Node Node; \ deba@148: typedef Digraph::NodeIt NodeIt; \ deba@148: typedef Digraph::Arc Arc; \ deba@148: typedef Digraph::ArcIt ArcIt; \ deba@148: typedef Digraph::InArcIt InArcIt; \ deba@148: typedef Digraph::OutArcIt OutArcIt; \ deba@148: typedef Digraph::NodeMap BoolNodeMap; \ deba@148: typedef Digraph::NodeMap IntNodeMap; \ deba@148: typedef Digraph::NodeMap DoubleNodeMap; \ deba@148: typedef Digraph::ArcMap BoolArcMap; \ deba@148: typedef Digraph::ArcMap IntArcMap; \ deba@148: typedef Digraph::ArcMap DoubleArcMap deba@140: deba@148: ///Creates convenience typedefs for the digraph types and iterators alpar@100: deba@148: ///\see DIGRAPH_TYPEDEFS deba@148: /// deba@148: ///\note Use this macro, if the graph type is a dependent type, deba@148: ///ie. the graph type depend on a template parameter. deba@148: #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ deba@148: typedef typename Digraph::Node Node; \ deba@148: typedef typename Digraph::NodeIt NodeIt; \ deba@148: typedef typename Digraph::Arc Arc; \ deba@148: typedef typename Digraph::ArcIt ArcIt; \ deba@148: typedef typename Digraph::InArcIt InArcIt; \ deba@148: typedef typename Digraph::OutArcIt OutArcIt; \ deba@148: typedef typename Digraph::template NodeMap BoolNodeMap; \ deba@148: typedef typename Digraph::template NodeMap IntNodeMap; \ deba@148: typedef typename Digraph::template NodeMap DoubleNodeMap; \ deba@148: typedef typename Digraph::template ArcMap BoolArcMap; \ deba@148: typedef typename Digraph::template ArcMap IntArcMap; \ deba@148: typedef typename Digraph::template ArcMap DoubleArcMap deba@148: alpar@100: ///Creates convenience typedefs for the graph types and iterators alpar@100: deba@139: ///This \c \#define creates the same convenience typedefs as defined deba@139: ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates deba@139: ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, deba@139: ///\c DoubleEdgeMap. deba@148: /// deba@148: ///\note If the graph type is a dependent type, ie. the graph type depend deba@148: ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() deba@148: ///macro. deba@139: #define GRAPH_TYPEDEFS(Graph) \ deba@139: DIGRAPH_TYPEDEFS(Graph); \ deba@148: typedef Graph::Edge Edge; \ deba@148: typedef Graph::EdgeIt EdgeIt; \ deba@148: typedef Graph::IncEdgeIt IncEdgeIt; \ deba@148: typedef Graph::EdgeMap BoolEdgeMap; \ deba@148: typedef Graph::EdgeMap IntEdgeMap; \ deba@148: typedef Graph::EdgeMap DoubleEdgeMap deba@140: deba@148: ///Creates convenience typedefs for the graph types and iterators deba@148: deba@148: ///\see GRAPH_TYPEDEFS deba@148: /// deba@148: ///\note Use this macro, if the graph type is a dependent type, deba@148: ///ie. the graph type depend on a template parameter. deba@148: #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ deba@148: TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ deba@148: typedef typename Graph::Edge Edge; \ deba@148: typedef typename Graph::EdgeIt EdgeIt; \ deba@148: typedef typename Graph::IncEdgeIt IncEdgeIt; \ deba@148: typedef typename Graph::template EdgeMap BoolEdgeMap; \ deba@148: typedef typename Graph::template EdgeMap IntEdgeMap; \ deba@148: typedef typename Graph::template EdgeMap DoubleEdgeMap deba@139: deba@139: /// \brief Function to count the items in the graph. alpar@100: /// deba@139: /// This function counts the items (nodes, arcs etc) in the graph. alpar@100: /// The complexity of the function is O(n) because alpar@100: /// it iterates on all of the items. deba@139: template deba@139: inline int countItems(const Graph& g) { deba@139: typedef typename ItemSetTraits::ItemIt ItemIt; alpar@100: int num = 0; alpar@100: for (ItemIt it(g); it != INVALID; ++it) { alpar@100: ++num; alpar@100: } alpar@100: return num; alpar@100: } alpar@100: alpar@100: // Node counting: alpar@100: deba@139: namespace _graph_utils_bits { alpar@100: deba@139: template alpar@100: struct CountNodesSelector { deba@139: static int count(const Graph &g) { deba@139: return countItems(g); alpar@100: } alpar@100: }; alpar@100: deba@139: template alpar@100: struct CountNodesSelector< deba@139: Graph, typename deba@139: enable_if::type> alpar@100: { deba@139: static int count(const Graph &g) { alpar@100: return g.nodeNum(); alpar@100: } alpar@100: }; alpar@100: } alpar@100: deba@139: /// \brief Function to count the nodes in the graph. alpar@100: /// deba@139: /// This function counts the nodes in the graph. alpar@100: /// The complexity of the function is O(n) but for some deba@139: /// graph structures it is specialized to run in O(1). alpar@100: /// deba@139: /// If the graph contains a \e nodeNum() member function and a alpar@100: /// \e NodeNumTag tag then this function calls directly the member alpar@100: /// function to query the cardinality of the node set. deba@139: template deba@139: inline int countNodes(const Graph& g) { deba@139: return _graph_utils_bits::CountNodesSelector::count(g); alpar@100: } alpar@100: deba@139: // Arc counting: deba@139: deba@139: namespace _graph_utils_bits { alpar@100: deba@139: template deba@139: struct CountArcsSelector { deba@139: static int count(const Graph &g) { deba@139: return countItems(g); alpar@100: } alpar@100: }; alpar@100: deba@139: template deba@139: struct CountArcsSelector< deba@139: Graph, deba@139: typename enable_if::type> alpar@100: { deba@139: static int count(const Graph &g) { alpar@100: return g.arcNum(); alpar@100: } alpar@100: }; alpar@100: } alpar@100: deba@139: /// \brief Function to count the arcs in the graph. alpar@100: /// deba@139: /// This function counts the arcs in the graph. alpar@100: /// The complexity of the function is O(e) but for some deba@139: /// graph structures it is specialized to run in O(1). alpar@100: /// deba@139: /// If the graph contains a \e arcNum() member function and a deba@139: /// \e EdgeNumTag tag then this function calls directly the member alpar@100: /// function to query the cardinality of the arc set. deba@139: template deba@139: inline int countArcs(const Graph& g) { deba@139: return _graph_utils_bits::CountArcsSelector::count(g); alpar@100: } alpar@100: deba@139: // Edge counting: deba@139: namespace _graph_utils_bits { alpar@100: deba@139: template alpar@100: struct CountEdgesSelector { deba@139: static int count(const Graph &g) { deba@139: return countItems(g); alpar@100: } alpar@100: }; alpar@100: deba@139: template alpar@100: struct CountEdgesSelector< deba@139: Graph, deba@139: typename enable_if::type> alpar@100: { deba@139: static int count(const Graph &g) { alpar@100: return g.edgeNum(); alpar@100: } alpar@100: }; alpar@100: } alpar@100: deba@139: /// \brief Function to count the edges in the graph. alpar@100: /// deba@139: /// This function counts the edges in the graph. deba@139: /// The complexity of the function is O(m) but for some deba@139: /// graph structures it is specialized to run in O(1). alpar@100: /// deba@139: /// If the graph contains a \e edgeNum() member function and a deba@139: /// \e EdgeNumTag tag then this function calls directly the member alpar@100: /// function to query the cardinality of the edge set. deba@139: template deba@139: inline int countEdges(const Graph& g) { deba@139: return _graph_utils_bits::CountEdgesSelector::count(g); alpar@100: alpar@100: } alpar@100: alpar@100: deba@139: template deba@139: inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { alpar@100: int num = 0; alpar@100: for (DegIt it(_g, _n); it != INVALID; ++it) { alpar@100: ++num; alpar@100: } alpar@100: return num; alpar@100: } alpar@100: alpar@100: /// \brief Function to count the number of the out-arcs from node \c n. alpar@100: /// alpar@100: /// This function counts the number of the out-arcs from node \c n deba@139: /// in the graph. deba@139: template deba@139: inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { deba@139: return countNodeDegree(_g, _n); alpar@100: } alpar@100: alpar@100: /// \brief Function to count the number of the in-arcs to node \c n. alpar@100: /// alpar@100: /// This function counts the number of the in-arcs to node \c n deba@139: /// in the graph. deba@139: template deba@139: inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { deba@139: return countNodeDegree(_g, _n); alpar@100: } alpar@100: deba@139: /// \brief Function to count the number of the inc-edges to node \c n. alpar@100: /// deba@139: /// This function counts the number of the inc-edges to node \c n deba@139: /// in the graph. deba@139: template deba@139: inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { deba@139: return countNodeDegree(_g, _n); alpar@100: } alpar@100: deba@139: namespace _graph_utils_bits { alpar@100: deba@139: template alpar@100: struct FindArcSelector { deba@139: typedef typename Graph::Node Node; deba@139: typedef typename Graph::Arc Arc; deba@139: static Arc find(const Graph &g, Node u, Node v, Arc e) { alpar@100: if (e == INVALID) { alpar@100: g.firstOut(e, u); alpar@100: } else { alpar@100: g.nextOut(e); alpar@100: } alpar@100: while (e != INVALID && g.target(e) != v) { alpar@100: g.nextOut(e); alpar@100: } alpar@100: return e; alpar@100: } alpar@100: }; alpar@100: deba@139: template alpar@100: struct FindArcSelector< deba@139: Graph, deba@139: typename enable_if::type> alpar@100: { deba@139: typedef typename Graph::Node Node; deba@139: typedef typename Graph::Arc Arc; deba@139: static Arc find(const Graph &g, Node u, Node v, Arc prev) { alpar@100: return g.findArc(u, v, prev); alpar@100: } alpar@100: }; alpar@100: } alpar@100: deba@139: /// \brief Finds an arc between two nodes of a graph. alpar@100: /// deba@139: /// Finds an arc from node \c u to node \c v in graph \c g. alpar@100: /// alpar@100: /// If \c prev is \ref INVALID (this is the default value), then alpar@100: /// it finds the first arc from \c u to \c v. Otherwise it looks for alpar@100: /// the next arc from \c u to \c v after \c prev. alpar@100: /// \return The found arc or \ref INVALID if there is no such an arc. alpar@100: /// alpar@100: /// Thus you can iterate through each arc from \c u to \c v as it follows. alpar@100: ///\code alpar@100: /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) { alpar@100: /// ... alpar@100: /// } alpar@100: ///\endcode alpar@100: /// alpar@100: ///\sa ArcLookUp alpar@100: ///\sa AllArcLookUp alpar@100: ///\sa DynArcLookUp alpar@100: ///\sa ConArcIt deba@139: template deba@139: inline typename Graph::Arc deba@139: findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, deba@139: typename Graph::Arc prev = INVALID) { deba@139: return _graph_utils_bits::FindArcSelector::find(g, u, v, prev); alpar@100: } alpar@100: alpar@100: /// \brief Iterator for iterating on arcs connected the same nodes. alpar@100: /// alpar@100: /// Iterator for iterating on arcs connected the same nodes. It is alpar@100: /// higher level interface for the findArc() function. You can alpar@100: /// use it the following way: alpar@100: ///\code deba@139: /// for (ConArcIt it(g, src, trg); it != INVALID; ++it) { alpar@100: /// ... alpar@100: /// } alpar@100: ///\endcode alpar@100: /// alpar@100: ///\sa findArc() alpar@100: ///\sa ArcLookUp alpar@100: ///\sa AllArcLookUp alpar@100: ///\sa DynArcLookUp deba@139: template deba@139: class ConArcIt : public _Graph::Arc { alpar@100: public: alpar@100: deba@139: typedef _Graph Graph; deba@139: typedef typename Graph::Arc Parent; alpar@100: deba@139: typedef typename Graph::Arc Arc; deba@139: typedef typename Graph::Node Node; alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Construct a new ConArcIt iterating on the arcs which alpar@100: /// connects the \c u and \c v node. deba@139: ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { deba@139: Parent::operator=(findArc(_graph, u, v)); alpar@100: } alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Construct a new ConArcIt which continues the iterating from alpar@100: /// the \c e arc. deba@139: ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} alpar@100: alpar@100: /// \brief Increment operator. alpar@100: /// alpar@100: /// It increments the iterator and gives back the next arc. alpar@100: ConArcIt& operator++() { deba@139: Parent::operator=(findArc(_graph, _graph.source(*this), deba@139: _graph.target(*this), *this)); alpar@100: return *this; alpar@100: } alpar@100: private: deba@139: const Graph& _graph; alpar@100: }; alpar@100: deba@139: namespace _graph_utils_bits { alpar@100: deba@139: template alpar@100: struct FindEdgeSelector { deba@139: typedef typename Graph::Node Node; deba@139: typedef typename Graph::Edge Edge; deba@139: static Edge find(const Graph &g, Node u, Node v, Edge e) { alpar@100: bool b; alpar@100: if (u != v) { alpar@100: if (e == INVALID) { alpar@100: g.firstInc(e, b, u); alpar@100: } else { alpar@100: b = g.source(e) == u; alpar@100: g.nextInc(e, b); alpar@100: } alpar@100: while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) { alpar@100: g.nextInc(e, b); alpar@100: } alpar@100: } else { alpar@100: if (e == INVALID) { alpar@100: g.firstInc(e, b, u); alpar@100: } else { alpar@100: b = true; alpar@100: g.nextInc(e, b); alpar@100: } alpar@100: while (e != INVALID && (!b || g.target(e) != v)) { alpar@100: g.nextInc(e, b); alpar@100: } alpar@100: } alpar@100: return e; alpar@100: } alpar@100: }; alpar@100: deba@139: template alpar@100: struct FindEdgeSelector< deba@139: Graph, deba@139: typename enable_if::type> alpar@100: { deba@139: typedef typename Graph::Node Node; deba@139: typedef typename Graph::Edge Edge; deba@139: static Edge find(const Graph &g, Node u, Node v, Edge prev) { alpar@100: return g.findEdge(u, v, prev); alpar@100: } alpar@100: }; alpar@100: } alpar@100: deba@139: /// \brief Finds an edge between two nodes of a graph. alpar@100: /// deba@139: /// Finds an edge from node \c u to node \c v in graph \c g. deba@139: /// If the node \c u and node \c v is equal then each loop edge deba@139: /// will be enumerated once. alpar@100: /// alpar@100: /// If \c prev is \ref INVALID (this is the default value), then alpar@100: /// it finds the first arc from \c u to \c v. Otherwise it looks for alpar@100: /// the next arc from \c u to \c v after \c prev. alpar@100: /// \return The found arc or \ref INVALID if there is no such an arc. alpar@100: /// alpar@100: /// Thus you can iterate through each arc from \c u to \c v as it follows. alpar@100: ///\code alpar@100: /// for(Edge e = findEdge(g,u,v); e != INVALID; alpar@100: /// e = findEdge(g,u,v,e)) { alpar@100: /// ... alpar@100: /// } alpar@100: ///\endcode alpar@100: /// alpar@100: ///\sa ConArcIt alpar@100: deba@139: template deba@139: inline typename Graph::Edge deba@139: findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, deba@139: typename Graph::Edge p = INVALID) { deba@139: return _graph_utils_bits::FindEdgeSelector::find(g, u, v, p); alpar@100: } alpar@100: alpar@100: /// \brief Iterator for iterating on edges connected the same nodes. alpar@100: /// alpar@100: /// Iterator for iterating on edges connected the same nodes. It is alpar@100: /// higher level interface for the findEdge() function. You can alpar@100: /// use it the following way: alpar@100: ///\code deba@139: /// for (ConEdgeIt it(g, src, trg); it != INVALID; ++it) { alpar@100: /// ... alpar@100: /// } alpar@100: ///\endcode alpar@100: /// alpar@100: ///\sa findEdge() deba@139: template deba@139: class ConEdgeIt : public _Graph::Edge { alpar@100: public: alpar@100: deba@139: typedef _Graph Graph; deba@139: typedef typename Graph::Edge Parent; alpar@100: deba@139: typedef typename Graph::Edge Edge; deba@139: typedef typename Graph::Node Node; alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// deba@139: /// Construct a new ConEdgeIt iterating on the edges which alpar@100: /// connects the \c u and \c v node. deba@139: ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { deba@139: Parent::operator=(findEdge(_graph, u, v)); alpar@100: } alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Construct a new ConEdgeIt which continues the iterating from deba@139: /// the \c e edge. deba@139: ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} alpar@100: alpar@100: /// \brief Increment operator. alpar@100: /// deba@139: /// It increments the iterator and gives back the next edge. alpar@100: ConEdgeIt& operator++() { deba@139: Parent::operator=(findEdge(_graph, _graph.source(*this), deba@139: _graph.target(*this), *this)); alpar@100: return *this; alpar@100: } alpar@100: private: deba@139: const Graph& _graph; alpar@100: }; alpar@100: deba@139: namespace _graph_utils_bits { alpar@100: alpar@100: template alpar@100: class MapCopyBase { alpar@100: public: alpar@100: virtual void copy(const Digraph& from, const RefMap& refMap) = 0; alpar@100: alpar@100: virtual ~MapCopyBase() {} alpar@100: }; alpar@100: alpar@100: template alpar@100: class MapCopy : public MapCopyBase { alpar@100: public: alpar@100: alpar@100: MapCopy(ToMap& tmap, const FromMap& map) alpar@100: : _tmap(tmap), _map(map) {} alpar@100: alpar@100: virtual void copy(const Digraph& digraph, const RefMap& refMap) { alpar@100: typedef typename ItemSetTraits::ItemIt ItemIt; alpar@100: for (ItemIt it(digraph); it != INVALID; ++it) { alpar@100: _tmap.set(refMap[it], _map[it]); alpar@100: } alpar@100: } alpar@100: alpar@100: private: alpar@100: ToMap& _tmap; alpar@100: const FromMap& _map; alpar@100: }; alpar@100: alpar@100: template alpar@100: class ItemCopy : public MapCopyBase { alpar@100: public: alpar@100: alpar@100: ItemCopy(It& it, const Item& item) : _it(it), _item(item) {} alpar@100: alpar@100: virtual void copy(const Digraph&, const RefMap& refMap) { alpar@100: _it = refMap[_item]; alpar@100: } alpar@100: alpar@100: private: alpar@100: It& _it; alpar@100: Item _item; alpar@100: }; alpar@100: alpar@100: template alpar@100: class RefCopy : public MapCopyBase { alpar@100: public: alpar@100: alpar@100: RefCopy(Ref& map) : _map(map) {} alpar@100: alpar@100: virtual void copy(const Digraph& digraph, const RefMap& refMap) { alpar@100: typedef typename ItemSetTraits::ItemIt ItemIt; alpar@100: for (ItemIt it(digraph); it != INVALID; ++it) { alpar@100: _map.set(it, refMap[it]); alpar@100: } alpar@100: } alpar@100: alpar@100: private: alpar@100: Ref& _map; alpar@100: }; alpar@100: alpar@100: template alpar@100: class CrossRefCopy : public MapCopyBase { alpar@100: public: alpar@100: alpar@100: CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {} alpar@100: alpar@100: virtual void copy(const Digraph& digraph, const RefMap& refMap) { alpar@100: typedef typename ItemSetTraits::ItemIt ItemIt; alpar@100: for (ItemIt it(digraph); it != INVALID; ++it) { alpar@100: _cmap.set(refMap[it], it); alpar@100: } alpar@100: } alpar@100: alpar@100: private: alpar@100: CrossRef& _cmap; alpar@100: }; alpar@100: alpar@100: template alpar@100: struct DigraphCopySelector { alpar@100: template alpar@100: static void copy(Digraph &to, const From& from, alpar@100: NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { alpar@100: for (typename From::NodeIt it(from); it != INVALID; ++it) { alpar@100: nodeRefMap[it] = to.addNode(); alpar@100: } alpar@100: for (typename From::ArcIt it(from); it != INVALID; ++it) { alpar@100: arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], alpar@100: nodeRefMap[from.target(it)]); alpar@100: } alpar@100: } alpar@100: }; alpar@100: alpar@100: template alpar@100: struct DigraphCopySelector< alpar@100: Digraph, alpar@100: typename enable_if::type> alpar@100: { alpar@100: template alpar@100: static void copy(Digraph &to, const From& from, alpar@100: NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { alpar@100: to.build(from, nodeRefMap, arcRefMap); alpar@100: } alpar@100: }; alpar@100: alpar@100: template alpar@100: struct GraphCopySelector { alpar@100: template alpar@100: static void copy(Graph &to, const From& from, alpar@100: NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { alpar@100: for (typename From::NodeIt it(from); it != INVALID; ++it) { alpar@100: nodeRefMap[it] = to.addNode(); alpar@100: } alpar@100: for (typename From::EdgeIt it(from); it != INVALID; ++it) { alpar@100: edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)], alpar@100: nodeRefMap[from.target(it)]); alpar@100: } alpar@100: } alpar@100: }; alpar@100: alpar@100: template alpar@100: struct GraphCopySelector< alpar@100: Graph, alpar@100: typename enable_if::type> alpar@100: { alpar@100: template alpar@100: static void copy(Graph &to, const From& from, alpar@100: NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { alpar@100: to.build(from, nodeRefMap, edgeRefMap); alpar@100: } alpar@100: }; alpar@100: alpar@100: } alpar@100: alpar@100: /// \brief Class to copy a digraph. alpar@100: /// alpar@100: /// Class to copy a digraph to another digraph (duplicate a digraph). The alpar@100: /// simplest way of using it is through the \c copyDigraph() function. deba@139: /// deba@139: /// This class not just make a copy of a graph, but it can create deba@139: /// references and cross references between the nodes and arcs of deba@139: /// the two graphs, it can copy maps for use with the newly created deba@139: /// graph and copy nodes and arcs. deba@139: /// deba@139: /// To make a copy from a graph, first an instance of DigraphCopy deba@139: /// should be created, then the data belongs to the graph should deba@139: /// assigned to copy. In the end, the \c run() member should be deba@139: /// called. deba@139: /// deba@139: /// The next code copies a graph with several data: deba@139: ///\code deba@139: /// DigraphCopy dc(new_graph, orig_graph); deba@139: /// // create a reference for the nodes deba@139: /// OrigGraph::NodeMap nr(orig_graph); deba@139: /// dc.nodeRef(nr); deba@139: /// // create a cross reference (inverse) for the arcs deba@139: /// NewGraph::ArcMap acr(new_graph); deba@139: /// dc.arcCrossRef(acr); deba@139: /// // copy an arc map deba@139: /// OrigGraph::ArcMap oamap(orig_graph); deba@139: /// NewGraph::ArcMap namap(new_graph); deba@139: /// dc.arcMap(namap, oamap); deba@139: /// // copy a node deba@139: /// OrigGraph::Node on; deba@139: /// NewGraph::Node nn; deba@139: /// dc.node(nn, on); deba@139: /// // Executions of copy deba@139: /// dc.run(); deba@139: ///\endcode alpar@100: template alpar@100: class DigraphCopy { alpar@100: private: alpar@100: alpar@100: typedef typename From::Node Node; alpar@100: typedef typename From::NodeIt NodeIt; alpar@100: typedef typename From::Arc Arc; alpar@100: typedef typename From::ArcIt ArcIt; alpar@100: alpar@100: typedef typename To::Node TNode; alpar@100: typedef typename To::Arc TArc; alpar@100: alpar@100: typedef typename From::template NodeMap NodeRefMap; alpar@100: typedef typename From::template ArcMap ArcRefMap; alpar@100: alpar@100: alpar@100: public: alpar@100: alpar@100: alpar@100: /// \brief Constructor for the DigraphCopy. alpar@100: /// alpar@100: /// It copies the content of the \c _from digraph into the alpar@100: /// \c _to digraph. deba@139: DigraphCopy(To& to, const From& from) deba@139: : _from(from), _to(to) {} alpar@100: alpar@100: /// \brief Destructor of the DigraphCopy alpar@100: /// alpar@100: /// Destructor of the DigraphCopy alpar@100: ~DigraphCopy() { deba@139: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@139: delete _node_maps[i]; alpar@100: } deba@139: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@139: delete _arc_maps[i]; alpar@100: } alpar@100: alpar@100: } alpar@100: alpar@100: /// \brief Copies the node references into the given map. alpar@100: /// deba@139: /// Copies the node references into the given map. The parameter deba@139: /// should be a map, which key type is the Node type of the source deba@139: /// graph, while the value type is the Node type of the deba@139: /// destination graph. alpar@100: template alpar@100: DigraphCopy& nodeRef(NodeRef& map) { deba@139: _node_maps.push_back(new _graph_utils_bits::RefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the node cross references into the given map. alpar@100: /// alpar@100: /// Copies the node cross references (reverse references) into deba@139: /// the given map. The parameter should be a map, which key type deba@139: /// is the Node type of the destination graph, while the value type is deba@139: /// the Node type of the source graph. alpar@100: template alpar@100: DigraphCopy& nodeCrossRef(NodeCrossRef& map) { deba@139: _node_maps.push_back(new _graph_utils_bits::CrossRefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make copy of the given map. alpar@100: /// deba@139: /// Makes copy of the given map for the newly created digraph. deba@139: /// The new map's key type is the destination graph's node type, deba@139: /// and the copied map's key type is the source graph's node type. alpar@100: template alpar@100: DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { deba@139: _node_maps.push_back(new _graph_utils_bits::MapCopy(tmap, map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make a copy of the given node. alpar@100: /// alpar@100: /// Make a copy of the given node. alpar@100: DigraphCopy& node(TNode& tnode, const Node& snode) { deba@139: _node_maps.push_back(new _graph_utils_bits::ItemCopy(tnode, snode)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the arc references into the given map. alpar@100: /// alpar@100: /// Copies the arc references into the given map. alpar@100: template alpar@100: DigraphCopy& arcRef(ArcRef& map) { deba@139: _arc_maps.push_back(new _graph_utils_bits::RefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the arc cross references into the given map. alpar@100: /// alpar@100: /// Copies the arc cross references (reverse references) into alpar@100: /// the given map. alpar@100: template alpar@100: DigraphCopy& arcCrossRef(ArcCrossRef& map) { deba@139: _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make copy of the given map. alpar@100: /// alpar@100: /// Makes copy of the given map for the newly created digraph. alpar@100: /// The new map's key type is the to digraph's arc type, alpar@100: /// and the copied map's key type is the from digraph's arc alpar@100: /// type. alpar@100: template alpar@100: DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { deba@139: _arc_maps.push_back(new _graph_utils_bits::MapCopy(tmap, map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make a copy of the given arc. alpar@100: /// alpar@100: /// Make a copy of the given arc. alpar@100: DigraphCopy& arc(TArc& tarc, const Arc& sarc) { deba@139: _arc_maps.push_back(new _graph_utils_bits::ItemCopy(tarc, sarc)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Executes the copies. alpar@100: /// alpar@100: /// Executes the copies. alpar@100: void run() { deba@139: NodeRefMap nodeRefMap(_from); deba@139: ArcRefMap arcRefMap(_from); deba@139: _graph_utils_bits::DigraphCopySelector:: deba@139: copy(_to, _from, nodeRefMap, arcRefMap); deba@139: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@139: _node_maps[i]->copy(_from, nodeRefMap); alpar@100: } deba@139: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@139: _arc_maps[i]->copy(_from, arcRefMap); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: deba@139: const From& _from; deba@139: To& _to; alpar@100: deba@139: std::vector<_graph_utils_bits::MapCopyBase* > deba@139: _node_maps; alpar@100: deba@139: std::vector<_graph_utils_bits::MapCopyBase* > deba@139: _arc_maps; alpar@100: alpar@100: }; alpar@100: alpar@100: /// \brief Copy a digraph to another digraph. alpar@100: /// deba@139: /// Copy a digraph to another digraph. The complete usage of the deba@139: /// function is detailed in the DigraphCopy class, but a short deba@139: /// example shows a basic work: alpar@100: ///\code alpar@100: /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); alpar@100: ///\endcode alpar@100: /// alpar@100: /// After the copy the \c nr map will contain the mapping from the alpar@100: /// nodes of the \c from digraph to the nodes of the \c to digraph and alpar@100: /// \c ecr will contain the mapping from the arcs of the \c to digraph alpar@100: /// to the arcs of the \c from digraph. alpar@100: /// alpar@100: /// \see DigraphCopy alpar@100: template alpar@100: DigraphCopy copyDigraph(To& to, const From& from) { alpar@100: return DigraphCopy(to, from); alpar@100: } alpar@100: deba@139: /// \brief Class to copy a graph. alpar@100: /// deba@139: /// Class to copy a graph to another graph (duplicate a graph). The deba@139: /// simplest way of using it is through the \c copyGraph() function. deba@139: /// deba@139: /// This class not just make a copy of a graph, but it can create deba@139: /// references and cross references between the nodes, edges and arcs of deba@139: /// the two graphs, it can copy maps for use with the newly created deba@139: /// graph and copy nodes, edges and arcs. deba@139: /// deba@139: /// To make a copy from a graph, first an instance of GraphCopy deba@139: /// should be created, then the data belongs to the graph should deba@139: /// assigned to copy. In the end, the \c run() member should be deba@139: /// called. deba@139: /// deba@139: /// The next code copies a graph with several data: deba@139: ///\code deba@139: /// GraphCopy dc(new_graph, orig_graph); deba@139: /// // create a reference for the nodes deba@139: /// OrigGraph::NodeMap nr(orig_graph); deba@139: /// dc.nodeRef(nr); deba@139: /// // create a cross reference (inverse) for the edges deba@139: /// NewGraph::EdgeMap ecr(new_graph); deba@139: /// dc.edgeCrossRef(ecr); deba@139: /// // copy an arc map deba@139: /// OrigGraph::ArcMap oamap(orig_graph); deba@139: /// NewGraph::ArcMap namap(new_graph); deba@139: /// dc.arcMap(namap, oamap); deba@139: /// // copy a node deba@139: /// OrigGraph::Node on; deba@139: /// NewGraph::Node nn; deba@139: /// dc.node(nn, on); deba@139: /// // Executions of copy deba@139: /// dc.run(); deba@139: ///\endcode alpar@100: template alpar@100: class GraphCopy { alpar@100: private: alpar@100: alpar@100: typedef typename From::Node Node; alpar@100: typedef typename From::NodeIt NodeIt; alpar@100: typedef typename From::Arc Arc; alpar@100: typedef typename From::ArcIt ArcIt; alpar@100: typedef typename From::Edge Edge; alpar@100: typedef typename From::EdgeIt EdgeIt; alpar@100: alpar@100: typedef typename To::Node TNode; alpar@100: typedef typename To::Arc TArc; alpar@100: typedef typename To::Edge TEdge; alpar@100: alpar@100: typedef typename From::template NodeMap NodeRefMap; alpar@100: typedef typename From::template EdgeMap EdgeRefMap; alpar@100: alpar@100: struct ArcRefMap { deba@139: ArcRefMap(const To& to, const From& from, deba@139: const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) deba@139: : _to(to), _from(from), deba@139: _edge_ref(edge_ref), _node_ref(node_ref) {} alpar@100: alpar@100: typedef typename From::Arc Key; alpar@100: typedef typename To::Arc Value; alpar@100: alpar@100: Value operator[](const Key& key) const { alpar@100: bool forward = deba@139: (_from.direction(key) == deba@139: (_node_ref[_from.source(key)] == _to.source(_edge_ref[key]))); deba@139: return _to.direct(_edge_ref[key], forward); alpar@100: } alpar@100: deba@139: const To& _to; deba@139: const From& _from; deba@139: const EdgeRefMap& _edge_ref; deba@139: const NodeRefMap& _node_ref; alpar@100: }; alpar@100: alpar@100: alpar@100: public: alpar@100: alpar@100: deba@139: /// \brief Constructor for the GraphCopy. alpar@100: /// deba@139: /// It copies the content of the \c _from graph into the deba@139: /// \c _to graph. deba@139: GraphCopy(To& to, const From& from) deba@139: : _from(from), _to(to) {} alpar@100: deba@139: /// \brief Destructor of the GraphCopy alpar@100: /// deba@139: /// Destructor of the GraphCopy alpar@100: ~GraphCopy() { deba@139: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@139: delete _node_maps[i]; alpar@100: } deba@139: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@139: delete _arc_maps[i]; alpar@100: } deba@139: for (int i = 0; i < int(_edge_maps.size()); ++i) { deba@139: delete _edge_maps[i]; alpar@100: } alpar@100: alpar@100: } alpar@100: alpar@100: /// \brief Copies the node references into the given map. alpar@100: /// alpar@100: /// Copies the node references into the given map. alpar@100: template alpar@100: GraphCopy& nodeRef(NodeRef& map) { deba@139: _node_maps.push_back(new _graph_utils_bits::RefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the node cross references into the given map. alpar@100: /// alpar@100: /// Copies the node cross references (reverse references) into alpar@100: /// the given map. alpar@100: template alpar@100: GraphCopy& nodeCrossRef(NodeCrossRef& map) { deba@139: _node_maps.push_back(new _graph_utils_bits::CrossRefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make copy of the given map. alpar@100: /// deba@139: /// Makes copy of the given map for the newly created graph. deba@139: /// The new map's key type is the to graph's node type, deba@139: /// and the copied map's key type is the from graph's node alpar@100: /// type. alpar@100: template alpar@100: GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { deba@139: _node_maps.push_back(new _graph_utils_bits::MapCopy(tmap, map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make a copy of the given node. alpar@100: /// alpar@100: /// Make a copy of the given node. alpar@100: GraphCopy& node(TNode& tnode, const Node& snode) { deba@139: _node_maps.push_back(new _graph_utils_bits::ItemCopy(tnode, snode)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the arc references into the given map. alpar@100: /// alpar@100: /// Copies the arc references into the given map. alpar@100: template alpar@100: GraphCopy& arcRef(ArcRef& map) { deba@139: _arc_maps.push_back(new _graph_utils_bits::RefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the arc cross references into the given map. alpar@100: /// alpar@100: /// Copies the arc cross references (reverse references) into alpar@100: /// the given map. alpar@100: template alpar@100: GraphCopy& arcCrossRef(ArcCrossRef& map) { deba@139: _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make copy of the given map. alpar@100: /// deba@139: /// Makes copy of the given map for the newly created graph. deba@139: /// The new map's key type is the to graph's arc type, deba@139: /// and the copied map's key type is the from graph's arc alpar@100: /// type. alpar@100: template alpar@100: GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { deba@139: _arc_maps.push_back(new _graph_utils_bits::MapCopy(tmap, map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make a copy of the given arc. alpar@100: /// alpar@100: /// Make a copy of the given arc. alpar@100: GraphCopy& arc(TArc& tarc, const Arc& sarc) { deba@139: _arc_maps.push_back(new _graph_utils_bits::ItemCopy(tarc, sarc)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the edge references into the given map. alpar@100: /// alpar@100: /// Copies the edge references into the given map. alpar@100: template alpar@100: GraphCopy& edgeRef(EdgeRef& map) { deba@139: _edge_maps.push_back(new _graph_utils_bits::RefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Copies the edge cross references into the given map. alpar@100: /// alpar@100: /// Copies the edge cross references (reverse alpar@100: /// references) into the given map. alpar@100: template alpar@100: GraphCopy& edgeCrossRef(EdgeCrossRef& map) { deba@139: _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy(map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make copy of the given map. alpar@100: /// deba@139: /// Makes copy of the given map for the newly created graph. deba@139: /// The new map's key type is the to graph's edge type, deba@139: /// and the copied map's key type is the from graph's edge alpar@100: /// type. alpar@100: template alpar@100: GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { deba@139: _edge_maps.push_back(new _graph_utils_bits::MapCopy(tmap, map)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Make a copy of the given edge. alpar@100: /// alpar@100: /// Make a copy of the given edge. alpar@100: GraphCopy& edge(TEdge& tedge, const Edge& sedge) { deba@139: _edge_maps.push_back(new _graph_utils_bits::ItemCopy(tedge, sedge)); alpar@100: return *this; alpar@100: } alpar@100: alpar@100: /// \brief Executes the copies. alpar@100: /// alpar@100: /// Executes the copies. alpar@100: void run() { deba@139: NodeRefMap nodeRefMap(_from); deba@139: EdgeRefMap edgeRefMap(_from); deba@139: ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); deba@139: _graph_utils_bits::GraphCopySelector:: deba@139: copy(_to, _from, nodeRefMap, edgeRefMap); deba@139: for (int i = 0; i < int(_node_maps.size()); ++i) { deba@139: _node_maps[i]->copy(_from, nodeRefMap); alpar@100: } deba@139: for (int i = 0; i < int(_edge_maps.size()); ++i) { deba@139: _edge_maps[i]->copy(_from, edgeRefMap); alpar@100: } deba@139: for (int i = 0; i < int(_arc_maps.size()); ++i) { deba@139: _arc_maps[i]->copy(_from, arcRefMap); alpar@100: } alpar@100: } alpar@100: alpar@100: private: alpar@100: deba@139: const From& _from; deba@139: To& _to; alpar@100: deba@139: std::vector<_graph_utils_bits::MapCopyBase* > deba@139: _node_maps; alpar@100: deba@139: std::vector<_graph_utils_bits::MapCopyBase* > deba@139: _arc_maps; alpar@100: deba@139: std::vector<_graph_utils_bits::MapCopyBase* > deba@139: _edge_maps; alpar@100: alpar@100: }; alpar@100: deba@139: /// \brief Copy a graph to another graph. alpar@100: /// deba@139: /// Copy a graph to another graph. The complete usage of the deba@139: /// function is detailed in the GraphCopy class, but a short deba@139: /// example shows a basic work: alpar@100: ///\code alpar@100: /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); alpar@100: ///\endcode alpar@100: /// alpar@100: /// After the copy the \c nr map will contain the mapping from the deba@139: /// nodes of the \c from graph to the nodes of the \c to graph and deba@139: /// \c ecr will contain the mapping from the arcs of the \c to graph deba@139: /// to the arcs of the \c from graph. alpar@100: /// alpar@100: /// \see GraphCopy alpar@100: template alpar@100: GraphCopy alpar@100: copyGraph(To& to, const From& from) { alpar@100: return GraphCopy(to, from); alpar@100: } alpar@100: alpar@100: /// @} alpar@100: deba@139: /// \addtogroup graph_maps alpar@100: /// @{ alpar@100: deba@139: /// Provides an immutable and unique id for each item in the graph. alpar@100: alpar@100: /// The IdMap class provides a unique and immutable id for each item of the deba@139: /// same type (e.g. node) in the graph. This id is
  • \b unique: alpar@100: /// different items (nodes) get different ids
  • \b immutable: the id of an alpar@100: /// item (node) does not change (even if you delete other nodes).
alpar@100: /// Through this map you get access (i.e. can read) the inner id values of deba@139: /// the items stored in the graph. This map can be inverted with its member deba@139: /// class \c InverseMap or with the \c operator() member. alpar@100: /// deba@139: template alpar@100: class IdMap { alpar@100: public: deba@139: typedef _Graph Graph; alpar@100: typedef int Value; alpar@100: typedef _Item Item; alpar@100: typedef _Item Key; alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor of the map. deba@139: explicit IdMap(const Graph& graph) : _graph(&graph) {} alpar@100: alpar@100: /// \brief Gives back the \e id of the item. alpar@100: /// alpar@100: /// Gives back the immutable and unique \e id of the item. deba@139: int operator[](const Item& item) const { return _graph->id(item);} alpar@100: alpar@100: /// \brief Gives back the item by its id. alpar@100: /// alpar@100: /// Gives back the item by its id. deba@139: Item operator()(int id) { return _graph->fromId(id, Item()); } alpar@100: alpar@100: private: deba@139: const Graph* _graph; alpar@100: alpar@100: public: alpar@100: alpar@100: /// \brief The class represents the inverse of its owner (IdMap). alpar@100: /// alpar@100: /// The class represents the inverse of its owner (IdMap). alpar@100: /// \see inverse() alpar@100: class InverseMap { alpar@100: public: alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor for creating an id-to-item map. deba@139: explicit InverseMap(const Graph& graph) : _graph(&graph) {} alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor for creating an id-to-item map. deba@139: explicit InverseMap(const IdMap& map) : _graph(map._graph) {} alpar@100: alpar@100: /// \brief Gives back the given item from its id. alpar@100: /// alpar@100: /// Gives back the given item from its id. alpar@100: /// deba@139: Item operator[](int id) const { return _graph->fromId(id, Item());} alpar@100: alpar@100: private: deba@139: const Graph* _graph; alpar@100: }; alpar@100: alpar@100: /// \brief Gives back the inverse of the map. alpar@100: /// alpar@100: /// Gives back the inverse of the IdMap. deba@139: InverseMap inverse() const { return InverseMap(*_graph);} alpar@100: alpar@100: }; alpar@100: alpar@100: deba@139: /// \brief General invertable graph-map type. alpar@100: deba@139: /// This type provides simple invertable graph-maps. alpar@100: /// The InvertableMap wraps an arbitrary ReadWriteMap alpar@100: /// and if a key is set to a new value then store it alpar@100: /// in the inverse map. alpar@100: /// alpar@100: /// The values of the map can be accessed alpar@100: /// with stl compatible forward iterator. alpar@100: /// kpeter@157: /// \tparam _Graph The graph type. kpeter@157: /// \tparam _Item The item type of the graph. kpeter@157: /// \tparam _Value The value type of the map. alpar@100: /// alpar@100: /// \see IterableValueMap deba@139: template deba@139: class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> { alpar@100: private: alpar@100: deba@139: typedef DefaultMap<_Graph, _Item, _Value> Map; deba@139: typedef _Graph Graph; alpar@100: alpar@100: typedef std::map<_Value, _Item> Container; deba@139: Container _inv_map; alpar@100: alpar@100: public: alpar@100: alpar@100: /// The key type of InvertableMap (Node, Arc, Edge). alpar@100: typedef typename Map::Key Key; alpar@100: /// The value type of the InvertableMap. alpar@100: typedef typename Map::Value Value; alpar@100: alpar@100: alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// deba@139: /// Construct a new InvertableMap for the graph. alpar@100: /// deba@139: explicit InvertableMap(const Graph& graph) : Map(graph) {} alpar@100: alpar@100: /// \brief Forward iterator for values. alpar@100: /// alpar@100: /// This iterator is an stl compatible forward alpar@100: /// iterator on the values of the map. The values can alpar@100: /// be accessed in the [beginValue, endValue) range. alpar@100: /// alpar@100: class ValueIterator alpar@100: : public std::iterator { alpar@100: friend class InvertableMap; alpar@100: private: alpar@100: ValueIterator(typename Container::const_iterator _it) alpar@100: : it(_it) {} alpar@100: public: alpar@100: alpar@100: ValueIterator() {} alpar@100: alpar@100: ValueIterator& operator++() { ++it; return *this; } alpar@100: ValueIterator operator++(int) { alpar@100: ValueIterator tmp(*this); alpar@100: operator++(); alpar@100: return tmp; alpar@100: } alpar@100: alpar@100: const Value& operator*() const { return it->first; } alpar@100: const Value* operator->() const { return &(it->first); } alpar@100: alpar@100: bool operator==(ValueIterator jt) const { return it == jt.it; } alpar@100: bool operator!=(ValueIterator jt) const { return it != jt.it; } alpar@100: alpar@100: private: alpar@100: typename Container::const_iterator it; alpar@100: }; alpar@100: alpar@100: /// \brief Returns an iterator to the first value. alpar@100: /// alpar@100: /// Returns an stl compatible iterator to the alpar@100: /// first value of the map. The values of the alpar@100: /// map can be accessed in the [beginValue, endValue) alpar@100: /// range. alpar@100: ValueIterator beginValue() const { deba@139: return ValueIterator(_inv_map.begin()); alpar@100: } alpar@100: alpar@100: /// \brief Returns an iterator after the last value. alpar@100: /// alpar@100: /// Returns an stl compatible iterator after the alpar@100: /// last value of the map. The values of the alpar@100: /// map can be accessed in the [beginValue, endValue) alpar@100: /// range. alpar@100: ValueIterator endValue() const { deba@139: return ValueIterator(_inv_map.end()); alpar@100: } alpar@100: alpar@100: /// \brief The setter function of the map. alpar@100: /// alpar@100: /// Sets the mapped value. alpar@100: void set(const Key& key, const Value& val) { alpar@100: Value oldval = Map::operator[](key); deba@139: typename Container::iterator it = _inv_map.find(oldval); deba@139: if (it != _inv_map.end() && it->second == key) { deba@139: _inv_map.erase(it); alpar@100: } deba@139: _inv_map.insert(make_pair(val, key)); alpar@100: Map::set(key, val); alpar@100: } alpar@100: alpar@100: /// \brief The getter function of the map. alpar@100: /// alpar@100: /// It gives back the value associated with the key. alpar@100: typename MapTraits::ConstReturnValue alpar@100: operator[](const Key& key) const { alpar@100: return Map::operator[](key); alpar@100: } alpar@100: alpar@100: /// \brief Gives back the item by its value. alpar@100: /// alpar@100: /// Gives back the item by its value. alpar@100: Key operator()(const Value& key) const { deba@139: typename Container::const_iterator it = _inv_map.find(key); deba@139: return it != _inv_map.end() ? it->second : INVALID; alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: /// \brief Erase the key from the map. alpar@100: /// alpar@100: /// Erase the key to the map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void erase(const Key& key) { alpar@100: Value val = Map::operator[](key); deba@139: typename Container::iterator it = _inv_map.find(val); deba@139: if (it != _inv_map.end() && it->second == key) { deba@139: _inv_map.erase(it); alpar@100: } alpar@100: Map::erase(key); alpar@100: } alpar@100: alpar@100: /// \brief Erase more keys from the map. alpar@100: /// alpar@100: /// Erase more keys from the map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void erase(const std::vector& keys) { alpar@100: for (int i = 0; i < int(keys.size()); ++i) { alpar@100: Value val = Map::operator[](keys[i]); deba@139: typename Container::iterator it = _inv_map.find(val); deba@139: if (it != _inv_map.end() && it->second == keys[i]) { deba@139: _inv_map.erase(it); alpar@100: } alpar@100: } alpar@100: Map::erase(keys); alpar@100: } alpar@100: alpar@100: /// \brief Clear the keys from the map and inverse map. alpar@100: /// alpar@100: /// Clear the keys from the map and inverse map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void clear() { deba@139: _inv_map.clear(); alpar@100: Map::clear(); alpar@100: } alpar@100: alpar@100: public: alpar@100: alpar@100: /// \brief The inverse map type. alpar@100: /// alpar@100: /// The inverse of this map. The subscript operator of the map alpar@100: /// gives back always the item what was last assigned to the value. alpar@100: class InverseMap { alpar@100: public: alpar@100: /// \brief Constructor of the InverseMap. alpar@100: /// alpar@100: /// Constructor of the InverseMap. deba@139: explicit InverseMap(const InvertableMap& inverted) deba@139: : _inverted(inverted) {} alpar@100: alpar@100: /// The value type of the InverseMap. alpar@100: typedef typename InvertableMap::Key Value; alpar@100: /// The key type of the InverseMap. alpar@100: typedef typename InvertableMap::Value Key; alpar@100: alpar@100: /// \brief Subscript operator. alpar@100: /// alpar@100: /// Subscript operator. It gives back always the item alpar@100: /// what was last assigned to the value. alpar@100: Value operator[](const Key& key) const { deba@139: return _inverted(key); alpar@100: } alpar@100: alpar@100: private: deba@139: const InvertableMap& _inverted; alpar@100: }; alpar@100: alpar@100: /// \brief It gives back the just readable inverse map. alpar@100: /// alpar@100: /// It gives back the just readable inverse map. alpar@100: InverseMap inverse() const { alpar@100: return InverseMap(*this); alpar@100: } alpar@100: alpar@100: alpar@100: alpar@100: }; alpar@100: alpar@100: /// \brief Provides a mutable, continuous and unique descriptor for each deba@139: /// item in the graph. alpar@100: /// alpar@100: /// The DescriptorMap class provides a unique and continuous (but mutable) alpar@100: /// descriptor (id) for each item of the same type (e.g. node) in the deba@139: /// graph. This id is
  • \b unique: different items (nodes) get alpar@100: /// different ids
  • \b continuous: the range of the ids is the set of alpar@100: /// integers between 0 and \c n-1, where \c n is the number of the items of alpar@100: /// this type (e.g. nodes) (so the id of a node can change if you delete an alpar@100: /// other node, i.e. this id is mutable).
This map can be inverted deba@139: /// with its member class \c InverseMap, or with the \c operator() member. alpar@100: /// kpeter@157: /// \tparam _Graph The graph class the \c DescriptorMap belongs to. kpeter@157: /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or alpar@100: /// Edge. deba@139: template deba@139: class DescriptorMap : protected DefaultMap<_Graph, _Item, int> { alpar@100: alpar@100: typedef _Item Item; deba@139: typedef DefaultMap<_Graph, _Item, int> Map; alpar@100: alpar@100: public: deba@139: /// The graph class of DescriptorMap. deba@139: typedef _Graph Graph; alpar@100: alpar@100: /// The key type of DescriptorMap (Node, Arc, Edge). alpar@100: typedef typename Map::Key Key; alpar@100: /// The value type of DescriptorMap. alpar@100: typedef typename Map::Value Value; alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor for descriptor map. deba@139: explicit DescriptorMap(const Graph& _graph) : Map(_graph) { alpar@100: Item it; alpar@100: const typename Map::Notifier* nf = Map::notifier(); alpar@100: for (nf->first(it); it != INVALID; nf->next(it)) { deba@139: Map::set(it, _inv_map.size()); deba@139: _inv_map.push_back(it); alpar@100: } alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: /// \brief Add a new key to the map. alpar@100: /// alpar@100: /// Add a new key to the map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void add(const Item& item) { alpar@100: Map::add(item); deba@139: Map::set(item, _inv_map.size()); deba@139: _inv_map.push_back(item); alpar@100: } alpar@100: alpar@100: /// \brief Add more new keys to the map. alpar@100: /// alpar@100: /// Add more new keys to the map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void add(const std::vector& items) { alpar@100: Map::add(items); alpar@100: for (int i = 0; i < int(items.size()); ++i) { deba@139: Map::set(items[i], _inv_map.size()); deba@139: _inv_map.push_back(items[i]); alpar@100: } alpar@100: } alpar@100: alpar@100: /// \brief Erase the key from the map. alpar@100: /// alpar@100: /// Erase the key from the map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void erase(const Item& item) { deba@139: Map::set(_inv_map.back(), Map::operator[](item)); deba@139: _inv_map[Map::operator[](item)] = _inv_map.back(); deba@139: _inv_map.pop_back(); alpar@100: Map::erase(item); alpar@100: } alpar@100: alpar@100: /// \brief Erase more keys from the map. alpar@100: /// alpar@100: /// Erase more keys from the map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void erase(const std::vector& items) { alpar@100: for (int i = 0; i < int(items.size()); ++i) { deba@139: Map::set(_inv_map.back(), Map::operator[](items[i])); deba@139: _inv_map[Map::operator[](items[i])] = _inv_map.back(); deba@139: _inv_map.pop_back(); alpar@100: } alpar@100: Map::erase(items); alpar@100: } alpar@100: alpar@100: /// \brief Build the unique map. alpar@100: /// alpar@100: /// Build the unique map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void build() { alpar@100: Map::build(); alpar@100: Item it; alpar@100: const typename Map::Notifier* nf = Map::notifier(); alpar@100: for (nf->first(it); it != INVALID; nf->next(it)) { deba@139: Map::set(it, _inv_map.size()); deba@139: _inv_map.push_back(it); alpar@100: } alpar@100: } alpar@100: alpar@100: /// \brief Clear the keys from the map. alpar@100: /// alpar@100: /// Clear the keys from the map. It is called by the alpar@100: /// \c AlterationNotifier. alpar@100: virtual void clear() { deba@139: _inv_map.clear(); alpar@100: Map::clear(); alpar@100: } alpar@100: alpar@100: public: alpar@100: alpar@100: /// \brief Returns the maximal value plus one. alpar@100: /// alpar@100: /// Returns the maximal value plus one in the map. alpar@100: unsigned int size() const { deba@139: return _inv_map.size(); alpar@100: } alpar@100: alpar@100: /// \brief Swaps the position of the two items in the map. alpar@100: /// alpar@100: /// Swaps the position of the two items in the map. alpar@100: void swap(const Item& p, const Item& q) { alpar@100: int pi = Map::operator[](p); alpar@100: int qi = Map::operator[](q); alpar@100: Map::set(p, qi); deba@139: _inv_map[qi] = p; alpar@100: Map::set(q, pi); deba@139: _inv_map[pi] = q; alpar@100: } alpar@100: alpar@100: /// \brief Gives back the \e descriptor of the item. alpar@100: /// alpar@100: /// Gives back the mutable and unique \e descriptor of the map. alpar@100: int operator[](const Item& item) const { alpar@100: return Map::operator[](item); alpar@100: } alpar@100: alpar@100: /// \brief Gives back the item by its descriptor. alpar@100: /// alpar@100: /// Gives back th item by its descriptor. alpar@100: Item operator()(int id) const { deba@139: return _inv_map[id]; alpar@100: } alpar@100: alpar@100: private: alpar@100: alpar@100: typedef std::vector Container; deba@139: Container _inv_map; alpar@100: alpar@100: public: alpar@100: /// \brief The inverse map type of DescriptorMap. alpar@100: /// alpar@100: /// The inverse map type of DescriptorMap. alpar@100: class InverseMap { alpar@100: public: alpar@100: /// \brief Constructor of the InverseMap. alpar@100: /// alpar@100: /// Constructor of the InverseMap. deba@139: explicit InverseMap(const DescriptorMap& inverted) deba@139: : _inverted(inverted) {} alpar@100: alpar@100: alpar@100: /// The value type of the InverseMap. alpar@100: typedef typename DescriptorMap::Key Value; alpar@100: /// The key type of the InverseMap. alpar@100: typedef typename DescriptorMap::Value Key; alpar@100: alpar@100: /// \brief Subscript operator. alpar@100: /// alpar@100: /// Subscript operator. It gives back the item alpar@100: /// that the descriptor belongs to currently. alpar@100: Value operator[](const Key& key) const { deba@139: return _inverted(key); alpar@100: } alpar@100: alpar@100: /// \brief Size of the map. alpar@100: /// alpar@100: /// Returns the size of the map. alpar@100: unsigned int size() const { deba@139: return _inverted.size(); alpar@100: } alpar@100: alpar@100: private: deba@139: const DescriptorMap& _inverted; alpar@100: }; alpar@100: alpar@100: /// \brief Gives back the inverse of the map. alpar@100: /// alpar@100: /// Gives back the inverse of the map. alpar@100: const InverseMap inverse() const { alpar@100: return InverseMap(*this); alpar@100: } alpar@100: }; alpar@100: alpar@100: /// \brief Returns the source of the given arc. alpar@100: /// alpar@100: /// The SourceMap gives back the source Node of the given arc. alpar@100: /// \see TargetMap alpar@100: template alpar@100: class SourceMap { alpar@100: public: alpar@100: alpar@100: typedef typename Digraph::Node Value; alpar@100: typedef typename Digraph::Arc Key; alpar@100: alpar@100: /// \brief Constructor alpar@100: /// alpar@100: /// Constructor alpar@100: /// \param _digraph The digraph that the map belongs to. deba@139: explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} alpar@100: alpar@100: /// \brief The subscript operator. alpar@100: /// alpar@100: /// The subscript operator. alpar@100: /// \param arc The arc alpar@100: /// \return The source of the arc alpar@100: Value operator[](const Key& arc) const { deba@139: return _digraph.source(arc); alpar@100: } alpar@100: alpar@100: private: deba@139: const Digraph& _digraph; alpar@100: }; alpar@100: alpar@100: /// \brief Returns a \ref SourceMap class. alpar@100: /// alpar@100: /// This function just returns an \ref SourceMap class. alpar@100: /// \relates SourceMap alpar@100: template alpar@100: inline SourceMap sourceMap(const Digraph& digraph) { alpar@100: return SourceMap(digraph); alpar@100: } alpar@100: alpar@100: /// \brief Returns the target of the given arc. alpar@100: /// alpar@100: /// The TargetMap gives back the target Node of the given arc. alpar@100: /// \see SourceMap alpar@100: template alpar@100: class TargetMap { alpar@100: public: alpar@100: alpar@100: typedef typename Digraph::Node Value; alpar@100: typedef typename Digraph::Arc Key; alpar@100: alpar@100: /// \brief Constructor alpar@100: /// alpar@100: /// Constructor alpar@100: /// \param _digraph The digraph that the map belongs to. deba@139: explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} alpar@100: alpar@100: /// \brief The subscript operator. alpar@100: /// alpar@100: /// The subscript operator. alpar@100: /// \param e The arc alpar@100: /// \return The target of the arc alpar@100: Value operator[](const Key& e) const { deba@139: return _digraph.target(e); alpar@100: } alpar@100: alpar@100: private: deba@139: const Digraph& _digraph; alpar@100: }; alpar@100: alpar@100: /// \brief Returns a \ref TargetMap class. alpar@100: /// alpar@100: /// This function just returns a \ref TargetMap class. alpar@100: /// \relates TargetMap alpar@100: template alpar@100: inline TargetMap targetMap(const Digraph& digraph) { alpar@100: return TargetMap(digraph); alpar@100: } alpar@100: alpar@100: /// \brief Returns the "forward" directed arc view of an edge. alpar@100: /// alpar@100: /// Returns the "forward" directed arc view of an edge. alpar@100: /// \see BackwardMap deba@139: template alpar@100: class ForwardMap { alpar@100: public: alpar@100: deba@139: typedef typename Graph::Arc Value; deba@139: typedef typename Graph::Edge Key; alpar@100: alpar@100: /// \brief Constructor alpar@100: /// alpar@100: /// Constructor deba@139: /// \param _graph The graph that the map belongs to. deba@139: explicit ForwardMap(const Graph& graph) : _graph(graph) {} alpar@100: alpar@100: /// \brief The subscript operator. alpar@100: /// alpar@100: /// The subscript operator. alpar@100: /// \param key An edge alpar@100: /// \return The "forward" directed arc view of edge alpar@100: Value operator[](const Key& key) const { deba@139: return _graph.direct(key, true); alpar@100: } alpar@100: alpar@100: private: deba@139: const Graph& _graph; alpar@100: }; alpar@100: alpar@100: /// \brief Returns a \ref ForwardMap class. alpar@100: /// alpar@100: /// This function just returns an \ref ForwardMap class. alpar@100: /// \relates ForwardMap deba@139: template deba@139: inline ForwardMap forwardMap(const Graph& graph) { deba@139: return ForwardMap(graph); alpar@100: } alpar@100: alpar@100: /// \brief Returns the "backward" directed arc view of an edge. alpar@100: /// alpar@100: /// Returns the "backward" directed arc view of an edge. alpar@100: /// \see ForwardMap deba@139: template alpar@100: class BackwardMap { alpar@100: public: alpar@100: deba@139: typedef typename Graph::Arc Value; deba@139: typedef typename Graph::Edge Key; alpar@100: alpar@100: /// \brief Constructor alpar@100: /// alpar@100: /// Constructor deba@139: /// \param _graph The graph that the map belongs to. deba@139: explicit BackwardMap(const Graph& graph) : _graph(graph) {} alpar@100: alpar@100: /// \brief The subscript operator. alpar@100: /// alpar@100: /// The subscript operator. alpar@100: /// \param key An edge alpar@100: /// \return The "backward" directed arc view of edge alpar@100: Value operator[](const Key& key) const { deba@139: return _graph.direct(key, false); alpar@100: } alpar@100: alpar@100: private: deba@139: const Graph& _graph; alpar@100: }; alpar@100: alpar@100: /// \brief Returns a \ref BackwardMap class alpar@100: alpar@100: /// This function just returns a \ref BackwardMap class. alpar@100: /// \relates BackwardMap deba@139: template deba@139: inline BackwardMap backwardMap(const Graph& graph) { deba@139: return BackwardMap(graph); alpar@100: } alpar@100: alpar@100: /// \brief Potential difference map alpar@100: /// alpar@100: /// If there is an potential map on the nodes then we alpar@100: /// can get an arc map as we get the substraction of the alpar@100: /// values of the target and source. alpar@100: template alpar@100: class PotentialDifferenceMap { alpar@100: public: alpar@100: typedef typename Digraph::Arc Key; alpar@100: typedef typename NodeMap::Value Value; alpar@100: alpar@100: /// \brief Constructor alpar@100: /// alpar@100: /// Contructor of the map deba@139: explicit PotentialDifferenceMap(const Digraph& digraph, deba@139: const NodeMap& potential) deba@139: : _digraph(digraph), _potential(potential) {} alpar@100: alpar@100: /// \brief Const subscription operator alpar@100: /// alpar@100: /// Const subscription operator alpar@100: Value operator[](const Key& arc) const { deba@139: return _potential[_digraph.target(arc)] - deba@139: _potential[_digraph.source(arc)]; alpar@100: } alpar@100: alpar@100: private: deba@139: const Digraph& _digraph; deba@139: const NodeMap& _potential; alpar@100: }; alpar@100: alpar@100: /// \brief Returns a PotentialDifferenceMap. alpar@100: /// alpar@100: /// This function just returns a PotentialDifferenceMap. alpar@100: /// \relates PotentialDifferenceMap alpar@100: template alpar@100: PotentialDifferenceMap alpar@100: potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) { alpar@100: return PotentialDifferenceMap(digraph, potential); alpar@100: } alpar@100: alpar@100: /// \brief Map of the node in-degrees. alpar@100: /// alpar@100: /// This map returns the in-degree of a node. Once it is constructed, alpar@100: /// the degrees are stored in a standard NodeMap, so each query is done alpar@100: /// in constant time. On the other hand, the values are updated automatically alpar@100: /// whenever the digraph changes. alpar@100: /// alpar@100: /// \warning Besides addNode() and addArc(), a digraph structure may provide alpar@100: /// alternative ways to modify the digraph. The correct behavior of InDegMap alpar@100: /// is not guarantied if these additional features are used. For example alpar@100: /// the functions \ref ListDigraph::changeSource() "changeSource()", alpar@100: /// \ref ListDigraph::changeTarget() "changeTarget()" and alpar@100: /// \ref ListDigraph::reverseArc() "reverseArc()" alpar@100: /// of \ref ListDigraph will \e not update the degree values correctly. alpar@100: /// alpar@100: /// \sa OutDegMap alpar@100: alpar@100: template alpar@100: class InDegMap alpar@100: : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> alpar@100: ::ItemNotifier::ObserverBase { alpar@100: alpar@100: public: alpar@100: alpar@100: typedef _Digraph Digraph; alpar@100: typedef int Value; alpar@100: typedef typename Digraph::Node Key; alpar@100: deba@139: typedef typename ItemSetTraits alpar@100: ::ItemNotifier::ObserverBase Parent; alpar@100: alpar@100: private: alpar@100: deba@139: class AutoNodeMap : public DefaultMap { alpar@100: public: alpar@100: deba@139: typedef DefaultMap Parent; alpar@100: alpar@100: AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} alpar@100: alpar@100: virtual void add(const Key& key) { alpar@100: Parent::add(key); alpar@100: Parent::set(key, 0); alpar@100: } alpar@100: alpar@100: virtual void add(const std::vector& keys) { alpar@100: Parent::add(keys); alpar@100: for (int i = 0; i < int(keys.size()); ++i) { alpar@100: Parent::set(keys[i], 0); alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void build() { alpar@100: Parent::build(); alpar@100: Key it; alpar@100: typename Parent::Notifier* nf = Parent::notifier(); alpar@100: for (nf->first(it); it != INVALID; nf->next(it)) { alpar@100: Parent::set(it, 0); alpar@100: } alpar@100: } alpar@100: }; alpar@100: alpar@100: public: alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor for creating in-degree map. deba@139: explicit InDegMap(const Digraph& digraph) deba@139: : _digraph(digraph), _deg(digraph) { deba@139: Parent::attach(_digraph.notifier(typename Digraph::Arc())); alpar@100: deba@139: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@139: _deg[it] = countInArcs(_digraph, it); alpar@100: } alpar@100: } alpar@100: alpar@100: /// Gives back the in-degree of a Node. alpar@100: int operator[](const Key& key) const { deba@139: return _deg[key]; alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: typedef typename Digraph::Arc Arc; alpar@100: alpar@100: virtual void add(const Arc& arc) { deba@139: ++_deg[_digraph.target(arc)]; alpar@100: } alpar@100: alpar@100: virtual void add(const std::vector& arcs) { alpar@100: for (int i = 0; i < int(arcs.size()); ++i) { deba@139: ++_deg[_digraph.target(arcs[i])]; alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void erase(const Arc& arc) { deba@139: --_deg[_digraph.target(arc)]; alpar@100: } alpar@100: alpar@100: virtual void erase(const std::vector& arcs) { alpar@100: for (int i = 0; i < int(arcs.size()); ++i) { deba@139: --_deg[_digraph.target(arcs[i])]; alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void build() { deba@139: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@139: _deg[it] = countInArcs(_digraph, it); alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void clear() { deba@139: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@139: _deg[it] = 0; alpar@100: } alpar@100: } alpar@100: private: alpar@100: deba@139: const Digraph& _digraph; deba@139: AutoNodeMap _deg; alpar@100: }; alpar@100: alpar@100: /// \brief Map of the node out-degrees. alpar@100: /// alpar@100: /// This map returns the out-degree of a node. Once it is constructed, alpar@100: /// the degrees are stored in a standard NodeMap, so each query is done alpar@100: /// in constant time. On the other hand, the values are updated automatically alpar@100: /// whenever the digraph changes. alpar@100: /// alpar@100: /// \warning Besides addNode() and addArc(), a digraph structure may provide alpar@100: /// alternative ways to modify the digraph. The correct behavior of OutDegMap alpar@100: /// is not guarantied if these additional features are used. For example alpar@100: /// the functions \ref ListDigraph::changeSource() "changeSource()", alpar@100: /// \ref ListDigraph::changeTarget() "changeTarget()" and alpar@100: /// \ref ListDigraph::reverseArc() "reverseArc()" alpar@100: /// of \ref ListDigraph will \e not update the degree values correctly. alpar@100: /// alpar@100: /// \sa InDegMap alpar@100: alpar@100: template alpar@100: class OutDegMap alpar@100: : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> alpar@100: ::ItemNotifier::ObserverBase { alpar@100: alpar@100: public: alpar@100: alpar@100: typedef _Digraph Digraph; alpar@100: typedef int Value; alpar@100: typedef typename Digraph::Node Key; alpar@100: deba@139: typedef typename ItemSetTraits deba@139: ::ItemNotifier::ObserverBase Parent; deba@139: alpar@100: private: alpar@100: deba@139: class AutoNodeMap : public DefaultMap { alpar@100: public: alpar@100: deba@139: typedef DefaultMap Parent; alpar@100: alpar@100: AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} alpar@100: alpar@100: virtual void add(const Key& key) { alpar@100: Parent::add(key); alpar@100: Parent::set(key, 0); alpar@100: } alpar@100: virtual void add(const std::vector& keys) { alpar@100: Parent::add(keys); alpar@100: for (int i = 0; i < int(keys.size()); ++i) { alpar@100: Parent::set(keys[i], 0); alpar@100: } alpar@100: } alpar@100: virtual void build() { alpar@100: Parent::build(); alpar@100: Key it; alpar@100: typename Parent::Notifier* nf = Parent::notifier(); alpar@100: for (nf->first(it); it != INVALID; nf->next(it)) { alpar@100: Parent::set(it, 0); alpar@100: } alpar@100: } alpar@100: }; alpar@100: alpar@100: public: alpar@100: alpar@100: /// \brief Constructor. alpar@100: /// alpar@100: /// Constructor for creating out-degree map. deba@139: explicit OutDegMap(const Digraph& digraph) deba@139: : _digraph(digraph), _deg(digraph) { deba@139: Parent::attach(_digraph.notifier(typename Digraph::Arc())); alpar@100: deba@139: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@139: _deg[it] = countOutArcs(_digraph, it); alpar@100: } alpar@100: } alpar@100: alpar@100: /// Gives back the out-degree of a Node. alpar@100: int operator[](const Key& key) const { deba@139: return _deg[key]; alpar@100: } alpar@100: alpar@100: protected: alpar@100: alpar@100: typedef typename Digraph::Arc Arc; alpar@100: alpar@100: virtual void add(const Arc& arc) { deba@139: ++_deg[_digraph.source(arc)]; alpar@100: } alpar@100: alpar@100: virtual void add(const std::vector& arcs) { alpar@100: for (int i = 0; i < int(arcs.size()); ++i) { deba@139: ++_deg[_digraph.source(arcs[i])]; alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void erase(const Arc& arc) { deba@139: --_deg[_digraph.source(arc)]; alpar@100: } alpar@100: alpar@100: virtual void erase(const std::vector& arcs) { alpar@100: for (int i = 0; i < int(arcs.size()); ++i) { deba@139: --_deg[_digraph.source(arcs[i])]; alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void build() { deba@139: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@139: _deg[it] = countOutArcs(_digraph, it); alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void clear() { deba@139: for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { deba@139: _deg[it] = 0; alpar@100: } alpar@100: } alpar@100: private: alpar@100: deba@139: const Digraph& _digraph; deba@139: AutoNodeMap _deg; alpar@100: }; alpar@100: alpar@100: alpar@100: ///Dynamic arc look up between given endpoints. alpar@100: alpar@100: ///\ingroup gutils alpar@100: ///Using this class, you can find an arc in a digraph from a given alpar@100: ///source to a given target in amortized time O(log d), alpar@100: ///where d is the out-degree of the source node. alpar@100: /// alpar@100: ///It is possible to find \e all parallel arcs between two nodes with alpar@100: ///the \c findFirst() and \c findNext() members. alpar@100: /// alpar@100: ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your deba@139: ///digraph is not changed so frequently. alpar@100: /// alpar@100: ///This class uses a self-adjusting binary search tree, Sleator's alpar@100: ///and Tarjan's Splay tree for guarantee the logarithmic amortized alpar@100: ///time bound for arc lookups. This class also guarantees the alpar@100: ///optimal time bound in a constant factor for any distribution of alpar@100: ///queries. alpar@100: /// kpeter@157: ///\tparam G The type of the underlying digraph. alpar@100: /// alpar@100: ///\sa ArcLookUp alpar@100: ///\sa AllArcLookUp alpar@100: template alpar@100: class DynArcLookUp alpar@100: : protected ItemSetTraits::ItemNotifier::ObserverBase alpar@100: { alpar@100: public: alpar@100: typedef typename ItemSetTraits alpar@100: ::ItemNotifier::ObserverBase Parent; alpar@100: deba@148: TEMPLATE_DIGRAPH_TYPEDEFS(G); alpar@100: typedef G Digraph; alpar@100: alpar@100: protected: alpar@100: alpar@100: class AutoNodeMap : public DefaultMap { alpar@100: public: alpar@100: alpar@100: typedef DefaultMap Parent; alpar@100: alpar@100: AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {} alpar@100: alpar@100: virtual void add(const Node& node) { alpar@100: Parent::add(node); alpar@100: Parent::set(node, INVALID); alpar@100: } alpar@100: alpar@100: virtual void add(const std::vector& nodes) { alpar@100: Parent::add(nodes); alpar@100: for (int i = 0; i < int(nodes.size()); ++i) { alpar@100: Parent::set(nodes[i], INVALID); alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void build() { alpar@100: Parent::build(); alpar@100: Node it; alpar@100: typename Parent::Notifier* nf = Parent::notifier(); alpar@100: for (nf->first(it); it != INVALID; nf->next(it)) { alpar@100: Parent::set(it, INVALID); alpar@100: } alpar@100: } alpar@100: }; alpar@100: alpar@100: const Digraph &_g; alpar@100: AutoNodeMap _head; alpar@100: typename Digraph::template ArcMap _parent; alpar@100: typename Digraph::template ArcMap _left; alpar@100: typename Digraph::template ArcMap _right; alpar@100: alpar@100: class ArcLess { alpar@100: const Digraph &g; alpar@100: public: alpar@100: ArcLess(const Digraph &_g) : g(_g) {} alpar@100: bool operator()(Arc a,Arc b) const alpar@100: { alpar@100: return g.target(a)& arcs) { alpar@100: for (int i = 0; i < int(arcs.size()); ++i) { alpar@100: insert(arcs[i]); alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void erase(const Arc& arc) { alpar@100: remove(arc); alpar@100: } alpar@100: alpar@100: virtual void erase(const std::vector& arcs) { alpar@100: for (int i = 0; i < int(arcs.size()); ++i) { alpar@100: remove(arcs[i]); alpar@100: } alpar@100: } alpar@100: alpar@100: virtual void build() { alpar@100: refresh(); alpar@100: } alpar@100: alpar@100: virtual void clear() { alpar@100: for(NodeIt n(_g);n!=INVALID;++n) { alpar@100: _head.set(n, INVALID); alpar@100: } alpar@100: } alpar@100: alpar@100: void insert(Arc arc) { alpar@100: Node s = _g.source(arc); alpar@100: Node t = _g.target(arc); alpar@100: _left.set(arc, INVALID); alpar@100: _right.set(arc, INVALID); alpar@100: alpar@100: Arc e = _head[s]; alpar@100: if (e == INVALID) { alpar@100: _head.set(s, arc); alpar@100: _parent.set(arc, INVALID); alpar@100: return; alpar@100: } alpar@100: while (true) { alpar@100: if (t < _g.target(e)) { alpar@100: if (_left[e] == INVALID) { alpar@100: _left.set(e, arc); alpar@100: _parent.set(arc, e); alpar@100: splay(arc); alpar@100: return; alpar@100: } else { alpar@100: e = _left[e]; alpar@100: } alpar@100: } else { alpar@100: if (_right[e] == INVALID) { alpar@100: _right.set(e, arc); alpar@100: _parent.set(arc, e); alpar@100: splay(arc); alpar@100: return; alpar@100: } else { alpar@100: e = _right[e]; alpar@100: } alpar@100: } alpar@100: } alpar@100: } alpar@100: alpar@100: void remove(Arc arc) { alpar@100: if (_left[arc] == INVALID) { alpar@100: if (_right[arc] != INVALID) { alpar@100: _parent.set(_right[arc], _parent[arc]); alpar@100: } alpar@100: if (_parent[arc] != INVALID) { alpar@100: if (_left[_parent[arc]] == arc) { alpar@100: _left.set(_parent[arc], _right[arc]); alpar@100: } else { alpar@100: _right.set(_parent[arc], _right[arc]); alpar@100: } alpar@100: } else { alpar@100: _head.set(_g.source(arc), _right[arc]); alpar@100: } alpar@100: } else if (_right[arc] == INVALID) { alpar@100: _parent.set(_left[arc], _parent[arc]); alpar@100: if (_parent[arc] != INVALID) { alpar@100: if (_left[_parent[arc]] == arc) { alpar@100: _left.set(_parent[arc], _left[arc]); alpar@100: } else { alpar@100: _right.set(_parent[arc], _left[arc]); alpar@100: } alpar@100: } else { alpar@100: _head.set(_g.source(arc), _left[arc]); alpar@100: } alpar@100: } else { alpar@100: Arc e = _left[arc]; alpar@100: if (_right[e] != INVALID) { alpar@100: e = _right[e]; alpar@100: while (_right[e] != INVALID) { alpar@100: e = _right[e]; alpar@100: } alpar@100: Arc s = _parent[e]; alpar@100: _right.set(_parent[e], _left[e]); alpar@100: if (_left[e] != INVALID) { alpar@100: _parent.set(_left[e], _parent[e]); alpar@100: } alpar@100: alpar@100: _left.set(e, _left[arc]); alpar@100: _parent.set(_left[arc], e); alpar@100: _right.set(e, _right[arc]); alpar@100: _parent.set(_right[arc], e); alpar@100: alpar@100: _parent.set(e, _parent[arc]); alpar@100: if (_parent[arc] != INVALID) { alpar@100: if (_left[_parent[arc]] == arc) { alpar@100: _left.set(_parent[arc], e); alpar@100: } else { alpar@100: _right.set(_parent[arc], e); alpar@100: } alpar@100: } alpar@100: splay(s); alpar@100: } else { alpar@100: _right.set(e, _right[arc]); alpar@100: _parent.set(_right[arc], e); alpar@100: alpar@100: if (_parent[arc] != INVALID) { alpar@100: if (_left[_parent[arc]] == arc) { alpar@100: _left.set(_parent[arc], e); alpar@100: } else { alpar@100: _right.set(_parent[arc], e); alpar@100: } alpar@100: } else { alpar@100: _head.set(_g.source(arc), e); alpar@100: } alpar@100: } alpar@100: } alpar@100: } alpar@100: alpar@100: Arc refreshRec(std::vector &v,int a,int b) alpar@100: { alpar@100: int m=(a+b)/2; alpar@100: Arc me=v[m]; alpar@100: if (a < m) { alpar@100: Arc left = refreshRec(v,a,m-1); alpar@100: _left.set(me, left); alpar@100: _parent.set(left, me); alpar@100: } else { alpar@100: _left.set(me, INVALID); alpar@100: } alpar@100: if (m < b) { alpar@100: Arc right = refreshRec(v,m+1,b); alpar@100: _right.set(me, right); alpar@100: _parent.set(right, me); alpar@100: } else { alpar@100: _right.set(me, INVALID); alpar@100: } alpar@100: return me; alpar@100: } alpar@100: alpar@100: void refresh() { alpar@100: for(NodeIt n(_g);n!=INVALID;++n) { alpar@100: std::vector v; alpar@100: for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); alpar@100: if(v.size()) { alpar@100: std::sort(v.begin(),v.end(),ArcLess(_g)); alpar@100: Arc head = refreshRec(v,0,v.size()-1); alpar@100: _head.set(n, head); alpar@100: _parent.set(head, INVALID); alpar@100: } alpar@100: else _head.set(n, INVALID); alpar@100: } alpar@100: } alpar@100: alpar@100: void zig(Arc v) { alpar@100: Arc w = _parent[v]; alpar@100: _parent.set(v, _parent[w]); alpar@100: _parent.set(w, v); alpar@100: _left.set(w, _right[v]); alpar@100: _right.set(v, w); alpar@100: if (_parent[v] != INVALID) { alpar@100: if (_right[_parent[v]] == w) { alpar@100: _right.set(_parent[v], v); alpar@100: } else { alpar@100: _left.set(_parent[v], v); alpar@100: } alpar@100: } alpar@100: if (_left[w] != INVALID){ alpar@100: _parent.set(_left[w], w); alpar@100: } alpar@100: } alpar@100: alpar@100: void zag(Arc v) { alpar@100: Arc w = _parent[v]; alpar@100: _parent.set(v, _parent[w]); alpar@100: _parent.set(w, v); alpar@100: _right.set(w, _left[v]); alpar@100: _left.set(v, w); alpar@100: if (_parent[v] != INVALID){ alpar@100: if (_left[_parent[v]] == w) { alpar@100: _left.set(_parent[v], v); alpar@100: } else { alpar@100: _right.set(_parent[v], v); alpar@100: } alpar@100: } alpar@100: if (_right[w] != INVALID){ alpar@100: _parent.set(_right[w], w); alpar@100: } alpar@100: } alpar@100: alpar@100: void splay(Arc v) { alpar@100: while (_parent[v] != INVALID) { alpar@100: if (v == _left[_parent[v]]) { alpar@100: if (_parent[_parent[v]] == INVALID) { alpar@100: zig(v); alpar@100: } else { alpar@100: if (_parent[v] == _left[_parent[_parent[v]]]) { alpar@100: zig(_parent[v]); alpar@100: zig(v); alpar@100: } else { alpar@100: zig(v); alpar@100: zag(v); alpar@100: } alpar@100: } alpar@100: } else { alpar@100: if (_parent[_parent[v]] == INVALID) { alpar@100: zag(v); alpar@100: } else { alpar@100: if (_parent[v] == _left[_parent[_parent[v]]]) { alpar@100: zag(v); alpar@100: zig(v); alpar@100: } else { alpar@100: zag(_parent[v]); alpar@100: zag(v); alpar@100: } alpar@100: } alpar@100: } alpar@100: } alpar@100: _head[_g.source(v)] = v; alpar@100: } alpar@100: alpar@100: alpar@100: public: alpar@100: alpar@100: ///Find an arc between two nodes. alpar@100: alpar@100: ///Find an arc between two nodes in time O(logd), where alpar@100: /// d is the number of outgoing arcs of \c s. alpar@100: ///\param s The source node alpar@100: ///\param t The target node alpar@100: ///\return An arc from \c s to \c t if there exists, alpar@100: ///\ref INVALID otherwise. alpar@100: Arc operator()(Node s, Node t) const alpar@100: { deba@139: Arc a = _head[s]; alpar@100: while (true) { deba@139: if (_g.target(a) == t) { deba@139: const_cast(*this).splay(a); deba@139: return a; deba@139: } else if (t < _g.target(a)) { deba@139: if (_left[a] == INVALID) { deba@139: const_cast(*this).splay(a); alpar@100: return INVALID; alpar@100: } else { deba@139: a = _left[a]; alpar@100: } alpar@100: } else { deba@139: if (_right[a] == INVALID) { deba@139: const_cast(*this).splay(a); alpar@100: return INVALID; alpar@100: } else { deba@139: a = _right[a]; alpar@100: } alpar@100: } alpar@100: } alpar@100: } alpar@100: alpar@100: ///Find the first arc between two nodes. alpar@100: alpar@100: ///Find the first arc between two nodes in time alpar@100: /// O(logd), where d is the number of alpar@100: /// outgoing arcs of \c s. alpar@100: ///\param s The source node alpar@100: ///\param t The target node alpar@100: ///\return An arc from \c s to \c t if there exists, \ref INVALID alpar@100: /// otherwise. alpar@100: Arc findFirst(Node s, Node t) const alpar@100: { deba@139: Arc a = _head[s]; alpar@100: Arc r = INVALID; alpar@100: while (true) { deba@139: if (_g.target(a) < t) { deba@139: if (_right[a] == INVALID) { deba@139: const_cast(*this).splay(a); alpar@100: return r; alpar@100: } else { deba@139: a = _right[a]; alpar@100: } alpar@100: } else { deba@139: if (_g.target(a) == t) { deba@139: r = a; alpar@100: } deba@139: if (_left[a] == INVALID) { deba@139: const_cast(*this).splay(a); alpar@100: return r; alpar@100: } else { deba@139: a = _left[a]; alpar@100: } alpar@100: } alpar@100: } alpar@100: } alpar@100: alpar@100: ///Find the next arc between two nodes. alpar@100: alpar@100: ///Find the next arc between two nodes in time alpar@100: /// O(logd), where d is the number of alpar@100: /// outgoing arcs of \c s. alpar@100: ///\param s The source node alpar@100: ///\param t The target node alpar@100: ///\return An arc from \c s to \c t if there exists, \ref INVALID alpar@100: /// otherwise. alpar@100: alpar@100: ///\note If \c e is not the result of the previous \c findFirst() alpar@100: ///operation then the amorized time bound can not be guaranteed. alpar@100: #ifdef DOXYGEN deba@139: Arc findNext(Node s, Node t, Arc a) const alpar@100: #else deba@139: Arc findNext(Node, Node t, Arc a) const alpar@100: #endif alpar@100: { deba@139: if (_right[a] != INVALID) { deba@139: a = _right[a]; deba@139: while (_left[a] != INVALID) { deba@139: a = _left[a]; alpar@100: } deba@139: const_cast(*this).splay(a); alpar@100: } else { deba@139: while (_parent[a] != INVALID && _right[_parent[a]] == a) { deba@139: a = _parent[a]; alpar@100: } deba@139: if (_parent[a] == INVALID) { alpar@100: return INVALID; alpar@100: } else { deba@139: a = _parent[a]; deba@139: const_cast(*this).splay(a); alpar@100: } alpar@100: } deba@139: if (_g.target(a) == t) return a; alpar@100: else return INVALID; alpar@100: } alpar@100: alpar@100: }; alpar@100: alpar@100: ///Fast arc look up between given endpoints. alpar@100: alpar@100: ///\ingroup gutils alpar@100: ///Using this class, you can find an arc in a digraph from a given alpar@100: ///source to a given target in time O(log d), alpar@100: ///where d is the out-degree of the source node. alpar@100: /// alpar@100: ///It is not possible to find \e all parallel arcs between two nodes. alpar@100: ///Use \ref AllArcLookUp for this purpose. alpar@100: /// alpar@100: ///\warning This class is static, so you should refresh() (or at least alpar@100: ///refresh(Node)) this data structure alpar@100: ///whenever the digraph changes. This is a time consuming (superlinearly alpar@100: ///proportional (O(mlogm)) to the number of arcs). alpar@100: /// kpeter@157: ///\tparam G The type of the underlying digraph. alpar@100: /// alpar@100: ///\sa DynArcLookUp alpar@100: ///\sa AllArcLookUp alpar@100: template alpar@100: class ArcLookUp alpar@100: { alpar@100: public: deba@148: TEMPLATE_DIGRAPH_TYPEDEFS(G); alpar@100: typedef G Digraph; alpar@100: alpar@100: protected: alpar@100: const Digraph &_g; alpar@100: typename Digraph::template NodeMap _head; alpar@100: typename Digraph::template ArcMap _left; alpar@100: typename Digraph::template ArcMap _right; alpar@100: alpar@100: class ArcLess { alpar@100: const Digraph &g; alpar@100: public: alpar@100: ArcLess(const Digraph &_g) : g(_g) {} alpar@100: bool operator()(Arc a,Arc b) const alpar@100: { alpar@100: return g.target(a) &v,int a,int b) alpar@100: { alpar@100: int m=(a+b)/2; alpar@100: Arc me=v[m]; alpar@100: _left[me] = aO(dlogd), where d is alpar@100: ///the number of the outgoing arcs of \c n. alpar@100: void refresh(Node n) alpar@100: { alpar@100: std::vector v; alpar@100: for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); alpar@100: if(v.size()) { alpar@100: std::sort(v.begin(),v.end(),ArcLess(_g)); alpar@100: _head[n]=refreshRec(v,0,v.size()-1); alpar@100: } alpar@100: else _head[n]=INVALID; alpar@100: } alpar@100: ///Refresh the full data structure. alpar@100: alpar@100: ///Build up the full search database. In fact, it simply calls alpar@100: ///\ref refresh(Node) "refresh(n)" for each node \c n. alpar@100: /// alpar@100: ///It runs in time O(mlogD), where m is alpar@100: ///the number of the arcs of \c n and D is the maximum alpar@100: ///out-degree of the digraph. alpar@100: alpar@100: void refresh() alpar@100: { alpar@100: for(NodeIt n(_g);n!=INVALID;++n) refresh(n); alpar@100: } alpar@100: alpar@100: ///Find an arc between two nodes. alpar@100: alpar@100: ///Find an arc between two nodes in time O(logd), where alpar@100: /// d is the number of outgoing arcs of \c s. alpar@100: ///\param s The source node alpar@100: ///\param t The target node alpar@100: ///\return An arc from \c s to \c t if there exists, alpar@100: ///\ref INVALID otherwise. alpar@100: /// alpar@100: ///\warning If you change the digraph, refresh() must be called before using alpar@100: ///this operator. If you change the outgoing arcs of alpar@100: ///a single node \c n, then alpar@100: ///\ref refresh(Node) "refresh(n)" is enough. alpar@100: /// alpar@100: Arc operator()(Node s, Node t) const alpar@100: { alpar@100: Arc e; alpar@100: for(e=_head[s]; alpar@100: e!=INVALID&&_g.target(e)!=t; alpar@100: e = t < _g.target(e)?_left[e]:_right[e]) ; alpar@100: return e; alpar@100: } alpar@100: alpar@100: }; alpar@100: alpar@100: ///Fast look up of all arcs between given endpoints. alpar@100: alpar@100: ///\ingroup gutils alpar@100: ///This class is the same as \ref ArcLookUp, with the addition alpar@100: ///that it makes it possible to find all arcs between given endpoints. alpar@100: /// alpar@100: ///\warning This class is static, so you should refresh() (or at least alpar@100: ///refresh(Node)) this data structure alpar@100: ///whenever the digraph changes. This is a time consuming (superlinearly alpar@100: ///proportional (O(mlogm)) to the number of arcs). alpar@100: /// kpeter@157: ///\tparam G The type of the underlying digraph. alpar@100: /// alpar@100: ///\sa DynArcLookUp alpar@100: ///\sa ArcLookUp alpar@100: template alpar@100: class AllArcLookUp : public ArcLookUp alpar@100: { alpar@100: using ArcLookUp::_g; alpar@100: using ArcLookUp::_right; alpar@100: using ArcLookUp::_left; alpar@100: using ArcLookUp::_head; alpar@100: deba@148: TEMPLATE_DIGRAPH_TYPEDEFS(G); alpar@100: typedef G Digraph; alpar@100: alpar@100: typename Digraph::template ArcMap _next; alpar@100: alpar@100: Arc refreshNext(Arc head,Arc next=INVALID) alpar@100: { alpar@100: if(head==INVALID) return next; alpar@100: else { alpar@100: next=refreshNext(_right[head],next); alpar@100: // _next[head]=next; alpar@100: _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) alpar@100: ? next : INVALID; alpar@100: return refreshNext(_left[head],head); alpar@100: } alpar@100: } alpar@100: alpar@100: void refreshNext() alpar@100: { alpar@100: for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]); alpar@100: } alpar@100: alpar@100: public: alpar@100: ///Constructor alpar@100: alpar@100: ///Constructor. alpar@100: /// alpar@100: ///It builds up the search database, which remains valid until the digraph alpar@100: ///changes. alpar@100: AllArcLookUp(const Digraph &g) : ArcLookUp(g), _next(g) {refreshNext();} alpar@100: alpar@100: ///Refresh the data structure at a node. alpar@100: alpar@100: ///Build up the search database of node \c n. alpar@100: /// alpar@100: ///It runs in time O(dlogd), where d is alpar@100: ///the number of the outgoing arcs of \c n. alpar@100: alpar@100: void refresh(Node n) alpar@100: { alpar@100: ArcLookUp::refresh(n); alpar@100: refreshNext(_head[n]); alpar@100: } alpar@100: alpar@100: ///Refresh the full data structure. alpar@100: alpar@100: ///Build up the full search database. In fact, it simply calls alpar@100: ///\ref refresh(Node) "refresh(n)" for each node \c n. alpar@100: /// alpar@100: ///It runs in time O(mlogD), where m is alpar@100: ///the number of the arcs of \c n and D is the maximum alpar@100: ///out-degree of the digraph. alpar@100: alpar@100: void refresh() alpar@100: { alpar@100: for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]); alpar@100: } alpar@100: alpar@100: ///Find an arc between two nodes. alpar@100: alpar@100: ///Find an arc between two nodes. alpar@100: ///\param s The source node alpar@100: ///\param t The target node alpar@100: ///\param prev The previous arc between \c s and \c t. It it is INVALID or alpar@100: ///not given, the operator finds the first appropriate arc. alpar@100: ///\return An arc from \c s to \c t after \c prev or alpar@100: ///\ref INVALID if there is no more. alpar@100: /// alpar@100: ///For example, you can count the number of arcs from \c u to \c v in the alpar@100: ///following way. alpar@100: ///\code alpar@100: ///AllArcLookUp ae(g); alpar@100: ///... alpar@100: ///int n=0; alpar@100: ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; alpar@100: ///\endcode alpar@100: /// alpar@100: ///Finding the first arc take O(logd) time, where alpar@100: /// d is the number of outgoing arcs of \c s. Then, the alpar@100: ///consecutive arcs are found in constant time. alpar@100: /// alpar@100: ///\warning If you change the digraph, refresh() must be called before using alpar@100: ///this operator. If you change the outgoing arcs of alpar@100: ///a single node \c n, then alpar@100: ///\ref refresh(Node) "refresh(n)" is enough. alpar@100: /// alpar@100: #ifdef DOXYGEN alpar@100: Arc operator()(Node s, Node t, Arc prev=INVALID) const {} alpar@100: #else alpar@100: using ArcLookUp::operator() ; alpar@100: Arc operator()(Node s, Node t, Arc prev) const alpar@100: { alpar@100: return prev==INVALID?(*this)(s,t):_next[prev]; alpar@100: } alpar@100: #endif alpar@100: alpar@100: }; alpar@100: alpar@100: /// @} alpar@100: alpar@100: } //END OF NAMESPACE LEMON alpar@100: alpar@100: #endif