1.1 --- a/lemon/graph_utils.h Mon Jul 14 15:40:24 2008 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,2760 +0,0 @@
1.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library.
1.7 - *
1.8 - * Copyright (C) 2003-2008
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_GRAPH_UTILS_H
1.23 -#define LEMON_GRAPH_UTILS_H
1.24 -
1.25 -#include <iterator>
1.26 -#include <vector>
1.27 -#include <map>
1.28 -#include <cmath>
1.29 -#include <algorithm>
1.30 -
1.31 -#include <lemon/bits/invalid.h>
1.32 -#include <lemon/bits/utility.h>
1.33 -#include <lemon/maps.h>
1.34 -#include <lemon/bits/traits.h>
1.35 -
1.36 -#include <lemon/bits/alteration_notifier.h>
1.37 -#include <lemon/bits/default_map.h>
1.38 -
1.39 -///\ingroup gutils
1.40 -///\file
1.41 -///\brief Graph utilities.
1.42 -
1.43 -namespace lemon {
1.44 -
1.45 - /// \addtogroup gutils
1.46 - /// @{
1.47 -
1.48 - ///Creates convenience typedefs for the digraph types and iterators
1.49 -
1.50 - ///This \c \#define creates convenience typedefs for the following types
1.51 - ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
1.52 - ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
1.53 - ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
1.54 - ///
1.55 - ///\note If the graph type is a dependent type, ie. the graph type depend
1.56 - ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
1.57 - ///macro.
1.58 -#define DIGRAPH_TYPEDEFS(Digraph) \
1.59 - typedef Digraph::Node Node; \
1.60 - typedef Digraph::NodeIt NodeIt; \
1.61 - typedef Digraph::Arc Arc; \
1.62 - typedef Digraph::ArcIt ArcIt; \
1.63 - typedef Digraph::InArcIt InArcIt; \
1.64 - typedef Digraph::OutArcIt OutArcIt; \
1.65 - typedef Digraph::NodeMap<bool> BoolNodeMap; \
1.66 - typedef Digraph::NodeMap<int> IntNodeMap; \
1.67 - typedef Digraph::NodeMap<double> DoubleNodeMap; \
1.68 - typedef Digraph::ArcMap<bool> BoolArcMap; \
1.69 - typedef Digraph::ArcMap<int> IntArcMap; \
1.70 - typedef Digraph::ArcMap<double> DoubleArcMap
1.71 -
1.72 - ///Creates convenience typedefs for the digraph types and iterators
1.73 -
1.74 - ///\see DIGRAPH_TYPEDEFS
1.75 - ///
1.76 - ///\note Use this macro, if the graph type is a dependent type,
1.77 - ///ie. the graph type depend on a template parameter.
1.78 -#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
1.79 - typedef typename Digraph::Node Node; \
1.80 - typedef typename Digraph::NodeIt NodeIt; \
1.81 - typedef typename Digraph::Arc Arc; \
1.82 - typedef typename Digraph::ArcIt ArcIt; \
1.83 - typedef typename Digraph::InArcIt InArcIt; \
1.84 - typedef typename Digraph::OutArcIt OutArcIt; \
1.85 - typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
1.86 - typedef typename Digraph::template NodeMap<int> IntNodeMap; \
1.87 - typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
1.88 - typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
1.89 - typedef typename Digraph::template ArcMap<int> IntArcMap; \
1.90 - typedef typename Digraph::template ArcMap<double> DoubleArcMap
1.91 -
1.92 - ///Creates convenience typedefs for the graph types and iterators
1.93 -
1.94 - ///This \c \#define creates the same convenience typedefs as defined
1.95 - ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
1.96 - ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
1.97 - ///\c DoubleEdgeMap.
1.98 - ///
1.99 - ///\note If the graph type is a dependent type, ie. the graph type depend
1.100 - ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
1.101 - ///macro.
1.102 -#define GRAPH_TYPEDEFS(Graph) \
1.103 - DIGRAPH_TYPEDEFS(Graph); \
1.104 - typedef Graph::Edge Edge; \
1.105 - typedef Graph::EdgeIt EdgeIt; \
1.106 - typedef Graph::IncEdgeIt IncEdgeIt; \
1.107 - typedef Graph::EdgeMap<bool> BoolEdgeMap; \
1.108 - typedef Graph::EdgeMap<int> IntEdgeMap; \
1.109 - typedef Graph::EdgeMap<double> DoubleEdgeMap
1.110 -
1.111 - ///Creates convenience typedefs for the graph types and iterators
1.112 -
1.113 - ///\see GRAPH_TYPEDEFS
1.114 - ///
1.115 - ///\note Use this macro, if the graph type is a dependent type,
1.116 - ///ie. the graph type depend on a template parameter.
1.117 -#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
1.118 - TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
1.119 - typedef typename Graph::Edge Edge; \
1.120 - typedef typename Graph::EdgeIt EdgeIt; \
1.121 - typedef typename Graph::IncEdgeIt IncEdgeIt; \
1.122 - typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
1.123 - typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
1.124 - typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
1.125 -
1.126 - /// \brief Function to count the items in the graph.
1.127 - ///
1.128 - /// This function counts the items (nodes, arcs etc) in the graph.
1.129 - /// The complexity of the function is O(n) because
1.130 - /// it iterates on all of the items.
1.131 - template <typename Graph, typename Item>
1.132 - inline int countItems(const Graph& g) {
1.133 - typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.134 - int num = 0;
1.135 - for (ItemIt it(g); it != INVALID; ++it) {
1.136 - ++num;
1.137 - }
1.138 - return num;
1.139 - }
1.140 -
1.141 - // Node counting:
1.142 -
1.143 - namespace _graph_utils_bits {
1.144 -
1.145 - template <typename Graph, typename Enable = void>
1.146 - struct CountNodesSelector {
1.147 - static int count(const Graph &g) {
1.148 - return countItems<Graph, typename Graph::Node>(g);
1.149 - }
1.150 - };
1.151 -
1.152 - template <typename Graph>
1.153 - struct CountNodesSelector<
1.154 - Graph, typename
1.155 - enable_if<typename Graph::NodeNumTag, void>::type>
1.156 - {
1.157 - static int count(const Graph &g) {
1.158 - return g.nodeNum();
1.159 - }
1.160 - };
1.161 - }
1.162 -
1.163 - /// \brief Function to count the nodes in the graph.
1.164 - ///
1.165 - /// This function counts the nodes in the graph.
1.166 - /// The complexity of the function is O(n) but for some
1.167 - /// graph structures it is specialized to run in O(1).
1.168 - ///
1.169 - /// If the graph contains a \e nodeNum() member function and a
1.170 - /// \e NodeNumTag tag then this function calls directly the member
1.171 - /// function to query the cardinality of the node set.
1.172 - template <typename Graph>
1.173 - inline int countNodes(const Graph& g) {
1.174 - return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
1.175 - }
1.176 -
1.177 - // Arc counting:
1.178 -
1.179 - namespace _graph_utils_bits {
1.180 -
1.181 - template <typename Graph, typename Enable = void>
1.182 - struct CountArcsSelector {
1.183 - static int count(const Graph &g) {
1.184 - return countItems<Graph, typename Graph::Arc>(g);
1.185 - }
1.186 - };
1.187 -
1.188 - template <typename Graph>
1.189 - struct CountArcsSelector<
1.190 - Graph,
1.191 - typename enable_if<typename Graph::ArcNumTag, void>::type>
1.192 - {
1.193 - static int count(const Graph &g) {
1.194 - return g.arcNum();
1.195 - }
1.196 - };
1.197 - }
1.198 -
1.199 - /// \brief Function to count the arcs in the graph.
1.200 - ///
1.201 - /// This function counts the arcs in the graph.
1.202 - /// The complexity of the function is O(e) but for some
1.203 - /// graph structures it is specialized to run in O(1).
1.204 - ///
1.205 - /// If the graph contains a \e arcNum() member function and a
1.206 - /// \e EdgeNumTag tag then this function calls directly the member
1.207 - /// function to query the cardinality of the arc set.
1.208 - template <typename Graph>
1.209 - inline int countArcs(const Graph& g) {
1.210 - return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
1.211 - }
1.212 -
1.213 - // Edge counting:
1.214 - namespace _graph_utils_bits {
1.215 -
1.216 - template <typename Graph, typename Enable = void>
1.217 - struct CountEdgesSelector {
1.218 - static int count(const Graph &g) {
1.219 - return countItems<Graph, typename Graph::Edge>(g);
1.220 - }
1.221 - };
1.222 -
1.223 - template <typename Graph>
1.224 - struct CountEdgesSelector<
1.225 - Graph,
1.226 - typename enable_if<typename Graph::EdgeNumTag, void>::type>
1.227 - {
1.228 - static int count(const Graph &g) {
1.229 - return g.edgeNum();
1.230 - }
1.231 - };
1.232 - }
1.233 -
1.234 - /// \brief Function to count the edges in the graph.
1.235 - ///
1.236 - /// This function counts the edges in the graph.
1.237 - /// The complexity of the function is O(m) but for some
1.238 - /// graph structures it is specialized to run in O(1).
1.239 - ///
1.240 - /// If the graph contains a \e edgeNum() member function and a
1.241 - /// \e EdgeNumTag tag then this function calls directly the member
1.242 - /// function to query the cardinality of the edge set.
1.243 - template <typename Graph>
1.244 - inline int countEdges(const Graph& g) {
1.245 - return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
1.246 -
1.247 - }
1.248 -
1.249 -
1.250 - template <typename Graph, typename DegIt>
1.251 - inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
1.252 - int num = 0;
1.253 - for (DegIt it(_g, _n); it != INVALID; ++it) {
1.254 - ++num;
1.255 - }
1.256 - return num;
1.257 - }
1.258 -
1.259 - /// \brief Function to count the number of the out-arcs from node \c n.
1.260 - ///
1.261 - /// This function counts the number of the out-arcs from node \c n
1.262 - /// in the graph.
1.263 - template <typename Graph>
1.264 - inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
1.265 - return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
1.266 - }
1.267 -
1.268 - /// \brief Function to count the number of the in-arcs to node \c n.
1.269 - ///
1.270 - /// This function counts the number of the in-arcs to node \c n
1.271 - /// in the graph.
1.272 - template <typename Graph>
1.273 - inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
1.274 - return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
1.275 - }
1.276 -
1.277 - /// \brief Function to count the number of the inc-edges to node \c n.
1.278 - ///
1.279 - /// This function counts the number of the inc-edges to node \c n
1.280 - /// in the graph.
1.281 - template <typename Graph>
1.282 - inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
1.283 - return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
1.284 - }
1.285 -
1.286 - namespace _graph_utils_bits {
1.287 -
1.288 - template <typename Graph, typename Enable = void>
1.289 - struct FindArcSelector {
1.290 - typedef typename Graph::Node Node;
1.291 - typedef typename Graph::Arc Arc;
1.292 - static Arc find(const Graph &g, Node u, Node v, Arc e) {
1.293 - if (e == INVALID) {
1.294 - g.firstOut(e, u);
1.295 - } else {
1.296 - g.nextOut(e);
1.297 - }
1.298 - while (e != INVALID && g.target(e) != v) {
1.299 - g.nextOut(e);
1.300 - }
1.301 - return e;
1.302 - }
1.303 - };
1.304 -
1.305 - template <typename Graph>
1.306 - struct FindArcSelector<
1.307 - Graph,
1.308 - typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.309 - {
1.310 - typedef typename Graph::Node Node;
1.311 - typedef typename Graph::Arc Arc;
1.312 - static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1.313 - return g.findArc(u, v, prev);
1.314 - }
1.315 - };
1.316 - }
1.317 -
1.318 - /// \brief Finds an arc between two nodes of a graph.
1.319 - ///
1.320 - /// Finds an arc from node \c u to node \c v in graph \c g.
1.321 - ///
1.322 - /// If \c prev is \ref INVALID (this is the default value), then
1.323 - /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.324 - /// the next arc from \c u to \c v after \c prev.
1.325 - /// \return The found arc or \ref INVALID if there is no such an arc.
1.326 - ///
1.327 - /// Thus you can iterate through each arc from \c u to \c v as it follows.
1.328 - ///\code
1.329 - /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
1.330 - /// ...
1.331 - /// }
1.332 - ///\endcode
1.333 - ///
1.334 - ///\sa ArcLookUp
1.335 - ///\sa AllArcLookUp
1.336 - ///\sa DynArcLookUp
1.337 - ///\sa ConArcIt
1.338 - template <typename Graph>
1.339 - inline typename Graph::Arc
1.340 - findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.341 - typename Graph::Arc prev = INVALID) {
1.342 - return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1.343 - }
1.344 -
1.345 - /// \brief Iterator for iterating on arcs connected the same nodes.
1.346 - ///
1.347 - /// Iterator for iterating on arcs connected the same nodes. It is
1.348 - /// higher level interface for the findArc() function. You can
1.349 - /// use it the following way:
1.350 - ///\code
1.351 - /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.352 - /// ...
1.353 - /// }
1.354 - ///\endcode
1.355 - ///
1.356 - ///\sa findArc()
1.357 - ///\sa ArcLookUp
1.358 - ///\sa AllArcLookUp
1.359 - ///\sa DynArcLookUp
1.360 - template <typename _Graph>
1.361 - class ConArcIt : public _Graph::Arc {
1.362 - public:
1.363 -
1.364 - typedef _Graph Graph;
1.365 - typedef typename Graph::Arc Parent;
1.366 -
1.367 - typedef typename Graph::Arc Arc;
1.368 - typedef typename Graph::Node Node;
1.369 -
1.370 - /// \brief Constructor.
1.371 - ///
1.372 - /// Construct a new ConArcIt iterating on the arcs which
1.373 - /// connects the \c u and \c v node.
1.374 - ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1.375 - Parent::operator=(findArc(_graph, u, v));
1.376 - }
1.377 -
1.378 - /// \brief Constructor.
1.379 - ///
1.380 - /// Construct a new ConArcIt which continues the iterating from
1.381 - /// the \c e arc.
1.382 - ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1.383 -
1.384 - /// \brief Increment operator.
1.385 - ///
1.386 - /// It increments the iterator and gives back the next arc.
1.387 - ConArcIt& operator++() {
1.388 - Parent::operator=(findArc(_graph, _graph.source(*this),
1.389 - _graph.target(*this), *this));
1.390 - return *this;
1.391 - }
1.392 - private:
1.393 - const Graph& _graph;
1.394 - };
1.395 -
1.396 - namespace _graph_utils_bits {
1.397 -
1.398 - template <typename Graph, typename Enable = void>
1.399 - struct FindEdgeSelector {
1.400 - typedef typename Graph::Node Node;
1.401 - typedef typename Graph::Edge Edge;
1.402 - static Edge find(const Graph &g, Node u, Node v, Edge e) {
1.403 - bool b;
1.404 - if (u != v) {
1.405 - if (e == INVALID) {
1.406 - g.firstInc(e, b, u);
1.407 - } else {
1.408 - b = g.u(e) == u;
1.409 - g.nextInc(e, b);
1.410 - }
1.411 - while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1.412 - g.nextInc(e, b);
1.413 - }
1.414 - } else {
1.415 - if (e == INVALID) {
1.416 - g.firstInc(e, b, u);
1.417 - } else {
1.418 - b = true;
1.419 - g.nextInc(e, b);
1.420 - }
1.421 - while (e != INVALID && (!b || g.v(e) != v)) {
1.422 - g.nextInc(e, b);
1.423 - }
1.424 - }
1.425 - return e;
1.426 - }
1.427 - };
1.428 -
1.429 - template <typename Graph>
1.430 - struct FindEdgeSelector<
1.431 - Graph,
1.432 - typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.433 - {
1.434 - typedef typename Graph::Node Node;
1.435 - typedef typename Graph::Edge Edge;
1.436 - static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1.437 - return g.findEdge(u, v, prev);
1.438 - }
1.439 - };
1.440 - }
1.441 -
1.442 - /// \brief Finds an edge between two nodes of a graph.
1.443 - ///
1.444 - /// Finds an edge from node \c u to node \c v in graph \c g.
1.445 - /// If the node \c u and node \c v is equal then each loop edge
1.446 - /// will be enumerated once.
1.447 - ///
1.448 - /// If \c prev is \ref INVALID (this is the default value), then
1.449 - /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.450 - /// the next arc from \c u to \c v after \c prev.
1.451 - /// \return The found arc or \ref INVALID if there is no such an arc.
1.452 - ///
1.453 - /// Thus you can iterate through each arc from \c u to \c v as it follows.
1.454 - ///\code
1.455 - /// for(Edge e = findEdge(g,u,v); e != INVALID;
1.456 - /// e = findEdge(g,u,v,e)) {
1.457 - /// ...
1.458 - /// }
1.459 - ///\endcode
1.460 - ///
1.461 - ///\sa ConEdgeIt
1.462 -
1.463 - template <typename Graph>
1.464 - inline typename Graph::Edge
1.465 - findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.466 - typename Graph::Edge p = INVALID) {
1.467 - return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1.468 - }
1.469 -
1.470 - /// \brief Iterator for iterating on edges connected the same nodes.
1.471 - ///
1.472 - /// Iterator for iterating on edges connected the same nodes. It is
1.473 - /// higher level interface for the findEdge() function. You can
1.474 - /// use it the following way:
1.475 - ///\code
1.476 - /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.477 - /// ...
1.478 - /// }
1.479 - ///\endcode
1.480 - ///
1.481 - ///\sa findEdge()
1.482 - template <typename _Graph>
1.483 - class ConEdgeIt : public _Graph::Edge {
1.484 - public:
1.485 -
1.486 - typedef _Graph Graph;
1.487 - typedef typename Graph::Edge Parent;
1.488 -
1.489 - typedef typename Graph::Edge Edge;
1.490 - typedef typename Graph::Node Node;
1.491 -
1.492 - /// \brief Constructor.
1.493 - ///
1.494 - /// Construct a new ConEdgeIt iterating on the edges which
1.495 - /// connects the \c u and \c v node.
1.496 - ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
1.497 - Parent::operator=(findEdge(_graph, u, v));
1.498 - }
1.499 -
1.500 - /// \brief Constructor.
1.501 - ///
1.502 - /// Construct a new ConEdgeIt which continues the iterating from
1.503 - /// the \c e edge.
1.504 - ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1.505 -
1.506 - /// \brief Increment operator.
1.507 - ///
1.508 - /// It increments the iterator and gives back the next edge.
1.509 - ConEdgeIt& operator++() {
1.510 - Parent::operator=(findEdge(_graph, _graph.u(*this),
1.511 - _graph.v(*this), *this));
1.512 - return *this;
1.513 - }
1.514 - private:
1.515 - const Graph& _graph;
1.516 - };
1.517 -
1.518 - namespace _graph_utils_bits {
1.519 -
1.520 - template <typename Digraph, typename Item, typename RefMap>
1.521 - class MapCopyBase {
1.522 - public:
1.523 - virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
1.524 -
1.525 - virtual ~MapCopyBase() {}
1.526 - };
1.527 -
1.528 - template <typename Digraph, typename Item, typename RefMap,
1.529 - typename ToMap, typename FromMap>
1.530 - class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.531 - public:
1.532 -
1.533 - MapCopy(ToMap& tmap, const FromMap& map)
1.534 - : _tmap(tmap), _map(map) {}
1.535 -
1.536 - virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.537 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.538 - for (ItemIt it(digraph); it != INVALID; ++it) {
1.539 - _tmap.set(refMap[it], _map[it]);
1.540 - }
1.541 - }
1.542 -
1.543 - private:
1.544 - ToMap& _tmap;
1.545 - const FromMap& _map;
1.546 - };
1.547 -
1.548 - template <typename Digraph, typename Item, typename RefMap, typename It>
1.549 - class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.550 - public:
1.551 -
1.552 - ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
1.553 -
1.554 - virtual void copy(const Digraph&, const RefMap& refMap) {
1.555 - _it = refMap[_item];
1.556 - }
1.557 -
1.558 - private:
1.559 - It& _it;
1.560 - Item _item;
1.561 - };
1.562 -
1.563 - template <typename Digraph, typename Item, typename RefMap, typename Ref>
1.564 - class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.565 - public:
1.566 -
1.567 - RefCopy(Ref& map) : _map(map) {}
1.568 -
1.569 - virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.570 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.571 - for (ItemIt it(digraph); it != INVALID; ++it) {
1.572 - _map.set(it, refMap[it]);
1.573 - }
1.574 - }
1.575 -
1.576 - private:
1.577 - Ref& _map;
1.578 - };
1.579 -
1.580 - template <typename Digraph, typename Item, typename RefMap,
1.581 - typename CrossRef>
1.582 - class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.583 - public:
1.584 -
1.585 - CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
1.586 -
1.587 - virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.588 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.589 - for (ItemIt it(digraph); it != INVALID; ++it) {
1.590 - _cmap.set(refMap[it], it);
1.591 - }
1.592 - }
1.593 -
1.594 - private:
1.595 - CrossRef& _cmap;
1.596 - };
1.597 -
1.598 - template <typename Digraph, typename Enable = void>
1.599 - struct DigraphCopySelector {
1.600 - template <typename From, typename NodeRefMap, typename ArcRefMap>
1.601 - static void copy(Digraph &to, const From& from,
1.602 - NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
1.603 - for (typename From::NodeIt it(from); it != INVALID; ++it) {
1.604 - nodeRefMap[it] = to.addNode();
1.605 - }
1.606 - for (typename From::ArcIt it(from); it != INVALID; ++it) {
1.607 - arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
1.608 - nodeRefMap[from.target(it)]);
1.609 - }
1.610 - }
1.611 - };
1.612 -
1.613 - template <typename Digraph>
1.614 - struct DigraphCopySelector<
1.615 - Digraph,
1.616 - typename enable_if<typename Digraph::BuildTag, void>::type>
1.617 - {
1.618 - template <typename From, typename NodeRefMap, typename ArcRefMap>
1.619 - static void copy(Digraph &to, const From& from,
1.620 - NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
1.621 - to.build(from, nodeRefMap, arcRefMap);
1.622 - }
1.623 - };
1.624 -
1.625 - template <typename Graph, typename Enable = void>
1.626 - struct GraphCopySelector {
1.627 - template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.628 - static void copy(Graph &to, const From& from,
1.629 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.630 - for (typename From::NodeIt it(from); it != INVALID; ++it) {
1.631 - nodeRefMap[it] = to.addNode();
1.632 - }
1.633 - for (typename From::EdgeIt it(from); it != INVALID; ++it) {
1.634 - edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
1.635 - nodeRefMap[from.v(it)]);
1.636 - }
1.637 - }
1.638 - };
1.639 -
1.640 - template <typename Graph>
1.641 - struct GraphCopySelector<
1.642 - Graph,
1.643 - typename enable_if<typename Graph::BuildTag, void>::type>
1.644 - {
1.645 - template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.646 - static void copy(Graph &to, const From& from,
1.647 - NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.648 - to.build(from, nodeRefMap, edgeRefMap);
1.649 - }
1.650 - };
1.651 -
1.652 - }
1.653 -
1.654 - /// \brief Class to copy a digraph.
1.655 - ///
1.656 - /// Class to copy a digraph to another digraph (duplicate a digraph). The
1.657 - /// simplest way of using it is through the \c copyDigraph() function.
1.658 - ///
1.659 - /// This class not just make a copy of a graph, but it can create
1.660 - /// references and cross references between the nodes and arcs of
1.661 - /// the two graphs, it can copy maps for use with the newly created
1.662 - /// graph and copy nodes and arcs.
1.663 - ///
1.664 - /// To make a copy from a graph, first an instance of DigraphCopy
1.665 - /// should be created, then the data belongs to the graph should
1.666 - /// assigned to copy. In the end, the \c run() member should be
1.667 - /// called.
1.668 - ///
1.669 - /// The next code copies a graph with several data:
1.670 - ///\code
1.671 - /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.672 - /// // create a reference for the nodes
1.673 - /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.674 - /// dc.nodeRef(nr);
1.675 - /// // create a cross reference (inverse) for the arcs
1.676 - /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
1.677 - /// dc.arcCrossRef(acr);
1.678 - /// // copy an arc map
1.679 - /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.680 - /// NewGraph::ArcMap<double> namap(new_graph);
1.681 - /// dc.arcMap(namap, oamap);
1.682 - /// // copy a node
1.683 - /// OrigGraph::Node on;
1.684 - /// NewGraph::Node nn;
1.685 - /// dc.node(nn, on);
1.686 - /// // Executions of copy
1.687 - /// dc.run();
1.688 - ///\endcode
1.689 - template <typename To, typename From>
1.690 - class DigraphCopy {
1.691 - private:
1.692 -
1.693 - typedef typename From::Node Node;
1.694 - typedef typename From::NodeIt NodeIt;
1.695 - typedef typename From::Arc Arc;
1.696 - typedef typename From::ArcIt ArcIt;
1.697 -
1.698 - typedef typename To::Node TNode;
1.699 - typedef typename To::Arc TArc;
1.700 -
1.701 - typedef typename From::template NodeMap<TNode> NodeRefMap;
1.702 - typedef typename From::template ArcMap<TArc> ArcRefMap;
1.703 -
1.704 -
1.705 - public:
1.706 -
1.707 -
1.708 - /// \brief Constructor for the DigraphCopy.
1.709 - ///
1.710 - /// It copies the content of the \c _from digraph into the
1.711 - /// \c _to digraph.
1.712 - DigraphCopy(To& to, const From& from)
1.713 - : _from(from), _to(to) {}
1.714 -
1.715 - /// \brief Destructor of the DigraphCopy
1.716 - ///
1.717 - /// Destructor of the DigraphCopy
1.718 - ~DigraphCopy() {
1.719 - for (int i = 0; i < int(_node_maps.size()); ++i) {
1.720 - delete _node_maps[i];
1.721 - }
1.722 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.723 - delete _arc_maps[i];
1.724 - }
1.725 -
1.726 - }
1.727 -
1.728 - /// \brief Copies the node references into the given map.
1.729 - ///
1.730 - /// Copies the node references into the given map. The parameter
1.731 - /// should be a map, which key type is the Node type of the source
1.732 - /// graph, while the value type is the Node type of the
1.733 - /// destination graph.
1.734 - template <typename NodeRef>
1.735 - DigraphCopy& nodeRef(NodeRef& map) {
1.736 - _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.737 - NodeRefMap, NodeRef>(map));
1.738 - return *this;
1.739 - }
1.740 -
1.741 - /// \brief Copies the node cross references into the given map.
1.742 - ///
1.743 - /// Copies the node cross references (reverse references) into
1.744 - /// the given map. The parameter should be a map, which key type
1.745 - /// is the Node type of the destination graph, while the value type is
1.746 - /// the Node type of the source graph.
1.747 - template <typename NodeCrossRef>
1.748 - DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.749 - _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1.750 - NodeRefMap, NodeCrossRef>(map));
1.751 - return *this;
1.752 - }
1.753 -
1.754 - /// \brief Make copy of the given map.
1.755 - ///
1.756 - /// Makes copy of the given map for the newly created digraph.
1.757 - /// The new map's key type is the destination graph's node type,
1.758 - /// and the copied map's key type is the source graph's node type.
1.759 - template <typename ToMap, typename FromMap>
1.760 - DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.761 - _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.762 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.763 - return *this;
1.764 - }
1.765 -
1.766 - /// \brief Make a copy of the given node.
1.767 - ///
1.768 - /// Make a copy of the given node.
1.769 - DigraphCopy& node(TNode& tnode, const Node& snode) {
1.770 - _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.771 - NodeRefMap, TNode>(tnode, snode));
1.772 - return *this;
1.773 - }
1.774 -
1.775 - /// \brief Copies the arc references into the given map.
1.776 - ///
1.777 - /// Copies the arc references into the given map.
1.778 - template <typename ArcRef>
1.779 - DigraphCopy& arcRef(ArcRef& map) {
1.780 - _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.781 - ArcRefMap, ArcRef>(map));
1.782 - return *this;
1.783 - }
1.784 -
1.785 - /// \brief Copies the arc cross references into the given map.
1.786 - ///
1.787 - /// Copies the arc cross references (reverse references) into
1.788 - /// the given map.
1.789 - template <typename ArcCrossRef>
1.790 - DigraphCopy& arcCrossRef(ArcCrossRef& map) {
1.791 - _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
1.792 - ArcRefMap, ArcCrossRef>(map));
1.793 - return *this;
1.794 - }
1.795 -
1.796 - /// \brief Make copy of the given map.
1.797 - ///
1.798 - /// Makes copy of the given map for the newly created digraph.
1.799 - /// The new map's key type is the to digraph's arc type,
1.800 - /// and the copied map's key type is the from digraph's arc
1.801 - /// type.
1.802 - template <typename ToMap, typename FromMap>
1.803 - DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.804 - _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.805 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.806 - return *this;
1.807 - }
1.808 -
1.809 - /// \brief Make a copy of the given arc.
1.810 - ///
1.811 - /// Make a copy of the given arc.
1.812 - DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.813 - _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.814 - ArcRefMap, TArc>(tarc, sarc));
1.815 - return *this;
1.816 - }
1.817 -
1.818 - /// \brief Executes the copies.
1.819 - ///
1.820 - /// Executes the copies.
1.821 - void run() {
1.822 - NodeRefMap nodeRefMap(_from);
1.823 - ArcRefMap arcRefMap(_from);
1.824 - _graph_utils_bits::DigraphCopySelector<To>::
1.825 - copy(_to, _from, nodeRefMap, arcRefMap);
1.826 - for (int i = 0; i < int(_node_maps.size()); ++i) {
1.827 - _node_maps[i]->copy(_from, nodeRefMap);
1.828 - }
1.829 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.830 - _arc_maps[i]->copy(_from, arcRefMap);
1.831 - }
1.832 - }
1.833 -
1.834 - protected:
1.835 -
1.836 -
1.837 - const From& _from;
1.838 - To& _to;
1.839 -
1.840 - std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.841 - _node_maps;
1.842 -
1.843 - std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.844 - _arc_maps;
1.845 -
1.846 - };
1.847 -
1.848 - /// \brief Copy a digraph to another digraph.
1.849 - ///
1.850 - /// Copy a digraph to another digraph. The complete usage of the
1.851 - /// function is detailed in the DigraphCopy class, but a short
1.852 - /// example shows a basic work:
1.853 - ///\code
1.854 - /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.855 - ///\endcode
1.856 - ///
1.857 - /// After the copy the \c nr map will contain the mapping from the
1.858 - /// nodes of the \c from digraph to the nodes of the \c to digraph and
1.859 - /// \c ecr will contain the mapping from the arcs of the \c to digraph
1.860 - /// to the arcs of the \c from digraph.
1.861 - ///
1.862 - /// \see DigraphCopy
1.863 - template <typename To, typename From>
1.864 - DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
1.865 - return DigraphCopy<To, From>(to, from);
1.866 - }
1.867 -
1.868 - /// \brief Class to copy a graph.
1.869 - ///
1.870 - /// Class to copy a graph to another graph (duplicate a graph). The
1.871 - /// simplest way of using it is through the \c copyGraph() function.
1.872 - ///
1.873 - /// This class not just make a copy of a graph, but it can create
1.874 - /// references and cross references between the nodes, edges and arcs of
1.875 - /// the two graphs, it can copy maps for use with the newly created
1.876 - /// graph and copy nodes, edges and arcs.
1.877 - ///
1.878 - /// To make a copy from a graph, first an instance of GraphCopy
1.879 - /// should be created, then the data belongs to the graph should
1.880 - /// assigned to copy. In the end, the \c run() member should be
1.881 - /// called.
1.882 - ///
1.883 - /// The next code copies a graph with several data:
1.884 - ///\code
1.885 - /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.886 - /// // create a reference for the nodes
1.887 - /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.888 - /// dc.nodeRef(nr);
1.889 - /// // create a cross reference (inverse) for the edges
1.890 - /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
1.891 - /// dc.edgeCrossRef(ecr);
1.892 - /// // copy an arc map
1.893 - /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.894 - /// NewGraph::ArcMap<double> namap(new_graph);
1.895 - /// dc.arcMap(namap, oamap);
1.896 - /// // copy a node
1.897 - /// OrigGraph::Node on;
1.898 - /// NewGraph::Node nn;
1.899 - /// dc.node(nn, on);
1.900 - /// // Executions of copy
1.901 - /// dc.run();
1.902 - ///\endcode
1.903 - template <typename To, typename From>
1.904 - class GraphCopy {
1.905 - private:
1.906 -
1.907 - typedef typename From::Node Node;
1.908 - typedef typename From::NodeIt NodeIt;
1.909 - typedef typename From::Arc Arc;
1.910 - typedef typename From::ArcIt ArcIt;
1.911 - typedef typename From::Edge Edge;
1.912 - typedef typename From::EdgeIt EdgeIt;
1.913 -
1.914 - typedef typename To::Node TNode;
1.915 - typedef typename To::Arc TArc;
1.916 - typedef typename To::Edge TEdge;
1.917 -
1.918 - typedef typename From::template NodeMap<TNode> NodeRefMap;
1.919 - typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1.920 -
1.921 - struct ArcRefMap {
1.922 - ArcRefMap(const To& to, const From& from,
1.923 - const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
1.924 - : _to(to), _from(from),
1.925 - _edge_ref(edge_ref), _node_ref(node_ref) {}
1.926 -
1.927 - typedef typename From::Arc Key;
1.928 - typedef typename To::Arc Value;
1.929 -
1.930 - Value operator[](const Key& key) const {
1.931 - bool forward = _from.u(key) != _from.v(key) ?
1.932 - _node_ref[_from.source(key)] ==
1.933 - _to.source(_to.direct(_edge_ref[key], true)) :
1.934 - _from.direction(key);
1.935 - return _to.direct(_edge_ref[key], forward);
1.936 - }
1.937 -
1.938 - const To& _to;
1.939 - const From& _from;
1.940 - const EdgeRefMap& _edge_ref;
1.941 - const NodeRefMap& _node_ref;
1.942 - };
1.943 -
1.944 -
1.945 - public:
1.946 -
1.947 -
1.948 - /// \brief Constructor for the GraphCopy.
1.949 - ///
1.950 - /// It copies the content of the \c _from graph into the
1.951 - /// \c _to graph.
1.952 - GraphCopy(To& to, const From& from)
1.953 - : _from(from), _to(to) {}
1.954 -
1.955 - /// \brief Destructor of the GraphCopy
1.956 - ///
1.957 - /// Destructor of the GraphCopy
1.958 - ~GraphCopy() {
1.959 - for (int i = 0; i < int(_node_maps.size()); ++i) {
1.960 - delete _node_maps[i];
1.961 - }
1.962 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.963 - delete _arc_maps[i];
1.964 - }
1.965 - for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.966 - delete _edge_maps[i];
1.967 - }
1.968 -
1.969 - }
1.970 -
1.971 - /// \brief Copies the node references into the given map.
1.972 - ///
1.973 - /// Copies the node references into the given map.
1.974 - template <typename NodeRef>
1.975 - GraphCopy& nodeRef(NodeRef& map) {
1.976 - _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.977 - NodeRefMap, NodeRef>(map));
1.978 - return *this;
1.979 - }
1.980 -
1.981 - /// \brief Copies the node cross references into the given map.
1.982 - ///
1.983 - /// Copies the node cross references (reverse references) into
1.984 - /// the given map.
1.985 - template <typename NodeCrossRef>
1.986 - GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.987 - _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1.988 - NodeRefMap, NodeCrossRef>(map));
1.989 - return *this;
1.990 - }
1.991 -
1.992 - /// \brief Make copy of the given map.
1.993 - ///
1.994 - /// Makes copy of the given map for the newly created graph.
1.995 - /// The new map's key type is the to graph's node type,
1.996 - /// and the copied map's key type is the from graph's node
1.997 - /// type.
1.998 - template <typename ToMap, typename FromMap>
1.999 - GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.1000 - _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.1001 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.1002 - return *this;
1.1003 - }
1.1004 -
1.1005 - /// \brief Make a copy of the given node.
1.1006 - ///
1.1007 - /// Make a copy of the given node.
1.1008 - GraphCopy& node(TNode& tnode, const Node& snode) {
1.1009 - _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.1010 - NodeRefMap, TNode>(tnode, snode));
1.1011 - return *this;
1.1012 - }
1.1013 -
1.1014 - /// \brief Copies the arc references into the given map.
1.1015 - ///
1.1016 - /// Copies the arc references into the given map.
1.1017 - template <typename ArcRef>
1.1018 - GraphCopy& arcRef(ArcRef& map) {
1.1019 - _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.1020 - ArcRefMap, ArcRef>(map));
1.1021 - return *this;
1.1022 - }
1.1023 -
1.1024 - /// \brief Copies the arc cross references into the given map.
1.1025 - ///
1.1026 - /// Copies the arc cross references (reverse references) into
1.1027 - /// the given map.
1.1028 - template <typename ArcCrossRef>
1.1029 - GraphCopy& arcCrossRef(ArcCrossRef& map) {
1.1030 - _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
1.1031 - ArcRefMap, ArcCrossRef>(map));
1.1032 - return *this;
1.1033 - }
1.1034 -
1.1035 - /// \brief Make copy of the given map.
1.1036 - ///
1.1037 - /// Makes copy of the given map for the newly created graph.
1.1038 - /// The new map's key type is the to graph's arc type,
1.1039 - /// and the copied map's key type is the from graph's arc
1.1040 - /// type.
1.1041 - template <typename ToMap, typename FromMap>
1.1042 - GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.1043 - _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.1044 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.1045 - return *this;
1.1046 - }
1.1047 -
1.1048 - /// \brief Make a copy of the given arc.
1.1049 - ///
1.1050 - /// Make a copy of the given arc.
1.1051 - GraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.1052 - _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.1053 - ArcRefMap, TArc>(tarc, sarc));
1.1054 - return *this;
1.1055 - }
1.1056 -
1.1057 - /// \brief Copies the edge references into the given map.
1.1058 - ///
1.1059 - /// Copies the edge references into the given map.
1.1060 - template <typename EdgeRef>
1.1061 - GraphCopy& edgeRef(EdgeRef& map) {
1.1062 - _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1.1063 - EdgeRefMap, EdgeRef>(map));
1.1064 - return *this;
1.1065 - }
1.1066 -
1.1067 - /// \brief Copies the edge cross references into the given map.
1.1068 - ///
1.1069 - /// Copies the edge cross references (reverse
1.1070 - /// references) into the given map.
1.1071 - template <typename EdgeCrossRef>
1.1072 - GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.1073 - _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
1.1074 - Edge, EdgeRefMap, EdgeCrossRef>(map));
1.1075 - return *this;
1.1076 - }
1.1077 -
1.1078 - /// \brief Make copy of the given map.
1.1079 - ///
1.1080 - /// Makes copy of the given map for the newly created graph.
1.1081 - /// The new map's key type is the to graph's edge type,
1.1082 - /// and the copied map's key type is the from graph's edge
1.1083 - /// type.
1.1084 - template <typename ToMap, typename FromMap>
1.1085 - GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1.1086 - _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1.1087 - EdgeRefMap, ToMap, FromMap>(tmap, map));
1.1088 - return *this;
1.1089 - }
1.1090 -
1.1091 - /// \brief Make a copy of the given edge.
1.1092 - ///
1.1093 - /// Make a copy of the given edge.
1.1094 - GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1.1095 - _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1.1096 - EdgeRefMap, TEdge>(tedge, sedge));
1.1097 - return *this;
1.1098 - }
1.1099 -
1.1100 - /// \brief Executes the copies.
1.1101 - ///
1.1102 - /// Executes the copies.
1.1103 - void run() {
1.1104 - NodeRefMap nodeRefMap(_from);
1.1105 - EdgeRefMap edgeRefMap(_from);
1.1106 - ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
1.1107 - _graph_utils_bits::GraphCopySelector<To>::
1.1108 - copy(_to, _from, nodeRefMap, edgeRefMap);
1.1109 - for (int i = 0; i < int(_node_maps.size()); ++i) {
1.1110 - _node_maps[i]->copy(_from, nodeRefMap);
1.1111 - }
1.1112 - for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.1113 - _edge_maps[i]->copy(_from, edgeRefMap);
1.1114 - }
1.1115 - for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.1116 - _arc_maps[i]->copy(_from, arcRefMap);
1.1117 - }
1.1118 - }
1.1119 -
1.1120 - private:
1.1121 -
1.1122 - const From& _from;
1.1123 - To& _to;
1.1124 -
1.1125 - std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.1126 - _node_maps;
1.1127 -
1.1128 - std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.1129 - _arc_maps;
1.1130 -
1.1131 - std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.1132 - _edge_maps;
1.1133 -
1.1134 - };
1.1135 -
1.1136 - /// \brief Copy a graph to another graph.
1.1137 - ///
1.1138 - /// Copy a graph to another graph. The complete usage of the
1.1139 - /// function is detailed in the GraphCopy class, but a short
1.1140 - /// example shows a basic work:
1.1141 - ///\code
1.1142 - /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.1143 - ///\endcode
1.1144 - ///
1.1145 - /// After the copy the \c nr map will contain the mapping from the
1.1146 - /// nodes of the \c from graph to the nodes of the \c to graph and
1.1147 - /// \c ecr will contain the mapping from the arcs of the \c to graph
1.1148 - /// to the arcs of the \c from graph.
1.1149 - ///
1.1150 - /// \see GraphCopy
1.1151 - template <typename To, typename From>
1.1152 - GraphCopy<To, From>
1.1153 - copyGraph(To& to, const From& from) {
1.1154 - return GraphCopy<To, From>(to, from);
1.1155 - }
1.1156 -
1.1157 - /// @}
1.1158 -
1.1159 - /// \addtogroup graph_maps
1.1160 - /// @{
1.1161 -
1.1162 - /// Provides an immutable and unique id for each item in the graph.
1.1163 -
1.1164 - /// The IdMap class provides a unique and immutable id for each item of the
1.1165 - /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1.1166 - /// different items (nodes) get different ids <li>\b immutable: the id of an
1.1167 - /// item (node) does not change (even if you delete other nodes). </ul>
1.1168 - /// Through this map you get access (i.e. can read) the inner id values of
1.1169 - /// the items stored in the graph. This map can be inverted with its member
1.1170 - /// class \c InverseMap or with the \c operator() member.
1.1171 - ///
1.1172 - template <typename _Graph, typename _Item>
1.1173 - class IdMap {
1.1174 - public:
1.1175 - typedef _Graph Graph;
1.1176 - typedef int Value;
1.1177 - typedef _Item Item;
1.1178 - typedef _Item Key;
1.1179 -
1.1180 - /// \brief Constructor.
1.1181 - ///
1.1182 - /// Constructor of the map.
1.1183 - explicit IdMap(const Graph& graph) : _graph(&graph) {}
1.1184 -
1.1185 - /// \brief Gives back the \e id of the item.
1.1186 - ///
1.1187 - /// Gives back the immutable and unique \e id of the item.
1.1188 - int operator[](const Item& item) const { return _graph->id(item);}
1.1189 -
1.1190 - /// \brief Gives back the item by its id.
1.1191 - ///
1.1192 - /// Gives back the item by its id.
1.1193 - Item operator()(int id) { return _graph->fromId(id, Item()); }
1.1194 -
1.1195 - private:
1.1196 - const Graph* _graph;
1.1197 -
1.1198 - public:
1.1199 -
1.1200 - /// \brief The class represents the inverse of its owner (IdMap).
1.1201 - ///
1.1202 - /// The class represents the inverse of its owner (IdMap).
1.1203 - /// \see inverse()
1.1204 - class InverseMap {
1.1205 - public:
1.1206 -
1.1207 - /// \brief Constructor.
1.1208 - ///
1.1209 - /// Constructor for creating an id-to-item map.
1.1210 - explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1.1211 -
1.1212 - /// \brief Constructor.
1.1213 - ///
1.1214 - /// Constructor for creating an id-to-item map.
1.1215 - explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1.1216 -
1.1217 - /// \brief Gives back the given item from its id.
1.1218 - ///
1.1219 - /// Gives back the given item from its id.
1.1220 - ///
1.1221 - Item operator[](int id) const { return _graph->fromId(id, Item());}
1.1222 -
1.1223 - private:
1.1224 - const Graph* _graph;
1.1225 - };
1.1226 -
1.1227 - /// \brief Gives back the inverse of the map.
1.1228 - ///
1.1229 - /// Gives back the inverse of the IdMap.
1.1230 - InverseMap inverse() const { return InverseMap(*_graph);}
1.1231 -
1.1232 - };
1.1233 -
1.1234 -
1.1235 - /// \brief General invertable graph-map type.
1.1236 -
1.1237 - /// This type provides simple invertable graph-maps.
1.1238 - /// The InvertableMap wraps an arbitrary ReadWriteMap
1.1239 - /// and if a key is set to a new value then store it
1.1240 - /// in the inverse map.
1.1241 - ///
1.1242 - /// The values of the map can be accessed
1.1243 - /// with stl compatible forward iterator.
1.1244 - ///
1.1245 - /// \tparam _Graph The graph type.
1.1246 - /// \tparam _Item The item type of the graph.
1.1247 - /// \tparam _Value The value type of the map.
1.1248 - ///
1.1249 - /// \see IterableValueMap
1.1250 - template <typename _Graph, typename _Item, typename _Value>
1.1251 - class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1.1252 - private:
1.1253 -
1.1254 - typedef DefaultMap<_Graph, _Item, _Value> Map;
1.1255 - typedef _Graph Graph;
1.1256 -
1.1257 - typedef std::map<_Value, _Item> Container;
1.1258 - Container _inv_map;
1.1259 -
1.1260 - public:
1.1261 -
1.1262 - /// The key type of InvertableMap (Node, Arc, Edge).
1.1263 - typedef typename Map::Key Key;
1.1264 - /// The value type of the InvertableMap.
1.1265 - typedef typename Map::Value Value;
1.1266 -
1.1267 -
1.1268 -
1.1269 - /// \brief Constructor.
1.1270 - ///
1.1271 - /// Construct a new InvertableMap for the graph.
1.1272 - ///
1.1273 - explicit InvertableMap(const Graph& graph) : Map(graph) {}
1.1274 -
1.1275 - /// \brief Forward iterator for values.
1.1276 - ///
1.1277 - /// This iterator is an stl compatible forward
1.1278 - /// iterator on the values of the map. The values can
1.1279 - /// be accessed in the [beginValue, endValue) range.
1.1280 - ///
1.1281 - class ValueIterator
1.1282 - : public std::iterator<std::forward_iterator_tag, Value> {
1.1283 - friend class InvertableMap;
1.1284 - private:
1.1285 - ValueIterator(typename Container::const_iterator _it)
1.1286 - : it(_it) {}
1.1287 - public:
1.1288 -
1.1289 - ValueIterator() {}
1.1290 -
1.1291 - ValueIterator& operator++() { ++it; return *this; }
1.1292 - ValueIterator operator++(int) {
1.1293 - ValueIterator tmp(*this);
1.1294 - operator++();
1.1295 - return tmp;
1.1296 - }
1.1297 -
1.1298 - const Value& operator*() const { return it->first; }
1.1299 - const Value* operator->() const { return &(it->first); }
1.1300 -
1.1301 - bool operator==(ValueIterator jt) const { return it == jt.it; }
1.1302 - bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.1303 -
1.1304 - private:
1.1305 - typename Container::const_iterator it;
1.1306 - };
1.1307 -
1.1308 - /// \brief Returns an iterator to the first value.
1.1309 - ///
1.1310 - /// Returns an stl compatible iterator to the
1.1311 - /// first value of the map. The values of the
1.1312 - /// map can be accessed in the [beginValue, endValue)
1.1313 - /// range.
1.1314 - ValueIterator beginValue() const {
1.1315 - return ValueIterator(_inv_map.begin());
1.1316 - }
1.1317 -
1.1318 - /// \brief Returns an iterator after the last value.
1.1319 - ///
1.1320 - /// Returns an stl compatible iterator after the
1.1321 - /// last value of the map. The values of the
1.1322 - /// map can be accessed in the [beginValue, endValue)
1.1323 - /// range.
1.1324 - ValueIterator endValue() const {
1.1325 - return ValueIterator(_inv_map.end());
1.1326 - }
1.1327 -
1.1328 - /// \brief The setter function of the map.
1.1329 - ///
1.1330 - /// Sets the mapped value.
1.1331 - void set(const Key& key, const Value& val) {
1.1332 - Value oldval = Map::operator[](key);
1.1333 - typename Container::iterator it = _inv_map.find(oldval);
1.1334 - if (it != _inv_map.end() && it->second == key) {
1.1335 - _inv_map.erase(it);
1.1336 - }
1.1337 - _inv_map.insert(make_pair(val, key));
1.1338 - Map::set(key, val);
1.1339 - }
1.1340 -
1.1341 - /// \brief The getter function of the map.
1.1342 - ///
1.1343 - /// It gives back the value associated with the key.
1.1344 - typename MapTraits<Map>::ConstReturnValue
1.1345 - operator[](const Key& key) const {
1.1346 - return Map::operator[](key);
1.1347 - }
1.1348 -
1.1349 - /// \brief Gives back the item by its value.
1.1350 - ///
1.1351 - /// Gives back the item by its value.
1.1352 - Key operator()(const Value& key) const {
1.1353 - typename Container::const_iterator it = _inv_map.find(key);
1.1354 - return it != _inv_map.end() ? it->second : INVALID;
1.1355 - }
1.1356 -
1.1357 - protected:
1.1358 -
1.1359 - /// \brief Erase the key from the map.
1.1360 - ///
1.1361 - /// Erase the key to the map. It is called by the
1.1362 - /// \c AlterationNotifier.
1.1363 - virtual void erase(const Key& key) {
1.1364 - Value val = Map::operator[](key);
1.1365 - typename Container::iterator it = _inv_map.find(val);
1.1366 - if (it != _inv_map.end() && it->second == key) {
1.1367 - _inv_map.erase(it);
1.1368 - }
1.1369 - Map::erase(key);
1.1370 - }
1.1371 -
1.1372 - /// \brief Erase more keys from the map.
1.1373 - ///
1.1374 - /// Erase more keys from the map. It is called by the
1.1375 - /// \c AlterationNotifier.
1.1376 - virtual void erase(const std::vector<Key>& keys) {
1.1377 - for (int i = 0; i < int(keys.size()); ++i) {
1.1378 - Value val = Map::operator[](keys[i]);
1.1379 - typename Container::iterator it = _inv_map.find(val);
1.1380 - if (it != _inv_map.end() && it->second == keys[i]) {
1.1381 - _inv_map.erase(it);
1.1382 - }
1.1383 - }
1.1384 - Map::erase(keys);
1.1385 - }
1.1386 -
1.1387 - /// \brief Clear the keys from the map and inverse map.
1.1388 - ///
1.1389 - /// Clear the keys from the map and inverse map. It is called by the
1.1390 - /// \c AlterationNotifier.
1.1391 - virtual void clear() {
1.1392 - _inv_map.clear();
1.1393 - Map::clear();
1.1394 - }
1.1395 -
1.1396 - public:
1.1397 -
1.1398 - /// \brief The inverse map type.
1.1399 - ///
1.1400 - /// The inverse of this map. The subscript operator of the map
1.1401 - /// gives back always the item what was last assigned to the value.
1.1402 - class InverseMap {
1.1403 - public:
1.1404 - /// \brief Constructor of the InverseMap.
1.1405 - ///
1.1406 - /// Constructor of the InverseMap.
1.1407 - explicit InverseMap(const InvertableMap& inverted)
1.1408 - : _inverted(inverted) {}
1.1409 -
1.1410 - /// The value type of the InverseMap.
1.1411 - typedef typename InvertableMap::Key Value;
1.1412 - /// The key type of the InverseMap.
1.1413 - typedef typename InvertableMap::Value Key;
1.1414 -
1.1415 - /// \brief Subscript operator.
1.1416 - ///
1.1417 - /// Subscript operator. It gives back always the item
1.1418 - /// what was last assigned to the value.
1.1419 - Value operator[](const Key& key) const {
1.1420 - return _inverted(key);
1.1421 - }
1.1422 -
1.1423 - private:
1.1424 - const InvertableMap& _inverted;
1.1425 - };
1.1426 -
1.1427 - /// \brief It gives back the just readable inverse map.
1.1428 - ///
1.1429 - /// It gives back the just readable inverse map.
1.1430 - InverseMap inverse() const {
1.1431 - return InverseMap(*this);
1.1432 - }
1.1433 -
1.1434 -
1.1435 -
1.1436 - };
1.1437 -
1.1438 - /// \brief Provides a mutable, continuous and unique descriptor for each
1.1439 - /// item in the graph.
1.1440 - ///
1.1441 - /// The DescriptorMap class provides a unique and continuous (but mutable)
1.1442 - /// descriptor (id) for each item of the same type (e.g. node) in the
1.1443 - /// graph. This id is <ul><li>\b unique: different items (nodes) get
1.1444 - /// different ids <li>\b continuous: the range of the ids is the set of
1.1445 - /// integers between 0 and \c n-1, where \c n is the number of the items of
1.1446 - /// this type (e.g. nodes) (so the id of a node can change if you delete an
1.1447 - /// other node, i.e. this id is mutable). </ul> This map can be inverted
1.1448 - /// with its member class \c InverseMap, or with the \c operator() member.
1.1449 - ///
1.1450 - /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
1.1451 - /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
1.1452 - /// Edge.
1.1453 - template <typename _Graph, typename _Item>
1.1454 - class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1.1455 -
1.1456 - typedef _Item Item;
1.1457 - typedef DefaultMap<_Graph, _Item, int> Map;
1.1458 -
1.1459 - public:
1.1460 - /// The graph class of DescriptorMap.
1.1461 - typedef _Graph Graph;
1.1462 -
1.1463 - /// The key type of DescriptorMap (Node, Arc, Edge).
1.1464 - typedef typename Map::Key Key;
1.1465 - /// The value type of DescriptorMap.
1.1466 - typedef typename Map::Value Value;
1.1467 -
1.1468 - /// \brief Constructor.
1.1469 - ///
1.1470 - /// Constructor for descriptor map.
1.1471 - explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1.1472 - Item it;
1.1473 - const typename Map::Notifier* nf = Map::notifier();
1.1474 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.1475 - Map::set(it, _inv_map.size());
1.1476 - _inv_map.push_back(it);
1.1477 - }
1.1478 - }
1.1479 -
1.1480 - protected:
1.1481 -
1.1482 - /// \brief Add a new key to the map.
1.1483 - ///
1.1484 - /// Add a new key to the map. It is called by the
1.1485 - /// \c AlterationNotifier.
1.1486 - virtual void add(const Item& item) {
1.1487 - Map::add(item);
1.1488 - Map::set(item, _inv_map.size());
1.1489 - _inv_map.push_back(item);
1.1490 - }
1.1491 -
1.1492 - /// \brief Add more new keys to the map.
1.1493 - ///
1.1494 - /// Add more new keys to the map. It is called by the
1.1495 - /// \c AlterationNotifier.
1.1496 - virtual void add(const std::vector<Item>& items) {
1.1497 - Map::add(items);
1.1498 - for (int i = 0; i < int(items.size()); ++i) {
1.1499 - Map::set(items[i], _inv_map.size());
1.1500 - _inv_map.push_back(items[i]);
1.1501 - }
1.1502 - }
1.1503 -
1.1504 - /// \brief Erase the key from the map.
1.1505 - ///
1.1506 - /// Erase the key from the map. It is called by the
1.1507 - /// \c AlterationNotifier.
1.1508 - virtual void erase(const Item& item) {
1.1509 - Map::set(_inv_map.back(), Map::operator[](item));
1.1510 - _inv_map[Map::operator[](item)] = _inv_map.back();
1.1511 - _inv_map.pop_back();
1.1512 - Map::erase(item);
1.1513 - }
1.1514 -
1.1515 - /// \brief Erase more keys from the map.
1.1516 - ///
1.1517 - /// Erase more keys from the map. It is called by the
1.1518 - /// \c AlterationNotifier.
1.1519 - virtual void erase(const std::vector<Item>& items) {
1.1520 - for (int i = 0; i < int(items.size()); ++i) {
1.1521 - Map::set(_inv_map.back(), Map::operator[](items[i]));
1.1522 - _inv_map[Map::operator[](items[i])] = _inv_map.back();
1.1523 - _inv_map.pop_back();
1.1524 - }
1.1525 - Map::erase(items);
1.1526 - }
1.1527 -
1.1528 - /// \brief Build the unique map.
1.1529 - ///
1.1530 - /// Build the unique map. It is called by the
1.1531 - /// \c AlterationNotifier.
1.1532 - virtual void build() {
1.1533 - Map::build();
1.1534 - Item it;
1.1535 - const typename Map::Notifier* nf = Map::notifier();
1.1536 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.1537 - Map::set(it, _inv_map.size());
1.1538 - _inv_map.push_back(it);
1.1539 - }
1.1540 - }
1.1541 -
1.1542 - /// \brief Clear the keys from the map.
1.1543 - ///
1.1544 - /// Clear the keys from the map. It is called by the
1.1545 - /// \c AlterationNotifier.
1.1546 - virtual void clear() {
1.1547 - _inv_map.clear();
1.1548 - Map::clear();
1.1549 - }
1.1550 -
1.1551 - public:
1.1552 -
1.1553 - /// \brief Returns the maximal value plus one.
1.1554 - ///
1.1555 - /// Returns the maximal value plus one in the map.
1.1556 - unsigned int size() const {
1.1557 - return _inv_map.size();
1.1558 - }
1.1559 -
1.1560 - /// \brief Swaps the position of the two items in the map.
1.1561 - ///
1.1562 - /// Swaps the position of the two items in the map.
1.1563 - void swap(const Item& p, const Item& q) {
1.1564 - int pi = Map::operator[](p);
1.1565 - int qi = Map::operator[](q);
1.1566 - Map::set(p, qi);
1.1567 - _inv_map[qi] = p;
1.1568 - Map::set(q, pi);
1.1569 - _inv_map[pi] = q;
1.1570 - }
1.1571 -
1.1572 - /// \brief Gives back the \e descriptor of the item.
1.1573 - ///
1.1574 - /// Gives back the mutable and unique \e descriptor of the map.
1.1575 - int operator[](const Item& item) const {
1.1576 - return Map::operator[](item);
1.1577 - }
1.1578 -
1.1579 - /// \brief Gives back the item by its descriptor.
1.1580 - ///
1.1581 - /// Gives back th item by its descriptor.
1.1582 - Item operator()(int id) const {
1.1583 - return _inv_map[id];
1.1584 - }
1.1585 -
1.1586 - private:
1.1587 -
1.1588 - typedef std::vector<Item> Container;
1.1589 - Container _inv_map;
1.1590 -
1.1591 - public:
1.1592 - /// \brief The inverse map type of DescriptorMap.
1.1593 - ///
1.1594 - /// The inverse map type of DescriptorMap.
1.1595 - class InverseMap {
1.1596 - public:
1.1597 - /// \brief Constructor of the InverseMap.
1.1598 - ///
1.1599 - /// Constructor of the InverseMap.
1.1600 - explicit InverseMap(const DescriptorMap& inverted)
1.1601 - : _inverted(inverted) {}
1.1602 -
1.1603 -
1.1604 - /// The value type of the InverseMap.
1.1605 - typedef typename DescriptorMap::Key Value;
1.1606 - /// The key type of the InverseMap.
1.1607 - typedef typename DescriptorMap::Value Key;
1.1608 -
1.1609 - /// \brief Subscript operator.
1.1610 - ///
1.1611 - /// Subscript operator. It gives back the item
1.1612 - /// that the descriptor belongs to currently.
1.1613 - Value operator[](const Key& key) const {
1.1614 - return _inverted(key);
1.1615 - }
1.1616 -
1.1617 - /// \brief Size of the map.
1.1618 - ///
1.1619 - /// Returns the size of the map.
1.1620 - unsigned int size() const {
1.1621 - return _inverted.size();
1.1622 - }
1.1623 -
1.1624 - private:
1.1625 - const DescriptorMap& _inverted;
1.1626 - };
1.1627 -
1.1628 - /// \brief Gives back the inverse of the map.
1.1629 - ///
1.1630 - /// Gives back the inverse of the map.
1.1631 - const InverseMap inverse() const {
1.1632 - return InverseMap(*this);
1.1633 - }
1.1634 - };
1.1635 -
1.1636 - /// \brief Returns the source of the given arc.
1.1637 - ///
1.1638 - /// The SourceMap gives back the source Node of the given arc.
1.1639 - /// \see TargetMap
1.1640 - template <typename Digraph>
1.1641 - class SourceMap {
1.1642 - public:
1.1643 -
1.1644 - typedef typename Digraph::Node Value;
1.1645 - typedef typename Digraph::Arc Key;
1.1646 -
1.1647 - /// \brief Constructor
1.1648 - ///
1.1649 - /// Constructor
1.1650 - /// \param _digraph The digraph that the map belongs to.
1.1651 - explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
1.1652 -
1.1653 - /// \brief The subscript operator.
1.1654 - ///
1.1655 - /// The subscript operator.
1.1656 - /// \param arc The arc
1.1657 - /// \return The source of the arc
1.1658 - Value operator[](const Key& arc) const {
1.1659 - return _digraph.source(arc);
1.1660 - }
1.1661 -
1.1662 - private:
1.1663 - const Digraph& _digraph;
1.1664 - };
1.1665 -
1.1666 - /// \brief Returns a \ref SourceMap class.
1.1667 - ///
1.1668 - /// This function just returns an \ref SourceMap class.
1.1669 - /// \relates SourceMap
1.1670 - template <typename Digraph>
1.1671 - inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
1.1672 - return SourceMap<Digraph>(digraph);
1.1673 - }
1.1674 -
1.1675 - /// \brief Returns the target of the given arc.
1.1676 - ///
1.1677 - /// The TargetMap gives back the target Node of the given arc.
1.1678 - /// \see SourceMap
1.1679 - template <typename Digraph>
1.1680 - class TargetMap {
1.1681 - public:
1.1682 -
1.1683 - typedef typename Digraph::Node Value;
1.1684 - typedef typename Digraph::Arc Key;
1.1685 -
1.1686 - /// \brief Constructor
1.1687 - ///
1.1688 - /// Constructor
1.1689 - /// \param _digraph The digraph that the map belongs to.
1.1690 - explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
1.1691 -
1.1692 - /// \brief The subscript operator.
1.1693 - ///
1.1694 - /// The subscript operator.
1.1695 - /// \param e The arc
1.1696 - /// \return The target of the arc
1.1697 - Value operator[](const Key& e) const {
1.1698 - return _digraph.target(e);
1.1699 - }
1.1700 -
1.1701 - private:
1.1702 - const Digraph& _digraph;
1.1703 - };
1.1704 -
1.1705 - /// \brief Returns a \ref TargetMap class.
1.1706 - ///
1.1707 - /// This function just returns a \ref TargetMap class.
1.1708 - /// \relates TargetMap
1.1709 - template <typename Digraph>
1.1710 - inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
1.1711 - return TargetMap<Digraph>(digraph);
1.1712 - }
1.1713 -
1.1714 - /// \brief Returns the "forward" directed arc view of an edge.
1.1715 - ///
1.1716 - /// Returns the "forward" directed arc view of an edge.
1.1717 - /// \see BackwardMap
1.1718 - template <typename Graph>
1.1719 - class ForwardMap {
1.1720 - public:
1.1721 -
1.1722 - typedef typename Graph::Arc Value;
1.1723 - typedef typename Graph::Edge Key;
1.1724 -
1.1725 - /// \brief Constructor
1.1726 - ///
1.1727 - /// Constructor
1.1728 - /// \param _graph The graph that the map belongs to.
1.1729 - explicit ForwardMap(const Graph& graph) : _graph(graph) {}
1.1730 -
1.1731 - /// \brief The subscript operator.
1.1732 - ///
1.1733 - /// The subscript operator.
1.1734 - /// \param key An edge
1.1735 - /// \return The "forward" directed arc view of edge
1.1736 - Value operator[](const Key& key) const {
1.1737 - return _graph.direct(key, true);
1.1738 - }
1.1739 -
1.1740 - private:
1.1741 - const Graph& _graph;
1.1742 - };
1.1743 -
1.1744 - /// \brief Returns a \ref ForwardMap class.
1.1745 - ///
1.1746 - /// This function just returns an \ref ForwardMap class.
1.1747 - /// \relates ForwardMap
1.1748 - template <typename Graph>
1.1749 - inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1.1750 - return ForwardMap<Graph>(graph);
1.1751 - }
1.1752 -
1.1753 - /// \brief Returns the "backward" directed arc view of an edge.
1.1754 - ///
1.1755 - /// Returns the "backward" directed arc view of an edge.
1.1756 - /// \see ForwardMap
1.1757 - template <typename Graph>
1.1758 - class BackwardMap {
1.1759 - public:
1.1760 -
1.1761 - typedef typename Graph::Arc Value;
1.1762 - typedef typename Graph::Edge Key;
1.1763 -
1.1764 - /// \brief Constructor
1.1765 - ///
1.1766 - /// Constructor
1.1767 - /// \param _graph The graph that the map belongs to.
1.1768 - explicit BackwardMap(const Graph& graph) : _graph(graph) {}
1.1769 -
1.1770 - /// \brief The subscript operator.
1.1771 - ///
1.1772 - /// The subscript operator.
1.1773 - /// \param key An edge
1.1774 - /// \return The "backward" directed arc view of edge
1.1775 - Value operator[](const Key& key) const {
1.1776 - return _graph.direct(key, false);
1.1777 - }
1.1778 -
1.1779 - private:
1.1780 - const Graph& _graph;
1.1781 - };
1.1782 -
1.1783 - /// \brief Returns a \ref BackwardMap class
1.1784 -
1.1785 - /// This function just returns a \ref BackwardMap class.
1.1786 - /// \relates BackwardMap
1.1787 - template <typename Graph>
1.1788 - inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1.1789 - return BackwardMap<Graph>(graph);
1.1790 - }
1.1791 -
1.1792 - /// \brief Potential difference map
1.1793 - ///
1.1794 - /// If there is an potential map on the nodes then we
1.1795 - /// can get an arc map as we get the substraction of the
1.1796 - /// values of the target and source.
1.1797 - template <typename Digraph, typename NodeMap>
1.1798 - class PotentialDifferenceMap {
1.1799 - public:
1.1800 - typedef typename Digraph::Arc Key;
1.1801 - typedef typename NodeMap::Value Value;
1.1802 -
1.1803 - /// \brief Constructor
1.1804 - ///
1.1805 - /// Contructor of the map
1.1806 - explicit PotentialDifferenceMap(const Digraph& digraph,
1.1807 - const NodeMap& potential)
1.1808 - : _digraph(digraph), _potential(potential) {}
1.1809 -
1.1810 - /// \brief Const subscription operator
1.1811 - ///
1.1812 - /// Const subscription operator
1.1813 - Value operator[](const Key& arc) const {
1.1814 - return _potential[_digraph.target(arc)] -
1.1815 - _potential[_digraph.source(arc)];
1.1816 - }
1.1817 -
1.1818 - private:
1.1819 - const Digraph& _digraph;
1.1820 - const NodeMap& _potential;
1.1821 - };
1.1822 -
1.1823 - /// \brief Returns a PotentialDifferenceMap.
1.1824 - ///
1.1825 - /// This function just returns a PotentialDifferenceMap.
1.1826 - /// \relates PotentialDifferenceMap
1.1827 - template <typename Digraph, typename NodeMap>
1.1828 - PotentialDifferenceMap<Digraph, NodeMap>
1.1829 - potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
1.1830 - return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
1.1831 - }
1.1832 -
1.1833 - /// \brief Map of the node in-degrees.
1.1834 - ///
1.1835 - /// This map returns the in-degree of a node. Once it is constructed,
1.1836 - /// the degrees are stored in a standard NodeMap, so each query is done
1.1837 - /// in constant time. On the other hand, the values are updated automatically
1.1838 - /// whenever the digraph changes.
1.1839 - ///
1.1840 - /// \warning Besides addNode() and addArc(), a digraph structure may provide
1.1841 - /// alternative ways to modify the digraph. The correct behavior of InDegMap
1.1842 - /// is not guarantied if these additional features are used. For example
1.1843 - /// the functions \ref ListDigraph::changeSource() "changeSource()",
1.1844 - /// \ref ListDigraph::changeTarget() "changeTarget()" and
1.1845 - /// \ref ListDigraph::reverseArc() "reverseArc()"
1.1846 - /// of \ref ListDigraph will \e not update the degree values correctly.
1.1847 - ///
1.1848 - /// \sa OutDegMap
1.1849 -
1.1850 - template <typename _Digraph>
1.1851 - class InDegMap
1.1852 - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.1853 - ::ItemNotifier::ObserverBase {
1.1854 -
1.1855 - public:
1.1856 -
1.1857 - typedef _Digraph Digraph;
1.1858 - typedef int Value;
1.1859 - typedef typename Digraph::Node Key;
1.1860 -
1.1861 - typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1.1862 - ::ItemNotifier::ObserverBase Parent;
1.1863 -
1.1864 - private:
1.1865 -
1.1866 - class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1.1867 - public:
1.1868 -
1.1869 - typedef DefaultMap<Digraph, Key, int> Parent;
1.1870 -
1.1871 - AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1.1872 -
1.1873 - virtual void add(const Key& key) {
1.1874 - Parent::add(key);
1.1875 - Parent::set(key, 0);
1.1876 - }
1.1877 -
1.1878 - virtual void add(const std::vector<Key>& keys) {
1.1879 - Parent::add(keys);
1.1880 - for (int i = 0; i < int(keys.size()); ++i) {
1.1881 - Parent::set(keys[i], 0);
1.1882 - }
1.1883 - }
1.1884 -
1.1885 - virtual void build() {
1.1886 - Parent::build();
1.1887 - Key it;
1.1888 - typename Parent::Notifier* nf = Parent::notifier();
1.1889 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.1890 - Parent::set(it, 0);
1.1891 - }
1.1892 - }
1.1893 - };
1.1894 -
1.1895 - public:
1.1896 -
1.1897 - /// \brief Constructor.
1.1898 - ///
1.1899 - /// Constructor for creating in-degree map.
1.1900 - explicit InDegMap(const Digraph& digraph)
1.1901 - : _digraph(digraph), _deg(digraph) {
1.1902 - Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.1903 -
1.1904 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1905 - _deg[it] = countInArcs(_digraph, it);
1.1906 - }
1.1907 - }
1.1908 -
1.1909 - /// Gives back the in-degree of a Node.
1.1910 - int operator[](const Key& key) const {
1.1911 - return _deg[key];
1.1912 - }
1.1913 -
1.1914 - protected:
1.1915 -
1.1916 - typedef typename Digraph::Arc Arc;
1.1917 -
1.1918 - virtual void add(const Arc& arc) {
1.1919 - ++_deg[_digraph.target(arc)];
1.1920 - }
1.1921 -
1.1922 - virtual void add(const std::vector<Arc>& arcs) {
1.1923 - for (int i = 0; i < int(arcs.size()); ++i) {
1.1924 - ++_deg[_digraph.target(arcs[i])];
1.1925 - }
1.1926 - }
1.1927 -
1.1928 - virtual void erase(const Arc& arc) {
1.1929 - --_deg[_digraph.target(arc)];
1.1930 - }
1.1931 -
1.1932 - virtual void erase(const std::vector<Arc>& arcs) {
1.1933 - for (int i = 0; i < int(arcs.size()); ++i) {
1.1934 - --_deg[_digraph.target(arcs[i])];
1.1935 - }
1.1936 - }
1.1937 -
1.1938 - virtual void build() {
1.1939 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1940 - _deg[it] = countInArcs(_digraph, it);
1.1941 - }
1.1942 - }
1.1943 -
1.1944 - virtual void clear() {
1.1945 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1946 - _deg[it] = 0;
1.1947 - }
1.1948 - }
1.1949 - private:
1.1950 -
1.1951 - const Digraph& _digraph;
1.1952 - AutoNodeMap _deg;
1.1953 - };
1.1954 -
1.1955 - /// \brief Map of the node out-degrees.
1.1956 - ///
1.1957 - /// This map returns the out-degree of a node. Once it is constructed,
1.1958 - /// the degrees are stored in a standard NodeMap, so each query is done
1.1959 - /// in constant time. On the other hand, the values are updated automatically
1.1960 - /// whenever the digraph changes.
1.1961 - ///
1.1962 - /// \warning Besides addNode() and addArc(), a digraph structure may provide
1.1963 - /// alternative ways to modify the digraph. The correct behavior of OutDegMap
1.1964 - /// is not guarantied if these additional features are used. For example
1.1965 - /// the functions \ref ListDigraph::changeSource() "changeSource()",
1.1966 - /// \ref ListDigraph::changeTarget() "changeTarget()" and
1.1967 - /// \ref ListDigraph::reverseArc() "reverseArc()"
1.1968 - /// of \ref ListDigraph will \e not update the degree values correctly.
1.1969 - ///
1.1970 - /// \sa InDegMap
1.1971 -
1.1972 - template <typename _Digraph>
1.1973 - class OutDegMap
1.1974 - : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.1975 - ::ItemNotifier::ObserverBase {
1.1976 -
1.1977 - public:
1.1978 -
1.1979 - typedef _Digraph Digraph;
1.1980 - typedef int Value;
1.1981 - typedef typename Digraph::Node Key;
1.1982 -
1.1983 - typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1.1984 - ::ItemNotifier::ObserverBase Parent;
1.1985 -
1.1986 - private:
1.1987 -
1.1988 - class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1.1989 - public:
1.1990 -
1.1991 - typedef DefaultMap<Digraph, Key, int> Parent;
1.1992 -
1.1993 - AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1.1994 -
1.1995 - virtual void add(const Key& key) {
1.1996 - Parent::add(key);
1.1997 - Parent::set(key, 0);
1.1998 - }
1.1999 - virtual void add(const std::vector<Key>& keys) {
1.2000 - Parent::add(keys);
1.2001 - for (int i = 0; i < int(keys.size()); ++i) {
1.2002 - Parent::set(keys[i], 0);
1.2003 - }
1.2004 - }
1.2005 - virtual void build() {
1.2006 - Parent::build();
1.2007 - Key it;
1.2008 - typename Parent::Notifier* nf = Parent::notifier();
1.2009 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.2010 - Parent::set(it, 0);
1.2011 - }
1.2012 - }
1.2013 - };
1.2014 -
1.2015 - public:
1.2016 -
1.2017 - /// \brief Constructor.
1.2018 - ///
1.2019 - /// Constructor for creating out-degree map.
1.2020 - explicit OutDegMap(const Digraph& digraph)
1.2021 - : _digraph(digraph), _deg(digraph) {
1.2022 - Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.2023 -
1.2024 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2025 - _deg[it] = countOutArcs(_digraph, it);
1.2026 - }
1.2027 - }
1.2028 -
1.2029 - /// Gives back the out-degree of a Node.
1.2030 - int operator[](const Key& key) const {
1.2031 - return _deg[key];
1.2032 - }
1.2033 -
1.2034 - protected:
1.2035 -
1.2036 - typedef typename Digraph::Arc Arc;
1.2037 -
1.2038 - virtual void add(const Arc& arc) {
1.2039 - ++_deg[_digraph.source(arc)];
1.2040 - }
1.2041 -
1.2042 - virtual void add(const std::vector<Arc>& arcs) {
1.2043 - for (int i = 0; i < int(arcs.size()); ++i) {
1.2044 - ++_deg[_digraph.source(arcs[i])];
1.2045 - }
1.2046 - }
1.2047 -
1.2048 - virtual void erase(const Arc& arc) {
1.2049 - --_deg[_digraph.source(arc)];
1.2050 - }
1.2051 -
1.2052 - virtual void erase(const std::vector<Arc>& arcs) {
1.2053 - for (int i = 0; i < int(arcs.size()); ++i) {
1.2054 - --_deg[_digraph.source(arcs[i])];
1.2055 - }
1.2056 - }
1.2057 -
1.2058 - virtual void build() {
1.2059 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2060 - _deg[it] = countOutArcs(_digraph, it);
1.2061 - }
1.2062 - }
1.2063 -
1.2064 - virtual void clear() {
1.2065 - for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2066 - _deg[it] = 0;
1.2067 - }
1.2068 - }
1.2069 - private:
1.2070 -
1.2071 - const Digraph& _digraph;
1.2072 - AutoNodeMap _deg;
1.2073 - };
1.2074 -
1.2075 -
1.2076 - ///Dynamic arc look up between given endpoints.
1.2077 -
1.2078 - ///\ingroup gutils
1.2079 - ///Using this class, you can find an arc in a digraph from a given
1.2080 - ///source to a given target in amortized time <em>O(log d)</em>,
1.2081 - ///where <em>d</em> is the out-degree of the source node.
1.2082 - ///
1.2083 - ///It is possible to find \e all parallel arcs between two nodes with
1.2084 - ///the \c findFirst() and \c findNext() members.
1.2085 - ///
1.2086 - ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
1.2087 - ///digraph is not changed so frequently.
1.2088 - ///
1.2089 - ///This class uses a self-adjusting binary search tree, Sleator's
1.2090 - ///and Tarjan's Splay tree for guarantee the logarithmic amortized
1.2091 - ///time bound for arc lookups. This class also guarantees the
1.2092 - ///optimal time bound in a constant factor for any distribution of
1.2093 - ///queries.
1.2094 - ///
1.2095 - ///\tparam G The type of the underlying digraph.
1.2096 - ///
1.2097 - ///\sa ArcLookUp
1.2098 - ///\sa AllArcLookUp
1.2099 - template<class G>
1.2100 - class DynArcLookUp
1.2101 - : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
1.2102 - {
1.2103 - public:
1.2104 - typedef typename ItemSetTraits<G, typename G::Arc>
1.2105 - ::ItemNotifier::ObserverBase Parent;
1.2106 -
1.2107 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.2108 - typedef G Digraph;
1.2109 -
1.2110 - protected:
1.2111 -
1.2112 - class AutoNodeMap : public DefaultMap<G, Node, Arc> {
1.2113 - public:
1.2114 -
1.2115 - typedef DefaultMap<G, Node, Arc> Parent;
1.2116 -
1.2117 - AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
1.2118 -
1.2119 - virtual void add(const Node& node) {
1.2120 - Parent::add(node);
1.2121 - Parent::set(node, INVALID);
1.2122 - }
1.2123 -
1.2124 - virtual void add(const std::vector<Node>& nodes) {
1.2125 - Parent::add(nodes);
1.2126 - for (int i = 0; i < int(nodes.size()); ++i) {
1.2127 - Parent::set(nodes[i], INVALID);
1.2128 - }
1.2129 - }
1.2130 -
1.2131 - virtual void build() {
1.2132 - Parent::build();
1.2133 - Node it;
1.2134 - typename Parent::Notifier* nf = Parent::notifier();
1.2135 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.2136 - Parent::set(it, INVALID);
1.2137 - }
1.2138 - }
1.2139 - };
1.2140 -
1.2141 - const Digraph &_g;
1.2142 - AutoNodeMap _head;
1.2143 - typename Digraph::template ArcMap<Arc> _parent;
1.2144 - typename Digraph::template ArcMap<Arc> _left;
1.2145 - typename Digraph::template ArcMap<Arc> _right;
1.2146 -
1.2147 - class ArcLess {
1.2148 - const Digraph &g;
1.2149 - public:
1.2150 - ArcLess(const Digraph &_g) : g(_g) {}
1.2151 - bool operator()(Arc a,Arc b) const
1.2152 - {
1.2153 - return g.target(a)<g.target(b);
1.2154 - }
1.2155 - };
1.2156 -
1.2157 - public:
1.2158 -
1.2159 - ///Constructor
1.2160 -
1.2161 - ///Constructor.
1.2162 - ///
1.2163 - ///It builds up the search database.
1.2164 - DynArcLookUp(const Digraph &g)
1.2165 - : _g(g),_head(g),_parent(g),_left(g),_right(g)
1.2166 - {
1.2167 - Parent::attach(_g.notifier(typename Digraph::Arc()));
1.2168 - refresh();
1.2169 - }
1.2170 -
1.2171 - protected:
1.2172 -
1.2173 - virtual void add(const Arc& arc) {
1.2174 - insert(arc);
1.2175 - }
1.2176 -
1.2177 - virtual void add(const std::vector<Arc>& arcs) {
1.2178 - for (int i = 0; i < int(arcs.size()); ++i) {
1.2179 - insert(arcs[i]);
1.2180 - }
1.2181 - }
1.2182 -
1.2183 - virtual void erase(const Arc& arc) {
1.2184 - remove(arc);
1.2185 - }
1.2186 -
1.2187 - virtual void erase(const std::vector<Arc>& arcs) {
1.2188 - for (int i = 0; i < int(arcs.size()); ++i) {
1.2189 - remove(arcs[i]);
1.2190 - }
1.2191 - }
1.2192 -
1.2193 - virtual void build() {
1.2194 - refresh();
1.2195 - }
1.2196 -
1.2197 - virtual void clear() {
1.2198 - for(NodeIt n(_g);n!=INVALID;++n) {
1.2199 - _head.set(n, INVALID);
1.2200 - }
1.2201 - }
1.2202 -
1.2203 - void insert(Arc arc) {
1.2204 - Node s = _g.source(arc);
1.2205 - Node t = _g.target(arc);
1.2206 - _left.set(arc, INVALID);
1.2207 - _right.set(arc, INVALID);
1.2208 -
1.2209 - Arc e = _head[s];
1.2210 - if (e == INVALID) {
1.2211 - _head.set(s, arc);
1.2212 - _parent.set(arc, INVALID);
1.2213 - return;
1.2214 - }
1.2215 - while (true) {
1.2216 - if (t < _g.target(e)) {
1.2217 - if (_left[e] == INVALID) {
1.2218 - _left.set(e, arc);
1.2219 - _parent.set(arc, e);
1.2220 - splay(arc);
1.2221 - return;
1.2222 - } else {
1.2223 - e = _left[e];
1.2224 - }
1.2225 - } else {
1.2226 - if (_right[e] == INVALID) {
1.2227 - _right.set(e, arc);
1.2228 - _parent.set(arc, e);
1.2229 - splay(arc);
1.2230 - return;
1.2231 - } else {
1.2232 - e = _right[e];
1.2233 - }
1.2234 - }
1.2235 - }
1.2236 - }
1.2237 -
1.2238 - void remove(Arc arc) {
1.2239 - if (_left[arc] == INVALID) {
1.2240 - if (_right[arc] != INVALID) {
1.2241 - _parent.set(_right[arc], _parent[arc]);
1.2242 - }
1.2243 - if (_parent[arc] != INVALID) {
1.2244 - if (_left[_parent[arc]] == arc) {
1.2245 - _left.set(_parent[arc], _right[arc]);
1.2246 - } else {
1.2247 - _right.set(_parent[arc], _right[arc]);
1.2248 - }
1.2249 - } else {
1.2250 - _head.set(_g.source(arc), _right[arc]);
1.2251 - }
1.2252 - } else if (_right[arc] == INVALID) {
1.2253 - _parent.set(_left[arc], _parent[arc]);
1.2254 - if (_parent[arc] != INVALID) {
1.2255 - if (_left[_parent[arc]] == arc) {
1.2256 - _left.set(_parent[arc], _left[arc]);
1.2257 - } else {
1.2258 - _right.set(_parent[arc], _left[arc]);
1.2259 - }
1.2260 - } else {
1.2261 - _head.set(_g.source(arc), _left[arc]);
1.2262 - }
1.2263 - } else {
1.2264 - Arc e = _left[arc];
1.2265 - if (_right[e] != INVALID) {
1.2266 - e = _right[e];
1.2267 - while (_right[e] != INVALID) {
1.2268 - e = _right[e];
1.2269 - }
1.2270 - Arc s = _parent[e];
1.2271 - _right.set(_parent[e], _left[e]);
1.2272 - if (_left[e] != INVALID) {
1.2273 - _parent.set(_left[e], _parent[e]);
1.2274 - }
1.2275 -
1.2276 - _left.set(e, _left[arc]);
1.2277 - _parent.set(_left[arc], e);
1.2278 - _right.set(e, _right[arc]);
1.2279 - _parent.set(_right[arc], e);
1.2280 -
1.2281 - _parent.set(e, _parent[arc]);
1.2282 - if (_parent[arc] != INVALID) {
1.2283 - if (_left[_parent[arc]] == arc) {
1.2284 - _left.set(_parent[arc], e);
1.2285 - } else {
1.2286 - _right.set(_parent[arc], e);
1.2287 - }
1.2288 - }
1.2289 - splay(s);
1.2290 - } else {
1.2291 - _right.set(e, _right[arc]);
1.2292 - _parent.set(_right[arc], e);
1.2293 -
1.2294 - if (_parent[arc] != INVALID) {
1.2295 - if (_left[_parent[arc]] == arc) {
1.2296 - _left.set(_parent[arc], e);
1.2297 - } else {
1.2298 - _right.set(_parent[arc], e);
1.2299 - }
1.2300 - } else {
1.2301 - _head.set(_g.source(arc), e);
1.2302 - }
1.2303 - }
1.2304 - }
1.2305 - }
1.2306 -
1.2307 - Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.2308 - {
1.2309 - int m=(a+b)/2;
1.2310 - Arc me=v[m];
1.2311 - if (a < m) {
1.2312 - Arc left = refreshRec(v,a,m-1);
1.2313 - _left.set(me, left);
1.2314 - _parent.set(left, me);
1.2315 - } else {
1.2316 - _left.set(me, INVALID);
1.2317 - }
1.2318 - if (m < b) {
1.2319 - Arc right = refreshRec(v,m+1,b);
1.2320 - _right.set(me, right);
1.2321 - _parent.set(right, me);
1.2322 - } else {
1.2323 - _right.set(me, INVALID);
1.2324 - }
1.2325 - return me;
1.2326 - }
1.2327 -
1.2328 - void refresh() {
1.2329 - for(NodeIt n(_g);n!=INVALID;++n) {
1.2330 - std::vector<Arc> v;
1.2331 - for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.2332 - if(v.size()) {
1.2333 - std::sort(v.begin(),v.end(),ArcLess(_g));
1.2334 - Arc head = refreshRec(v,0,v.size()-1);
1.2335 - _head.set(n, head);
1.2336 - _parent.set(head, INVALID);
1.2337 - }
1.2338 - else _head.set(n, INVALID);
1.2339 - }
1.2340 - }
1.2341 -
1.2342 - void zig(Arc v) {
1.2343 - Arc w = _parent[v];
1.2344 - _parent.set(v, _parent[w]);
1.2345 - _parent.set(w, v);
1.2346 - _left.set(w, _right[v]);
1.2347 - _right.set(v, w);
1.2348 - if (_parent[v] != INVALID) {
1.2349 - if (_right[_parent[v]] == w) {
1.2350 - _right.set(_parent[v], v);
1.2351 - } else {
1.2352 - _left.set(_parent[v], v);
1.2353 - }
1.2354 - }
1.2355 - if (_left[w] != INVALID){
1.2356 - _parent.set(_left[w], w);
1.2357 - }
1.2358 - }
1.2359 -
1.2360 - void zag(Arc v) {
1.2361 - Arc w = _parent[v];
1.2362 - _parent.set(v, _parent[w]);
1.2363 - _parent.set(w, v);
1.2364 - _right.set(w, _left[v]);
1.2365 - _left.set(v, w);
1.2366 - if (_parent[v] != INVALID){
1.2367 - if (_left[_parent[v]] == w) {
1.2368 - _left.set(_parent[v], v);
1.2369 - } else {
1.2370 - _right.set(_parent[v], v);
1.2371 - }
1.2372 - }
1.2373 - if (_right[w] != INVALID){
1.2374 - _parent.set(_right[w], w);
1.2375 - }
1.2376 - }
1.2377 -
1.2378 - void splay(Arc v) {
1.2379 - while (_parent[v] != INVALID) {
1.2380 - if (v == _left[_parent[v]]) {
1.2381 - if (_parent[_parent[v]] == INVALID) {
1.2382 - zig(v);
1.2383 - } else {
1.2384 - if (_parent[v] == _left[_parent[_parent[v]]]) {
1.2385 - zig(_parent[v]);
1.2386 - zig(v);
1.2387 - } else {
1.2388 - zig(v);
1.2389 - zag(v);
1.2390 - }
1.2391 - }
1.2392 - } else {
1.2393 - if (_parent[_parent[v]] == INVALID) {
1.2394 - zag(v);
1.2395 - } else {
1.2396 - if (_parent[v] == _left[_parent[_parent[v]]]) {
1.2397 - zag(v);
1.2398 - zig(v);
1.2399 - } else {
1.2400 - zag(_parent[v]);
1.2401 - zag(v);
1.2402 - }
1.2403 - }
1.2404 - }
1.2405 - }
1.2406 - _head[_g.source(v)] = v;
1.2407 - }
1.2408 -
1.2409 -
1.2410 - public:
1.2411 -
1.2412 - ///Find an arc between two nodes.
1.2413 -
1.2414 - ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.2415 - /// <em>d</em> is the number of outgoing arcs of \c s.
1.2416 - ///\param s The source node
1.2417 - ///\param t The target node
1.2418 - ///\return An arc from \c s to \c t if there exists,
1.2419 - ///\ref INVALID otherwise.
1.2420 - Arc operator()(Node s, Node t) const
1.2421 - {
1.2422 - Arc a = _head[s];
1.2423 - while (true) {
1.2424 - if (_g.target(a) == t) {
1.2425 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2426 - return a;
1.2427 - } else if (t < _g.target(a)) {
1.2428 - if (_left[a] == INVALID) {
1.2429 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2430 - return INVALID;
1.2431 - } else {
1.2432 - a = _left[a];
1.2433 - }
1.2434 - } else {
1.2435 - if (_right[a] == INVALID) {
1.2436 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2437 - return INVALID;
1.2438 - } else {
1.2439 - a = _right[a];
1.2440 - }
1.2441 - }
1.2442 - }
1.2443 - }
1.2444 -
1.2445 - ///Find the first arc between two nodes.
1.2446 -
1.2447 - ///Find the first arc between two nodes in time
1.2448 - /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.2449 - /// outgoing arcs of \c s.
1.2450 - ///\param s The source node
1.2451 - ///\param t The target node
1.2452 - ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.2453 - /// otherwise.
1.2454 - Arc findFirst(Node s, Node t) const
1.2455 - {
1.2456 - Arc a = _head[s];
1.2457 - Arc r = INVALID;
1.2458 - while (true) {
1.2459 - if (_g.target(a) < t) {
1.2460 - if (_right[a] == INVALID) {
1.2461 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2462 - return r;
1.2463 - } else {
1.2464 - a = _right[a];
1.2465 - }
1.2466 - } else {
1.2467 - if (_g.target(a) == t) {
1.2468 - r = a;
1.2469 - }
1.2470 - if (_left[a] == INVALID) {
1.2471 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2472 - return r;
1.2473 - } else {
1.2474 - a = _left[a];
1.2475 - }
1.2476 - }
1.2477 - }
1.2478 - }
1.2479 -
1.2480 - ///Find the next arc between two nodes.
1.2481 -
1.2482 - ///Find the next arc between two nodes in time
1.2483 - /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.2484 - /// outgoing arcs of \c s.
1.2485 - ///\param s The source node
1.2486 - ///\param t The target node
1.2487 - ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.2488 - /// otherwise.
1.2489 -
1.2490 - ///\note If \c e is not the result of the previous \c findFirst()
1.2491 - ///operation then the amorized time bound can not be guaranteed.
1.2492 -#ifdef DOXYGEN
1.2493 - Arc findNext(Node s, Node t, Arc a) const
1.2494 -#else
1.2495 - Arc findNext(Node, Node t, Arc a) const
1.2496 -#endif
1.2497 - {
1.2498 - if (_right[a] != INVALID) {
1.2499 - a = _right[a];
1.2500 - while (_left[a] != INVALID) {
1.2501 - a = _left[a];
1.2502 - }
1.2503 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2504 - } else {
1.2505 - while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1.2506 - a = _parent[a];
1.2507 - }
1.2508 - if (_parent[a] == INVALID) {
1.2509 - return INVALID;
1.2510 - } else {
1.2511 - a = _parent[a];
1.2512 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2513 - }
1.2514 - }
1.2515 - if (_g.target(a) == t) return a;
1.2516 - else return INVALID;
1.2517 - }
1.2518 -
1.2519 - };
1.2520 -
1.2521 - ///Fast arc look up between given endpoints.
1.2522 -
1.2523 - ///\ingroup gutils
1.2524 - ///Using this class, you can find an arc in a digraph from a given
1.2525 - ///source to a given target in time <em>O(log d)</em>,
1.2526 - ///where <em>d</em> is the out-degree of the source node.
1.2527 - ///
1.2528 - ///It is not possible to find \e all parallel arcs between two nodes.
1.2529 - ///Use \ref AllArcLookUp for this purpose.
1.2530 - ///
1.2531 - ///\warning This class is static, so you should refresh() (or at least
1.2532 - ///refresh(Node)) this data structure
1.2533 - ///whenever the digraph changes. This is a time consuming (superlinearly
1.2534 - ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
1.2535 - ///
1.2536 - ///\tparam G The type of the underlying digraph.
1.2537 - ///
1.2538 - ///\sa DynArcLookUp
1.2539 - ///\sa AllArcLookUp
1.2540 - template<class G>
1.2541 - class ArcLookUp
1.2542 - {
1.2543 - public:
1.2544 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.2545 - typedef G Digraph;
1.2546 -
1.2547 - protected:
1.2548 - const Digraph &_g;
1.2549 - typename Digraph::template NodeMap<Arc> _head;
1.2550 - typename Digraph::template ArcMap<Arc> _left;
1.2551 - typename Digraph::template ArcMap<Arc> _right;
1.2552 -
1.2553 - class ArcLess {
1.2554 - const Digraph &g;
1.2555 - public:
1.2556 - ArcLess(const Digraph &_g) : g(_g) {}
1.2557 - bool operator()(Arc a,Arc b) const
1.2558 - {
1.2559 - return g.target(a)<g.target(b);
1.2560 - }
1.2561 - };
1.2562 -
1.2563 - public:
1.2564 -
1.2565 - ///Constructor
1.2566 -
1.2567 - ///Constructor.
1.2568 - ///
1.2569 - ///It builds up the search database, which remains valid until the digraph
1.2570 - ///changes.
1.2571 - ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1.2572 -
1.2573 - private:
1.2574 - Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.2575 - {
1.2576 - int m=(a+b)/2;
1.2577 - Arc me=v[m];
1.2578 - _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
1.2579 - _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
1.2580 - return me;
1.2581 - }
1.2582 - public:
1.2583 - ///Refresh the data structure at a node.
1.2584 -
1.2585 - ///Build up the search database of node \c n.
1.2586 - ///
1.2587 - ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.2588 - ///the number of the outgoing arcs of \c n.
1.2589 - void refresh(Node n)
1.2590 - {
1.2591 - std::vector<Arc> v;
1.2592 - for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.2593 - if(v.size()) {
1.2594 - std::sort(v.begin(),v.end(),ArcLess(_g));
1.2595 - _head[n]=refreshRec(v,0,v.size()-1);
1.2596 - }
1.2597 - else _head[n]=INVALID;
1.2598 - }
1.2599 - ///Refresh the full data structure.
1.2600 -
1.2601 - ///Build up the full search database. In fact, it simply calls
1.2602 - ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.2603 - ///
1.2604 - ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.2605 - ///the number of the arcs of \c n and <em>D</em> is the maximum
1.2606 - ///out-degree of the digraph.
1.2607 -
1.2608 - void refresh()
1.2609 - {
1.2610 - for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.2611 - }
1.2612 -
1.2613 - ///Find an arc between two nodes.
1.2614 -
1.2615 - ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.2616 - /// <em>d</em> is the number of outgoing arcs of \c s.
1.2617 - ///\param s The source node
1.2618 - ///\param t The target node
1.2619 - ///\return An arc from \c s to \c t if there exists,
1.2620 - ///\ref INVALID otherwise.
1.2621 - ///
1.2622 - ///\warning If you change the digraph, refresh() must be called before using
1.2623 - ///this operator. If you change the outgoing arcs of
1.2624 - ///a single node \c n, then
1.2625 - ///\ref refresh(Node) "refresh(n)" is enough.
1.2626 - ///
1.2627 - Arc operator()(Node s, Node t) const
1.2628 - {
1.2629 - Arc e;
1.2630 - for(e=_head[s];
1.2631 - e!=INVALID&&_g.target(e)!=t;
1.2632 - e = t < _g.target(e)?_left[e]:_right[e]) ;
1.2633 - return e;
1.2634 - }
1.2635 -
1.2636 - };
1.2637 -
1.2638 - ///Fast look up of all arcs between given endpoints.
1.2639 -
1.2640 - ///\ingroup gutils
1.2641 - ///This class is the same as \ref ArcLookUp, with the addition
1.2642 - ///that it makes it possible to find all arcs between given endpoints.
1.2643 - ///
1.2644 - ///\warning This class is static, so you should refresh() (or at least
1.2645 - ///refresh(Node)) this data structure
1.2646 - ///whenever the digraph changes. This is a time consuming (superlinearly
1.2647 - ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
1.2648 - ///
1.2649 - ///\tparam G The type of the underlying digraph.
1.2650 - ///
1.2651 - ///\sa DynArcLookUp
1.2652 - ///\sa ArcLookUp
1.2653 - template<class G>
1.2654 - class AllArcLookUp : public ArcLookUp<G>
1.2655 - {
1.2656 - using ArcLookUp<G>::_g;
1.2657 - using ArcLookUp<G>::_right;
1.2658 - using ArcLookUp<G>::_left;
1.2659 - using ArcLookUp<G>::_head;
1.2660 -
1.2661 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.2662 - typedef G Digraph;
1.2663 -
1.2664 - typename Digraph::template ArcMap<Arc> _next;
1.2665 -
1.2666 - Arc refreshNext(Arc head,Arc next=INVALID)
1.2667 - {
1.2668 - if(head==INVALID) return next;
1.2669 - else {
1.2670 - next=refreshNext(_right[head],next);
1.2671 -// _next[head]=next;
1.2672 - _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1.2673 - ? next : INVALID;
1.2674 - return refreshNext(_left[head],head);
1.2675 - }
1.2676 - }
1.2677 -
1.2678 - void refreshNext()
1.2679 - {
1.2680 - for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1.2681 - }
1.2682 -
1.2683 - public:
1.2684 - ///Constructor
1.2685 -
1.2686 - ///Constructor.
1.2687 - ///
1.2688 - ///It builds up the search database, which remains valid until the digraph
1.2689 - ///changes.
1.2690 - AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
1.2691 -
1.2692 - ///Refresh the data structure at a node.
1.2693 -
1.2694 - ///Build up the search database of node \c n.
1.2695 - ///
1.2696 - ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.2697 - ///the number of the outgoing arcs of \c n.
1.2698 -
1.2699 - void refresh(Node n)
1.2700 - {
1.2701 - ArcLookUp<G>::refresh(n);
1.2702 - refreshNext(_head[n]);
1.2703 - }
1.2704 -
1.2705 - ///Refresh the full data structure.
1.2706 -
1.2707 - ///Build up the full search database. In fact, it simply calls
1.2708 - ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.2709 - ///
1.2710 - ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.2711 - ///the number of the arcs of \c n and <em>D</em> is the maximum
1.2712 - ///out-degree of the digraph.
1.2713 -
1.2714 - void refresh()
1.2715 - {
1.2716 - for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1.2717 - }
1.2718 -
1.2719 - ///Find an arc between two nodes.
1.2720 -
1.2721 - ///Find an arc between two nodes.
1.2722 - ///\param s The source node
1.2723 - ///\param t The target node
1.2724 - ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1.2725 - ///not given, the operator finds the first appropriate arc.
1.2726 - ///\return An arc from \c s to \c t after \c prev or
1.2727 - ///\ref INVALID if there is no more.
1.2728 - ///
1.2729 - ///For example, you can count the number of arcs from \c u to \c v in the
1.2730 - ///following way.
1.2731 - ///\code
1.2732 - ///AllArcLookUp<ListDigraph> ae(g);
1.2733 - ///...
1.2734 - ///int n=0;
1.2735 - ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
1.2736 - ///\endcode
1.2737 - ///
1.2738 - ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
1.2739 - /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
1.2740 - ///consecutive arcs are found in constant time.
1.2741 - ///
1.2742 - ///\warning If you change the digraph, refresh() must be called before using
1.2743 - ///this operator. If you change the outgoing arcs of
1.2744 - ///a single node \c n, then
1.2745 - ///\ref refresh(Node) "refresh(n)" is enough.
1.2746 - ///
1.2747 -#ifdef DOXYGEN
1.2748 - Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1.2749 -#else
1.2750 - using ArcLookUp<G>::operator() ;
1.2751 - Arc operator()(Node s, Node t, Arc prev) const
1.2752 - {
1.2753 - return prev==INVALID?(*this)(s,t):_next[prev];
1.2754 - }
1.2755 -#endif
1.2756 -
1.2757 - };
1.2758 -
1.2759 - /// @}
1.2760 -
1.2761 -} //END OF NAMESPACE LEMON
1.2762 -
1.2763 -#endif