COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2366:bfbdded3763a

Last change on this file since 2366:bfbdded3763a was 2350:eb371753e814, checked in by Alpar Juttner, 17 years ago

Several doc improvements.

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