COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/core.h @ 227:33f8d69e642a

Last change on this file since 227:33f8d69e642a was 220:a5d8c039f218, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

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