COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/graph_utils.h @ 244:c30731a37f91

Last change on this file since 244:c30731a37f91 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
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
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
38///\brief Graph utilities.
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,
49  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
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.
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;                               \
67  typedef Digraph::ArcMap<double> DoubleArcMap
68
69  ///Creates convenience typedefs for the digraph types and iterators
70
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.
75#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
76  typedef typename Digraph::Node Node;                                  \
77  typedef typename Digraph::NodeIt NodeIt;                              \
78  typedef typename Digraph::Arc Arc;                                    \
79  typedef typename Digraph::ArcIt ArcIt;                                \
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;             \
87  typedef typename Digraph::template ArcMap<double> DoubleArcMap
88
89  ///Creates convenience typedefs for the graph types and iterators
90
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.
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.
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;                               \
106  typedef Graph::EdgeMap<double> DoubleEdgeMap
107
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.
114#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
115  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
116  typedef typename Graph::Edge Edge;                                    \
117  typedef typename Graph::EdgeIt EdgeIt;                                \
118  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
119  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
120  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
121  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
122
123  /// \brief Function to count the items in the graph.
124  ///
125  /// This function counts the items (nodes, arcs etc) in the graph.
126  /// The complexity of the function is O(n) because
127  /// it iterates on all of the items.
128  template <typename Graph, typename Item>
129  inline int countItems(const Graph& g) {
130    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
131    int num = 0;
132    for (ItemIt it(g); it != INVALID; ++it) {
133      ++num;
134    }
135    return num;
136  }
137
138  // Node counting:
139
140  namespace _graph_utils_bits {
141
142    template <typename Graph, typename Enable = void>
143    struct CountNodesSelector {
144      static int count(const Graph &g) {
145        return countItems<Graph, typename Graph::Node>(g);
146      }
147    };
148
149    template <typename Graph>
150    struct CountNodesSelector<
151      Graph, typename
152      enable_if<typename Graph::NodeNumTag, void>::type>
153    {
154      static int count(const Graph &g) {
155        return g.nodeNum();
156      }
157    };
158  }
159
160  /// \brief Function to count the nodes in the graph.
161  ///
162  /// This function counts the nodes in the graph.
163  /// The complexity of the function is O(n) but for some
164  /// graph structures it is specialized to run in O(1).
165  ///
166  /// If the graph contains a \e nodeNum() member function and a
167  /// \e NodeNumTag tag then this function calls directly the member
168  /// function to query the cardinality of the node set.
169  template <typename Graph>
170  inline int countNodes(const Graph& g) {
171    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
172  }
173
174  // Arc counting:
175
176  namespace _graph_utils_bits {
177
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);
182      }
183    };
184
185    template <typename Graph>
186    struct CountArcsSelector<
187      Graph,
188      typename enable_if<typename Graph::ArcNumTag, void>::type>
189    {
190      static int count(const Graph &g) {
191        return g.arcNum();
192      }
193    };
194  }
195
196  /// \brief Function to count the arcs in the graph.
197  ///
198  /// This function counts the arcs in the graph.
199  /// The complexity of the function is O(e) but for some
200  /// graph structures it is specialized to run in O(1).
201  ///
202  /// If the graph contains a \e arcNum() member function and a
203  /// \e EdgeNumTag tag then this function calls directly the member
204  /// function to query the cardinality of the arc set.
205  template <typename Graph>
206  inline int countArcs(const Graph& g) {
207    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
208  }
209
210  // Edge counting:
211  namespace _graph_utils_bits {
212
213    template <typename Graph, typename Enable = void>
214    struct CountEdgesSelector {
215      static int count(const Graph &g) {
216        return countItems<Graph, typename Graph::Edge>(g);
217      }
218    };
219
220    template <typename Graph>
221    struct CountEdgesSelector<
222      Graph,
223      typename enable_if<typename Graph::EdgeNumTag, void>::type>
224    {
225      static int count(const Graph &g) {
226        return g.edgeNum();
227      }
228    };
229  }
230
231  /// \brief Function to count the edges in the graph.
232  ///
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).
236  ///
237  /// If the graph contains a \e edgeNum() member function and a
238  /// \e EdgeNumTag tag then this function calls directly the member
239  /// function to query the cardinality of the edge set.
240  template <typename Graph>
241  inline int countEdges(const Graph& g) {
242    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
243
244  }
245
246
247  template <typename Graph, typename DegIt>
248  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
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
259  /// in the graph.
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);
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
268  /// in the graph.
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);
272  }
273
274  /// \brief Function to count the number of the inc-edges to node \c n.
275  ///
276  /// This function counts the number of the inc-edges to node \c n
277  /// in the graph.
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);
281  }
282
283  namespace _graph_utils_bits {
284
285    template <typename Graph, typename Enable = void>
286    struct FindArcSelector {
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) {
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
302    template <typename Graph>
303    struct FindArcSelector<
304      Graph,
305      typename enable_if<typename Graph::FindEdgeTag, void>::type>
306    {
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) {
310        return g.findArc(u, v, prev);
311      }
312    };
313  }
314
315  /// \brief Finds an arc between two nodes of a graph.
316  ///
317  /// Finds an arc from node \c u to node \c v in graph \c g.
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
335  template <typename Graph>
336  inline typename Graph::Arc
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);
340  }
341
342  /// \brief Iterator for iterating on arcs connected the same nodes.
343  ///
344  /// Iterator for iterating on arcs connected the same nodes. It is
345  /// higher level interface for the findArc() function. You can
346  /// use it the following way:
347  ///\code
348  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
349  ///   ...
350  /// }
351  ///\endcode
352  ///
353  ///\sa findArc()
354  ///\sa ArcLookUp
355  ///\sa AllArcLookUp
356  ///\sa DynArcLookUp
357  template <typename _Graph>
358  class ConArcIt : public _Graph::Arc {
359  public:
360
361    typedef _Graph Graph;
362    typedef typename Graph::Arc Parent;
363
364    typedef typename Graph::Arc Arc;
365    typedef typename Graph::Node Node;
366
367    /// \brief Constructor.
368    ///
369    /// Construct a new ConArcIt iterating on the arcs which
370    /// connects the \c u and \c v node.
371    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
372      Parent::operator=(findArc(_graph, u, v));
373    }
374
375    /// \brief Constructor.
376    ///
377    /// Construct a new ConArcIt which continues the iterating from
378    /// the \c e arc.
379    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
380
381    /// \brief Increment operator.
382    ///
383    /// It increments the iterator and gives back the next arc.
384    ConArcIt& operator++() {
385      Parent::operator=(findArc(_graph, _graph.source(*this),
386                                _graph.target(*this), *this));
387      return *this;
388    }
389  private:
390    const Graph& _graph;
391  };
392
393  namespace _graph_utils_bits {
394
395    template <typename Graph, typename Enable = void>
396    struct FindEdgeSelector {
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) {
400        bool b;
401        if (u != v) {
402          if (e == INVALID) {
403            g.firstInc(e, b, u);
404          } else {
405            b = g.u(e) == u;
406            g.nextInc(e, b);
407          }
408          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
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          }
418          while (e != INVALID && (!b || g.v(e) != v)) {
419            g.nextInc(e, b);
420          }
421        }
422        return e;
423      }
424    };
425
426    template <typename Graph>
427    struct FindEdgeSelector<
428      Graph,
429      typename enable_if<typename Graph::FindEdgeTag, void>::type>
430    {
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) {
434        return g.findEdge(u, v, prev);
435      }
436    };
437  }
438
439  /// \brief Finds an edge between two nodes of a graph.
440  ///
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.
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
452  /// for(Edge e = findEdge(g,u,v); e != INVALID;
453  ///     e = findEdge(g,u,v,e)) {
454  ///   ...
455  /// }
456  ///\endcode
457  ///
458  ///\sa ConEdgeIt
459
460  template <typename Graph>
461  inline typename Graph::Edge
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);
465  }
466
467  /// \brief Iterator for iterating on edges connected the same nodes.
468  ///
469  /// Iterator for iterating on edges connected the same nodes. It is
470  /// higher level interface for the findEdge() function. You can
471  /// use it the following way:
472  ///\code
473  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
474  ///   ...
475  /// }
476  ///\endcode
477  ///
478  ///\sa findEdge()
479  template <typename _Graph>
480  class ConEdgeIt : public _Graph::Edge {
481  public:
482
483    typedef _Graph Graph;
484    typedef typename Graph::Edge Parent;
485
486    typedef typename Graph::Edge Edge;
487    typedef typename Graph::Node Node;
488
489    /// \brief Constructor.
490    ///
491    /// Construct a new ConEdgeIt iterating on the edges which
492    /// connects the \c u and \c v node.
493    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
494      Parent::operator=(findEdge(_graph, u, v));
495    }
496
497    /// \brief Constructor.
498    ///
499    /// Construct a new ConEdgeIt which continues the iterating from
500    /// the \c e edge.
501    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
502
503    /// \brief Increment operator.
504    ///
505    /// It increments the iterator and gives back the next edge.
506    ConEdgeIt& operator++() {
507      Parent::operator=(findEdge(_graph, _graph.u(*this),
508                                 _graph.v(*this), *this));
509      return *this;
510    }
511  private:
512    const Graph& _graph;
513  };
514
515  namespace _graph_utils_bits {
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;
521
522      virtual ~MapCopyBase() {}
523    };
524
525    template <typename Digraph, typename Item, typename RefMap,
526              typename ToMap, typename FromMap>
527    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
528    public:
529
530      MapCopy(ToMap& tmap, const FromMap& map)
531        : _tmap(tmap), _map(map) {}
532
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) {}
550
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) {}
565
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
577    template <typename Digraph, typename Item, typename RefMap,
578              typename CrossRef>
579    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
580    public:
581
582      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
583
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) {
604          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
605                                    nodeRefMap[from.target(it)]);
606        }
607      }
608    };
609
610    template <typename Digraph>
611    struct DigraphCopySelector<
612      Digraph,
613      typename enable_if<typename Digraph::BuildTag, void>::type>
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) {
631          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
632                                      nodeRefMap[from.v(it)]);
633        }
634      }
635    };
636
637    template <typename Graph>
638    struct GraphCopySelector<
639      Graph,
640      typename enable_if<typename Graph::BuildTag, void>::type>
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.
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
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;
700
701
702  public:
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.
709    DigraphCopy(To& to, const From& from)
710      : _from(from), _to(to) {}
711
712    /// \brief Destructor of the DigraphCopy
713    ///
714    /// Destructor of the DigraphCopy
715    ~DigraphCopy() {
716      for (int i = 0; i < int(_node_maps.size()); ++i) {
717        delete _node_maps[i];
718      }
719      for (int i = 0; i < int(_arc_maps.size()); ++i) {
720        delete _arc_maps[i];
721      }
722
723    }
724
725    /// \brief Copies the node references into the given map.
726    ///
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.
731    template <typename NodeRef>
732    DigraphCopy& nodeRef(NodeRef& map) {
733      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
734                           NodeRefMap, NodeRef>(map));
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
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.
744    template <typename NodeCrossRef>
745    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
746      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
747                           NodeRefMap, NodeCrossRef>(map));
748      return *this;
749    }
750
751    /// \brief Make copy of the given map.
752    ///
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.
756    template <typename ToMap, typename FromMap>
757    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
758      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
759                           NodeRefMap, ToMap, FromMap>(tmap, map));
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) {
767      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
768                           NodeRefMap, TNode>(tnode, snode));
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) {
777      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
778                          ArcRefMap, ArcRef>(map));
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) {
788      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
789                          ArcRefMap, ArcCrossRef>(map));
790      return *this;
791    }
792
793    /// \brief Make copy of the given map.
794    ///
795    /// Makes copy of the given map for the newly created digraph.
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
798    /// type.
799    template <typename ToMap, typename FromMap>
800    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
801      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
802                          ArcRefMap, ToMap, FromMap>(tmap, map));
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) {
810      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
811                          ArcRefMap, TArc>(tarc, sarc));
812      return *this;
813    }
814
815    /// \brief Executes the copies.
816    ///
817    /// Executes the copies.
818    void run() {
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);
825      }
826      for (int i = 0; i < int(_arc_maps.size()); ++i) {
827        _arc_maps[i]->copy(_from, arcRefMap);
828      }
829    }
830
831  protected:
832
833
834    const From& _from;
835    To& _to;
836
837    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
838    _node_maps;
839
840    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
841    _arc_maps;
842
843  };
844
845  /// \brief Copy a digraph to another digraph.
846  ///
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:
850  ///\code
851  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
852  ///\endcode
853  ///
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  ///
859  /// \see DigraphCopy
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
865  /// \brief Class to copy a graph.
866  ///
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
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 {
919      ArcRefMap(const To& to, const From& from,
920                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
921        : _to(to), _from(from),
922          _edge_ref(edge_ref), _node_ref(node_ref) {}
923
924      typedef typename From::Arc Key;
925      typedef typename To::Arc Value;
926
927      Value operator[](const Key& key) const {
928        bool forward = _from.u(key) != _from.v(key) ?
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);
933      }
934
935      const To& _to;
936      const From& _from;
937      const EdgeRefMap& _edge_ref;
938      const NodeRefMap& _node_ref;
939    };
940
941
942  public:
943
944
945    /// \brief Constructor for the GraphCopy.
946    ///
947    /// It copies the content of the \c _from graph into the
948    /// \c _to graph.
949    GraphCopy(To& to, const From& from)
950      : _from(from), _to(to) {}
951
952    /// \brief Destructor of the GraphCopy
953    ///
954    /// Destructor of the GraphCopy
955    ~GraphCopy() {
956      for (int i = 0; i < int(_node_maps.size()); ++i) {
957        delete _node_maps[i];
958      }
959      for (int i = 0; i < int(_arc_maps.size()); ++i) {
960        delete _arc_maps[i];
961      }
962      for (int i = 0; i < int(_edge_maps.size()); ++i) {
963        delete _edge_maps[i];
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) {
973      _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
974                           NodeRefMap, NodeRef>(map));
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) {
984      _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
985                           NodeRefMap, NodeCrossRef>(map));
986      return *this;
987    }
988
989    /// \brief Make copy of the given map.
990    ///
991    /// Makes copy of the given map for the newly created graph.
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
994    /// type.
995    template <typename ToMap, typename FromMap>
996    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
997      _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
998                           NodeRefMap, ToMap, FromMap>(tmap, map));
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) {
1006      _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1007                           NodeRefMap, TNode>(tnode, snode));
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) {
1016      _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1017                          ArcRefMap, ArcRef>(map));
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) {
1027      _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
1028                          ArcRefMap, ArcCrossRef>(map));
1029      return *this;
1030    }
1031
1032    /// \brief Make copy of the given map.
1033    ///
1034    /// Makes copy of the given map for the newly created graph.
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
1037    /// type.
1038    template <typename ToMap, typename FromMap>
1039    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1040      _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1041                          ArcRefMap, ToMap, FromMap>(tmap, map));
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) {
1049      _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1050                          ArcRefMap, TArc>(tarc, sarc));
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) {
1059      _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1060                           EdgeRefMap, EdgeRef>(map));
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) {
1070      _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
1071                           Edge, EdgeRefMap, EdgeCrossRef>(map));
1072      return *this;
1073    }
1074
1075    /// \brief Make copy of the given map.
1076    ///
1077    /// Makes copy of the given map for the newly created graph.
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
1080    /// type.
1081    template <typename ToMap, typename FromMap>
1082    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1083      _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1084                           EdgeRefMap, ToMap, FromMap>(tmap, map));
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) {
1092      _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1093                           EdgeRefMap, TEdge>(tedge, sedge));
1094      return *this;
1095    }
1096
1097    /// \brief Executes the copies.
1098    ///
1099    /// Executes the copies.
1100    void run() {
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);
1108      }
1109      for (int i = 0; i < int(_edge_maps.size()); ++i) {
1110        _edge_maps[i]->copy(_from, edgeRefMap);
1111      }
1112      for (int i = 0; i < int(_arc_maps.size()); ++i) {
1113        _arc_maps[i]->copy(_from, arcRefMap);
1114      }
1115    }
1116
1117  private:
1118
1119    const From& _from;
1120    To& _to;
1121
1122    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1123    _node_maps;
1124
1125    std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1126    _arc_maps;
1127
1128    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1129    _edge_maps;
1130
1131  };
1132
1133  /// \brief Copy a graph to another graph.
1134  ///
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:
1138  ///\code
1139  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1140  ///\endcode
1141  ///
1142  /// After the copy the \c nr map will contain the mapping from the
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.
1146  ///
1147  /// \see GraphCopy
1148  template <typename To, typename From>
1149  GraphCopy<To, From>
1150  copyGraph(To& to, const From& from) {
1151    return GraphCopy<To, From>(to, from);
1152  }
1153
1154  /// @}
1155
1156  /// \addtogroup graph_maps
1157  /// @{
1158
1159  /// Provides an immutable and unique id for each item in the graph.
1160
1161  /// The IdMap class provides a unique and immutable id for each item of the
1162  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
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
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.
1168  ///
1169  template <typename _Graph, typename _Item>
1170  class IdMap {
1171  public:
1172    typedef _Graph Graph;
1173    typedef int Value;
1174    typedef _Item Item;
1175    typedef _Item Key;
1176
1177    /// \brief Constructor.
1178    ///
1179    /// Constructor of the map.
1180    explicit IdMap(const Graph& graph) : _graph(&graph) {}
1181
1182    /// \brief Gives back the \e id of the item.
1183    ///
1184    /// Gives back the immutable and unique \e id of the item.
1185    int operator[](const Item& item) const { return _graph->id(item);}
1186
1187    /// \brief Gives back the item by its id.
1188    ///
1189    /// Gives back the item by its id.
1190    Item operator()(int id) { return _graph->fromId(id, Item()); }
1191
1192  private:
1193    const Graph* _graph;
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.
1207      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1208
1209      /// \brief Constructor.
1210      ///
1211      /// Constructor for creating an id-to-item map.
1212      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1213
1214      /// \brief Gives back the given item from its id.
1215      ///
1216      /// Gives back the given item from its id.
1217      ///
1218      Item operator[](int id) const { return _graph->fromId(id, Item());}
1219
1220    private:
1221      const Graph* _graph;
1222    };
1223
1224    /// \brief Gives back the inverse of the map.
1225    ///
1226    /// Gives back the inverse of the IdMap.
1227    InverseMap inverse() const { return InverseMap(*_graph);}
1228
1229  };
1230
1231
1232  /// \brief General invertable graph-map type.
1233
1234  /// This type provides simple invertable graph-maps.
1235  /// The InvertableMap wraps an arbitrary ReadWriteMap
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  ///
1242  /// \tparam _Graph The graph type.
1243  /// \tparam _Item The item type of the graph.
1244  /// \tparam _Value The value type of the map.
1245  ///
1246  /// \see IterableValueMap
1247  template <typename _Graph, typename _Item, typename _Value>
1248  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1249  private:
1250
1251    typedef DefaultMap<_Graph, _Item, _Value> Map;
1252    typedef _Graph Graph;
1253
1254    typedef std::map<_Value, _Item> Container;
1255    Container _inv_map;
1256
1257  public:
1258
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    ///
1268    /// Construct a new InvertableMap for the graph.
1269    ///
1270    explicit InvertableMap(const Graph& graph) : Map(graph) {}
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    ///
1278    class ValueIterator
1279      : public std::iterator<std::forward_iterator_tag, Value> {
1280      friend class InvertableMap;
1281    private:
1282      ValueIterator(typename Container::const_iterator _it)
1283        : it(_it) {}
1284    public:
1285
1286      ValueIterator() {}
1287
1288      ValueIterator& operator++() { ++it; return *this; }
1289      ValueIterator operator++(int) {
1290        ValueIterator tmp(*this);
1291        operator++();
1292        return tmp;
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; }
1300
1301    private:
1302      typename Container::const_iterator it;
1303    };
1304
1305    /// \brief Returns an iterator to the first value.
1306    ///
1307    /// Returns an stl compatible iterator to the
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 {
1312      return ValueIterator(_inv_map.begin());
1313    }
1314
1315    /// \brief Returns an iterator after the last value.
1316    ///
1317    /// Returns an stl compatible iterator after the
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 {
1322      return ValueIterator(_inv_map.end());
1323    }
1324
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);
1330      typename Container::iterator it = _inv_map.find(oldval);
1331      if (it != _inv_map.end() && it->second == key) {
1332        _inv_map.erase(it);
1333      }
1334      _inv_map.insert(make_pair(val, key));
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.
1341    typename MapTraits<Map>::ConstReturnValue
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 {
1350      typename Container::const_iterator it = _inv_map.find(key);
1351      return it != _inv_map.end() ? it->second : INVALID;
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);
1362      typename Container::iterator it = _inv_map.find(val);
1363      if (it != _inv_map.end() && it->second == key) {
1364        _inv_map.erase(it);
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) {
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        }
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() {
1389      _inv_map.clear();
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
1398    /// gives back always the item what was last assigned to the value.
1399    class InverseMap {
1400    public:
1401      /// \brief Constructor of the InverseMap.
1402      ///
1403      /// Constructor of the InverseMap.
1404      explicit InverseMap(const InvertableMap& inverted)
1405        : _inverted(inverted) {}
1406
1407      /// The value type of the InverseMap.
1408      typedef typename InvertableMap::Key Value;
1409      /// The key type of the InverseMap.
1410      typedef typename InvertableMap::Value Key;
1411
1412      /// \brief Subscript operator.
1413      ///
1414      /// Subscript operator. It gives back always the item
1415      /// what was last assigned to the value.
1416      Value operator[](const Key& key) const {
1417        return _inverted(key);
1418      }
1419
1420    private:
1421      const InvertableMap& _inverted;
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);
1429    }
1430
1431
1432
1433  };
1434
1435  /// \brief Provides a mutable, continuous and unique descriptor for each
1436  /// item in the graph.
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
1440  /// graph. This id is <ul><li>\b unique: different items (nodes) get
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
1445  /// with its member class \c InverseMap, or with the \c operator() member.
1446  ///
1447  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
1448  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
1449  /// Edge.
1450  template <typename _Graph, typename _Item>
1451  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1452
1453    typedef _Item Item;
1454    typedef DefaultMap<_Graph, _Item, int> Map;
1455
1456  public:
1457    /// The graph class of DescriptorMap.
1458    typedef _Graph Graph;
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.
1468    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1469      Item it;
1470      const typename Map::Notifier* nf = Map::notifier();
1471      for (nf->first(it); it != INVALID; nf->next(it)) {
1472        Map::set(it, _inv_map.size());
1473        _inv_map.push_back(it);
1474      }
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);
1485      Map::set(item, _inv_map.size());
1486      _inv_map.push_back(item);
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) {
1496        Map::set(items[i], _inv_map.size());
1497        _inv_map.push_back(items[i]);
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) {
1506      Map::set(_inv_map.back(), Map::operator[](item));
1507      _inv_map[Map::operator[](item)] = _inv_map.back();
1508      _inv_map.pop_back();
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) {
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();
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;
1532      const typename Map::Notifier* nf = Map::notifier();
1533      for (nf->first(it); it != INVALID; nf->next(it)) {
1534        Map::set(it, _inv_map.size());
1535        _inv_map.push_back(it);
1536      }
1537    }
1538
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() {
1544      _inv_map.clear();
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 {
1554      return _inv_map.size();
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);
1564      _inv_map[qi] = p;
1565      Map::set(q, pi);
1566      _inv_map[pi] = q;
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 {
1580      return _inv_map[id];
1581    }
1582
1583  private:
1584
1585    typedef std::vector<Item> Container;
1586    Container _inv_map;
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.
1597      explicit InverseMap(const DescriptorMap& inverted)
1598        : _inverted(inverted) {}
1599
1600
1601      /// The value type of the InverseMap.
1602      typedef typename DescriptorMap::Key Value;
1603      /// The key type of the InverseMap.
1604      typedef typename DescriptorMap::Value Key;
1605
1606      /// \brief Subscript operator.
1607      ///
1608      /// Subscript operator. It gives back the item
1609      /// that the descriptor belongs to currently.
1610      Value operator[](const Key& key) const {
1611        return _inverted(key);
1612      }
1613
1614      /// \brief Size of the map.
1615      ///
1616      /// Returns the size of the map.
1617      unsigned int size() const {
1618        return _inverted.size();
1619      }
1620
1621    private:
1622      const DescriptorMap& _inverted;
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  ///
1635  /// The SourceMap gives back the source Node of the given arc.
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.
1648    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
1649
1650    /// \brief The subscript operator.
1651    ///
1652    /// The subscript operator.
1653    /// \param arc The arc
1654    /// \return The source of the arc
1655    Value operator[](const Key& arc) const {
1656      return _digraph.source(arc);
1657    }
1658
1659  private:
1660    const Digraph& _digraph;
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);
1670  }
1671
1672  /// \brief Returns the target of the given arc.
1673  ///
1674  /// The TargetMap gives back the target Node of the given arc.
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.
1687    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
1688
1689    /// \brief The subscript operator.
1690    ///
1691    /// The subscript operator.
1692    /// \param e The arc
1693    /// \return The target of the arc
1694    Value operator[](const Key& e) const {
1695      return _digraph.target(e);
1696    }
1697
1698  private:
1699    const Digraph& _digraph;
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
1715  template <typename Graph>
1716  class ForwardMap {
1717  public:
1718
1719    typedef typename Graph::Arc Value;
1720    typedef typename Graph::Edge Key;
1721
1722    /// \brief Constructor
1723    ///
1724    /// Constructor
1725    /// \param _graph The graph that the map belongs to.
1726    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
1727
1728    /// \brief The subscript operator.
1729    ///
1730    /// The subscript operator.
1731    /// \param key An edge
1732    /// \return The "forward" directed arc view of edge
1733    Value operator[](const Key& key) const {
1734      return _graph.direct(key, true);
1735    }
1736
1737  private:
1738    const Graph& _graph;
1739  };
1740
1741  /// \brief Returns a \ref ForwardMap class.
1742  ///
1743  /// This function just returns an \ref ForwardMap class.
1744  /// \relates ForwardMap
1745  template <typename Graph>
1746  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1747    return ForwardMap<Graph>(graph);
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
1754  template <typename Graph>
1755  class BackwardMap {
1756  public:
1757
1758    typedef typename Graph::Arc Value;
1759    typedef typename Graph::Edge Key;
1760
1761    /// \brief Constructor
1762    ///
1763    /// Constructor
1764    /// \param _graph The graph that the map belongs to.
1765    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
1766
1767    /// \brief The subscript operator.
1768    ///
1769    /// The subscript operator.
1770    /// \param key An edge
1771    /// \return The "backward" directed arc view of edge
1772    Value operator[](const Key& key) const {
1773      return _graph.direct(key, false);
1774    }
1775
1776  private:
1777    const Graph& _graph;
1778  };
1779
1780  /// \brief Returns a \ref BackwardMap class
1781
1782  /// This function just returns a \ref BackwardMap class.
1783  /// \relates BackwardMap
1784  template <typename Graph>
1785  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1786    return BackwardMap<Graph>(graph);
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
1803    explicit PotentialDifferenceMap(const Digraph& digraph,
1804                                    const NodeMap& potential)
1805      : _digraph(digraph), _potential(potential) {}
1806
1807    /// \brief Const subscription operator
1808    ///
1809    /// Const subscription operator
1810    Value operator[](const Key& arc) const {
1811      return _potential[_digraph.target(arc)] -
1812        _potential[_digraph.source(arc)];
1813    }
1814
1815  private:
1816    const Digraph& _digraph;
1817    const NodeMap& _potential;
1818  };
1819
1820  /// \brief Returns a PotentialDifferenceMap.
1821  ///
1822  /// This function just returns a PotentialDifferenceMap.
1823  /// \relates PotentialDifferenceMap
1824  template <typename Digraph, typename NodeMap>
1825  PotentialDifferenceMap<Digraph, NodeMap>
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>
1848  class InDegMap
1849    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1850      ::ItemNotifier::ObserverBase {
1851
1852  public:
1853
1854    typedef _Digraph Digraph;
1855    typedef int Value;
1856    typedef typename Digraph::Node Key;
1857
1858    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1859    ::ItemNotifier::ObserverBase Parent;
1860
1861  private:
1862
1863    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1864    public:
1865
1866      typedef DefaultMap<Digraph, Key, int> Parent;
1867
1868      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1869
1870      virtual void add(const Key& key) {
1871        Parent::add(key);
1872        Parent::set(key, 0);
1873      }
1874
1875      virtual void add(const std::vector<Key>& keys) {
1876        Parent::add(keys);
1877        for (int i = 0; i < int(keys.size()); ++i) {
1878          Parent::set(keys[i], 0);
1879        }
1880      }
1881
1882      virtual void build() {
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        }
1889      }
1890    };
1891
1892  public:
1893
1894    /// \brief Constructor.
1895    ///
1896    /// Constructor for creating in-degree map.
1897    explicit InDegMap(const Digraph& digraph)
1898      : _digraph(digraph), _deg(digraph) {
1899      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1900
1901      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1902        _deg[it] = countInArcs(_digraph, it);
1903      }
1904    }
1905
1906    /// Gives back the in-degree of a Node.
1907    int operator[](const Key& key) const {
1908      return _deg[key];
1909    }
1910
1911  protected:
1912
1913    typedef typename Digraph::Arc Arc;
1914
1915    virtual void add(const Arc& arc) {
1916      ++_deg[_digraph.target(arc)];
1917    }
1918
1919    virtual void add(const std::vector<Arc>& arcs) {
1920      for (int i = 0; i < int(arcs.size()); ++i) {
1921        ++_deg[_digraph.target(arcs[i])];
1922      }
1923    }
1924
1925    virtual void erase(const Arc& arc) {
1926      --_deg[_digraph.target(arc)];
1927    }
1928
1929    virtual void erase(const std::vector<Arc>& arcs) {
1930      for (int i = 0; i < int(arcs.size()); ++i) {
1931        --_deg[_digraph.target(arcs[i])];
1932      }
1933    }
1934
1935    virtual void build() {
1936      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1937        _deg[it] = countInArcs(_digraph, it);
1938      }
1939    }
1940
1941    virtual void clear() {
1942      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1943        _deg[it] = 0;
1944      }
1945    }
1946  private:
1947
1948    const Digraph& _digraph;
1949    AutoNodeMap _deg;
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>
1970  class OutDegMap
1971    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1972      ::ItemNotifier::ObserverBase {
1973
1974  public:
1975
1976    typedef _Digraph Digraph;
1977    typedef int Value;
1978    typedef typename Digraph::Node Key;
1979
1980    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1981    ::ItemNotifier::ObserverBase Parent;
1982
1983  private:
1984
1985    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1986    public:
1987
1988      typedef DefaultMap<Digraph, Key, int> Parent;
1989
1990      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1991
1992      virtual void add(const Key& key) {
1993        Parent::add(key);
1994        Parent::set(key, 0);
1995      }
1996      virtual void add(const std::vector<Key>& keys) {
1997        Parent::add(keys);
1998        for (int i = 0; i < int(keys.size()); ++i) {
1999          Parent::set(keys[i], 0);
2000        }
2001      }
2002      virtual void build() {
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        }
2009      }
2010    };
2011
2012  public:
2013
2014    /// \brief Constructor.
2015    ///
2016    /// Constructor for creating out-degree map.
2017    explicit OutDegMap(const Digraph& digraph)
2018      : _digraph(digraph), _deg(digraph) {
2019      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2020
2021      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2022        _deg[it] = countOutArcs(_digraph, it);
2023      }
2024    }
2025
2026    /// Gives back the out-degree of a Node.
2027    int operator[](const Key& key) const {
2028      return _deg[key];
2029    }
2030
2031  protected:
2032
2033    typedef typename Digraph::Arc Arc;
2034
2035    virtual void add(const Arc& arc) {
2036      ++_deg[_digraph.source(arc)];
2037    }
2038
2039    virtual void add(const std::vector<Arc>& arcs) {
2040      for (int i = 0; i < int(arcs.size()); ++i) {
2041        ++_deg[_digraph.source(arcs[i])];
2042      }
2043    }
2044
2045    virtual void erase(const Arc& arc) {
2046      --_deg[_digraph.source(arc)];
2047    }
2048
2049    virtual void erase(const std::vector<Arc>& arcs) {
2050      for (int i = 0; i < int(arcs.size()); ++i) {
2051        --_deg[_digraph.source(arcs[i])];
2052      }
2053    }
2054
2055    virtual void build() {
2056      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2057        _deg[it] = countOutArcs(_digraph, it);
2058      }
2059    }
2060
2061    virtual void clear() {
2062      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2063        _deg[it] = 0;
2064      }
2065    }
2066  private:
2067
2068    const Digraph& _digraph;
2069    AutoNodeMap _deg;
2070  };
2071
2072
2073  ///Dynamic arc look up between given endpoints.
2074
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
2084  ///digraph is not changed so frequently.
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  ///
2092  ///\tparam G The type of the underlying digraph.
2093  ///
2094  ///\sa ArcLookUp
2095  ///\sa AllArcLookUp
2096  template<class G>
2097  class DynArcLookUp
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
2104    TEMPLATE_DIGRAPH_TYPEDEFS(G);
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) {}
2115
2116      virtual void add(const Node& node) {
2117        Parent::add(node);
2118        Parent::set(node, INVALID);
2119      }
2120
2121      virtual void add(const std::vector<Node>& nodes) {
2122        Parent::add(nodes);
2123        for (int i = 0; i < int(nodes.size()); ++i) {
2124          Parent::set(nodes[i], INVALID);
2125        }
2126      }
2127
2128      virtual void build() {
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        }
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;
2143
2144    class ArcLess {
2145      const Digraph &g;
2146    public:
2147      ArcLess(const Digraph &_g) : g(_g) {}
2148      bool operator()(Arc a,Arc b) const
2149      {
2150        return g.target(a)<g.target(b);
2151      }
2152    };
2153
2154  public:
2155
2156    ///Constructor
2157
2158    ///Constructor.
2159    ///
2160    ///It builds up the search database.
2161    DynArcLookUp(const Digraph &g)
2162      : _g(g),_head(g),_parent(g),_left(g),_right(g)
2163    {
2164      Parent::attach(_g.notifier(typename Digraph::Arc()));
2165      refresh();
2166    }
2167
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) {
2176        insert(arcs[i]);
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) {
2186        remove(arcs[i]);
2187      }
2188    }
2189
2190    virtual void build() {
2191      refresh();
2192    }
2193
2194    virtual void clear() {
2195      for(NodeIt n(_g);n!=INVALID;++n) {
2196        _head.set(n, INVALID);
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);
2205
2206      Arc e = _head[s];
2207      if (e == INVALID) {
2208        _head.set(s, arc);
2209        _parent.set(arc, INVALID);
2210        return;
2211      }
2212      while (true) {
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        }
2232      }
2233    }
2234
2235    void remove(Arc arc) {
2236      if (_left[arc] == INVALID) {
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        }
2249      } else if (_right[arc] == INVALID) {
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        }
2260      } else {
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        }
2301      }
2302    }
2303
2304    Arc refreshRec(std::vector<Arc> &v,int a,int b)
2305    {
2306      int m=(a+b)/2;
2307      Arc me=v[m];
2308      if (a < m) {
2309        Arc left = refreshRec(v,a,m-1);
2310        _left.set(me, left);
2311        _parent.set(left, me);
2312      } else {
2313        _left.set(me, INVALID);
2314      }
2315      if (m < b) {
2316        Arc right = refreshRec(v,m+1,b);
2317        _right.set(me, right);
2318        _parent.set(right, me);
2319      } else {
2320        _right.set(me, INVALID);
2321      }
2322      return me;
2323    }
2324
2325    void refresh() {
2326      for(NodeIt n(_g);n!=INVALID;++n) {
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);
2336      }
2337    }
2338
2339    void zig(Arc v) {
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) {
2346        if (_right[_parent[v]] == w) {
2347          _right.set(_parent[v], v);
2348        } else {
2349          _left.set(_parent[v], v);
2350        }
2351      }
2352      if (_left[w] != INVALID){
2353        _parent.set(_left[w], w);
2354      }
2355    }
2356
2357    void zag(Arc v) {
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){
2364        if (_left[_parent[v]] == w) {
2365          _left.set(_parent[v], v);
2366        } else {
2367          _right.set(_parent[v], v);
2368        }
2369      }
2370      if (_right[w] != INVALID){
2371        _parent.set(_right[w], w);
2372      }
2373    }
2374
2375    void splay(Arc v) {
2376      while (_parent[v] != INVALID) {
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        }
2402      }
2403      _head[_g.source(v)] = v;
2404    }
2405
2406
2407  public:
2408
2409    ///Find an arc between two nodes.
2410
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    {
2419      Arc a = _head[s];
2420      while (true) {
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        }
2439      }
2440    }
2441
2442    ///Find the first arc between two nodes.
2443
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
2446    /// outgoing arcs of \c s.
2447    ///\param s The source node
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    {
2453      Arc a = _head[s];
2454      Arc r = INVALID;
2455      while (true) {
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        }
2474      }
2475    }
2476
2477    ///Find the next arc between two nodes.
2478
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
2481    /// outgoing arcs of \c s.
2482    ///\param s The source node
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
2490    Arc findNext(Node s, Node t, Arc a) const
2491#else
2492    Arc findNext(Node, Node t, Arc a) const
2493#endif
2494    {
2495      if (_right[a] != INVALID) {
2496        a = _right[a];
2497        while (_left[a] != INVALID) {
2498          a = _left[a];
2499        }
2500        const_cast<DynArcLookUp&>(*this).splay(a);
2501      } else {
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        }
2511      }
2512      if (_g.target(a) == t) return a;
2513      else return INVALID;
2514    }
2515
2516  };
2517
2518  ///Fast arc look up between given endpoints.
2519
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  ///
2533  ///\tparam G The type of the underlying digraph.
2534  ///
2535  ///\sa DynArcLookUp
2536  ///\sa AllArcLookUp
2537  template<class G>
2538  class ArcLookUp
2539  {
2540  public:
2541    TEMPLATE_DIGRAPH_TYPEDEFS(G);
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;
2549
2550    class ArcLess {
2551      const Digraph &g;
2552    public:
2553      ArcLess(const Digraph &_g) : g(_g) {}
2554      bool operator()(Arc a,Arc b) const
2555      {
2556        return g.target(a)<g.target(b);
2557      }
2558    };
2559
2560  public:
2561
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();}
2569
2570  private:
2571    Arc refreshRec(std::vector<Arc> &v,int a,int b)
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.
2586    void refresh(Node n)
2587    {
2588      std::vector<Arc> v;
2589      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2590      if(v.size()) {
2591        std::sort(v.begin(),v.end(),ArcLess(_g));
2592        _head[n]=refreshRec(v,0,v.size()-1);
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
2605    void refresh()
2606    {
2607      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2608    }
2609
2610    ///Find an arc between two nodes.
2611
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];
2628          e!=INVALID&&_g.target(e)!=t;
2629          e = t < _g.target(e)?_left[e]:_right[e]) ;
2630      return e;
2631    }
2632
2633  };
2634
2635  ///Fast look up of all arcs between given endpoints.
2636
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  ///
2646  ///\tparam G The type of the underlying digraph.
2647  ///
2648  ///\sa DynArcLookUp
2649  ///\sa ArcLookUp
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
2658    TEMPLATE_DIGRAPH_TYPEDEFS(G);
2659    typedef G Digraph;
2660
2661    typename Digraph::template ArcMap<Arc> _next;
2662
2663    Arc refreshNext(Arc head,Arc next=INVALID)
2664    {
2665      if(head==INVALID) return next;
2666      else {
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);
2672      }
2673    }
2674
2675    void refreshNext()
2676    {
2677      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2678    }
2679
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.
2695
2696    void refresh(Node n)
2697    {
2698      ArcLookUp<G>::refresh(n);
2699      refreshNext(_head[n]);
2700    }
2701
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
2711    void refresh()
2712    {
2713      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2714    }
2715
2716    ///Find an arc between two nodes.
2717
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
2753
2754  };
2755
2756  /// @}
2757
2758} //END OF NAMESPACE LEMON
2759
2760#endif
Note: See TracBrowser for help on using the repository browser.