COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/core.h @ 395:8a144437db7d

Last change on this file since 395:8a144437db7d was 379:39aaeea2d471, checked in by Alpar Juttner <alpar@…>, 11 years ago

Include /lemon/config.h globally (#230)

File size: 58.5 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-2008
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/core.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 _Graph>
1038  class ConArcIt : public _Graph::Arc {
1039  public:
1040
1041    typedef _Graph Graph;
1042    typedef typename Graph::Arc Parent;
1043
1044    typedef typename Graph::Arc Arc;
1045    typedef typename Graph::Node Node;
1046
1047    /// \brief Constructor.
1048    ///
1049    /// Construct a new ConArcIt iterating on the arcs that
1050    /// connects nodes \c u and \c v.
1051    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1052      Parent::operator=(findArc(_graph, u, v));
1053    }
1054
1055    /// \brief Constructor.
1056    ///
1057    /// Construct a new ConArcIt that continues the iterating from arc \c a.
1058    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1059
1060    /// \brief Increment operator.
1061    ///
1062    /// It increments the iterator and gives back the next arc.
1063    ConArcIt& operator++() {
1064      Parent::operator=(findArc(_graph, _graph.source(*this),
1065                                _graph.target(*this), *this));
1066      return *this;
1067    }
1068  private:
1069    const Graph& _graph;
1070  };
1071
1072  namespace _core_bits {
1073
1074    template <typename Graph, typename Enable = void>
1075    struct FindEdgeSelector {
1076      typedef typename Graph::Node Node;
1077      typedef typename Graph::Edge Edge;
1078      static Edge find(const Graph &g, Node u, Node v, Edge e) {
1079        bool b;
1080        if (u != v) {
1081          if (e == INVALID) {
1082            g.firstInc(e, b, u);
1083          } else {
1084            b = g.u(e) == u;
1085            g.nextInc(e, b);
1086          }
1087          while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
1088            g.nextInc(e, b);
1089          }
1090        } else {
1091          if (e == INVALID) {
1092            g.firstInc(e, b, u);
1093          } else {
1094            b = true;
1095            g.nextInc(e, b);
1096          }
1097          while (e != INVALID && (!b || g.v(e) != v)) {
1098            g.nextInc(e, b);
1099          }
1100        }
1101        return e;
1102      }
1103    };
1104
1105    template <typename Graph>
1106    struct FindEdgeSelector<
1107      Graph,
1108      typename enable_if<typename Graph::FindEdgeTag, void>::type>
1109    {
1110      typedef typename Graph::Node Node;
1111      typedef typename Graph::Edge Edge;
1112      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1113        return g.findEdge(u, v, prev);
1114      }
1115    };
1116  }
1117
1118  /// \brief Find an edge between two nodes of a graph.
1119  ///
1120  /// This function finds an edge from node \c u to node \c v in graph \c g.
1121  /// If node \c u and node \c v is equal then each loop edge
1122  /// will be enumerated once.
1123  ///
1124  /// If \c prev is \ref INVALID (this is the default value), then
1125  /// it finds the first edge from \c u to \c v. Otherwise it looks for
1126  /// the next edge from \c u to \c v after \c prev.
1127  /// \return The found edge or \ref INVALID if there is no such an edge.
1128  ///
1129  /// Thus you can iterate through each edge between \c u and \c v
1130  /// as it follows.
1131  ///\code
1132  /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1133  ///   ...
1134  /// }
1135  ///\endcode
1136  ///
1137  /// \note \ref ConEdgeIt provides iterator interface for the same
1138  /// functionality.
1139  ///
1140  ///\sa ConEdgeIt
1141  template <typename Graph>
1142  inline typename Graph::Edge
1143  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1144            typename Graph::Edge p = INVALID) {
1145    return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1146  }
1147
1148  /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1149  ///
1150  /// Iterator for iterating on parallel edges connecting the same nodes.
1151  /// It is a higher level interface for the findEdge() function. You can
1152  /// use it the following way:
1153  ///\code
1154  /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1155  ///   ...
1156  /// }
1157  ///\endcode
1158  ///
1159  ///\sa findEdge()
1160  template <typename _Graph>
1161  class ConEdgeIt : public _Graph::Edge {
1162  public:
1163
1164    typedef _Graph Graph;
1165    typedef typename Graph::Edge Parent;
1166
1167    typedef typename Graph::Edge Edge;
1168    typedef typename Graph::Node Node;
1169
1170    /// \brief Constructor.
1171    ///
1172    /// Construct a new ConEdgeIt iterating on the edges that
1173    /// connects nodes \c u and \c v.
1174    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1175      Parent::operator=(findEdge(_graph, _u, _v));
1176    }
1177
1178    /// \brief Constructor.
1179    ///
1180    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1181    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1182
1183    /// \brief Increment operator.
1184    ///
1185    /// It increments the iterator and gives back the next edge.
1186    ConEdgeIt& operator++() {
1187      Parent::operator=(findEdge(_graph, _u, _v, *this));
1188      return *this;
1189    }
1190  private:
1191    const Graph& _graph;
1192    Node _u, _v;
1193  };
1194
1195
1196  ///Dynamic arc look-up between given endpoints.
1197
1198  ///Using this class, you can find an arc in a digraph from a given
1199  ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1200  ///where <em>d</em> is the out-degree of the source node.
1201  ///
1202  ///It is possible to find \e all parallel arcs between two nodes with
1203  ///the \c operator() member.
1204  ///
1205  ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1206  ///\ref AllArcLookUp if your digraph is not changed so frequently.
1207  ///
1208  ///This class uses a self-adjusting binary search tree, the Splay tree
1209  ///of Sleator and Tarjan to guarantee the logarithmic amortized
1210  ///time bound for arc look-ups. This class also guarantees the
1211  ///optimal time bound in a constant factor for any distribution of
1212  ///queries.
1213  ///
1214  ///\tparam G The type of the underlying digraph.
1215  ///
1216  ///\sa ArcLookUp
1217  ///\sa AllArcLookUp
1218  template<class G>
1219  class DynArcLookUp
1220    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
1221  {
1222  public:
1223    typedef typename ItemSetTraits<G, typename G::Arc>
1224    ::ItemNotifier::ObserverBase Parent;
1225
1226    TEMPLATE_DIGRAPH_TYPEDEFS(G);
1227    typedef G Digraph;
1228
1229  protected:
1230
1231    class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
1232    public:
1233
1234      typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
1235
1236      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
1237
1238      virtual void add(const Node& node) {
1239        Parent::add(node);
1240        Parent::set(node, INVALID);
1241      }
1242
1243      virtual void add(const std::vector<Node>& nodes) {
1244        Parent::add(nodes);
1245        for (int i = 0; i < int(nodes.size()); ++i) {
1246          Parent::set(nodes[i], INVALID);
1247        }
1248      }
1249
1250      virtual void build() {
1251        Parent::build();
1252        Node it;
1253        typename Parent::Notifier* nf = Parent::notifier();
1254        for (nf->first(it); it != INVALID; nf->next(it)) {
1255          Parent::set(it, INVALID);
1256        }
1257      }
1258    };
1259
1260    const Digraph &_g;
1261    AutoNodeMap _head;
1262    typename Digraph::template ArcMap<Arc> _parent;
1263    typename Digraph::template ArcMap<Arc> _left;
1264    typename Digraph::template ArcMap<Arc> _right;
1265
1266    class ArcLess {
1267      const Digraph &g;
1268    public:
1269      ArcLess(const Digraph &_g) : g(_g) {}
1270      bool operator()(Arc a,Arc b) const
1271      {
1272        return g.target(a)<g.target(b);
1273      }
1274    };
1275
1276  public:
1277
1278    ///Constructor
1279
1280    ///Constructor.
1281    ///
1282    ///It builds up the search database.
1283    DynArcLookUp(const Digraph &g)
1284      : _g(g),_head(g),_parent(g),_left(g),_right(g)
1285    {
1286      Parent::attach(_g.notifier(typename Digraph::Arc()));
1287      refresh();
1288    }
1289
1290  protected:
1291
1292    virtual void add(const Arc& arc) {
1293      insert(arc);
1294    }
1295
1296    virtual void add(const std::vector<Arc>& arcs) {
1297      for (int i = 0; i < int(arcs.size()); ++i) {
1298        insert(arcs[i]);
1299      }
1300    }
1301
1302    virtual void erase(const Arc& arc) {
1303      remove(arc);
1304    }
1305
1306    virtual void erase(const std::vector<Arc>& arcs) {
1307      for (int i = 0; i < int(arcs.size()); ++i) {
1308        remove(arcs[i]);
1309      }
1310    }
1311
1312    virtual void build() {
1313      refresh();
1314    }
1315
1316    virtual void clear() {
1317      for(NodeIt n(_g);n!=INVALID;++n) {
1318        _head.set(n, INVALID);
1319      }
1320    }
1321
1322    void insert(Arc arc) {
1323      Node s = _g.source(arc);
1324      Node t = _g.target(arc);
1325      _left.set(arc, INVALID);
1326      _right.set(arc, INVALID);
1327
1328      Arc e = _head[s];
1329      if (e == INVALID) {
1330        _head.set(s, arc);
1331        _parent.set(arc, INVALID);
1332        return;
1333      }
1334      while (true) {
1335        if (t < _g.target(e)) {
1336          if (_left[e] == INVALID) {
1337            _left.set(e, arc);
1338            _parent.set(arc, e);
1339            splay(arc);
1340            return;
1341          } else {
1342            e = _left[e];
1343          }
1344        } else {
1345          if (_right[e] == INVALID) {
1346            _right.set(e, arc);
1347            _parent.set(arc, e);
1348            splay(arc);
1349            return;
1350          } else {
1351            e = _right[e];
1352          }
1353        }
1354      }
1355    }
1356
1357    void remove(Arc arc) {
1358      if (_left[arc] == INVALID) {
1359        if (_right[arc] != INVALID) {
1360          _parent.set(_right[arc], _parent[arc]);
1361        }
1362        if (_parent[arc] != INVALID) {
1363          if (_left[_parent[arc]] == arc) {
1364            _left.set(_parent[arc], _right[arc]);
1365          } else {
1366            _right.set(_parent[arc], _right[arc]);
1367          }
1368        } else {
1369          _head.set(_g.source(arc), _right[arc]);
1370        }
1371      } else if (_right[arc] == INVALID) {
1372        _parent.set(_left[arc], _parent[arc]);
1373        if (_parent[arc] != INVALID) {
1374          if (_left[_parent[arc]] == arc) {
1375            _left.set(_parent[arc], _left[arc]);
1376          } else {
1377            _right.set(_parent[arc], _left[arc]);
1378          }
1379        } else {
1380          _head.set(_g.source(arc), _left[arc]);
1381        }
1382      } else {
1383        Arc e = _left[arc];
1384        if (_right[e] != INVALID) {
1385          e = _right[e];
1386          while (_right[e] != INVALID) {
1387            e = _right[e];
1388          }
1389          Arc s = _parent[e];
1390          _right.set(_parent[e], _left[e]);
1391          if (_left[e] != INVALID) {
1392            _parent.set(_left[e], _parent[e]);
1393          }
1394
1395          _left.set(e, _left[arc]);
1396          _parent.set(_left[arc], e);
1397          _right.set(e, _right[arc]);
1398          _parent.set(_right[arc], e);
1399
1400          _parent.set(e, _parent[arc]);
1401          if (_parent[arc] != INVALID) {
1402            if (_left[_parent[arc]] == arc) {
1403              _left.set(_parent[arc], e);
1404            } else {
1405              _right.set(_parent[arc], e);
1406            }
1407          }
1408          splay(s);
1409        } else {
1410          _right.set(e, _right[arc]);
1411          _parent.set(_right[arc], e);
1412          _parent.set(e, _parent[arc]);
1413
1414          if (_parent[arc] != INVALID) {
1415            if (_left[_parent[arc]] == arc) {
1416              _left.set(_parent[arc], e);
1417            } else {
1418              _right.set(_parent[arc], e);
1419            }
1420          } else {
1421            _head.set(_g.source(arc), e);
1422          }
1423        }
1424      }
1425    }
1426
1427    Arc refreshRec(std::vector<Arc> &v,int a,int b)
1428    {
1429      int m=(a+b)/2;
1430      Arc me=v[m];
1431      if (a < m) {
1432        Arc left = refreshRec(v,a,m-1);
1433        _left.set(me, left);
1434        _parent.set(left, me);
1435      } else {
1436        _left.set(me, INVALID);
1437      }
1438      if (m < b) {
1439        Arc right = refreshRec(v,m+1,b);
1440        _right.set(me, right);
1441        _parent.set(right, me);
1442      } else {
1443        _right.set(me, INVALID);
1444      }
1445      return me;
1446    }
1447
1448    void refresh() {
1449      for(NodeIt n(_g);n!=INVALID;++n) {
1450        std::vector<Arc> v;
1451        for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
1452        if (!v.empty()) {
1453          std::sort(v.begin(),v.end(),ArcLess(_g));
1454          Arc head = refreshRec(v,0,v.size()-1);
1455          _head.set(n, head);
1456          _parent.set(head, INVALID);
1457        }
1458        else _head.set(n, INVALID);
1459      }
1460    }
1461
1462    void zig(Arc v) {
1463      Arc w = _parent[v];
1464      _parent.set(v, _parent[w]);
1465      _parent.set(w, v);
1466      _left.set(w, _right[v]);
1467      _right.set(v, w);
1468      if (_parent[v] != INVALID) {
1469        if (_right[_parent[v]] == w) {
1470          _right.set(_parent[v], v);
1471        } else {
1472          _left.set(_parent[v], v);
1473        }
1474      }
1475      if (_left[w] != INVALID){
1476        _parent.set(_left[w], w);
1477      }
1478    }
1479
1480    void zag(Arc v) {
1481      Arc w = _parent[v];
1482      _parent.set(v, _parent[w]);
1483      _parent.set(w, v);
1484      _right.set(w, _left[v]);
1485      _left.set(v, w);
1486      if (_parent[v] != INVALID){
1487        if (_left[_parent[v]] == w) {
1488          _left.set(_parent[v], v);
1489        } else {
1490          _right.set(_parent[v], v);
1491        }
1492      }
1493      if (_right[w] != INVALID){
1494        _parent.set(_right[w], w);
1495      }
1496    }
1497
1498    void splay(Arc v) {
1499      while (_parent[v] != INVALID) {
1500        if (v == _left[_parent[v]]) {
1501          if (_parent[_parent[v]] == INVALID) {
1502            zig(v);
1503          } else {
1504            if (_parent[v] == _left[_parent[_parent[v]]]) {
1505              zig(_parent[v]);
1506              zig(v);
1507            } else {
1508              zig(v);
1509              zag(v);
1510            }
1511          }
1512        } else {
1513          if (_parent[_parent[v]] == INVALID) {
1514            zag(v);
1515          } else {
1516            if (_parent[v] == _left[_parent[_parent[v]]]) {
1517              zag(v);
1518              zig(v);
1519            } else {
1520              zag(_parent[v]);
1521              zag(v);
1522            }
1523          }
1524        }
1525      }
1526      _head[_g.source(v)] = v;
1527    }
1528
1529
1530  public:
1531
1532    ///Find an arc between two nodes.
1533
1534    ///Find an arc between two nodes.
1535    ///\param s The source node.
1536    ///\param t The target node.
1537    ///\param p The previous arc between \c s and \c t. It it is INVALID or
1538    ///not given, the operator finds the first appropriate arc.
1539    ///\return An arc from \c s to \c t after \c p or
1540    ///\ref INVALID if there is no more.
1541    ///
1542    ///For example, you can count the number of arcs from \c u to \c v in the
1543    ///following way.
1544    ///\code
1545    ///DynArcLookUp<ListDigraph> ae(g);
1546    ///...
1547    ///int n = 0;
1548    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
1549    ///\endcode
1550    ///
1551    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
1552    ///amortized time, specifically, the time complexity of the lookups
1553    ///is equal to the optimal search tree implementation for the
1554    ///current query distribution in a constant factor.
1555    ///
1556    ///\note This is a dynamic data structure, therefore the data
1557    ///structure is updated after each graph alteration. Thus although
1558    ///this data structure is theoretically faster than \ref ArcLookUp
1559    ///and \ref AllArcLookUp, it often provides worse performance than
1560    ///them.
1561    Arc operator()(Node s, Node t, Arc p = INVALID) const  {
1562      if (p == INVALID) {
1563        Arc a = _head[s];
1564        if (a == INVALID) return INVALID;
1565        Arc r = INVALID;
1566        while (true) {
1567          if (_g.target(a) < t) {
1568            if (_right[a] == INVALID) {
1569              const_cast<DynArcLookUp&>(*this).splay(a);
1570              return r;
1571            } else {
1572              a = _right[a];
1573            }
1574          } else {
1575            if (_g.target(a) == t) {
1576              r = a;
1577            }
1578            if (_left[a] == INVALID) {
1579              const_cast<DynArcLookUp&>(*this).splay(a);
1580              return r;
1581            } else {
1582              a = _left[a];
1583            }
1584          }
1585        }
1586      } else {
1587        Arc a = p;
1588        if (_right[a] != INVALID) {
1589          a = _right[a];
1590          while (_left[a] != INVALID) {
1591            a = _left[a];
1592          }
1593          const_cast<DynArcLookUp&>(*this).splay(a);
1594        } else {
1595          while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
1596            a = _parent[a];
1597          }
1598          if (_parent[a] == INVALID) {
1599            return INVALID;
1600          } else {
1601            a = _parent[a];
1602            const_cast<DynArcLookUp&>(*this).splay(a);
1603          }
1604        }
1605        if (_g.target(a) == t) return a;
1606        else return INVALID;
1607      }
1608    }
1609
1610  };
1611
1612  ///Fast arc look-up between given endpoints.
1613
1614  ///Using this class, you can find an arc in a digraph from a given
1615  ///source to a given target in time <em>O</em>(log<em>d</em>),
1616  ///where <em>d</em> is the out-degree of the source node.
1617  ///
1618  ///It is not possible to find \e all parallel arcs between two nodes.
1619  ///Use \ref AllArcLookUp for this purpose.
1620  ///
1621  ///\warning This class is static, so you should call refresh() (or at
1622  ///least refresh(Node)) to refresh this data structure whenever the
1623  ///digraph changes. This is a time consuming (superlinearly proportional
1624  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1625  ///
1626  ///\tparam G The type of the underlying digraph.
1627  ///
1628  ///\sa DynArcLookUp
1629  ///\sa AllArcLookUp
1630  template<class G>
1631  class ArcLookUp
1632  {
1633  public:
1634    TEMPLATE_DIGRAPH_TYPEDEFS(G);
1635    typedef G Digraph;
1636
1637  protected:
1638    const Digraph &_g;
1639    typename Digraph::template NodeMap<Arc> _head;
1640    typename Digraph::template ArcMap<Arc> _left;
1641    typename Digraph::template ArcMap<Arc> _right;
1642
1643    class ArcLess {
1644      const Digraph &g;
1645    public:
1646      ArcLess(const Digraph &_g) : g(_g) {}
1647      bool operator()(Arc a,Arc b) const
1648      {
1649        return g.target(a)<g.target(b);
1650      }
1651    };
1652
1653  public:
1654
1655    ///Constructor
1656
1657    ///Constructor.
1658    ///
1659    ///It builds up the search database, which remains valid until the digraph
1660    ///changes.
1661    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1662
1663  private:
1664    Arc refreshRec(std::vector<Arc> &v,int a,int b)
1665    {
1666      int m=(a+b)/2;
1667      Arc me=v[m];
1668      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;
1669      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;
1670      return me;
1671    }
1672  public:
1673    ///Refresh the search data structure at a node.
1674
1675    ///Build up the search database of node \c n.
1676    ///
1677    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
1678    ///is the number of the outgoing arcs of \c n.
1679    void refresh(Node n)
1680    {
1681      std::vector<Arc> v;
1682      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1683      if(v.size()) {
1684        std::sort(v.begin(),v.end(),ArcLess(_g));
1685        _head[n]=refreshRec(v,0,v.size()-1);
1686      }
1687      else _head[n]=INVALID;
1688    }
1689    ///Refresh the full data structure.
1690
1691    ///Build up the full search database. In fact, it simply calls
1692    ///\ref refresh(Node) "refresh(n)" for each node \c n.
1693    ///
1694    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1695    ///the number of the arcs in the digraph and <em>D</em> is the maximum
1696    ///out-degree of the digraph.
1697    void refresh()
1698    {
1699      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1700    }
1701
1702    ///Find an arc between two nodes.
1703
1704    ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
1705    ///where <em>d</em> is the number of outgoing arcs of \c s.
1706    ///\param s The source node.
1707    ///\param t The target node.
1708    ///\return An arc from \c s to \c t if there exists,
1709    ///\ref INVALID otherwise.
1710    ///
1711    ///\warning If you change the digraph, refresh() must be called before using
1712    ///this operator. If you change the outgoing arcs of
1713    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1714    Arc operator()(Node s, Node t) const
1715    {
1716      Arc e;
1717      for(e=_head[s];
1718          e!=INVALID&&_g.target(e)!=t;
1719          e = t < _g.target(e)?_left[e]:_right[e]) ;
1720      return e;
1721    }
1722
1723  };
1724
1725  ///Fast look-up of all arcs between given endpoints.
1726
1727  ///This class is the same as \ref ArcLookUp, with the addition
1728  ///that it makes it possible to find all parallel arcs between given
1729  ///endpoints.
1730  ///
1731  ///\warning This class is static, so you should call refresh() (or at
1732  ///least refresh(Node)) to refresh this data structure whenever the
1733  ///digraph changes. This is a time consuming (superlinearly proportional
1734  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1735  ///
1736  ///\tparam G The type of the underlying digraph.
1737  ///
1738  ///\sa DynArcLookUp
1739  ///\sa ArcLookUp
1740  template<class G>
1741  class AllArcLookUp : public ArcLookUp<G>
1742  {
1743    using ArcLookUp<G>::_g;
1744    using ArcLookUp<G>::_right;
1745    using ArcLookUp<G>::_left;
1746    using ArcLookUp<G>::_head;
1747
1748    TEMPLATE_DIGRAPH_TYPEDEFS(G);
1749    typedef G Digraph;
1750
1751    typename Digraph::template ArcMap<Arc> _next;
1752
1753    Arc refreshNext(Arc head,Arc next=INVALID)
1754    {
1755      if(head==INVALID) return next;
1756      else {
1757        next=refreshNext(_right[head],next);
1758        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1759          ? next : INVALID;
1760        return refreshNext(_left[head],head);
1761      }
1762    }
1763
1764    void refreshNext()
1765    {
1766      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1767    }
1768
1769  public:
1770    ///Constructor
1771
1772    ///Constructor.
1773    ///
1774    ///It builds up the search database, which remains valid until the digraph
1775    ///changes.
1776    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
1777
1778    ///Refresh the data structure at a node.
1779
1780    ///Build up the search database of node \c n.
1781    ///
1782    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
1783    ///the number of the outgoing arcs of \c n.
1784    void refresh(Node n)
1785    {
1786      ArcLookUp<G>::refresh(n);
1787      refreshNext(_head[n]);
1788    }
1789
1790    ///Refresh the full data structure.
1791
1792    ///Build up the full search database. In fact, it simply calls
1793    ///\ref refresh(Node) "refresh(n)" for each node \c n.
1794    ///
1795    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1796    ///the number of the arcs in the digraph and <em>D</em> is the maximum
1797    ///out-degree of the digraph.
1798    void refresh()
1799    {
1800      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1801    }
1802
1803    ///Find an arc between two nodes.
1804
1805    ///Find an arc between two nodes.
1806    ///\param s The source node.
1807    ///\param t The target node.
1808    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1809    ///not given, the operator finds the first appropriate arc.
1810    ///\return An arc from \c s to \c t after \c prev or
1811    ///\ref INVALID if there is no more.
1812    ///
1813    ///For example, you can count the number of arcs from \c u to \c v in the
1814    ///following way.
1815    ///\code
1816    ///AllArcLookUp<ListDigraph> ae(g);
1817    ///...
1818    ///int n = 0;
1819    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
1820    ///\endcode
1821    ///
1822    ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
1823    ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
1824    ///consecutive arcs are found in constant time.
1825    ///
1826    ///\warning If you change the digraph, refresh() must be called before using
1827    ///this operator. If you change the outgoing arcs of
1828    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1829    ///
1830#ifdef DOXYGEN
1831    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1832#else
1833    using ArcLookUp<G>::operator() ;
1834    Arc operator()(Node s, Node t, Arc prev) const
1835    {
1836      return prev==INVALID?(*this)(s,t):_next[prev];
1837    }
1838#endif
1839
1840  };
1841
1842  /// @}
1843
1844} //namespace lemon
1845
1846#endif
Note: See TracBrowser for help on using the repository browser.