COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2476:059dcdda37c5, checked in by Peter Kovacs, 12 years ago

Bug fixes in the documentation (mainly bad references).

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