COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/core.h @ 639:72ac25ad276e

Last change on this file since 639:72ac25ad276e was 639:72ac25ad276e, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge

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