COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/graph_utils.h @ 139:701c529ba737

Last change on this file since 139:701c529ba737 was 139:701c529ba737, checked in by Balazs Dezso <deba@…>, 16 years ago

Renamings in the graph_utils.h + graph_utils_test added

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