COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

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