COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2286:1ef281b2b10e

Last change on this file since 2286:1ef281b2b10e was 2286:1ef281b2b10e, checked in by Balazs Dezso, 14 years ago

The implementation of the graph copy is changed
Make explicit more constructors

File size: 63.9 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#ifndef DOXYGEN
1136  /// \param _Map A ReadWriteMap mapping from the item type to integer.
1137  template <
1138    typename _Graph, typename _Item, typename _Value,
1139    typename _Map = DefaultMap<_Graph, _Item, _Value>
1140  >
1141#else
1142  template <typename _Graph, typename _Item, typename _Value>
1143#endif
1144  class InvertableMap : protected _Map {
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  private:
1153   
1154    typedef _Map Map;
1155    typedef _Graph Graph;
1156
1157    typedef std::map<Value, Key> Container;
1158    Container invMap;   
1159
1160  public:
1161 
1162
1163
1164    /// \brief Constructor.
1165    ///
1166    /// Construct a new InvertableMap for the graph.
1167    ///
1168    explicit InvertableMap(const Graph& graph) : Map(graph) {}
1169
1170    /// \brief Forward iterator for values.
1171    ///
1172    /// This iterator is an stl compatible forward
1173    /// iterator on the values of the map. The values can
1174    /// be accessed in the [beginValue, endValue) range.
1175    ///
1176    class ValueIterator
1177      : public std::iterator<std::forward_iterator_tag, Value> {
1178      friend class InvertableMap;
1179    private:
1180      ValueIterator(typename Container::const_iterator _it)
1181        : it(_it) {}
1182    public:
1183     
1184      ValueIterator() {}
1185
1186      ValueIterator& operator++() { ++it; return *this; }
1187      ValueIterator operator++(int) {
1188        ValueIterator tmp(*this);
1189        operator++();
1190        return tmp;
1191      }
1192
1193      const Value& operator*() const { return it->first; }
1194      const Value* operator->() const { return &(it->first); }
1195
1196      bool operator==(ValueIterator jt) const { return it == jt.it; }
1197      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1198     
1199    private:
1200      typename Container::const_iterator it;
1201    };
1202
1203    /// \brief Returns an iterator to the first value.
1204    ///
1205    /// Returns an stl compatible iterator to the
1206    /// first value of the map. The values of the
1207    /// map can be accessed in the [beginValue, endValue)
1208    /// range.
1209    ValueIterator beginValue() const {
1210      return ValueIterator(invMap.begin());
1211    }
1212
1213    /// \brief Returns an iterator after the last value.
1214    ///
1215    /// Returns an stl compatible iterator after the
1216    /// last value of the map. The values of the
1217    /// map can be accessed in the [beginValue, endValue)
1218    /// range.
1219    ValueIterator endValue() const {
1220      return ValueIterator(invMap.end());
1221    }
1222   
1223    /// \brief The setter function of the map.
1224    ///
1225    /// Sets the mapped value.
1226    void set(const Key& key, const Value& val) {
1227      Value oldval = Map::operator[](key);
1228      typename Container::iterator it = invMap.find(oldval);
1229      if (it != invMap.end() && it->second == key) {
1230        invMap.erase(it);
1231      }     
1232      invMap.insert(make_pair(val, key));
1233      Map::set(key, val);
1234    }
1235
1236    /// \brief The getter function of the map.
1237    ///
1238    /// It gives back the value associated with the key.
1239    typename MapTraits<Map>::ConstReturnValue
1240    operator[](const Key& key) const {
1241      return Map::operator[](key);
1242    }
1243
1244  protected:
1245
1246    /// \brief Erase the key from the map.
1247    ///
1248    /// Erase the key to the map. It is called by the
1249    /// \c AlterationNotifier.
1250    virtual void erase(const Key& key) {
1251      Value val = Map::operator[](key);
1252      typename Container::iterator it = invMap.find(val);
1253      if (it != invMap.end() && it->second == key) {
1254        invMap.erase(it);
1255      }
1256      Map::erase(key);
1257    }
1258
1259    /// \brief Erase more keys from the map.
1260    ///
1261    /// Erase more keys from the map. It is called by the
1262    /// \c AlterationNotifier.
1263    virtual void erase(const std::vector<Key>& keys) {
1264      for (int i = 0; i < (int)keys.size(); ++i) {
1265        Value val = Map::operator[](keys[i]);
1266        typename Container::iterator it = invMap.find(val);
1267        if (it != invMap.end() && it->second == keys[i]) {
1268          invMap.erase(it);
1269        }
1270      }
1271      Map::erase(keys);
1272    }
1273
1274    /// \brief Clear the keys from the map and inverse map.
1275    ///
1276    /// Clear the keys from the map and inverse map. It is called by the
1277    /// \c AlterationNotifier.
1278    virtual void clear() {
1279      invMap.clear();
1280      Map::clear();
1281    }
1282
1283  public:
1284
1285    /// \brief The inverse map type.
1286    ///
1287    /// The inverse of this map. The subscript operator of the map
1288    /// gives back always the item what was last assigned to the value.
1289    class InverseMap {
1290    public:
1291      /// \brief Constructor of the InverseMap.
1292      ///
1293      /// Constructor of the InverseMap.
1294      explicit InverseMap(const InvertableMap& _inverted)
1295        : inverted(_inverted) {}
1296
1297      /// The value type of the InverseMap.
1298      typedef typename InvertableMap::Key Value;
1299      /// The key type of the InverseMap.
1300      typedef typename InvertableMap::Value Key;
1301
1302      /// \brief Subscript operator.
1303      ///
1304      /// Subscript operator. It gives back always the item
1305      /// what was last assigned to the value.
1306      Value operator[](const Key& key) const {
1307        typename Container::const_iterator it = inverted.invMap.find(key);
1308        return it->second;
1309      }
1310     
1311    private:
1312      const InvertableMap& inverted;
1313    };
1314
1315    /// \brief It gives back the just readable inverse map.
1316    ///
1317    /// It gives back the just readable inverse map.
1318    InverseMap inverse() const {
1319      return InverseMap(*this);
1320    }
1321
1322
1323   
1324  };
1325
1326  /// \brief Provides a mutable, continuous and unique descriptor for each
1327  /// item in the graph.
1328  ///
1329  /// The DescriptorMap class provides a unique and continuous (but mutable)
1330  /// descriptor (id) for each item of the same type (e.g. node) in the
1331  /// graph. This id is <ul><li>\b unique: different items (nodes) get
1332  /// different ids <li>\b continuous: the range of the ids is the set of
1333  /// integers between 0 and \c n-1, where \c n is the number of the items of
1334  /// this type (e.g. nodes) (so the id of a node can change if you delete an
1335  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
1336  /// with its member class \c InverseMap.
1337  ///
1338  /// \param _Graph The graph class the \c DescriptorMap belongs to.
1339  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1340  /// UEdge.
1341#ifndef DOXYGEN
1342  /// \param _Map A ReadWriteMap mapping from the item type to integer.
1343  template <
1344    typename _Graph, typename _Item,
1345    typename _Map = DefaultMap<_Graph, _Item, int>
1346  >
1347#else
1348  template <typename _Graph, typename _Item>
1349#endif
1350  class DescriptorMap : protected _Map {
1351
1352    typedef _Item Item;
1353    typedef _Map Map;
1354
1355  public:
1356    /// The graph class of DescriptorMap.
1357    typedef _Graph Graph;
1358
1359    /// The key type of DescriptorMap (Node, Edge, UEdge).
1360    typedef typename _Map::Key Key;
1361    /// The value type of DescriptorMap.
1362    typedef typename _Map::Value Value;
1363
1364    /// \brief Constructor.
1365    ///
1366    /// Constructor for descriptor map.
1367    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1368      Item it;
1369      const typename Map::Notifier* notifier = Map::getNotifier();
1370      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1371        Map::set(it, invMap.size());
1372        invMap.push_back(it);   
1373      }     
1374    }
1375
1376
1377  protected:
1378
1379    /// \brief Add a new key to the map.
1380    ///
1381    /// Add a new key to the map. It is called by the
1382    /// \c AlterationNotifier.
1383    virtual void add(const Item& item) {
1384      Map::add(item);
1385      Map::set(item, invMap.size());
1386      invMap.push_back(item);
1387    }
1388
1389    /// \brief Add more new keys to the map.
1390    ///
1391    /// Add more new keys to the map. It is called by the
1392    /// \c AlterationNotifier.
1393    virtual void add(const std::vector<Item>& items) {
1394      Map::add(items);
1395      for (int i = 0; i < (int)items.size(); ++i) {
1396        Map::set(items[i], invMap.size());
1397        invMap.push_back(items[i]);
1398      }
1399    }
1400
1401    /// \brief Erase the key from the map.
1402    ///
1403    /// Erase the key from the map. It is called by the
1404    /// \c AlterationNotifier.
1405    virtual void erase(const Item& item) {
1406      Map::set(invMap.back(), Map::operator[](item));
1407      invMap[Map::operator[](item)] = invMap.back();
1408      invMap.pop_back();
1409      Map::erase(item);
1410    }
1411
1412    /// \brief Erase more keys from the map.
1413    ///
1414    /// Erase more keys from the map. It is called by the
1415    /// \c AlterationNotifier.
1416    virtual void erase(const std::vector<Item>& items) {
1417      for (int i = 0; i < (int)items.size(); ++i) {
1418        Map::set(invMap.back(), Map::operator[](items[i]));
1419        invMap[Map::operator[](items[i])] = invMap.back();
1420        invMap.pop_back();
1421      }
1422      Map::erase(items);
1423    }
1424
1425    /// \brief Build the unique map.
1426    ///
1427    /// Build the unique map. It is called by the
1428    /// \c AlterationNotifier.
1429    virtual void build() {
1430      Map::build();
1431      Item it;
1432      const typename Map::Notifier* notifier = Map::getNotifier();
1433      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1434        Map::set(it, invMap.size());
1435        invMap.push_back(it);   
1436      }     
1437    }
1438   
1439    /// \brief Clear the keys from the map.
1440    ///
1441    /// Clear the keys from the map. It is called by the
1442    /// \c AlterationNotifier.
1443    virtual void clear() {
1444      invMap.clear();
1445      Map::clear();
1446    }
1447
1448  public:
1449
1450    /// \brief Returns the maximal value plus one.
1451    ///
1452    /// Returns the maximal value plus one in the map.
1453    unsigned int size() const {
1454      return invMap.size();
1455    }
1456
1457    /// \brief Swaps the position of the two items in the map.
1458    ///
1459    /// Swaps the position of the two items in the map.
1460    void swap(const Item& p, const Item& q) {
1461      int pi = Map::operator[](p);
1462      int qi = Map::operator[](q);
1463      Map::set(p, qi);
1464      invMap[qi] = p;
1465      Map::set(q, pi);
1466      invMap[pi] = q;
1467    }
1468
1469    /// \brief Gives back the \e descriptor of the item.
1470    ///
1471    /// Gives back the mutable and unique \e descriptor of the map.
1472    int operator[](const Item& item) const {
1473      return Map::operator[](item);
1474    }
1475   
1476  private:
1477
1478    typedef std::vector<Item> Container;
1479    Container invMap;
1480
1481  public:
1482    /// \brief The inverse map type of DescriptorMap.
1483    ///
1484    /// The inverse map type of DescriptorMap.
1485    class InverseMap {
1486    public:
1487      /// \brief Constructor of the InverseMap.
1488      ///
1489      /// Constructor of the InverseMap.
1490      explicit InverseMap(const DescriptorMap& _inverted)
1491        : inverted(_inverted) {}
1492
1493
1494      /// The value type of the InverseMap.
1495      typedef typename DescriptorMap::Key Value;
1496      /// The key type of the InverseMap.
1497      typedef typename DescriptorMap::Value Key;
1498
1499      /// \brief Subscript operator.
1500      ///
1501      /// Subscript operator. It gives back the item
1502      /// that the descriptor belongs to currently.
1503      Value operator[](const Key& key) const {
1504        return inverted.invMap[key];
1505      }
1506
1507      /// \brief Size of the map.
1508      ///
1509      /// Returns the size of the map.
1510      unsigned int size() const {
1511        return inverted.invMap.size();
1512      }
1513     
1514    private:
1515      const DescriptorMap& inverted;
1516    };
1517
1518    /// \brief Gives back the inverse of the map.
1519    ///
1520    /// Gives back the inverse of the map.
1521    const InverseMap inverse() const {
1522      return InverseMap(*this);
1523    }
1524  };
1525
1526  /// \brief Returns the source of the given edge.
1527  ///
1528  /// The SourceMap gives back the source Node of the given edge.
1529  /// \author Balazs Dezso
1530  template <typename Graph>
1531  class SourceMap {
1532  public:
1533
1534    typedef typename Graph::Node Value;
1535    typedef typename Graph::Edge Key;
1536
1537    /// \brief Constructor
1538    ///
1539    /// Constructor
1540    /// \param _graph The graph that the map belongs to.
1541    explicit SourceMap(const Graph& _graph) : graph(_graph) {}
1542
1543    /// \brief The subscript operator.
1544    ///
1545    /// The subscript operator.
1546    /// \param edge The edge
1547    /// \return The source of the edge
1548    Value operator[](const Key& edge) const {
1549      return graph.source(edge);
1550    }
1551
1552  private:
1553    const Graph& graph;
1554  };
1555
1556  /// \brief Returns a \ref SourceMap class
1557  ///
1558  /// This function just returns an \ref SourceMap class.
1559  /// \relates SourceMap
1560  template <typename Graph>
1561  inline SourceMap<Graph> sourceMap(const Graph& graph) {
1562    return SourceMap<Graph>(graph);
1563  }
1564
1565  /// \brief Returns the target of the given edge.
1566  ///
1567  /// The TargetMap gives back the target Node of the given edge.
1568  /// \author Balazs Dezso
1569  template <typename Graph>
1570  class TargetMap {
1571  public:
1572
1573    typedef typename Graph::Node Value;
1574    typedef typename Graph::Edge Key;
1575
1576    /// \brief Constructor
1577    ///
1578    /// Constructor
1579    /// \param _graph The graph that the map belongs to.
1580    explicit TargetMap(const Graph& _graph) : graph(_graph) {}
1581
1582    /// \brief The subscript operator.
1583    ///
1584    /// The subscript operator.
1585    /// \param e The edge
1586    /// \return The target of the edge
1587    Value operator[](const Key& e) const {
1588      return graph.target(e);
1589    }
1590
1591  private:
1592    const Graph& graph;
1593  };
1594
1595  /// \brief Returns a \ref TargetMap class
1596  ///
1597  /// This function just returns a \ref TargetMap class.
1598  /// \relates TargetMap
1599  template <typename Graph>
1600  inline TargetMap<Graph> targetMap(const Graph& graph) {
1601    return TargetMap<Graph>(graph);
1602  }
1603
1604  /// \brief Returns the "forward" directed edge view of an undirected edge.
1605  ///
1606  /// Returns the "forward" directed edge view of an undirected edge.
1607  /// \author Balazs Dezso
1608  template <typename Graph>
1609  class ForwardMap {
1610  public:
1611
1612    typedef typename Graph::Edge Value;
1613    typedef typename Graph::UEdge Key;
1614
1615    /// \brief Constructor
1616    ///
1617    /// Constructor
1618    /// \param _graph The graph that the map belongs to.
1619    explicit ForwardMap(const Graph& _graph) : graph(_graph) {}
1620
1621    /// \brief The subscript operator.
1622    ///
1623    /// The subscript operator.
1624    /// \param key An undirected edge
1625    /// \return The "forward" directed edge view of undirected edge
1626    Value operator[](const Key& key) const {
1627      return graph.direct(key, true);
1628    }
1629
1630  private:
1631    const Graph& graph;
1632  };
1633
1634  /// \brief Returns a \ref ForwardMap class
1635  ///
1636  /// This function just returns an \ref ForwardMap class.
1637  /// \relates ForwardMap
1638  template <typename Graph>
1639  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1640    return ForwardMap<Graph>(graph);
1641  }
1642
1643  /// \brief Returns the "backward" directed edge view of an undirected edge.
1644  ///
1645  /// Returns the "backward" directed edge view of an undirected edge.
1646  /// \author Balazs Dezso
1647  template <typename Graph>
1648  class BackwardMap {
1649  public:
1650
1651    typedef typename Graph::Edge Value;
1652    typedef typename Graph::UEdge Key;
1653
1654    /// \brief Constructor
1655    ///
1656    /// Constructor
1657    /// \param _graph The graph that the map belongs to.
1658    explicit BackwardMap(const Graph& _graph) : graph(_graph) {}
1659
1660    /// \brief The subscript operator.
1661    ///
1662    /// The subscript operator.
1663    /// \param key An undirected edge
1664    /// \return The "backward" directed edge view of undirected edge
1665    Value operator[](const Key& key) const {
1666      return graph.direct(key, false);
1667    }
1668
1669  private:
1670    const Graph& graph;
1671  };
1672
1673  /// \brief Returns a \ref BackwardMap class
1674
1675  /// This function just returns a \ref BackwardMap class.
1676  /// \relates BackwardMap
1677  template <typename Graph>
1678  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1679    return BackwardMap<Graph>(graph);
1680  }
1681
1682  /// \brief Potential difference map
1683  ///
1684  /// If there is an potential map on the nodes then we
1685  /// can get an edge map as we get the substraction of the
1686  /// values of the target and source.
1687  template <typename Graph, typename NodeMap>
1688  class PotentialDifferenceMap {
1689  public:
1690    typedef typename Graph::Edge Key;
1691    typedef typename NodeMap::Value Value;
1692
1693    /// \brief Constructor
1694    ///
1695    /// Contructor of the map
1696    explicit PotentialDifferenceMap(const Graph& _graph,
1697                                    const NodeMap& _potential)
1698      : graph(_graph), potential(_potential) {}
1699
1700    /// \brief Const subscription operator
1701    ///
1702    /// Const subscription operator
1703    Value operator[](const Key& edge) const {
1704      return potential[graph.target(edge)] - potential[graph.source(edge)];
1705    }
1706
1707  private:
1708    const Graph& graph;
1709    const NodeMap& potential;
1710  };
1711
1712  /// \brief Just returns a PotentialDifferenceMap
1713  ///
1714  /// Just returns a PotentialDifferenceMap
1715  /// \relates PotentialDifferenceMap
1716  template <typename Graph, typename NodeMap>
1717  PotentialDifferenceMap<Graph, NodeMap>
1718  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1719    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1720  }
1721
1722  /// \brief Map of the node in-degrees.
1723  ///
1724  /// This map returns the in-degree of a node. Once it is constructed,
1725  /// the degrees are stored in a standard NodeMap, so each query is done
1726  /// in constant time. On the other hand, the values are updated automatically
1727  /// whenever the graph changes.
1728  ///
1729  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1730  /// alternative ways to modify the graph. The correct behavior of InDegMap
1731  /// is not guarantied if these additional features are used. For example
1732  /// the functions \ref ListGraph::changeSource() "changeSource()",
1733  /// \ref ListGraph::changeTarget() "changeTarget()" and
1734  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1735  /// of \ref ListGraph will \e not update the degree values correctly.
1736  ///
1737  /// \sa OutDegMap
1738
1739  template <typename _Graph>
1740  class InDegMap 
1741    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1742      ::ItemNotifier::ObserverBase {
1743
1744  public:
1745   
1746    typedef _Graph Graph;
1747    typedef int Value;
1748    typedef typename Graph::Node Key;
1749
1750    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1751    ::ItemNotifier::ObserverBase Parent;
1752
1753  private:
1754
1755    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1756    public:
1757
1758      typedef DefaultMap<_Graph, Key, int> Parent;
1759      typedef typename Parent::Graph Graph;
1760
1761      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1762     
1763      virtual void add(const Key& key) {
1764        Parent::add(key);
1765        Parent::set(key, 0);
1766      }
1767
1768      virtual void add(const std::vector<Key>& keys) {
1769        Parent::add(keys);
1770        for (int i = 0; i < (int)keys.size(); ++i) {
1771          Parent::set(keys[i], 0);
1772        }
1773      }
1774    };
1775
1776  public:
1777
1778    /// \brief Constructor.
1779    ///
1780    /// Constructor for creating in-degree map.
1781    explicit InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1782      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1783     
1784      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1785        deg[it] = countInEdges(graph, it);
1786      }
1787    }
1788   
1789    /// Gives back the in-degree of a Node.
1790    int operator[](const Key& key) const {
1791      return deg[key];
1792    }
1793
1794  protected:
1795   
1796    typedef typename Graph::Edge Edge;
1797
1798    virtual void add(const Edge& edge) {
1799      ++deg[graph.target(edge)];
1800    }
1801
1802    virtual void add(const std::vector<Edge>& edges) {
1803      for (int i = 0; i < (int)edges.size(); ++i) {
1804        ++deg[graph.target(edges[i])];
1805      }
1806    }
1807
1808    virtual void erase(const Edge& edge) {
1809      --deg[graph.target(edge)];
1810    }
1811
1812    virtual void erase(const std::vector<Edge>& edges) {
1813      for (int i = 0; i < (int)edges.size(); ++i) {
1814        --deg[graph.target(edges[i])];
1815      }
1816    }
1817
1818    virtual void build() {
1819      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1820        deg[it] = countInEdges(graph, it);
1821      }     
1822    }
1823
1824    virtual void clear() {
1825      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1826        deg[it] = 0;
1827      }
1828    }
1829  private:
1830   
1831    const _Graph& graph;
1832    AutoNodeMap deg;
1833  };
1834
1835  /// \brief Map of the node out-degrees.
1836  ///
1837  /// This map returns the out-degree of a node. Once it is constructed,
1838  /// the degrees are stored in a standard NodeMap, so each query is done
1839  /// in constant time. On the other hand, the values are updated automatically
1840  /// whenever the graph changes.
1841  ///
1842  /// \warning Besides addNode() and addEdge(), a graph structure may provide
1843  /// alternative ways to modify the graph. The correct behavior of OutDegMap
1844  /// is not guarantied if these additional features are used. For example
1845  /// the functions \ref ListGraph::changeSource() "changeSource()",
1846  /// \ref ListGraph::changeTarget() "changeTarget()" and
1847  /// \ref ListGraph::reverseEdge() "reverseEdge()"
1848  /// of \ref ListGraph will \e not update the degree values correctly.
1849  ///
1850  /// \sa InDegMap
1851
1852  template <typename _Graph>
1853  class OutDegMap 
1854    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
1855      ::ItemNotifier::ObserverBase {
1856
1857  public:
1858
1859    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
1860    ::ItemNotifier::ObserverBase Parent;
1861   
1862    typedef _Graph Graph;
1863    typedef int Value;
1864    typedef typename Graph::Node Key;
1865
1866  private:
1867
1868    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
1869    public:
1870
1871      typedef DefaultMap<_Graph, Key, int> Parent;
1872      typedef typename Parent::Graph Graph;
1873
1874      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1875     
1876      virtual void add(const Key& key) {
1877        Parent::add(key);
1878        Parent::set(key, 0);
1879      }
1880      virtual void add(const std::vector<Key>& keys) {
1881        Parent::add(keys);
1882        for (int i = 0; i < (int)keys.size(); ++i) {
1883          Parent::set(keys[i], 0);
1884        }
1885      }
1886    };
1887
1888  public:
1889
1890    /// \brief Constructor.
1891    ///
1892    /// Constructor for creating out-degree map.
1893    explicit OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1894      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1895     
1896      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1897        deg[it] = countOutEdges(graph, it);
1898      }
1899    }
1900
1901    /// Gives back the out-degree of a Node.
1902    int operator[](const Key& key) const {
1903      return deg[key];
1904    }
1905
1906  protected:
1907   
1908    typedef typename Graph::Edge Edge;
1909
1910    virtual void add(const Edge& edge) {
1911      ++deg[graph.source(edge)];
1912    }
1913
1914    virtual void add(const std::vector<Edge>& edges) {
1915      for (int i = 0; i < (int)edges.size(); ++i) {
1916        ++deg[graph.source(edges[i])];
1917      }
1918    }
1919
1920    virtual void erase(const Edge& edge) {
1921      --deg[graph.source(edge)];
1922    }
1923
1924    virtual void erase(const std::vector<Edge>& edges) {
1925      for (int i = 0; i < (int)edges.size(); ++i) {
1926        --deg[graph.source(edges[i])];
1927      }
1928    }
1929
1930    virtual void build() {
1931      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1932        deg[it] = countOutEdges(graph, it);
1933      }     
1934    }
1935
1936    virtual void clear() {
1937      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1938        deg[it] = 0;
1939      }
1940    }
1941  private:
1942   
1943    const _Graph& graph;
1944    AutoNodeMap deg;
1945  };
1946
1947
1948  ///Fast edge look up between given endpoints.
1949 
1950  ///\ingroup gutils
1951  ///Using this class, you can find an edge in a graph from a given
1952  ///source to a given target in time <em>O(log d)</em>,
1953  ///where <em>d</em> is the out-degree of the source node.
1954  ///
1955  ///It is not possible to find \e all parallel edges between two nodes.
1956  ///Use \ref AllEdgeLookUp for this purpose.
1957  ///
1958  ///\warning This class is static, so you should refresh() (or at least
1959  ///refresh(Node)) this data structure
1960  ///whenever the graph changes. This is a time consuming (superlinearly
1961  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
1962  ///
1963  ///\param G The type of the underlying graph.
1964  ///
1965  ///\sa AllEdgeLookUp 
1966  template<class G>
1967  class EdgeLookUp
1968  {
1969  public:
1970    GRAPH_TYPEDEFS(typename G)
1971    typedef G Graph;
1972
1973  protected:
1974    const Graph &_g;
1975    typename Graph::template NodeMap<Edge> _head;
1976    typename Graph::template EdgeMap<Edge> _left;
1977    typename Graph::template EdgeMap<Edge> _right;
1978   
1979    class EdgeLess {
1980      const Graph &g;
1981    public:
1982      EdgeLess(const Graph &_g) : g(_g) {}
1983      bool operator()(Edge a,Edge b) const
1984      {
1985        return g.target(a)<g.target(b);
1986      }
1987    };
1988   
1989  public:
1990   
1991    ///Constructor
1992
1993    ///Constructor.
1994    ///
1995    ///It builds up the search database, which remains valid until the graph
1996    ///changes.
1997    EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1998   
1999  private:
2000    Edge refresh_rec(std::vector<Edge> &v,int a,int b)
2001    {
2002      int m=(a+b)/2;
2003      Edge me=v[m];
2004      _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
2005      _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
2006      return me;
2007    }
2008  public:
2009    ///Refresh the data structure at a node.
2010
2011    ///Build up the search database of node \c n.
2012    ///
2013    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2014    ///the number of the outgoing edges of \c n.
2015    void refresh(Node n)
2016    {
2017      std::vector<Edge> v;
2018      for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2019      if(v.size()) {
2020        std::sort(v.begin(),v.end(),EdgeLess(_g));
2021        _head[n]=refresh_rec(v,0,v.size()-1);
2022      }
2023      else _head[n]=INVALID;
2024    }
2025    ///Refresh the full data structure.
2026
2027    ///Build up the full search database. In fact, it simply calls
2028    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2029    ///
2030    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2031    ///the number of the edges of \c n and <em>D</em> is the maximum
2032    ///out-degree of the graph.
2033
2034    void refresh()
2035    {
2036      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2037    }
2038   
2039    ///Find an edge between two nodes.
2040   
2041    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
2042    /// <em>d</em> is the number of outgoing edges of \c s.
2043    ///\param s The source node
2044    ///\param t The target node
2045    ///\return An edge from \c s to \c t if there exists,
2046    ///\ref INVALID otherwise.
2047    ///
2048    ///\warning If you change the graph, refresh() must be called before using
2049    ///this operator. If you change the outgoing edges of
2050    ///a single node \c n, then
2051    ///\ref refresh(Node) "refresh(n)" is enough.
2052    ///
2053    Edge operator()(Node s, Node t) const
2054    {
2055      Edge e;
2056      for(e=_head[s];
2057          e!=INVALID&&_g.target(e)!=t;
2058          e = t < _g.target(e)?_left[e]:_right[e]) ;
2059      return e;
2060    }
2061
2062  };
2063
2064  ///Fast look up of all edges between given endpoints.
2065 
2066  ///\ingroup gutils
2067  ///This class is the same as \ref EdgeLookUp, with the addition
2068  ///that it makes it possible to find all edges between given endpoints.
2069  ///
2070  ///\warning This class is static, so you should refresh() (or at least
2071  ///refresh(Node)) this data structure
2072  ///whenever the graph changes. This is a time consuming (superlinearly
2073  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2074  ///
2075  ///\param G The type of the underlying graph.
2076  ///
2077  ///\sa EdgeLookUp 
2078  template<class G>
2079  class AllEdgeLookUp : public EdgeLookUp<G>
2080  {
2081    using EdgeLookUp<G>::_g;
2082    using EdgeLookUp<G>::_right;
2083    using EdgeLookUp<G>::_left;
2084    using EdgeLookUp<G>::_head;
2085
2086    GRAPH_TYPEDEFS(typename G)
2087    typedef G Graph;
2088   
2089    typename Graph::template EdgeMap<Edge> _next;
2090   
2091    Edge refreshNext(Edge head,Edge next=INVALID)
2092    {
2093      if(head==INVALID) return next;
2094      else {
2095        next=refreshNext(_right[head],next);
2096//      _next[head]=next;
2097        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2098          ? next : INVALID;
2099        return refreshNext(_left[head],head);
2100      }
2101    }
2102   
2103    void refreshNext()
2104    {
2105      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2106    }
2107   
2108  public:
2109    ///Constructor
2110
2111    ///Constructor.
2112    ///
2113    ///It builds up the search database, which remains valid until the graph
2114    ///changes.
2115    AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
2116
2117    ///Refresh the data structure at a node.
2118
2119    ///Build up the search database of node \c n.
2120    ///
2121    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2122    ///the number of the outgoing edges of \c n.
2123   
2124    void refresh(Node n)
2125    {
2126      EdgeLookUp<G>::refresh(n);
2127      refreshNext(_head[n]);
2128    }
2129   
2130    ///Refresh the full data structure.
2131
2132    ///Build up the full search database. In fact, it simply calls
2133    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2134    ///
2135    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2136    ///the number of the edges of \c n and <em>D</em> is the maximum
2137    ///out-degree of the graph.
2138
2139    void refresh()
2140    {
2141      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2142    }
2143   
2144    ///Find an edge between two nodes.
2145   
2146    ///Find an edge between two nodes.
2147    ///\param s The source node
2148    ///\param t The target node
2149    ///\param prev The previous edge between \c s and \c t. It it is INVALID or
2150    ///not given, the operator finds the first appropriate edge.
2151    ///\return An edge from \c s to \c t after \prev or
2152    ///\ref INVALID if there is no more.
2153    ///
2154    ///For example, you can count the number of edges from \c u to \c v in the
2155    ///following way.
2156    ///\code
2157    ///AllEdgeLookUp<ListGraph> ae(g);
2158    ///...
2159    ///int n=0;
2160    ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
2161    ///\endcode
2162    ///
2163    ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
2164    /// <em>d</em> is the number of outgoing edges of \c s. Then, the
2165    ///consecutive edges are found in constant time.
2166    ///
2167    ///\warning If you change the graph, refresh() must be called before using
2168    ///this operator. If you change the outgoing edges of
2169    ///a single node \c n, then
2170    ///\ref refresh(Node) "refresh(n)" is enough.
2171    ///
2172#ifdef DOXYGEN
2173    Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
2174#else
2175    using EdgeLookUp<G>::operator() ;
2176    Edge operator()(Node s, Node t, Edge prev) const
2177    {
2178      return prev==INVALID?(*this)(s,t):_next[prev];
2179    }
2180#endif
2181     
2182  };
2183
2184  /// @}
2185
2186} //END OF NAMESPACE LEMON
2187
2188#endif
Note: See TracBrowser for help on using the repository browser.