COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 1096:bcb6e4402a6e

1.1 r1.1.4
Last change on this file since 1096:bcb6e4402a6e was 1081:f1398882a928, checked in by Alpar Juttner <alpar@…>, 13 years ago

Unify sources

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