COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/graph_utils.h @ 2530:f86f7e4eb2ba

Last change on this file since 2530:f86f7e4eb2ba was 2510:bb523a4758f7, checked in by Balazs Dezso, 16 years ago

removing semicolon ftom the end of GRAPH_TYPEDEFS

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