COIN-OR::LEMON - Graph Library

source: lemon/lemon/core.h @ 1188:5ef0ab7b61cd

Last change on this file since 1188:5ef0ab7b61cd was 1188:5ef0ab7b61cd, checked in by Balazs Dezso <deba@…>, 13 years ago

FullBpGraph? implementation (#69)

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