COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 301:9db8964f0cf6

Last change on this file since 301:9db8964f0cf6 was 282:dc9e8d2c0df9, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Using from-to order in graph copying tools + doc improvements (ticket #150)

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