COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/graph_utils.h @ 118:407c08a0eae9

Last change on this file since 118:407c08a0eae9 was 100:4f754b4cf82b, checked in by Alpar Juttner <alpar@…>, 12 years ago

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

File size: 93.0 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 <cmath>
26#include <algorithm>
27
28#include <lemon/bits/invalid.h>
29#include <lemon/bits/utility.h>
30#include <lemon/maps.h>
31#include <lemon/bits/traits.h>
32
33#include <lemon/bits/alteration_notifier.h>
34#include <lemon/bits/default_map.h>
35
36///\ingroup gutils
37///\file
38///\brief Digraph utilities.
39
40namespace lemon {
41
42  /// \addtogroup gutils
43  /// @{
44
45  ///Creates convenience typedefs for the digraph types and iterators
46
47  ///This \c \#define creates convenience typedefs for the following types
48  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
49  ///\c OutArcIt
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 digraph maps because of the lack of
56  ///template typedefs in C++.
57#define GRAPH_TYPEDEFS(Digraph)                         \
58  typedef Digraph::     Node      Node;                 \
59    typedef Digraph::   NodeIt    NodeIt;                       \
60    typedef Digraph::   Arc      Arc;                   \
61    typedef Digraph::   ArcIt    ArcIt;                 \
62    typedef Digraph:: InArcIt  InArcIt;                 \
63    typedef Digraph::OutArcIt OutArcIt
64
65  ///Creates convenience typedefs for the graph types and iterators
66
67  ///This \c \#define creates the same convenience typedefs as defined by
68  ///\ref GRAPH_TYPEDEFS(Digraph) and three more, namely it creates
69  ///\c Edge, \c EdgeIt, \c IncArcIt,
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 digraph maps because of the lack of
77  ///template typedefs in C++.
78#define UGRAPH_TYPEDEFS(Digraph)                                \
79  GRAPH_TYPEDEFS(Digraph);                              \
80    typedef Digraph:: Edge   Edge;                      \
81    typedef Digraph:: EdgeIt EdgeIt;                    \
82    typedef Digraph:: IncArcIt   IncArcIt
83
84  ///\brief Creates convenience typedefs for the bipartite digraph
85  ///types and iterators
86
87  ///This \c \#define creates the same convenience typedefs as defined by
88  ///\ref UGRAPH_TYPEDEFS(Digraph) and two more, namely it creates
89  ///\c RedIt, \c BlueIt,
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 digraph maps because of the lack of
97  ///template typedefs in C++.
98#define BPUGRAPH_TYPEDEFS(Digraph)            \
99  UGRAPH_TYPEDEFS(Digraph);                 \
100    typedef Digraph::Red Red;             \
101    typedef Digraph::Blue Blue;             \
102    typedef Digraph::RedIt RedIt;           \
103    typedef Digraph::BlueIt BlueIt
104
105  /// \brief Function to count the items in the digraph.
106  ///
107  /// This function counts the items (nodes, arcs etc) in the digraph.
108  /// The complexity of the function is O(n) because
109  /// it iterates on all of the items.
110
111  template <typename Digraph, typename Item>
112  inline int countItems(const Digraph& g) {
113    typedef typename ItemSetTraits<Digraph, 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 _digraph_utils_bits {
124   
125    template <typename Digraph, typename Enable = void>
126    struct CountNodesSelector {
127      static int count(const Digraph &g) {
128        return countItems<Digraph, typename Digraph::Node>(g);
129      }
130    };
131
132    template <typename Digraph>
133    struct CountNodesSelector<
134      Digraph, typename
135      enable_if<typename Digraph::NodeNumTag, void>::type>
136    {
137      static int count(const Digraph &g) {
138        return g.nodeNum();
139      }
140    };   
141  }
142
143  /// \brief Function to count the nodes in the digraph.
144  ///
145  /// This function counts the nodes in the digraph.
146  /// The complexity of the function is O(n) but for some
147  /// digraph structures it is specialized to run in O(1).
148  ///
149  /// If the digraph 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 Digraph>
153  inline int countNodes(const Digraph& g) {
154    return _digraph_utils_bits::CountNodesSelector<Digraph>::count(g);
155  }
156
157  namespace _digraph_utils_bits {
158   
159    template <typename Digraph, typename Enable = void>
160    struct CountRedsSelector {
161      static int count(const Digraph &g) {
162        return countItems<Digraph, typename Digraph::Red>(g);
163      }
164    };
165
166    template <typename Digraph>
167    struct CountRedsSelector<
168      Digraph, typename
169      enable_if<typename Digraph::NodeNumTag, void>::type>
170    {
171      static int count(const Digraph &g) {
172        return g.redNum();
173      }
174    };   
175  }
176
177  /// \brief Function to count the reds in the digraph.
178  ///
179  /// This function counts the reds in the digraph.
180  /// The complexity of the function is O(an) but for some
181  /// digraph structures it is specialized to run in O(1).
182  ///
183  /// If the digraph contains an \e redNum() 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 Digraph>
187  inline int countReds(const Digraph& g) {
188    return _digraph_utils_bits::CountRedsSelector<Digraph>::count(g);
189  }
190
191  namespace _digraph_utils_bits {
192   
193    template <typename Digraph, typename Enable = void>
194    struct CountBluesSelector {
195      static int count(const Digraph &g) {
196        return countItems<Digraph, typename Digraph::Blue>(g);
197      }
198    };
199
200    template <typename Digraph>
201    struct CountBluesSelector<
202      Digraph, typename
203      enable_if<typename Digraph::NodeNumTag, void>::type>
204    {
205      static int count(const Digraph &g) {
206        return g.blueNum();
207      }
208    };   
209  }
210
211  /// \brief Function to count the blues in the digraph.
212  ///
213  /// This function counts the blues in the digraph.
214  /// The complexity of the function is O(bn) but for some
215  /// digraph structures it is specialized to run in O(1).
216  ///
217  /// If the digraph contains a \e blueNum() 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 Digraph>
221  inline int countBlues(const Digraph& g) {
222    return _digraph_utils_bits::CountBluesSelector<Digraph>::count(g);
223  }
224
225
226  // Arc counting:
227
228  namespace _digraph_utils_bits {
229   
230    template <typename Digraph, typename Enable = void>
231    struct CountArcsSelector {
232      static int count(const Digraph &g) {
233        return countItems<Digraph, typename Digraph::Arc>(g);
234      }
235    };
236
237    template <typename Digraph>
238    struct CountArcsSelector<
239      Digraph,
240      typename enable_if<typename Digraph::ArcNumTag, void>::type>
241    {
242      static int count(const Digraph &g) {
243        return g.arcNum();
244      }
245    };   
246  }
247
248  /// \brief Function to count the arcs in the digraph.
249  ///
250  /// This function counts the arcs in the digraph.
251  /// The complexity of the function is O(e) but for some
252  /// digraph structures it is specialized to run in O(1).
253  ///
254  /// If the digraph contains a \e arcNum() member function and a
255  /// \e ArcNumTag tag then this function calls directly the member
256  /// function to query the cardinality of the arc set.
257  template <typename Digraph>
258  inline int countArcs(const Digraph& g) {
259    return _digraph_utils_bits::CountArcsSelector<Digraph>::count(g);
260  }
261
262  // Undirected arc counting:
263  namespace _digraph_utils_bits {
264   
265    template <typename Digraph, typename Enable = void>
266    struct CountEdgesSelector {
267      static int count(const Digraph &g) {
268        return countItems<Digraph, typename Digraph::Edge>(g);
269      }
270    };
271
272    template <typename Digraph>
273    struct CountEdgesSelector<
274      Digraph,
275      typename enable_if<typename Digraph::ArcNumTag, void>::type>
276    {
277      static int count(const Digraph &g) {
278        return g.edgeNum();
279      }
280    };   
281  }
282
283  /// \brief Function to count the edges in the digraph.
284  ///
285  /// This function counts the edges in the digraph.
286  /// The complexity of the function is O(e) but for some
287  /// digraph structures it is specialized to run in O(1).
288  ///
289  /// If the digraph contains a \e edgeNum() member function and a
290  /// \e ArcNumTag tag then this function calls directly the member
291  /// function to query the cardinality of the edge set.
292  template <typename Digraph>
293  inline int countEdges(const Digraph& g) {
294    return _digraph_utils_bits::CountEdgesSelector<Digraph>::count(g);
295
296  }
297
298
299  template <typename Digraph, typename DegIt>
300  inline int countNodeDegree(const Digraph& _g, const typename Digraph::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-arcs from node \c n.
309  ///
310  /// This function counts the number of the out-arcs from node \c n
311  /// in the digraph. 
312  template <typename Digraph>
313  inline int countOutArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
314    return countNodeDegree<Digraph, typename Digraph::OutArcIt>(_g, _n);
315  }
316
317  /// \brief Function to count the number of the in-arcs to node \c n.
318  ///
319  /// This function counts the number of the in-arcs to node \c n
320  /// in the digraph. 
321  template <typename Digraph>
322  inline int countInArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
323    return countNodeDegree<Digraph, typename Digraph::InArcIt>(_g, _n);
324  }
325
326  /// \brief Function to count the number of the inc-arcs to node \c n.
327  ///
328  /// This function counts the number of the inc-arcs to node \c n
329  /// in the digraph. 
330  template <typename Digraph>
331  inline int countIncArcs(const Digraph& _g,  const typename Digraph::Node& _n) {
332    return countNodeDegree<Digraph, typename Digraph::IncArcIt>(_g, _n);
333  }
334
335  namespace _digraph_utils_bits {
336   
337    template <typename Digraph, typename Enable = void>
338    struct FindArcSelector {
339      typedef typename Digraph::Node Node;
340      typedef typename Digraph::Arc Arc;
341      static Arc find(const Digraph &g, Node u, Node v, Arc 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 Digraph>
355    struct FindArcSelector<
356      Digraph,
357      typename enable_if<typename Digraph::FindArcTag, void>::type>
358    {
359      typedef typename Digraph::Node Node;
360      typedef typename Digraph::Arc Arc;
361      static Arc find(const Digraph &g, Node u, Node v, Arc prev) {
362        return g.findArc(u, v, prev);
363      }
364    };   
365  }
366
367  /// \brief Finds an arc between two nodes of a digraph.
368  ///
369  /// Finds an arc from node \c u to node \c v in digraph \c g.
370  ///
371  /// If \c prev is \ref INVALID (this is the default value), then
372  /// it finds the first arc from \c u to \c v. Otherwise it looks for
373  /// the next arc from \c u to \c v after \c prev.
374  /// \return The found arc or \ref INVALID if there is no such an arc.
375  ///
376  /// Thus you can iterate through each arc from \c u to \c v as it follows.
377  ///\code
378  /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
379  ///   ...
380  /// }
381  ///\endcode
382  ///
383  ///\sa ArcLookUp
384  ///\sa AllArcLookUp
385  ///\sa DynArcLookUp
386  ///\sa ConArcIt
387  template <typename Digraph>
388  inline typename Digraph::Arc
389  findArc(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
390           typename Digraph::Arc prev = INVALID) {
391    return _digraph_utils_bits::FindArcSelector<Digraph>::find(g, u, v, prev);
392  }
393
394  /// \brief Iterator for iterating on arcs connected the same nodes.
395  ///
396  /// Iterator for iterating on arcs connected the same nodes. It is
397  /// higher level interface for the findArc() function. You can
398  /// use it the following way:
399  ///\code
400  /// for (ConArcIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
401  ///   ...
402  /// }
403  ///\endcode
404  ///
405  ///\sa findArc()
406  ///\sa ArcLookUp
407  ///\sa AllArcLookUp
408  ///\sa DynArcLookUp
409  ///
410  /// \author Balazs Dezso
411  template <typename _Digraph>
412  class ConArcIt : public _Digraph::Arc {
413  public:
414
415    typedef _Digraph Digraph;
416    typedef typename Digraph::Arc Parent;
417
418    typedef typename Digraph::Arc Arc;
419    typedef typename Digraph::Node Node;
420
421    /// \brief Constructor.
422    ///
423    /// Construct a new ConArcIt iterating on the arcs which
424    /// connects the \c u and \c v node.
425    ConArcIt(const Digraph& g, Node u, Node v) : digraph(g) {
426      Parent::operator=(findArc(digraph, u, v));
427    }
428
429    /// \brief Constructor.
430    ///
431    /// Construct a new ConArcIt which continues the iterating from
432    /// the \c e arc.
433    ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}
434   
435    /// \brief Increment operator.
436    ///
437    /// It increments the iterator and gives back the next arc.
438    ConArcIt& operator++() {
439      Parent::operator=(findArc(digraph, digraph.source(*this),
440                                 digraph.target(*this), *this));
441      return *this;
442    }
443  private:
444    const Digraph& digraph;
445  };
446
447  namespace _digraph_utils_bits {
448   
449    template <typename Digraph, typename Enable = void>
450    struct FindEdgeSelector {
451      typedef typename Digraph::Node Node;
452      typedef typename Digraph::Edge Edge;
453      static Edge find(const Digraph &g, Node u, Node v, Edge 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 Digraph>
481    struct FindEdgeSelector<
482      Digraph,
483      typename enable_if<typename Digraph::FindArcTag, void>::type>
484    {
485      typedef typename Digraph::Node Node;
486      typedef typename Digraph::Edge Edge;
487      static Edge find(const Digraph &g, Node u, Node v, Edge prev) {
488        return g.findEdge(u, v, prev);
489      }
490    };   
491  }
492
493  /// \brief Finds an edge between two nodes of a digraph.
494  ///
495  /// Finds an edge from node \c u to node \c v in digraph \c g.
496  /// If the node \c u and node \c v is equal then each loop arc
497  /// will be enumerated.
498  ///
499  /// If \c prev is \ref INVALID (this is the default value), then
500  /// it finds the first arc from \c u to \c v. Otherwise it looks for
501  /// the next arc from \c u to \c v after \c prev.
502  /// \return The found arc or \ref INVALID if there is no such an arc.
503  ///
504  /// Thus you can iterate through each arc from \c u to \c v as it follows.
505  ///\code
506  /// for(Edge e = findEdge(g,u,v); e != INVALID;
507  ///     e = findEdge(g,u,v,e)) {
508  ///   ...
509  /// }
510  ///\endcode
511  ///
512  ///\sa ConArcIt
513
514  template <typename Digraph>
515  inline typename Digraph::Edge
516  findEdge(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
517            typename Digraph::Edge p = INVALID) {
518    return _digraph_utils_bits::FindEdgeSelector<Digraph>::find(g, u, v, p);
519  }
520
521  /// \brief Iterator for iterating on edges connected the same nodes.
522  ///
523  /// Iterator for iterating on edges connected the same nodes. It is
524  /// higher level interface for the findEdge() function. You can
525  /// use it the following way:
526  ///\code
527  /// for (ConEdgeIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
528  ///   ...
529  /// }
530  ///\endcode
531  ///
532  ///\sa findEdge()
533  ///
534  /// \author Balazs Dezso
535  template <typename _Digraph>
536  class ConEdgeIt : public _Digraph::Edge {
537  public:
538
539    typedef _Digraph Digraph;
540    typedef typename Digraph::Edge Parent;
541
542    typedef typename Digraph::Edge Edge;
543    typedef typename Digraph::Node Node;
544
545    /// \brief Constructor.
546    ///
547    /// Construct a new ConEdgeIt iterating on the arcs which
548    /// connects the \c u and \c v node.
549    ConEdgeIt(const Digraph& g, Node u, Node v) : digraph(g) {
550      Parent::operator=(findEdge(digraph, u, v));
551    }
552
553    /// \brief Constructor.
554    ///
555    /// Construct a new ConEdgeIt which continues the iterating from
556    /// the \c e arc.
557    ConEdgeIt(const Digraph& g, Edge e) : Parent(e), digraph(g) {}
558   
559    /// \brief Increment operator.
560    ///
561    /// It increments the iterator and gives back the next arc.
562    ConEdgeIt& operator++() {
563      Parent::operator=(findEdge(digraph, digraph.source(*this),
564                                      digraph.target(*this), *this));
565      return *this;
566    }
567  private:
568    const Digraph& digraph;
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 _digraph_utils_bits {
597
598    template <typename Digraph, typename Item, typename RefMap>
599    class MapCopyBase {
600    public:
601      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
602     
603      virtual ~MapCopyBase() {}
604    };
605
606    template <typename Digraph, typename Item, typename RefMap,
607              typename ToMap, typename FromMap>
608    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
609    public:
610
611      MapCopy(ToMap& tmap, const FromMap& map)
612        : _tmap(tmap), _map(map) {}
613     
614      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
615        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
616        for (ItemIt it(digraph); 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 Digraph, typename Item, typename RefMap, typename It>
627    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
628    public:
629
630      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
631     
632      virtual void copy(const Digraph&, const RefMap& refMap) {
633        _it = refMap[_item];
634      }
635
636    private:
637      It& _it;
638      Item _item;
639    };
640
641    template <typename Digraph, typename Item, typename RefMap, typename Ref>
642    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
643    public:
644
645      RefCopy(Ref& map) : _map(map) {}
646     
647      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
648        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
649        for (ItemIt it(digraph); it != INVALID; ++it) {
650          _map.set(it, refMap[it]);
651        }
652      }
653
654    private:
655      Ref& _map;
656    };
657
658    template <typename Digraph, typename Item, typename RefMap,
659              typename CrossRef>
660    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
661    public:
662
663      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
664     
665      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
666        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
667        for (ItemIt it(digraph); it != INVALID; ++it) {
668          _cmap.set(refMap[it], it);
669        }
670      }
671
672    private:
673      CrossRef& _cmap;
674    };
675
676    template <typename Digraph, typename Enable = void>
677    struct DigraphCopySelector {
678      template <typename From, typename NodeRefMap, typename ArcRefMap>
679      static void copy(Digraph &to, const From& from,
680                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
681        for (typename From::NodeIt it(from); it != INVALID; ++it) {
682          nodeRefMap[it] = to.addNode();
683        }
684        for (typename From::ArcIt it(from); it != INVALID; ++it) {
685          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
686                                          nodeRefMap[from.target(it)]);
687        }
688      }
689    };
690
691    template <typename Digraph>
692    struct DigraphCopySelector<
693      Digraph,
694      typename enable_if<typename Digraph::BuildTag, void>::type>
695    {
696      template <typename From, typename NodeRefMap, typename ArcRefMap>
697      static void copy(Digraph &to, const From& from,
698                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
699        to.build(from, nodeRefMap, arcRefMap);
700      }
701    };
702
703    template <typename Graph, typename Enable = void>
704    struct GraphCopySelector {
705      template <typename From, typename NodeRefMap, typename EdgeRefMap>
706      static void copy(Graph &to, const From& from,
707                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
708        for (typename From::NodeIt it(from); it != INVALID; ++it) {
709          nodeRefMap[it] = to.addNode();
710        }
711        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
712          edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
713                                       nodeRefMap[from.target(it)]);
714        }
715      }
716    };
717
718    template <typename Graph>
719    struct GraphCopySelector<
720      Graph,
721      typename enable_if<typename Graph::BuildTag, void>::type>
722    {
723      template <typename From, typename NodeRefMap, typename EdgeRefMap>
724      static void copy(Graph &to, const From& from,
725                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
726        to.build(from, nodeRefMap, edgeRefMap);
727      }
728    };
729
730    template <typename BpGraph, typename Enable = void>
731    struct BpGraphCopySelector {
732      template <typename From, typename RedRefMap,
733                typename BlueRefMap, typename EdgeRefMap>
734      static void copy(BpGraph &to, const From& from,
735                       RedRefMap& redRefMap, BlueRefMap& blueRefMap,
736                       EdgeRefMap& edgeRefMap) {
737        for (typename From::RedIt it(from); it != INVALID; ++it) {
738          redRefMap[it] = to.addRed();
739        }
740        for (typename From::BlueIt it(from); it != INVALID; ++it) {
741          blueRefMap[it] = to.addBlue();
742        }
743        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
744          edgeRefMap[it] = to.addArc(redRefMap[from.red(it)],
745                                           blueRefMap[from.blue(it)]);
746        }
747      }
748    };
749
750    template <typename BpGraph>
751    struct BpGraphCopySelector<
752      BpGraph,
753      typename enable_if<typename BpGraph::BuildTag, void>::type>
754    {
755      template <typename From, typename RedRefMap,
756                typename BlueRefMap, typename EdgeRefMap>
757      static void copy(BpGraph &to, const From& from,
758                       RedRefMap& redRefMap, BlueRefMap& blueRefMap,
759                       EdgeRefMap& edgeRefMap) {
760        to.build(from, redRefMap, blueRefMap, edgeRefMap);
761      }
762    };
763   
764
765  }
766
767  /// \brief Class to copy a digraph.
768  ///
769  /// Class to copy a digraph to another digraph (duplicate a digraph). The
770  /// simplest way of using it is through the \c copyDigraph() function.
771  template <typename To, typename From>
772  class DigraphCopy {
773  private:
774
775    typedef typename From::Node Node;
776    typedef typename From::NodeIt NodeIt;
777    typedef typename From::Arc Arc;
778    typedef typename From::ArcIt ArcIt;
779
780    typedef typename To::Node TNode;
781    typedef typename To::Arc TArc;
782
783    typedef typename From::template NodeMap<TNode> NodeRefMap;
784    typedef typename From::template ArcMap<TArc> ArcRefMap;
785   
786   
787  public:
788
789
790    /// \brief Constructor for the DigraphCopy.
791    ///
792    /// It copies the content of the \c _from digraph into the
793    /// \c _to digraph.
794    DigraphCopy(To& _to, const From& _from)
795      : from(_from), to(_to) {}
796
797    /// \brief Destructor of the DigraphCopy
798    ///
799    /// Destructor of the DigraphCopy
800    ~DigraphCopy() {
801      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
802        delete nodeMapCopies[i];
803      }
804      for (int i = 0; i < int(arcMapCopies.size()); ++i) {
805        delete arcMapCopies[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    DigraphCopy& nodeRef(NodeRef& map) {
815      nodeMapCopies.push_back(new _digraph_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    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
826      nodeMapCopies.push_back(new _digraph_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 digraph.
834    /// The new map's key type is the to digraph's node type,
835    /// and the copied map's key type is the from digraph's node
836    /// type. 
837    template <typename ToMap, typename FromMap>
838    DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
839      nodeMapCopies.push_back(new _digraph_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    DigraphCopy& node(TNode& tnode, const Node& snode) {
848      nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
849                              NodeRefMap, TNode>(tnode, snode));
850      return *this;
851    }
852
853    /// \brief Copies the arc references into the given map.
854    ///
855    /// Copies the arc references into the given map.
856    template <typename ArcRef>
857    DigraphCopy& arcRef(ArcRef& map) {
858      arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
859                              ArcRefMap, ArcRef>(map));
860      return *this;
861    }
862
863    /// \brief Copies the arc cross references into the given map.
864    ///
865    ///  Copies the arc cross references (reverse references) into
866    ///  the given map.
867    template <typename ArcCrossRef>
868    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
869      arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
870                              ArcRefMap, ArcCrossRef>(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 digraph.
877    /// The new map's key type is the to digraph's arc type,
878    /// and the copied map's key type is the from digraph's arc
879    /// type. 
880    template <typename ToMap, typename FromMap>
881    DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
882      arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
883                              ArcRefMap, ToMap, FromMap>(tmap, map));
884      return *this;
885    }
886
887    /// \brief Make a copy of the given arc.
888    ///
889    /// Make a copy of the given arc.
890    DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
891      arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
892                              ArcRefMap, TArc>(tarc, sarc));
893      return *this;
894    }
895
896    /// \brief Executes the copies.
897    ///
898    /// Executes the copies.
899    void run() {
900      NodeRefMap nodeRefMap(from);
901      ArcRefMap arcRefMap(from);
902      _digraph_utils_bits::DigraphCopySelector<To>::
903        copy(to, from, nodeRefMap, arcRefMap);
904      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
905        nodeMapCopies[i]->copy(from, nodeRefMap);
906      }
907      for (int i = 0; i < int(arcMapCopies.size()); ++i) {
908        arcMapCopies[i]->copy(from, arcRefMap);
909      }     
910    }
911
912  protected:
913
914
915    const From& from;
916    To& to;
917
918    std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
919    nodeMapCopies;
920
921    std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
922    arcMapCopies;
923
924  };
925
926  /// \brief Copy a digraph to another digraph.
927  ///
928  /// Copy a digraph to another digraph.
929  /// The usage of the function:
930  ///
931  ///\code
932  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(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 digraph to the nodes of the \c to digraph and
937  /// \c ecr will contain the mapping from the arcs of the \c to digraph
938  /// to the arcs of the \c from digraph.
939  ///
940  /// \see DigraphCopy
941  template <typename To, typename From>
942  DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
943    return DigraphCopy<To, From>(to, from);
944  }
945
946  /// \brief Class to copy an graph.
947  ///
948  /// Class to copy an graph to another digraph (duplicate a digraph).
949  /// The simplest way of using it is through the \c copyGraph() function.
950  template <typename To, typename From>
951  class GraphCopy {
952  private:
953
954    typedef typename From::Node Node;
955    typedef typename From::NodeIt NodeIt;
956    typedef typename From::Arc Arc;
957    typedef typename From::ArcIt ArcIt;
958    typedef typename From::Edge Edge;
959    typedef typename From::EdgeIt EdgeIt;
960
961    typedef typename To::Node TNode;
962    typedef typename To::Arc TArc;
963    typedef typename To::Edge TEdge;
964
965    typedef typename From::template NodeMap<TNode> NodeRefMap;
966    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
967
968    struct ArcRefMap {
969      ArcRefMap(const To& _to, const From& _from,
970                 const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
971        : to(_to), from(_from),
972          edge_ref(_edge_ref), node_ref(_node_ref) {}
973
974      typedef typename From::Arc Key;
975      typedef typename To::Arc Value;
976
977      Value operator[](const Key& key) const {
978        bool forward =
979          (from.direction(key) ==
980           (node_ref[from.source(static_cast<const Edge&>(key))] ==
981            to.source(edge_ref[static_cast<const Edge&>(key)])));
982        return to.direct(edge_ref[key], forward);
983      }
984     
985      const To& to;
986      const From& from;
987      const EdgeRefMap& edge_ref;
988      const NodeRefMap& node_ref;
989    };
990
991   
992  public:
993
994
995    /// \brief Constructor for the DigraphCopy.
996    ///
997    /// It copies the content of the \c _from digraph into the
998    /// \c _to digraph.
999    GraphCopy(To& _to, const From& _from)
1000      : from(_from), to(_to) {}
1001
1002    /// \brief Destructor of the DigraphCopy
1003    ///
1004    /// Destructor of the DigraphCopy
1005    ~GraphCopy() {
1006      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1007        delete nodeMapCopies[i];
1008      }
1009      for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1010        delete arcMapCopies[i];
1011      }
1012      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1013        delete edgeMapCopies[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    GraphCopy& nodeRef(NodeRef& map) {
1023      nodeMapCopies.push_back(new _digraph_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    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1034      nodeMapCopies.push_back(new _digraph_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 digraph.
1042    /// The new map's key type is the to digraph's node type,
1043    /// and the copied map's key type is the from digraph's node
1044    /// type. 
1045    template <typename ToMap, typename FromMap>
1046    GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1047      nodeMapCopies.push_back(new _digraph_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    GraphCopy& node(TNode& tnode, const Node& snode) {
1056      nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
1057                              NodeRefMap, TNode>(tnode, snode));
1058      return *this;
1059    }
1060
1061    /// \brief Copies the arc references into the given map.
1062    ///
1063    /// Copies the arc references into the given map.
1064    template <typename ArcRef>
1065    GraphCopy& arcRef(ArcRef& map) {
1066      arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
1067                              ArcRefMap, ArcRef>(map));
1068      return *this;
1069    }
1070
1071    /// \brief Copies the arc cross references into the given map.
1072    ///
1073    ///  Copies the arc cross references (reverse references) into
1074    ///  the given map.
1075    template <typename ArcCrossRef>
1076    GraphCopy& arcCrossRef(ArcCrossRef& map) {
1077      arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
1078                              ArcRefMap, ArcCrossRef>(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 digraph.
1085    /// The new map's key type is the to digraph's arc type,
1086    /// and the copied map's key type is the from digraph's arc
1087    /// type. 
1088    template <typename ToMap, typename FromMap>
1089    GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1090      arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
1091                              ArcRefMap, ToMap, FromMap>(tmap, map));
1092      return *this;
1093    }
1094
1095    /// \brief Make a copy of the given arc.
1096    ///
1097    /// Make a copy of the given arc.
1098    GraphCopy& arc(TArc& tarc, const Arc& sarc) {
1099      arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
1100                              ArcRefMap, TArc>(tarc, sarc));
1101      return *this;
1102    }
1103
1104    /// \brief Copies the edge references into the given map.
1105    ///
1106    /// Copies the edge references into the given map.
1107    template <typename EdgeRef>
1108    GraphCopy& edgeRef(EdgeRef& map) {
1109      edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
1110                               EdgeRefMap, EdgeRef>(map));
1111      return *this;
1112    }
1113
1114    /// \brief Copies the edge cross references into the given map.
1115    ///
1116    /// Copies the edge cross references (reverse
1117    /// references) into the given map.
1118    template <typename EdgeCrossRef>
1119    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1120      edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1121                               Edge, EdgeRefMap, EdgeCrossRef>(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 digraph.
1128    /// The new map's key type is the to digraph's edge type,
1129    /// and the copied map's key type is the from digraph's edge
1130    /// type. 
1131    template <typename ToMap, typename FromMap>
1132    GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1133      edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
1134                               EdgeRefMap, ToMap, FromMap>(tmap, map));
1135      return *this;
1136    }
1137
1138    /// \brief Make a copy of the given edge.
1139    ///
1140    /// Make a copy of the given edge.
1141    GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1142      edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
1143                               EdgeRefMap, TEdge>(tedge, sedge));
1144      return *this;
1145    }
1146
1147    /// \brief Executes the copies.
1148    ///
1149    /// Executes the copies.
1150    void run() {
1151      NodeRefMap nodeRefMap(from);
1152      EdgeRefMap edgeRefMap(from);
1153      ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
1154      _digraph_utils_bits::GraphCopySelector<To>::
1155        copy(to, from, nodeRefMap, edgeRefMap);
1156      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1157        nodeMapCopies[i]->copy(from, nodeRefMap);
1158      }
1159      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1160        edgeMapCopies[i]->copy(from, edgeRefMap);
1161      }
1162      for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1163        arcMapCopies[i]->copy(from, arcRefMap);
1164      }
1165    }
1166
1167  private:
1168   
1169    const From& from;
1170    To& to;
1171
1172    std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1173    nodeMapCopies;
1174
1175    std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1176    arcMapCopies;
1177
1178    std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1179    edgeMapCopies;
1180
1181  };
1182
1183  /// \brief Copy an graph to another digraph.
1184  ///
1185  /// Copy an graph to another digraph.
1186  /// The usage of the function:
1187  ///
1188  ///\code
1189  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(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 digraph to the nodes of the \c to digraph and
1194  /// \c ecr will contain the mapping from the arcs of the \c to digraph
1195  /// to the arcs of the \c from digraph.
1196  ///
1197  /// \see GraphCopy
1198  template <typename To, typename From>
1199  GraphCopy<To, From>
1200  copyGraph(To& to, const From& from) {
1201    return GraphCopy<To, From>(to, from);
1202  }
1203
1204  /// \brief Class to copy a bipartite digraph.
1205  ///
1206  /// Class to copy a bipartite digraph to another digraph
1207  /// (duplicate a digraph).  The simplest way of using it is through
1208  /// the \c copyBpGraph() function.
1209  template <typename To, typename From>
1210  class BpGraphCopy {
1211  private:
1212
1213    typedef typename From::Node Node;
1214    typedef typename From::Red Red;
1215    typedef typename From::Blue Blue;
1216    typedef typename From::NodeIt NodeIt;
1217    typedef typename From::Arc Arc;
1218    typedef typename From::ArcIt ArcIt;
1219    typedef typename From::Edge Edge;
1220    typedef typename From::EdgeIt EdgeIt;
1221
1222    typedef typename To::Node TNode;
1223    typedef typename To::Arc TArc;
1224    typedef typename To::Edge TEdge;
1225
1226    typedef typename From::template RedMap<TNode> RedRefMap;
1227    typedef typename From::template BlueMap<TNode> BlueRefMap;
1228    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1229
1230    struct NodeRefMap {
1231      NodeRefMap(const From& _from, const RedRefMap& _red_ref,
1232                 const BlueRefMap& _blue_ref)
1233        : from(_from), red_ref(_red_ref), blue_ref(_blue_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.red(key) ? red_ref[key] : blue_ref[key];
1240      }
1241     
1242      const From& from;
1243      const RedRefMap& red_ref;
1244      const BlueRefMap& blue_ref;
1245    };
1246
1247    struct ArcRefMap {
1248      ArcRefMap(const To& _to, const From& _from,
1249                 const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
1250        : to(_to), from(_from),
1251          edge_ref(_edge_ref), node_ref(_node_ref) {}
1252
1253      typedef typename From::Arc Key;
1254      typedef typename To::Arc Value;
1255
1256      Value operator[](const Key& key) const {
1257        bool forward =
1258          (from.direction(key) ==
1259           (node_ref[from.source(static_cast<const Edge&>(key))] ==
1260            to.source(edge_ref[static_cast<const Edge&>(key)])));
1261        return to.direct(edge_ref[key], forward);
1262      }
1263     
1264      const To& to;
1265      const From& from;
1266      const EdgeRefMap& edge_ref;
1267      const NodeRefMap& node_ref;
1268    };
1269   
1270  public:
1271
1272
1273    /// \brief Constructor for the DigraphCopy.
1274    ///
1275    /// It copies the content of the \c _from digraph into the
1276    /// \c _to digraph.
1277    BpGraphCopy(To& _to, const From& _from)
1278      : from(_from), to(_to) {}
1279
1280    /// \brief Destructor of the DigraphCopy
1281    ///
1282    /// Destructor of the DigraphCopy
1283    ~BpGraphCopy() {
1284      for (int i = 0; i < int(redMapCopies.size()); ++i) {
1285        delete redMapCopies[i];
1286      }
1287      for (int i = 0; i < int(blueMapCopies.size()); ++i) {
1288        delete blueMapCopies[i];
1289      }
1290      for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1291        delete nodeMapCopies[i];
1292      }
1293      for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1294        delete arcMapCopies[i];
1295      }
1296      for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1297        delete edgeMapCopies[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 RedRef>
1306    BpGraphCopy& redRef(RedRef& map) {
1307      redMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Red,
1308                               RedRefMap, RedRef>(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 RedCrossRef>
1317    BpGraphCopy& redCrossRef(RedCrossRef& map) {
1318      redMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1319                               Red, RedRefMap, RedCrossRef>(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 digraph.
1326    /// The new map's key type is the to digraph's node type,
1327    /// and the copied map's key type is the from digraph's node
1328    /// type. 
1329    template <typename ToMap, typename FromMap>
1330    BpGraphCopy& redMap(ToMap& tmap, const FromMap& map) {
1331      redMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Red,
1332                               RedRefMap, 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 BlueRef>
1340    BpGraphCopy& blueRef(BlueRef& map) {
1341      blueMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Blue,
1342                               BlueRefMap, BlueRef>(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 BlueCrossRef>
1351    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
1352      blueMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1353                              Blue, BlueRefMap, BlueCrossRef>(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 digraph.
1360    /// The new map's key type is the to digraph's node type,
1361    /// and the copied map's key type is the from digraph's node
1362    /// type. 
1363    template <typename ToMap, typename FromMap>
1364    BpGraphCopy& blueMap(ToMap& tmap, const FromMap& map) {
1365      blueMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Blue,
1366                               BlueRefMap, 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    BpGraphCopy& nodeRef(NodeRef& map) {
1374      nodeMapCopies.push_back(new _digraph_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    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1385      nodeMapCopies.push_back(new _digraph_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 digraph.
1393    /// The new map's key type is the to digraph's node type,
1394    /// and the copied map's key type is the from digraph's node
1395    /// type. 
1396    template <typename ToMap, typename FromMap>
1397    BpGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1398      nodeMapCopies.push_back(new _digraph_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    BpGraphCopy& node(TNode& tnode, const Node& snode) {
1407      nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
1408                              NodeRefMap, TNode>(tnode, snode));
1409      return *this;
1410    }
1411
1412    /// \brief Copies the arc references into the given map.
1413    ///
1414    /// Copies the arc references into the given map.
1415    template <typename ArcRef>
1416    BpGraphCopy& arcRef(ArcRef& map) {
1417      arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
1418                              ArcRefMap, ArcRef>(map));
1419      return *this;
1420    }
1421
1422    /// \brief Copies the arc cross references into the given map.
1423    ///
1424    ///  Copies the arc cross references (reverse references) into
1425    ///  the given map.
1426    template <typename ArcCrossRef>
1427    BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
1428      arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
1429                              ArcRefMap, ArcCrossRef>(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 digraph.
1436    /// The new map's key type is the to digraph's arc type,
1437    /// and the copied map's key type is the from digraph's arc
1438    /// type. 
1439    template <typename ToMap, typename FromMap>
1440    BpGraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1441      arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
1442                              ArcRefMap, ToMap, FromMap>(tmap, map));
1443      return *this;
1444    }
1445
1446    /// \brief Make a copy of the given arc.
1447    ///
1448    /// Make a copy of the given arc.
1449    BpGraphCopy& arc(TArc& tarc, const Arc& sarc) {
1450      arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
1451                              ArcRefMap, TArc>(tarc, sarc));
1452      return *this;
1453    }
1454
1455    /// \brief Copies the edge references into the given map.
1456    ///
1457    /// Copies the edge references into the given map.
1458    template <typename EdgeRef>
1459    BpGraphCopy& edgeRef(EdgeRef& map) {
1460      edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
1461                               EdgeRefMap, EdgeRef>(map));
1462      return *this;
1463    }
1464
1465    /// \brief Copies the edge cross references into the given map.
1466    ///
1467    /// Copies the edge cross references (reverse
1468    /// references) into the given map.
1469    template <typename EdgeCrossRef>
1470    BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1471      edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1472                               Edge, EdgeRefMap, EdgeCrossRef>(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 digraph.
1479    /// The new map's key type is the to digraph's edge type,
1480    /// and the copied map's key type is the from digraph's edge
1481    /// type. 
1482    template <typename ToMap, typename FromMap>
1483    BpGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1484      edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
1485                               EdgeRefMap, ToMap, FromMap>(tmap, map));
1486      return *this;
1487    }
1488
1489    /// \brief Make a copy of the given edge.
1490    ///
1491    /// Make a copy of the given edge.
1492    BpGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1493      edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
1494                               EdgeRefMap, TEdge>(tedge, sedge));
1495      return *this;
1496    }
1497
1498    /// \brief Executes the copies.
1499    ///
1500    /// Executes the copies.
1501    void run() {
1502      RedRefMap redRefMap(from);
1503      BlueRefMap blueRefMap(from);
1504      NodeRefMap nodeRefMap(from, redRefMap, blueRefMap);
1505      EdgeRefMap edgeRefMap(from);
1506      ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
1507      _digraph_utils_bits::BpGraphCopySelector<To>::
1508        copy(to, from, redRefMap, blueRefMap, edgeRefMap);
1509      for (int i = 0; i < int(redMapCopies.size()); ++i) {
1510        redMapCopies[i]->copy(from, redRefMap);
1511      }
1512      for (int i = 0; i < int(blueMapCopies.size()); ++i) {
1513        blueMapCopies[i]->copy(from, blueRefMap);
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(edgeMapCopies.size()); ++i) {
1519        edgeMapCopies[i]->copy(from, edgeRefMap);
1520      }
1521      for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1522        arcMapCopies[i]->copy(from, arcRefMap);
1523      }
1524    }
1525
1526  private:
1527   
1528    const From& from;
1529    To& to;
1530
1531    std::vector<_digraph_utils_bits::MapCopyBase<From, Red, RedRefMap>* >
1532    redMapCopies;
1533
1534    std::vector<_digraph_utils_bits::MapCopyBase<From, Blue, BlueRefMap>* >
1535    blueMapCopies;
1536
1537    std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1538    nodeMapCopies;
1539
1540    std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1541    arcMapCopies;
1542
1543    std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1544    edgeMapCopies;
1545
1546  };
1547
1548  /// \brief Copy a bipartite digraph to another digraph.
1549  ///
1550  /// Copy a bipartite digraph to another digraph.
1551  /// The usage of the function:
1552  ///
1553  ///\code
1554  /// copyBpGraph(trg, src).redRef(anr).arcCrossRef(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 digraph to the nodes of the \c to digraph and
1559  /// \c ecr will contain the mapping from the arcs of the \c to digraph
1560  /// to the arcs of the \c from digraph.
1561  ///
1562  /// \see BpGraphCopy
1563  template <typename To, typename From>
1564  BpGraphCopy<To, From>
1565  copyBpGraph(To& to, const From& from) {
1566    return BpGraphCopy<To, From>(to, from);
1567  }
1568
1569
1570  /// @}
1571
1572  /// \addtogroup digraph_maps
1573  /// @{
1574
1575  /// Provides an immutable and unique id for each item in the digraph.
1576
1577  /// The IdMap class provides a unique and immutable id for each item of the
1578  /// same type (e.g. node) in the digraph. 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 digraph. This map can be inverted with its member
1583  /// class \c InverseMap.
1584  ///
1585  template <typename _Digraph, typename _Item>
1586  class IdMap {
1587  public:
1588    typedef _Digraph Digraph;
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 Digraph& _digraph) : digraph(&_digraph) {}
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 digraph->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 digraph->fromId(id, Item()); }
1607
1608  private:
1609    const Digraph* digraph;
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 Digraph& _digraph) : digraph(&_digraph) {}
1624
1625      /// \brief Constructor.
1626      ///
1627      /// Constructor for creating an id-to-item map.
1628      explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}
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 digraph->fromId(id, Item());}
1635
1636    private:
1637      const Digraph* digraph;
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(*digraph);}
1644
1645  };
1646
1647 
1648  /// \brief General invertable digraph-map type.
1649
1650  /// This type provides simple invertable digraph-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 _Digraph The digraph type.
1659  /// \param _Item The item type of the digraph.
1660  /// \param _Value The value type of the map.
1661  ///
1662  /// \see IterableValueMap
1663  template <typename _Digraph, typename _Item, typename _Value>
1664  class InvertableMap : protected DefaultMap<_Digraph, _Item, _Value> {
1665  private:
1666   
1667    typedef DefaultMap<_Digraph, _Item, _Value> Map;
1668    typedef _Digraph Digraph;
1669
1670    typedef std::map<_Value, _Item> Container;
1671    Container invMap;   
1672
1673  public:
1674 
1675    /// The key type of InvertableMap (Node, Arc, Edge).
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 digraph.
1685    ///
1686    explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}
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 digraph.
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  /// digraph. 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 _Digraph The digraph class the \c DescriptorMap belongs to.
1864  /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
1865  /// Edge.
1866  template <typename _Digraph, typename _Item>
1867  class DescriptorMap : protected DefaultMap<_Digraph, _Item, int> {
1868
1869    typedef _Item Item;
1870    typedef DefaultMap<_Digraph, _Item, int> Map;
1871
1872  public:
1873    /// The digraph class of DescriptorMap.
1874    typedef _Digraph Digraph;
1875
1876    /// The key type of DescriptorMap (Node, Arc, Edge).
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 Digraph& _digraph) : Map(_digraph) {
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 arc.
2050  ///
2051  /// The SourceMap gives back the source Node of the given arc.
2052  /// \see TargetMap
2053  /// \author Balazs Dezso
2054  template <typename Digraph>
2055  class SourceMap {
2056  public:
2057
2058    typedef typename Digraph::Node Value;
2059    typedef typename Digraph::Arc Key;
2060
2061    /// \brief Constructor
2062    ///
2063    /// Constructor
2064    /// \param _digraph The digraph that the map belongs to.
2065    explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}
2066
2067    /// \brief The subscript operator.
2068    ///
2069    /// The subscript operator.
2070    /// \param arc The arc
2071    /// \return The source of the arc
2072    Value operator[](const Key& arc) const {
2073      return digraph.source(arc);
2074    }
2075
2076  private:
2077    const Digraph& digraph;
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 Digraph>
2085  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
2086    return SourceMap<Digraph>(digraph);
2087  }
2088
2089  /// \brief Returns the target of the given arc.
2090  ///
2091  /// The TargetMap gives back the target Node of the given arc.
2092  /// \see SourceMap
2093  /// \author Balazs Dezso
2094  template <typename Digraph>
2095  class TargetMap {
2096  public:
2097
2098    typedef typename Digraph::Node Value;
2099    typedef typename Digraph::Arc Key;
2100
2101    /// \brief Constructor
2102    ///
2103    /// Constructor
2104    /// \param _digraph The digraph that the map belongs to.
2105    explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}
2106
2107    /// \brief The subscript operator.
2108    ///
2109    /// The subscript operator.
2110    /// \param e The arc
2111    /// \return The target of the arc
2112    Value operator[](const Key& e) const {
2113      return digraph.target(e);
2114    }
2115
2116  private:
2117    const Digraph& digraph;
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 Digraph>
2125  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
2126    return TargetMap<Digraph>(digraph);
2127  }
2128
2129  /// \brief Returns the "forward" directed arc view of an edge.
2130  ///
2131  /// Returns the "forward" directed arc view of an edge.
2132  /// \see BackwardMap
2133  /// \author Balazs Dezso
2134  template <typename Digraph>
2135  class ForwardMap {
2136  public:
2137
2138    typedef typename Digraph::Arc Value;
2139    typedef typename Digraph::Edge Key;
2140
2141    /// \brief Constructor
2142    ///
2143    /// Constructor
2144    /// \param _digraph The digraph that the map belongs to.
2145    explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}
2146
2147    /// \brief The subscript operator.
2148    ///
2149    /// The subscript operator.
2150    /// \param key An edge
2151    /// \return The "forward" directed arc view of edge
2152    Value operator[](const Key& key) const {
2153      return digraph.direct(key, true);
2154    }
2155
2156  private:
2157    const Digraph& digraph;
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 Digraph>
2165  inline ForwardMap<Digraph> forwardMap(const Digraph& digraph) {
2166    return ForwardMap<Digraph>(digraph);
2167  }
2168
2169  /// \brief Returns the "backward" directed arc view of an edge.
2170  ///
2171  /// Returns the "backward" directed arc view of an edge.
2172  /// \see ForwardMap
2173  /// \author Balazs Dezso
2174  template <typename Digraph>
2175  class BackwardMap {
2176  public:
2177
2178    typedef typename Digraph::Arc Value;
2179    typedef typename Digraph::Edge Key;
2180
2181    /// \brief Constructor
2182    ///
2183    /// Constructor
2184    /// \param _digraph The digraph that the map belongs to.
2185    explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}
2186
2187    /// \brief The subscript operator.
2188    ///
2189    /// The subscript operator.
2190    /// \param key An edge
2191    /// \return The "backward" directed arc view of edge
2192    Value operator[](const Key& key) const {
2193      return digraph.direct(key, false);
2194    }
2195
2196  private:
2197    const Digraph& digraph;
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 Digraph>
2205  inline BackwardMap<Digraph> backwardMap(const Digraph& digraph) {
2206    return BackwardMap<Digraph>(digraph);
2207  }
2208
2209  /// \brief Potential difference map
2210  ///
2211  /// If there is an potential map on the nodes then we
2212  /// can get an arc map as we get the substraction of the
2213  /// values of the target and source.
2214  template <typename Digraph, typename NodeMap>
2215  class PotentialDifferenceMap {
2216  public:
2217    typedef typename Digraph::Arc Key;
2218    typedef typename NodeMap::Value Value;
2219
2220    /// \brief Constructor
2221    ///
2222    /// Contructor of the map
2223    explicit PotentialDifferenceMap(const Digraph& _digraph,
2224                                    const NodeMap& _potential)
2225      : digraph(_digraph), potential(_potential) {}
2226
2227    /// \brief Const subscription operator
2228    ///
2229    /// Const subscription operator
2230    Value operator[](const Key& arc) const {
2231      return potential[digraph.target(arc)] - potential[digraph.source(arc)];
2232    }
2233
2234  private:
2235    const Digraph& digraph;
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 Digraph, typename NodeMap>
2244  PotentialDifferenceMap<Digraph, NodeMap>
2245  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
2246    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, 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 digraph changes.
2255  ///
2256  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2257  /// alternative ways to modify the digraph. The correct behavior of InDegMap
2258  /// is not guarantied if these additional features are used. For example
2259  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2260  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2261  /// \ref ListDigraph::reverseArc() "reverseArc()"
2262  /// of \ref ListDigraph will \e not update the degree values correctly.
2263  ///
2264  /// \sa OutDegMap
2265
2266  template <typename _Digraph>
2267  class InDegMap 
2268    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2269      ::ItemNotifier::ObserverBase {
2270
2271  public:
2272   
2273    typedef _Digraph Digraph;
2274    typedef int Value;
2275    typedef typename Digraph::Node Key;
2276
2277    typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
2278    ::ItemNotifier::ObserverBase Parent;
2279
2280  private:
2281
2282    class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
2283    public:
2284
2285      typedef DefaultMap<_Digraph, Key, int> Parent;
2286      typedef typename Parent::Digraph Digraph;
2287
2288      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 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 Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
2318      Parent::attach(digraph.notifier(typename _Digraph::Arc()));
2319     
2320      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2321        deg[it] = countInArcs(digraph, 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 Digraph::Arc Arc;
2333
2334    virtual void add(const Arc& arc) {
2335      ++deg[digraph.target(arc)];
2336    }
2337
2338    virtual void add(const std::vector<Arc>& arcs) {
2339      for (int i = 0; i < int(arcs.size()); ++i) {
2340        ++deg[digraph.target(arcs[i])];
2341      }
2342    }
2343
2344    virtual void erase(const Arc& arc) {
2345      --deg[digraph.target(arc)];
2346    }
2347
2348    virtual void erase(const std::vector<Arc>& arcs) {
2349      for (int i = 0; i < int(arcs.size()); ++i) {
2350        --deg[digraph.target(arcs[i])];
2351      }
2352    }
2353
2354    virtual void build() {
2355      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2356        deg[it] = countInArcs(digraph, it);
2357      }     
2358    }
2359
2360    virtual void clear() {
2361      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2362        deg[it] = 0;
2363      }
2364    }
2365  private:
2366   
2367    const _Digraph& digraph;
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 digraph changes.
2377  ///
2378  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2379  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
2380  /// is not guarantied if these additional features are used. For example
2381  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2382  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2383  /// \ref ListDigraph::reverseArc() "reverseArc()"
2384  /// of \ref ListDigraph will \e not update the degree values correctly.
2385  ///
2386  /// \sa InDegMap
2387
2388  template <typename _Digraph>
2389  class OutDegMap 
2390    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2391      ::ItemNotifier::ObserverBase {
2392
2393  public:
2394
2395    typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
2396    ::ItemNotifier::ObserverBase Parent;
2397   
2398    typedef _Digraph Digraph;
2399    typedef int Value;
2400    typedef typename Digraph::Node Key;
2401
2402  private:
2403
2404    class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
2405    public:
2406
2407      typedef DefaultMap<_Digraph, Key, int> Parent;
2408      typedef typename Parent::Digraph Digraph;
2409
2410      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 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 Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
2438      Parent::attach(digraph.notifier(typename _Digraph::Arc()));
2439     
2440      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2441        deg[it] = countOutArcs(digraph, 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 Digraph::Arc Arc;
2453
2454    virtual void add(const Arc& arc) {
2455      ++deg[digraph.source(arc)];
2456    }
2457
2458    virtual void add(const std::vector<Arc>& arcs) {
2459      for (int i = 0; i < int(arcs.size()); ++i) {
2460        ++deg[digraph.source(arcs[i])];
2461      }
2462    }
2463
2464    virtual void erase(const Arc& arc) {
2465      --deg[digraph.source(arc)];
2466    }
2467
2468    virtual void erase(const std::vector<Arc>& arcs) {
2469      for (int i = 0; i < int(arcs.size()); ++i) {
2470        --deg[digraph.source(arcs[i])];
2471      }
2472    }
2473
2474    virtual void build() {
2475      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2476        deg[it] = countOutArcs(digraph, it);
2477      }     
2478    }
2479
2480    virtual void clear() {
2481      for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2482        deg[it] = 0;
2483      }
2484    }
2485  private:
2486   
2487    const _Digraph& digraph;
2488    AutoNodeMap deg;
2489  };
2490
2491
2492  ///Dynamic arc look up between given endpoints.
2493 
2494  ///\ingroup gutils
2495  ///Using this class, you can find an arc in a digraph 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 arcs between two nodes with
2500  ///the \c findFirst() and \c findNext() members.
2501  ///
2502  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
2503  ///digraph 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 arc 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 digraph. 
2512  ///
2513  ///\sa ArcLookUp 
2514  ///\sa AllArcLookUp 
2515  template<class G>
2516  class DynArcLookUp
2517    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
2518  {
2519  public:
2520    typedef typename ItemSetTraits<G, typename G::Arc>
2521    ::ItemNotifier::ObserverBase Parent;
2522
2523    GRAPH_TYPEDEFS(typename G);
2524    typedef G Digraph;
2525
2526  protected:
2527
2528    class AutoNodeMap : public DefaultMap<G, Node, Arc> {
2529    public:
2530
2531      typedef DefaultMap<G, Node, Arc> Parent;
2532
2533      AutoNodeMap(const G& digraph) : Parent(digraph, 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 Digraph &_g;
2558    AutoNodeMap _head;
2559    typename Digraph::template ArcMap<Arc> _parent;
2560    typename Digraph::template ArcMap<Arc> _left;
2561    typename Digraph::template ArcMap<Arc> _right;
2562   
2563    class ArcLess {
2564      const Digraph &g;
2565    public:
2566      ArcLess(const Digraph &_g) : g(_g) {}
2567      bool operator()(Arc a,Arc 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    DynArcLookUp(const Digraph &g)
2581      : _g(g),_head(g),_parent(g),_left(g),_right(g)
2582    {
2583      Parent::attach(_g.notifier(typename Digraph::Arc()));
2584      refresh();
2585    }
2586   
2587  protected:
2588
2589    virtual void add(const Arc& arc) {
2590      insert(arc);
2591    }
2592
2593    virtual void add(const std::vector<Arc>& arcs) {
2594      for (int i = 0; i < int(arcs.size()); ++i) {
2595        insert(arcs[i]);
2596      }
2597    }
2598
2599    virtual void erase(const Arc& arc) {
2600      remove(arc);
2601    }
2602
2603    virtual void erase(const std::vector<Arc>& arcs) {
2604      for (int i = 0; i < int(arcs.size()); ++i) {
2605        remove(arcs[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(Arc arc) {
2620      Node s = _g.source(arc);
2621      Node t = _g.target(arc);
2622      _left.set(arc, INVALID);
2623      _right.set(arc, INVALID);
2624     
2625      Arc e = _head[s];
2626      if (e == INVALID) {
2627        _head.set(s, arc);
2628        _parent.set(arc, INVALID);
2629        return;
2630      }
2631      while (true) {
2632        if (t < _g.target(e)) {
2633          if (_left[e] == INVALID) {
2634            _left.set(e, arc);
2635            _parent.set(arc, e);
2636            splay(arc);
2637            return;
2638          } else {
2639            e = _left[e];
2640          }
2641        } else {
2642          if (_right[e] == INVALID) {
2643            _right.set(e, arc);
2644            _parent.set(arc, e);
2645            splay(arc);
2646            return;
2647          } else {
2648            e = _right[e];
2649          }
2650        }
2651      }
2652    }
2653
2654    void remove(Arc arc) {
2655      if (_left[arc] == INVALID) {
2656        if (_right[arc] != INVALID) {
2657          _parent.set(_right[arc], _parent[arc]);
2658        }
2659        if (_parent[arc] != INVALID) {
2660          if (_left[_parent[arc]] == arc) {
2661            _left.set(_parent[arc], _right[arc]);
2662          } else {
2663            _right.set(_parent[arc], _right[arc]);
2664          }
2665        } else {
2666          _head.set(_g.source(arc), _right[arc]);
2667        }
2668      } else if (_right[arc] == INVALID) {
2669        _parent.set(_left[arc], _parent[arc]);
2670        if (_parent[arc] != INVALID) {
2671          if (_left[_parent[arc]] == arc) {
2672            _left.set(_parent[arc], _left[arc]);
2673          } else {
2674            _right.set(_parent[arc], _left[arc]);
2675          }
2676        } else {
2677          _head.set(_g.source(arc), _left[arc]);
2678        }
2679      } else {
2680        Arc e = _left[arc];
2681        if (_right[e] != INVALID) {
2682          e = _right[e];         
2683          while (_right[e] != INVALID) {
2684            e = _right[e];
2685          }
2686          Arc 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[arc]);
2693          _parent.set(_left[arc], e);
2694          _right.set(e, _right[arc]);
2695          _parent.set(_right[arc], e);
2696
2697          _parent.set(e, _parent[arc]);
2698          if (_parent[arc] != INVALID) {
2699            if (_left[_parent[arc]] == arc) {
2700              _left.set(_parent[arc], e);
2701            } else {
2702              _right.set(_parent[arc], e);
2703            }
2704          }
2705          splay(s);
2706        } else {
2707          _right.set(e, _right[arc]);
2708          _parent.set(_right[arc], e);
2709
2710          if (_parent[arc] != INVALID) {
2711            if (_left[_parent[arc]] == arc) {
2712              _left.set(_parent[arc], e);
2713            } else {
2714              _right.set(_parent[arc], e);
2715            }
2716          } else {
2717            _head.set(_g.source(arc), e);
2718          }
2719        }
2720      }
2721    }
2722
2723    Arc refreshRec(std::vector<Arc> &v,int a,int b)
2724    {
2725      int m=(a+b)/2;
2726      Arc me=v[m];
2727      if (a < m) {
2728        Arc left = refreshRec(v,a,m-1);
2729        _left.set(me, left);
2730        _parent.set(left, me);
2731      } else {
2732        _left.set(me, INVALID);
2733      }
2734      if (m < b) {
2735        Arc right = refreshRec(v,m+1,b);
2736        _right.set(me, right);
2737        _parent.set(right, me);
2738      } else {
2739        _right.set(me, INVALID);
2740      }
2741      return me;
2742    }
2743
2744    void refresh() {
2745      for(NodeIt n(_g);n!=INVALID;++n) {
2746        std::vector<Arc> v;
2747        for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2748        if(v.size()) {
2749          std::sort(v.begin(),v.end(),ArcLess(_g));
2750          Arc head = refreshRec(v,0,v.size()-1);
2751          _head.set(n, head);
2752          _parent.set(head, INVALID);
2753        }
2754        else _head.set(n, INVALID);
2755      }
2756    }
2757
2758    void zig(Arc v) {       
2759      Arc w = _parent[v];
2760      _parent.set(v, _parent[w]);
2761      _parent.set(w, v);
2762      _left.set(w, _right[v]);
2763      _right.set(v, w);
2764      if (_parent[v] != INVALID) {
2765        if (_right[_parent[v]] == w) {
2766          _right.set(_parent[v], v);
2767        } else {
2768          _left.set(_parent[v], v);
2769        }
2770      }
2771      if (_left[w] != INVALID){
2772        _parent.set(_left[w], w);
2773      }
2774    }
2775
2776    void zag(Arc v) {       
2777      Arc w = _parent[v];
2778      _parent.set(v, _parent[w]);
2779      _parent.set(w, v);
2780      _right.set(w, _left[v]);
2781      _left.set(v, w);
2782      if (_parent[v] != INVALID){
2783        if (_left[_parent[v]] == w) {
2784          _left.set(_parent[v], v);
2785        } else {
2786          _right.set(_parent[v], v);
2787        }
2788      }
2789      if (_right[w] != INVALID){
2790        _parent.set(_right[w], w);
2791      }
2792    }
2793
2794    void splay(Arc v) {
2795      while (_parent[v] != INVALID) {
2796        if (v == _left[_parent[v]]) {
2797          if (_parent[_parent[v]] == INVALID) {
2798            zig(v);
2799          } else {
2800            if (_parent[v] == _left[_parent[_parent[v]]]) {
2801              zig(_parent[v]);
2802              zig(v);
2803            } else {
2804              zig(v);
2805              zag(v);
2806            }
2807          }
2808        } else {
2809          if (_parent[_parent[v]] == INVALID) {
2810            zag(v);
2811          } else {
2812            if (_parent[v] == _left[_parent[_parent[v]]]) {
2813              zag(v);
2814              zig(v);
2815            } else {
2816              zag(_parent[v]);
2817              zag(v);
2818            }
2819          }
2820        }
2821      }
2822      _head[_g.source(v)] = v;
2823    }
2824
2825
2826  public:
2827   
2828    ///Find an arc between two nodes.
2829   
2830    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
2831    /// <em>d</em> is the number of outgoing arcs of \c s.
2832    ///\param s The source node
2833    ///\param t The target node
2834    ///\return An arc from \c s to \c t if there exists,
2835    ///\ref INVALID otherwise.
2836    Arc operator()(Node s, Node t) const
2837    {
2838      Arc e = _head[s];
2839      while (true) {
2840        if (_g.target(e) == t) {
2841          const_cast<DynArcLookUp&>(*this).splay(e);
2842          return e;
2843        } else if (t < _g.target(e)) {
2844          if (_left[e] == INVALID) {
2845            const_cast<DynArcLookUp&>(*this).splay(e);
2846            return INVALID;
2847          } else {
2848            e = _left[e];
2849          }
2850        } else  {
2851          if (_right[e] == INVALID) {
2852            const_cast<DynArcLookUp&>(*this).splay(e);
2853            return INVALID;
2854          } else {
2855            e = _right[e];
2856          }
2857        }
2858      }
2859    }
2860
2861    ///Find the first arc between two nodes.
2862   
2863    ///Find the first arc between two nodes in time
2864    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2865    /// outgoing arcs of \c s. 
2866    ///\param s The source node
2867    ///\param t The target node
2868    ///\return An arc from \c s to \c t if there exists, \ref INVALID
2869    /// otherwise.
2870    Arc findFirst(Node s, Node t) const
2871    {
2872      Arc e = _head[s];
2873      Arc r = INVALID;
2874      while (true) {
2875        if (_g.target(e) < t) {
2876          if (_right[e] == INVALID) {
2877            const_cast<DynArcLookUp&>(*this).splay(e);
2878            return r;
2879          } else {
2880            e = _right[e];
2881          }
2882        } else {
2883          if (_g.target(e) == t) {
2884            r = e;
2885          }
2886          if (_left[e] == INVALID) {
2887            const_cast<DynArcLookUp&>(*this).splay(e);
2888            return r;
2889          } else {
2890            e = _left[e];
2891          }
2892        }
2893      }
2894    }
2895
2896    ///Find the next arc between two nodes.
2897   
2898    ///Find the next arc between two nodes in time
2899    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
2900    /// outgoing arcs of \c s. 
2901    ///\param s The source node
2902    ///\param t The target node
2903    ///\return An arc from \c s to \c t if there exists, \ref INVALID
2904    /// otherwise.
2905
2906    ///\note If \c e is not the result of the previous \c findFirst()
2907    ///operation then the amorized time bound can not be guaranteed.
2908#ifdef DOXYGEN
2909    Arc findNext(Node s, Node t, Arc e) const
2910#else
2911    Arc findNext(Node, Node t, Arc e) const
2912#endif
2913    {
2914      if (_right[e] != INVALID) {
2915        e = _right[e];
2916        while (_left[e] != INVALID) {
2917          e = _left[e];
2918        }
2919        const_cast<DynArcLookUp&>(*this).splay(e);
2920      } else {
2921        while (_parent[e] != INVALID && _right[_parent[e]] ==  e) {
2922          e = _parent[e];
2923        }
2924        if (_parent[e] == INVALID) {
2925          return INVALID;
2926        } else {
2927          e = _parent[e];
2928          const_cast<DynArcLookUp&>(*this).splay(e);
2929        }
2930      }
2931      if (_g.target(e) == t) return e;
2932      else return INVALID;   
2933    }
2934
2935  };
2936
2937  ///Fast arc look up between given endpoints.
2938 
2939  ///\ingroup gutils
2940  ///Using this class, you can find an arc in a digraph from a given
2941  ///source to a given target in time <em>O(log d)</em>,
2942  ///where <em>d</em> is the out-degree of the source node.
2943  ///
2944  ///It is not possible to find \e all parallel arcs between two nodes.
2945  ///Use \ref AllArcLookUp for this purpose.
2946  ///
2947  ///\warning This class is static, so you should refresh() (or at least
2948  ///refresh(Node)) this data structure
2949  ///whenever the digraph changes. This is a time consuming (superlinearly
2950  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
2951  ///
2952  ///\param G The type of the underlying digraph.
2953  ///
2954  ///\sa DynArcLookUp
2955  ///\sa AllArcLookUp 
2956  template<class G>
2957  class ArcLookUp
2958  {
2959  public:
2960    GRAPH_TYPEDEFS(typename G);
2961    typedef G Digraph;
2962
2963  protected:
2964    const Digraph &_g;
2965    typename Digraph::template NodeMap<Arc> _head;
2966    typename Digraph::template ArcMap<Arc> _left;
2967    typename Digraph::template ArcMap<Arc> _right;
2968   
2969    class ArcLess {
2970      const Digraph &g;
2971    public:
2972      ArcLess(const Digraph &_g) : g(_g) {}
2973      bool operator()(Arc a,Arc b) const
2974      {
2975        return g.target(a)<g.target(b);
2976      }
2977    };
2978   
2979  public:
2980   
2981    ///Constructor
2982
2983    ///Constructor.
2984    ///
2985    ///It builds up the search database, which remains valid until the digraph
2986    ///changes.
2987    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2988   
2989  private:
2990    Arc refreshRec(std::vector<Arc> &v,int a,int b)
2991    {
2992      int m=(a+b)/2;
2993      Arc me=v[m];
2994      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
2995      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
2996      return me;
2997    }
2998  public:
2999    ///Refresh the data structure at a node.
3000
3001    ///Build up the search database of node \c n.
3002    ///
3003    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
3004    ///the number of the outgoing arcs of \c n.
3005    void refresh(Node n)
3006    {
3007      std::vector<Arc> v;
3008      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
3009      if(v.size()) {
3010        std::sort(v.begin(),v.end(),ArcLess(_g));
3011        _head[n]=refreshRec(v,0,v.size()-1);
3012      }
3013      else _head[n]=INVALID;
3014    }
3015    ///Refresh the full data structure.
3016
3017    ///Build up the full search database. In fact, it simply calls
3018    ///\ref refresh(Node) "refresh(n)" for each node \c n.
3019    ///
3020    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
3021    ///the number of the arcs of \c n and <em>D</em> is the maximum
3022    ///out-degree of the digraph.
3023
3024    void refresh()
3025    {
3026      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
3027    }
3028   
3029    ///Find an arc between two nodes.
3030   
3031    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
3032    /// <em>d</em> is the number of outgoing arcs of \c s.
3033    ///\param s The source node
3034    ///\param t The target node
3035    ///\return An arc from \c s to \c t if there exists,
3036    ///\ref INVALID otherwise.
3037    ///
3038    ///\warning If you change the digraph, refresh() must be called before using
3039    ///this operator. If you change the outgoing arcs of
3040    ///a single node \c n, then
3041    ///\ref refresh(Node) "refresh(n)" is enough.
3042    ///
3043    Arc operator()(Node s, Node t) const
3044    {
3045      Arc e;
3046      for(e=_head[s];
3047          e!=INVALID&&_g.target(e)!=t;
3048          e = t < _g.target(e)?_left[e]:_right[e]) ;
3049      return e;
3050    }
3051
3052  };
3053
3054  ///Fast look up of all arcs between given endpoints.
3055 
3056  ///\ingroup gutils
3057  ///This class is the same as \ref ArcLookUp, with the addition
3058  ///that it makes it possible to find all arcs between given endpoints.
3059  ///
3060  ///\warning This class is static, so you should refresh() (or at least
3061  ///refresh(Node)) this data structure
3062  ///whenever the digraph changes. This is a time consuming (superlinearly
3063  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
3064  ///
3065  ///\param G The type of the underlying digraph.
3066  ///
3067  ///\sa DynArcLookUp
3068  ///\sa ArcLookUp 
3069  template<class G>
3070  class AllArcLookUp : public ArcLookUp<G>
3071  {
3072    using ArcLookUp<G>::_g;
3073    using ArcLookUp<G>::_right;
3074    using ArcLookUp<G>::_left;
3075    using ArcLookUp<G>::_head;
3076
3077    GRAPH_TYPEDEFS(typename G);
3078    typedef G Digraph;
3079   
3080    typename Digraph::template ArcMap<Arc> _next;
3081   
3082    Arc refreshNext(Arc head,Arc next=INVALID)
3083    {
3084      if(head==INVALID) return next;
3085      else {
3086        next=refreshNext(_right[head],next);
3087//      _next[head]=next;
3088        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
3089          ? next : INVALID;
3090        return refreshNext(_left[head],head);
3091      }
3092    }
3093   
3094    void refreshNext()
3095    {
3096      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
3097    }
3098   
3099  public:
3100    ///Constructor
3101
3102    ///Constructor.
3103    ///
3104    ///It builds up the search database, which remains valid until the digraph
3105    ///changes.
3106    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
3107
3108    ///Refresh the data structure at a node.
3109
3110    ///Build up the search database of node \c n.
3111    ///
3112    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
3113    ///the number of the outgoing arcs of \c n.
3114   
3115    void refresh(Node n)
3116    {
3117      ArcLookUp<G>::refresh(n);
3118      refreshNext(_head[n]);
3119    }
3120   
3121    ///Refresh the full data structure.
3122
3123    ///Build up the full search database. In fact, it simply calls
3124    ///\ref refresh(Node) "refresh(n)" for each node \c n.
3125    ///
3126    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
3127    ///the number of the arcs of \c n and <em>D</em> is the maximum
3128    ///out-degree of the digraph.
3129
3130    void refresh()
3131    {
3132      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
3133    }
3134   
3135    ///Find an arc between two nodes.
3136   
3137    ///Find an arc between two nodes.
3138    ///\param s The source node
3139    ///\param t The target node
3140    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
3141    ///not given, the operator finds the first appropriate arc.
3142    ///\return An arc from \c s to \c t after \c prev or
3143    ///\ref INVALID if there is no more.
3144    ///
3145    ///For example, you can count the number of arcs from \c u to \c v in the
3146    ///following way.
3147    ///\code
3148    ///AllArcLookUp<ListDigraph> ae(g);
3149    ///...
3150    ///int n=0;
3151    ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
3152    ///\endcode
3153    ///
3154    ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
3155    /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
3156    ///consecutive arcs are found in constant time.
3157    ///
3158    ///\warning If you change the digraph, refresh() must be called before using
3159    ///this operator. If you change the outgoing arcs of
3160    ///a single node \c n, then
3161    ///\ref refresh(Node) "refresh(n)" is enough.
3162    ///
3163#ifdef DOXYGEN
3164    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
3165#else
3166    using ArcLookUp<G>::operator() ;
3167    Arc operator()(Node s, Node t, Arc prev) const
3168    {
3169      return prev==INVALID?(*this)(s,t):_next[prev];
3170    }
3171#endif
3172     
3173  };
3174
3175  /// @}
3176
3177} //END OF NAMESPACE LEMON
3178
3179#endif
Note: See TracBrowser for help on using the repository browser.