COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2539:c25f62a6452d

Last change on this file since 2539:c25f62a6452d was 2539:c25f62a6452d, checked in by Balazs Dezso, 16 years ago

DynEdgeLookUp? implementation based on splay trees
In general case it is slower than the static version, but it should not
refreshed on the change of the graph

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