COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/graph_utils.h @ 191:abc5b9d0c67e

Last change on this file since 191:abc5b9d0c67e was 169:5b507a86ad72, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Fix various rename bugs

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