COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2300:69330d717235

Last change on this file since 2300:69330d717235 was 2290:f30867b359a8, checked in by Balazs Dezso, 17 years ago

GraphCopy? and UGraphCopy modifications
Preliminary support for static graphs

=> cloning graphs

Added BpUGraphCopy

Tests for graph copies

File size: 82.1 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  ///\se 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::CloneableTag, 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.clone(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::CloneableTag, 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.clone(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::CloneableTag, 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.clone(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 for creating id 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 map.
1591    int operator[](const Item& item) const { return graph->id(item);}
1592
1593
1594  private:
1595    const Graph* graph;
1596
1597  public:
1598
1599    /// \brief The class represents the inverse of its owner (IdMap).
1600    ///
1601    /// The class represents the inverse of its owner (IdMap).
1602    /// \see inverse()
1603    class InverseMap {
1604    public:
1605
1606      /// \brief Constructor.
1607      ///
1608      /// Constructor for creating an id-to-item map.
1609      explicit InverseMap(const Graph& _graph) : graph(&_graph) {}
1610
1611      /// \brief Constructor.
1612      ///
1613      /// Constructor for creating an id-to-item map.
1614      explicit InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
1615
1616      /// \brief Gives back the given item from its id.
1617      ///
1618      /// Gives back the given item from its id.
1619      ///
1620      Item operator[](int id) const { return graph->fromId(id, Item());}
1621    private:
1622      const Graph* graph;
1623    };
1624
1625    /// \brief Gives back the inverse of the map.
1626    ///
1627    /// Gives back the inverse of the IdMap.
1628    InverseMap inverse() const { return InverseMap(*graph);}
1629
1630  };
1631
1632 
1633  /// \brief General invertable graph-map type.
1634
1635  /// This type provides simple invertable graph-maps.
1636  /// The InvertableMap wraps an arbitrary ReadWriteMap
1637  /// and if a key is set to a new value then store it
1638  /// in the inverse map.
1639  ///
1640  /// The values of the map can be accessed
1641  /// with stl compatible forward iterator.
1642  ///
1643  /// \param _Graph The graph type.
1644  /// \param _Item The item type of the graph.
1645  /// \param _Value The value type of the map.
1646  ///
1647  /// \see IterableValueMap
1648  template <typename _Graph, typename _Item, typename _Value>
1649  class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1650  private:
1651   
1652    typedef DefaultMap<_Graph, _Item, _Value> Map;
1653    typedef _Graph Graph;
1654
1655    typedef std::map<_Value, _Item> Container;
1656    Container invMap;   
1657
1658  public:
1659 
1660    /// The key type of InvertableMap (Node, Edge, UEdge).
1661    typedef typename Map::Key Key;
1662    /// The value type of the InvertableMap.
1663    typedef typename Map::Value Value;
1664
1665
1666
1667    /// \brief Constructor.
1668    ///
1669    /// Construct a new InvertableMap for the graph.
1670    ///
1671    explicit InvertableMap(const Graph& graph) : Map(graph) {}
1672
1673    /// \brief Forward iterator for values.
1674    ///
1675    /// This iterator is an stl compatible forward
1676    /// iterator on the values of the map. The values can
1677    /// be accessed in the [beginValue, endValue) range.
1678    ///
1679    class ValueIterator
1680      : public std::iterator<std::forward_iterator_tag, Value> {
1681      friend class InvertableMap;
1682    private:
1683      ValueIterator(typename Container::const_iterator _it)
1684        : it(_it) {}
1685    public:
1686     
1687      ValueIterator() {}
1688
1689      ValueIterator& operator++() { ++it; return *this; }
1690      ValueIterator operator++(int) {
1691        ValueIterator tmp(*this);
1692        operator++();
1693        return tmp;
1694      }
1695
1696      const Value& operator*() const { return it->first; }
1697      const Value* operator->() const { return &(it->first); }
1698
1699      bool operator==(ValueIterator jt) const { return it == jt.it; }
1700      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1701     
1702    private:
1703      typename Container::const_iterator it;
1704    };
1705
1706    /// \brief Returns an iterator to the first value.
1707    ///
1708    /// Returns an stl compatible iterator to the
1709    /// first value of the map. The values of the
1710    /// map can be accessed in the [beginValue, endValue)
1711    /// range.
1712    ValueIterator beginValue() const {
1713      return ValueIterator(invMap.begin());
1714    }
1715
1716    /// \brief Returns an iterator after the last value.
1717    ///
1718    /// Returns an stl compatible iterator after the
1719    /// last value of the map. The values of the
1720    /// map can be accessed in the [beginValue, endValue)
1721    /// range.
1722    ValueIterator endValue() const {
1723      return ValueIterator(invMap.end());
1724    }
1725   
1726    /// \brief The setter function of the map.
1727    ///
1728    /// Sets the mapped value.
1729    void set(const Key& key, const Value& val) {
1730      Value oldval = Map::operator[](key);
1731      typename Container::iterator it = invMap.find(oldval);
1732      if (it != invMap.end() && it->second == key) {
1733        invMap.erase(it);
1734      }     
1735      invMap.insert(make_pair(val, key));
1736      Map::set(key, val);
1737    }
1738
1739    /// \brief The getter function of the map.
1740    ///
1741    /// It gives back the value associated with the key.
1742    typename MapTraits<Map>::ConstReturnValue
1743    operator[](const Key& key) const {
1744      return Map::operator[](key);
1745    }
1746
1747  protected:
1748
1749    /// \brief Erase the key from the map.
1750    ///
1751    /// Erase the key to the map. It is called by the
1752    /// \c AlterationNotifier.
1753    virtual void erase(const Key& key) {
1754      Value val = Map::operator[](key);
1755      typename Container::iterator it = invMap.find(val);
1756      if (it != invMap.end() && it->second == key) {
1757        invMap.erase(it);
1758      }
1759      Map::erase(key);
1760    }
1761
1762    /// \brief Erase more keys from the map.
1763    ///
1764    /// Erase more keys from the map. It is called by the
1765    /// \c AlterationNotifier.
1766    virtual void erase(const std::vector<Key>& keys) {
1767      for (int i = 0; i < (int)keys.size(); ++i) {
1768        Value val = Map::operator[](keys[i]);
1769        typename Container::iterator it = invMap.find(val);
1770        if (it != invMap.end() && it->second == keys[i]) {
1771          invMap.erase(it);
1772        }
1773      }
1774      Map::erase(keys);
1775    }
1776
1777    /// \brief Clear the keys from the map and inverse map.
1778    ///
1779    /// Clear the keys from the map and inverse map. It is called by the
1780    /// \c AlterationNotifier.
1781    virtual void clear() {
1782      invMap.clear();
1783      Map::clear();
1784    }
1785
1786  public:
1787
1788    /// \brief The inverse map type.
1789    ///
1790    /// The inverse of this map. The subscript operator of the map
1791    /// gives back always the item what was last assigned to the value.
1792    class InverseMap {
1793    public:
1794      /// \brief Constructor of the InverseMap.
1795      ///
1796      /// Constructor of the InverseMap.
1797      explicit InverseMap(const InvertableMap& _inverted)
1798        : inverted(_inverted) {}
1799
1800      /// The value type of the InverseMap.
1801      typedef typename InvertableMap::Key Value;
1802      /// The key type of the InverseMap.
1803      typedef typename InvertableMap::Value Key;
1804
1805      /// \brief Subscript operator.
1806      ///
1807      /// Subscript operator. It gives back always the item
1808      /// what was last assigned to the value.
1809      Value operator[](const Key& key) const {
1810        typename Container::const_iterator it = inverted.invMap.find(key);
1811        return it->second;
1812      }
1813     
1814    private:
1815      const InvertableMap& inverted;
1816    };
1817
1818    /// \brief It gives back the just readable inverse map.
1819    ///
1820    /// It gives back the just readable inverse map.
1821    InverseMap inverse() const {
1822      return InverseMap(*this);
1823    }
1824
1825
1826   
1827  };
1828
1829  /// \brief Provides a mutable, continuous and unique descriptor for each
1830  /// item in the graph.
1831  ///
1832  /// The DescriptorMap class provides a unique and continuous (but mutable)
1833  /// descriptor (id) for each item of the same type (e.g. node) in the
1834  /// graph. This id is <ul><li>\b unique: different items (nodes) get
1835  /// different ids <li>\b continuous: the range of the ids is the set of
1836  /// integers between 0 and \c n-1, where \c n is the number of the items of
1837  /// this type (e.g. nodes) (so the id of a node can change if you delete an
1838  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
1839  /// with its member class \c InverseMap.
1840  ///
1841  /// \param _Graph The graph class the \c DescriptorMap belongs to.
1842  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
1843  /// UEdge.
1844  template <typename _Graph, typename _Item>
1845  class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1846
1847    typedef _Item Item;
1848    typedef DefaultMap<_Graph, _Item, int> Map;
1849
1850  public:
1851    /// The graph class of DescriptorMap.
1852    typedef _Graph Graph;
1853
1854    /// The key type of DescriptorMap (Node, Edge, UEdge).
1855    typedef typename Map::Key Key;
1856    /// The value type of DescriptorMap.
1857    typedef typename Map::Value Value;
1858
1859    /// \brief Constructor.
1860    ///
1861    /// Constructor for descriptor map.
1862    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1863      Item it;
1864      const typename Map::Notifier* notifier = Map::getNotifier();
1865      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1866        Map::set(it, invMap.size());
1867        invMap.push_back(it);   
1868      }     
1869    }
1870
1871  protected:
1872
1873    /// \brief Add a new key to the map.
1874    ///
1875    /// Add a new key to the map. It is called by the
1876    /// \c AlterationNotifier.
1877    virtual void add(const Item& item) {
1878      Map::add(item);
1879      Map::set(item, invMap.size());
1880      invMap.push_back(item);
1881    }
1882
1883    /// \brief Add more new keys to the map.
1884    ///
1885    /// Add more new keys to the map. It is called by the
1886    /// \c AlterationNotifier.
1887    virtual void add(const std::vector<Item>& items) {
1888      Map::add(items);
1889      for (int i = 0; i < (int)items.size(); ++i) {
1890        Map::set(items[i], invMap.size());
1891        invMap.push_back(items[i]);
1892      }
1893    }
1894
1895    /// \brief Erase the key from the map.
1896    ///
1897    /// Erase the key from the map. It is called by the
1898    /// \c AlterationNotifier.
1899    virtual void erase(const Item& item) {
1900      Map::set(invMap.back(), Map::operator[](item));
1901      invMap[Map::operator[](item)] = invMap.back();
1902      invMap.pop_back();
1903      Map::erase(item);
1904    }
1905
1906    /// \brief Erase more keys from the map.
1907    ///
1908    /// Erase more keys from the map. It is called by the
1909    /// \c AlterationNotifier.
1910    virtual void erase(const std::vector<Item>& items) {
1911      for (int i = 0; i < (int)items.size(); ++i) {
1912        Map::set(invMap.back(), Map::operator[](items[i]));
1913        invMap[Map::operator[](items[i])] = invMap.back();
1914        invMap.pop_back();
1915      }
1916      Map::erase(items);
1917    }
1918
1919    /// \brief Build the unique map.
1920    ///
1921    /// Build the unique map. It is called by the
1922    /// \c AlterationNotifier.
1923    virtual void build() {
1924      Map::build();
1925      Item it;
1926      const typename Map::Notifier* notifier = Map::getNotifier();
1927      for (notifier->first(it); it != INVALID; notifier->next(it)) {
1928        Map::set(it, invMap.size());
1929        invMap.push_back(it);   
1930      }     
1931    }
1932   
1933    /// \brief Clear the keys from the map.
1934    ///
1935    /// Clear the keys from the map. It is called by the
1936    /// \c AlterationNotifier.
1937    virtual void clear() {
1938      invMap.clear();
1939      Map::clear();
1940    }
1941
1942  public:
1943
1944    /// \brief Returns the maximal value plus one.
1945    ///
1946    /// Returns the maximal value plus one in the map.
1947    unsigned int size() const {
1948      return invMap.size();
1949    }
1950
1951    /// \brief Swaps the position of the two items in the map.
1952    ///
1953    /// Swaps the position of the two items in the map.
1954    void swap(const Item& p, const Item& q) {
1955      int pi = Map::operator[](p);
1956      int qi = Map::operator[](q);
1957      Map::set(p, qi);
1958      invMap[qi] = p;
1959      Map::set(q, pi);
1960      invMap[pi] = q;
1961    }
1962
1963    /// \brief Gives back the \e descriptor of the item.
1964    ///
1965    /// Gives back the mutable and unique \e descriptor of the map.
1966    int operator[](const Item& item) const {
1967      return Map::operator[](item);
1968    }
1969   
1970  private:
1971
1972    typedef std::vector<Item> Container;
1973    Container invMap;
1974
1975  public:
1976    /// \brief The inverse map type of DescriptorMap.
1977    ///
1978    /// The inverse map type of DescriptorMap.
1979    class InverseMap {
1980    public:
1981      /// \brief Constructor of the InverseMap.
1982      ///
1983      /// Constructor of the InverseMap.
1984      explicit InverseMap(const DescriptorMap& _inverted)
1985        : inverted(_inverted) {}
1986
1987
1988      /// The value type of the InverseMap.
1989      typedef typename DescriptorMap::Key Value;
1990      /// The key type of the InverseMap.
1991      typedef typename DescriptorMap::Value Key;
1992
1993      /// \brief Subscript operator.
1994      ///
1995      /// Subscript operator. It gives back the item
1996      /// that the descriptor belongs to currently.
1997      Value operator[](const Key& key) const {
1998        return inverted.invMap[key];
1999      }
2000
2001      /// \brief Size of the map.
2002      ///
2003      /// Returns the size of the map.
2004      unsigned int size() const {
2005        return inverted.invMap.size();
2006      }
2007     
2008    private:
2009      const DescriptorMap& inverted;
2010    };
2011
2012    /// \brief Gives back the inverse of the map.
2013    ///
2014    /// Gives back the inverse of the map.
2015    const InverseMap inverse() const {
2016      return InverseMap(*this);
2017    }
2018  };
2019
2020  /// \brief Returns the source of the given edge.
2021  ///
2022  /// The SourceMap gives back the source Node of the given edge.
2023  /// \author Balazs Dezso
2024  template <typename Graph>
2025  class SourceMap {
2026  public:
2027
2028    typedef typename Graph::Node Value;
2029    typedef typename Graph::Edge Key;
2030
2031    /// \brief Constructor
2032    ///
2033    /// Constructor
2034    /// \param _graph The graph that the map belongs to.
2035    explicit SourceMap(const Graph& _graph) : graph(_graph) {}
2036
2037    /// \brief The subscript operator.
2038    ///
2039    /// The subscript operator.
2040    /// \param edge The edge
2041    /// \return The source of the edge
2042    Value operator[](const Key& edge) const {
2043      return graph.source(edge);
2044    }
2045
2046  private:
2047    const Graph& graph;
2048  };
2049
2050  /// \brief Returns a \ref SourceMap class
2051  ///
2052  /// This function just returns an \ref SourceMap class.
2053  /// \relates SourceMap
2054  template <typename Graph>
2055  inline SourceMap<Graph> sourceMap(const Graph& graph) {
2056    return SourceMap<Graph>(graph);
2057  }
2058
2059  /// \brief Returns the target of the given edge.
2060  ///
2061  /// The TargetMap gives back the target Node of the given edge.
2062  /// \author Balazs Dezso
2063  template <typename Graph>
2064  class TargetMap {
2065  public:
2066
2067    typedef typename Graph::Node Value;
2068    typedef typename Graph::Edge Key;
2069
2070    /// \brief Constructor
2071    ///
2072    /// Constructor
2073    /// \param _graph The graph that the map belongs to.
2074    explicit TargetMap(const Graph& _graph) : graph(_graph) {}
2075
2076    /// \brief The subscript operator.
2077    ///
2078    /// The subscript operator.
2079    /// \param e The edge
2080    /// \return The target of the edge
2081    Value operator[](const Key& e) const {
2082      return graph.target(e);
2083    }
2084
2085  private:
2086    const Graph& graph;
2087  };
2088
2089  /// \brief Returns a \ref TargetMap class
2090  ///
2091  /// This function just returns a \ref TargetMap class.
2092  /// \relates TargetMap
2093  template <typename Graph>
2094  inline TargetMap<Graph> targetMap(const Graph& graph) {
2095    return TargetMap<Graph>(graph);
2096  }
2097
2098  /// \brief Returns the "forward" directed edge view of an undirected edge.
2099  ///
2100  /// Returns the "forward" directed edge view of an undirected edge.
2101  /// \author Balazs Dezso
2102  template <typename Graph>
2103  class ForwardMap {
2104  public:
2105
2106    typedef typename Graph::Edge Value;
2107    typedef typename Graph::UEdge Key;
2108
2109    /// \brief Constructor
2110    ///
2111    /// Constructor
2112    /// \param _graph The graph that the map belongs to.
2113    explicit ForwardMap(const Graph& _graph) : graph(_graph) {}
2114
2115    /// \brief The subscript operator.
2116    ///
2117    /// The subscript operator.
2118    /// \param key An undirected edge
2119    /// \return The "forward" directed edge view of undirected edge
2120    Value operator[](const Key& key) const {
2121      return graph.direct(key, true);
2122    }
2123
2124  private:
2125    const Graph& graph;
2126  };
2127
2128  /// \brief Returns a \ref ForwardMap class
2129  ///
2130  /// This function just returns an \ref ForwardMap class.
2131  /// \relates ForwardMap
2132  template <typename Graph>
2133  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2134    return ForwardMap<Graph>(graph);
2135  }
2136
2137  /// \brief Returns the "backward" directed edge view of an undirected edge.
2138  ///
2139  /// Returns the "backward" directed edge view of an undirected edge.
2140  /// \author Balazs Dezso
2141  template <typename Graph>
2142  class BackwardMap {
2143  public:
2144
2145    typedef typename Graph::Edge Value;
2146    typedef typename Graph::UEdge Key;
2147
2148    /// \brief Constructor
2149    ///
2150    /// Constructor
2151    /// \param _graph The graph that the map belongs to.
2152    explicit BackwardMap(const Graph& _graph) : graph(_graph) {}
2153
2154    /// \brief The subscript operator.
2155    ///
2156    /// The subscript operator.
2157    /// \param key An undirected edge
2158    /// \return The "backward" directed edge view of undirected edge
2159    Value operator[](const Key& key) const {
2160      return graph.direct(key, false);
2161    }
2162
2163  private:
2164    const Graph& graph;
2165  };
2166
2167  /// \brief Returns a \ref BackwardMap class
2168
2169  /// This function just returns a \ref BackwardMap class.
2170  /// \relates BackwardMap
2171  template <typename Graph>
2172  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2173    return BackwardMap<Graph>(graph);
2174  }
2175
2176  /// \brief Potential difference map
2177  ///
2178  /// If there is an potential map on the nodes then we
2179  /// can get an edge map as we get the substraction of the
2180  /// values of the target and source.
2181  template <typename Graph, typename NodeMap>
2182  class PotentialDifferenceMap {
2183  public:
2184    typedef typename Graph::Edge Key;
2185    typedef typename NodeMap::Value Value;
2186
2187    /// \brief Constructor
2188    ///
2189    /// Contructor of the map
2190    explicit PotentialDifferenceMap(const Graph& _graph,
2191                                    const NodeMap& _potential)
2192      : graph(_graph), potential(_potential) {}
2193
2194    /// \brief Const subscription operator
2195    ///
2196    /// Const subscription operator
2197    Value operator[](const Key& edge) const {
2198      return potential[graph.target(edge)] - potential[graph.source(edge)];
2199    }
2200
2201  private:
2202    const Graph& graph;
2203    const NodeMap& potential;
2204  };
2205
2206  /// \brief Just returns a PotentialDifferenceMap
2207  ///
2208  /// Just returns a PotentialDifferenceMap
2209  /// \relates PotentialDifferenceMap
2210  template <typename Graph, typename NodeMap>
2211  PotentialDifferenceMap<Graph, NodeMap>
2212  potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
2213    return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
2214  }
2215
2216  /// \brief Map of the node in-degrees.
2217  ///
2218  /// This map returns the in-degree of a node. Once it is constructed,
2219  /// the degrees are stored in a standard NodeMap, so each query is done
2220  /// in constant time. On the other hand, the values are updated automatically
2221  /// whenever the graph changes.
2222  ///
2223  /// \warning Besides addNode() and addEdge(), a graph structure may provide
2224  /// alternative ways to modify the graph. The correct behavior of InDegMap
2225  /// is not guarantied if these additional features are used. For example
2226  /// the functions \ref ListGraph::changeSource() "changeSource()",
2227  /// \ref ListGraph::changeTarget() "changeTarget()" and
2228  /// \ref ListGraph::reverseEdge() "reverseEdge()"
2229  /// of \ref ListGraph will \e not update the degree values correctly.
2230  ///
2231  /// \sa OutDegMap
2232
2233  template <typename _Graph>
2234  class InDegMap 
2235    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2236      ::ItemNotifier::ObserverBase {
2237
2238  public:
2239   
2240    typedef _Graph Graph;
2241    typedef int Value;
2242    typedef typename Graph::Node Key;
2243
2244    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2245    ::ItemNotifier::ObserverBase Parent;
2246
2247  private:
2248
2249    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
2250    public:
2251
2252      typedef DefaultMap<_Graph, Key, int> Parent;
2253      typedef typename Parent::Graph Graph;
2254
2255      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2256     
2257      virtual void add(const Key& key) {
2258        Parent::add(key);
2259        Parent::set(key, 0);
2260      }
2261
2262      virtual void add(const std::vector<Key>& keys) {
2263        Parent::add(keys);
2264        for (int i = 0; i < (int)keys.size(); ++i) {
2265          Parent::set(keys[i], 0);
2266        }
2267      }
2268    };
2269
2270  public:
2271
2272    /// \brief Constructor.
2273    ///
2274    /// Constructor for creating in-degree map.
2275    explicit InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
2276      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
2277     
2278      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2279        deg[it] = countInEdges(graph, it);
2280      }
2281    }
2282   
2283    /// Gives back the in-degree of a Node.
2284    int operator[](const Key& key) const {
2285      return deg[key];
2286    }
2287
2288  protected:
2289   
2290    typedef typename Graph::Edge Edge;
2291
2292    virtual void add(const Edge& edge) {
2293      ++deg[graph.target(edge)];
2294    }
2295
2296    virtual void add(const std::vector<Edge>& edges) {
2297      for (int i = 0; i < (int)edges.size(); ++i) {
2298        ++deg[graph.target(edges[i])];
2299      }
2300    }
2301
2302    virtual void erase(const Edge& edge) {
2303      --deg[graph.target(edge)];
2304    }
2305
2306    virtual void erase(const std::vector<Edge>& edges) {
2307      for (int i = 0; i < (int)edges.size(); ++i) {
2308        --deg[graph.target(edges[i])];
2309      }
2310    }
2311
2312    virtual void build() {
2313      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2314        deg[it] = countInEdges(graph, it);
2315      }     
2316    }
2317
2318    virtual void clear() {
2319      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2320        deg[it] = 0;
2321      }
2322    }
2323  private:
2324   
2325    const _Graph& graph;
2326    AutoNodeMap deg;
2327  };
2328
2329  /// \brief Map of the node out-degrees.
2330  ///
2331  /// This map returns the out-degree of a node. Once it is constructed,
2332  /// the degrees are stored in a standard NodeMap, so each query is done
2333  /// in constant time. On the other hand, the values are updated automatically
2334  /// whenever the graph changes.
2335  ///
2336  /// \warning Besides addNode() and addEdge(), a graph structure may provide
2337  /// alternative ways to modify the graph. The correct behavior of OutDegMap
2338  /// is not guarantied if these additional features are used. For example
2339  /// the functions \ref ListGraph::changeSource() "changeSource()",
2340  /// \ref ListGraph::changeTarget() "changeTarget()" and
2341  /// \ref ListGraph::reverseEdge() "reverseEdge()"
2342  /// of \ref ListGraph will \e not update the degree values correctly.
2343  ///
2344  /// \sa InDegMap
2345
2346  template <typename _Graph>
2347  class OutDegMap 
2348    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
2349      ::ItemNotifier::ObserverBase {
2350
2351  public:
2352
2353    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
2354    ::ItemNotifier::ObserverBase Parent;
2355   
2356    typedef _Graph Graph;
2357    typedef int Value;
2358    typedef typename Graph::Node Key;
2359
2360  private:
2361
2362    class AutoNodeMap : public DefaultMap<_Graph, Key, int> {
2363    public:
2364
2365      typedef DefaultMap<_Graph, Key, int> Parent;
2366      typedef typename Parent::Graph Graph;
2367
2368      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
2369     
2370      virtual void add(const Key& key) {
2371        Parent::add(key);
2372        Parent::set(key, 0);
2373      }
2374      virtual void add(const std::vector<Key>& keys) {
2375        Parent::add(keys);
2376        for (int i = 0; i < (int)keys.size(); ++i) {
2377          Parent::set(keys[i], 0);
2378        }
2379      }
2380    };
2381
2382  public:
2383
2384    /// \brief Constructor.
2385    ///
2386    /// Constructor for creating out-degree map.
2387    explicit OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
2388      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
2389     
2390      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2391        deg[it] = countOutEdges(graph, it);
2392      }
2393    }
2394
2395    /// Gives back the out-degree of a Node.
2396    int operator[](const Key& key) const {
2397      return deg[key];
2398    }
2399
2400  protected:
2401   
2402    typedef typename Graph::Edge Edge;
2403
2404    virtual void add(const Edge& edge) {
2405      ++deg[graph.source(edge)];
2406    }
2407
2408    virtual void add(const std::vector<Edge>& edges) {
2409      for (int i = 0; i < (int)edges.size(); ++i) {
2410        ++deg[graph.source(edges[i])];
2411      }
2412    }
2413
2414    virtual void erase(const Edge& edge) {
2415      --deg[graph.source(edge)];
2416    }
2417
2418    virtual void erase(const std::vector<Edge>& edges) {
2419      for (int i = 0; i < (int)edges.size(); ++i) {
2420        --deg[graph.source(edges[i])];
2421      }
2422    }
2423
2424    virtual void build() {
2425      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2426        deg[it] = countOutEdges(graph, it);
2427      }     
2428    }
2429
2430    virtual void clear() {
2431      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2432        deg[it] = 0;
2433      }
2434    }
2435  private:
2436   
2437    const _Graph& graph;
2438    AutoNodeMap deg;
2439  };
2440
2441
2442  ///Fast edge look up between given endpoints.
2443 
2444  ///\ingroup gutils
2445  ///Using this class, you can find an edge in a graph from a given
2446  ///source to a given target in time <em>O(log d)</em>,
2447  ///where <em>d</em> is the out-degree of the source node.
2448  ///
2449  ///It is not possible to find \e all parallel edges between two nodes.
2450  ///Use \ref AllEdgeLookUp for this purpose.
2451  ///
2452  ///\warning This class is static, so you should refresh() (or at least
2453  ///refresh(Node)) this data structure
2454  ///whenever the graph changes. This is a time consuming (superlinearly
2455  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2456  ///
2457  ///\param G The type of the underlying graph.
2458  ///
2459  ///\sa AllEdgeLookUp 
2460  template<class G>
2461  class EdgeLookUp
2462  {
2463  public:
2464    GRAPH_TYPEDEFS(typename G)
2465    typedef G Graph;
2466
2467  protected:
2468    const Graph &_g;
2469    typename Graph::template NodeMap<Edge> _head;
2470    typename Graph::template EdgeMap<Edge> _left;
2471    typename Graph::template EdgeMap<Edge> _right;
2472   
2473    class EdgeLess {
2474      const Graph &g;
2475    public:
2476      EdgeLess(const Graph &_g) : g(_g) {}
2477      bool operator()(Edge a,Edge b) const
2478      {
2479        return g.target(a)<g.target(b);
2480      }
2481    };
2482   
2483  public:
2484   
2485    ///Constructor
2486
2487    ///Constructor.
2488    ///
2489    ///It builds up the search database, which remains valid until the graph
2490    ///changes.
2491    EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
2492   
2493  private:
2494    Edge refresh_rec(std::vector<Edge> &v,int a,int b)
2495    {
2496      int m=(a+b)/2;
2497      Edge me=v[m];
2498      _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
2499      _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
2500      return me;
2501    }
2502  public:
2503    ///Refresh the data structure at a node.
2504
2505    ///Build up the search database of node \c n.
2506    ///
2507    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2508    ///the number of the outgoing edges of \c n.
2509    void refresh(Node n)
2510    {
2511      std::vector<Edge> v;
2512      for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
2513      if(v.size()) {
2514        std::sort(v.begin(),v.end(),EdgeLess(_g));
2515        _head[n]=refresh_rec(v,0,v.size()-1);
2516      }
2517      else _head[n]=INVALID;
2518    }
2519    ///Refresh the full data structure.
2520
2521    ///Build up the full search database. In fact, it simply calls
2522    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2523    ///
2524    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2525    ///the number of the edges of \c n and <em>D</em> is the maximum
2526    ///out-degree of the graph.
2527
2528    void refresh()
2529    {
2530      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
2531    }
2532   
2533    ///Find an edge between two nodes.
2534   
2535    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
2536    /// <em>d</em> is the number of outgoing edges of \c s.
2537    ///\param s The source node
2538    ///\param t The target node
2539    ///\return An edge from \c s to \c t if there exists,
2540    ///\ref INVALID otherwise.
2541    ///
2542    ///\warning If you change the graph, refresh() must be called before using
2543    ///this operator. If you change the outgoing edges of
2544    ///a single node \c n, then
2545    ///\ref refresh(Node) "refresh(n)" is enough.
2546    ///
2547    Edge operator()(Node s, Node t) const
2548    {
2549      Edge e;
2550      for(e=_head[s];
2551          e!=INVALID&&_g.target(e)!=t;
2552          e = t < _g.target(e)?_left[e]:_right[e]) ;
2553      return e;
2554    }
2555
2556  };
2557
2558  ///Fast look up of all edges between given endpoints.
2559 
2560  ///\ingroup gutils
2561  ///This class is the same as \ref EdgeLookUp, with the addition
2562  ///that it makes it possible to find all edges between given endpoints.
2563  ///
2564  ///\warning This class is static, so you should refresh() (or at least
2565  ///refresh(Node)) this data structure
2566  ///whenever the graph changes. This is a time consuming (superlinearly
2567  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
2568  ///
2569  ///\param G The type of the underlying graph.
2570  ///
2571  ///\sa EdgeLookUp 
2572  template<class G>
2573  class AllEdgeLookUp : public EdgeLookUp<G>
2574  {
2575    using EdgeLookUp<G>::_g;
2576    using EdgeLookUp<G>::_right;
2577    using EdgeLookUp<G>::_left;
2578    using EdgeLookUp<G>::_head;
2579
2580    GRAPH_TYPEDEFS(typename G)
2581    typedef G Graph;
2582   
2583    typename Graph::template EdgeMap<Edge> _next;
2584   
2585    Edge refreshNext(Edge head,Edge next=INVALID)
2586    {
2587      if(head==INVALID) return next;
2588      else {
2589        next=refreshNext(_right[head],next);
2590//      _next[head]=next;
2591        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
2592          ? next : INVALID;
2593        return refreshNext(_left[head],head);
2594      }
2595    }
2596   
2597    void refreshNext()
2598    {
2599      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
2600    }
2601   
2602  public:
2603    ///Constructor
2604
2605    ///Constructor.
2606    ///
2607    ///It builds up the search database, which remains valid until the graph
2608    ///changes.
2609    AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
2610
2611    ///Refresh the data structure at a node.
2612
2613    ///Build up the search database of node \c n.
2614    ///
2615    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
2616    ///the number of the outgoing edges of \c n.
2617   
2618    void refresh(Node n)
2619    {
2620      EdgeLookUp<G>::refresh(n);
2621      refreshNext(_head[n]);
2622    }
2623   
2624    ///Refresh the full data structure.
2625
2626    ///Build up the full search database. In fact, it simply calls
2627    ///\ref refresh(Node) "refresh(n)" for each node \c n.
2628    ///
2629    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
2630    ///the number of the edges of \c n and <em>D</em> is the maximum
2631    ///out-degree of the graph.
2632
2633    void refresh()
2634    {
2635      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
2636    }
2637   
2638    ///Find an edge between two nodes.
2639   
2640    ///Find an edge between two nodes.
2641    ///\param s The source node
2642    ///\param t The target node
2643    ///\param prev The previous edge between \c s and \c t. It it is INVALID or
2644    ///not given, the operator finds the first appropriate edge.
2645    ///\return An edge from \c s to \c t after \prev or
2646    ///\ref INVALID if there is no more.
2647    ///
2648    ///For example, you can count the number of edges from \c u to \c v in the
2649    ///following way.
2650    ///\code
2651    ///AllEdgeLookUp<ListGraph> ae(g);
2652    ///...
2653    ///int n=0;
2654    ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
2655    ///\endcode
2656    ///
2657    ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
2658    /// <em>d</em> is the number of outgoing edges of \c s. Then, the
2659    ///consecutive edges are found in constant time.
2660    ///
2661    ///\warning If you change the graph, refresh() must be called before using
2662    ///this operator. If you change the outgoing edges of
2663    ///a single node \c n, then
2664    ///\ref refresh(Node) "refresh(n)" is enough.
2665    ///
2666#ifdef DOXYGEN
2667    Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
2668#else
2669    using EdgeLookUp<G>::operator() ;
2670    Edge operator()(Node s, Node t, Edge prev) const
2671    {
2672      return prev==INVALID?(*this)(s,t):_next[prev];
2673    }
2674#endif
2675     
2676  };
2677
2678  /// @}
2679
2680} //END OF NAMESPACE LEMON
2681
2682#endif
Note: See TracBrowser for help on using the repository browser.