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