COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/core.h @ 1064:fc3854d936f7

Last change on this file since 1064:fc3854d936f7 was 1000:404b98971e1f, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge #449

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