COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 969:6dd226d3dcba

Last change on this file since 969:6dd226d3dcba was 966:dc376822c17d, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Add an undirected() function (#364)

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