COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/core.h @ 893:bb871cb8ac06

Last change on this file since 893:bb871cb8ac06 was 893:bb871cb8ac06, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Bug fix in (di)graphCopy() (#371)

The target graph is cleared before adding nodes and arcs/edges.

File size: 58.5 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
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_CORE_H
20#define LEMON_CORE_H
21
22#include <vector>
23#include <algorithm>
24
25#include <lemon/config.h>
26#include <lemon/bits/enable_if.h>
27#include <lemon/bits/traits.h>
28#include <lemon/assert.h>
29
30///\file
31///\brief LEMON core utilities.
32///
33///This header file contains core utilities for LEMON.
34///It is automatically included by all graph types, therefore it usually
35///do not have to be included directly.
36
37namespace lemon {
38
39  /// \brief Dummy type to make it easier to create invalid iterators.
40  ///
41  /// Dummy type to make it easier to create invalid iterators.
42  /// See \ref INVALID for the usage.
43  struct Invalid {
44  public:
45    bool operator==(Invalid) { return true;  }
46    bool operator!=(Invalid) { return false; }
47    bool operator< (Invalid) { return false; }
48  };
49
50  /// \brief Invalid iterators.
51  ///
52  /// \ref Invalid is a global type that converts to each iterator
53  /// in such a way that the value of the target iterator will be invalid.
54#ifdef LEMON_ONLY_TEMPLATES
55  const Invalid INVALID = Invalid();
56#else
57  extern const Invalid INVALID;
58#endif
59
60  /// \addtogroup gutils
61  /// @{
62
63  ///Create convenience typedefs for the digraph types and iterators
64
65  ///This \c \#define creates convenient type definitions for the following
66  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
67  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
68  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
69  ///
70  ///\note If the graph type is a dependent type, ie. the graph type depend
71  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
72  ///macro.
73#define DIGRAPH_TYPEDEFS(Digraph)                                       \
74  typedef Digraph::Node Node;                                           \
75  typedef Digraph::NodeIt NodeIt;                                       \
76  typedef Digraph::Arc Arc;                                             \
77  typedef Digraph::ArcIt ArcIt;                                         \
78  typedef Digraph::InArcIt InArcIt;                                     \
79  typedef Digraph::OutArcIt OutArcIt;                                   \
80  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \
81  typedef Digraph::NodeMap<int> IntNodeMap;                             \
82  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \
83  typedef Digraph::ArcMap<bool> BoolArcMap;                             \
84  typedef Digraph::ArcMap<int> IntArcMap;                               \
85  typedef Digraph::ArcMap<double> DoubleArcMap
86
87  ///Create convenience typedefs for the digraph types and iterators
88
89  ///\see DIGRAPH_TYPEDEFS
90  ///
91  ///\note Use this macro, if the graph type is a dependent type,
92  ///ie. the graph type depend on a template parameter.
93#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph)                              \
94  typedef typename Digraph::Node Node;                                  \
95  typedef typename Digraph::NodeIt NodeIt;                              \
96  typedef typename Digraph::Arc Arc;                                    \
97  typedef typename Digraph::ArcIt ArcIt;                                \
98  typedef typename Digraph::InArcIt InArcIt;                            \
99  typedef typename Digraph::OutArcIt OutArcIt;                          \
100  typedef typename Digraph::template NodeMap<bool> BoolNodeMap;         \
101  typedef typename Digraph::template NodeMap<int> IntNodeMap;           \
102  typedef typename Digraph::template NodeMap<double> DoubleNodeMap;     \
103  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \
104  typedef typename Digraph::template ArcMap<int> IntArcMap;             \
105  typedef typename Digraph::template ArcMap<double> DoubleArcMap
106
107  ///Create convenience typedefs for the graph types and iterators
108
109  ///This \c \#define creates the same convenient type definitions as defined
110  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
111  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
112  ///\c DoubleEdgeMap.
113  ///
114  ///\note If the graph type is a dependent type, ie. the graph type depend
115  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
116  ///macro.
117#define GRAPH_TYPEDEFS(Graph)                                           \
118  DIGRAPH_TYPEDEFS(Graph);                                              \
119  typedef Graph::Edge Edge;                                             \
120  typedef Graph::EdgeIt EdgeIt;                                         \
121  typedef Graph::IncEdgeIt IncEdgeIt;                                   \
122  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \
123  typedef Graph::EdgeMap<int> IntEdgeMap;                               \
124  typedef Graph::EdgeMap<double> DoubleEdgeMap
125
126  ///Create convenience typedefs for the graph types and iterators
127
128  ///\see GRAPH_TYPEDEFS
129  ///
130  ///\note Use this macro, if the graph type is a dependent type,
131  ///ie. the graph type depend on a template parameter.
132#define TEMPLATE_GRAPH_TYPEDEFS(Graph)                                  \
133  TEMPLATE_DIGRAPH_TYPEDEFS(Graph);                                     \
134  typedef typename Graph::Edge Edge;                                    \
135  typedef typename Graph::EdgeIt EdgeIt;                                \
136  typedef typename Graph::IncEdgeIt IncEdgeIt;                          \
137  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \
138  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \
139  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
140
141  /// \brief Function to count the items in a graph.
142  ///
143  /// This function counts the items (nodes, arcs etc.) in a graph.
144  /// The complexity of the function is linear because
145  /// it iterates on all of the items.
146  template <typename Graph, typename Item>
147  inline int countItems(const Graph& g) {
148    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
149    int num = 0;
150    for (ItemIt it(g); it != INVALID; ++it) {
151      ++num;
152    }
153    return num;
154  }
155
156  // Node counting:
157
158  namespace _core_bits {
159
160    template <typename Graph, typename Enable = void>
161    struct CountNodesSelector {
162      static int count(const Graph &g) {
163        return countItems<Graph, typename Graph::Node>(g);
164      }
165    };
166
167    template <typename Graph>
168    struct CountNodesSelector<
169      Graph, typename
170      enable_if<typename Graph::NodeNumTag, void>::type>
171    {
172      static int count(const Graph &g) {
173        return g.nodeNum();
174      }
175    };
176  }
177
178  /// \brief Function to count the nodes in the graph.
179  ///
180  /// This function counts the nodes in the graph.
181  /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
182  /// graph structures it is specialized to run in <em>O</em>(1).
183  ///
184  /// \note If the graph contains a \c nodeNum() member function and a
185  /// \c NodeNumTag tag then this function calls directly the member
186  /// function to query the cardinality of the node set.
187  template <typename Graph>
188  inline int countNodes(const Graph& g) {
189    return _core_bits::CountNodesSelector<Graph>::count(g);
190  }
191
192  // Arc counting:
193
194  namespace _core_bits {
195
196    template <typename Graph, typename Enable = void>
197    struct CountArcsSelector {
198      static int count(const Graph &g) {
199        return countItems<Graph, typename Graph::Arc>(g);
200      }
201    };
202
203    template <typename Graph>
204    struct CountArcsSelector<
205      Graph,
206      typename enable_if<typename Graph::ArcNumTag, void>::type>
207    {
208      static int count(const Graph &g) {
209        return g.arcNum();
210      }
211    };
212  }
213
214  /// \brief Function to count the arcs in the graph.
215  ///
216  /// This function counts the arcs in the graph.
217  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
218  /// graph structures it is specialized to run in <em>O</em>(1).
219  ///
220  /// \note If the graph contains a \c arcNum() member function and a
221  /// \c ArcNumTag tag then this function calls directly the member
222  /// function to query the cardinality of the arc set.
223  template <typename Graph>
224  inline int countArcs(const Graph& g) {
225    return _core_bits::CountArcsSelector<Graph>::count(g);
226  }
227
228  // Edge counting:
229
230  namespace _core_bits {
231
232    template <typename Graph, typename Enable = void>
233    struct CountEdgesSelector {
234      static int count(const Graph &g) {
235        return countItems<Graph, typename Graph::Edge>(g);
236      }
237    };
238
239    template <typename Graph>
240    struct CountEdgesSelector<
241      Graph,
242      typename enable_if<typename Graph::EdgeNumTag, void>::type>
243    {
244      static int count(const Graph &g) {
245        return g.edgeNum();
246      }
247    };
248  }
249
250  /// \brief Function to count the edges in the graph.
251  ///
252  /// This function counts the edges in the graph.
253  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
254  /// graph structures it is specialized to run in <em>O</em>(1).
255  ///
256  /// \note If the graph contains a \c edgeNum() member function and a
257  /// \c EdgeNumTag tag then this function calls directly the member
258  /// function to query the cardinality of the edge set.
259  template <typename Graph>
260  inline int countEdges(const Graph& g) {
261    return _core_bits::CountEdgesSelector<Graph>::count(g);
262
263  }
264
265
266  template <typename Graph, typename DegIt>
267  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
268    int num = 0;
269    for (DegIt it(_g, _n); it != INVALID; ++it) {
270      ++num;
271    }
272    return num;
273  }
274
275  /// \brief Function to count the number of the out-arcs from node \c n.
276  ///
277  /// This function counts the number of the out-arcs from node \c n
278  /// in the graph \c g.
279  template <typename Graph>
280  inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) {
281    return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
282  }
283
284  /// \brief Function to count the number of the in-arcs to node \c n.
285  ///
286  /// This function counts the number of the in-arcs to node \c n
287  /// in the graph \c g.
288  template <typename Graph>
289  inline int countInArcs(const Graph& g,  const typename Graph::Node& n) {
290    return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
291  }
292
293  /// \brief Function to count the number of the inc-edges to node \c n.
294  ///
295  /// This function counts the number of the inc-edges to node \c n
296  /// in the undirected graph \c g.
297  template <typename Graph>
298  inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) {
299    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
300  }
301
302  namespace _core_bits {
303
304    template <typename Digraph, typename Item, typename RefMap>
305    class MapCopyBase {
306    public:
307      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
308
309      virtual ~MapCopyBase() {}
310    };
311
312    template <typename Digraph, typename Item, typename RefMap,
313              typename FromMap, typename ToMap>
314    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
315    public:
316
317      MapCopy(const FromMap& map, ToMap& tmap)
318        : _map(map), _tmap(tmap) {}
319
320      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
321        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
322        for (ItemIt it(digraph); it != INVALID; ++it) {
323          _tmap.set(refMap[it], _map[it]);
324        }
325      }
326
327    private:
328      const FromMap& _map;
329      ToMap& _tmap;
330    };
331
332    template <typename Digraph, typename Item, typename RefMap, typename It>
333    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
334    public:
335
336      ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
337
338      virtual void copy(const Digraph&, const RefMap& refMap) {
339        _it = refMap[_item];
340      }
341
342    private:
343      Item _item;
344      It& _it;
345    };
346
347    template <typename Digraph, typename Item, typename RefMap, typename Ref>
348    class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
349    public:
350
351      RefCopy(Ref& map) : _map(map) {}
352
353      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
354        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
355        for (ItemIt it(digraph); it != INVALID; ++it) {
356          _map.set(it, refMap[it]);
357        }
358      }
359
360    private:
361      Ref& _map;
362    };
363
364    template <typename Digraph, typename Item, typename RefMap,
365              typename CrossRef>
366    class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
367    public:
368
369      CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
370
371      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
372        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
373        for (ItemIt it(digraph); it != INVALID; ++it) {
374          _cmap.set(refMap[it], it);
375        }
376      }
377
378    private:
379      CrossRef& _cmap;
380    };
381
382    template <typename Digraph, typename Enable = void>
383    struct DigraphCopySelector {
384      template <typename From, typename NodeRefMap, typename ArcRefMap>
385      static void copy(const From& from, Digraph &to,
386                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
387        to.clear();
388        for (typename From::NodeIt it(from); it != INVALID; ++it) {
389          nodeRefMap[it] = to.addNode();
390        }
391        for (typename From::ArcIt it(from); it != INVALID; ++it) {
392          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
393                                    nodeRefMap[from.target(it)]);
394        }
395      }
396    };
397
398    template <typename Digraph>
399    struct DigraphCopySelector<
400      Digraph,
401      typename enable_if<typename Digraph::BuildTag, void>::type>
402    {
403      template <typename From, typename NodeRefMap, typename ArcRefMap>
404      static void copy(const From& from, Digraph &to,
405                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
406        to.build(from, nodeRefMap, arcRefMap);
407      }
408    };
409
410    template <typename Graph, typename Enable = void>
411    struct GraphCopySelector {
412      template <typename From, typename NodeRefMap, typename EdgeRefMap>
413      static void copy(const From& from, Graph &to,
414                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
415        to.clear();
416        for (typename From::NodeIt it(from); it != INVALID; ++it) {
417          nodeRefMap[it] = to.addNode();
418        }
419        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
420          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
421                                      nodeRefMap[from.v(it)]);
422        }
423      }
424    };
425
426    template <typename Graph>
427    struct GraphCopySelector<
428      Graph,
429      typename enable_if<typename Graph::BuildTag, void>::type>
430    {
431      template <typename From, typename NodeRefMap, typename EdgeRefMap>
432      static void copy(const From& from, Graph &to,
433                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
434        to.build(from, nodeRefMap, edgeRefMap);
435      }
436    };
437
438  }
439
440  /// \brief Class to copy a digraph.
441  ///
442  /// Class to copy a digraph to another digraph (duplicate a digraph). The
443  /// simplest way of using it is through the \c digraphCopy() function.
444  ///
445  /// This class not only make a copy of a digraph, but it can create
446  /// references and cross references between the nodes and arcs of
447  /// the two digraphs, and it can copy maps to use with the newly created
448  /// digraph.
449  ///
450  /// To make a copy from a digraph, first an instance of DigraphCopy
451  /// should be created, then the data belongs to the digraph should
452  /// assigned to copy. In the end, the \c run() member should be
453  /// called.
454  ///
455  /// The next code copies a digraph with several data:
456  ///\code
457  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
458  ///  // Create references for the nodes
459  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
460  ///  cg.nodeRef(nr);
461  ///  // Create cross references (inverse) for the arcs
462  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
463  ///  cg.arcCrossRef(acr);
464  ///  // Copy an arc map
465  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
466  ///  NewGraph::ArcMap<double> namap(new_graph);
467  ///  cg.arcMap(oamap, namap);
468  ///  // Copy a node
469  ///  OrigGraph::Node on;
470  ///  NewGraph::Node nn;
471  ///  cg.node(on, nn);
472  ///  // Execute copying
473  ///  cg.run();
474  ///\endcode
475  template <typename From, typename To>
476  class DigraphCopy {
477  private:
478
479    typedef typename From::Node Node;
480    typedef typename From::NodeIt NodeIt;
481    typedef typename From::Arc Arc;
482    typedef typename From::ArcIt ArcIt;
483
484    typedef typename To::Node TNode;
485    typedef typename To::Arc TArc;
486
487    typedef typename From::template NodeMap<TNode> NodeRefMap;
488    typedef typename From::template ArcMap<TArc> ArcRefMap;
489
490  public:
491
492    /// \brief Constructor of DigraphCopy.
493    ///
494    /// Constructor of DigraphCopy for copying the content of the
495    /// \c from digraph into the \c to digraph.
496    DigraphCopy(const From& from, To& to)
497      : _from(from), _to(to) {}
498
499    /// \brief Destructor of DigraphCopy
500    ///
501    /// Destructor of DigraphCopy.
502    ~DigraphCopy() {
503      for (int i = 0; i < int(_node_maps.size()); ++i) {
504        delete _node_maps[i];
505      }
506      for (int i = 0; i < int(_arc_maps.size()); ++i) {
507        delete _arc_maps[i];
508      }
509
510    }
511
512    /// \brief Copy the node references into the given map.
513    ///
514    /// This function copies the node references into the given map.
515    /// The parameter should be a map, whose key type is the Node type of
516    /// the source digraph, while the value type is the Node type of the
517    /// destination digraph.
518    template <typename NodeRef>
519    DigraphCopy& nodeRef(NodeRef& map) {
520      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
521                           NodeRefMap, NodeRef>(map));
522      return *this;
523    }
524
525    /// \brief Copy the node cross references into the given map.
526    ///
527    /// This function copies the node cross references (reverse references)
528    /// into the given map. The parameter should be a map, whose key type
529    /// is the Node type of the destination digraph, while the value type is
530    /// the Node type of the source digraph.
531    template <typename NodeCrossRef>
532    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
533      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
534                           NodeRefMap, NodeCrossRef>(map));
535      return *this;
536    }
537
538    /// \brief Make a copy of the given node map.
539    ///
540    /// This function makes a copy of the given node map for the newly
541    /// created digraph.
542    /// The key type of the new map \c tmap should be the Node type of the
543    /// destination digraph, and the key type of the original map \c map
544    /// should be the Node type of the source digraph.
545    template <typename FromMap, typename ToMap>
546    DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
547      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
548                           NodeRefMap, FromMap, ToMap>(map, tmap));
549      return *this;
550    }
551
552    /// \brief Make a copy of the given node.
553    ///
554    /// This function makes a copy of the given node.
555    DigraphCopy& node(const Node& node, TNode& tnode) {
556      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
557                           NodeRefMap, TNode>(node, tnode));
558      return *this;
559    }
560
561    /// \brief Copy the arc references into the given map.
562    ///
563    /// This function copies the arc references into the given map.
564    /// The parameter should be a map, whose key type is the Arc type of
565    /// the source digraph, while the value type is the Arc type of the
566    /// destination digraph.
567    template <typename ArcRef>
568    DigraphCopy& arcRef(ArcRef& map) {
569      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
570                          ArcRefMap, ArcRef>(map));
571      return *this;
572    }
573
574    /// \brief Copy the arc cross references into the given map.
575    ///
576    /// This function copies the arc cross references (reverse references)
577    /// into the given map. The parameter should be a map, whose key type
578    /// is the Arc type of the destination digraph, while the value type is
579    /// the Arc type of the source digraph.
580    template <typename ArcCrossRef>
581    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
582      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
583                          ArcRefMap, ArcCrossRef>(map));
584      return *this;
585    }
586
587    /// \brief Make a copy of the given arc map.
588    ///
589    /// This function makes a copy of the given arc map for the newly
590    /// created digraph.
591    /// The key type of the new map \c tmap should be the Arc type of the
592    /// destination digraph, and the key type of the original map \c map
593    /// should be the Arc type of the source digraph.
594    template <typename FromMap, typename ToMap>
595    DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
596      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
597                          ArcRefMap, FromMap, ToMap>(map, tmap));
598      return *this;
599    }
600
601    /// \brief Make a copy of the given arc.
602    ///
603    /// This function makes a copy of the given arc.
604    DigraphCopy& arc(const Arc& arc, TArc& tarc) {
605      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
606                          ArcRefMap, TArc>(arc, tarc));
607      return *this;
608    }
609
610    /// \brief Execute copying.
611    ///
612    /// This function executes the copying of the digraph along with the
613    /// copying of the assigned data.
614    void run() {
615      NodeRefMap nodeRefMap(_from);
616      ArcRefMap arcRefMap(_from);
617      _core_bits::DigraphCopySelector<To>::
618        copy(_from, _to, nodeRefMap, arcRefMap);
619      for (int i = 0; i < int(_node_maps.size()); ++i) {
620        _node_maps[i]->copy(_from, nodeRefMap);
621      }
622      for (int i = 0; i < int(_arc_maps.size()); ++i) {
623        _arc_maps[i]->copy(_from, arcRefMap);
624      }
625    }
626
627  protected:
628
629    const From& _from;
630    To& _to;
631
632    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
633      _node_maps;
634
635    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
636      _arc_maps;
637
638  };
639
640  /// \brief Copy a digraph to another digraph.
641  ///
642  /// This function copies a digraph to another digraph.
643  /// The complete usage of it is detailed in the DigraphCopy class, but
644  /// a short example shows a basic work:
645  ///\code
646  /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
647  ///\endcode
648  ///
649  /// After the copy the \c nr map will contain the mapping from the
650  /// nodes of the \c from digraph to the nodes of the \c to digraph and
651  /// \c acr will contain the mapping from the arcs of the \c to digraph
652  /// to the arcs of the \c from digraph.
653  ///
654  /// \see DigraphCopy
655  template <typename From, typename To>
656  DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
657    return DigraphCopy<From, To>(from, to);
658  }
659
660  /// \brief Class to copy a graph.
661  ///
662  /// Class to copy a graph to another graph (duplicate a graph). The
663  /// simplest way of using it is through the \c graphCopy() function.
664  ///
665  /// This class not only make a copy of a graph, but it can create
666  /// references and cross references between the nodes, edges and arcs of
667  /// the two graphs, and it can copy maps for using with the newly created
668  /// graph.
669  ///
670  /// To make a copy from a graph, first an instance of GraphCopy
671  /// should be created, then the data belongs to the graph should
672  /// assigned to copy. In the end, the \c run() member should be
673  /// called.
674  ///
675  /// The next code copies a graph with several data:
676  ///\code
677  ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
678  ///  // Create references for the nodes
679  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
680  ///  cg.nodeRef(nr);
681  ///  // Create cross references (inverse) for the edges
682  ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
683  ///  cg.edgeCrossRef(ecr);
684  ///  // Copy an edge map
685  ///  OrigGraph::EdgeMap<double> oemap(orig_graph);
686  ///  NewGraph::EdgeMap<double> nemap(new_graph);
687  ///  cg.edgeMap(oemap, nemap);
688  ///  // Copy a node
689  ///  OrigGraph::Node on;
690  ///  NewGraph::Node nn;
691  ///  cg.node(on, nn);
692  ///  // Execute copying
693  ///  cg.run();
694  ///\endcode
695  template <typename From, typename To>
696  class GraphCopy {
697  private:
698
699    typedef typename From::Node Node;
700    typedef typename From::NodeIt NodeIt;
701    typedef typename From::Arc Arc;
702    typedef typename From::ArcIt ArcIt;
703    typedef typename From::Edge Edge;
704    typedef typename From::EdgeIt EdgeIt;
705
706    typedef typename To::Node TNode;
707    typedef typename To::Arc TArc;
708    typedef typename To::Edge TEdge;
709
710    typedef typename From::template NodeMap<TNode> NodeRefMap;
711    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
712
713    struct ArcRefMap {
714      ArcRefMap(const From& from, const To& to,
715                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
716        : _from(from), _to(to),
717          _edge_ref(edge_ref), _node_ref(node_ref) {}
718
719      typedef typename From::Arc Key;
720      typedef typename To::Arc Value;
721
722      Value operator[](const Key& key) const {
723        bool forward = _from.u(key) != _from.v(key) ?
724          _node_ref[_from.source(key)] ==
725          _to.source(_to.direct(_edge_ref[key], true)) :
726          _from.direction(key);
727        return _to.direct(_edge_ref[key], forward);
728      }
729
730      const From& _from;
731      const To& _to;
732      const EdgeRefMap& _edge_ref;
733      const NodeRefMap& _node_ref;
734    };
735
736  public:
737
738    /// \brief Constructor of GraphCopy.
739    ///
740    /// Constructor of GraphCopy for copying the content of the
741    /// \c from graph into the \c to graph.
742    GraphCopy(const From& from, To& to)
743      : _from(from), _to(to) {}
744
745    /// \brief Destructor of GraphCopy
746    ///
747    /// Destructor of GraphCopy.
748    ~GraphCopy() {
749      for (int i = 0; i < int(_node_maps.size()); ++i) {
750        delete _node_maps[i];
751      }
752      for (int i = 0; i < int(_arc_maps.size()); ++i) {
753        delete _arc_maps[i];
754      }
755      for (int i = 0; i < int(_edge_maps.size()); ++i) {
756        delete _edge_maps[i];
757      }
758    }
759
760    /// \brief Copy the node references into the given map.
761    ///
762    /// This function copies the node references into the given map.
763    /// The parameter should be a map, whose key type is the Node type of
764    /// the source graph, while the value type is the Node type of the
765    /// destination graph.
766    template <typename NodeRef>
767    GraphCopy& nodeRef(NodeRef& map) {
768      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
769                           NodeRefMap, NodeRef>(map));
770      return *this;
771    }
772
773    /// \brief Copy the node cross references into the given map.
774    ///
775    /// This function copies the node cross references (reverse references)
776    /// into the given map. The parameter should be a map, whose key type
777    /// is the Node type of the destination graph, while the value type is
778    /// the Node type of the source graph.
779    template <typename NodeCrossRef>
780    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
781      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
782                           NodeRefMap, NodeCrossRef>(map));
783      return *this;
784    }
785
786    /// \brief Make a copy of the given node map.
787    ///
788    /// This function makes a copy of the given node map for the newly
789    /// created graph.
790    /// The key type of the new map \c tmap should be the Node type of the
791    /// destination graph, and the key type of the original map \c map
792    /// should be the Node type of the source graph.
793    template <typename FromMap, typename ToMap>
794    GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
795      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
796                           NodeRefMap, FromMap, ToMap>(map, tmap));
797      return *this;
798    }
799
800    /// \brief Make a copy of the given node.
801    ///
802    /// This function makes a copy of the given node.
803    GraphCopy& node(const Node& node, TNode& tnode) {
804      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
805                           NodeRefMap, TNode>(node, tnode));
806      return *this;
807    }
808
809    /// \brief Copy the arc references into the given map.
810    ///
811    /// This function copies the arc references into the given map.
812    /// The parameter should be a map, whose key type is the Arc type of
813    /// the source graph, while the value type is the Arc type of the
814    /// destination graph.
815    template <typename ArcRef>
816    GraphCopy& arcRef(ArcRef& map) {
817      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
818                          ArcRefMap, ArcRef>(map));
819      return *this;
820    }
821
822    /// \brief Copy the arc cross references into the given map.
823    ///
824    /// This function copies the arc cross references (reverse references)
825    /// into the given map. The parameter should be a map, whose key type
826    /// is the Arc type of the destination graph, while the value type is
827    /// the Arc type of the source graph.
828    template <typename ArcCrossRef>
829    GraphCopy& arcCrossRef(ArcCrossRef& map) {
830      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
831                          ArcRefMap, ArcCrossRef>(map));
832      return *this;
833    }
834
835    /// \brief Make a copy of the given arc map.
836    ///
837    /// This function makes a copy of the given arc map for the newly
838    /// created graph.
839    /// The key type of the new map \c tmap should be the Arc type of the
840    /// destination graph, and the key type of the original map \c map
841    /// should be the Arc type of the source graph.
842    template <typename FromMap, typename ToMap>
843    GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
844      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
845                          ArcRefMap, FromMap, ToMap>(map, tmap));
846      return *this;
847    }
848
849    /// \brief Make a copy of the given arc.
850    ///
851    /// This function makes a copy of the given arc.
852    GraphCopy& arc(const Arc& arc, TArc& tarc) {
853      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
854                          ArcRefMap, TArc>(arc, tarc));
855      return *this;
856    }
857
858    /// \brief Copy the edge references into the given map.
859    ///
860    /// This function copies the edge references into the given map.
861    /// The parameter should be a map, whose key type is the Edge type of
862    /// the source graph, while the value type is the Edge type of the
863    /// destination graph.
864    template <typename EdgeRef>
865    GraphCopy& edgeRef(EdgeRef& map) {
866      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
867                           EdgeRefMap, EdgeRef>(map));
868      return *this;
869    }
870
871    /// \brief Copy the edge cross references into the given map.
872    ///
873    /// This function copies the edge cross references (reverse references)
874    /// into the given map. The parameter should be a map, whose key type
875    /// is the Edge type of the destination graph, while the value type is
876    /// the Edge type of the source graph.
877    template <typename EdgeCrossRef>
878    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
879      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
880                           Edge, EdgeRefMap, EdgeCrossRef>(map));
881      return *this;
882    }
883
884    /// \brief Make a copy of the given edge map.
885    ///
886    /// This function makes a copy of the given edge map for the newly
887    /// created graph.
888    /// The key type of the new map \c tmap should be the Edge type of the
889    /// destination graph, and the key type of the original map \c map
890    /// should be the Edge type of the source graph.
891    template <typename FromMap, typename ToMap>
892    GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
893      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
894                           EdgeRefMap, FromMap, ToMap>(map, tmap));
895      return *this;
896    }
897
898    /// \brief Make a copy of the given edge.
899    ///
900    /// This function makes a copy of the given edge.
901    GraphCopy& edge(const Edge& edge, TEdge& tedge) {
902      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
903                           EdgeRefMap, TEdge>(edge, tedge));
904      return *this;
905    }
906
907    /// \brief Execute copying.
908    ///
909    /// This function executes the copying of the graph along with the
910    /// copying of the assigned data.
911    void run() {
912      NodeRefMap nodeRefMap(_from);
913      EdgeRefMap edgeRefMap(_from);
914      ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
915      _core_bits::GraphCopySelector<To>::
916        copy(_from, _to, nodeRefMap, edgeRefMap);
917      for (int i = 0; i < int(_node_maps.size()); ++i) {
918        _node_maps[i]->copy(_from, nodeRefMap);
919      }
920      for (int i = 0; i < int(_edge_maps.size()); ++i) {
921        _edge_maps[i]->copy(_from, edgeRefMap);
922      }
923      for (int i = 0; i < int(_arc_maps.size()); ++i) {
924        _arc_maps[i]->copy(_from, arcRefMap);
925      }
926    }
927
928  private:
929
930    const From& _from;
931    To& _to;
932
933    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
934      _node_maps;
935
936    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
937      _arc_maps;
938
939    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
940      _edge_maps;
941
942  };
943
944  /// \brief Copy a graph to another graph.
945  ///
946  /// This function copies a graph to another graph.
947  /// The complete usage of it is detailed in the GraphCopy class,
948  /// but a short example shows a basic work:
949  ///\code
950  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
951  ///\endcode
952  ///
953  /// After the copy the \c nr map will contain the mapping from the
954  /// nodes of the \c from graph to the nodes of the \c to graph and
955  /// \c ecr will contain the mapping from the edges of the \c to graph
956  /// to the edges of the \c from graph.
957  ///
958  /// \see GraphCopy
959  template <typename From, typename To>
960  GraphCopy<From, To>
961  graphCopy(const From& from, To& to) {
962    return GraphCopy<From, To>(from, to);
963  }
964
965  namespace _core_bits {
966
967    template <typename Graph, typename Enable = void>
968    struct FindArcSelector {
969      typedef typename Graph::Node Node;
970      typedef typename Graph::Arc Arc;
971      static Arc find(const Graph &g, Node u, Node v, Arc e) {
972        if (e == INVALID) {
973          g.firstOut(e, u);
974        } else {
975          g.nextOut(e);
976        }
977        while (e != INVALID && g.target(e) != v) {
978          g.nextOut(e);
979        }
980        return e;
981      }
982    };
983
984    template <typename Graph>
985    struct FindArcSelector<
986      Graph,
987      typename enable_if<typename Graph::FindArcTag, void>::type>
988    {
989      typedef typename Graph::Node Node;
990      typedef typename Graph::Arc Arc;
991      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
992        return g.findArc(u, v, prev);
993      }
994    };
995  }
996
997  /// \brief Find an arc between two nodes of a digraph.
998  ///
999  /// This function finds an arc from node \c u to node \c v in the
1000  /// digraph \c g.
1001  ///
1002  /// If \c prev is \ref INVALID (this is the default value), then
1003  /// it finds the first arc from \c u to \c v. Otherwise it looks for
1004  /// the next arc from \c u to \c v after \c prev.
1005  /// \return The found arc or \ref INVALID if there is no such an arc.
1006  ///
1007  /// Thus you can iterate through each arc from \c u to \c v as it follows.
1008  ///\code
1009  /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1010  ///   ...
1011  /// }
1012  ///\endcode
1013  ///
1014  /// \note \ref ConArcIt provides iterator interface for the same
1015  /// functionality.
1016  ///
1017  ///\sa ConArcIt
1018  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1019  template <typename Graph>
1020  inline typename Graph::Arc
1021  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1022          typename Graph::Arc prev = INVALID) {
1023    return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1024  }
1025
1026  /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
1027  ///
1028  /// Iterator for iterating on parallel arcs connecting the same nodes. It is
1029  /// a higher level interface for the \ref findArc() function. You can
1030  /// use it the following way:
1031  ///\code
1032  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1033  ///   ...
1034  /// }
1035  ///\endcode
1036  ///
1037  ///\sa findArc()
1038  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1039  template <typename _Graph>
1040  class ConArcIt : public _Graph::Arc {
1041  public:
1042
1043    typedef _Graph Graph;
1044    typedef typename Graph::Arc Parent;
1045
1046    typedef typename Graph::Arc Arc;
1047    typedef typename Graph::Node Node;
1048
1049    /// \brief Constructor.
1050    ///
1051    /// Construct a new ConArcIt iterating on the arcs that
1052    /// connects nodes \c u and \c v.
1053    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1054      Parent::operator=(findArc(_graph, u, v));
1055    }
1056
1057    /// \brief Constructor.
1058    ///
1059    /// Construct a new ConArcIt that continues the iterating from arc \c a.
1060    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1061
1062    /// \brief Increment operator.
1063    ///
1064    /// It increments the iterator and gives back the next arc.
1065    ConArcIt& operator++() {
1066      Parent::operator=(findArc(_graph, _graph.source(*this),
1067                                _graph.target(*this), *this));
1068      return *this;
1069    }
1070  private:
1071    const Graph& _graph;
1072  };
1073
1074  namespace _core_bits {
1075
1076    template <typename Graph, typename Enable = void>
1077    struct FindEdgeSelector {
1078      typedef typename Graph::Node Node;
1079      typedef typename Graph::Edge Edge;
1080      static Edge find(const Graph &g, Node u, Node v, Edge e) {
1081        bool b;
1082        if (u != v) {
1083          if (e == INVALID) {
1084            g.firstInc(e, b, u);
1085          } else {
1086            b = g.u(e) == u;
1087            g.nextInc(e, b);
1088          }
1089          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1090            g.nextInc(e, b);
1091          }
1092        } else {
1093          if (e == INVALID) {
1094            g.firstInc(e, b, u);
1095          } else {
1096            b = true;
1097            g.nextInc(e, b);
1098          }
1099          while (e != INVALID && (!b || g.v(e) != v)) {
1100            g.nextInc(e, b);
1101          }
1102        }
1103        return e;
1104      }
1105    };
1106
1107    template <typename Graph>
1108    struct FindEdgeSelector<
1109      Graph,
1110      typename enable_if<typename Graph::FindEdgeTag, void>::type>
1111    {
1112      typedef typename Graph::Node Node;
1113      typedef typename Graph::Edge Edge;
1114      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1115        return g.findEdge(u, v, prev);
1116      }
1117    };
1118  }
1119
1120  /// \brief Find an edge between two nodes of a graph.
1121  ///
1122  /// This function finds an edge from node \c u to node \c v in graph \c g.
1123  /// If node \c u and node \c v is equal then each loop edge
1124  /// will be enumerated once.
1125  ///
1126  /// If \c prev is \ref INVALID (this is the default value), then
1127  /// it finds the first edge from \c u to \c v. Otherwise it looks for
1128  /// the next edge from \c u to \c v after \c prev.
1129  /// \return The found edge or \ref INVALID if there is no such an edge.
1130  ///
1131  /// Thus you can iterate through each edge between \c u and \c v
1132  /// as it follows.
1133  ///\code
1134  /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1135  ///   ...
1136  /// }
1137  ///\endcode
1138  ///
1139  /// \note \ref ConEdgeIt provides iterator interface for the same
1140  /// functionality.
1141  ///
1142  ///\sa ConEdgeIt
1143  template <typename Graph>
1144  inline typename Graph::Edge
1145  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1146            typename Graph::Edge p = INVALID) {
1147    return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1148  }
1149
1150  /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1151  ///
1152  /// Iterator for iterating on parallel edges connecting the same nodes.
1153  /// It is a higher level interface for the findEdge() function. You can
1154  /// use it the following way:
1155  ///\code
1156  /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1157  ///   ...
1158  /// }
1159  ///\endcode
1160  ///
1161  ///\sa findEdge()
1162  template <typename _Graph>
1163  class ConEdgeIt : public _Graph::Edge {
1164  public:
1165
1166    typedef _Graph Graph;
1167    typedef typename Graph::Edge Parent;
1168
1169    typedef typename Graph::Edge Edge;
1170    typedef typename Graph::Node Node;
1171
1172    /// \brief Constructor.
1173    ///
1174    /// Construct a new ConEdgeIt iterating on the edges that
1175    /// connects nodes \c u and \c v.
1176    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1177      Parent::operator=(findEdge(_graph, _u, _v));
1178    }
1179
1180    /// \brief Constructor.
1181    ///
1182    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1183    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1184
1185    /// \brief Increment operator.
1186    ///
1187    /// It increments the iterator and gives back the next edge.
1188    ConEdgeIt& operator++() {
1189      Parent::operator=(findEdge(_graph, _u, _v, *this));
1190      return *this;
1191    }
1192  private:
1193    const Graph& _graph;
1194    Node _u, _v;
1195  };
1196
1197
1198  ///Dynamic arc look-up between given endpoints.
1199
1200  ///Using this class, you can find an arc in a digraph from a given
1201  ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1202  ///where <em>d</em> is the out-degree of the source node.
1203  ///
1204  ///It is possible to find \e all parallel arcs between two nodes with
1205  ///the \c operator() member.
1206  ///
1207  ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1208  ///\ref AllArcLookUp if your digraph is not changed so frequently.
1209  ///
1210  ///This class uses a self-adjusting binary search tree, the Splay tree
1211  ///of Sleator and Tarjan to guarantee the logarithmic amortized
1212  ///time bound for arc look-ups. This class also guarantees the
1213  ///optimal time bound in a constant factor for any distribution of
1214  ///queries.
1215  ///
1216  ///\tparam G The type of the underlying digraph.
1217  ///
1218  ///\sa ArcLookUp
1219  ///\sa AllArcLookUp
1220  template<class G>
1221  class DynArcLookUp
1222    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
1223  {
1224  public:
1225    typedef typename ItemSetTraits<G, typename G::Arc>
1226    ::ItemNotifier::ObserverBase Parent;
1227
1228    TEMPLATE_DIGRAPH_TYPEDEFS(G);
1229    typedef G Digraph;
1230
1231  protected:
1232
1233    class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
1234    public:
1235
1236      typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
1237
1238      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
1239
1240      virtual void add(const Node& node) {
1241        Parent::add(node);
1242        Parent::set(node, INVALID);
1243      }
1244
1245      virtual void add(const std::vector<Node>& nodes) {
1246        Parent::add(nodes);
1247        for (int i = 0; i < int(nodes.size()); ++i) {
1248          Parent::set(nodes[i], INVALID);
1249        }
1250      }
1251
1252      virtual void build() {
1253        Parent::build();
1254        Node it;
1255        typename Parent::Notifier* nf = Parent::notifier();
1256        for (nf->first(it); it != INVALID; nf->next(it)) {
1257          Parent::set(it, INVALID);
1258        }
1259      }
1260    };
1261
1262    const Digraph &_g;
1263    AutoNodeMap _head;
1264    typename Digraph::template ArcMap<Arc> _parent;
1265    typename Digraph::template ArcMap<Arc> _left;
1266    typename Digraph::template ArcMap<Arc> _right;
1267
1268    class ArcLess {
1269      const Digraph &g;
1270    public:
1271      ArcLess(const Digraph &_g) : g(_g) {}
1272      bool operator()(Arc a,Arc b) const
1273      {
1274        return g.target(a)<g.target(b);
1275      }
1276    };
1277
1278  public:
1279
1280    ///Constructor
1281
1282    ///Constructor.
1283    ///
1284    ///It builds up the search database.
1285    DynArcLookUp(const Digraph &g)
1286      : _g(g),_head(g),_parent(g),_left(g),_right(g)
1287    {
1288      Parent::attach(_g.notifier(typename Digraph::Arc()));
1289      refresh();
1290    }
1291
1292  protected:
1293
1294    virtual void add(const Arc& arc) {
1295      insert(arc);
1296    }
1297
1298    virtual void add(const std::vector<Arc>& arcs) {
1299      for (int i = 0; i < int(arcs.size()); ++i) {
1300        insert(arcs[i]);
1301      }
1302    }
1303
1304    virtual void erase(const Arc& arc) {
1305      remove(arc);
1306    }
1307
1308    virtual void erase(const std::vector<Arc>& arcs) {
1309      for (int i = 0; i < int(arcs.size()); ++i) {
1310        remove(arcs[i]);
1311      }
1312    }
1313
1314    virtual void build() {
1315      refresh();
1316    }
1317
1318    virtual void clear() {
1319      for(NodeIt n(_g);n!=INVALID;++n) {
1320        _head.set(n, INVALID);
1321      }
1322    }
1323
1324    void insert(Arc arc) {
1325      Node s = _g.source(arc);
1326      Node t = _g.target(arc);
1327      _left.set(arc, INVALID);
1328      _right.set(arc, INVALID);
1329
1330      Arc e = _head[s];
1331      if (e == INVALID) {
1332        _head.set(s, arc);
1333        _parent.set(arc, INVALID);
1334        return;
1335      }
1336      while (true) {
1337        if (t < _g.target(e)) {
1338          if (_left[e] == INVALID) {
1339            _left.set(e, arc);
1340            _parent.set(arc, e);
1341            splay(arc);
1342            return;
1343          } else {
1344            e = _left[e];
1345          }
1346        } else {
1347          if (_right[e] == INVALID) {
1348            _right.set(e, arc);
1349            _parent.set(arc, e);
1350            splay(arc);
1351            return;
1352          } else {
1353            e = _right[e];
1354          }
1355        }
1356      }
1357    }
1358
1359    void remove(Arc arc) {
1360      if (_left[arc] == INVALID) {
1361        if (_right[arc] != INVALID) {
1362          _parent.set(_right[arc], _parent[arc]);
1363        }
1364        if (_parent[arc] != INVALID) {
1365          if (_left[_parent[arc]] == arc) {
1366            _left.set(_parent[arc], _right[arc]);
1367          } else {
1368            _right.set(_parent[arc], _right[arc]);
1369          }
1370        } else {
1371          _head.set(_g.source(arc), _right[arc]);
1372        }
1373      } else if (_right[arc] == INVALID) {
1374        _parent.set(_left[arc], _parent[arc]);
1375        if (_parent[arc] != INVALID) {
1376          if (_left[_parent[arc]] == arc) {
1377            _left.set(_parent[arc], _left[arc]);
1378          } else {
1379            _right.set(_parent[arc], _left[arc]);
1380          }
1381        } else {
1382          _head.set(_g.source(arc), _left[arc]);
1383        }
1384      } else {
1385        Arc e = _left[arc];
1386        if (_right[e] != INVALID) {
1387          e = _right[e];
1388          while (_right[e] != INVALID) {
1389            e = _right[e];
1390          }
1391          Arc s = _parent[e];
1392          _right.set(_parent[e], _left[e]);
1393          if (_left[e] != INVALID) {
1394            _parent.set(_left[e], _parent[e]);
1395          }
1396
1397          _left.set(e, _left[arc]);
1398          _parent.set(_left[arc], e);
1399          _right.set(e, _right[arc]);
1400          _parent.set(_right[arc], e);
1401
1402          _parent.set(e, _parent[arc]);
1403          if (_parent[arc] != INVALID) {
1404            if (_left[_parent[arc]] == arc) {
1405              _left.set(_parent[arc], e);
1406            } else {
1407              _right.set(_parent[arc], e);
1408            }
1409          }
1410          splay(s);
1411        } else {
1412          _right.set(e, _right[arc]);
1413          _parent.set(_right[arc], e);
1414          _parent.set(e, _parent[arc]);
1415
1416          if (_parent[arc] != INVALID) {
1417            if (_left[_parent[arc]] == arc) {
1418              _left.set(_parent[arc], e);
1419            } else {
1420              _right.set(_parent[arc], e);
1421            }
1422          } else {
1423            _head.set(_g.source(arc), e);
1424          }
1425        }
1426      }
1427    }
1428
1429    Arc refreshRec(std::vector<Arc> &v,int a,int b)
1430    {
1431      int m=(a+b)/2;
1432      Arc me=v[m];
1433      if (a < m) {
1434        Arc left = refreshRec(v,a,m-1);
1435        _left.set(me, left);
1436        _parent.set(left, me);
1437      } else {
1438        _left.set(me, INVALID);
1439      }
1440      if (m < b) {
1441        Arc right = refreshRec(v,m+1,b);
1442        _right.set(me, right);
1443        _parent.set(right, me);
1444      } else {
1445        _right.set(me, INVALID);
1446      }
1447      return me;
1448    }
1449
1450    void refresh() {
1451      for(NodeIt n(_g);n!=INVALID;++n) {
1452        std::vector<Arc> v;
1453        for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
1454        if (!v.empty()) {
1455          std::sort(v.begin(),v.end(),ArcLess(_g));
1456          Arc head = refreshRec(v,0,v.size()-1);
1457          _head.set(n, head);
1458          _parent.set(head, INVALID);
1459        }
1460        else _head.set(n, INVALID);
1461      }
1462    }
1463
1464    void zig(Arc v) {
1465      Arc w = _parent[v];
1466      _parent.set(v, _parent[w]);
1467      _parent.set(w, v);
1468      _left.set(w, _right[v]);
1469      _right.set(v, w);
1470      if (_parent[v] != INVALID) {
1471        if (_right[_parent[v]] == w) {
1472          _right.set(_parent[v], v);
1473        } else {
1474          _left.set(_parent[v], v);
1475        }
1476      }
1477      if (_left[w] != INVALID){
1478        _parent.set(_left[w], w);
1479      }
1480    }
1481
1482    void zag(Arc v) {
1483      Arc w = _parent[v];
1484      _parent.set(v, _parent[w]);
1485      _parent.set(w, v);
1486      _right.set(w, _left[v]);
1487      _left.set(v, w);
1488      if (_parent[v] != INVALID){
1489        if (_left[_parent[v]] == w) {
1490          _left.set(_parent[v], v);
1491        } else {
1492          _right.set(_parent[v], v);
1493        }
1494      }
1495      if (_right[w] != INVALID){
1496        _parent.set(_right[w], w);
1497      }
1498    }
1499
1500    void splay(Arc v) {
1501      while (_parent[v] != INVALID) {
1502        if (v == _left[_parent[v]]) {
1503          if (_parent[_parent[v]] == INVALID) {
1504            zig(v);
1505          } else {
1506            if (_parent[v] == _left[_parent[_parent[v]]]) {
1507              zig(_parent[v]);
1508              zig(v);
1509            } else {
1510              zig(v);
1511              zag(v);
1512            }
1513          }
1514        } else {
1515          if (_parent[_parent[v]] == INVALID) {
1516            zag(v);
1517          } else {
1518            if (_parent[v] == _left[_parent[_parent[v]]]) {
1519              zag(v);
1520              zig(v);
1521            } else {
1522              zag(_parent[v]);
1523              zag(v);
1524            }
1525          }
1526        }
1527      }
1528      _head[_g.source(v)] = v;
1529    }
1530
1531
1532  public:
1533
1534    ///Find an arc between two nodes.
1535
1536    ///Find an arc between two nodes.
1537    ///\param s The source node.
1538    ///\param t The target node.
1539    ///\param p The previous arc between \c s and \c t. It it is INVALID or
1540    ///not given, the operator finds the first appropriate arc.
1541    ///\return An arc from \c s to \c t after \c p or
1542    ///\ref INVALID if there is no more.
1543    ///
1544    ///For example, you can count the number of arcs from \c u to \c v in the
1545    ///following way.
1546    ///\code
1547    ///DynArcLookUp<ListDigraph> ae(g);
1548    ///...
1549    ///int n = 0;
1550    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
1551    ///\endcode
1552    ///
1553    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
1554    ///amortized time, specifically, the time complexity of the lookups
1555    ///is equal to the optimal search tree implementation for the
1556    ///current query distribution in a constant factor.
1557    ///
1558    ///\note This is a dynamic data structure, therefore the data
1559    ///structure is updated after each graph alteration. Thus although
1560    ///this data structure is theoretically faster than \ref ArcLookUp
1561    ///and \ref AllArcLookUp, it often provides worse performance than
1562    ///them.
1563    Arc operator()(Node s, Node t, Arc p = INVALID) const  {
1564      if (p == INVALID) {
1565        Arc a = _head[s];
1566        if (a == INVALID) return INVALID;
1567        Arc r = INVALID;
1568        while (true) {
1569          if (_g.target(a) < t) {
1570            if (_right[a] == INVALID) {
1571              const_cast<DynArcLookUp&>(*this).splay(a);
1572              return r;
1573            } else {
1574              a = _right[a];
1575            }
1576          } else {
1577            if (_g.target(a) == t) {
1578              r = a;
1579            }
1580            if (_left[a] == INVALID) {
1581              const_cast<DynArcLookUp&>(*this).splay(a);
1582              return r;
1583            } else {
1584              a = _left[a];
1585            }
1586          }
1587        }
1588      } else {
1589        Arc a = p;
1590        if (_right[a] != INVALID) {
1591          a = _right[a];
1592          while (_left[a] != INVALID) {
1593            a = _left[a];
1594          }
1595          const_cast<DynArcLookUp&>(*this).splay(a);
1596        } else {
1597          while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
1598            a = _parent[a];
1599          }
1600          if (_parent[a] == INVALID) {
1601            return INVALID;
1602          } else {
1603            a = _parent[a];
1604            const_cast<DynArcLookUp&>(*this).splay(a);
1605          }
1606        }
1607        if (_g.target(a) == t) return a;
1608        else return INVALID;
1609      }
1610    }
1611
1612  };
1613
1614  ///Fast arc look-up between given endpoints.
1615
1616  ///Using this class, you can find an arc in a digraph from a given
1617  ///source to a given target in time <em>O</em>(log<em>d</em>),
1618  ///where <em>d</em> is the out-degree of the source node.
1619  ///
1620  ///It is not possible to find \e all parallel arcs between two nodes.
1621  ///Use \ref AllArcLookUp for this purpose.
1622  ///
1623  ///\warning This class is static, so you should call refresh() (or at
1624  ///least refresh(Node)) to refresh this data structure whenever the
1625  ///digraph changes. This is a time consuming (superlinearly proportional
1626  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1627  ///
1628  ///\tparam G The type of the underlying digraph.
1629  ///
1630  ///\sa DynArcLookUp
1631  ///\sa AllArcLookUp
1632  template<class G>
1633  class ArcLookUp
1634  {
1635  public:
1636    TEMPLATE_DIGRAPH_TYPEDEFS(G);
1637    typedef G Digraph;
1638
1639  protected:
1640    const Digraph &_g;
1641    typename Digraph::template NodeMap<Arc> _head;
1642    typename Digraph::template ArcMap<Arc> _left;
1643    typename Digraph::template ArcMap<Arc> _right;
1644
1645    class ArcLess {
1646      const Digraph &g;
1647    public:
1648      ArcLess(const Digraph &_g) : g(_g) {}
1649      bool operator()(Arc a,Arc b) const
1650      {
1651        return g.target(a)<g.target(b);
1652      }
1653    };
1654
1655  public:
1656
1657    ///Constructor
1658
1659    ///Constructor.
1660    ///
1661    ///It builds up the search database, which remains valid until the digraph
1662    ///changes.
1663    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1664
1665  private:
1666    Arc refreshRec(std::vector<Arc> &v,int a,int b)
1667    {
1668      int m=(a+b)/2;
1669      Arc me=v[m];
1670      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
1671      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
1672      return me;
1673    }
1674  public:
1675    ///Refresh the search data structure at a node.
1676
1677    ///Build up the search database of node \c n.
1678    ///
1679    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
1680    ///is the number of the outgoing arcs of \c n.
1681    void refresh(Node n)
1682    {
1683      std::vector<Arc> v;
1684      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1685      if(v.size()) {
1686        std::sort(v.begin(),v.end(),ArcLess(_g));
1687        _head[n]=refreshRec(v,0,v.size()-1);
1688      }
1689      else _head[n]=INVALID;
1690    }
1691    ///Refresh the full data structure.
1692
1693    ///Build up the full search database. In fact, it simply calls
1694    ///\ref refresh(Node) "refresh(n)" for each node \c n.
1695    ///
1696    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1697    ///the number of the arcs in the digraph and <em>D</em> is the maximum
1698    ///out-degree of the digraph.
1699    void refresh()
1700    {
1701      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1702    }
1703
1704    ///Find an arc between two nodes.
1705
1706    ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
1707    ///where <em>d</em> is the number of outgoing arcs of \c s.
1708    ///\param s The source node.
1709    ///\param t The target node.
1710    ///\return An arc from \c s to \c t if there exists,
1711    ///\ref INVALID otherwise.
1712    ///
1713    ///\warning If you change the digraph, refresh() must be called before using
1714    ///this operator. If you change the outgoing arcs of
1715    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1716    Arc operator()(Node s, Node t) const
1717    {
1718      Arc e;
1719      for(e=_head[s];
1720          e!=INVALID&&_g.target(e)!=t;
1721          e = t < _g.target(e)?_left[e]:_right[e]) ;
1722      return e;
1723    }
1724
1725  };
1726
1727  ///Fast look-up of all arcs between given endpoints.
1728
1729  ///This class is the same as \ref ArcLookUp, with the addition
1730  ///that it makes it possible to find all parallel arcs between given
1731  ///endpoints.
1732  ///
1733  ///\warning This class is static, so you should call refresh() (or at
1734  ///least refresh(Node)) to refresh this data structure whenever the
1735  ///digraph changes. This is a time consuming (superlinearly proportional
1736  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1737  ///
1738  ///\tparam G The type of the underlying digraph.
1739  ///
1740  ///\sa DynArcLookUp
1741  ///\sa ArcLookUp
1742  template<class G>
1743  class AllArcLookUp : public ArcLookUp<G>
1744  {
1745    using ArcLookUp<G>::_g;
1746    using ArcLookUp<G>::_right;
1747    using ArcLookUp<G>::_left;
1748    using ArcLookUp<G>::_head;
1749
1750    TEMPLATE_DIGRAPH_TYPEDEFS(G);
1751    typedef G Digraph;
1752
1753    typename Digraph::template ArcMap<Arc> _next;
1754
1755    Arc refreshNext(Arc head,Arc next=INVALID)
1756    {
1757      if(head==INVALID) return next;
1758      else {
1759        next=refreshNext(_right[head],next);
1760        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1761          ? next : INVALID;
1762        return refreshNext(_left[head],head);
1763      }
1764    }
1765
1766    void refreshNext()
1767    {
1768      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1769    }
1770
1771  public:
1772    ///Constructor
1773
1774    ///Constructor.
1775    ///
1776    ///It builds up the search database, which remains valid until the digraph
1777    ///changes.
1778    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
1779
1780    ///Refresh the data structure at a node.
1781
1782    ///Build up the search database of node \c n.
1783    ///
1784    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
1785    ///the number of the outgoing arcs of \c n.
1786    void refresh(Node n)
1787    {
1788      ArcLookUp<G>::refresh(n);
1789      refreshNext(_head[n]);
1790    }
1791
1792    ///Refresh the full data structure.
1793
1794    ///Build up the full search database. In fact, it simply calls
1795    ///\ref refresh(Node) "refresh(n)" for each node \c n.
1796    ///
1797    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1798    ///the number of the arcs in the digraph and <em>D</em> is the maximum
1799    ///out-degree of the digraph.
1800    void refresh()
1801    {
1802      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1803    }
1804
1805    ///Find an arc between two nodes.
1806
1807    ///Find an arc between two nodes.
1808    ///\param s The source node.
1809    ///\param t The target node.
1810    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1811    ///not given, the operator finds the first appropriate arc.
1812    ///\return An arc from \c s to \c t after \c prev or
1813    ///\ref INVALID if there is no more.
1814    ///
1815    ///For example, you can count the number of arcs from \c u to \c v in the
1816    ///following way.
1817    ///\code
1818    ///AllArcLookUp<ListDigraph> ae(g);
1819    ///...
1820    ///int n = 0;
1821    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
1822    ///\endcode
1823    ///
1824    ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
1825    ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
1826    ///consecutive arcs are found in constant time.
1827    ///
1828    ///\warning If you change the digraph, refresh() must be called before using
1829    ///this operator. If you change the outgoing arcs of
1830    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1831    ///
1832#ifdef DOXYGEN
1833    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1834#else
1835    using ArcLookUp<G>::operator() ;
1836    Arc operator()(Node s, Node t, Arc prev) const
1837    {
1838      return prev==INVALID?(*this)(s,t):_next[prev];
1839    }
1840#endif
1841
1842  };
1843
1844  /// @}
1845
1846} //namespace lemon
1847
1848#endif
Note: See TracBrowser for help on using the repository browser.