COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h

Last change on this file was 2616:02971275e7bf, checked in by Balazs Dezso, 16 years ago

Back port bug fix from hg changeset [0915721396dc]

File size: 93.2 KB
RevLine 
[946]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2553]5 * Copyright (C) 2003-2008
[1956]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[946]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>
[1419]23#include <vector>
[1402]24#include <map>
[2569]25#include <lemon/math.h>
[2235]26#include <algorithm>
[946]27
[1993]28#include <lemon/bits/invalid.h>
29#include <lemon/bits/utility.h>
[1413]30#include <lemon/maps.h>
[1993]31#include <lemon/bits/traits.h>
[1990]32
[1459]33#include <lemon/bits/alteration_notifier.h>
[1990]34#include <lemon/bits/default_map.h>
[946]35
[947]36///\ingroup gutils
[946]37///\file
[947]38///\brief Graph utilities.
[946]39
40namespace lemon {
41
[1267]42  /// \addtogroup gutils
43  /// @{
[947]44
[1756]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,
[2031]49  ///\c OutEdgeIt
[1756]50  ///\note If \c G it a template parameter, it should be used in this way.
51  ///\code
[2510]52  ///  GRAPH_TYPEDEFS(typename G);
[1756]53  ///\endcode
54  ///
55  ///\warning There are no typedefs for the graph maps because of the lack of
56  ///template typedefs in C++.
[1804]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;                 \
[2510]63    typedef Graph::OutEdgeIt OutEdgeIt
[2031]64
[1756]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
[1909]69  ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
[1756]70  ///
71  ///\note If \c G it a template parameter, it should be used in this way.
72  ///\code
[2510]73  ///  UGRAPH_TYPEDEFS(typename G);
[1756]74  ///\endcode
75  ///
76  ///\warning There are no typedefs for the graph maps because of the lack of
77  ///template typedefs in C++.
[1992]78#define UGRAPH_TYPEDEFS(Graph)                          \
[2510]79  GRAPH_TYPEDEFS(Graph);                                \
[1909]80    typedef Graph:: UEdge   UEdge;                      \
81    typedef Graph:: UEdgeIt UEdgeIt;                    \
[2510]82    typedef Graph:: IncEdgeIt   IncEdgeIt
[1756]83
[2031]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
[2510]93  ///  BPUGRAPH_TYPEDEFS(typename G);
[2031]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)            \
[2510]99  UGRAPH_TYPEDEFS(Graph);                   \
[2286]100    typedef Graph::ANode ANode;             \
101    typedef Graph::BNode BNode;             \
[2031]102    typedef Graph::ANodeIt ANodeIt;         \
[2510]103    typedef Graph::BNodeIt BNodeIt
[1756]104
[946]105  /// \brief Function to count the items in the graph.
106  ///
[1540]107  /// This function counts the items (nodes, edges etc) in the graph.
[946]108  /// The complexity of the function is O(n) because
109  /// it iterates on all of the items.
110
[2020]111  template <typename Graph, typename Item>
[977]112  inline int countItems(const Graph& g) {
[2020]113    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
[946]114    int num = 0;
[977]115    for (ItemIt it(g); it != INVALID; ++it) {
[946]116      ++num;
117    }
118    return num;
119  }
120
[977]121  // Node counting:
122
[2020]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    };
[977]131
[2020]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    };   
[977]141  }
142
[946]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
[1526]147  /// graph structures it is specialized to run in O(1).
[977]148  ///
[2485]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.
[946]152  template <typename Graph>
[977]153  inline int countNodes(const Graph& g) {
[2020]154    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
[977]155  }
156
[2029]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) {
[2186]172        return g.aNodeNum();
[2029]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  ///
[2485]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.
[2029]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) {
[2186]206        return g.bNodeNum();
[2029]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  ///
[2485]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.
[2029]220  template <typename Graph>
221  inline int countBNodes(const Graph& g) {
222    return _graph_utils_bits::CountBNodesSelector<Graph>::count(g);
223  }
224
[2020]225
[977]226  // Edge counting:
227
[2020]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    };
[977]236
[2020]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    };   
[946]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
[1526]252  /// graph structures it is specialized to run in O(1).
[2485]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.
[946]257  template <typename Graph>
[977]258  inline int countEdges(const Graph& g) {
[2020]259    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
[946]260  }
261
[1053]262  // Undirected edge counting:
[2020]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    };
[1053]271
[2020]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    };   
[1053]281  }
282
[1526]283  /// \brief Function to count the undirected edges in the graph.
[946]284  ///
[1526]285  /// This function counts the undirected edges in the graph.
[946]286  /// The complexity of the function is O(e) but for some
[1540]287  /// graph structures it is specialized to run in O(1).
[2485]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.
[946]292  template <typename Graph>
[1909]293  inline int countUEdges(const Graph& g) {
[2020]294    return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
295
[946]296  }
297
[977]298
[946]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  }
[967]307
[1531]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
[1704]326  /// \brief Function to count the number of the inc-edges to node \c n.
[1679]327  ///
[1704]328  /// This function counts the number of the inc-edges to node \c n
[1679]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
[2020]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    };
[1531]353
[2020]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    };   
[1565]365  }
366
367  /// \brief Finds an edge between two nodes of a graph.
368  ///
[967]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.
[1946]377  ///\code
[967]378  /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
379  ///   ...
380  /// }
[1946]381  ///\endcode
[2155]382  ///
[2235]383  ///\sa EdgeLookUp
[2476]384  ///\sa AllEdgeLookUp
[2539]385  ///\sa DynEdgeLookUp
[2155]386  ///\sa ConEdgeIt
[967]387  template <typename Graph>
[2286]388  inline typename Graph::Edge
389  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
390           typename Graph::Edge prev = INVALID) {
[2020]391    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
[967]392  }
[1531]393
[1565]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
[1591]398  /// use it the following way:
[1946]399  ///\code
[1565]400  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
401  ///   ...
402  /// }
[1946]403  ///\endcode
[2155]404  ///
405  ///\sa findEdge()
[2235]406  ///\sa EdgeLookUp
[2474]407  ///\sa AllEdgeLookUp
[2539]408  ///\sa DynEdgeLookUp
[1565]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
[2020]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) {
[2031]457            g.firstInc(e, b, u);
[2020]458          } else {
459            b = g.source(e) == u;
460            g.nextInc(e, b);
461          }
[2064]462          while (e != INVALID && (b ? g.target(e) : g.source(e)) != v) {
[2020]463            g.nextInc(e, b);
464          }
465        } else {
466          if (e == INVALID) {
[2031]467            g.firstInc(e, b, u);
[2020]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    };
[1704]479
[2020]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    };   
[1704]491  }
492
[1909]493  /// \brief Finds an uedge between two nodes of a graph.
[1704]494  ///
[1909]495  /// Finds an uedge from node \c u to node \c v in graph \c g.
[2020]496  /// If the node \c u and node \c v is equal then each loop edge
497  /// will be enumerated.
[1704]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.
[1946]505  ///\code
[1909]506  /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
507  ///     e = findUEdge(g,u,v,e)) {
[1704]508  ///   ...
509  /// }
[1946]510  ///\endcode
[2155]511  ///
512  ///\sa ConEdgeIt
513
[1704]514  template <typename Graph>
[2286]515  inline typename Graph::UEdge
516  findUEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
517            typename Graph::UEdge p = INVALID) {
[2031]518    return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
[1704]519  }
520
[1909]521  /// \brief Iterator for iterating on uedges connected the same nodes.
[1704]522  ///
[1909]523  /// Iterator for iterating on uedges connected the same nodes. It is
524  /// higher level interface for the findUEdge() function. You can
[1704]525  /// use it the following way:
[1946]526  ///\code
[1909]527  /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
[1704]528  ///   ...
529  /// }
[1946]530  ///\endcode
[1704]531  ///
[2155]532  ///\sa findUEdge()
533  ///
[1704]534  /// \author Balazs Dezso
535  template <typename _Graph>
[1909]536  class ConUEdgeIt : public _Graph::UEdge {
[1704]537  public:
538
539    typedef _Graph Graph;
[1909]540    typedef typename Graph::UEdge Parent;
[1704]541
[1909]542    typedef typename Graph::UEdge UEdge;
[1704]543    typedef typename Graph::Node Node;
544
545    /// \brief Constructor.
546    ///
[1909]547    /// Construct a new ConUEdgeIt iterating on the edges which
[1704]548    /// connects the \c u and \c v node.
[1909]549    ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
550      Parent::operator=(findUEdge(graph, u, v));
[1704]551    }
552
553    /// \brief Constructor.
554    ///
[1909]555    /// Construct a new ConUEdgeIt which continues the iterating from
[1704]556    /// the \c e edge.
[1909]557    ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
[1704]558   
559    /// \brief Increment operator.
560    ///
561    /// It increments the iterator and gives back the next edge.
[1909]562    ConUEdgeIt& operator++() {
563      Parent::operator=(findUEdge(graph, graph.source(*this),
[1829]564                                      graph.target(*this), *this));
[1704]565      return *this;
566    }
567  private:
568    const Graph& graph;
569  };
570
[1540]571  /// \brief Copy a map.
[964]572  ///
[2485]573  /// This function copies the \c from map to the \c to map. It uses the
[1540]574  /// given iterator to iterate on the data structure and it uses the \c ref
[2485]575  /// mapping to convert the from's keys to the to's keys.
576  template <typename To, typename From,
[1531]577            typename ItemIt, typename Ref>         
[2485]578  void copyMap(To& to, const From& from,
[1531]579               ItemIt it, const Ref& ref) {
580    for (; it != INVALID; ++it) {
[2485]581      to[ref[it]] = from[it];
[946]582    }
583  }
584
[2485]585  /// \brief Copy the from map to the to map.
[1531]586  ///
[2485]587  /// Copy the \c from map to the \c to map. It uses the given iterator
[1531]588  /// to iterate on the data structure.
[2485]589  template <typename To, typename From, typename ItemIt>           
590  void copyMap(To& to, const From& from, ItemIt it) {
[1531]591    for (; it != INVALID; ++it) {
[2485]592      to[it] = from[it];
[946]593    }
594  }
595
[2286]596  namespace _graph_utils_bits {
597
598    template <typename Graph, typename Item, typename RefMap>
599    class MapCopyBase {
600    public:
[2485]601      virtual void copy(const Graph& from, const RefMap& refMap) = 0;
[2286]602     
603      virtual ~MapCopyBase() {}
604    };
605
606    template <typename Graph, typename Item, typename RefMap,
[2485]607              typename ToMap, typename FromMap>
[2286]608    class MapCopy : public MapCopyBase<Graph, Item, RefMap> {
609    public:
610
[2485]611      MapCopy(ToMap& tmap, const FromMap& map)
[2286]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:
[2485]622      ToMap& _tmap;
623      const FromMap& _map;
[2286]624    };
625
[2290]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
[2286]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
[2290]676    template <typename Graph, typename Enable = void>
677    struct GraphCopySelector {
[2485]678      template <typename From, typename NodeRefMap, typename EdgeRefMap>
679      static void copy(Graph &to, const From& from,
[2290]680                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
[2485]681        for (typename From::NodeIt it(from); it != INVALID; ++it) {
682          nodeRefMap[it] = to.addNode();
[2290]683        }
[2485]684        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
685          edgeRefMap[it] = to.addEdge(nodeRefMap[from.source(it)],
686                                          nodeRefMap[from.target(it)]);
[2290]687        }
688      }
689    };
690
691    template <typename Graph>
692    struct GraphCopySelector<
693      Graph,
[2329]694      typename enable_if<typename Graph::BuildTag, void>::type>
[2290]695    {
[2485]696      template <typename From, typename NodeRefMap, typename EdgeRefMap>
697      static void copy(Graph &to, const From& from,
[2290]698                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
[2485]699        to.build(from, nodeRefMap, edgeRefMap);
[2290]700      }
701    };
702
703    template <typename UGraph, typename Enable = void>
704    struct UGraphCopySelector {
[2485]705      template <typename From, typename NodeRefMap, typename UEdgeRefMap>
706      static void copy(UGraph &to, const From& from,
[2290]707                       NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
[2485]708        for (typename From::NodeIt it(from); it != INVALID; ++it) {
709          nodeRefMap[it] = to.addNode();
[2290]710        }
[2485]711        for (typename From::UEdgeIt it(from); it != INVALID; ++it) {
712          uEdgeRefMap[it] = to.addEdge(nodeRefMap[from.source(it)],
713                                       nodeRefMap[from.target(it)]);
[2290]714        }
715      }
716    };
717
718    template <typename UGraph>
719    struct UGraphCopySelector<
720      UGraph,
[2329]721      typename enable_if<typename UGraph::BuildTag, void>::type>
[2290]722    {
[2485]723      template <typename From, typename NodeRefMap, typename UEdgeRefMap>
724      static void copy(UGraph &to, const From& from,
[2290]725                       NodeRefMap& nodeRefMap, UEdgeRefMap& uEdgeRefMap) {
[2485]726        to.build(from, nodeRefMap, uEdgeRefMap);
[2290]727      }
728    };
729
730    template <typename BpUGraph, typename Enable = void>
731    struct BpUGraphCopySelector {
[2485]732      template <typename From, typename ANodeRefMap,
[2290]733                typename BNodeRefMap, typename UEdgeRefMap>
[2485]734      static void copy(BpUGraph &to, const From& from,
[2290]735                       ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
736                       UEdgeRefMap& uEdgeRefMap) {
[2485]737        for (typename From::ANodeIt it(from); it != INVALID; ++it) {
738          aNodeRefMap[it] = to.addANode();
[2290]739        }
[2485]740        for (typename From::BNodeIt it(from); it != INVALID; ++it) {
741          bNodeRefMap[it] = to.addBNode();
[2290]742        }
[2485]743        for (typename From::UEdgeIt it(from); it != INVALID; ++it) {
744          uEdgeRefMap[it] = to.addEdge(aNodeRefMap[from.aNode(it)],
745                                           bNodeRefMap[from.bNode(it)]);
[2290]746        }
747      }
748    };
749
750    template <typename BpUGraph>
751    struct BpUGraphCopySelector<
752      BpUGraph,
[2329]753      typename enable_if<typename BpUGraph::BuildTag, void>::type>
[2290]754    {
[2485]755      template <typename From, typename ANodeRefMap,
[2290]756                typename BNodeRefMap, typename UEdgeRefMap>
[2485]757      static void copy(BpUGraph &to, const From& from,
[2290]758                       ANodeRefMap& aNodeRefMap, BNodeRefMap& bNodeRefMap,
759                       UEdgeRefMap& uEdgeRefMap) {
[2485]760        to.build(from, aNodeRefMap, bNodeRefMap, uEdgeRefMap);
[2290]761      }
762    };
763   
764
[2286]765  }
766
[1540]767  /// \brief Class to copy a graph.
[1531]768  ///
[2006]769  /// Class to copy a graph to another graph (duplicate a graph). The
[1540]770  /// simplest way of using it is through the \c copyGraph() function.
[2485]771  template <typename To, typename From>
[1267]772  class GraphCopy {
[2286]773  private:
774
[2485]775    typedef typename From::Node Node;
776    typedef typename From::NodeIt NodeIt;
777    typedef typename From::Edge Edge;
778    typedef typename From::EdgeIt EdgeIt;
[946]779
[2485]780    typedef typename To::Node TNode;
781    typedef typename To::Edge TEdge;
[2286]782
[2485]783    typedef typename From::template NodeMap<TNode> NodeRefMap;
784    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
[2286]785   
786   
787  public:
788
[946]789
[1531]790    /// \brief Constructor for the GraphCopy.
791    ///
[2485]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) {}
[2286]796
797    /// \brief Destructor of the GraphCopy
798    ///
799    /// Destructor of the GraphCopy
800    ~GraphCopy() {
[2386]801      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
[2286]802        delete nodeMapCopies[i];
[1531]803      }
[2386]804      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
[2286]805        delete edgeMapCopies[i];
[1531]806      }
[2286]807
[1267]808    }
[946]809
[1531]810    /// \brief Copies the node references into the given map.
811    ///
812    /// Copies the node references into the given map.
813    template <typename NodeRef>
[2286]814    GraphCopy& nodeRef(NodeRef& map) {
[2485]815      nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Node,
[2286]816                              NodeRefMap, NodeRef>(map));
[1531]817      return *this;
[1267]818    }
[1531]819
[2290]820    /// \brief Copies the node cross references into the given map.
[1531]821    ///
[2290]822    ///  Copies the node cross references (reverse references) into
823    ///  the given map.
[2286]824    template <typename NodeCrossRef>
825    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
[2485]826      nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
[2286]827                              NodeRefMap, NodeCrossRef>(map));
[1531]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.
[2485]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
[1531]836    /// type. 
[2485]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));
[2286]841      return *this;
842    }
843
[2290]844    /// \brief Make a copy of the given node.
845    ///
846    /// Make a copy of the given node.
[2386]847    GraphCopy& node(TNode& tnode, const Node& snode) {
[2485]848      nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Node,
[2386]849                              NodeRefMap, TNode>(tnode, snode));
[2290]850      return *this;
851    }
852
[2286]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) {
[2485]858      edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Edge,
[2286]859                              EdgeRefMap, EdgeRef>(map));
860      return *this;
861    }
862
[2290]863    /// \brief Copies the edge cross references into the given map.
[2286]864    ///
[2290]865    ///  Copies the edge cross references (reverse references) into
866    ///  the given map.
[2286]867    template <typename EdgeCrossRef>
868    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
[2485]869      edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Edge,
[2286]870                              EdgeRefMap, EdgeCrossRef>(map));
[1531]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.
[2485]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
[1531]879    /// type. 
[2485]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));
[1531]884      return *this;
885    }
886
[2290]887    /// \brief Make a copy of the given edge.
888    ///
889    /// Make a copy of the given edge.
[2386]890    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
[2485]891      edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
[2386]892                              EdgeRefMap, TEdge>(tedge, sedge));
[2290]893      return *this;
894    }
895
[2286]896    /// \brief Executes the copies.
[1531]897    ///
[2286]898    /// Executes the copies.
899    void run() {
[2485]900      NodeRefMap nodeRefMap(from);
901      EdgeRefMap edgeRefMap(from);
902      _graph_utils_bits::GraphCopySelector<To>::
903        copy(to, from, nodeRefMap, edgeRefMap);
[2386]904      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
[2485]905        nodeMapCopies[i]->copy(from, nodeRefMap);
[2286]906      }
[2386]907      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
[2485]908        edgeMapCopies[i]->copy(from, edgeRefMap);
[2290]909      }     
[1531]910    }
911
[2290]912  protected:
913
914
[2485]915    const From& from;
916    To& to;
[1531]917
[2485]918    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
[2286]919    nodeMapCopies;
920
[2485]921    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
[2286]922    edgeMapCopies;
923
[1267]924  };
[946]925
[2006]926  /// \brief Copy a graph to another graph.
[1531]927  ///
[2006]928  /// Copy a graph to another graph.
[1531]929  /// The usage of the function:
930  ///
[1946]931  ///\code
[2286]932  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
[1946]933  ///\endcode
[1531]934  ///
935  /// After the copy the \c nr map will contain the mapping from the
[2534]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.
[2290]939  ///
940  /// \see GraphCopy
[2485]941  template <typename To, typename From>
942  GraphCopy<To, From> copyGraph(To& to, const From& from) {
943    return GraphCopy<To, From>(to, from);
[1531]944  }
[946]945
[1720]946  /// \brief Class to copy an undirected graph.
947  ///
[2006]948  /// Class to copy an undirected graph to another graph (duplicate a graph).
[1909]949  /// The simplest way of using it is through the \c copyUGraph() function.
[2485]950  template <typename To, typename From>
[1909]951  class UGraphCopy {
[2286]952  private:
953
[2485]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;
[1720]960
[2485]961    typedef typename To::Node TNode;
962    typedef typename To::Edge TEdge;
963    typedef typename To::UEdge TUEdge;
[1720]964
[2485]965    typedef typename From::template NodeMap<TNode> NodeRefMap;
966    typedef typename From::template UEdgeMap<TUEdge> UEdgeRefMap;
[1720]967
968    struct EdgeRefMap {
[2485]969      EdgeRefMap(const To& _to, const From& _from,
[2286]970                 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
[2485]971        : to(_to), from(_from),
[2286]972          uedge_ref(_uedge_ref), node_ref(_node_ref) {}
973
[2485]974      typedef typename From::Edge Key;
975      typedef typename To::Edge Value;
[1720]976
[2286]977      Value operator[](const Key& key) const {
[2386]978        bool forward =
[2485]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);
[1720]983      }
984     
[2485]985      const To& to;
986      const From& from;
[2286]987      const UEdgeRefMap& uedge_ref;
988      const NodeRefMap& node_ref;
[1720]989    };
[2286]990
[1720]991   
[2286]992  public:
[1720]993
[2286]994
995    /// \brief Constructor for the GraphCopy.
[1720]996    ///
[2485]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) {}
[2286]1001
1002    /// \brief Destructor of the GraphCopy
1003    ///
1004    /// Destructor of the GraphCopy
1005    ~UGraphCopy() {
[2386]1006      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
[2286]1007        delete nodeMapCopies[i];
[1720]1008      }
[2386]1009      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
[2286]1010        delete edgeMapCopies[i];
[1720]1011      }
[2386]1012      for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
[2286]1013        delete uEdgeMapCopies[i];
1014      }
1015
[1720]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>
[2286]1022    UGraphCopy& nodeRef(NodeRef& map) {
[2485]1023      nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Node,
[2286]1024                              NodeRefMap, NodeRef>(map));
[1720]1025      return *this;
1026    }
1027
[2290]1028    /// \brief Copies the node cross references into the given map.
[1720]1029    ///
[2290]1030    ///  Copies the node cross references (reverse references) into
1031    ///  the given map.
[2286]1032    template <typename NodeCrossRef>
1033    UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
[2485]1034      nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
[2286]1035                              NodeRefMap, NodeCrossRef>(map));
[1720]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.
[2485]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
[1720]1044    /// type. 
[2485]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));
[2286]1049      return *this;
1050    }
1051
[2290]1052    /// \brief Make a copy of the given node.
1053    ///
1054    /// Make a copy of the given node.
[2386]1055    UGraphCopy& node(TNode& tnode, const Node& snode) {
[2485]1056      nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Node,
[2386]1057                              NodeRefMap, TNode>(tnode, snode));
[2290]1058      return *this;
1059    }
1060
[2286]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) {
[2485]1066      edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Edge,
[2286]1067                              EdgeRefMap, EdgeRef>(map));
1068      return *this;
1069    }
1070
[2290]1071    /// \brief Copies the edge cross references into the given map.
[2286]1072    ///
[2290]1073    ///  Copies the edge cross references (reverse references) into
1074    ///  the given map.
[2286]1075    template <typename EdgeCrossRef>
1076    UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
[2485]1077      edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Edge,
[2286]1078                              EdgeRefMap, EdgeCrossRef>(map));
[1720]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.
[2485]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
[1720]1087    /// type. 
[2485]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));
[2286]1092      return *this;
1093    }
1094
[2290]1095    /// \brief Make a copy of the given edge.
[2286]1096    ///
[2290]1097    /// Make a copy of the given edge.
[2386]1098    UGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
[2485]1099      edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
[2386]1100                              EdgeRefMap, TEdge>(tedge, sedge));
[2290]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.
[2286]1107    template <typename UEdgeRef>
1108    UGraphCopy& uEdgeRef(UEdgeRef& map) {
[2485]1109      uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, UEdge,
[2286]1110                               UEdgeRefMap, UEdgeRef>(map));
1111      return *this;
1112    }
1113
[2290]1114    /// \brief Copies the undirected edge cross references into the given map.
[2286]1115    ///
[2290]1116    /// Copies the undirected edge cross references (reverse
1117    /// references) into the given map.
[2286]1118    template <typename UEdgeCrossRef>
1119    UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
[2485]1120      uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
[2286]1121                               UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
[1720]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.
[2485]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
[1720]1130    /// type. 
[2485]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));
[1720]1135      return *this;
1136    }
1137
[2290]1138    /// \brief Make a copy of the given undirected edge.
1139    ///
1140    /// Make a copy of the given undirected edge.
[2386]1141    UGraphCopy& uEdge(TUEdge& tuedge, const UEdge& suedge) {
[2485]1142      uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, UEdge,
[2386]1143                               UEdgeRefMap, TUEdge>(tuedge, suedge));
[2290]1144      return *this;
1145    }
1146
[2286]1147    /// \brief Executes the copies.
[1720]1148    ///
[2286]1149    /// Executes the copies.
1150    void run() {
[2485]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);
[2386]1156      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
[2485]1157        nodeMapCopies[i]->copy(from, nodeRefMap);
[2286]1158      }
[2386]1159      for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
[2485]1160        uEdgeMapCopies[i]->copy(from, uEdgeRefMap);
[2286]1161      }
[2386]1162      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
[2485]1163        edgeMapCopies[i]->copy(from, edgeRefMap);
[2286]1164      }
[1720]1165    }
1166
1167  private:
[1192]1168   
[2485]1169    const From& from;
1170    To& to;
[947]1171
[2485]1172    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
[2286]1173    nodeMapCopies;
1174
[2485]1175    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
[2286]1176    edgeMapCopies;
1177
[2485]1178    std::vector<_graph_utils_bits::MapCopyBase<From, UEdge, UEdgeRefMap>* >
[2286]1179    uEdgeMapCopies;
1180
[1192]1181  };
1182
[2290]1183  /// \brief Copy an undirected graph to another graph.
[1720]1184  ///
[2290]1185  /// Copy an undirected graph to another graph.
[1720]1186  /// The usage of the function:
1187  ///
[1946]1188  ///\code
[2286]1189  /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
[1946]1190  ///\endcode
[1720]1191  ///
1192  /// After the copy the \c nr map will contain the mapping from the
[2534]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.
[2290]1196  ///
1197  /// \see UGraphCopy
[2485]1198  template <typename To, typename From>
1199  UGraphCopy<To, From>
1200  copyUGraph(To& to, const From& from) {
1201    return UGraphCopy<To, From>(to, from);
[1720]1202  }
[1192]1203
[2290]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.
[2485]1209  template <typename To, typename From>
[2290]1210  class BpUGraphCopy {
1211  private:
1212
[2485]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;
[2290]1221
[2485]1222    typedef typename To::Node TNode;
1223    typedef typename To::Edge TEdge;
1224    typedef typename To::UEdge TUEdge;
[2290]1225
[2485]1226    typedef typename From::template ANodeMap<TNode> ANodeRefMap;
1227    typedef typename From::template BNodeMap<TNode> BNodeRefMap;
1228    typedef typename From::template UEdgeMap<TUEdge> UEdgeRefMap;
[2290]1229
1230    struct NodeRefMap {
[2485]1231      NodeRefMap(const From& _from, const ANodeRefMap& _anode_ref,
[2290]1232                 const BNodeRefMap& _bnode_ref)
[2485]1233        : from(_from), anode_ref(_anode_ref), bnode_ref(_bnode_ref) {}
[2290]1234
[2485]1235      typedef typename From::Node Key;
1236      typedef typename To::Node Value;
[2290]1237
1238      Value operator[](const Key& key) const {
[2485]1239        return from.aNode(key) ? anode_ref[key] : bnode_ref[key];
[2290]1240      }
1241     
[2485]1242      const From& from;
[2290]1243      const ANodeRefMap& anode_ref;
1244      const BNodeRefMap& bnode_ref;
1245    };
1246
1247    struct EdgeRefMap {
[2485]1248      EdgeRefMap(const To& _to, const From& _from,
[2290]1249                 const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
[2485]1250        : to(_to), from(_from),
[2290]1251          uedge_ref(_uedge_ref), node_ref(_node_ref) {}
1252
[2485]1253      typedef typename From::Edge Key;
1254      typedef typename To::Edge Value;
[2290]1255
1256      Value operator[](const Key& key) const {
[2386]1257        bool forward =
[2485]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);
[2290]1262      }
1263     
[2485]1264      const To& to;
1265      const From& from;
[2290]1266      const UEdgeRefMap& uedge_ref;
1267      const NodeRefMap& node_ref;
1268    };
1269   
1270  public:
1271
1272
1273    /// \brief Constructor for the GraphCopy.
1274    ///
[2485]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) {}
[2290]1279
1280    /// \brief Destructor of the GraphCopy
1281    ///
1282    /// Destructor of the GraphCopy
1283    ~BpUGraphCopy() {
[2386]1284      for (int i = 0; i < int(aNodeMapCopies.size()); ++i) {
[2290]1285        delete aNodeMapCopies[i];
1286      }
[2386]1287      for (int i = 0; i < int(bNodeMapCopies.size()); ++i) {
[2290]1288        delete bNodeMapCopies[i];
1289      }
[2386]1290      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
[2290]1291        delete nodeMapCopies[i];
1292      }
[2386]1293      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
[2290]1294        delete edgeMapCopies[i];
1295      }
[2386]1296      for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
[2290]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) {
[2485]1307      aNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, ANode,
[2290]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) {
[2485]1318      aNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
[2290]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.
[2485]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
[2290]1328    /// type. 
[2485]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));
[2290]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) {
[2485]1341      bNodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, BNode,
[2290]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) {
[2485]1352      bNodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
[2290]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.
[2485]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
[2290]1362    /// type. 
[2485]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));
[2290]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) {
[2485]1374      nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Node,
[2290]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) {
[2485]1385      nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
[2290]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.
[2485]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
[2290]1395    /// type. 
[2485]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));
[2290]1400      return *this;
1401    }
1402
1403    /// \brief Make a copy of the given node.
1404    ///
1405    /// Make a copy of the given node.
[2386]1406    BpUGraphCopy& node(TNode& tnode, const Node& snode) {
[2485]1407      nodeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Node,
[2386]1408                              NodeRefMap, TNode>(tnode, snode));
[2290]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) {
[2485]1417      edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, Edge,
[2290]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) {
[2485]1428      edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From, Edge,
[2290]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.
[2485]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
[2290]1438    /// type. 
[2485]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));
[2290]1443      return *this;
1444    }
1445
1446    /// \brief Make a copy of the given edge.
1447    ///
1448    /// Make a copy of the given edge.
[2386]1449    BpUGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
[2485]1450      edgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
[2386]1451                              EdgeRefMap, TEdge>(tedge, sedge));
[2290]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) {
[2485]1460      uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<From, UEdge,
[2290]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) {
[2485]1471      uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<From,
[2290]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.
[2485]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
[2290]1481    /// type. 
[2485]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));
[2290]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.
[2386]1492    BpUGraphCopy& uEdge(TUEdge& tuedge, const UEdge& suedge) {
[2485]1493      uEdgeMapCopies.push_back(new _graph_utils_bits::ItemCopy<From, UEdge,
[2386]1494                               UEdgeRefMap, TUEdge>(tuedge, suedge));
[2290]1495      return *this;
1496    }
1497
1498    /// \brief Executes the copies.
1499    ///
1500    /// Executes the copies.
1501    void run() {
[2485]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);
[2386]1509      for (int i = 0; i < int(aNodeMapCopies.size()); ++i) {
[2485]1510        aNodeMapCopies[i]->copy(from, aNodeRefMap);
[2290]1511      }
[2386]1512      for (int i = 0; i < int(bNodeMapCopies.size()); ++i) {
[2485]1513        bNodeMapCopies[i]->copy(from, bNodeRefMap);
[2290]1514      }
[2386]1515      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
[2485]1516        nodeMapCopies[i]->copy(from, nodeRefMap);
[2290]1517      }
[2386]1518      for (int i = 0; i < int(uEdgeMapCopies.size()); ++i) {
[2485]1519        uEdgeMapCopies[i]->copy(from, uEdgeRefMap);
[2290]1520      }
[2386]1521      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
[2485]1522        edgeMapCopies[i]->copy(from, edgeRefMap);
[2290]1523      }
1524    }
1525
1526  private:
1527   
[2485]1528    const From& from;
1529    To& to;
[2290]1530
[2485]1531    std::vector<_graph_utils_bits::MapCopyBase<From, ANode, ANodeRefMap>* >
[2290]1532    aNodeMapCopies;
1533
[2485]1534    std::vector<_graph_utils_bits::MapCopyBase<From, BNode, BNodeRefMap>* >
[2290]1535    bNodeMapCopies;
1536
[2485]1537    std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
[2290]1538    nodeMapCopies;
1539
[2485]1540    std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
[2290]1541    edgeMapCopies;
1542
[2485]1543    std::vector<_graph_utils_bits::MapCopyBase<From, UEdge, UEdgeRefMap>* >
[2290]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
[2534]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.
[2290]1561  ///
1562  /// \see BpUGraphCopy
[2485]1563  template <typename To, typename From>
1564  BpUGraphCopy<To, From>
1565  copyBpUGraph(To& to, const From& from) {
1566    return BpUGraphCopy<To, From>(to, from);
[2290]1567  }
1568
[1192]1569
1570  /// @}
[1402]1571
1572  /// \addtogroup graph_maps
1573  /// @{
1574
[1413]1575  /// Provides an immutable and unique id for each item in the graph.
1576
[1540]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.
[1413]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    ///
[2331]1595    /// Constructor of the map.
[2286]1596    explicit IdMap(const Graph& _graph) : graph(&_graph) {}
[1413]1597
1598    /// \brief Gives back the \e id of the item.
1599    ///
[2331]1600    /// Gives back the immutable and unique \e id of the item.
[1413]1601    int operator[](const Item& item) const { return graph->id(item);}
1602
[2331]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()); }
[1413]1607
1608  private:
1609    const Graph* graph;
1610
1611  public:
1612
[1540]1613    /// \brief The class represents the inverse of its owner (IdMap).
[1413]1614    ///
[1540]1615    /// The class represents the inverse of its owner (IdMap).
[1413]1616    /// \see inverse()
1617    class InverseMap {
1618    public:
[1419]1619
[1413]1620      /// \brief Constructor.
1621      ///
1622      /// Constructor for creating an id-to-item map.
[2286]1623      explicit InverseMap(const Graph& _graph) : graph(&_graph) {}
[1413]1624
1625      /// \brief Constructor.
1626      ///
1627      /// Constructor for creating an id-to-item map.
[2286]1628      explicit InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
[1413]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());}
[2331]1635
[1413]1636    private:
1637      const Graph* graph;
1638    };
1639
1640    /// \brief Gives back the inverse of the map.
1641    ///
[1540]1642    /// Gives back the inverse of the IdMap.
[1413]1643    InverseMap inverse() const { return InverseMap(*graph);}
1644
1645  };
1646
1647 
[1526]1648  /// \brief General invertable graph-map type.
[1402]1649
[1540]1650  /// This type provides simple invertable graph-maps.
[1526]1651  /// The InvertableMap wraps an arbitrary ReadWriteMap
1652  /// and if a key is set to a new value then store it
[1402]1653  /// in the inverse map.
[1931]1654  ///
1655  /// The values of the map can be accessed
1656  /// with stl compatible forward iterator.
1657  ///
[1402]1658  /// \param _Graph The graph type.
[1830]1659  /// \param _Item The item type of the graph.
1660  /// \param _Value The value type of the map.
[1931]1661  ///
1662  /// \see IterableValueMap
[1830]1663  template <typename _Graph, typename _Item, typename _Value>
[2287]1664  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
[1931]1665  private:
1666   
[2287]1667    typedef DefaultMap<_Graph, _Item, _Value> Map;
[1931]1668    typedef _Graph Graph;
1669
[2287]1670    typedef std::map<_Value, _Item> Container;
[1931]1671    Container invMap;   
1672
1673  public:
1674 
[2287]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
[1931]1680
1681
[1402]1682    /// \brief Constructor.
1683    ///
[1413]1684    /// Construct a new InvertableMap for the graph.
[1402]1685    ///
[2286]1686    explicit InvertableMap(const Graph& graph) : Map(graph) {}
[1931]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    }
[1402]1740   
1741    /// \brief The setter function of the map.
1742    ///
[1413]1743    /// Sets the mapped value.
[1402]1744    void set(const Key& key, const Value& val) {
1745      Value oldval = Map::operator[](key);
[1413]1746      typename Container::iterator it = invMap.find(oldval);
[1402]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.
[1931]1757    typename MapTraits<Map>::ConstReturnValue
1758    operator[](const Key& key) const {
[1402]1759      return Map::operator[](key);
1760    }
1761
[2331]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
[1515]1770  protected:
1771
[1402]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);
[1413]1778      typename Container::iterator it = invMap.find(val);
[1402]1779      if (it != invMap.end() && it->second == key) {
1780        invMap.erase(it);
1781      }
1782      Map::erase(key);
1783    }
1784
[1829]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) {
[2386]1790      for (int i = 0; i < int(keys.size()); ++i) {
[1829]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
[1402]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
[1413]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.
[2286]1820      explicit InverseMap(const InvertableMap& _inverted)
1821        : inverted(_inverted) {}
[1413]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 {
[2331]1833        return inverted(key);
[1413]1834      }
1835     
1836    private:
1837      const InvertableMap& inverted;
1838    };
1839
[2094]1840    /// \brief It gives back the just readable inverse map.
[1402]1841    ///
[2094]1842    /// It gives back the just readable inverse map.
[1413]1843    InverseMap inverse() const {
1844      return InverseMap(*this);
[1402]1845    }
1846
1847
[1413]1848   
[1402]1849  };
1850
1851  /// \brief Provides a mutable, continuous and unique descriptor for each
1852  /// item in the graph.
1853  ///
[1540]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.
[1402]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
[1909]1865  /// UEdge.
[1830]1866  template <typename _Graph, typename _Item>
[2287]1867  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
[1402]1868
1869    typedef _Item Item;
[2287]1870    typedef DefaultMap<_Graph, _Item, int> Map;
[1402]1871
1872  public:
1873    /// The graph class of DescriptorMap.
1874    typedef _Graph Graph;
1875
[1909]1876    /// The key type of DescriptorMap (Node, Edge, UEdge).
[2287]1877    typedef typename Map::Key Key;
[1402]1878    /// The value type of DescriptorMap.
[2287]1879    typedef typename Map::Value Value;
[1402]1880
1881    /// \brief Constructor.
1882    ///
[1413]1883    /// Constructor for descriptor map.
[2286]1884    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
[2201]1885      Item it;
[2386]1886      const typename Map::Notifier* nf = Map::notifier();
1887      for (nf->first(it); it != INVALID; nf->next(it)) {
[2201]1888        Map::set(it, invMap.size());
1889        invMap.push_back(it);   
1890      }     
[1402]1891    }
1892
[1515]1893  protected:
1894
[1402]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
[1829]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);
[2386]1911      for (int i = 0; i < int(items.size()); ++i) {
[1829]1912        Map::set(items[i], invMap.size());
1913        invMap.push_back(items[i]);
1914      }
1915    }
1916
[1402]1917    /// \brief Erase the key from the map.
1918    ///
[1829]1919    /// Erase the key from the map. It is called by the
[1402]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();
[1413]1924      invMap.pop_back();
[1402]1925      Map::erase(item);
1926    }
1927
[1829]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) {
[2386]1933      for (int i = 0; i < int(items.size()); ++i) {
[1829]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
[1402]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;
[2386]1948      const typename Map::Notifier* nf = Map::notifier();
1949      for (nf->first(it); it != INVALID; nf->next(it)) {
[1402]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
[1538]1964  public:
1965
[1931]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
[1552]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
[1402]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    }
[2331]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    }
[1402]1998   
[1413]1999  private:
2000
2001    typedef std::vector<Item> Container;
2002    Container invMap;
2003
2004  public:
[1540]2005    /// \brief The inverse map type of DescriptorMap.
[1413]2006    ///
[1540]2007    /// The inverse map type of DescriptorMap.
[1413]2008    class InverseMap {
2009    public:
2010      /// \brief Constructor of the InverseMap.
2011      ///
2012      /// Constructor of the InverseMap.
[2286]2013      explicit InverseMap(const DescriptorMap& _inverted)
[1413]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 {
[2331]2027        return inverted(key);
[1413]2028      }
[1470]2029
2030      /// \brief Size of the map.
2031      ///
2032      /// Returns the size of the map.
[1931]2033      unsigned int size() const {
[2331]2034        return inverted.size();
[1470]2035      }
[1413]2036     
2037    private:
2038      const DescriptorMap& inverted;
2039    };
2040
[1402]2041    /// \brief Gives back the inverse of the map.
2042    ///
2043    /// Gives back the inverse of the map.
2044    const InverseMap inverse() const {
[1413]2045      return InverseMap(*this);
[1402]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.
[2474]2052  /// \see TargetMap
[1402]2053  /// \author Balazs Dezso
2054  template <typename Graph>
2055  class SourceMap {
2056  public:
[1419]2057
[1402]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.
[2286]2065    explicit SourceMap(const Graph& _graph) : graph(_graph) {}
[1402]2066
2067    /// \brief The subscript operator.
2068    ///
2069    /// The subscript operator.
2070    /// \param edge The edge
2071    /// \return The source of the edge
[1679]2072    Value operator[](const Key& edge) const {
[1402]2073      return graph.source(edge);
2074    }
2075
2076  private:
2077    const Graph& graph;
2078  };
2079
[2474]2080  /// \brief Returns a \ref SourceMap class.
[1402]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.
[2474]2092  /// \see SourceMap
[1402]2093  /// \author Balazs Dezso
2094  template <typename Graph>
2095  class TargetMap {
2096  public:
[1419]2097
[1402]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.
[2286]2105    explicit TargetMap(const Graph& _graph) : graph(_graph) {}
[1402]2106
2107    /// \brief The subscript operator.
2108    ///
2109    /// The subscript operator.
[1536]2110    /// \param e The edge
[1402]2111    /// \return The target of the edge
[1679]2112    Value operator[](const Key& e) const {
[1536]2113      return graph.target(e);
[1402]2114    }
2115
2116  private:
2117    const Graph& graph;
2118  };
2119
[2474]2120  /// \brief Returns a \ref TargetMap class.
[1515]2121  ///
[1540]2122  /// This function just returns a \ref TargetMap class.
[1402]2123  /// \relates TargetMap
2124  template <typename Graph>
2125  inline TargetMap<Graph> targetMap(const Graph& graph) {
2126    return TargetMap<Graph>(graph);
2127  }
2128
[1540]2129  /// \brief Returns the "forward" directed edge view of an undirected edge.
[1419]2130  ///
[1540]2131  /// Returns the "forward" directed edge view of an undirected edge.
[2474]2132  /// \see BackwardMap
[1419]2133  /// \author Balazs Dezso
2134  template <typename Graph>
2135  class ForwardMap {
2136  public:
2137
2138    typedef typename Graph::Edge Value;
[1909]2139    typedef typename Graph::UEdge Key;
[1419]2140
2141    /// \brief Constructor
2142    ///
2143    /// Constructor
2144    /// \param _graph The graph that the map belongs to.
[2286]2145    explicit ForwardMap(const Graph& _graph) : graph(_graph) {}
[1419]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 {
[1627]2153      return graph.direct(key, true);
[1419]2154    }
2155
2156  private:
2157    const Graph& graph;
2158  };
2159
[2474]2160  /// \brief Returns a \ref ForwardMap class.
[1515]2161  ///
[1419]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
[1540]2169  /// \brief Returns the "backward" directed edge view of an undirected edge.
[1419]2170  ///
[1540]2171  /// Returns the "backward" directed edge view of an undirected edge.
[2474]2172  /// \see ForwardMap
[1419]2173  /// \author Balazs Dezso
2174  template <typename Graph>
2175  class BackwardMap {
2176  public:
2177
2178    typedef typename Graph::Edge Value;
[1909]2179    typedef typename Graph::UEdge Key;
[1419]2180
2181    /// \brief Constructor
2182    ///
2183    /// Constructor
2184    /// \param _graph The graph that the map belongs to.
[2286]2185    explicit BackwardMap(const Graph& _graph) : graph(_graph) {}
[1419]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 {
[1627]2193      return graph.direct(key, false);
[1419]2194    }
2195
2196  private:
2197    const Graph& graph;
2198  };
2199
2200  /// \brief Returns a \ref BackwardMap class
2201
[1540]2202  /// This function just returns a \ref BackwardMap class.
[1419]2203  /// \relates BackwardMap
2204  template <typename Graph>
2205  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2206    return BackwardMap<Graph>(graph);
2207  }
2208
[1695]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 {
[1515]2216  public:
[1695]2217    typedef typename Graph::Edge Key;
2218    typedef typename NodeMap::Value Value;
2219
2220    /// \brief Constructor
2221    ///
2222    /// Contructor of the map
[2286]2223    explicit PotentialDifferenceMap(const Graph& _graph,
2224                                    const NodeMap& _potential)
[1695]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
[2474]2239  /// \brief Returns a PotentialDifferenceMap.
[1695]2240  ///
[2474]2241  /// This function just returns a PotentialDifferenceMap.
[1695]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
[1515]2249  /// \brief Map of the node in-degrees.
[1453]2250  ///
[1540]2251  /// This map returns the in-degree of a node. Once it is constructed,
[1515]2252  /// the degrees are stored in a standard NodeMap, so each query is done
[1540]2253  /// in constant time. On the other hand, the values are updated automatically
[1515]2254  /// whenever the graph changes.
2255  ///
[1729]2256  /// \warning Besides addNode() and addEdge(), a graph structure may provide
[1730]2257  /// alternative ways to modify the graph. The correct behavior of InDegMap
[1829]2258  /// is not guarantied if these additional features are used. For example
2259  /// the functions \ref ListGraph::changeSource() "changeSource()",
[1729]2260  /// \ref ListGraph::changeTarget() "changeTarget()" and
2261  /// \ref ListGraph::reverseEdge() "reverseEdge()"
2262  /// of \ref ListGraph will \e not update the degree values correctly.
2263  ///
[1515]2264  /// \sa OutDegMap
2265
[1453]2266  template <typename _Graph>
[1515]2267  class InDegMap 
[1999]2268    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2269      ::ItemNotifier::ObserverBase {
[1515]2270
[1453]2271  public:
[1515]2272   
2273    typedef _Graph Graph;
[1453]2274    typedef int Value;
[1515]2275    typedef typename Graph::Node Key;
2276
[1999]2277    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2278    ::ItemNotifier::ObserverBase Parent;
2279
[1515]2280  private:
2281
[1990]2282    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
[1515]2283    public:
2284
[1990]2285      typedef DefaultMap<_Graph, Key, int> Parent;
[2002]2286      typedef typename Parent::Graph Graph;
[1515]2287
2288      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2289     
[1829]2290      virtual void add(const Key& key) {
[1515]2291        Parent::add(key);
2292        Parent::set(key, 0);
2293      }
[1931]2294
[1829]2295      virtual void add(const std::vector<Key>& keys) {
2296        Parent::add(keys);
[2386]2297        for (int i = 0; i < int(keys.size()); ++i) {
[1829]2298          Parent::set(keys[i], 0);
2299        }
2300      }
[2539]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      }
[1515]2310    };
2311
2312  public:
[1453]2313
2314    /// \brief Constructor.
2315    ///
2316    /// Constructor for creating in-degree map.
[2286]2317    explicit InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
[2384]2318      Parent::attach(graph.notifier(typename _Graph::Edge()));
[1515]2319     
2320      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2321        deg[it] = countInEdges(graph, it);
2322      }
[1453]2323    }
2324   
[1459]2325    /// Gives back the in-degree of a Node.
[1515]2326    int operator[](const Key& key) const {
2327      return deg[key];
[1459]2328    }
[1453]2329
2330  protected:
[1515]2331   
2332    typedef typename Graph::Edge Edge;
2333
2334    virtual void add(const Edge& edge) {
2335      ++deg[graph.target(edge)];
[1453]2336    }
2337
[1931]2338    virtual void add(const std::vector<Edge>& edges) {
[2386]2339      for (int i = 0; i < int(edges.size()); ++i) {
[1931]2340        ++deg[graph.target(edges[i])];
2341      }
2342    }
2343
[1515]2344    virtual void erase(const Edge& edge) {
2345      --deg[graph.target(edge)];
2346    }
2347
[1931]2348    virtual void erase(const std::vector<Edge>& edges) {
[2386]2349      for (int i = 0; i < int(edges.size()); ++i) {
[1931]2350        --deg[graph.target(edges[i])];
2351      }
2352    }
2353
[1515]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:
[1506]2366   
[1515]2367    const _Graph& graph;
2368    AutoNodeMap deg;
[1459]2369  };
2370
[1515]2371  /// \brief Map of the node out-degrees.
2372  ///
[1540]2373  /// This map returns the out-degree of a node. Once it is constructed,
[1515]2374  /// the degrees are stored in a standard NodeMap, so each query is done
[1540]2375  /// in constant time. On the other hand, the values are updated automatically
[1515]2376  /// whenever the graph changes.
2377  ///
[1729]2378  /// \warning Besides addNode() and addEdge(), a graph structure may provide
[1730]2379  /// alternative ways to modify the graph. The correct behavior of OutDegMap
[1829]2380  /// is not guarantied if these additional features are used. For example
2381  /// the functions \ref ListGraph::changeSource() "changeSource()",
[1729]2382  /// \ref ListGraph::changeTarget() "changeTarget()" and
2383  /// \ref ListGraph::reverseEdge() "reverseEdge()"
2384  /// of \ref ListGraph will \e not update the degree values correctly.
2385  ///
[1555]2386  /// \sa InDegMap
[1459]2387
2388  template <typename _Graph>
[1515]2389  class OutDegMap 
[1999]2390    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2391      ::ItemNotifier::ObserverBase {
[1515]2392
[1459]2393  public:
[1999]2394
2395    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2396    ::ItemNotifier::ObserverBase Parent;
[1515]2397   
2398    typedef _Graph Graph;
[1459]2399    typedef int Value;
[1515]2400    typedef typename Graph::Node Key;
2401
2402  private:
2403
[1990]2404    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
[1515]2405    public:
2406
[1990]2407      typedef DefaultMap<_Graph, Key, int> Parent;
[2002]2408      typedef typename Parent::Graph Graph;
[1515]2409
2410      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2411     
[1829]2412      virtual void add(const Key& key) {
[1515]2413        Parent::add(key);
2414        Parent::set(key, 0);
2415      }
[1829]2416      virtual void add(const std::vector<Key>& keys) {
2417        Parent::add(keys);
[2386]2418        for (int i = 0; i < int(keys.size()); ++i) {
[1829]2419          Parent::set(keys[i], 0);
2420        }
2421      }
[2539]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      }
[1515]2430    };
2431
2432  public:
[1459]2433
2434    /// \brief Constructor.
2435    ///
2436    /// Constructor for creating out-degree map.
[2286]2437    explicit OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
[2384]2438      Parent::attach(graph.notifier(typename _Graph::Edge()));
[1515]2439     
2440      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2441        deg[it] = countOutEdges(graph, it);
2442      }
[1459]2443    }
2444
[1990]2445    /// Gives back the out-degree of a Node.
[1515]2446    int operator[](const Key& key) const {
2447      return deg[key];
[1459]2448    }
2449
2450  protected:
[1515]2451   
2452    typedef typename Graph::Edge Edge;
2453
2454    virtual void add(const Edge& edge) {
2455      ++deg[graph.source(edge)];
[1459]2456    }
2457
[1931]2458    virtual void add(const std::vector<Edge>& edges) {
[2386]2459      for (int i = 0; i < int(edges.size()); ++i) {
[1931]2460        ++deg[graph.source(edges[i])];
2461      }
2462    }
2463
[1515]2464    virtual void erase(const Edge& edge) {
2465      --deg[graph.source(edge)];
2466    }
2467
[1931]2468    virtual void erase(const std::vector<Edge>& edges) {
[2386]2469      for (int i = 0; i < int(edges.size()); ++i) {
[1931]2470        --deg[graph.source(edges[i])];
2471      }
2472    }
2473
[1515]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:
[1506]2486   
[1515]2487    const _Graph& graph;
2488    AutoNodeMap deg;
[1453]2489  };
2490
[1695]2491
[2539]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
[2540]2528    class AutoNodeMap : public DefaultMap<G, Node, Edge> {
[2539]2529    public:
2530
[2540]2531      typedef DefaultMap<G, Node, Edge> Parent;
2532
2533      AutoNodeMap(const G& graph) : Parent(graph, INVALID) {}
[2539]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);
[2616]2709          _parent.set(e, _parent[edge]);
2710         
[2539]2711          if (_parent[edge] != INVALID) {
2712            if (_left[_parent[edge]] == edge) {
2713              _left.set(_parent[edge], e);
2714            } else {
2715              _right.set(_parent[edge], e);
2716            }
2717          } else {
2718            _head.set(_g.source(edge), e);
2719          }
2720        }
2721      }
2722    }
2723
2724    Edge refreshRec(std::vector<Edge> &v,int a,int b)
2725    {
2726      int m=(a+b)/2;
2727      Edge me=v[m];
2728      if (a < m) {
2729        Edge left = refreshRec(v,a,m-1);
2730        _left.set(me, left);
2731        _parent.set(left, me);
2732      } else {
2733        _left.set(me, INVALID);
2734      }
2735      if (m < b) {
2736        Edge right = refreshRec(v,m+1,b);
2737        _right.set(me, right);
2738        _parent.set(right, me);
2739      } else {
2740        _right.set(me, INVALID);
2741      }
2742      return me;
2743    }
2744
2745    void refresh() {
2746      for(NodeIt n(_g);n!=INVALID;++n) {
2747        std::vector<Edge> v;
2748        for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2749        if(v.size()) {
2750          std::sort(v.begin(),v.end(),EdgeLess(_g));
2751          Edge head = refreshRec(v,0,v.size()-1);
2752          _head.set(n, head);
2753          _parent.set(head, INVALID);
2754        }
2755        else _head.set(n, INVALID);
2756      }
2757    }
2758
2759    void zig(Edge v) {       
2760      Edge w = _parent[v];
2761      _parent.set(v, _parent[w]);
2762      _parent.set(w, v);
2763      _left.set(w, _right[v]);
2764      _right.set(v, w);
2765      if (_parent[v] != INVALID) {
2766        if (_right[_parent[v]] == w) {
2767          _right.set(_parent[v], v);
2768        } else {
2769          _left.set(_parent[v], v);
2770        }
2771      }
2772      if (_left[w] != INVALID){
2773        _parent.set(_left[w], w);
2774      }
2775    }
2776
2777    void zag(Edge v) {       
2778      Edge w = _parent[v];
2779      _parent.set(v, _parent[w]);
2780      _parent.set(w, v);
2781      _right.set(w, _left[v]);
2782      _left.set(v, w);
2783      if (_parent[v] != INVALID){
2784        if (_left[_parent[v]] == w) {
2785          _left.set(_parent[v], v);
2786        } else {
2787          _right.set(_parent[v], v);
2788        }
2789      }
2790      if (_right[w] != INVALID){
2791        _parent.set(_right[w], w);
2792      }
2793    }
2794
2795    void splay(Edge v) {
2796      while (_parent[v] != INVALID) {
2797        if (v == _left[_parent[v]]) {
2798          if (_parent[_parent[v]] == INVALID) {
2799            zig(v);
2800          } else {
2801            if (_parent[v] == _left[_parent[_parent[v]]]) {
2802              zig(_parent[v]);
2803              zig(v);
2804            } else {
2805              zig(v);
2806              zag(v);
2807            }
2808          }
2809        } else {
2810          if (_parent[_parent[v]] == INVALID) {
2811            zag(v);
2812          } else {
2813            if (_parent[v] == _left[_parent[_parent[v]]]) {
2814              zag(v);
2815              zig(v);
2816            } else {
2817              zag(_parent[v]);
2818              zag(v);
2819            }
2820          }
2821        }
2822      }
2823      _head[_g.source(v)] = v;
2824    }
2825
2826
2827  public:
2828   
2829    ///Find an edge between two nodes.
2830   
2831    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
2832    /// <em>d</em> is the number of outgoing edges of \c s.
2833    ///\param s The source node
2834    ///\param t The target node
2835    ///\return An edge from \c s to \c t if there exists,
2836    ///\ref INVALID otherwise.
2837    Edge operator()(Node s, Node t) const
2838    {
2839      Edge e = _head[s];
[2616]2840      if (e == INVALID) return INVALID;
[2539]2841      while (true) {
2842        if (_g.target(e) == t) {
2843          const_cast<DynEdgeLookUp&>(*this).splay(e);
2844          return e;
2845        } else if (t < _g.target(e)) {
2846          if (_left[e] == INVALID) {
2847            const_cast<DynEdgeLookUp&>(*this).splay(e);
2848            return INVALID;
2849          } else {
2850            e = _left[e];
2851          }
2852        } else  {
2853          if (_right[e] == INVALID) {
2854            const_cast<DynEdgeLookUp&>(*this).splay(e);
2855            return INVALID;
2856          } else {
2857            e = _right[e];
2858          }
2859        }
2860      }
2861    }
2862
2863    ///Find the first edge between two nodes.
2864   
2865    ///Find the first edge between two nodes in time
2866    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2867    /// outgoing edges of \c s. 
2868    ///\param s The source node
2869    ///\param t The target node
2870    ///\return An edge from \c s to \c t if there exists, \ref INVALID
2871    /// otherwise.
2872    Edge findFirst(Node s, Node t) const
2873    {
2874      Edge e = _head[s];
2875      Edge r = INVALID;
2876      while (true) {
2877        if (_g.target(e) < t) {
2878          if (_right[e] == INVALID) {
2879            const_cast<DynEdgeLookUp&>(*this).splay(e);
2880            return r;
2881          } else {
2882            e = _right[e];
2883          }
2884        } else {
2885          if (_g.target(e) == t) {
2886            r = e;
2887          }
2888          if (_left[e] == INVALID) {
2889            const_cast<DynEdgeLookUp&>(*this).splay(e);
2890            return r;
2891          } else {
2892            e = _left[e];
2893          }
2894        }
2895      }
2896    }
2897
2898    ///Find the next edge between two nodes.
2899   
2900    ///Find the next edge between two nodes in time
2901    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2902    /// outgoing edges of \c s. 
2903    ///\param s The source node
2904    ///\param t The target node
2905    ///\return An edge from \c s to \c t if there exists, \ref INVALID
2906    /// otherwise.
2907
2908    ///\note If \c e is not the result of the previous \c findFirst()
2909    ///operation then the amorized time bound can not be guaranteed.
2910#ifdef DOXYGEN
2911    Edge findNext(Node s, Node t, Edge e) const
2912#else
2913    Edge findNext(Node, Node t, Edge e) const
2914#endif
2915    {
2916      if (_right[e] != INVALID) {
2917        e = _right[e];
2918        while (_left[e] != INVALID) {
2919          e = _left[e];
2920        }
2921        const_cast<DynEdgeLookUp&>(*this).splay(e);
2922      } else {
2923        while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
2924          e = _parent[e];
2925        }
2926        if (_parent[e] == INVALID) {
2927          return INVALID;
2928        } else {
2929          e = _parent[e];
2930          const_cast<DynEdgeLookUp&>(*this).splay(e);
2931        }
2932      }
2933      if (_g.target(e) == t) return e;
2934      else return INVALID;   
2935    }
2936
2937  };
2938
[2235]2939  ///Fast edge look up between given endpoints.
2940 
2941  ///\ingroup gutils
2942  ///Using this class, you can find an edge in a graph from a given
2943  ///source to a given target in time <em>O(log d)</em>,
2944  ///where <em>d</em> is the out-degree of the source node.
2945  ///
2946  ///It is not possible to find \e all parallel edges between two nodes.
2947  ///Use \ref AllEdgeLookUp for this purpose.
2948  ///
2949  ///\warning This class is static, so you should refresh() (or at least
2950  ///refresh(Node)) this data structure
2951  ///whenever the graph changes. This is a time consuming (superlinearly
2952  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2953  ///
2954  ///\param G The type of the underlying graph.
2955  ///
[2539]2956  ///\sa DynEdgeLookUp
[2235]2957  ///\sa AllEdgeLookUp 
2958  template<class G>
2959  class EdgeLookUp
2960  {
2961  public:
[2510]2962    GRAPH_TYPEDEFS(typename G);
[2235]2963    typedef G Graph;
2964
2965  protected:
2966    const Graph &_g;
2967    typename Graph::template NodeMap<Edge> _head;
2968    typename Graph::template EdgeMap<Edge> _left;
2969    typename Graph::template EdgeMap<Edge> _right;
2970   
2971    class EdgeLess {
2972      const Graph &g;
2973    public:
2974      EdgeLess(const Graph &_g) : g(_g) {}
2975      bool operator()(Edge a,Edge b) const
2976      {
2977        return g.target(a)<g.target(b);
2978      }
2979    };
2980   
2981  public:
2982   
2983    ///Constructor
2984
2985    ///Constructor.
2986    ///
2987    ///It builds up the search database, which remains valid until the graph
2988    ///changes.
2989    EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2990   
2991  private:
[2539]2992    Edge refreshRec(std::vector<Edge> &v,int a,int b)
[2235]2993    {
2994      int m=(a+b)/2;
2995      Edge me=v[m];
[2539]2996      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2997      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
[2235]2998      return me;
2999    }
3000  public:
3001    ///Refresh the data structure at a node.
3002
3003    ///Build up the search database of node \c n.
3004    ///
3005    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
3006    ///the number of the outgoing edges of \c n.
3007    void refresh(Node n)
3008    {
3009      std::vector<Edge> v;
3010      for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
3011      if(v.size()) {
3012        std::sort(v.begin(),v.end(),EdgeLess(_g));
[2539]3013        _head[n]=refreshRec(v,0,v.size()-1);
[2235]3014      }
3015      else _head[n]=INVALID;
3016    }
3017    ///Refresh the full data structure.
3018
3019    ///Build up the full search database. In fact, it simply calls
3020    ///\ref refresh(Node) "refresh(n)" for each node \c n.
3021    ///
3022    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
3023    ///the number of the edges of \c n and <em>D</em> is the maximum
3024    ///out-degree of the graph.
3025
3026    void refresh()
3027    {
3028      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
3029    }
3030   
3031    ///Find an edge between two nodes.
3032   
3033    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
3034    /// <em>d</em> is the number of outgoing edges of \c s.
3035    ///\param s The source node
3036    ///\param t The target node
3037    ///\return An edge from \c s to \c t if there exists,
3038    ///\ref INVALID otherwise.
3039    ///
3040    ///\warning If you change the graph, refresh() must be called before using
3041    ///this operator. If you change the outgoing edges of
3042    ///a single node \c n, then
3043    ///\ref refresh(Node) "refresh(n)" is enough.
3044    ///
3045    Edge operator()(Node s, Node t) const
3046    {
3047      Edge e;
3048      for(e=_head[s];
3049          e!=INVALID&&_g.target(e)!=t;
3050          e = t < _g.target(e)?_left[e]:_right[e]) ;
3051      return e;
3052    }
3053
3054  };
3055
3056  ///Fast look up of all edges between given endpoints.
3057 
3058  ///\ingroup gutils
3059  ///This class is the same as \ref EdgeLookUp, with the addition
3060  ///that it makes it possible to find all edges between given endpoints.
3061  ///
3062  ///\warning This class is static, so you should refresh() (or at least
3063  ///refresh(Node)) this data structure
3064  ///whenever the graph changes. This is a time consuming (superlinearly
3065  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
3066  ///
3067  ///\param G The type of the underlying graph.
3068  ///
[2539]3069  ///\sa DynEdgeLookUp
[2235]3070  ///\sa EdgeLookUp 
3071  template<class G>
3072  class AllEdgeLookUp : public EdgeLookUp<G>
3073  {
3074    using EdgeLookUp<G>::_g;
3075    using EdgeLookUp<G>::_right;
3076    using EdgeLookUp<G>::_left;
3077    using EdgeLookUp<G>::_head;
3078
[2510]3079    GRAPH_TYPEDEFS(typename G);
[2235]3080    typedef G Graph;
3081   
3082    typename Graph::template EdgeMap<Edge> _next;
3083   
3084    Edge refreshNext(Edge head,Edge next=INVALID)
3085    {
3086      if(head==INVALID) return next;
3087      else {
3088        next=refreshNext(_right[head],next);
3089//      _next[head]=next;
3090        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
3091          ? next : INVALID;
3092        return refreshNext(_left[head],head);
3093      }
3094    }
3095   
3096    void refreshNext()
3097    {
3098      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
3099    }
3100   
3101  public:
3102    ///Constructor
3103
3104    ///Constructor.
3105    ///
3106    ///It builds up the search database, which remains valid until the graph
3107    ///changes.
3108    AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
3109
3110    ///Refresh the data structure at a node.
3111
3112    ///Build up the search database of node \c n.
3113    ///
3114    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
3115    ///the number of the outgoing edges of \c n.
3116   
3117    void refresh(Node n)
3118    {
3119      EdgeLookUp<G>::refresh(n);
3120      refreshNext(_head[n]);
3121    }
3122   
3123    ///Refresh the full data structure.
3124
3125    ///Build up the full search database. In fact, it simply calls
3126    ///\ref refresh(Node) "refresh(n)" for each node \c n.
3127    ///
3128    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
3129    ///the number of the edges of \c n and <em>D</em> is the maximum
3130    ///out-degree of the graph.
3131
3132    void refresh()
3133    {
3134      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
3135    }
3136   
3137    ///Find an edge between two nodes.
3138   
3139    ///Find an edge between two nodes.
3140    ///\param s The source node
3141    ///\param t The target node
3142    ///\param prev The previous edge between \c s and \c t. It it is INVALID or
3143    ///not given, the operator finds the first appropriate edge.
[2350]3144    ///\return An edge from \c s to \c t after \c prev or
[2235]3145    ///\ref INVALID if there is no more.
3146    ///
3147    ///For example, you can count the number of edges from \c u to \c v in the
3148    ///following way.
3149    ///\code
3150    ///AllEdgeLookUp<ListGraph> ae(g);
3151    ///...
3152    ///int n=0;
3153    ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
3154    ///\endcode
3155    ///
3156    ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
3157    /// <em>d</em> is the number of outgoing edges of \c s. Then, the
3158    ///consecutive edges are found in constant time.
3159    ///
3160    ///\warning If you change the graph, refresh() must be called before using
3161    ///this operator. If you change the outgoing edges of
3162    ///a single node \c n, then
3163    ///\ref refresh(Node) "refresh(n)" is enough.
3164    ///
3165#ifdef DOXYGEN
3166    Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
3167#else
3168    using EdgeLookUp<G>::operator() ;
3169    Edge operator()(Node s, Node t, Edge prev) const
3170    {
3171      return prev==INVALID?(*this)(s,t):_next[prev];
3172    }
3173#endif
3174     
3175  };
3176
[1402]3177  /// @}
3178
[947]3179} //END OF NAMESPACE LEMON
[946]3180
3181#endif
Note: See TracBrowser for help on using the repository browser.