COIN-OR::LEMON - Graph Library

source: lemon/lemon/graph_utils.h @ 212:1ae84dea7d09

Last change on this file since 212:1ae84dea7d09 was 212:1ae84dea7d09, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Fix the incorrect tab replacements of unify-sources.sh

File size: 81.7 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[100]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[100]4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_GRAPH_UTILS_H
20#define LEMON_GRAPH_UTILS_H
21
22#include <iterator>
23#include <vector>
24#include <map>
25#include <cmath>
26#include <algorithm>
27
28#include <lemon/bits/invalid.h>
29#include <lemon/bits/utility.h>
30#include <lemon/maps.h>
31#include <lemon/bits/traits.h>
32
33#include <lemon/bits/alteration_notifier.h>
34#include <lemon/bits/default_map.h>
35
36///\ingroup gutils
37///\file
[139]38///\brief Graph utilities.
[100]39
40namespace lemon {
41
42  /// \addtogroup gutils
43  /// @{
44
45  ///Creates convenience typedefs for the digraph types and iterators
46
47  ///This \c \#define creates convenience typedefs for the following types
48  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
[209]49  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
[148]50  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
51  ///
52  ///\note If the graph type is a dependent type, ie. the graph type depend
53  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
54  ///macro.
[212]55#define DIGRAPH_TYPEDEFS(Digraph)                                       \
56  typedef Digraph::Node Node;                                           \
57  typedef Digraph::NodeIt NodeIt;                                       \
58  typedef Digraph::Arc Arc;                                             \
59  typedef Digraph::ArcIt ArcIt;                                         \
60  typedef Digraph::InArcIt InArcIt;                                     \
61  typedef Digraph::OutArcIt OutArcIt;                                   \
62  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
63  typedef Digraph::NodeMap<int> IntNodeMap;                             \
64  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
65  typedef Digraph::ArcMap<bool> BoolArcMap;                             \
66  typedef Digraph::ArcMap<int> IntArcMap;                               \
[148]67  typedef Digraph::ArcMap<double> DoubleArcMap
[140]68
[148]69  ///Creates convenience typedefs for the digraph types and iterators
[100]70
[148]71  ///\see DIGRAPH_TYPEDEFS
72  ///
73  ///\note Use this macro, if the graph type is a dependent type,
74  ///ie. the graph type depend on a template parameter.
[212]75#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
76  typedef typename Digraph::Node Node;                                  \
77  typedef typename Digraph::NodeIt NodeIt;                              \
78  typedef typename Digraph::Arc Arc;                                    \
[209]79  typedef typename Digraph::ArcIt ArcIt;                                \
[212]80  typedef typename Digraph::InArcIt InArcIt;                            \
81  typedef typename Digraph::OutArcIt OutArcIt;                          \
82  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
83  typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
84  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
85  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
86  typedef typename Digraph::template ArcMap<int> IntArcMap;             \
[148]87  typedef typename Digraph::template ArcMap<double> DoubleArcMap
[209]88
[100]89  ///Creates convenience typedefs for the graph types and iterators
90
[139]91  ///This \c \#define creates the same convenience typedefs as defined
92  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
93  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
94  ///\c DoubleEdgeMap.
[148]95  ///
96  ///\note If the graph type is a dependent type, ie. the graph type depend
97  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
98  ///macro.
[212]99#define GRAPH_TYPEDEFS(Graph)                                           \
100  DIGRAPH_TYPEDEFS(Graph);                                              \
101  typedef Graph::Edge Edge;                                             \
102  typedef Graph::EdgeIt EdgeIt;                                         \
103  typedef Graph::IncEdgeIt IncEdgeIt;                                   \
104  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
105  typedef Graph::EdgeMap<int> IntEdgeMap;                               \
[148]106  typedef Graph::EdgeMap<double> DoubleEdgeMap
[140]107
[148]108  ///Creates convenience typedefs for the graph types and iterators
109
110  ///\see GRAPH_TYPEDEFS
111  ///
112  ///\note Use this macro, if the graph type is a dependent type,
113  ///ie. the graph type depend on a template parameter.
[212]114#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
115  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
116  typedef typename Graph::Edge Edge;                                    \
[209]117  typedef typename Graph::EdgeIt EdgeIt;                                \
[212]118  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
119  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
120  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
[148]121  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
[139]122
123  /// \brief Function to count the items in the graph.
[100]124  ///
[139]125  /// This function counts the items (nodes, arcs etc) in the graph.
[100]126  /// The complexity of the function is O(n) because
127  /// it iterates on all of the items.
[139]128  template <typename Graph, typename Item>
129  inline int countItems(const Graph& g) {
130    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
[100]131    int num = 0;
132    for (ItemIt it(g); it != INVALID; ++it) {
133      ++num;
134    }
135    return num;
136  }
137
138  // Node counting:
139
[139]140  namespace _graph_utils_bits {
[209]141
[139]142    template <typename Graph, typename Enable = void>
[100]143    struct CountNodesSelector {
[139]144      static int count(const Graph &g) {
145        return countItems<Graph, typename Graph::Node>(g);
[100]146      }
147    };
148
[139]149    template <typename Graph>
[100]150    struct CountNodesSelector<
[209]151      Graph, typename
152      enable_if<typename Graph::NodeNumTag, void>::type>
[100]153    {
[139]154      static int count(const Graph &g) {
[100]155        return g.nodeNum();
156      }
[209]157    };
[100]158  }
159
[139]160  /// \brief Function to count the nodes in the graph.
[100]161  ///
[139]162  /// This function counts the nodes in the graph.
[100]163  /// The complexity of the function is O(n) but for some
[139]164  /// graph structures it is specialized to run in O(1).
[100]165  ///
[209]166  /// If the graph contains a \e nodeNum() member function and a
[100]167  /// \e NodeNumTag tag then this function calls directly the member
168  /// function to query the cardinality of the node set.
[139]169  template <typename Graph>
170  inline int countNodes(const Graph& g) {
171    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
[100]172  }
173
[139]174  // Arc counting:
175
176  namespace _graph_utils_bits {
[209]177
[139]178    template <typename Graph, typename Enable = void>
179    struct CountArcsSelector {
180      static int count(const Graph &g) {
181        return countItems<Graph, typename Graph::Arc>(g);
[100]182      }
183    };
184
[139]185    template <typename Graph>
186    struct CountArcsSelector<
[209]187      Graph,
188      typename enable_if<typename Graph::ArcNumTag, void>::type>
[100]189    {
[139]190      static int count(const Graph &g) {
[100]191        return g.arcNum();
192      }
[209]193    };
[100]194  }
195
[139]196  /// \brief Function to count the arcs in the graph.
[100]197  ///
[139]198  /// This function counts the arcs in the graph.
[100]199  /// The complexity of the function is O(e) but for some
[139]200  /// graph structures it is specialized to run in O(1).
[100]201  ///
[209]202  /// If the graph contains a \e arcNum() member function and a
[139]203  /// \e EdgeNumTag tag then this function calls directly the member
[100]204  /// function to query the cardinality of the arc set.
[139]205  template <typename Graph>
206  inline int countArcs(const Graph& g) {
207    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
[100]208  }
209
[139]210  // Edge counting:
211  namespace _graph_utils_bits {
[209]212
[139]213    template <typename Graph, typename Enable = void>
[100]214    struct CountEdgesSelector {
[139]215      static int count(const Graph &g) {
216        return countItems<Graph, typename Graph::Edge>(g);
[100]217      }
218    };
219
[139]220    template <typename Graph>
[100]221    struct CountEdgesSelector<
[209]222      Graph,
223      typename enable_if<typename Graph::EdgeNumTag, void>::type>
[100]224    {
[139]225      static int count(const Graph &g) {
[100]226        return g.edgeNum();
227      }
[209]228    };
[100]229  }
230
[139]231  /// \brief Function to count the edges in the graph.
[100]232  ///
[139]233  /// This function counts the edges in the graph.
234  /// The complexity of the function is O(m) but for some
235  /// graph structures it is specialized to run in O(1).
[100]236  ///
[209]237  /// If the graph contains a \e edgeNum() member function and a
[139]238  /// \e EdgeNumTag tag then this function calls directly the member
[100]239  /// function to query the cardinality of the edge set.
[139]240  template <typename Graph>
241  inline int countEdges(const Graph& g) {
242    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
[100]243
244  }
245
246
[139]247  template <typename Graph, typename DegIt>
248  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
[100]249    int num = 0;
250    for (DegIt it(_g, _n); it != INVALID; ++it) {
251      ++num;
252    }
253    return num;
254  }
255
256  /// \brief Function to count the number of the out-arcs from node \c n.
257  ///
258  /// This function counts the number of the out-arcs from node \c n
[209]259  /// in the graph.
[139]260  template <typename Graph>
261  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
262    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
[100]263  }
264
265  /// \brief Function to count the number of the in-arcs to node \c n.
266  ///
267  /// This function counts the number of the in-arcs to node \c n
[209]268  /// in the graph.
[139]269  template <typename Graph>
270  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
271    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
[100]272  }
273
[139]274  /// \brief Function to count the number of the inc-edges to node \c n.
[100]275  ///
[139]276  /// This function counts the number of the inc-edges to node \c n
[209]277  /// in the graph.
[139]278  template <typename Graph>
279  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
280    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
[100]281  }
282
[139]283  namespace _graph_utils_bits {
[209]284
[139]285    template <typename Graph, typename Enable = void>
[100]286    struct FindArcSelector {
[139]287      typedef typename Graph::Node Node;
288      typedef typename Graph::Arc Arc;
289      static Arc find(const Graph &g, Node u, Node v, Arc e) {
[100]290        if (e == INVALID) {
291          g.firstOut(e, u);
292        } else {
293          g.nextOut(e);
294        }
295        while (e != INVALID && g.target(e) != v) {
296          g.nextOut(e);
297        }
298        return e;
299      }
300    };
301
[139]302    template <typename Graph>
[100]303    struct FindArcSelector<
[209]304      Graph,
305      typename enable_if<typename Graph::FindEdgeTag, void>::type>
[100]306    {
[139]307      typedef typename Graph::Node Node;
308      typedef typename Graph::Arc Arc;
309      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
[100]310        return g.findArc(u, v, prev);
311      }
[209]312    };
[100]313  }
314
[139]315  /// \brief Finds an arc between two nodes of a graph.
[100]316  ///
[139]317  /// Finds an arc from node \c u to node \c v in graph \c g.
[100]318  ///
319  /// If \c prev is \ref INVALID (this is the default value), then
320  /// it finds the first arc from \c u to \c v. Otherwise it looks for
321  /// the next arc from \c u to \c v after \c prev.
322  /// \return The found arc or \ref INVALID if there is no such an arc.
323  ///
324  /// Thus you can iterate through each arc from \c u to \c v as it follows.
325  ///\code
326  /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
327  ///   ...
328  /// }
329  ///\endcode
330  ///
331  ///\sa ArcLookUp
332  ///\sa AllArcLookUp
333  ///\sa DynArcLookUp
334  ///\sa ConArcIt
[139]335  template <typename Graph>
[209]336  inline typename Graph::Arc
[139]337  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
338           typename Graph::Arc prev = INVALID) {
339    return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
[100]340  }
341
342  /// \brief Iterator for iterating on arcs connected the same nodes.
343  ///
[209]344  /// Iterator for iterating on arcs connected the same nodes. It is
[100]345  /// higher level interface for the findArc() function. You can
346  /// use it the following way:
347  ///\code
[139]348  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
[100]349  ///   ...
350  /// }
351  ///\endcode
[209]352  ///
[100]353  ///\sa findArc()
354  ///\sa ArcLookUp
355  ///\sa AllArcLookUp
356  ///\sa DynArcLookUp
[139]357  template <typename _Graph>
358  class ConArcIt : public _Graph::Arc {
[100]359  public:
360
[139]361    typedef _Graph Graph;
362    typedef typename Graph::Arc Parent;
[100]363
[139]364    typedef typename Graph::Arc Arc;
365    typedef typename Graph::Node Node;
[100]366
367    /// \brief Constructor.
368    ///
369    /// Construct a new ConArcIt iterating on the arcs which
370    /// connects the \c u and \c v node.
[139]371    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
372      Parent::operator=(findArc(_graph, u, v));
[100]373    }
374
375    /// \brief Constructor.
376    ///
[209]377    /// Construct a new ConArcIt which continues the iterating from
[100]378    /// the \c e arc.
[139]379    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
[209]380
[100]381    /// \brief Increment operator.
382    ///
383    /// It increments the iterator and gives back the next arc.
384    ConArcIt& operator++() {
[209]385      Parent::operator=(findArc(_graph, _graph.source(*this),
386                                _graph.target(*this), *this));
[100]387      return *this;
388    }
389  private:
[139]390    const Graph& _graph;
[100]391  };
392
[139]393  namespace _graph_utils_bits {
[209]394
[139]395    template <typename Graph, typename Enable = void>
[100]396    struct FindEdgeSelector {
[139]397      typedef typename Graph::Node Node;
398      typedef typename Graph::Edge Edge;
399      static Edge find(const Graph &g, Node u, Node v, Edge e) {
[100]400        bool b;
401        if (u != v) {
402          if (e == INVALID) {
403            g.firstInc(e, b, u);
404          } else {
[169]405            b = g.u(e) == u;
[100]406            g.nextInc(e, b);
407          }
[169]408          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
[100]409            g.nextInc(e, b);
410          }
411        } else {
412          if (e == INVALID) {
413            g.firstInc(e, b, u);
414          } else {
415            b = true;
416            g.nextInc(e, b);
417          }
[169]418          while (e != INVALID && (!b || g.v(e) != v)) {
[100]419            g.nextInc(e, b);
420          }
421        }
422        return e;
423      }
424    };
425
[139]426    template <typename Graph>
[100]427    struct FindEdgeSelector<
[209]428      Graph,
429      typename enable_if<typename Graph::FindEdgeTag, void>::type>
[100]430    {
[139]431      typedef typename Graph::Node Node;
432      typedef typename Graph::Edge Edge;
433      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
[100]434        return g.findEdge(u, v, prev);
435      }
[209]436    };
[100]437  }
438
[139]439  /// \brief Finds an edge between two nodes of a graph.
[100]440  ///
[139]441  /// Finds an edge from node \c u to node \c v in graph \c g.
442  /// If the node \c u and node \c v is equal then each loop edge
443  /// will be enumerated once.
[100]444  ///
445  /// If \c prev is \ref INVALID (this is the default value), then
446  /// it finds the first arc from \c u to \c v. Otherwise it looks for
447  /// the next arc from \c u to \c v after \c prev.
448  /// \return The found arc or \ref INVALID if there is no such an arc.
449  ///
450  /// Thus you can iterate through each arc from \c u to \c v as it follows.
451  ///\code
[209]452  /// for(Edge e = findEdge(g,u,v); e != INVALID;
[100]453  ///     e = findEdge(g,u,v,e)) {
454  ///   ...
455  /// }
456  ///\endcode
457  ///
[169]458  ///\sa ConEdgeIt
[100]459
[139]460  template <typename Graph>
[209]461  inline typename Graph::Edge
[139]462  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
463            typename Graph::Edge p = INVALID) {
464    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
[100]465  }
466
467  /// \brief Iterator for iterating on edges connected the same nodes.
468  ///
[209]469  /// Iterator for iterating on edges connected the same nodes. It is
[100]470  /// higher level interface for the findEdge() function. You can
471  /// use it the following way:
472  ///\code
[139]473  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
[100]474  ///   ...
475  /// }
476  ///\endcode
477  ///
478  ///\sa findEdge()
[139]479  template <typename _Graph>
480  class ConEdgeIt : public _Graph::Edge {
[100]481  public:
482
[139]483    typedef _Graph Graph;
484    typedef typename Graph::Edge Parent;
[100]485
[139]486    typedef typename Graph::Edge Edge;
487    typedef typename Graph::Node Node;
[100]488
489    /// \brief Constructor.
490    ///
[139]491    /// Construct a new ConEdgeIt iterating on the edges which
[100]492    /// connects the \c u and \c v node.
[139]493    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
494      Parent::operator=(findEdge(_graph, u, v));
[100]495    }
496
497    /// \brief Constructor.
498    ///
[209]499    /// Construct a new ConEdgeIt which continues the iterating from
[139]500    /// the \c e edge.
501    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
[209]502
[100]503    /// \brief Increment operator.
504    ///
[139]505    /// It increments the iterator and gives back the next edge.
[100]506    ConEdgeIt& operator++() {
[209]507      Parent::operator=(findEdge(_graph, _graph.u(*this),
508                                 _graph.v(*this), *this));
[100]509      return *this;
510    }
511  private:
[139]512    const Graph& _graph;
[100]513  };
514
[139]515  namespace _graph_utils_bits {
[100]516
517    template <typename Digraph, typename Item, typename RefMap>
518    class MapCopyBase {
519    public:
520      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
[209]521
[100]522      virtual ~MapCopyBase() {}
523    };
524
[209]525    template <typename Digraph, typename Item, typename RefMap,
[100]526              typename ToMap, typename FromMap>
527    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
528    public:
529
[209]530      MapCopy(ToMap& tmap, const FromMap& map)
[100]531        : _tmap(tmap), _map(map) {}
[209]532
[100]533      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
534        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
535        for (ItemIt it(digraph); it != INVALID; ++it) {
536          _tmap.set(refMap[it], _map[it]);
537        }
538      }
539
540    private:
541      ToMap& _tmap;
542      const FromMap& _map;
543    };
544
545    template <typename Digraph, typename Item, typename RefMap, typename It>
546    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
547    public:
548
549      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
[209]550
[100]551      virtual void copy(const Digraph&, const RefMap& refMap) {
552        _it = refMap[_item];
553      }
554
555    private:
556      It& _it;
557      Item _item;
558    };
559
560    template <typename Digraph, typename Item, typename RefMap, typename Ref>
561    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
562    public:
563
564      RefCopy(Ref& map) : _map(map) {}
[209]565
[100]566      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
567        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
568        for (ItemIt it(digraph); it != INVALID; ++it) {
569          _map.set(it, refMap[it]);
570        }
571      }
572
573    private:
574      Ref& _map;
575    };
576
[209]577    template <typename Digraph, typename Item, typename RefMap,
[100]578              typename CrossRef>
579    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
580    public:
581
582      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
[209]583
[100]584      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
585        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
586        for (ItemIt it(digraph); it != INVALID; ++it) {
587          _cmap.set(refMap[it], it);
588        }
589      }
590
591    private:
592      CrossRef& _cmap;
593    };
594
595    template <typename Digraph, typename Enable = void>
596    struct DigraphCopySelector {
597      template <typename From, typename NodeRefMap, typename ArcRefMap>
598      static void copy(Digraph &to, const From& from,
599                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
600        for (typename From::NodeIt it(from); it != INVALID; ++it) {
601          nodeRefMap[it] = to.addNode();
602        }
603        for (typename From::ArcIt it(from); it != INVALID; ++it) {
[209]604          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
605                                    nodeRefMap[from.target(it)]);
[100]606        }
607      }
608    };
609
610    template <typename Digraph>
611    struct DigraphCopySelector<
[209]612      Digraph,
613      typename enable_if<typename Digraph::BuildTag, void>::type>
[100]614    {
615      template <typename From, typename NodeRefMap, typename ArcRefMap>
616      static void copy(Digraph &to, const From& from,
617                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
618        to.build(from, nodeRefMap, arcRefMap);
619      }
620    };
621
622    template <typename Graph, typename Enable = void>
623    struct GraphCopySelector {
624      template <typename From, typename NodeRefMap, typename EdgeRefMap>
625      static void copy(Graph &to, const From& from,
626                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
627        for (typename From::NodeIt it(from); it != INVALID; ++it) {
628          nodeRefMap[it] = to.addNode();
629        }
630        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
[209]631          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
632                                      nodeRefMap[from.v(it)]);
[100]633        }
634      }
635    };
636
637    template <typename Graph>
638    struct GraphCopySelector<
[209]639      Graph,
640      typename enable_if<typename Graph::BuildTag, void>::type>
[100]641    {
642      template <typename From, typename NodeRefMap, typename EdgeRefMap>
643      static void copy(Graph &to, const From& from,
644                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
645        to.build(from, nodeRefMap, edgeRefMap);
646      }
647    };
648
649  }
650
651  /// \brief Class to copy a digraph.
652  ///
653  /// Class to copy a digraph to another digraph (duplicate a digraph). The
654  /// simplest way of using it is through the \c copyDigraph() function.
[139]655  ///
656  /// This class not just make a copy of a graph, but it can create
657  /// references and cross references between the nodes and arcs of
658  /// the two graphs, it can copy maps for use with the newly created
659  /// graph and copy nodes and arcs.
660  ///
661  /// To make a copy from a graph, first an instance of DigraphCopy
662  /// should be created, then the data belongs to the graph should
663  /// assigned to copy. In the end, the \c run() member should be
664  /// called.
665  ///
666  /// The next code copies a graph with several data:
667  ///\code
668  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
669  ///  // create a reference for the nodes
670  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
671  ///  dc.nodeRef(nr);
672  ///  // create a cross reference (inverse) for the arcs
673  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
674  ///  dc.arcCrossRef(acr);
675  ///  // copy an arc map
676  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
677  ///  NewGraph::ArcMap<double> namap(new_graph);
678  ///  dc.arcMap(namap, oamap);
679  ///  // copy a node
680  ///  OrigGraph::Node on;
681  ///  NewGraph::Node nn;
682  ///  dc.node(nn, on);
683  ///  // Executions of copy
684  ///  dc.run();
685  ///\endcode
[100]686  template <typename To, typename From>
687  class DigraphCopy {
688  private:
689
690    typedef typename From::Node Node;
691    typedef typename From::NodeIt NodeIt;
692    typedef typename From::Arc Arc;
693    typedef typename From::ArcIt ArcIt;
694
695    typedef typename To::Node TNode;
696    typedef typename To::Arc TArc;
697
698    typedef typename From::template NodeMap<TNode> NodeRefMap;
699    typedef typename From::template ArcMap<TArc> ArcRefMap;
[209]700
701
702  public:
[100]703
704
705    /// \brief Constructor for the DigraphCopy.
706    ///
707    /// It copies the content of the \c _from digraph into the
708    /// \c _to digraph.
[209]709    DigraphCopy(To& to, const From& from)
[139]710      : _from(from), _to(to) {}
[100]711
712    /// \brief Destructor of the DigraphCopy
713    ///
714    /// Destructor of the DigraphCopy
715    ~DigraphCopy() {
[139]716      for (int i = 0; i < int(_node_maps.size()); ++i) {
717        delete _node_maps[i];
[100]718      }
[139]719      for (int i = 0; i < int(_arc_maps.size()); ++i) {
720        delete _arc_maps[i];
[100]721      }
722
723    }
724
725    /// \brief Copies the node references into the given map.
726    ///
[139]727    /// Copies the node references into the given map. The parameter
728    /// should be a map, which key type is the Node type of the source
729    /// graph, while the value type is the Node type of the
730    /// destination graph.
[100]731    template <typename NodeRef>
732    DigraphCopy& nodeRef(NodeRef& map) {
[209]733      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
734                           NodeRefMap, NodeRef>(map));
[100]735      return *this;
736    }
737
738    /// \brief Copies the node cross references into the given map.
739    ///
740    ///  Copies the node cross references (reverse references) into
[139]741    ///  the given map. The parameter should be a map, which key type
742    ///  is the Node type of the destination graph, while the value type is
743    ///  the Node type of the source graph.
[100]744    template <typename NodeCrossRef>
745    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
[139]746      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
[209]747                           NodeRefMap, NodeCrossRef>(map));
[100]748      return *this;
749    }
750
751    /// \brief Make copy of the given map.
752    ///
[139]753    /// Makes copy of the given map for the newly created digraph.
754    /// The new map's key type is the destination graph's node type,
755    /// and the copied map's key type is the source graph's node type.
[100]756    template <typename ToMap, typename FromMap>
757    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
[209]758      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
759                           NodeRefMap, ToMap, FromMap>(tmap, map));
[100]760      return *this;
761    }
762
763    /// \brief Make a copy of the given node.
764    ///
765    /// Make a copy of the given node.
766    DigraphCopy& node(TNode& tnode, const Node& snode) {
[209]767      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
768                           NodeRefMap, TNode>(tnode, snode));
[100]769      return *this;
770    }
771
772    /// \brief Copies the arc references into the given map.
773    ///
774    /// Copies the arc references into the given map.
775    template <typename ArcRef>
776    DigraphCopy& arcRef(ArcRef& map) {
[209]777      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
778                          ArcRefMap, ArcRef>(map));
[100]779      return *this;
780    }
781
782    /// \brief Copies the arc cross references into the given map.
783    ///
784    ///  Copies the arc cross references (reverse references) into
785    ///  the given map.
786    template <typename ArcCrossRef>
787    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
[139]788      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
[209]789                          ArcRefMap, ArcCrossRef>(map));
[100]790      return *this;
791    }
792
793    /// \brief Make copy of the given map.
794    ///
[209]795    /// Makes copy of the given map for the newly created digraph.
[100]796    /// The new map's key type is the to digraph's arc type,
797    /// and the copied map's key type is the from digraph's arc
[209]798    /// type.
[100]799    template <typename ToMap, typename FromMap>
800    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
[209]801      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
802                          ArcRefMap, ToMap, FromMap>(tmap, map));
[100]803      return *this;
804    }
805
806    /// \brief Make a copy of the given arc.
807    ///
808    /// Make a copy of the given arc.
809    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
[209]810      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
811                          ArcRefMap, TArc>(tarc, sarc));
[100]812      return *this;
813    }
814
815    /// \brief Executes the copies.
816    ///
817    /// Executes the copies.
818    void run() {
[139]819      NodeRefMap nodeRefMap(_from);
820      ArcRefMap arcRefMap(_from);
821      _graph_utils_bits::DigraphCopySelector<To>::
822        copy(_to, _from, nodeRefMap, arcRefMap);
823      for (int i = 0; i < int(_node_maps.size()); ++i) {
824        _node_maps[i]->copy(_from, nodeRefMap);
[100]825      }
[139]826      for (int i = 0; i < int(_arc_maps.size()); ++i) {
827        _arc_maps[i]->copy(_from, arcRefMap);
[209]828      }
[100]829    }
830
831  protected:
832
833
[139]834    const From& _from;
835    To& _to;
[100]836
[209]837    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
[139]838    _node_maps;
[100]839
[209]840    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
[139]841    _arc_maps;
[100]842
843  };
844
845  /// \brief Copy a digraph to another digraph.
846  ///
[139]847  /// Copy a digraph to another digraph. The complete usage of the
848  /// function is detailed in the DigraphCopy class, but a short
849  /// example shows a basic work:
[100]850  ///\code
851  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
852  ///\endcode
[209]853  ///
[100]854  /// After the copy the \c nr map will contain the mapping from the
855  /// nodes of the \c from digraph to the nodes of the \c to digraph and
856  /// \c ecr will contain the mapping from the arcs of the \c to digraph
857  /// to the arcs of the \c from digraph.
858  ///
[209]859  /// \see DigraphCopy
[100]860  template <typename To, typename From>
861  DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
862    return DigraphCopy<To, From>(to, from);
863  }
864
[139]865  /// \brief Class to copy a graph.
[100]866  ///
[139]867  /// Class to copy a graph to another graph (duplicate a graph). The
868  /// simplest way of using it is through the \c copyGraph() function.
869  ///
870  /// This class not just make a copy of a graph, but it can create
871  /// references and cross references between the nodes, edges and arcs of
872  /// the two graphs, it can copy maps for use with the newly created
873  /// graph and copy nodes, edges and arcs.
874  ///
875  /// To make a copy from a graph, first an instance of GraphCopy
876  /// should be created, then the data belongs to the graph should
877  /// assigned to copy. In the end, the \c run() member should be
878  /// called.
879  ///
880  /// The next code copies a graph with several data:
881  ///\code
882  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
883  ///  // create a reference for the nodes
884  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
885  ///  dc.nodeRef(nr);
886  ///  // create a cross reference (inverse) for the edges
887  ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
888  ///  dc.edgeCrossRef(ecr);
889  ///  // copy an arc map
890  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
891  ///  NewGraph::ArcMap<double> namap(new_graph);
892  ///  dc.arcMap(namap, oamap);
893  ///  // copy a node
894  ///  OrigGraph::Node on;
895  ///  NewGraph::Node nn;
896  ///  dc.node(nn, on);
897  ///  // Executions of copy
898  ///  dc.run();
899  ///\endcode
[100]900  template <typename To, typename From>
901  class GraphCopy {
902  private:
903
904    typedef typename From::Node Node;
905    typedef typename From::NodeIt NodeIt;
906    typedef typename From::Arc Arc;
907    typedef typename From::ArcIt ArcIt;
908    typedef typename From::Edge Edge;
909    typedef typename From::EdgeIt EdgeIt;
910
911    typedef typename To::Node TNode;
912    typedef typename To::Arc TArc;
913    typedef typename To::Edge TEdge;
914
915    typedef typename From::template NodeMap<TNode> NodeRefMap;
916    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
917
918    struct ArcRefMap {
[139]919      ArcRefMap(const To& to, const From& from,
[209]920                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
921        : _to(to), _from(from),
[139]922          _edge_ref(edge_ref), _node_ref(node_ref) {}
[100]923
924      typedef typename From::Arc Key;
925      typedef typename To::Arc Value;
926
927      Value operator[](const Key& key) const {
[199]928        bool forward = _from.u(key) != _from.v(key) ?
[209]929          _node_ref[_from.source(key)] ==
930          _to.source(_to.direct(_edge_ref[key], true)) :
931          _from.direction(key);
932        return _to.direct(_edge_ref[key], forward);
[100]933      }
[209]934
[139]935      const To& _to;
936      const From& _from;
937      const EdgeRefMap& _edge_ref;
938      const NodeRefMap& _node_ref;
[100]939    };
940
[209]941
942  public:
[100]943
944
[139]945    /// \brief Constructor for the GraphCopy.
[100]946    ///
[139]947    /// It copies the content of the \c _from graph into the
948    /// \c _to graph.
[209]949    GraphCopy(To& to, const From& from)
[139]950      : _from(from), _to(to) {}
[100]951
[139]952    /// \brief Destructor of the GraphCopy
[100]953    ///
[139]954    /// Destructor of the GraphCopy
[100]955    ~GraphCopy() {
[139]956      for (int i = 0; i < int(_node_maps.size()); ++i) {
957        delete _node_maps[i];
[100]958      }
[139]959      for (int i = 0; i < int(_arc_maps.size()); ++i) {
960        delete _arc_maps[i];
[100]961      }
[139]962      for (int i = 0; i < int(_edge_maps.size()); ++i) {
963        delete _edge_maps[i];
[100]964      }
965
966    }
967
968    /// \brief Copies the node references into the given map.
969    ///
970    /// Copies the node references into the given map.
971    template <typename NodeRef>
972    GraphCopy& nodeRef(NodeRef& map) {
[209]973      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
974                           NodeRefMap, NodeRef>(map));
[100]975      return *this;
976    }
977
978    /// \brief Copies the node cross references into the given map.
979    ///
980    ///  Copies the node cross references (reverse references) into
981    ///  the given map.
982    template <typename NodeCrossRef>
983    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
[139]984      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
[209]985                           NodeRefMap, NodeCrossRef>(map));
[100]986      return *this;
987    }
988
989    /// \brief Make copy of the given map.
990    ///
[209]991    /// Makes copy of the given map for the newly created graph.
[139]992    /// The new map's key type is the to graph's node type,
993    /// and the copied map's key type is the from graph's node
[209]994    /// type.
[100]995    template <typename ToMap, typename FromMap>
996    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
[209]997      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
998                           NodeRefMap, ToMap, FromMap>(tmap, map));
[100]999      return *this;
1000    }
1001
1002    /// \brief Make a copy of the given node.
1003    ///
1004    /// Make a copy of the given node.
1005    GraphCopy& node(TNode& tnode, const Node& snode) {
[209]1006      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1007                           NodeRefMap, TNode>(tnode, snode));
[100]1008      return *this;
1009    }
1010
1011    /// \brief Copies the arc references into the given map.
1012    ///
1013    /// Copies the arc references into the given map.
1014    template <typename ArcRef>
1015    GraphCopy& arcRef(ArcRef& map) {
[209]1016      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1017                          ArcRefMap, ArcRef>(map));
[100]1018      return *this;
1019    }
1020
1021    /// \brief Copies the arc cross references into the given map.
1022    ///
1023    ///  Copies the arc cross references (reverse references) into
1024    ///  the given map.
1025    template <typename ArcCrossRef>
1026    GraphCopy& arcCrossRef(ArcCrossRef& map) {
[139]1027      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
[209]1028                          ArcRefMap, ArcCrossRef>(map));
[100]1029      return *this;
1030    }
1031
1032    /// \brief Make copy of the given map.
1033    ///
[209]1034    /// Makes copy of the given map for the newly created graph.
[139]1035    /// The new map's key type is the to graph's arc type,
1036    /// and the copied map's key type is the from graph's arc
[209]1037    /// type.
[100]1038    template <typename ToMap, typename FromMap>
1039    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
[209]1040      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1041                          ArcRefMap, ToMap, FromMap>(tmap, map));
[100]1042      return *this;
1043    }
1044
1045    /// \brief Make a copy of the given arc.
1046    ///
1047    /// Make a copy of the given arc.
1048    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
[209]1049      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1050                          ArcRefMap, TArc>(tarc, sarc));
[100]1051      return *this;
1052    }
1053
1054    /// \brief Copies the edge references into the given map.
1055    ///
1056    /// Copies the edge references into the given map.
1057    template <typename EdgeRef>
1058    GraphCopy& edgeRef(EdgeRef& map) {
[209]1059      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1060                           EdgeRefMap, EdgeRef>(map));
[100]1061      return *this;
1062    }
1063
1064    /// \brief Copies the edge cross references into the given map.
1065    ///
1066    /// Copies the edge cross references (reverse
1067    /// references) into the given map.
1068    template <typename EdgeCrossRef>
1069    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
[209]1070      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
1071                           Edge, EdgeRefMap, EdgeCrossRef>(map));
[100]1072      return *this;
1073    }
1074
1075    /// \brief Make copy of the given map.
1076    ///
[209]1077    /// Makes copy of the given map for the newly created graph.
[139]1078    /// The new map's key type is the to graph's edge type,
1079    /// and the copied map's key type is the from graph's edge
[209]1080    /// type.
[100]1081    template <typename ToMap, typename FromMap>
1082    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
[209]1083      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1084                           EdgeRefMap, ToMap, FromMap>(tmap, map));
[100]1085      return *this;
1086    }
1087
1088    /// \brief Make a copy of the given edge.
1089    ///
1090    /// Make a copy of the given edge.
1091    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
[209]1092      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1093                           EdgeRefMap, TEdge>(tedge, sedge));
[100]1094      return *this;
1095    }
1096
1097    /// \brief Executes the copies.
1098    ///
1099    /// Executes the copies.
1100    void run() {
[139]1101      NodeRefMap nodeRefMap(_from);
1102      EdgeRefMap edgeRefMap(_from);
1103      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
1104      _graph_utils_bits::GraphCopySelector<To>::
1105        copy(_to, _from, nodeRefMap, edgeRefMap);
1106      for (int i = 0; i < int(_node_maps.size()); ++i) {
1107        _node_maps[i]->copy(_from, nodeRefMap);
[100]1108      }
[139]1109      for (int i = 0; i < int(_edge_maps.size()); ++i) {
1110        _edge_maps[i]->copy(_from, edgeRefMap);
[100]1111      }
[139]1112      for (int i = 0; i < int(_arc_maps.size()); ++i) {
1113        _arc_maps[i]->copy(_from, arcRefMap);
[100]1114      }
1115    }
1116
1117  private:
[209]1118
[139]1119    const From& _from;
1120    To& _to;
[100]1121
[209]1122    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
[139]1123    _node_maps;
[100]1124
[209]1125    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
[139]1126    _arc_maps;
[100]1127
[209]1128    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
[139]1129    _edge_maps;
[100]1130
1131  };
1132
[139]1133  /// \brief Copy a graph to another graph.
[100]1134  ///
[139]1135  /// Copy a graph to another graph. The complete usage of the
1136  /// function is detailed in the GraphCopy class, but a short
1137  /// example shows a basic work:
[100]1138  ///\code
1139  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1140  ///\endcode
[209]1141  ///
[100]1142  /// After the copy the \c nr map will contain the mapping from the
[139]1143  /// nodes of the \c from graph to the nodes of the \c to graph and
1144  /// \c ecr will contain the mapping from the arcs of the \c to graph
1145  /// to the arcs of the \c from graph.
[100]1146  ///
[209]1147  /// \see GraphCopy
[100]1148  template <typename To, typename From>
[209]1149  GraphCopy<To, From>
[100]1150  copyGraph(To& to, const From& from) {
1151    return GraphCopy<To, From>(to, from);
1152  }
1153
1154  /// @}
1155
[139]1156  /// \addtogroup graph_maps
[100]1157  /// @{
1158
[139]1159  /// Provides an immutable and unique id for each item in the graph.
[100]1160
1161  /// The IdMap class provides a unique and immutable id for each item of the
[139]1162  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
[100]1163  /// different items (nodes) get different ids <li>\b immutable: the id of an
1164  /// item (node) does not change (even if you delete other nodes).  </ul>
1165  /// Through this map you get access (i.e. can read) the inner id values of
[139]1166  /// the items stored in the graph. This map can be inverted with its member
1167  /// class \c InverseMap or with the \c operator() member.
[100]1168  ///
[139]1169  template <typename _Graph, typename _Item>
[100]1170  class IdMap {
1171  public:
[139]1172    typedef _Graph Graph;
[100]1173    typedef int Value;
1174    typedef _Item Item;
1175    typedef _Item Key;
1176
1177    /// \brief Constructor.
1178    ///
1179    /// Constructor of the map.
[139]1180    explicit IdMap(const Graph& graph) : _graph(&graph) {}
[100]1181
1182    /// \brief Gives back the \e id of the item.
1183    ///
1184    /// Gives back the immutable and unique \e id of the item.
[139]1185    int operator[](const Item& item) const { return _graph->id(item);}
[100]1186
1187    /// \brief Gives back the item by its id.
1188    ///
1189    /// Gives back the item by its id.
[139]1190    Item operator()(int id) { return _graph->fromId(id, Item()); }
[100]1191
1192  private:
[139]1193    const Graph* _graph;
[100]1194
1195  public:
1196
1197    /// \brief The class represents the inverse of its owner (IdMap).
1198    ///
1199    /// The class represents the inverse of its owner (IdMap).
1200    /// \see inverse()
1201    class InverseMap {
1202    public:
1203
1204      /// \brief Constructor.
1205      ///
1206      /// Constructor for creating an id-to-item map.
[139]1207      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
[100]1208
1209      /// \brief Constructor.
1210      ///
1211      /// Constructor for creating an id-to-item map.
[139]1212      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
[100]1213
1214      /// \brief Gives back the given item from its id.
1215      ///
1216      /// Gives back the given item from its id.
[209]1217      ///
[139]1218      Item operator[](int id) const { return _graph->fromId(id, Item());}
[100]1219
1220    private:
[139]1221      const Graph* _graph;
[100]1222    };
1223
1224    /// \brief Gives back the inverse of the map.
1225    ///
1226    /// Gives back the inverse of the IdMap.
[209]1227    InverseMap inverse() const { return InverseMap(*_graph);}
[100]1228
1229  };
1230
[209]1231
[139]1232  /// \brief General invertable graph-map type.
[100]1233
[209]1234  /// This type provides simple invertable graph-maps.
1235  /// The InvertableMap wraps an arbitrary ReadWriteMap
[100]1236  /// and if a key is set to a new value then store it
1237  /// in the inverse map.
1238  ///
1239  /// The values of the map can be accessed
1240  /// with stl compatible forward iterator.
1241  ///
[157]1242  /// \tparam _Graph The graph type.
1243  /// \tparam _Item The item type of the graph.
1244  /// \tparam _Value The value type of the map.
[100]1245  ///
1246  /// \see IterableValueMap
[139]1247  template <typename _Graph, typename _Item, typename _Value>
1248  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
[100]1249  private:
[209]1250
[139]1251    typedef DefaultMap<_Graph, _Item, _Value> Map;
1252    typedef _Graph Graph;
[100]1253
1254    typedef std::map<_Value, _Item> Container;
[209]1255    Container _inv_map;
[100]1256
1257  public:
[209]1258
[100]1259    /// The key type of InvertableMap (Node, Arc, Edge).
1260    typedef typename Map::Key Key;
1261    /// The value type of the InvertableMap.
1262    typedef typename Map::Value Value;
1263
1264
1265
1266    /// \brief Constructor.
1267    ///
[139]1268    /// Construct a new InvertableMap for the graph.
[100]1269    ///
[209]1270    explicit InvertableMap(const Graph& graph) : Map(graph) {}
[100]1271
1272    /// \brief Forward iterator for values.
1273    ///
1274    /// This iterator is an stl compatible forward
1275    /// iterator on the values of the map. The values can
1276    /// be accessed in the [beginValue, endValue) range.
1277    ///
[209]1278    class ValueIterator
[100]1279      : public std::iterator<std::forward_iterator_tag, Value> {
1280      friend class InvertableMap;
1281    private:
[209]1282      ValueIterator(typename Container::const_iterator _it)
[100]1283        : it(_it) {}
1284    public:
[209]1285
[100]1286      ValueIterator() {}
1287
1288      ValueIterator& operator++() { ++it; return *this; }
[209]1289      ValueIterator operator++(int) {
1290        ValueIterator tmp(*this);
[100]1291        operator++();
[209]1292        return tmp;
[100]1293      }
1294
1295      const Value& operator*() const { return it->first; }
1296      const Value* operator->() const { return &(it->first); }
1297
1298      bool operator==(ValueIterator jt) const { return it == jt.it; }
1299      bool operator!=(ValueIterator jt) const { return it != jt.it; }
[209]1300
[100]1301    private:
1302      typename Container::const_iterator it;
1303    };
1304
1305    /// \brief Returns an iterator to the first value.
1306    ///
[209]1307    /// Returns an stl compatible iterator to the
[100]1308    /// first value of the map. The values of the
1309    /// map can be accessed in the [beginValue, endValue)
1310    /// range.
1311    ValueIterator beginValue() const {
[139]1312      return ValueIterator(_inv_map.begin());
[100]1313    }
1314
1315    /// \brief Returns an iterator after the last value.
1316    ///
[209]1317    /// Returns an stl compatible iterator after the
[100]1318    /// last value of the map. The values of the
1319    /// map can be accessed in the [beginValue, endValue)
1320    /// range.
1321    ValueIterator endValue() const {
[139]1322      return ValueIterator(_inv_map.end());
[100]1323    }
[209]1324
[100]1325    /// \brief The setter function of the map.
1326    ///
1327    /// Sets the mapped value.
1328    void set(const Key& key, const Value& val) {
1329      Value oldval = Map::operator[](key);
[139]1330      typename Container::iterator it = _inv_map.find(oldval);
1331      if (it != _inv_map.end() && it->second == key) {
[209]1332        _inv_map.erase(it);
1333      }
[139]1334      _inv_map.insert(make_pair(val, key));
[100]1335      Map::set(key, val);
1336    }
1337
1338    /// \brief The getter function of the map.
1339    ///
1340    /// It gives back the value associated with the key.
[209]1341    typename MapTraits<Map>::ConstReturnValue
[100]1342    operator[](const Key& key) const {
1343      return Map::operator[](key);
1344    }
1345
1346    /// \brief Gives back the item by its value.
1347    ///
1348    /// Gives back the item by its value.
1349    Key operator()(const Value& key) const {
[139]1350      typename Container::const_iterator it = _inv_map.find(key);
1351      return it != _inv_map.end() ? it->second : INVALID;
[100]1352    }
1353
1354  protected:
1355
1356    /// \brief Erase the key from the map.
1357    ///
1358    /// Erase the key to the map. It is called by the
1359    /// \c AlterationNotifier.
1360    virtual void erase(const Key& key) {
1361      Value val = Map::operator[](key);
[139]1362      typename Container::iterator it = _inv_map.find(val);
1363      if (it != _inv_map.end() && it->second == key) {
[209]1364        _inv_map.erase(it);
[100]1365      }
1366      Map::erase(key);
1367    }
1368
1369    /// \brief Erase more keys from the map.
1370    ///
1371    /// Erase more keys from the map. It is called by the
1372    /// \c AlterationNotifier.
1373    virtual void erase(const std::vector<Key>& keys) {
1374      for (int i = 0; i < int(keys.size()); ++i) {
[209]1375        Value val = Map::operator[](keys[i]);
1376        typename Container::iterator it = _inv_map.find(val);
1377        if (it != _inv_map.end() && it->second == keys[i]) {
1378          _inv_map.erase(it);
1379        }
[100]1380      }
1381      Map::erase(keys);
1382    }
1383
1384    /// \brief Clear the keys from the map and inverse map.
1385    ///
1386    /// Clear the keys from the map and inverse map. It is called by the
1387    /// \c AlterationNotifier.
1388    virtual void clear() {
[139]1389      _inv_map.clear();
[100]1390      Map::clear();
1391    }
1392
1393  public:
1394
1395    /// \brief The inverse map type.
1396    ///
1397    /// The inverse of this map. The subscript operator of the map
[209]1398    /// gives back always the item what was last assigned to the value.
[100]1399    class InverseMap {
1400    public:
1401      /// \brief Constructor of the InverseMap.
1402      ///
1403      /// Constructor of the InverseMap.
[209]1404      explicit InverseMap(const InvertableMap& inverted)
[139]1405        : _inverted(inverted) {}
[100]1406
1407      /// The value type of the InverseMap.
1408      typedef typename InvertableMap::Key Value;
1409      /// The key type of the InverseMap.
[209]1410      typedef typename InvertableMap::Value Key;
1411
1412      /// \brief Subscript operator.
[100]1413      ///
[209]1414      /// Subscript operator. It gives back always the item
[100]1415      /// what was last assigned to the value.
1416      Value operator[](const Key& key) const {
[209]1417        return _inverted(key);
[100]1418      }
[209]1419
[100]1420    private:
[139]1421      const InvertableMap& _inverted;
[100]1422    };
1423
1424    /// \brief It gives back the just readable inverse map.
1425    ///
1426    /// It gives back the just readable inverse map.
1427    InverseMap inverse() const {
1428      return InverseMap(*this);
[209]1429    }
1430
1431
1432
[100]1433  };
1434
[209]1435  /// \brief Provides a mutable, continuous and unique descriptor for each
[139]1436  /// item in the graph.
[100]1437  ///
1438  /// The DescriptorMap class provides a unique and continuous (but mutable)
1439  /// descriptor (id) for each item of the same type (e.g. node) in the
[139]1440  /// graph. This id is <ul><li>\b unique: different items (nodes) get
[100]1441  /// different ids <li>\b continuous: the range of the ids is the set of
1442  /// integers between 0 and \c n-1, where \c n is the number of the items of
1443  /// this type (e.g. nodes) (so the id of a node can change if you delete an
1444  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
[139]1445  /// with its member class \c InverseMap, or with the \c operator() member.
[100]1446  ///
[157]1447  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
[209]1448  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
[100]1449  /// Edge.
[139]1450  template <typename _Graph, typename _Item>
1451  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
[100]1452
1453    typedef _Item Item;
[139]1454    typedef DefaultMap<_Graph, _Item, int> Map;
[100]1455
1456  public:
[139]1457    /// The graph class of DescriptorMap.
1458    typedef _Graph Graph;
[100]1459
1460    /// The key type of DescriptorMap (Node, Arc, Edge).
1461    typedef typename Map::Key Key;
1462    /// The value type of DescriptorMap.
1463    typedef typename Map::Value Value;
1464
1465    /// \brief Constructor.
1466    ///
1467    /// Constructor for descriptor map.
[139]1468    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
[100]1469      Item it;
[209]1470      const typename Map::Notifier* nf = Map::notifier();
[100]1471      for (nf->first(it); it != INVALID; nf->next(it)) {
[209]1472        Map::set(it, _inv_map.size());
1473        _inv_map.push_back(it);
1474      }
[100]1475    }
1476
1477  protected:
1478
1479    /// \brief Add a new key to the map.
1480    ///
1481    /// Add a new key to the map. It is called by the
1482    /// \c AlterationNotifier.
1483    virtual void add(const Item& item) {
1484      Map::add(item);
[139]1485      Map::set(item, _inv_map.size());
1486      _inv_map.push_back(item);
[100]1487    }
1488
1489    /// \brief Add more new keys to the map.
1490    ///
1491    /// Add more new keys to the map. It is called by the
1492    /// \c AlterationNotifier.
1493    virtual void add(const std::vector<Item>& items) {
1494      Map::add(items);
1495      for (int i = 0; i < int(items.size()); ++i) {
[209]1496        Map::set(items[i], _inv_map.size());
1497        _inv_map.push_back(items[i]);
[100]1498      }
1499    }
1500
1501    /// \brief Erase the key from the map.
1502    ///
1503    /// Erase the key from the map. It is called by the
1504    /// \c AlterationNotifier.
1505    virtual void erase(const Item& item) {
[139]1506      Map::set(_inv_map.back(), Map::operator[](item));
1507      _inv_map[Map::operator[](item)] = _inv_map.back();
1508      _inv_map.pop_back();
[100]1509      Map::erase(item);
1510    }
1511
1512    /// \brief Erase more keys from the map.
1513    ///
1514    /// Erase more keys from the map. It is called by the
1515    /// \c AlterationNotifier.
1516    virtual void erase(const std::vector<Item>& items) {
1517      for (int i = 0; i < int(items.size()); ++i) {
[209]1518        Map::set(_inv_map.back(), Map::operator[](items[i]));
1519        _inv_map[Map::operator[](items[i])] = _inv_map.back();
1520        _inv_map.pop_back();
[100]1521      }
1522      Map::erase(items);
1523    }
1524
1525    /// \brief Build the unique map.
1526    ///
1527    /// Build the unique map. It is called by the
1528    /// \c AlterationNotifier.
1529    virtual void build() {
1530      Map::build();
1531      Item it;
[209]1532      const typename Map::Notifier* nf = Map::notifier();
[100]1533      for (nf->first(it); it != INVALID; nf->next(it)) {
[209]1534        Map::set(it, _inv_map.size());
1535        _inv_map.push_back(it);
1536      }
[100]1537    }
[209]1538
[100]1539    /// \brief Clear the keys from the map.
1540    ///
1541    /// Clear the keys from the map. It is called by the
1542    /// \c AlterationNotifier.
1543    virtual void clear() {
[139]1544      _inv_map.clear();
[100]1545      Map::clear();
1546    }
1547
1548  public:
1549
1550    /// \brief Returns the maximal value plus one.
1551    ///
1552    /// Returns the maximal value plus one in the map.
1553    unsigned int size() const {
[139]1554      return _inv_map.size();
[100]1555    }
1556
1557    /// \brief Swaps the position of the two items in the map.
1558    ///
1559    /// Swaps the position of the two items in the map.
1560    void swap(const Item& p, const Item& q) {
1561      int pi = Map::operator[](p);
1562      int qi = Map::operator[](q);
1563      Map::set(p, qi);
[139]1564      _inv_map[qi] = p;
[100]1565      Map::set(q, pi);
[139]1566      _inv_map[pi] = q;
[100]1567    }
1568
1569    /// \brief Gives back the \e descriptor of the item.
1570    ///
1571    /// Gives back the mutable and unique \e descriptor of the map.
1572    int operator[](const Item& item) const {
1573      return Map::operator[](item);
1574    }
1575
1576    /// \brief Gives back the item by its descriptor.
1577    ///
1578    /// Gives back th item by its descriptor.
1579    Item operator()(int id) const {
[139]1580      return _inv_map[id];
[100]1581    }
[209]1582
[100]1583  private:
1584
1585    typedef std::vector<Item> Container;
[139]1586    Container _inv_map;
[100]1587
1588  public:
1589    /// \brief The inverse map type of DescriptorMap.
1590    ///
1591    /// The inverse map type of DescriptorMap.
1592    class InverseMap {
1593    public:
1594      /// \brief Constructor of the InverseMap.
1595      ///
1596      /// Constructor of the InverseMap.
[209]1597      explicit InverseMap(const DescriptorMap& inverted)
1598        : _inverted(inverted) {}
[100]1599
1600
1601      /// The value type of the InverseMap.
1602      typedef typename DescriptorMap::Key Value;
1603      /// The key type of the InverseMap.
[209]1604      typedef typename DescriptorMap::Value Key;
1605
1606      /// \brief Subscript operator.
[100]1607      ///
[209]1608      /// Subscript operator. It gives back the item
[100]1609      /// that the descriptor belongs to currently.
1610      Value operator[](const Key& key) const {
[209]1611        return _inverted(key);
[100]1612      }
1613
1614      /// \brief Size of the map.
1615      ///
1616      /// Returns the size of the map.
1617      unsigned int size() const {
[209]1618        return _inverted.size();
[100]1619      }
[209]1620
[100]1621    private:
[139]1622      const DescriptorMap& _inverted;
[100]1623    };
1624
1625    /// \brief Gives back the inverse of the map.
1626    ///
1627    /// Gives back the inverse of the map.
1628    const InverseMap inverse() const {
1629      return InverseMap(*this);
1630    }
1631  };
1632
1633  /// \brief Returns the source of the given arc.
1634  ///
[209]1635  /// The SourceMap gives back the source Node of the given arc.
[100]1636  /// \see TargetMap
1637  template <typename Digraph>
1638  class SourceMap {
1639  public:
1640
1641    typedef typename Digraph::Node Value;
1642    typedef typename Digraph::Arc Key;
1643
1644    /// \brief Constructor
1645    ///
1646    /// Constructor
1647    /// \param _digraph The digraph that the map belongs to.
[139]1648    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
[100]1649
1650    /// \brief The subscript operator.
1651    ///
1652    /// The subscript operator.
[209]1653    /// \param arc The arc
1654    /// \return The source of the arc
[100]1655    Value operator[](const Key& arc) const {
[139]1656      return _digraph.source(arc);
[100]1657    }
1658
1659  private:
[139]1660    const Digraph& _digraph;
[100]1661  };
1662
1663  /// \brief Returns a \ref SourceMap class.
1664  ///
1665  /// This function just returns an \ref SourceMap class.
1666  /// \relates SourceMap
1667  template <typename Digraph>
1668  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
1669    return SourceMap<Digraph>(digraph);
[209]1670  }
[100]1671
1672  /// \brief Returns the target of the given arc.
1673  ///
[209]1674  /// The TargetMap gives back the target Node of the given arc.
[100]1675  /// \see SourceMap
1676  template <typename Digraph>
1677  class TargetMap {
1678  public:
1679
1680    typedef typename Digraph::Node Value;
1681    typedef typename Digraph::Arc Key;
1682
1683    /// \brief Constructor
1684    ///
1685    /// Constructor
1686    /// \param _digraph The digraph that the map belongs to.
[139]1687    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
[100]1688
1689    /// \brief The subscript operator.
1690    ///
1691    /// The subscript operator.
[209]1692    /// \param e The arc
1693    /// \return The target of the arc
[100]1694    Value operator[](const Key& e) const {
[139]1695      return _digraph.target(e);
[100]1696    }
1697
1698  private:
[139]1699    const Digraph& _digraph;
[100]1700  };
1701
1702  /// \brief Returns a \ref TargetMap class.
1703  ///
1704  /// This function just returns a \ref TargetMap class.
1705  /// \relates TargetMap
1706  template <typename Digraph>
1707  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
1708    return TargetMap<Digraph>(digraph);
1709  }
1710
1711  /// \brief Returns the "forward" directed arc view of an edge.
1712  ///
1713  /// Returns the "forward" directed arc view of an edge.
1714  /// \see BackwardMap
[139]1715  template <typename Graph>
[100]1716  class ForwardMap {
1717  public:
1718
[139]1719    typedef typename Graph::Arc Value;
1720    typedef typename Graph::Edge Key;
[100]1721
1722    /// \brief Constructor
1723    ///
1724    /// Constructor
[139]1725    /// \param _graph The graph that the map belongs to.
1726    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
[100]1727
1728    /// \brief The subscript operator.
1729    ///
1730    /// The subscript operator.
[209]1731    /// \param key An edge
1732    /// \return The "forward" directed arc view of edge
[100]1733    Value operator[](const Key& key) const {
[139]1734      return _graph.direct(key, true);
[100]1735    }
1736
1737  private:
[139]1738    const Graph& _graph;
[100]1739  };
1740
1741  /// \brief Returns a \ref ForwardMap class.
1742  ///
1743  /// This function just returns an \ref ForwardMap class.
1744  /// \relates ForwardMap
[139]1745  template <typename Graph>
1746  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1747    return ForwardMap<Graph>(graph);
[100]1748  }
1749
1750  /// \brief Returns the "backward" directed arc view of an edge.
1751  ///
1752  /// Returns the "backward" directed arc view of an edge.
1753  /// \see ForwardMap
[139]1754  template <typename Graph>
[100]1755  class BackwardMap {
1756  public:
1757
[139]1758    typedef typename Graph::Arc Value;
1759    typedef typename Graph::Edge Key;
[100]1760
1761    /// \brief Constructor
1762    ///
1763    /// Constructor
[139]1764    /// \param _graph The graph that the map belongs to.
1765    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
[100]1766
1767    /// \brief The subscript operator.
1768    ///
1769    /// The subscript operator.
[209]1770    /// \param key An edge
1771    /// \return The "backward" directed arc view of edge
[100]1772    Value operator[](const Key& key) const {
[139]1773      return _graph.direct(key, false);
[100]1774    }
1775
1776  private:
[139]1777    const Graph& _graph;
[100]1778  };
1779
1780  /// \brief Returns a \ref BackwardMap class
1781
1782  /// This function just returns a \ref BackwardMap class.
1783  /// \relates BackwardMap
[139]1784  template <typename Graph>
1785  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1786    return BackwardMap<Graph>(graph);
[100]1787  }
1788
1789  /// \brief Potential difference map
1790  ///
1791  /// If there is an potential map on the nodes then we
1792  /// can get an arc map as we get the substraction of the
1793  /// values of the target and source.
1794  template <typename Digraph, typename NodeMap>
1795  class PotentialDifferenceMap {
1796  public:
1797    typedef typename Digraph::Arc Key;
1798    typedef typename NodeMap::Value Value;
1799
1800    /// \brief Constructor
1801    ///
1802    /// Contructor of the map
[209]1803    explicit PotentialDifferenceMap(const Digraph& digraph,
1804                                    const NodeMap& potential)
[139]1805      : _digraph(digraph), _potential(potential) {}
[100]1806
1807    /// \brief Const subscription operator
1808    ///
1809    /// Const subscription operator
1810    Value operator[](const Key& arc) const {
[209]1811      return _potential[_digraph.target(arc)] -
1812        _potential[_digraph.source(arc)];
[100]1813    }
1814
1815  private:
[139]1816    const Digraph& _digraph;
1817    const NodeMap& _potential;
[100]1818  };
1819
1820  /// \brief Returns a PotentialDifferenceMap.
1821  ///
1822  /// This function just returns a PotentialDifferenceMap.
1823  /// \relates PotentialDifferenceMap
1824  template <typename Digraph, typename NodeMap>
[209]1825  PotentialDifferenceMap<Digraph, NodeMap>
[100]1826  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
1827    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
1828  }
1829
1830  /// \brief Map of the node in-degrees.
1831  ///
1832  /// This map returns the in-degree of a node. Once it is constructed,
1833  /// the degrees are stored in a standard NodeMap, so each query is done
1834  /// in constant time. On the other hand, the values are updated automatically
1835  /// whenever the digraph changes.
1836  ///
1837  /// \warning Besides addNode() and addArc(), a digraph structure may provide
1838  /// alternative ways to modify the digraph. The correct behavior of InDegMap
1839  /// is not guarantied if these additional features are used. For example
1840  /// the functions \ref ListDigraph::changeSource() "changeSource()",
1841  /// \ref ListDigraph::changeTarget() "changeTarget()" and
1842  /// \ref ListDigraph::reverseArc() "reverseArc()"
1843  /// of \ref ListDigraph will \e not update the degree values correctly.
1844  ///
1845  /// \sa OutDegMap
1846
1847  template <typename _Digraph>
[209]1848  class InDegMap
[100]1849    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1850      ::ItemNotifier::ObserverBase {
1851
1852  public:
[209]1853
[100]1854    typedef _Digraph Digraph;
1855    typedef int Value;
1856    typedef typename Digraph::Node Key;
1857
[139]1858    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
[100]1859    ::ItemNotifier::ObserverBase Parent;
1860
1861  private:
1862
[139]1863    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
[100]1864    public:
1865
[139]1866      typedef DefaultMap<Digraph, Key, int> Parent;
[100]1867
1868      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
[209]1869
[100]1870      virtual void add(const Key& key) {
[209]1871        Parent::add(key);
1872        Parent::set(key, 0);
[100]1873      }
1874
1875      virtual void add(const std::vector<Key>& keys) {
[209]1876        Parent::add(keys);
1877        for (int i = 0; i < int(keys.size()); ++i) {
1878          Parent::set(keys[i], 0);
1879        }
[100]1880      }
1881
1882      virtual void build() {
[209]1883        Parent::build();
1884        Key it;
1885        typename Parent::Notifier* nf = Parent::notifier();
1886        for (nf->first(it); it != INVALID; nf->next(it)) {
1887          Parent::set(it, 0);
1888        }
[100]1889      }
1890    };
1891
1892  public:
1893
1894    /// \brief Constructor.
1895    ///
1896    /// Constructor for creating in-degree map.
[209]1897    explicit InDegMap(const Digraph& digraph)
[139]1898      : _digraph(digraph), _deg(digraph) {
1899      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
[209]1900
[139]1901      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
[209]1902        _deg[it] = countInArcs(_digraph, it);
[100]1903      }
1904    }
[209]1905
[100]1906    /// Gives back the in-degree of a Node.
1907    int operator[](const Key& key) const {
[139]1908      return _deg[key];
[100]1909    }
1910
1911  protected:
[209]1912
[100]1913    typedef typename Digraph::Arc Arc;
1914
1915    virtual void add(const Arc& arc) {
[139]1916      ++_deg[_digraph.target(arc)];
[100]1917    }
1918
1919    virtual void add(const std::vector<Arc>& arcs) {
1920      for (int i = 0; i < int(arcs.size()); ++i) {
[139]1921        ++_deg[_digraph.target(arcs[i])];
[100]1922      }
1923    }
1924
1925    virtual void erase(const Arc& arc) {
[139]1926      --_deg[_digraph.target(arc)];
[100]1927    }
1928
1929    virtual void erase(const std::vector<Arc>& arcs) {
1930      for (int i = 0; i < int(arcs.size()); ++i) {
[139]1931        --_deg[_digraph.target(arcs[i])];
[100]1932      }
1933    }
1934
1935    virtual void build() {
[139]1936      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
[209]1937        _deg[it] = countInArcs(_digraph, it);
1938      }
[100]1939    }
1940
1941    virtual void clear() {
[139]1942      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
[209]1943        _deg[it] = 0;
[100]1944      }
1945    }
1946  private:
[209]1947
[139]1948    const Digraph& _digraph;
1949    AutoNodeMap _deg;
[100]1950  };
1951
1952  /// \brief Map of the node out-degrees.
1953  ///
1954  /// This map returns the out-degree of a node. Once it is constructed,
1955  /// the degrees are stored in a standard NodeMap, so each query is done
1956  /// in constant time. On the other hand, the values are updated automatically
1957  /// whenever the digraph changes.
1958  ///
1959  /// \warning Besides addNode() and addArc(), a digraph structure may provide
1960  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
1961  /// is not guarantied if these additional features are used. For example
1962  /// the functions \ref ListDigraph::changeSource() "changeSource()",
1963  /// \ref ListDigraph::changeTarget() "changeTarget()" and
1964  /// \ref ListDigraph::reverseArc() "reverseArc()"
1965  /// of \ref ListDigraph will \e not update the degree values correctly.
1966  ///
1967  /// \sa InDegMap
1968
1969  template <typename _Digraph>
[209]1970  class OutDegMap
[100]1971    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1972      ::ItemNotifier::ObserverBase {
1973
1974  public:
[209]1975
[100]1976    typedef _Digraph Digraph;
1977    typedef int Value;
1978    typedef typename Digraph::Node Key;
1979
[139]1980    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1981    ::ItemNotifier::ObserverBase Parent;
1982
[100]1983  private:
1984
[139]1985    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
[100]1986    public:
1987
[139]1988      typedef DefaultMap<Digraph, Key, int> Parent;
[100]1989
1990      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
[209]1991
[100]1992      virtual void add(const Key& key) {
[209]1993        Parent::add(key);
1994        Parent::set(key, 0);
[100]1995      }
1996      virtual void add(const std::vector<Key>& keys) {
[209]1997        Parent::add(keys);
1998        for (int i = 0; i < int(keys.size()); ++i) {
1999          Parent::set(keys[i], 0);
2000        }
[100]2001      }
2002      virtual void build() {
[209]2003        Parent::build();
2004        Key it;
2005        typename Parent::Notifier* nf = Parent::notifier();
2006        for (nf->first(it); it != INVALID; nf->next(it)) {
2007          Parent::set(it, 0);
2008        }
[100]2009      }
2010    };
2011
2012  public:
2013
2014    /// \brief Constructor.
2015    ///
2016    /// Constructor for creating out-degree map.
[209]2017    explicit OutDegMap(const Digraph& digraph)
[139]2018      : _digraph(digraph), _deg(digraph) {
2019      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
[209]2020
[139]2021      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
[209]2022        _deg[it] = countOutArcs(_digraph, it);
[100]2023      }
2024    }
2025
2026    /// Gives back the out-degree of a Node.
2027    int operator[](const Key& key) const {
[139]2028      return _deg[key];
[100]2029    }
2030
2031  protected:
[209]2032
[100]2033    typedef typename Digraph::Arc Arc;
2034
2035    virtual void add(const Arc& arc) {
[139]2036      ++_deg[_digraph.source(arc)];
[100]2037    }
2038
2039    virtual void add(const std::vector<Arc>& arcs) {
2040      for (int i = 0; i < int(arcs.size()); ++i) {
[139]2041        ++_deg[_digraph.source(arcs[i])];
[100]2042      }
2043    }
2044
2045    virtual void erase(const Arc& arc) {
[139]2046      --_deg[_digraph.source(arc)];
[100]2047    }
2048
2049    virtual void erase(const std::vector<Arc>& arcs) {
2050      for (int i = 0; i < int(arcs.size()); ++i) {
[139]2051        --_deg[_digraph.source(arcs[i])];
[100]2052      }
2053    }
2054
2055    virtual void build() {
[139]2056      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
[209]2057        _deg[it] = countOutArcs(_digraph, it);
2058      }
[100]2059    }
2060
2061    virtual void clear() {
[139]2062      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
[209]2063        _deg[it] = 0;
[100]2064      }
2065    }
2066  private:
[209]2067
[139]2068    const Digraph& _digraph;
2069    AutoNodeMap _deg;
[100]2070  };
2071
2072
2073  ///Dynamic arc look up between given endpoints.
[209]2074
[100]2075  ///\ingroup gutils
2076  ///Using this class, you can find an arc in a digraph from a given
2077  ///source to a given target in amortized time <em>O(log d)</em>,
2078  ///where <em>d</em> is the out-degree of the source node.
2079  ///
2080  ///It is possible to find \e all parallel arcs between two nodes with
2081  ///the \c findFirst() and \c findNext() members.
2082  ///
2083  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
[139]2084  ///digraph is not changed so frequently.
[100]2085  ///
2086  ///This class uses a self-adjusting binary search tree, Sleator's
2087  ///and Tarjan's Splay tree for guarantee the logarithmic amortized
2088  ///time bound for arc lookups. This class also guarantees the
2089  ///optimal time bound in a constant factor for any distribution of
2090  ///queries.
2091  ///
[209]2092  ///\tparam G The type of the underlying digraph.
[100]2093  ///
[209]2094  ///\sa ArcLookUp
2095  ///\sa AllArcLookUp
[100]2096  template<class G>
[209]2097  class DynArcLookUp
[100]2098    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
2099  {
2100  public:
2101    typedef typename ItemSetTraits<G, typename G::Arc>
2102    ::ItemNotifier::ObserverBase Parent;
2103
[148]2104    TEMPLATE_DIGRAPH_TYPEDEFS(G);
[100]2105    typedef G Digraph;
2106
2107  protected:
2108
2109    class AutoNodeMap : public DefaultMap<G, Node, Arc> {
2110    public:
2111
2112      typedef DefaultMap<G, Node, Arc> Parent;
2113
2114      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
[209]2115
[100]2116      virtual void add(const Node& node) {
[209]2117        Parent::add(node);
2118        Parent::set(node, INVALID);
[100]2119      }
2120
2121      virtual void add(const std::vector<Node>& nodes) {
[209]2122        Parent::add(nodes);
2123        for (int i = 0; i < int(nodes.size()); ++i) {
2124          Parent::set(nodes[i], INVALID);
2125        }
[100]2126      }
2127
2128      virtual void build() {
[209]2129        Parent::build();
2130        Node it;
2131        typename Parent::Notifier* nf = Parent::notifier();
2132        for (nf->first(it); it != INVALID; nf->next(it)) {
2133          Parent::set(it, INVALID);
2134        }
[100]2135      }
2136    };
2137
2138    const Digraph &_g;
2139    AutoNodeMap _head;
2140    typename Digraph::template ArcMap<Arc> _parent;
2141    typename Digraph::template ArcMap<Arc> _left;
2142    typename Digraph::template ArcMap<Arc> _right;
[209]2143
[100]2144    class ArcLess {
2145      const Digraph &g;
2146    public:
2147      ArcLess(const Digraph &_g) : g(_g) {}
[209]2148      bool operator()(Arc a,Arc b) const
[100]2149      {
[209]2150        return g.target(a)<g.target(b);
[100]2151      }
2152    };
[209]2153
[100]2154  public:
[209]2155
[100]2156    ///Constructor
2157
2158    ///Constructor.
2159    ///
2160    ///It builds up the search database.
[209]2161    DynArcLookUp(const Digraph &g)
2162      : _g(g),_head(g),_parent(g),_left(g),_right(g)
2163    {
[100]2164      Parent::attach(_g.notifier(typename Digraph::Arc()));
[209]2165      refresh();
[100]2166    }
[209]2167
[100]2168  protected:
2169
2170    virtual void add(const Arc& arc) {
2171      insert(arc);
2172    }
2173
2174    virtual void add(const std::vector<Arc>& arcs) {
2175      for (int i = 0; i < int(arcs.size()); ++i) {
[209]2176        insert(arcs[i]);
[100]2177      }
2178    }
2179
2180    virtual void erase(const Arc& arc) {
2181      remove(arc);
2182    }
2183
2184    virtual void erase(const std::vector<Arc>& arcs) {
2185      for (int i = 0; i < int(arcs.size()); ++i) {
[209]2186        remove(arcs[i]);
2187      }
[100]2188    }
2189
2190    virtual void build() {
2191      refresh();
2192    }
2193
2194    virtual void clear() {
2195      for(NodeIt n(_g);n!=INVALID;++n) {
[209]2196        _head.set(n, INVALID);
[100]2197      }
2198    }
2199
2200    void insert(Arc arc) {
2201      Node s = _g.source(arc);
2202      Node t = _g.target(arc);
2203      _left.set(arc, INVALID);
2204      _right.set(arc, INVALID);
[209]2205
[100]2206      Arc e = _head[s];
2207      if (e == INVALID) {
[209]2208        _head.set(s, arc);
2209        _parent.set(arc, INVALID);
2210        return;
[100]2211      }
2212      while (true) {
[209]2213        if (t < _g.target(e)) {
2214          if (_left[e] == INVALID) {
2215            _left.set(e, arc);
2216            _parent.set(arc, e);
2217            splay(arc);
2218            return;
2219          } else {
2220            e = _left[e];
2221          }
2222        } else {
2223          if (_right[e] == INVALID) {
2224            _right.set(e, arc);
2225            _parent.set(arc, e);
2226            splay(arc);
2227            return;
2228          } else {
2229            e = _right[e];
2230          }
2231        }
[100]2232      }
2233    }
2234
2235    void remove(Arc arc) {
2236      if (_left[arc] == INVALID) {
[209]2237        if (_right[arc] != INVALID) {
2238          _parent.set(_right[arc], _parent[arc]);
2239        }
2240        if (_parent[arc] != INVALID) {
2241          if (_left[_parent[arc]] == arc) {
2242            _left.set(_parent[arc], _right[arc]);
2243          } else {
2244            _right.set(_parent[arc], _right[arc]);
2245          }
2246        } else {
2247          _head.set(_g.source(arc), _right[arc]);
2248        }
[100]2249      } else if (_right[arc] == INVALID) {
[209]2250        _parent.set(_left[arc], _parent[arc]);
2251        if (_parent[arc] != INVALID) {
2252          if (_left[_parent[arc]] == arc) {
2253            _left.set(_parent[arc], _left[arc]);
2254          } else {
2255            _right.set(_parent[arc], _left[arc]);
2256          }
2257        } else {
2258          _head.set(_g.source(arc), _left[arc]);
2259        }
[100]2260      } else {
[209]2261        Arc e = _left[arc];
2262        if (_right[e] != INVALID) {
2263          e = _right[e];
2264          while (_right[e] != INVALID) {
2265            e = _right[e];
2266          }
2267          Arc s = _parent[e];
2268          _right.set(_parent[e], _left[e]);
2269          if (_left[e] != INVALID) {
2270            _parent.set(_left[e], _parent[e]);
2271          }
2272
2273          _left.set(e, _left[arc]);
2274          _parent.set(_left[arc], e);
2275          _right.set(e, _right[arc]);
2276          _parent.set(_right[arc], e);
2277
2278          _parent.set(e, _parent[arc]);
2279          if (_parent[arc] != INVALID) {
2280            if (_left[_parent[arc]] == arc) {
2281              _left.set(_parent[arc], e);
2282            } else {
2283              _right.set(_parent[arc], e);
2284            }
2285          }
2286          splay(s);
2287        } else {
2288          _right.set(e, _right[arc]);
2289          _parent.set(_right[arc], e);
2290
2291          if (_parent[arc] != INVALID) {
2292            if (_left[_parent[arc]] == arc) {
2293              _left.set(_parent[arc], e);
2294            } else {
2295              _right.set(_parent[arc], e);
2296            }
2297          } else {
2298            _head.set(_g.source(arc), e);
2299          }
2300        }
[100]2301      }
2302    }
2303
[209]2304    Arc refreshRec(std::vector<Arc> &v,int a,int b)
[100]2305    {
2306      int m=(a+b)/2;
2307      Arc me=v[m];
2308      if (a < m) {
[209]2309        Arc left = refreshRec(v,a,m-1);
2310        _left.set(me, left);
2311        _parent.set(left, me);
[100]2312      } else {
[209]2313        _left.set(me, INVALID);
[100]2314      }
2315      if (m < b) {
[209]2316        Arc right = refreshRec(v,m+1,b);
2317        _right.set(me, right);
2318        _parent.set(right, me);
[100]2319      } else {
[209]2320        _right.set(me, INVALID);
[100]2321      }
2322      return me;
2323    }
2324
2325    void refresh() {
2326      for(NodeIt n(_g);n!=INVALID;++n) {
[209]2327        std::vector<Arc> v;
2328        for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2329        if(v.size()) {
2330          std::sort(v.begin(),v.end(),ArcLess(_g));
2331          Arc head = refreshRec(v,0,v.size()-1);
2332          _head.set(n, head);
2333          _parent.set(head, INVALID);
2334        }
2335        else _head.set(n, INVALID);
[100]2336      }
2337    }
2338
[209]2339    void zig(Arc v) {
[100]2340      Arc w = _parent[v];
2341      _parent.set(v, _parent[w]);
2342      _parent.set(w, v);
2343      _left.set(w, _right[v]);
2344      _right.set(v, w);
2345      if (_parent[v] != INVALID) {
[209]2346        if (_right[_parent[v]] == w) {
2347          _right.set(_parent[v], v);
2348        } else {
2349          _left.set(_parent[v], v);
2350        }
[100]2351      }
2352      if (_left[w] != INVALID){
[209]2353        _parent.set(_left[w], w);
[100]2354      }
2355    }
2356
[209]2357    void zag(Arc v) {
[100]2358      Arc w = _parent[v];
2359      _parent.set(v, _parent[w]);
2360      _parent.set(w, v);
2361      _right.set(w, _left[v]);
2362      _left.set(v, w);
2363      if (_parent[v] != INVALID){
[209]2364        if (_left[_parent[v]] == w) {
2365          _left.set(_parent[v], v);
2366        } else {
2367          _right.set(_parent[v], v);
2368        }
[100]2369      }
2370      if (_right[w] != INVALID){
[209]2371        _parent.set(_right[w], w);
[100]2372      }
2373    }
2374
2375    void splay(Arc v) {
2376      while (_parent[v] != INVALID) {
[209]2377        if (v == _left[_parent[v]]) {
2378          if (_parent[_parent[v]] == INVALID) {
2379            zig(v);
2380          } else {
2381            if (_parent[v] == _left[_parent[_parent[v]]]) {
2382              zig(_parent[v]);
2383              zig(v);
2384            } else {
2385              zig(v);
2386              zag(v);
2387            }
2388          }
2389        } else {
2390          if (_parent[_parent[v]] == INVALID) {
2391            zag(v);
2392          } else {
2393            if (_parent[v] == _left[_parent[_parent[v]]]) {
2394              zag(v);
2395              zig(v);
2396            } else {
2397              zag(_parent[v]);
2398              zag(v);
2399            }
2400          }
2401        }
[100]2402      }
2403      _head[_g.source(v)] = v;
2404    }
2405
2406
2407  public:
[209]2408
[100]2409    ///Find an arc between two nodes.
[209]2410
[100]2411    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
2412    /// <em>d</em> is the number of outgoing arcs of \c s.
2413    ///\param s The source node
2414    ///\param t The target node
2415    ///\return An arc from \c s to \c t if there exists,
2416    ///\ref INVALID otherwise.
2417    Arc operator()(Node s, Node t) const
2418    {
[139]2419      Arc a = _head[s];
[100]2420      while (true) {
[209]2421        if (_g.target(a) == t) {
2422          const_cast<DynArcLookUp&>(*this).splay(a);
2423          return a;
2424        } else if (t < _g.target(a)) {
2425          if (_left[a] == INVALID) {
2426            const_cast<DynArcLookUp&>(*this).splay(a);
2427            return INVALID;
2428          } else {
2429            a = _left[a];
2430          }
2431        } else  {
2432          if (_right[a] == INVALID) {
2433            const_cast<DynArcLookUp&>(*this).splay(a);
2434            return INVALID;
2435          } else {
2436            a = _right[a];
2437          }
2438        }
[100]2439      }
2440    }
2441
2442    ///Find the first arc between two nodes.
[209]2443
[100]2444    ///Find the first arc between two nodes in time
2445    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
[209]2446    /// outgoing arcs of \c s.
2447    ///\param s The source node
[100]2448    ///\param t The target node
2449    ///\return An arc from \c s to \c t if there exists, \ref INVALID
2450    /// otherwise.
2451    Arc findFirst(Node s, Node t) const
2452    {
[139]2453      Arc a = _head[s];
[100]2454      Arc r = INVALID;
2455      while (true) {
[209]2456        if (_g.target(a) < t) {
2457          if (_right[a] == INVALID) {
2458            const_cast<DynArcLookUp&>(*this).splay(a);
2459            return r;
2460          } else {
2461            a = _right[a];
2462          }
2463        } else {
2464          if (_g.target(a) == t) {
2465            r = a;
2466          }
2467          if (_left[a] == INVALID) {
2468            const_cast<DynArcLookUp&>(*this).splay(a);
2469            return r;
2470          } else {
2471            a = _left[a];
2472          }
2473        }
[100]2474      }
2475    }
2476
2477    ///Find the next arc between two nodes.
[209]2478
[100]2479    ///Find the next arc between two nodes in time
2480    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
[209]2481    /// outgoing arcs of \c s.
2482    ///\param s The source node
[100]2483    ///\param t The target node
2484    ///\return An arc from \c s to \c t if there exists, \ref INVALID
2485    /// otherwise.
2486
2487    ///\note If \c e is not the result of the previous \c findFirst()
2488    ///operation then the amorized time bound can not be guaranteed.
2489#ifdef DOXYGEN
[139]2490    Arc findNext(Node s, Node t, Arc a) const
[100]2491#else
[139]2492    Arc findNext(Node, Node t, Arc a) const
[100]2493#endif
2494    {
[139]2495      if (_right[a] != INVALID) {
[209]2496        a = _right[a];
2497        while (_left[a] != INVALID) {
2498          a = _left[a];
2499        }
2500        const_cast<DynArcLookUp&>(*this).splay(a);
[100]2501      } else {
[209]2502        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
2503          a = _parent[a];
2504        }
2505        if (_parent[a] == INVALID) {
2506          return INVALID;
2507        } else {
2508          a = _parent[a];
2509          const_cast<DynArcLookUp&>(*this).splay(a);
2510        }
[100]2511      }
[139]2512      if (_g.target(a) == t) return a;
[209]2513      else return INVALID;
[100]2514    }
2515
2516  };
2517
2518  ///Fast arc look up between given endpoints.
[209]2519
[100]2520  ///\ingroup gutils
2521  ///Using this class, you can find an arc in a digraph from a given
2522  ///source to a given target in time <em>O(log d)</em>,
2523  ///where <em>d</em> is the out-degree of the source node.
2524  ///
2525  ///It is not possible to find \e all parallel arcs between two nodes.
2526  ///Use \ref AllArcLookUp for this purpose.
2527  ///
2528  ///\warning This class is static, so you should refresh() (or at least
2529  ///refresh(Node)) this data structure
2530  ///whenever the digraph changes. This is a time consuming (superlinearly
2531  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
2532  ///
[157]2533  ///\tparam G The type of the underlying digraph.
[100]2534  ///
2535  ///\sa DynArcLookUp
[209]2536  ///\sa AllArcLookUp
[100]2537  template<class G>
[209]2538  class ArcLookUp
[100]2539  {
2540  public:
[148]2541    TEMPLATE_DIGRAPH_TYPEDEFS(G);
[100]2542    typedef G Digraph;
2543
2544  protected:
2545    const Digraph &_g;
2546    typename Digraph::template NodeMap<Arc> _head;
2547    typename Digraph::template ArcMap<Arc> _left;
2548    typename Digraph::template ArcMap<Arc> _right;
[209]2549
[100]2550    class ArcLess {
2551      const Digraph &g;
2552    public:
2553      ArcLess(const Digraph &_g) : g(_g) {}
[209]2554      bool operator()(Arc a,Arc b) const
[100]2555      {
[209]2556        return g.target(a)<g.target(b);
[100]2557      }
2558    };
[209]2559
[100]2560  public:
[209]2561
[100]2562    ///Constructor
2563
2564    ///Constructor.
2565    ///
2566    ///It builds up the search database, which remains valid until the digraph
2567    ///changes.
2568    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
[209]2569
[100]2570  private:
[209]2571    Arc refreshRec(std::vector<Arc> &v,int a,int b)
[100]2572    {
2573      int m=(a+b)/2;
2574      Arc me=v[m];
2575      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2576      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
2577      return me;
2578    }
2579  public:
2580    ///Refresh the data structure at a node.
2581
2582    ///Build up the search database of node \c n.
2583    ///
2584    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2585    ///the number of the outgoing arcs of \c n.
[209]2586    void refresh(Node n)
[100]2587    {
2588      std::vector<Arc> v;
2589      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2590      if(v.size()) {
[209]2591        std::sort(v.begin(),v.end(),ArcLess(_g));
2592        _head[n]=refreshRec(v,0,v.size()-1);
[100]2593      }
2594      else _head[n]=INVALID;
2595    }
2596    ///Refresh the full data structure.
2597
2598    ///Build up the full search database. In fact, it simply calls
2599    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2600    ///
2601    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2602    ///the number of the arcs of \c n and <em>D</em> is the maximum
2603    ///out-degree of the digraph.
2604
[209]2605    void refresh()
[100]2606    {
2607      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2608    }
[209]2609
[100]2610    ///Find an arc between two nodes.
[209]2611
[100]2612    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
2613    /// <em>d</em> is the number of outgoing arcs of \c s.
2614    ///\param s The source node
2615    ///\param t The target node
2616    ///\return An arc from \c s to \c t if there exists,
2617    ///\ref INVALID otherwise.
2618    ///
2619    ///\warning If you change the digraph, refresh() must be called before using
2620    ///this operator. If you change the outgoing arcs of
2621    ///a single node \c n, then
2622    ///\ref refresh(Node) "refresh(n)" is enough.
2623    ///
2624    Arc operator()(Node s, Node t) const
2625    {
2626      Arc e;
2627      for(e=_head[s];
[209]2628          e!=INVALID&&_g.target(e)!=t;
2629          e = t < _g.target(e)?_left[e]:_right[e]) ;
[100]2630      return e;
2631    }
2632
2633  };
2634
2635  ///Fast look up of all arcs between given endpoints.
[209]2636
[100]2637  ///\ingroup gutils
2638  ///This class is the same as \ref ArcLookUp, with the addition
2639  ///that it makes it possible to find all arcs between given endpoints.
2640  ///
2641  ///\warning This class is static, so you should refresh() (or at least
2642  ///refresh(Node)) this data structure
2643  ///whenever the digraph changes. This is a time consuming (superlinearly
2644  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
2645  ///
[157]2646  ///\tparam G The type of the underlying digraph.
[100]2647  ///
2648  ///\sa DynArcLookUp
[209]2649  ///\sa ArcLookUp
[100]2650  template<class G>
2651  class AllArcLookUp : public ArcLookUp<G>
2652  {
2653    using ArcLookUp<G>::_g;
2654    using ArcLookUp<G>::_right;
2655    using ArcLookUp<G>::_left;
2656    using ArcLookUp<G>::_head;
2657
[148]2658    TEMPLATE_DIGRAPH_TYPEDEFS(G);
[100]2659    typedef G Digraph;
[209]2660
[100]2661    typename Digraph::template ArcMap<Arc> _next;
[209]2662
[100]2663    Arc refreshNext(Arc head,Arc next=INVALID)
2664    {
2665      if(head==INVALID) return next;
2666      else {
[209]2667        next=refreshNext(_right[head],next);
2668//         _next[head]=next;
2669        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2670          ? next : INVALID;
2671        return refreshNext(_left[head],head);
[100]2672      }
2673    }
[209]2674
[100]2675    void refreshNext()
2676    {
2677      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2678    }
[209]2679
[100]2680  public:
2681    ///Constructor
2682
2683    ///Constructor.
2684    ///
2685    ///It builds up the search database, which remains valid until the digraph
2686    ///changes.
2687    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
2688
2689    ///Refresh the data structure at a node.
2690
2691    ///Build up the search database of node \c n.
2692    ///
2693    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2694    ///the number of the outgoing arcs of \c n.
[209]2695
2696    void refresh(Node n)
[100]2697    {
2698      ArcLookUp<G>::refresh(n);
2699      refreshNext(_head[n]);
2700    }
[209]2701
[100]2702    ///Refresh the full data structure.
2703
2704    ///Build up the full search database. In fact, it simply calls
2705    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2706    ///
2707    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2708    ///the number of the arcs of \c n and <em>D</em> is the maximum
2709    ///out-degree of the digraph.
2710
[209]2711    void refresh()
[100]2712    {
2713      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2714    }
[209]2715
[100]2716    ///Find an arc between two nodes.
[209]2717
[100]2718    ///Find an arc between two nodes.
2719    ///\param s The source node
2720    ///\param t The target node
2721    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
2722    ///not given, the operator finds the first appropriate arc.
2723    ///\return An arc from \c s to \c t after \c prev or
2724    ///\ref INVALID if there is no more.
2725    ///
2726    ///For example, you can count the number of arcs from \c u to \c v in the
2727    ///following way.
2728    ///\code
2729    ///AllArcLookUp<ListDigraph> ae(g);
2730    ///...
2731    ///int n=0;
2732    ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
2733    ///\endcode
2734    ///
2735    ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
2736    /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
2737    ///consecutive arcs are found in constant time.
2738    ///
2739    ///\warning If you change the digraph, refresh() must be called before using
2740    ///this operator. If you change the outgoing arcs of
2741    ///a single node \c n, then
2742    ///\ref refresh(Node) "refresh(n)" is enough.
2743    ///
2744#ifdef DOXYGEN
2745    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
2746#else
2747    using ArcLookUp<G>::operator() ;
2748    Arc operator()(Node s, Node t, Arc prev) const
2749    {
2750      return prev==INVALID?(*this)(s,t):_next[prev];
2751    }
2752#endif
[209]2753
[100]2754  };
2755
2756  /// @}
2757
2758} //END OF NAMESPACE LEMON
2759
2760#endif
Note: See TracBrowser for help on using the repository browser.