COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2287:16954ac69517

Last change on this file since 2287:16954ac69517 was 2287:16954ac69517, checked in by Balazs Dezso, 13 years ago

Removing template Map template parameter from InvertableMaps?

File size: 63.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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///
40///
41
42
43namespace lemon {
44
45  /// \addtogroup gutils
46  /// @{
47
48  ///Creates convenience typedefs for the graph types and iterators
49
50  ///This \c \#define creates convenience typedefs for the following types
51  ///of \c Graph: \c Node,  \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
52  ///\c OutEdgeIt
53  ///\note If \c G it a template parameter, it should be used in this way.
54  ///\code
55  ///  GRAPH_TYPEDEFS(typename G)
56  ///\endcode
57  ///
58  ///\warning There are no typedefs for the graph maps because of the lack of
59  ///template typedefs in C++.
60#define GRAPH_TYPEDEFS(Graph)                           \
61  typedef Graph::     Node      Node;                   \
62    typedef Graph::   NodeIt    NodeIt;                 \
63    typedef Graph::   Edge      Edge;                   \
64    typedef Graph::   EdgeIt    EdgeIt;                 \
65    typedef Graph:: InEdgeIt  InEdgeIt;                 \
66    typedef Graph::OutEdgeIt OutEdgeIt;                 
67
68  ///Creates convenience typedefs for the undirected graph types and iterators
69
70  ///This \c \#define creates the same convenience typedefs as defined by
71  ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
72  ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
73  ///
74  ///\note If \c G it a template parameter, it should be used in this way.
75  ///\code
76  ///  UGRAPH_TYPEDEFS(typename G)
77  ///\endcode
78  ///
79  ///\warning There are no typedefs for the graph maps because of the lack of
80  ///template typedefs in C++.
81#define UGRAPH_TYPEDEFS(Graph)                          \
82  GRAPH_TYPEDEFS(Graph)                                         \
83    typedef Graph:: UEdge   UEdge;                      \
84    typedef Graph:: UEdgeIt UEdgeIt;                    \
85    typedef Graph:: IncEdgeIt   IncEdgeIt;                     
86
87  ///\brief Creates convenience typedefs for the bipartite undirected graph
88  ///types and iterators
89
90  ///This \c \#define creates the same convenience typedefs as defined by
91  ///\ref UGRAPH_TYPEDEFS(Graph) and two more, namely it creates
92  ///\c ANodeIt, \c BNodeIt,
93  ///
94  ///\note If \c G it a template parameter, it should be used in this way.
95  ///\code
96  ///  BPUGRAPH_TYPEDEFS(typename G)
97  ///\endcode
98  ///
99  ///\warning There are no typedefs for the graph maps because of the lack of
100  ///template typedefs in C++.
101#define BPUGRAPH_TYPEDEFS(Graph)            \
102  UGRAPH_TYPEDEFS(Graph)                    \
103    typedef Graph::ANode ANode;             \
104    typedef Graph::BNode BNode;             \
105    typedef Graph::ANodeIt ANodeIt;         \
106    typedef Graph::BNodeIt BNodeIt;
107
108  /// \brief Function to count the items in the graph.
109  ///
110  /// This function counts the items (nodes, edges etc) in the graph.
111  /// The complexity of the function is O(n) because
112  /// it iterates on all of the items.
113
114  template <typename Graph, typename Item>
115  inline int countItems(const Graph& g) {
116    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
117    int num = 0;
118    for (ItemIt it(g); it != INVALID; ++it) {
119      ++num;
120    }
121    return num;
122  }
123
124  // Node counting:
125
126  namespace _graph_utils_bits {
127   
128    template <typename Graph, typename Enable = void>
129    struct CountNodesSelector {
130      static int count(const Graph &g) {
131        return countItems<Graph, typename Graph::Node>(g);
132      }
133    };
134
135    template <typename Graph>
136    struct CountNodesSelector<
137      Graph, typename
138      enable_if<typename Graph::NodeNumTag, void>::type>
139    {
140      static int count(const Graph &g) {
141        return g.nodeNum();
142      }
143    };   
144  }
145
146  /// \brief Function to count the nodes in the graph.
147  ///
148  /// This function counts the nodes in the graph.
149  /// The complexity of the function is O(n) but for some
150  /// graph structures it is specialized to run in O(1).
151  ///
152  /// \todo refer how to specialize it
153
154  template <typename Graph>
155  inline int countNodes(const Graph& g) {
156    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
157  }
158
159  namespace _graph_utils_bits {
160   
161    template <typename Graph, typename Enable = void>
162    struct CountANodesSelector {
163      static int count(const Graph &g) {
164        return countItems<Graph, typename Graph::ANode>(g);
165      }
166    };
167
168    template <typename Graph>
169    struct CountANodesSelector<
170      Graph, typename
171      enable_if<typename Graph::NodeNumTag, void>::type>
172    {
173      static int count(const Graph &g) {
174        return g.aNodeNum();
175      }
176    };   
177  }
178
179  /// \brief Function to count the anodes in the graph.
180  ///
181  /// This function counts the anodes in the graph.
182  /// The complexity of the function is O(an) but for some
183  /// graph structures it is specialized to run in O(1).
184  ///
185  /// \todo refer how to specialize it
186
187  template <typename Graph>
188  inline int countANodes(const Graph& g) {
189    return _graph_utils_bits::CountANodesSelector<Graph>::count(g);
190  }
191
192  namespace _graph_utils_bits {
193   
194    template <typename Graph, typename Enable = void>
195    struct CountBNodesSelector {
196      static int count(const Graph &g) {
197        return countItems<Graph, typename Graph::BNode>(g);
198      }
199    };
200
201    template <typename Graph>
202    struct CountBNodesSelector<
203      Graph, typename
204      enable_if<typename Graph::NodeNumTag, void>::type>
205    {
206      static int count(const Graph &g) {
207        return g.bNodeNum();
208      }
209    };   
210  }
211
212  /// \brief Function to count the bnodes in the graph.
213  ///
214  /// This function counts the bnodes in the graph.
215  /// The complexity of the function is O(bn) but for some
216  /// graph structures it is specialized to run in O(1).
217  ///
218  /// \todo refer how to specialize it
219
220  template <typename Graph>
221  inline int countBNodes(const Graph& g) {
222    return _graph_utils_bits::CountBNodesSelector<Graph>::count(g);
223  }
224
225
226  // Edge counting:
227
228  namespace _graph_utils_bits {
229   
230    template <typename Graph, typename Enable = void>
231    struct CountEdgesSelector {
232      static int count(const Graph &g) {
233        return countItems<Graph, typename Graph::Edge>(g);
234      }
235    };
236
237    template <typename Graph>
238    struct CountEdgesSelector<
239      Graph,
240      typename enable_if<typename Graph::EdgeNumTag, void>::type>
241    {
242      static int count(const Graph &g) {
243        return g.edgeNum();
244      }
245    };   
246  }
247
248  /// \brief Function to count the edges in the graph.
249  ///
250  /// This function counts the edges in the graph.
251  /// The complexity of the function is O(e) but for some
252  /// graph structures it is specialized to run in O(1).
253
254  template <typename Graph>
255  inline int countEdges(const Graph& g) {
256    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
257  }
258
259  // Undirected edge counting:
260  namespace _graph_utils_bits {
261   
262    template <typename Graph, typename Enable = void>
263    struct CountUEdgesSelector {
264      static int count(const Graph &g) {
265        return countItems<Graph, typename Graph::UEdge>(g);
266      }
267    };
268
269    template <typename Graph>
270    struct CountUEdgesSelector<
271      Graph,
272      typename enable_if<typename Graph::EdgeNumTag, void>::type>
273    {
274      static int count(const Graph &g) {
275        return g.uEdgeNum();
276      }
277    };   
278  }
279
280  /// \brief Function to count the undirected edges in the graph.
281  ///
282  /// This function counts the undirected edges in the graph.
283  /// The complexity of the function is O(e) but for some
284  /// graph structures it is specialized to run in O(1).
285
286  template <typename Graph>
287  inline int countUEdges(const Graph& g) {
288    return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
289
290  }
291
292
293  template <typename Graph, typename DegIt>
294  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
295    int num = 0;
296    for (DegIt it(_g, _n); it != INVALID; ++it) {
297      ++num;
298    }
299    return num;
300  }
301
302  /// \brief Function to count the number of the out-edges from node \c n.
303  ///
304  /// This function counts the number of the out-edges from node \c n
305  /// in the graph. 
306  template <typename Graph>
307  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
308    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
309  }
310
311  /// \brief Function to count the number of the in-edges to node \c n.
312  ///
313  /// This function counts the number of the in-edges to node \c n
314  /// in the graph. 
315  template <typename Graph>
316  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
317    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
318  }
319
320  /// \brief Function to count the number of the inc-edges to node \c n.
321  ///
322  /// This function counts the number of the inc-edges to node \c n
323  /// in the graph. 
324  template <typename Graph>
325  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
326    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
327  }
328
329  namespace _graph_utils_bits {
330   
331    template <typename Graph, typename Enable = void>
332    struct FindEdgeSelector {
333      typedef typename Graph::Node Node;
334      typedef typename Graph::Edge Edge;
335      static Edge find(const Graph &g, Node u, Node v, Edge e) {
336        if (e == INVALID) {
337          g.firstOut(e, u);
338        } else {
339          g.nextOut(e);
340        }
341        while (e != INVALID && g.target(e) != v) {
342          g.nextOut(e);
343        }
344        return e;
345      }
346    };
347
348    template <typename Graph>
349    struct FindEdgeSelector<
350      Graph,
351      typename enable_if<typename Graph::FindEdgeTag, void>::type>
352    {
353      typedef typename Graph::Node Node;
354      typedef typename Graph::Edge Edge;
355      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
356        return g.findEdge(u, v, prev);
357      }
358    };   
359  }
360
361  /// \brief Finds an edge between two nodes of a graph.
362  ///
363  /// Finds an edge from node \c u to node \c v in graph \c g.
364  ///
365  /// If \c prev is \ref INVALID (this is the default value), then
366  /// it finds the first edge from \c u to \c v. Otherwise it looks for
367  /// the next edge from \c u to \c v after \c prev.
368  /// \return The found edge or \ref INVALID if there is no such an edge.
369  ///
370  /// Thus you can iterate through each edge from \c u to \c v as it follows.
371  ///\code
372  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
373  ///   ...
374  /// }
375  ///\endcode
376  ///
377  ///\sa EdgeLookUp
378  ///\se AllEdgeLookup
379  ///\sa ConEdgeIt
380  template <typename Graph>
381  inline typename Graph::Edge
382  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
383           typename Graph::Edge prev = INVALID) {
384    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
385  }
386
387  /// \brief Iterator for iterating on edges connected the same nodes.
388  ///
389  /// Iterator for iterating on edges connected the same nodes. It is
390  /// higher level interface for the findEdge() function. You can
391  /// use it the following way:
392  ///\code
393  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
394  ///   ...
395  /// }
396  ///\endcode
397  ///
398  ///\sa findEdge()
399  ///\sa EdgeLookUp
400  ///\se AllEdgeLookup
401  ///
402  /// \author Balazs Dezso
403  template <typename _Graph>
404  class ConEdgeIt : public _Graph::Edge {
405  public:
406
407    typedef _Graph Graph;
408    typedef typename Graph::Edge Parent;
409
410    typedef typename Graph::Edge Edge;
411    typedef typename Graph::Node Node;
412
413    /// \brief Constructor.
414    ///
415    /// Construct a new ConEdgeIt iterating on the edges which
416    /// connects the \c u and \c v node.
417    ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
418      Parent::operator=(findEdge(graph, u, v));
419    }
420
421    /// \brief Constructor.
422    ///
423    /// Construct a new ConEdgeIt which continues the iterating from
424    /// the \c e edge.
425    ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
426   
427    /// \brief Increment operator.
428    ///
429    /// It increments the iterator and gives back the next edge.
430    ConEdgeIt& operator++() {
431      Parent::operator=(findEdge(graph, graph.source(*this),
432                                 graph.target(*this), *this));
433      return *this;
434    }
435  private:
436    const Graph& graph;
437  };
438
439  namespace _graph_utils_bits {
440   
441    template <typename Graph, typename Enable = void>
442    struct FindUEdgeSelector {
443      typedef typename Graph::Node Node;
444      typedef typename Graph::UEdge UEdge;
445      static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
446        bool b;
447        if (u != v) {
448          if (e == INVALID) {
449            g.firstInc(e, b, u);
450          } else {
451            b = g.source(e) == u;
452            g.nextInc(e, b);
453          }
454          while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
455            g.nextInc(e, b);
456          }
457        } else {
458          if (e == INVALID) {
459            g.firstInc(e, b, u);
460          } else {
461            b = true;
462            g.nextInc(e, b);
463          }
464          while (e != INVALID && (!b || g.target(e) != v)) {
465            g.nextInc(e, b);
466          }
467        }
468        return e;
469      }
470    };
471
472    template <typename Graph>
473    struct FindUEdgeSelector<
474      Graph,
475      typename enable_if<typename Graph::FindEdgeTag, void>::type>
476    {
477      typedef typename Graph::Node Node;
478      typedef typename Graph::UEdge UEdge;
479      static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
480        return g.findUEdge(u, v, prev);
481      }
482    };   
483  }
484
485  /// \brief Finds an uedge between two nodes of a graph.
486  ///
487  /// Finds an uedge from node \c u to node \c v in graph \c g.
488  /// If the node \c u and node \c v is equal then each loop edge
489  /// will be enumerated.
490  ///
491  /// If \c prev is \ref INVALID (this is the default value), then
492  /// it finds the first edge from \c u to \c v. Otherwise it looks for
493  /// the next edge from \c u to \c v after \c prev.
494  /// \return The found edge or \ref INVALID if there is no such an edge.
495  ///
496  /// Thus you can iterate through each edge from \c u to \c v as it follows.
497  ///\code
498  /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
499  ///     e = findUEdge(g,u,v,e)) {
500  ///   ...
501  /// }
502  ///\endcode
503  ///
504  ///\sa ConEdgeIt
505
506  template <typename Graph>
507  inline typename Graph::UEdge
508  findUEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
509            typename Graph::UEdge p = INVALID) {
510    return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
511  }
512
513  /// \brief Iterator for iterating on uedges connected the same nodes.
514  ///
515  /// Iterator for iterating on uedges connected the same nodes. It is
516  /// higher level interface for the findUEdge() function. You can
517  /// use it the following way:
518  ///\code
519  /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
520  ///   ...
521  /// }
522  ///\endcode
523  ///
524  ///\sa findUEdge()
525  ///
526  /// \author Balazs Dezso
527  template <typename _Graph>
528  class ConUEdgeIt : public _Graph::UEdge {
529  public:
530
531    typedef _Graph Graph;
532    typedef typename Graph::UEdge Parent;
533
534    typedef typename Graph::UEdge UEdge;
535    typedef typename Graph::Node Node;
536
537    /// \brief Constructor.
538    ///
539    /// Construct a new ConUEdgeIt iterating on the edges which
540    /// connects the \c u and \c v node.
541    ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
542      Parent::operator=(findUEdge(graph, u, v));
543    }
544
545    /// \brief Constructor.
546    ///
547    /// Construct a new ConUEdgeIt which continues the iterating from
548    /// the \c e edge.
549    ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
550   
551    /// \brief Increment operator.
552    ///
553    /// It increments the iterator and gives back the next edge.
554    ConUEdgeIt& operator++() {
555      Parent::operator=(findUEdge(graph, graph.source(*this),
556                                      graph.target(*this), *this));
557      return *this;
558    }
559  private:
560    const Graph& graph;
561  };
562
563  /// \brief Copy a map.
564  ///
565  /// This function copies the \c source map to the \c target map. It uses the
566  /// given iterator to iterate on the data structure and it uses the \c ref
567  /// mapping to convert the source's keys to the target's keys.
568  template <typename Target, typename Source,
569            typename ItemIt, typename Ref>         
570  void copyMap(Target& target, const Source& source,
571               ItemIt it, const Ref& ref) {
572    for (; it != INVALID; ++it) {
573      target[ref[it]] = source[it];
574    }
575  }
576
577  /// \brief Copy the source map to the target map.
578  ///
579  /// Copy the \c source map to the \c target map. It uses the given iterator
580  /// to iterate on the data structure.
581  template <typename Target, typename Source, typename ItemIt>     
582  void copyMap(Target& target, const Source& source, ItemIt it) {
583    for (; it != INVALID; ++it) {
584      target[it] = source[it];
585    }
586  }
587
588  namespace _graph_utils_bits {
589
590    template <typename Graph, typename Item, typename RefMap>
591    class MapCopyBase {
592    public:
593      virtual void copy(const Graph& source, const RefMap& refMap) = 0;
594     
595      virtual ~MapCopyBase() {}
596    };
597
598    template <typename Graph, typename Item, typename RefMap,
599              typename TargetMap, typename SourceMap>
600    class MapCopy : public MapCopyBase<Graph, Item, RefMap> {
601    public:
602
603      MapCopy(TargetMap& tmap, const SourceMap& map)
604        : _tmap(tmap), _map(map) {}
605     
606      virtual void copy(const Graph& graph, const RefMap& refMap) {
607        typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
608        for (ItemIt it(graph); it != INVALID; ++it) {
609          _tmap.set(refMap[it], _map[it]);
610        }
611      }
612
613    private:
614      TargetMap& _tmap;
615      const SourceMap& _map;
616    };
617
618    template <typename Graph, typename Item, typename RefMap, typename Ref>
619    class RefCopy : public MapCopyBase<Graph, Item, RefMap> {
620    public:
621
622      RefCopy(Ref& map) : _map(map) {}
623     
624      virtual void copy(const Graph& graph, const RefMap& refMap) {
625        typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
626        for (ItemIt it(graph); it != INVALID; ++it) {
627          _map.set(it, refMap[it]);
628        }
629      }
630
631    private:
632      Ref& _map;
633    };
634
635    template <typename Graph, typename Item, typename RefMap,
636              typename CrossRef>
637    class CrossRefCopy : public MapCopyBase<Graph, Item, RefMap> {
638    public:
639
640      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
641     
642      virtual void copy(const Graph& graph, const RefMap& refMap) {
643        typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
644        for (ItemIt it(graph); it != INVALID; ++it) {
645          _cmap.set(refMap[it], it);
646        }
647      }
648
649    private:
650      CrossRef& _cmap;
651    };
652
653  }
654
655  /// \brief Class to copy a graph.
656  ///
657  /// Class to copy a graph to another graph (duplicate a graph). The
658  /// simplest way of using it is through the \c copyGraph() function.
659  template <typename Target, typename Source>
660  class GraphCopy {
661  private:
662
663    typedef typename Source::Node Node;
664    typedef typename Source::NodeIt NodeIt;
665    typedef typename Source::Edge Edge;
666    typedef typename Source::EdgeIt EdgeIt;
667
668    typedef typename Target::Node TNode;
669    typedef typename Target::Edge TEdge;
670
671    typedef typename Source::template NodeMap<TNode> NodeRefMap;
672    typedef typename Source::template EdgeMap<TEdge> EdgeRefMap;
673   
674   
675  public:
676
677
678    /// \brief Constructor for the GraphCopy.
679    ///
680    /// It copies the content of the \c _source graph into the
681    /// \c _target graph.
682    GraphCopy(Target& _target, const Source& _source)
683      : source(_source), target(_target) {}
684
685    /// \brief Destructor of the GraphCopy
686    ///
687    /// Destructor of the GraphCopy
688    ~GraphCopy() {
689      for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
690        delete nodeMapCopies[i];
691      }
692      for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
693        delete edgeMapCopies[i];
694      }
695
696    }
697
698    /// \brief Copies the node references into the given map.
699    ///
700    /// Copies the node references into the given map.
701    template <typename NodeRef>
702    GraphCopy& nodeRef(NodeRef& map) {
703      nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
704                              NodeRefMap, NodeRef>(map));
705      return *this;
706    }
707
708    /// \brief Reverse and copies the node references into the given map.
709    ///
710    /// Reverse and copies the node references into the given map.
711    template <typename NodeCrossRef>
712    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
713      nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
714                              NodeRefMap, NodeCrossRef>(map));
715      return *this;
716    }
717
718    /// \brief Make copy of the given map.
719    ///
720    /// Makes copy of the given map for the newly created graph.
721    /// The new map's key type is the target graph's node type,
722    /// and the copied map's key type is the source graph's node
723    /// type. 
724    template <typename TargetMap, typename SourceMap>
725    GraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
726      nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
727                              NodeRefMap, TargetMap, SourceMap>(tmap, map));
728      return *this;
729    }
730
731    /// \brief Copies the edge references into the given map.
732    ///
733    /// Copies the edge references into the given map.
734    template <typename EdgeRef>
735    GraphCopy& edgeRef(EdgeRef& map) {
736      edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
737                              EdgeRefMap, EdgeRef>(map));
738      return *this;
739    }
740
741    /// \brief Reverse and copies the edge references into the given map.
742    ///
743    /// Reverse and copies the edge references into the given map.
744    template <typename EdgeCrossRef>
745    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
746      edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
747                              EdgeRefMap, EdgeCrossRef>(map));
748      return *this;
749    }
750
751    /// \brief Make copy of the given map.
752    ///
753    /// Makes copy of the given map for the newly created graph.
754    /// The new map's key type is the target graph's edge type,
755    /// and the copied map's key type is the source graph's edge
756    /// type. 
757    template <typename TargetMap, typename SourceMap>
758    GraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
759      edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
760                              EdgeRefMap, TargetMap, SourceMap>(tmap, map));
761      return *this;
762    }
763
764    /// \brief Executes the copies.
765    ///
766    /// Executes the copies.
767    void run() {
768      NodeRefMap nodeRefMap(source);
769      for (NodeIt it(source); it != INVALID; ++it) {
770        nodeRefMap[it] = target.addNode();
771      }
772      for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
773        nodeMapCopies[i]->copy(source, nodeRefMap);
774      }
775      EdgeRefMap edgeRefMap(source);
776      for (EdgeIt it(source); it != INVALID; ++it) {
777        edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
778                                        nodeRefMap[source.target(it)]);
779      }
780      for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
781        edgeMapCopies[i]->copy(source, edgeRefMap);
782      }
783    }
784
785  private:
786   
787    const Source& source;
788    Target& target;
789
790    std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
791    nodeMapCopies;
792
793    std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
794    edgeMapCopies;
795
796  };
797
798  /// \brief Copy a graph to another graph.
799  ///
800  /// Copy a graph to another graph.
801  /// The usage of the function:
802  ///
803  ///\code
804  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
805  ///\endcode
806  ///
807  /// After the copy the \c nr map will contain the mapping from the
808  /// source graph's nodes to the target graph's nodes and the \c ecr will
809  /// contain the mapping from the target graph's edges to the source's
810  /// edges.
811  template <typename Target, typename Source>
812  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
813    return GraphCopy<Target, Source>(target, source);
814  }
815
816  /// \brief Class to copy an undirected graph.
817  ///
818  /// Class to copy an undirected graph to another graph (duplicate a graph).
819  /// The simplest way of using it is through the \c copyUGraph() function.
820  template <typename Target, typename Source>
821  class UGraphCopy {
822  private:
823
824    typedef typename Source::Node Node;
825    typedef typename Source::NodeIt NodeIt;
826    typedef typename Source::Edge Edge;
827    typedef typename Source::EdgeIt EdgeIt;
828    typedef typename Source::UEdge UEdge;
829    typedef typename Source::UEdgeIt UEdgeIt;
830
831    typedef typename Target::Node TNode;
832    typedef typename Target::Edge TEdge;
833    typedef typename Target::UEdge TUEdge;
834
835    typedef typename Source::template NodeMap<TNode> NodeRefMap;
836    typedef typename Source::template UEdgeMap<TUEdge> UEdgeRefMap;
837
838    struct EdgeRefMap {
839      EdgeRefMap(const Target& _target, const Source& _source,
840                 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
841        : target(_target), source(_source),
842          uedge_ref(_uedge_ref), node_ref(_node_ref) {}
843
844      typedef typename Source::Edge Key;
845      typedef typename Target::Edge Value;
846
847      Value operator[](const Key& key) const {
848        bool forward = (source.direction(key) ==
849                        (node_ref[source.source((UEdge)key)] ==
850                         target.source(uedge_ref[(UEdge)key])));
851        return target.direct(uedge_ref[key], forward);
852      }
853     
854      const Target& target;
855      const Source& source;
856      const UEdgeRefMap& uedge_ref;
857      const NodeRefMap& node_ref;
858    };
859
860   
861  public:
862
863
864    /// \brief Constructor for the GraphCopy.
865    ///
866    /// It copies the content of the \c _source graph into the
867    /// \c _target graph.
868    UGraphCopy(Target& _target, const Source& _source)
869      : source(_source), target(_target) {}
870
871    /// \brief Destructor of the GraphCopy
872    ///
873    /// Destructor of the GraphCopy
874    ~UGraphCopy() {
875      for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
876        delete nodeMapCopies[i];
877      }
878      for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
879        delete edgeMapCopies[i];
880      }
881      for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
882        delete uEdgeMapCopies[i];
883      }
884
885    }
886
887    /// \brief Copies the node references into the given map.
888    ///
889    /// Copies the node references into the given map.
890    template <typename NodeRef>
891    UGraphCopy& nodeRef(NodeRef& map) {
892      nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
893                              NodeRefMap, NodeRef>(map));
894      return *this;
895    }
896
897    /// \brief Reverse and copies the node references into the given map.
898    ///
899    /// Reverse and copies the node references into the given map.
900    template <typename NodeCrossRef>
901    UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
902      nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
903                              NodeRefMap, NodeCrossRef>(map));
904      return *this;
905    }
906
907    /// \brief Make copy of the given map.
908    ///
909    /// Makes copy of the given map for the newly created graph.
910    /// The new map's key type is the target graph's node type,
911    /// and the copied map's key type is the source graph's node
912    /// type. 
913    template <typename TargetMap, typename SourceMap>
914    UGraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
915      nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
916                              NodeRefMap, TargetMap, SourceMap>(tmap, map));
917      return *this;
918    }
919
920    /// \brief Copies the edge references into the given map.
921    ///
922    /// Copies the edge references into the given map.
923    template <typename EdgeRef>
924    UGraphCopy& edgeRef(EdgeRef& map) {
925      edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
926                              EdgeRefMap, EdgeRef>(map));
927      return *this;
928    }
929
930    /// \brief Reverse and copies the edge references into the given map.
931    ///
932    /// Reverse and copies the edge references into the given map.
933    template <typename EdgeCrossRef>
934    UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
935      edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
936                              EdgeRefMap, EdgeCrossRef>(map));
937      return *this;
938    }
939
940    /// \brief Make copy of the given map.
941    ///
942    /// Makes copy of the given map for the newly created graph.
943    /// The new map's key type is the target graph's edge type,
944    /// and the copied map's key type is the source graph's edge
945    /// type. 
946    template <typename TargetMap, typename SourceMap>
947    UGraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
948      edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
949                              EdgeRefMap, TargetMap, SourceMap>(tmap, map));
950      return *this;
951    }
952
953    /// \brief Copies the uEdge references into the given map.
954    ///
955    /// Copies the uEdge references into the given map.
956    template <typename UEdgeRef>
957    UGraphCopy& uEdgeRef(UEdgeRef& map) {
958      uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
959                               UEdgeRefMap, UEdgeRef>(map));
960      return *this;
961    }
962
963    /// \brief Reverse and copies the uEdge references into the given map.
964    ///
965    /// Reverse and copies the uEdge references into the given map.
966    template <typename UEdgeCrossRef>
967    UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
968      uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
969                               UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
970      return *this;
971    }
972
973    /// \brief Make copy of the given map.
974    ///
975    /// Makes copy of the given map for the newly created graph.
976    /// The new map's key type is the target graph's uEdge type,
977    /// and the copied map's key type is the source graph's uEdge
978    /// type. 
979    template <typename TargetMap, typename SourceMap>
980    UGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
981      uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, UEdge,
982                               UEdgeRefMap, TargetMap, SourceMap>(tmap, map));
983      return *this;
984    }
985
986    /// \brief Executes the copies.
987    ///
988    /// Executes the copies.
989    void run() {
990      NodeRefMap nodeRefMap(source);
991      for (NodeIt it(source); it != INVALID; ++it) {
992        nodeRefMap[it] = target.addNode();
993      }
994      for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
995        nodeMapCopies[i]->copy(source, nodeRefMap);
996      }
997      UEdgeRefMap uEdgeRefMap(source);
998      EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
999      for (UEdgeIt it(source); it != INVALID; ++it) {
1000        uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1001                                         nodeRefMap[source.target(it)]);
1002      }
1003      for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
1004        uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
1005      }
1006      for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1007        edgeMapCopies[i]->copy(source, edgeRefMap);
1008      }
1009    }
1010
1011  private:
1012   
1013    const Source& source;
1014    Target& target;
1015
1016    std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
1017    nodeMapCopies;
1018
1019    std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
1020    edgeMapCopies;
1021
1022    std::vector<_graph_utils_bits::MapCopyBase<Source, UEdge, UEdgeRefMap>* >
1023    uEdgeMapCopies;
1024
1025  };
1026
1027  /// \brief Copy a graph to another graph.
1028  ///
1029  /// Copy a graph to another graph.
1030  /// The usage of the function:
1031  ///
1032  ///\code
1033  /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
1034  ///\endcode
1035  ///
1036  /// After the copy the \c nr map will contain the mapping from the
1037  /// source graph's nodes to the target graph's nodes and the \c ecr will
1038  /// contain the mapping from the target graph's edges to the source's
1039  /// edges.
1040  template <typename Target, typename Source>
1041  UGraphCopy<Target, Source>
1042  copyUGraph(Target& target, const Source& source) {
1043    return UGraphCopy<Target, Source>(target, source);
1044  }
1045
1046
1047  /// @}
1048
1049  /// \addtogroup graph_maps
1050  /// @{
1051
1052  /// Provides an immutable and unique id for each item in the graph.
1053
1054  /// The IdMap class provides a unique and immutable id for each item of the
1055  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1056  /// different items (nodes) get different ids <li>\b immutable: the id of an
1057  /// item (node) does not change (even if you delete other nodes).  </ul>
1058  /// Through this map you get access (i.e. can read) the inner id values of
1059  /// the items stored in the graph. This map can be inverted with its member
1060  /// class \c InverseMap.
1061  ///
1062  template <typename _Graph, typename _Item>
1063  class IdMap {
1064  public:
1065    typedef _Graph Graph;
1066    typedef int Value;
1067    typedef _Item Item;
1068    typedef _Item Key;
1069
1070    /// \brief Constructor.
1071    ///
1072    /// Constructor for creating id map.
1073    explicit IdMap(const Graph& _graph) : graph(&_graph) {}
1074
1075    /// \brief Gives back the \e id of the item.
1076    ///
1077    /// Gives back the immutable and unique \e id of the map.
1078    int operator[](const Item& item) const { return graph->id(item);}
1079
1080
1081  private:
1082    const Graph* graph;
1083
1084  public:
1085
1086    /// \brief The class represents the inverse of its owner (IdMap).
1087    ///
1088    /// The class represents the inverse of its owner (IdMap).
1089    /// \see inverse()
1090    class InverseMap {
1091    public:
1092
1093      /// \brief Constructor.
1094      ///
1095      /// Constructor for creating an id-to-item map.
1096      explicit InverseMap(const Graph& _graph) : graph(&_graph) {}
1097
1098      /// \brief Constructor.
1099      ///
1100      /// Constructor for creating an id-to-item map.
1101      explicit InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
1102
1103      /// \brief Gives back the given item from its id.
1104      ///
1105      /// Gives back the given item from its id.
1106      ///
1107      Item operator[](int id) const { return graph->fromId(id, Item());}
1108    private:
1109      const Graph* graph;
1110    };
1111
1112    /// \brief Gives back the inverse of the map.
1113    ///
1114    /// Gives back the inverse of the IdMap.
1115    InverseMap inverse() const { return InverseMap(*graph);}
1116
1117  };
1118
1119 
1120  /// \brief General invertable graph-map type.
1121
1122  /// This type provides simple invertable graph-maps.
1123  /// The InvertableMap wraps an arbitrary ReadWriteMap
1124  /// and if a key is set to a new value then store it
1125  /// in the inverse map.
1126  ///
1127  /// The values of the map can be accessed
1128  /// with stl compatible forward iterator.
1129  ///
1130  /// \param _Graph The graph type.
1131  /// \param _Item The item type of the graph.
1132  /// \param _Value The value type of the map.
1133  ///
1134  /// \see IterableValueMap
1135  template <typename _Graph, typename _Item, typename _Value>
1136  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1137  private:
1138   
1139    typedef DefaultMap<_Graph, _Item, _Value> Map;
1140    typedef _Graph Graph;
1141
1142    typedef std::map<_Value, _Item> Container;
1143    Container invMap;   
1144
1145  public:
1146 
1147    /// The key type of InvertableMap (Node, Edge, UEdge).
1148    typedef typename Map::Key Key;
1149    /// The value type of the InvertableMap.
1150    typedef typename Map::Value Value;
1151
1152
1153
1154    /// \brief Constructor.
1155    ///
1156    /// Construct a new InvertableMap for the graph.
1157    ///
1158    explicit InvertableMap(const Graph& graph) : Map(graph) {}
1159
1160    /// \brief Forward iterator for values.
1161    ///
1162    /// This iterator is an stl compatible forward
1163    /// iterator on the values of the map. The values can
1164    /// be accessed in the [beginValue, endValue) range.
1165    ///
1166    class ValueIterator
1167      : public std::iterator<std::forward_iterator_tag, Value> {
1168      friend class InvertableMap;
1169    private:
1170      ValueIterator(typename Container::const_iterator _it)
1171        : it(_it) {}
1172    public:
1173     
1174      ValueIterator() {}
1175
1176      ValueIterator& operator++() { ++it; return *this; }
1177      ValueIterator operator++(int) {
1178        ValueIterator tmp(*this);
1179        operator++();
1180        return tmp;
1181      }
1182
1183      const Value& operator*() const { return it->first; }
1184      const Value* operator->() const { return &(it->first); }
1185
1186      bool operator==(ValueIterator jt) const { return it == jt.it; }
1187      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1188     
1189    private:
1190      typename Container::const_iterator it;
1191    };
1192
1193    /// \brief Returns an iterator to the first value.
1194    ///
1195    /// Returns an stl compatible iterator to the
1196    /// first value of the map. The values of the
1197    /// map can be accessed in the [beginValue, endValue)
1198    /// range.
1199    ValueIterator beginValue() const {
1200      return ValueIterator(invMap.begin());
1201    }
1202
1203    /// \brief Returns an iterator after the last value.
1204    ///
1205    /// Returns an stl compatible iterator after the
1206    /// last value of the map. The values of the
1207    /// map can be accessed in the [beginValue, endValue)
1208    /// range.
1209    ValueIterator endValue() const {
1210      return ValueIterator(invMap.end());
1211    }
1212   
1213    /// \brief The setter function of the map.
1214    ///
1215    /// Sets the mapped value.
1216    void set(const Key& key, const Value& val) {
1217      Value oldval = Map::operator[](key);
1218      typename Container::iterator it = invMap.find(oldval);
1219      if (it != invMap.end() && it->second == key) {
1220        invMap.erase(it);
1221      }     
1222      invMap.insert(make_pair(val, key));
1223      Map::set(key, val);
1224    }
1225
1226    /// \brief The getter function of the map.
1227    ///
1228    /// It gives back the value associated with the key.
1229    typename MapTraits<Map>::ConstReturnValue
1230    operator[](const Key& key) const {
1231      return Map::operator[](key);
1232    }
1233
1234  protected:
1235
1236    /// \brief Erase the key from the map.
1237    ///
1238    /// Erase the key to the map. It is called by the
1239    /// \c AlterationNotifier.
1240    virtual void erase(const Key& key) {
1241      Value val = Map::operator[](key);
1242      typename Container::iterator it = invMap.find(val);
1243      if (it != invMap.end() && it->second == key) {
1244        invMap.erase(it);
1245      }
1246      Map::erase(key);
1247    }
1248
1249    /// \brief Erase more keys from the map.
1250    ///
1251    /// Erase more keys from the map. It is called by the
1252    /// \c AlterationNotifier.
1253    virtual void erase(const std::vector<Key>& keys) {
1254      for (int i = 0; i < (int)keys.size(); ++i) {
1255        Value val = Map::operator[](keys[i]);
1256        typename Container::iterator it = invMap.find(val);
1257        if (it != invMap.end() && it->second == keys[i]) {
1258          invMap.erase(it);
1259        }
1260      }
1261      Map::erase(keys);
1262    }
1263
1264    /// \brief Clear the keys from the map and inverse map.
1265    ///
1266    /// Clear the keys from the map and inverse map. It is called by the
1267    /// \c AlterationNotifier.
1268    virtual void clear() {
1269      invMap.clear();
1270      Map::clear();
1271    }
1272
1273  public:
1274
1275    /// \brief The inverse map type.
1276    ///
1277    /// The inverse of this map. The subscript operator of the map
1278    /// gives back always the item what was last assigned to the value.
1279    class InverseMap {
1280    public:
1281      /// \brief Constructor of the InverseMap.
1282      ///
1283      /// Constructor of the InverseMap.
1284      explicit InverseMap(const InvertableMap& _inverted)
1285        : inverted(_inverted) {}
1286
1287      /// The value type of the InverseMap.
1288      typedef typename InvertableMap::Key Value;
1289      /// The key type of the InverseMap.
1290      typedef typename InvertableMap::Value Key;
1291
1292      /// \brief Subscript operator.
1293      ///
1294      /// Subscript operator. It gives back always the item
1295      /// what was last assigned to the value.
1296      Value operator[](const Key& key) const {
1297        typename Container::const_iterator it = inverted.invMap.find(key);
1298        return it->second;
1299      }
1300     
1301    private:
1302      const InvertableMap& inverted;
1303    };
1304
1305    /// \brief It gives back the just readable inverse map.
1306    ///
1307    /// It gives back the just readable inverse map.
1308    InverseMap inverse() const {
1309      return InverseMap(*this);
1310    }
1311
1312
1313   
1314  };
1315
1316  /// \brief Provides a mutable, continuous and unique descriptor for each
1317  /// item in the graph.
1318  ///
1319  /// The DescriptorMap class provides a unique and continuous (but mutable)
1320  /// descriptor (id) for each item of the same type (e.g. node) in the
1321  /// graph. This id is <ul><li>\b unique: different items (nodes) get
1322  /// different ids <li>\b continuous: the range of the ids is the set of
1323  /// integers between 0 and \c n-1, where \c n is the number of the items of
1324  /// this type (e.g. nodes) (so the id of a node can change if you delete an
1325  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
1326  /// with its member class \c InverseMap.
1327  ///
1328  /// \param _Graph The graph class the \c DescriptorMap belongs to.
1329  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1330  /// UEdge.
1331  template <typename _Graph, typename _Item>
1332  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1333
1334    typedef _Item Item;
1335    typedef DefaultMap<_Graph, _Item, int> Map;
1336
1337  public:
1338    /// The graph class of DescriptorMap.
1339    typedef _Graph Graph;
1340
1341    /// The key type of DescriptorMap (Node, Edge, UEdge).
1342    typedef typename Map::Key Key;
1343    /// The value type of DescriptorMap.
1344    typedef typename Map::Value Value;
1345
1346    /// \brief Constructor.
1347    ///
1348    /// Constructor for descriptor map.
1349    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1350      Item it;
1351      const typename Map::Notifier* notifier = Map::getNotifier();
1352      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1353        Map::set(it, invMap.size());
1354        invMap.push_back(it);   
1355      }     
1356    }
1357
1358  protected:
1359
1360    /// \brief Add a new key to the map.
1361    ///
1362    /// Add a new key to the map. It is called by the
1363    /// \c AlterationNotifier.
1364    virtual void add(const Item& item) {
1365      Map::add(item);
1366      Map::set(item, invMap.size());
1367      invMap.push_back(item);
1368    }
1369
1370    /// \brief Add more new keys to the map.
1371    ///
1372    /// Add more new keys to the map. It is called by the
1373    /// \c AlterationNotifier.
1374    virtual void add(const std::vector<Item>& items) {
1375      Map::add(items);
1376      for (int i = 0; i < (int)items.size(); ++i) {
1377        Map::set(items[i], invMap.size());
1378        invMap.push_back(items[i]);
1379      }
1380    }
1381
1382    /// \brief Erase the key from the map.
1383    ///
1384    /// Erase the key from the map. It is called by the
1385    /// \c AlterationNotifier.
1386    virtual void erase(const Item& item) {
1387      Map::set(invMap.back(), Map::operator[](item));
1388      invMap[Map::operator[](item)] = invMap.back();
1389      invMap.pop_back();
1390      Map::erase(item);
1391    }
1392
1393    /// \brief Erase more keys from the map.
1394    ///
1395    /// Erase more keys from the map. It is called by the
1396    /// \c AlterationNotifier.
1397    virtual void erase(const std::vector<Item>& items) {
1398      for (int i = 0; i < (int)items.size(); ++i) {
1399        Map::set(invMap.back(), Map::operator[](items[i]));
1400        invMap[Map::operator[](items[i])] = invMap.back();
1401        invMap.pop_back();
1402      }
1403      Map::erase(items);
1404    }
1405
1406    /// \brief Build the unique map.
1407    ///
1408    /// Build the unique map. It is called by the
1409    /// \c AlterationNotifier.
1410    virtual void build() {
1411      Map::build();
1412      Item it;
1413      const typename Map::Notifier* notifier = Map::getNotifier();
1414      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1415        Map::set(it, invMap.size());
1416        invMap.push_back(it);   
1417      }     
1418    }
1419   
1420    /// \brief Clear the keys from the map.
1421    ///
1422    /// Clear the keys from the map. It is called by the
1423    /// \c AlterationNotifier.
1424    virtual void clear() {
1425      invMap.clear();
1426      Map::clear();
1427    }
1428
1429  public:
1430
1431    /// \brief Returns the maximal value plus one.
1432    ///
1433    /// Returns the maximal value plus one in the map.
1434    unsigned int size() const {
1435      return invMap.size();
1436    }
1437
1438    /// \brief Swaps the position of the two items in the map.
1439    ///
1440    /// Swaps the position of the two items in the map.
1441    void swap(const Item& p, const Item& q) {
1442      int pi = Map::operator[](p);
1443      int qi = Map::operator[](q);
1444      Map::set(p, qi);
1445      invMap[qi] = p;
1446      Map::set(q, pi);
1447      invMap[pi] = q;
1448    }
1449
1450    /// \brief Gives back the \e descriptor of the item.
1451    ///
1452    /// Gives back the mutable and unique \e descriptor of the map.
1453    int operator[](const Item& item) const {
1454      return Map::operator[](item);
1455    }
1456   
1457  private:
1458
1459    typedef std::vector<Item> Container;
1460    Container invMap;
1461
1462  public:
1463    /// \brief The inverse map type of DescriptorMap.
1464    ///
1465    /// The inverse map type of DescriptorMap.
1466    class InverseMap {
1467    public:
1468      /// \brief Constructor of the InverseMap.
1469      ///
1470      /// Constructor of the InverseMap.
1471      explicit InverseMap(const DescriptorMap& _inverted)
1472        : inverted(_inverted) {}
1473
1474
1475      /// The value type of the InverseMap.
1476      typedef typename DescriptorMap::Key Value;
1477      /// The key type of the InverseMap.
1478      typedef typename DescriptorMap::Value Key;
1479
1480      /// \brief Subscript operator.
1481      ///
1482      /// Subscript operator. It gives back the item
1483      /// that the descriptor belongs to currently.
1484      Value operator[](const Key& key) const {
1485        return inverted.invMap[key];
1486      }
1487
1488      /// \brief Size of the map.
1489      ///
1490      /// Returns the size of the map.
1491      unsigned int size() const {
1492        return inverted.invMap.size();
1493      }
1494     
1495    private:
1496      const DescriptorMap& inverted;
1497    };
1498
1499    /// \brief Gives back the inverse of the map.
1500    ///
1501    /// Gives back the inverse of the map.
1502    const InverseMap inverse() const {
1503      return InverseMap(*this);
1504    }
1505  };
1506
1507  /// \brief Returns the source of the given edge.
1508  ///
1509  /// The SourceMap gives back the source Node of the given edge.
1510  /// \author Balazs Dezso
1511  template <typename Graph>
1512  class SourceMap {
1513  public:
1514
1515    typedef typename Graph::Node Value;
1516    typedef typename Graph::Edge Key;
1517
1518    /// \brief Constructor
1519    ///
1520    /// Constructor
1521    /// \param _graph The graph that the map belongs to.
1522    explicit SourceMap(const Graph& _graph) : graph(_graph) {}
1523
1524    /// \brief The subscript operator.
1525    ///
1526    /// The subscript operator.
1527    /// \param edge The edge
1528    /// \return The source of the edge
1529    Value operator[](const Key& edge) const {
1530      return graph.source(edge);
1531    }
1532
1533  private:
1534    const Graph& graph;
1535  };
1536
1537  /// \brief Returns a \ref SourceMap class
1538  ///
1539  /// This function just returns an \ref SourceMap class.
1540  /// \relates SourceMap
1541  template <typename Graph>
1542  inline SourceMap<Graph> sourceMap(const Graph& graph) {
1543    return SourceMap<Graph>(graph);
1544  }
1545
1546  /// \brief Returns the target of the given edge.
1547  ///
1548  /// The TargetMap gives back the target Node of the given edge.
1549  /// \author Balazs Dezso
1550  template <typename Graph>
1551  class TargetMap {
1552  public:
1553
1554    typedef typename Graph::Node Value;
1555    typedef typename Graph::Edge Key;
1556
1557    /// \brief Constructor
1558    ///
1559    /// Constructor
1560    /// \param _graph The graph that the map belongs to.
1561    explicit TargetMap(const Graph& _graph) : graph(_graph) {}
1562
1563    /// \brief The subscript operator.
1564    ///
1565    /// The subscript operator.
1566    /// \param e The edge
1567    /// \return The target of the edge
1568    Value operator[](const Key& e) const {
1569      return graph.target(e);
1570    }
1571
1572  private:
1573    const Graph& graph;
1574  };
1575
1576  /// \brief Returns a \ref TargetMap class
1577  ///
1578  /// This function just returns a \ref TargetMap class.
1579  /// \relates TargetMap
1580  template <typename Graph>
1581  inline TargetMap<Graph> targetMap(const Graph& graph) {
1582    return TargetMap<Graph>(graph);
1583  }
1584
1585  /// \brief Returns the "forward" directed edge view of an undirected edge.
1586  ///
1587  /// Returns the "forward" directed edge view of an undirected edge.
1588  /// \author Balazs Dezso
1589  template <typename Graph>
1590  class ForwardMap {
1591  public:
1592
1593    typedef typename Graph::Edge Value;
1594    typedef typename Graph::UEdge Key;
1595
1596    /// \brief Constructor
1597    ///
1598    /// Constructor
1599    /// \param _graph The graph that the map belongs to.
1600    explicit ForwardMap(const Graph& _graph) : graph(_graph) {}
1601
1602    /// \brief The subscript operator.
1603    ///
1604    /// The subscript operator.
1605    /// \param key An undirected edge
1606    /// \return The "forward" directed edge view of undirected edge
1607    Value operator[](const Key& key) const {
1608      return graph.direct(key, true);
1609    }
1610
1611  private:
1612    const Graph& graph;
1613  };
1614
1615  /// \brief Returns a \ref ForwardMap class
1616  ///
1617  /// This function just returns an \ref ForwardMap class.
1618  /// \relates ForwardMap
1619  template <typename Graph>
1620  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1621    return ForwardMap<Graph>(graph);
1622  }
1623
1624  /// \brief Returns the "backward" directed edge view of an undirected edge.
1625  ///
1626  /// Returns the "backward" directed edge view of an undirected edge.
1627  /// \author Balazs Dezso
1628  template <typename Graph>
1629  class BackwardMap {
1630  public:
1631
1632    typedef typename Graph::Edge Value;
1633    typedef typename Graph::UEdge Key;
1634
1635    /// \brief Constructor
1636    ///
1637    /// Constructor
1638    /// \param _graph The graph that the map belongs to.
1639    explicit BackwardMap(const Graph& _graph) : graph(_graph) {}
1640
1641    /// \brief The subscript operator.
1642    ///
1643    /// The subscript operator.
1644    /// \param key An undirected edge
1645    /// \return The "backward" directed edge view of undirected edge
1646    Value operator[](const Key& key) const {
1647      return graph.direct(key, false);
1648    }
1649
1650  private:
1651    const Graph& graph;
1652  };
1653
1654  /// \brief Returns a \ref BackwardMap class
1655
1656  /// This function just returns a \ref BackwardMap class.
1657  /// \relates BackwardMap
1658  template <typename Graph>
1659  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1660    return BackwardMap<Graph>(graph);
1661  }
1662
1663  /// \brief Potential difference map
1664  ///
1665  /// If there is an potential map on the nodes then we
1666  /// can get an edge map as we get the substraction of the
1667  /// values of the target and source.
1668  template <typename Graph, typename NodeMap>
1669  class PotentialDifferenceMap {
1670  public:
1671    typedef typename Graph::Edge Key;
1672    typedef typename NodeMap::Value Value;
1673
1674    /// \brief Constructor
1675    ///
1676    /// Contructor of the map
1677    explicit PotentialDifferenceMap(const Graph& _graph,
1678                                    const NodeMap& _potential)
1679      : graph(_graph), potential(_potential) {}
1680
1681    /// \brief Const subscription operator
1682    ///
1683    /// Const subscription operator
1684    Value operator[](const Key& edge) const {
1685      return potential[graph.target(edge)] - potential[graph.source(edge)];
1686    }
1687
1688  private:
1689    const Graph& graph;
1690    const NodeMap& potential;
1691  };
1692
1693  /// \brief Just returns a PotentialDifferenceMap
1694  ///
1695  /// Just returns a PotentialDifferenceMap
1696  /// \relates PotentialDifferenceMap
1697  template <typename Graph, typename NodeMap>
1698  PotentialDifferenceMap<Graph, NodeMap>
1699  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1700    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1701  }
1702
1703  /// \brief Map of the node in-degrees.
1704  ///
1705  /// This map returns the in-degree of a node. Once it is constructed,
1706  /// the degrees are stored in a standard NodeMap, so each query is done
1707  /// in constant time. On the other hand, the values are updated automatically
1708  /// whenever the graph changes.
1709  ///
1710  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1711  /// alternative ways to modify the graph. The correct behavior of InDegMap
1712  /// is not guarantied if these additional features are used. For example
1713  /// the functions \ref ListGraph::changeSource() "changeSource()",
1714  /// \ref ListGraph::changeTarget() "changeTarget()" and
1715  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1716  /// of \ref ListGraph will \e not update the degree values correctly.
1717  ///
1718  /// \sa OutDegMap
1719
1720  template <typename _Graph>
1721  class InDegMap 
1722    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1723      ::ItemNotifier::ObserverBase {
1724
1725  public:
1726   
1727    typedef _Graph Graph;
1728    typedef int Value;
1729    typedef typename Graph::Node Key;
1730
1731    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1732    ::ItemNotifier::ObserverBase Parent;
1733
1734  private:
1735
1736    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1737    public:
1738
1739      typedef DefaultMap<_Graph, Key, int> Parent;
1740      typedef typename Parent::Graph Graph;
1741
1742      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1743     
1744      virtual void add(const Key& key) {
1745        Parent::add(key);
1746        Parent::set(key, 0);
1747      }
1748
1749      virtual void add(const std::vector<Key>& keys) {
1750        Parent::add(keys);
1751        for (int i = 0; i < (int)keys.size(); ++i) {
1752          Parent::set(keys[i], 0);
1753        }
1754      }
1755    };
1756
1757  public:
1758
1759    /// \brief Constructor.
1760    ///
1761    /// Constructor for creating in-degree map.
1762    explicit InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1763      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1764     
1765      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1766        deg[it] = countInEdges(graph, it);
1767      }
1768    }
1769   
1770    /// Gives back the in-degree of a Node.
1771    int operator[](const Key& key) const {
1772      return deg[key];
1773    }
1774
1775  protected:
1776   
1777    typedef typename Graph::Edge Edge;
1778
1779    virtual void add(const Edge& edge) {
1780      ++deg[graph.target(edge)];
1781    }
1782
1783    virtual void add(const std::vector<Edge>& edges) {
1784      for (int i = 0; i < (int)edges.size(); ++i) {
1785        ++deg[graph.target(edges[i])];
1786      }
1787    }
1788
1789    virtual void erase(const Edge& edge) {
1790      --deg[graph.target(edge)];
1791    }
1792
1793    virtual void erase(const std::vector<Edge>& edges) {
1794      for (int i = 0; i < (int)edges.size(); ++i) {
1795        --deg[graph.target(edges[i])];
1796      }
1797    }
1798
1799    virtual void build() {
1800      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1801        deg[it] = countInEdges(graph, it);
1802      }     
1803    }
1804
1805    virtual void clear() {
1806      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1807        deg[it] = 0;
1808      }
1809    }
1810  private:
1811   
1812    const _Graph& graph;
1813    AutoNodeMap deg;
1814  };
1815
1816  /// \brief Map of the node out-degrees.
1817  ///
1818  /// This map returns the out-degree of a node. Once it is constructed,
1819  /// the degrees are stored in a standard NodeMap, so each query is done
1820  /// in constant time. On the other hand, the values are updated automatically
1821  /// whenever the graph changes.
1822  ///
1823  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1824  /// alternative ways to modify the graph. The correct behavior of OutDegMap
1825  /// is not guarantied if these additional features are used. For example
1826  /// the functions \ref ListGraph::changeSource() "changeSource()",
1827  /// \ref ListGraph::changeTarget() "changeTarget()" and
1828  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1829  /// of \ref ListGraph will \e not update the degree values correctly.
1830  ///
1831  /// \sa InDegMap
1832
1833  template <typename _Graph>
1834  class OutDegMap 
1835    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1836      ::ItemNotifier::ObserverBase {
1837
1838  public:
1839
1840    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1841    ::ItemNotifier::ObserverBase Parent;
1842   
1843    typedef _Graph Graph;
1844    typedef int Value;
1845    typedef typename Graph::Node Key;
1846
1847  private:
1848
1849    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1850    public:
1851
1852      typedef DefaultMap<_Graph, Key, int> Parent;
1853      typedef typename Parent::Graph Graph;
1854
1855      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1856     
1857      virtual void add(const Key& key) {
1858        Parent::add(key);
1859        Parent::set(key, 0);
1860      }
1861      virtual void add(const std::vector<Key>& keys) {
1862        Parent::add(keys);
1863        for (int i = 0; i < (int)keys.size(); ++i) {
1864          Parent::set(keys[i], 0);
1865        }
1866      }
1867    };
1868
1869  public:
1870
1871    /// \brief Constructor.
1872    ///
1873    /// Constructor for creating out-degree map.
1874    explicit OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1875      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1876     
1877      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1878        deg[it] = countOutEdges(graph, it);
1879      }
1880    }
1881
1882    /// Gives back the out-degree of a Node.
1883    int operator[](const Key& key) const {
1884      return deg[key];
1885    }
1886
1887  protected:
1888   
1889    typedef typename Graph::Edge Edge;
1890
1891    virtual void add(const Edge& edge) {
1892      ++deg[graph.source(edge)];
1893    }
1894
1895    virtual void add(const std::vector<Edge>& edges) {
1896      for (int i = 0; i < (int)edges.size(); ++i) {
1897        ++deg[graph.source(edges[i])];
1898      }
1899    }
1900
1901    virtual void erase(const Edge& edge) {
1902      --deg[graph.source(edge)];
1903    }
1904
1905    virtual void erase(const std::vector<Edge>& edges) {
1906      for (int i = 0; i < (int)edges.size(); ++i) {
1907        --deg[graph.source(edges[i])];
1908      }
1909    }
1910
1911    virtual void build() {
1912      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1913        deg[it] = countOutEdges(graph, it);
1914      }     
1915    }
1916
1917    virtual void clear() {
1918      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1919        deg[it] = 0;
1920      }
1921    }
1922  private:
1923   
1924    const _Graph& graph;
1925    AutoNodeMap deg;
1926  };
1927
1928
1929  ///Fast edge look up between given endpoints.
1930 
1931  ///\ingroup gutils
1932  ///Using this class, you can find an edge in a graph from a given
1933  ///source to a given target in time <em>O(log d)</em>,
1934  ///where <em>d</em> is the out-degree of the source node.
1935  ///
1936  ///It is not possible to find \e all parallel edges between two nodes.
1937  ///Use \ref AllEdgeLookUp for this purpose.
1938  ///
1939  ///\warning This class is static, so you should refresh() (or at least
1940  ///refresh(Node)) this data structure
1941  ///whenever the graph changes. This is a time consuming (superlinearly
1942  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
1943  ///
1944  ///\param G The type of the underlying graph.
1945  ///
1946  ///\sa AllEdgeLookUp 
1947  template<class G>
1948  class EdgeLookUp
1949  {
1950  public:
1951    GRAPH_TYPEDEFS(typename G)
1952    typedef G Graph;
1953
1954  protected:
1955    const Graph &_g;
1956    typename Graph::template NodeMap<Edge> _head;
1957    typename Graph::template EdgeMap<Edge> _left;
1958    typename Graph::template EdgeMap<Edge> _right;
1959   
1960    class EdgeLess {
1961      const Graph &g;
1962    public:
1963      EdgeLess(const Graph &_g) : g(_g) {}
1964      bool operator()(Edge a,Edge b) const
1965      {
1966        return g.target(a)<g.target(b);
1967      }
1968    };
1969   
1970  public:
1971   
1972    ///Constructor
1973
1974    ///Constructor.
1975    ///
1976    ///It builds up the search database, which remains valid until the graph
1977    ///changes.
1978    EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1979   
1980  private:
1981    Edge refresh_rec(std::vector<Edge> &v,int a,int b)
1982    {
1983      int m=(a+b)/2;
1984      Edge me=v[m];
1985      _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
1986      _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
1987      return me;
1988    }
1989  public:
1990    ///Refresh the data structure at a node.
1991
1992    ///Build up the search database of node \c n.
1993    ///
1994    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1995    ///the number of the outgoing edges of \c n.
1996    void refresh(Node n)
1997    {
1998      std::vector<Edge> v;
1999      for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2000      if(v.size()) {
2001        std::sort(v.begin(),v.end(),EdgeLess(_g));
2002        _head[n]=refresh_rec(v,0,v.size()-1);
2003      }
2004      else _head[n]=INVALID;
2005    }
2006    ///Refresh the full data structure.
2007
2008    ///Build up the full search database. In fact, it simply calls
2009    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2010    ///
2011    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2012    ///the number of the edges of \c n and <em>D</em> is the maximum
2013    ///out-degree of the graph.
2014
2015    void refresh()
2016    {
2017      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2018    }
2019   
2020    ///Find an edge between two nodes.
2021   
2022    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
2023    /// <em>d</em> is the number of outgoing edges of \c s.
2024    ///\param s The source node
2025    ///\param t The target node
2026    ///\return An edge from \c s to \c t if there exists,
2027    ///\ref INVALID otherwise.
2028    ///
2029    ///\warning If you change the graph, refresh() must be called before using
2030    ///this operator. If you change the outgoing edges of
2031    ///a single node \c n, then
2032    ///\ref refresh(Node) "refresh(n)" is enough.
2033    ///
2034    Edge operator()(Node s, Node t) const
2035    {
2036      Edge e;
2037      for(e=_head[s];
2038          e!=INVALID&&_g.target(e)!=t;
2039          e = t < _g.target(e)?_left[e]:_right[e]) ;
2040      return e;
2041    }
2042
2043  };
2044
2045  ///Fast look up of all edges between given endpoints.
2046 
2047  ///\ingroup gutils
2048  ///This class is the same as \ref EdgeLookUp, with the addition
2049  ///that it makes it possible to find all edges between given endpoints.
2050  ///
2051  ///\warning This class is static, so you should refresh() (or at least
2052  ///refresh(Node)) this data structure
2053  ///whenever the graph changes. This is a time consuming (superlinearly
2054  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2055  ///
2056  ///\param G The type of the underlying graph.
2057  ///
2058  ///\sa EdgeLookUp 
2059  template<class G>
2060  class AllEdgeLookUp : public EdgeLookUp<G>
2061  {
2062    using EdgeLookUp<G>::_g;
2063    using EdgeLookUp<G>::_right;
2064    using EdgeLookUp<G>::_left;
2065    using EdgeLookUp<G>::_head;
2066
2067    GRAPH_TYPEDEFS(typename G)
2068    typedef G Graph;
2069   
2070    typename Graph::template EdgeMap<Edge> _next;
2071   
2072    Edge refreshNext(Edge head,Edge next=INVALID)
2073    {
2074      if(head==INVALID) return next;
2075      else {
2076        next=refreshNext(_right[head],next);
2077//      _next[head]=next;
2078        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2079          ? next : INVALID;
2080        return refreshNext(_left[head],head);
2081      }
2082    }
2083   
2084    void refreshNext()
2085    {
2086      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2087    }
2088   
2089  public:
2090    ///Constructor
2091
2092    ///Constructor.
2093    ///
2094    ///It builds up the search database, which remains valid until the graph
2095    ///changes.
2096    AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
2097
2098    ///Refresh the data structure at a node.
2099
2100    ///Build up the search database of node \c n.
2101    ///
2102    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2103    ///the number of the outgoing edges of \c n.
2104   
2105    void refresh(Node n)
2106    {
2107      EdgeLookUp<G>::refresh(n);
2108      refreshNext(_head[n]);
2109    }
2110   
2111    ///Refresh the full data structure.
2112
2113    ///Build up the full search database. In fact, it simply calls
2114    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2115    ///
2116    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2117    ///the number of the edges of \c n and <em>D</em> is the maximum
2118    ///out-degree of the graph.
2119
2120    void refresh()
2121    {
2122      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2123    }
2124   
2125    ///Find an edge between two nodes.
2126   
2127    ///Find an edge between two nodes.
2128    ///\param s The source node
2129    ///\param t The target node
2130    ///\param prev The previous edge between \c s and \c t. It it is INVALID or
2131    ///not given, the operator finds the first appropriate edge.
2132    ///\return An edge from \c s to \c t after \prev or
2133    ///\ref INVALID if there is no more.
2134    ///
2135    ///For example, you can count the number of edges from \c u to \c v in the
2136    ///following way.
2137    ///\code
2138    ///AllEdgeLookUp<ListGraph> ae(g);
2139    ///...
2140    ///int n=0;
2141    ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
2142    ///\endcode
2143    ///
2144    ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
2145    /// <em>d</em> is the number of outgoing edges of \c s. Then, the
2146    ///consecutive edges are found in constant time.
2147    ///
2148    ///\warning If you change the graph, refresh() must be called before using
2149    ///this operator. If you change the outgoing edges of
2150    ///a single node \c n, then
2151    ///\ref refresh(Node) "refresh(n)" is enough.
2152    ///
2153#ifdef DOXYGEN
2154    Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
2155#else
2156    using EdgeLookUp<G>::operator() ;
2157    Edge operator()(Node s, Node t, Edge prev) const
2158    {
2159      return prev==INVALID?(*this)(s,t):_next[prev];
2160    }
2161#endif
2162     
2163  };
2164
2165  /// @}
2166
2167} //END OF NAMESPACE LEMON
2168
2169#endif
Note: See TracBrowser for help on using the repository browser.