COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/graph_utils.h @ 148:4e2581021300

Last change on this file since 148:4e2581021300 was 148:4e2581021300, checked in by Balazs Dezso <deba@…>, 11 years ago

Revert 356930927a71 and add TEMPLATE_GRAPH_TYPEDEFS instead (ticket #89)

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