COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/graph_utils.h @ 140:356930927a71

Last change on this file since 140:356930927a71 was 140:356930927a71, checked in by Balazs Dezso <deba@…>, 12 years ago

New implementation of GRAPH_TYPEDEFS

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