COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/core.h @ 894:bb70ad62c95f

Last change on this file since 894:bb70ad62c95f was 671:da70af8844b9, checked in by Akos Ladanyi <ladanyi@…>, 10 years ago

Suppress MSVC warnings using pragmas (#295)

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-2009
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        for (typename From::NodeIt it(from); it != INVALID; ++it) {
398          nodeRefMap[it] = to.addNode();
399        }
400        for (typename From::ArcIt it(from); it != INVALID; ++it) {
401          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
402                                    nodeRefMap[from.target(it)]);
403        }
404      }
405    };
406
407    template <typename Digraph>
408    struct DigraphCopySelector<
409      Digraph,
410      typename enable_if<typename Digraph::BuildTag, void>::type>
411    {
412      template <typename From, typename NodeRefMap, typename ArcRefMap>
413      static void copy(const From& from, Digraph &to,
414                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
415        to.build(from, nodeRefMap, arcRefMap);
416      }
417    };
418
419    template <typename Graph, typename Enable = void>
420    struct GraphCopySelector {
421      template <typename From, typename NodeRefMap, typename EdgeRefMap>
422      static void copy(const From& from, Graph &to,
423                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
424        for (typename From::NodeIt it(from); it != INVALID; ++it) {
425          nodeRefMap[it] = to.addNode();
426        }
427        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
428          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
429                                      nodeRefMap[from.v(it)]);
430        }
431      }
432    };
433
434    template <typename Graph>
435    struct GraphCopySelector<
436      Graph,
437      typename enable_if<typename Graph::BuildTag, void>::type>
438    {
439      template <typename From, typename NodeRefMap, typename EdgeRefMap>
440      static void copy(const From& from, Graph &to,
441                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
442        to.build(from, nodeRefMap, edgeRefMap);
443      }
444    };
445
446  }
447
448  /// \brief Class to copy a digraph.
449  ///
450  /// Class to copy a digraph to another digraph (duplicate a digraph). The
451  /// simplest way of using it is through the \c digraphCopy() function.
452  ///
453  /// This class not only make a copy of a digraph, but it can create
454  /// references and cross references between the nodes and arcs of
455  /// the two digraphs, and it can copy maps to use with the newly created
456  /// digraph.
457  ///
458  /// To make a copy from a digraph, first an instance of DigraphCopy
459  /// should be created, then the data belongs to the digraph should
460  /// assigned to copy. In the end, the \c run() member should be
461  /// called.
462  ///
463  /// The next code copies a digraph with several data:
464  ///\code
465  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
466  ///  // Create references for the nodes
467  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
468  ///  cg.nodeRef(nr);
469  ///  // Create cross references (inverse) for the arcs
470  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
471  ///  cg.arcCrossRef(acr);
472  ///  // Copy an arc map
473  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
474  ///  NewGraph::ArcMap<double> namap(new_graph);
475  ///  cg.arcMap(oamap, namap);
476  ///  // Copy a node
477  ///  OrigGraph::Node on;
478  ///  NewGraph::Node nn;
479  ///  cg.node(on, nn);
480  ///  // Execute copying
481  ///  cg.run();
482  ///\endcode
483  template <typename From, typename To>
484  class DigraphCopy {
485  private:
486
487    typedef typename From::Node Node;
488    typedef typename From::NodeIt NodeIt;
489    typedef typename From::Arc Arc;
490    typedef typename From::ArcIt ArcIt;
491
492    typedef typename To::Node TNode;
493    typedef typename To::Arc TArc;
494
495    typedef typename From::template NodeMap<TNode> NodeRefMap;
496    typedef typename From::template ArcMap<TArc> ArcRefMap;
497
498  public:
499
500    /// \brief Constructor of DigraphCopy.
501    ///
502    /// Constructor of DigraphCopy for copying the content of the
503    /// \c from digraph into the \c to digraph.
504    DigraphCopy(const From& from, To& to)
505      : _from(from), _to(to) {}
506
507    /// \brief Destructor of DigraphCopy
508    ///
509    /// Destructor of DigraphCopy.
510    ~DigraphCopy() {
511      for (int i = 0; i < int(_node_maps.size()); ++i) {
512        delete _node_maps[i];
513      }
514      for (int i = 0; i < int(_arc_maps.size()); ++i) {
515        delete _arc_maps[i];
516      }
517
518    }
519
520    /// \brief Copy the node references into the given map.
521    ///
522    /// This function copies the node references into the given map.
523    /// The parameter should be a map, whose key type is the Node type of
524    /// the source digraph, while the value type is the Node type of the
525    /// destination digraph.
526    template <typename NodeRef>
527    DigraphCopy& nodeRef(NodeRef& map) {
528      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
529                           NodeRefMap, NodeRef>(map));
530      return *this;
531    }
532
533    /// \brief Copy the node cross references into the given map.
534    ///
535    /// This function copies the node cross references (reverse references)
536    /// into the given map. The parameter should be a map, whose key type
537    /// is the Node type of the destination digraph, while the value type is
538    /// the Node type of the source digraph.
539    template <typename NodeCrossRef>
540    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
541      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
542                           NodeRefMap, NodeCrossRef>(map));
543      return *this;
544    }
545
546    /// \brief Make a copy of the given node map.
547    ///
548    /// This function makes a copy of the given node map for the newly
549    /// created digraph.
550    /// The key type of the new map \c tmap should be the Node type of the
551    /// destination digraph, and the key type of the original map \c map
552    /// should be the Node type of the source digraph.
553    template <typename FromMap, typename ToMap>
554    DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
555      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
556                           NodeRefMap, FromMap, ToMap>(map, tmap));
557      return *this;
558    }
559
560    /// \brief Make a copy of the given node.
561    ///
562    /// This function makes a copy of the given node.
563    DigraphCopy& node(const Node& node, TNode& tnode) {
564      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
565                           NodeRefMap, TNode>(node, tnode));
566      return *this;
567    }
568
569    /// \brief Copy the arc references into the given map.
570    ///
571    /// This function copies the arc references into the given map.
572    /// The parameter should be a map, whose key type is the Arc type of
573    /// the source digraph, while the value type is the Arc type of the
574    /// destination digraph.
575    template <typename ArcRef>
576    DigraphCopy& arcRef(ArcRef& map) {
577      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
578                          ArcRefMap, ArcRef>(map));
579      return *this;
580    }
581
582    /// \brief Copy the arc cross references into the given map.
583    ///
584    /// This function copies the arc cross references (reverse references)
585    /// into the given map. The parameter should be a map, whose key type
586    /// is the Arc type of the destination digraph, while the value type is
587    /// the Arc type of the source digraph.
588    template <typename ArcCrossRef>
589    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
590      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
591                          ArcRefMap, ArcCrossRef>(map));
592      return *this;
593    }
594
595    /// \brief Make a copy of the given arc map.
596    ///
597    /// This function makes a copy of the given arc map for the newly
598    /// created digraph.
599    /// The key type of the new map \c tmap should be the Arc type of the
600    /// destination digraph, and the key type of the original map \c map
601    /// should be the Arc type of the source digraph.
602    template <typename FromMap, typename ToMap>
603    DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
604      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
605                          ArcRefMap, FromMap, ToMap>(map, tmap));
606      return *this;
607    }
608
609    /// \brief Make a copy of the given arc.
610    ///
611    /// This function makes a copy of the given arc.
612    DigraphCopy& arc(const Arc& arc, TArc& tarc) {
613      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
614                          ArcRefMap, TArc>(arc, tarc));
615      return *this;
616    }
617
618    /// \brief Execute copying.
619    ///
620    /// This function executes the copying of the digraph along with the
621    /// copying of the assigned data.
622    void run() {
623      NodeRefMap nodeRefMap(_from);
624      ArcRefMap arcRefMap(_from);
625      _core_bits::DigraphCopySelector<To>::
626        copy(_from, _to, nodeRefMap, arcRefMap);
627      for (int i = 0; i < int(_node_maps.size()); ++i) {
628        _node_maps[i]->copy(_from, nodeRefMap);
629      }
630      for (int i = 0; i < int(_arc_maps.size()); ++i) {
631        _arc_maps[i]->copy(_from, arcRefMap);
632      }
633    }
634
635  protected:
636
637    const From& _from;
638    To& _to;
639
640    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
641      _node_maps;
642
643    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
644      _arc_maps;
645
646  };
647
648  /// \brief Copy a digraph to another digraph.
649  ///
650  /// This function copies a digraph to another digraph.
651  /// The complete usage of it is detailed in the DigraphCopy class, but
652  /// a short example shows a basic work:
653  ///\code
654  /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
655  ///\endcode
656  ///
657  /// After the copy the \c nr map will contain the mapping from the
658  /// nodes of the \c from digraph to the nodes of the \c to digraph and
659  /// \c acr will contain the mapping from the arcs of the \c to digraph
660  /// to the arcs of the \c from digraph.
661  ///
662  /// \see DigraphCopy
663  template <typename From, typename To>
664  DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
665    return DigraphCopy<From, To>(from, to);
666  }
667
668  /// \brief Class to copy a graph.
669  ///
670  /// Class to copy a graph to another graph (duplicate a graph). The
671  /// simplest way of using it is through the \c graphCopy() function.
672  ///
673  /// This class not only make a copy of a graph, but it can create
674  /// references and cross references between the nodes, edges and arcs of
675  /// the two graphs, and it can copy maps for using with the newly created
676  /// graph.
677  ///
678  /// To make a copy from a graph, first an instance of GraphCopy
679  /// should be created, then the data belongs to the graph should
680  /// assigned to copy. In the end, the \c run() member should be
681  /// called.
682  ///
683  /// The next code copies a graph with several data:
684  ///\code
685  ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
686  ///  // Create references for the nodes
687  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
688  ///  cg.nodeRef(nr);
689  ///  // Create cross references (inverse) for the edges
690  ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
691  ///  cg.edgeCrossRef(ecr);
692  ///  // Copy an edge map
693  ///  OrigGraph::EdgeMap<double> oemap(orig_graph);
694  ///  NewGraph::EdgeMap<double> nemap(new_graph);
695  ///  cg.edgeMap(oemap, nemap);
696  ///  // Copy a node
697  ///  OrigGraph::Node on;
698  ///  NewGraph::Node nn;
699  ///  cg.node(on, nn);
700  ///  // Execute copying
701  ///  cg.run();
702  ///\endcode
703  template <typename From, typename To>
704  class GraphCopy {
705  private:
706
707    typedef typename From::Node Node;
708    typedef typename From::NodeIt NodeIt;
709    typedef typename From::Arc Arc;
710    typedef typename From::ArcIt ArcIt;
711    typedef typename From::Edge Edge;
712    typedef typename From::EdgeIt EdgeIt;
713
714    typedef typename To::Node TNode;
715    typedef typename To::Arc TArc;
716    typedef typename To::Edge TEdge;
717
718    typedef typename From::template NodeMap<TNode> NodeRefMap;
719    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
720
721    struct ArcRefMap {
722      ArcRefMap(const From& from, const To& to,
723                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
724        : _from(from), _to(to),
725          _edge_ref(edge_ref), _node_ref(node_ref) {}
726
727      typedef typename From::Arc Key;
728      typedef typename To::Arc Value;
729
730      Value operator[](const Key& key) const {
731        bool forward = _from.u(key) != _from.v(key) ?
732          _node_ref[_from.source(key)] ==
733          _to.source(_to.direct(_edge_ref[key], true)) :
734          _from.direction(key);
735        return _to.direct(_edge_ref[key], forward);
736      }
737
738      const From& _from;
739      const To& _to;
740      const EdgeRefMap& _edge_ref;
741      const NodeRefMap& _node_ref;
742    };
743
744  public:
745
746    /// \brief Constructor of GraphCopy.
747    ///
748    /// Constructor of GraphCopy for copying the content of the
749    /// \c from graph into the \c to graph.
750    GraphCopy(const From& from, To& to)
751      : _from(from), _to(to) {}
752
753    /// \brief Destructor of GraphCopy
754    ///
755    /// Destructor of GraphCopy.
756    ~GraphCopy() {
757      for (int i = 0; i < int(_node_maps.size()); ++i) {
758        delete _node_maps[i];
759      }
760      for (int i = 0; i < int(_arc_maps.size()); ++i) {
761        delete _arc_maps[i];
762      }
763      for (int i = 0; i < int(_edge_maps.size()); ++i) {
764        delete _edge_maps[i];
765      }
766    }
767
768    /// \brief Copy the node references into the given map.
769    ///
770    /// This function copies the node references into the given map.
771    /// The parameter should be a map, whose key type is the Node type of
772    /// the source graph, while the value type is the Node type of the
773    /// destination graph.
774    template <typename NodeRef>
775    GraphCopy& nodeRef(NodeRef& map) {
776      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
777                           NodeRefMap, NodeRef>(map));
778      return *this;
779    }
780
781    /// \brief Copy the node cross references into the given map.
782    ///
783    /// This function copies the node cross references (reverse references)
784    /// into the given map. The parameter should be a map, whose key type
785    /// is the Node type of the destination graph, while the value type is
786    /// the Node type of the source graph.
787    template <typename NodeCrossRef>
788    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
789      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
790                           NodeRefMap, NodeCrossRef>(map));
791      return *this;
792    }
793
794    /// \brief Make a copy of the given node map.
795    ///
796    /// This function makes a copy of the given node map for the newly
797    /// created graph.
798    /// The key type of the new map \c tmap should be the Node type of the
799    /// destination graph, and the key type of the original map \c map
800    /// should be the Node type of the source graph.
801    template <typename FromMap, typename ToMap>
802    GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
803      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
804                           NodeRefMap, FromMap, ToMap>(map, tmap));
805      return *this;
806    }
807
808    /// \brief Make a copy of the given node.
809    ///
810    /// This function makes a copy of the given node.
811    GraphCopy& node(const Node& node, TNode& tnode) {
812      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
813                           NodeRefMap, TNode>(node, tnode));
814      return *this;
815    }
816
817    /// \brief Copy the arc references into the given map.
818    ///
819    /// This function copies the arc references into the given map.
820    /// The parameter should be a map, whose key type is the Arc type of
821    /// the source graph, while the value type is the Arc type of the
822    /// destination graph.
823    template <typename ArcRef>
824    GraphCopy& arcRef(ArcRef& map) {
825      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
826                          ArcRefMap, ArcRef>(map));
827      return *this;
828    }
829
830    /// \brief Copy the arc cross references into the given map.
831    ///
832    /// This function copies the arc cross references (reverse references)
833    /// into the given map. The parameter should be a map, whose key type
834    /// is the Arc type of the destination graph, while the value type is
835    /// the Arc type of the source graph.
836    template <typename ArcCrossRef>
837    GraphCopy& arcCrossRef(ArcCrossRef& map) {
838      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
839                          ArcRefMap, ArcCrossRef>(map));
840      return *this;
841    }
842
843    /// \brief Make a copy of the given arc map.
844    ///
845    /// This function makes a copy of the given arc map for the newly
846    /// created graph.
847    /// The key type of the new map \c tmap should be the Arc type of the
848    /// destination graph, and the key type of the original map \c map
849    /// should be the Arc type of the source graph.
850    template <typename FromMap, typename ToMap>
851    GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
852      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
853                          ArcRefMap, FromMap, ToMap>(map, tmap));
854      return *this;
855    }
856
857    /// \brief Make a copy of the given arc.
858    ///
859    /// This function makes a copy of the given arc.
860    GraphCopy& arc(const Arc& arc, TArc& tarc) {
861      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
862                          ArcRefMap, TArc>(arc, tarc));
863      return *this;
864    }
865
866    /// \brief Copy the edge references into the given map.
867    ///
868    /// This function copies the edge references into the given map.
869    /// The parameter should be a map, whose key type is the Edge type of
870    /// the source graph, while the value type is the Edge type of the
871    /// destination graph.
872    template <typename EdgeRef>
873    GraphCopy& edgeRef(EdgeRef& map) {
874      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
875                           EdgeRefMap, EdgeRef>(map));
876      return *this;
877    }
878
879    /// \brief Copy the edge cross references into the given map.
880    ///
881    /// This function copies the edge cross references (reverse references)
882    /// into the given map. The parameter should be a map, whose key type
883    /// is the Edge type of the destination graph, while the value type is
884    /// the Edge type of the source graph.
885    template <typename EdgeCrossRef>
886    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
887      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
888                           Edge, EdgeRefMap, EdgeCrossRef>(map));
889      return *this;
890    }
891
892    /// \brief Make a copy of the given edge map.
893    ///
894    /// This function makes a copy of the given edge map for the newly
895    /// created graph.
896    /// The key type of the new map \c tmap should be the Edge type of the
897    /// destination graph, and the key type of the original map \c map
898    /// should be the Edge type of the source graph.
899    template <typename FromMap, typename ToMap>
900    GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
901      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
902                           EdgeRefMap, FromMap, ToMap>(map, tmap));
903      return *this;
904    }
905
906    /// \brief Make a copy of the given edge.
907    ///
908    /// This function makes a copy of the given edge.
909    GraphCopy& edge(const Edge& edge, TEdge& tedge) {
910      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
911                           EdgeRefMap, TEdge>(edge, tedge));
912      return *this;
913    }
914
915    /// \brief Execute copying.
916    ///
917    /// This function executes the copying of the graph along with the
918    /// copying of the assigned data.
919    void run() {
920      NodeRefMap nodeRefMap(_from);
921      EdgeRefMap edgeRefMap(_from);
922      ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
923      _core_bits::GraphCopySelector<To>::
924        copy(_from, _to, nodeRefMap, edgeRefMap);
925      for (int i = 0; i < int(_node_maps.size()); ++i) {
926        _node_maps[i]->copy(_from, nodeRefMap);
927      }
928      for (int i = 0; i < int(_edge_maps.size()); ++i) {
929        _edge_maps[i]->copy(_from, edgeRefMap);
930      }
931      for (int i = 0; i < int(_arc_maps.size()); ++i) {
932        _arc_maps[i]->copy(_from, arcRefMap);
933      }
934    }
935
936  private:
937
938    const From& _from;
939    To& _to;
940
941    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
942      _node_maps;
943
944    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
945      _arc_maps;
946
947    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
948      _edge_maps;
949
950  };
951
952  /// \brief Copy a graph to another graph.
953  ///
954  /// This function copies a graph to another graph.
955  /// The complete usage of it is detailed in the GraphCopy class,
956  /// but a short example shows a basic work:
957  ///\code
958  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
959  ///\endcode
960  ///
961  /// After the copy the \c nr map will contain the mapping from the
962  /// nodes of the \c from graph to the nodes of the \c to graph and
963  /// \c ecr will contain the mapping from the edges of the \c to graph
964  /// to the edges of the \c from graph.
965  ///
966  /// \see GraphCopy
967  template <typename From, typename To>
968  GraphCopy<From, To>
969  graphCopy(const From& from, To& to) {
970    return GraphCopy<From, To>(from, to);
971  }
972
973  namespace _core_bits {
974
975    template <typename Graph, typename Enable = void>
976    struct FindArcSelector {
977      typedef typename Graph::Node Node;
978      typedef typename Graph::Arc Arc;
979      static Arc find(const Graph &g, Node u, Node v, Arc e) {
980        if (e == INVALID) {
981          g.firstOut(e, u);
982        } else {
983          g.nextOut(e);
984        }
985        while (e != INVALID && g.target(e) != v) {
986          g.nextOut(e);
987        }
988        return e;
989      }
990    };
991
992    template <typename Graph>
993    struct FindArcSelector<
994      Graph,
995      typename enable_if<typename Graph::FindArcTag, void>::type>
996    {
997      typedef typename Graph::Node Node;
998      typedef typename Graph::Arc Arc;
999      static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1000        return g.findArc(u, v, prev);
1001      }
1002    };
1003  }
1004
1005  /// \brief Find an arc between two nodes of a digraph.
1006  ///
1007  /// This function finds an arc from node \c u to node \c v in the
1008  /// digraph \c g.
1009  ///
1010  /// If \c prev is \ref INVALID (this is the default value), then
1011  /// it finds the first arc from \c u to \c v. Otherwise it looks for
1012  /// the next arc from \c u to \c v after \c prev.
1013  /// \return The found arc or \ref INVALID if there is no such an arc.
1014  ///
1015  /// Thus you can iterate through each arc from \c u to \c v as it follows.
1016  ///\code
1017  /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1018  ///   ...
1019  /// }
1020  ///\endcode
1021  ///
1022  /// \note \ref ConArcIt provides iterator interface for the same
1023  /// functionality.
1024  ///
1025  ///\sa ConArcIt
1026  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1027  template <typename Graph>
1028  inline typename Graph::Arc
1029  findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1030          typename Graph::Arc prev = INVALID) {
1031    return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1032  }
1033
1034  /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
1035  ///
1036  /// Iterator for iterating on parallel arcs connecting the same nodes. It is
1037  /// a higher level interface for the \ref findArc() function. You can
1038  /// use it the following way:
1039  ///\code
1040  /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1041  ///   ...
1042  /// }
1043  ///\endcode
1044  ///
1045  ///\sa findArc()
1046  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1047  template <typename GR>
1048  class ConArcIt : public GR::Arc {
1049    typedef typename GR::Arc Parent;
1050
1051  public:
1052
1053    typedef typename GR::Arc Arc;
1054    typedef typename GR::Node Node;
1055
1056    /// \brief Constructor.
1057    ///
1058    /// Construct a new ConArcIt iterating on the arcs that
1059    /// connects nodes \c u and \c v.
1060    ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
1061      Parent::operator=(findArc(_graph, u, v));
1062    }
1063
1064    /// \brief Constructor.
1065    ///
1066    /// Construct a new ConArcIt that continues the iterating from arc \c a.
1067    ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
1068
1069    /// \brief Increment operator.
1070    ///
1071    /// It increments the iterator and gives back the next arc.
1072    ConArcIt& operator++() {
1073      Parent::operator=(findArc(_graph, _graph.source(*this),
1074                                _graph.target(*this), *this));
1075      return *this;
1076    }
1077  private:
1078    const GR& _graph;
1079  };
1080
1081  namespace _core_bits {
1082
1083    template <typename Graph, typename Enable = void>
1084    struct FindEdgeSelector {
1085      typedef typename Graph::Node Node;
1086      typedef typename Graph::Edge Edge;
1087      static Edge find(const Graph &g, Node u, Node v, Edge e) {
1088        bool b;
1089        if (u != v) {
1090          if (e == INVALID) {
1091            g.firstInc(e, b, u);
1092          } else {
1093            b = g.u(e) == u;
1094            g.nextInc(e, b);
1095          }
1096          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1097            g.nextInc(e, b);
1098          }
1099        } else {
1100          if (e == INVALID) {
1101            g.firstInc(e, b, u);
1102          } else {
1103            b = true;
1104            g.nextInc(e, b);
1105          }
1106          while (e != INVALID && (!b || g.v(e) != v)) {
1107            g.nextInc(e, b);
1108          }
1109        }
1110        return e;
1111      }
1112    };
1113
1114    template <typename Graph>
1115    struct FindEdgeSelector<
1116      Graph,
1117      typename enable_if<typename Graph::FindEdgeTag, void>::type>
1118    {
1119      typedef typename Graph::Node Node;
1120      typedef typename Graph::Edge Edge;
1121      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1122        return g.findEdge(u, v, prev);
1123      }
1124    };
1125  }
1126
1127  /// \brief Find an edge between two nodes of a graph.
1128  ///
1129  /// This function finds an edge from node \c u to node \c v in graph \c g.
1130  /// If node \c u and node \c v is equal then each loop edge
1131  /// will be enumerated once.
1132  ///
1133  /// If \c prev is \ref INVALID (this is the default value), then
1134  /// it finds the first edge from \c u to \c v. Otherwise it looks for
1135  /// the next edge from \c u to \c v after \c prev.
1136  /// \return The found edge or \ref INVALID if there is no such an edge.
1137  ///
1138  /// Thus you can iterate through each edge between \c u and \c v
1139  /// as it follows.
1140  ///\code
1141  /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1142  ///   ...
1143  /// }
1144  ///\endcode
1145  ///
1146  /// \note \ref ConEdgeIt provides iterator interface for the same
1147  /// functionality.
1148  ///
1149  ///\sa ConEdgeIt
1150  template <typename Graph>
1151  inline typename Graph::Edge
1152  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1153            typename Graph::Edge p = INVALID) {
1154    return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1155  }
1156
1157  /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1158  ///
1159  /// Iterator for iterating on parallel edges connecting the same nodes.
1160  /// It is a higher level interface for the findEdge() function. You can
1161  /// use it the following way:
1162  ///\code
1163  /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1164  ///   ...
1165  /// }
1166  ///\endcode
1167  ///
1168  ///\sa findEdge()
1169  template <typename GR>
1170  class ConEdgeIt : public GR::Edge {
1171    typedef typename GR::Edge Parent;
1172
1173  public:
1174
1175    typedef typename GR::Edge Edge;
1176    typedef typename GR::Node Node;
1177
1178    /// \brief Constructor.
1179    ///
1180    /// Construct a new ConEdgeIt iterating on the edges that
1181    /// connects nodes \c u and \c v.
1182    ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1183      Parent::operator=(findEdge(_graph, _u, _v));
1184    }
1185
1186    /// \brief Constructor.
1187    ///
1188    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1189    ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
1190
1191    /// \brief Increment operator.
1192    ///
1193    /// It increments the iterator and gives back the next edge.
1194    ConEdgeIt& operator++() {
1195      Parent::operator=(findEdge(_graph, _u, _v, *this));
1196      return *this;
1197    }
1198  private:
1199    const GR& _graph;
1200    Node _u, _v;
1201  };
1202
1203
1204  ///Dynamic arc look-up between given endpoints.
1205
1206  ///Using this class, you can find an arc in a digraph from a given
1207  ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1208  ///where <em>d</em> is the out-degree of the source node.
1209  ///
1210  ///It is possible to find \e all parallel arcs between two nodes with
1211  ///the \c operator() member.
1212  ///
1213  ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1214  ///\ref AllArcLookUp if your digraph is not changed so frequently.
1215  ///
1216  ///This class uses a self-adjusting binary search tree, the Splay tree
1217  ///of Sleator and Tarjan to guarantee the logarithmic amortized
1218  ///time bound for arc look-ups. This class also guarantees the
1219  ///optimal time bound in a constant factor for any distribution of
1220  ///queries.
1221  ///
1222  ///\tparam GR The type of the underlying digraph.
1223  ///
1224  ///\sa ArcLookUp
1225  ///\sa AllArcLookUp
1226  template <typename GR>
1227  class DynArcLookUp
1228    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
1229  {
1230    typedef typename ItemSetTraits<GR, typename GR::Arc>
1231    ::ItemNotifier::ObserverBase Parent;
1232
1233    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1234
1235  public:
1236
1237    /// The Digraph type
1238    typedef GR Digraph;
1239
1240  protected:
1241
1242    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
1243      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
1244
1245    public:
1246
1247      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
1248
1249      virtual void add(const Node& node) {
1250        Parent::add(node);
1251        Parent::set(node, INVALID);
1252      }
1253
1254      virtual void add(const std::vector<Node>& nodes) {
1255        Parent::add(nodes);
1256        for (int i = 0; i < int(nodes.size()); ++i) {
1257          Parent::set(nodes[i], INVALID);
1258        }
1259      }
1260
1261      virtual void build() {
1262        Parent::build();
1263        Node it;
1264        typename Parent::Notifier* nf = Parent::notifier();
1265        for (nf->first(it); it != INVALID; nf->next(it)) {
1266          Parent::set(it, INVALID);
1267        }
1268      }
1269    };
1270
1271    class ArcLess {
1272      const Digraph &g;
1273    public:
1274      ArcLess(const Digraph &_g) : g(_g) {}
1275      bool operator()(Arc a,Arc b) const
1276      {
1277        return g.target(a)<g.target(b);
1278      }
1279    };
1280
1281  protected:
1282
1283    const Digraph &_g;
1284    AutoNodeMap _head;
1285    typename Digraph::template ArcMap<Arc> _parent;
1286    typename Digraph::template ArcMap<Arc> _left;
1287    typename Digraph::template ArcMap<Arc> _right;
1288
1289  public:
1290
1291    ///Constructor
1292
1293    ///Constructor.
1294    ///
1295    ///It builds up the search database.
1296    DynArcLookUp(const Digraph &g)
1297      : _g(g),_head(g),_parent(g),_left(g),_right(g)
1298    {
1299      Parent::attach(_g.notifier(typename Digraph::Arc()));
1300      refresh();
1301    }
1302
1303  protected:
1304
1305    virtual void add(const Arc& arc) {
1306      insert(arc);
1307    }
1308
1309    virtual void add(const std::vector<Arc>& arcs) {
1310      for (int i = 0; i < int(arcs.size()); ++i) {
1311        insert(arcs[i]);
1312      }
1313    }
1314
1315    virtual void erase(const Arc& arc) {
1316      remove(arc);
1317    }
1318
1319    virtual void erase(const std::vector<Arc>& arcs) {
1320      for (int i = 0; i < int(arcs.size()); ++i) {
1321        remove(arcs[i]);
1322      }
1323    }
1324
1325    virtual void build() {
1326      refresh();
1327    }
1328
1329    virtual void clear() {
1330      for(NodeIt n(_g);n!=INVALID;++n) {
1331        _head[n] = INVALID;
1332      }
1333    }
1334
1335    void insert(Arc arc) {
1336      Node s = _g.source(arc);
1337      Node t = _g.target(arc);
1338      _left[arc] = INVALID;
1339      _right[arc] = INVALID;
1340
1341      Arc e = _head[s];
1342      if (e == INVALID) {
1343        _head[s] = arc;
1344        _parent[arc] = INVALID;
1345        return;
1346      }
1347      while (true) {
1348        if (t < _g.target(e)) {
1349          if (_left[e] == INVALID) {
1350            _left[e] = arc;
1351            _parent[arc] = e;
1352            splay(arc);
1353            return;
1354          } else {
1355            e = _left[e];
1356          }
1357        } else {
1358          if (_right[e] == INVALID) {
1359            _right[e] = arc;
1360            _parent[arc] = e;
1361            splay(arc);
1362            return;
1363          } else {
1364            e = _right[e];
1365          }
1366        }
1367      }
1368    }
1369
1370    void remove(Arc arc) {
1371      if (_left[arc] == INVALID) {
1372        if (_right[arc] != INVALID) {
1373          _parent[_right[arc]] = _parent[arc];
1374        }
1375        if (_parent[arc] != INVALID) {
1376          if (_left[_parent[arc]] == arc) {
1377            _left[_parent[arc]] = _right[arc];
1378          } else {
1379            _right[_parent[arc]] = _right[arc];
1380          }
1381        } else {
1382          _head[_g.source(arc)] = _right[arc];
1383        }
1384      } else if (_right[arc] == INVALID) {
1385        _parent[_left[arc]] = _parent[arc];
1386        if (_parent[arc] != INVALID) {
1387          if (_left[_parent[arc]] == arc) {
1388            _left[_parent[arc]] = _left[arc];
1389          } else {
1390            _right[_parent[arc]] = _left[arc];
1391          }
1392        } else {
1393          _head[_g.source(arc)] = _left[arc];
1394        }
1395      } else {
1396        Arc e = _left[arc];
1397        if (_right[e] != INVALID) {
1398          e = _right[e];
1399          while (_right[e] != INVALID) {
1400            e = _right[e];
1401          }
1402          Arc s = _parent[e];
1403          _right[_parent[e]] = _left[e];
1404          if (_left[e] != INVALID) {
1405            _parent[_left[e]] = _parent[e];
1406          }
1407
1408          _left[e] = _left[arc];
1409          _parent[_left[arc]] = e;
1410          _right[e] = _right[arc];
1411          _parent[_right[arc]] = e;
1412
1413          _parent[e] = _parent[arc];
1414          if (_parent[arc] != INVALID) {
1415            if (_left[_parent[arc]] == arc) {
1416              _left[_parent[arc]] = e;
1417            } else {
1418              _right[_parent[arc]] = e;
1419            }
1420          }
1421          splay(s);
1422        } else {
1423          _right[e] = _right[arc];
1424          _parent[_right[arc]] = e;
1425          _parent[e] = _parent[arc];
1426
1427          if (_parent[arc] != INVALID) {
1428            if (_left[_parent[arc]] == arc) {
1429              _left[_parent[arc]] = e;
1430            } else {
1431              _right[_parent[arc]] = e;
1432            }
1433          } else {
1434            _head[_g.source(arc)] = e;
1435          }
1436        }
1437      }
1438    }
1439
1440    Arc refreshRec(std::vector<Arc> &v,int a,int b)
1441    {
1442      int m=(a+b)/2;
1443      Arc me=v[m];
1444      if (a < m) {
1445        Arc left = refreshRec(v,a,m-1);
1446        _left[me] = left;
1447        _parent[left] = me;
1448      } else {
1449        _left[me] = INVALID;
1450      }
1451      if (m < b) {
1452        Arc right = refreshRec(v,m+1,b);
1453        _right[me] = right;
1454        _parent[right] = me;
1455      } else {
1456        _right[me] = INVALID;
1457      }
1458      return me;
1459    }
1460
1461    void refresh() {
1462      for(NodeIt n(_g);n!=INVALID;++n) {
1463        std::vector<Arc> v;
1464        for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
1465        if (!v.empty()) {
1466          std::sort(v.begin(),v.end(),ArcLess(_g));
1467          Arc head = refreshRec(v,0,v.size()-1);
1468          _head[n] = head;
1469          _parent[head] = INVALID;
1470        }
1471        else _head[n] = INVALID;
1472      }
1473    }
1474
1475    void zig(Arc v) {
1476      Arc w = _parent[v];
1477      _parent[v] = _parent[w];
1478      _parent[w] = v;
1479      _left[w] = _right[v];
1480      _right[v] = w;
1481      if (_parent[v] != INVALID) {
1482        if (_right[_parent[v]] == w) {
1483          _right[_parent[v]] = v;
1484        } else {
1485          _left[_parent[v]] = v;
1486        }
1487      }
1488      if (_left[w] != INVALID){
1489        _parent[_left[w]] = w;
1490      }
1491    }
1492
1493    void zag(Arc v) {
1494      Arc w = _parent[v];
1495      _parent[v] = _parent[w];
1496      _parent[w] = v;
1497      _right[w] = _left[v];
1498      _left[v] = w;
1499      if (_parent[v] != INVALID){
1500        if (_left[_parent[v]] == w) {
1501          _left[_parent[v]] = v;
1502        } else {
1503          _right[_parent[v]] = v;
1504        }
1505      }
1506      if (_right[w] != INVALID){
1507        _parent[_right[w]] = w;
1508      }
1509    }
1510
1511    void splay(Arc v) {
1512      while (_parent[v] != INVALID) {
1513        if (v == _left[_parent[v]]) {
1514          if (_parent[_parent[v]] == INVALID) {
1515            zig(v);
1516          } else {
1517            if (_parent[v] == _left[_parent[_parent[v]]]) {
1518              zig(_parent[v]);
1519              zig(v);
1520            } else {
1521              zig(v);
1522              zag(v);
1523            }
1524          }
1525        } else {
1526          if (_parent[_parent[v]] == INVALID) {
1527            zag(v);
1528          } else {
1529            if (_parent[v] == _left[_parent[_parent[v]]]) {
1530              zag(v);
1531              zig(v);
1532            } else {
1533              zag(_parent[v]);
1534              zag(v);
1535            }
1536          }
1537        }
1538      }
1539      _head[_g.source(v)] = v;
1540    }
1541
1542
1543  public:
1544
1545    ///Find an arc between two nodes.
1546
1547    ///Find an arc between two nodes.
1548    ///\param s The source node.
1549    ///\param t The target node.
1550    ///\param p The previous arc between \c s and \c t. It it is INVALID or
1551    ///not given, the operator finds the first appropriate arc.
1552    ///\return An arc from \c s to \c t after \c p or
1553    ///\ref INVALID if there is no more.
1554    ///
1555    ///For example, you can count the number of arcs from \c u to \c v in the
1556    ///following way.
1557    ///\code
1558    ///DynArcLookUp<ListDigraph> ae(g);
1559    ///...
1560    ///int n = 0;
1561    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
1562    ///\endcode
1563    ///
1564    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
1565    ///amortized time, specifically, the time complexity of the lookups
1566    ///is equal to the optimal search tree implementation for the
1567    ///current query distribution in a constant factor.
1568    ///
1569    ///\note This is a dynamic data structure, therefore the data
1570    ///structure is updated after each graph alteration. Thus although
1571    ///this data structure is theoretically faster than \ref ArcLookUp
1572    ///and \ref AllArcLookUp, it often provides worse performance than
1573    ///them.
1574    Arc operator()(Node s, Node t, Arc p = INVALID) const  {
1575      if (p == INVALID) {
1576        Arc a = _head[s];
1577        if (a == INVALID) return INVALID;
1578        Arc r = INVALID;
1579        while (true) {
1580          if (_g.target(a) < t) {
1581            if (_right[a] == INVALID) {
1582              const_cast<DynArcLookUp&>(*this).splay(a);
1583              return r;
1584            } else {
1585              a = _right[a];
1586            }
1587          } else {
1588            if (_g.target(a) == t) {
1589              r = a;
1590            }
1591            if (_left[a] == INVALID) {
1592              const_cast<DynArcLookUp&>(*this).splay(a);
1593              return r;
1594            } else {
1595              a = _left[a];
1596            }
1597          }
1598        }
1599      } else {
1600        Arc a = p;
1601        if (_right[a] != INVALID) {
1602          a = _right[a];
1603          while (_left[a] != INVALID) {
1604            a = _left[a];
1605          }
1606          const_cast<DynArcLookUp&>(*this).splay(a);
1607        } else {
1608          while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
1609            a = _parent[a];
1610          }
1611          if (_parent[a] == INVALID) {
1612            return INVALID;
1613          } else {
1614            a = _parent[a];
1615            const_cast<DynArcLookUp&>(*this).splay(a);
1616          }
1617        }
1618        if (_g.target(a) == t) return a;
1619        else return INVALID;
1620      }
1621    }
1622
1623  };
1624
1625  ///Fast arc look-up between given endpoints.
1626
1627  ///Using this class, you can find an arc in a digraph from a given
1628  ///source to a given target in time <em>O</em>(log<em>d</em>),
1629  ///where <em>d</em> is the out-degree of the source node.
1630  ///
1631  ///It is not possible to find \e all parallel arcs between two nodes.
1632  ///Use \ref AllArcLookUp for this purpose.
1633  ///
1634  ///\warning This class is static, so you should call refresh() (or at
1635  ///least refresh(Node)) to refresh this data structure whenever the
1636  ///digraph changes. This is a time consuming (superlinearly proportional
1637  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1638  ///
1639  ///\tparam GR The type of the underlying digraph.
1640  ///
1641  ///\sa DynArcLookUp
1642  ///\sa AllArcLookUp
1643  template<class GR>
1644  class ArcLookUp
1645  {
1646    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1647
1648  public:
1649
1650    /// The Digraph type
1651    typedef GR Digraph;
1652
1653  protected:
1654    const Digraph &_g;
1655    typename Digraph::template NodeMap<Arc> _head;
1656    typename Digraph::template ArcMap<Arc> _left;
1657    typename Digraph::template ArcMap<Arc> _right;
1658
1659    class ArcLess {
1660      const Digraph &g;
1661    public:
1662      ArcLess(const Digraph &_g) : g(_g) {}
1663      bool operator()(Arc a,Arc b) const
1664      {
1665        return g.target(a)<g.target(b);
1666      }
1667    };
1668
1669  public:
1670
1671    ///Constructor
1672
1673    ///Constructor.
1674    ///
1675    ///It builds up the search database, which remains valid until the digraph
1676    ///changes.
1677    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1678
1679  private:
1680    Arc refreshRec(std::vector<Arc> &v,int a,int b)
1681    {
1682      int m=(a+b)/2;
1683      Arc me=v[m];
1684      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
1685      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
1686      return me;
1687    }
1688  public:
1689    ///Refresh the search data structure at a node.
1690
1691    ///Build up the search database of node \c n.
1692    ///
1693    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
1694    ///is the number of the outgoing arcs of \c n.
1695    void refresh(Node n)
1696    {
1697      std::vector<Arc> v;
1698      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1699      if(v.size()) {
1700        std::sort(v.begin(),v.end(),ArcLess(_g));
1701        _head[n]=refreshRec(v,0,v.size()-1);
1702      }
1703      else _head[n]=INVALID;
1704    }
1705    ///Refresh the full data structure.
1706
1707    ///Build up the full search database. In fact, it simply calls
1708    ///\ref refresh(Node) "refresh(n)" for each node \c n.
1709    ///
1710    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1711    ///the number of the arcs in the digraph and <em>D</em> is the maximum
1712    ///out-degree of the digraph.
1713    void refresh()
1714    {
1715      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1716    }
1717
1718    ///Find an arc between two nodes.
1719
1720    ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
1721    ///where <em>d</em> is the number of outgoing arcs of \c s.
1722    ///\param s The source node.
1723    ///\param t The target node.
1724    ///\return An arc from \c s to \c t if there exists,
1725    ///\ref INVALID otherwise.
1726    ///
1727    ///\warning If you change the digraph, refresh() must be called before using
1728    ///this operator. If you change the outgoing arcs of
1729    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1730    Arc operator()(Node s, Node t) const
1731    {
1732      Arc e;
1733      for(e=_head[s];
1734          e!=INVALID&&_g.target(e)!=t;
1735          e = t < _g.target(e)?_left[e]:_right[e]) ;
1736      return e;
1737    }
1738
1739  };
1740
1741  ///Fast look-up of all arcs between given endpoints.
1742
1743  ///This class is the same as \ref ArcLookUp, with the addition
1744  ///that it makes it possible to find all parallel arcs between given
1745  ///endpoints.
1746  ///
1747  ///\warning This class is static, so you should call refresh() (or at
1748  ///least refresh(Node)) to refresh this data structure whenever the
1749  ///digraph changes. This is a time consuming (superlinearly proportional
1750  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1751  ///
1752  ///\tparam GR The type of the underlying digraph.
1753  ///
1754  ///\sa DynArcLookUp
1755  ///\sa ArcLookUp
1756  template<class GR>
1757  class AllArcLookUp : public ArcLookUp<GR>
1758  {
1759    using ArcLookUp<GR>::_g;
1760    using ArcLookUp<GR>::_right;
1761    using ArcLookUp<GR>::_left;
1762    using ArcLookUp<GR>::_head;
1763
1764    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1765
1766    typename GR::template ArcMap<Arc> _next;
1767
1768    Arc refreshNext(Arc head,Arc next=INVALID)
1769    {
1770      if(head==INVALID) return next;
1771      else {
1772        next=refreshNext(_right[head],next);
1773        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1774          ? next : INVALID;
1775        return refreshNext(_left[head],head);
1776      }
1777    }
1778
1779    void refreshNext()
1780    {
1781      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1782    }
1783
1784  public:
1785
1786    /// The Digraph type
1787    typedef GR Digraph;
1788
1789    ///Constructor
1790
1791    ///Constructor.
1792    ///
1793    ///It builds up the search database, which remains valid until the digraph
1794    ///changes.
1795    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
1796
1797    ///Refresh the data structure at a node.
1798
1799    ///Build up the search database of node \c n.
1800    ///
1801    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
1802    ///the number of the outgoing arcs of \c n.
1803    void refresh(Node n)
1804    {
1805      ArcLookUp<GR>::refresh(n);
1806      refreshNext(_head[n]);
1807    }
1808
1809    ///Refresh the full data structure.
1810
1811    ///Build up the full search database. In fact, it simply calls
1812    ///\ref refresh(Node) "refresh(n)" for each node \c n.
1813    ///
1814    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1815    ///the number of the arcs in the digraph and <em>D</em> is the maximum
1816    ///out-degree of the digraph.
1817    void refresh()
1818    {
1819      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1820    }
1821
1822    ///Find an arc between two nodes.
1823
1824    ///Find an arc between two nodes.
1825    ///\param s The source node.
1826    ///\param t The target node.
1827    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1828    ///not given, the operator finds the first appropriate arc.
1829    ///\return An arc from \c s to \c t after \c prev or
1830    ///\ref INVALID if there is no more.
1831    ///
1832    ///For example, you can count the number of arcs from \c u to \c v in the
1833    ///following way.
1834    ///\code
1835    ///AllArcLookUp<ListDigraph> ae(g);
1836    ///...
1837    ///int n = 0;
1838    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
1839    ///\endcode
1840    ///
1841    ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
1842    ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
1843    ///consecutive arcs are found in constant time.
1844    ///
1845    ///\warning If you change the digraph, refresh() must be called before using
1846    ///this operator. If you change the outgoing arcs of
1847    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1848    ///
1849#ifdef DOXYGEN
1850    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1851#else
1852    using ArcLookUp<GR>::operator() ;
1853    Arc operator()(Node s, Node t, Arc prev) const
1854    {
1855      return prev==INVALID?(*this)(s,t):_next[prev];
1856    }
1857#endif
1858
1859  };
1860
1861  /// @}
1862
1863} //namespace lemon
1864
1865#endif
Note: See TracBrowser for help on using the repository browser.