RhodeCode

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_GRAPH_UTILS_H

#define LEMON_GRAPH_UTILS_H

#include <iterator>

#include <vector>

#include <map>

#include <cmath>

#include <algorithm>

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

#include <lemon/maps.h>

#include <lemon/bits/traits.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/bits/default_map.h>

///\ingroup gutils

///\file

///\brief Graph utilities.

namespace lemon {

  /// \addtogroup gutils

  /// @{

  ///Creates convenience typedefs for the digraph types and iterators

  ///This \c \#define creates convenience typedefs for the following types

  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,

  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 

  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 

#define DIGRAPH_TYPEDEFS(Digraph)					\

  ///Creates convenience typedefs for the graph types and iterators

  ///This \c \#define creates the same convenience typedefs as defined

  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates

  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,

  ///\c DoubleEdgeMap.

#define GRAPH_TYPEDEFS(Graph)						\

  DIGRAPH_TYPEDEFS(Graph);						\

  /// \brief Function to count the items in the graph.

  ///

  /// This function counts the items (nodes, arcs etc) in the graph.

  /// The complexity of the function is O(n) because

  /// it iterates on all of the items.

  template <typename Graph, typename Item>

  inline int countItems(const Graph& g) {

    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;

    int num = 0;

    for (ItemIt it(g); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  // Node counting:

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct CountNodesSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Node>(g);

      }

    };

    template <typename Graph>

    struct CountNodesSelector<

      Graph, typename 

      enable_if<typename Graph::NodeNumTag, void>::type> 

    {

      static int count(const Graph &g) {

        return g.nodeNum();

      }

    };    

  }

  /// \brief Function to count the nodes in the graph.

  ///

  /// This function counts the nodes in the graph.

  /// The complexity of the function is O(n) but for some

  /// graph structures it is specialized to run in O(1).

  ///

  /// If the graph contains a \e nodeNum() member function and a 

  /// \e NodeNumTag tag then this function calls directly the member

  /// function to query the cardinality of the node set.

  template <typename Graph>

  inline int countNodes(const Graph& g) {

    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);

  }

  // Arc counting:

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct CountArcsSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Arc>(g);

      }

    };

    template <typename Graph>

    struct CountArcsSelector<

      Graph, 

      typename enable_if<typename Graph::ArcNumTag, void>::type> 

    {

      static int count(const Graph &g) {

        return g.arcNum();

      }

    };    

  }

  /// \brief Function to count the arcs in the graph.

  ///

  /// This function counts the arcs in the graph.

  /// The complexity of the function is O(e) but for some

  /// graph structures it is specialized to run in O(1).

  ///

  /// If the graph contains a \e arcNum() member function and a 

  /// \e EdgeNumTag tag then this function calls directly the member

  /// function to query the cardinality of the arc set.

  template <typename Graph>

  inline int countArcs(const Graph& g) {

    return _graph_utils_bits::CountArcsSelector<Graph>::count(g);

  }

  // Edge counting:

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct CountEdgesSelector {

      static int count(const Graph &g) {

        return countItems<Graph, typename Graph::Edge>(g);

      }

    };

    template <typename Graph>

    struct CountEdgesSelector<

      Graph, 

      typename enable_if<typename Graph::EdgeNumTag, void>::type> 

    {

      static int count(const Graph &g) {

        return g.edgeNum();

      }

    };    

  }

  /// \brief Function to count the edges in the graph.

  ///

  /// This function counts the edges in the graph.

  /// The complexity of the function is O(m) but for some

  /// graph structures it is specialized to run in O(1).

  ///

  /// If the graph contains a \e edgeNum() member function and a 

  /// \e EdgeNumTag tag then this function calls directly the member

  /// function to query the cardinality of the edge set.

  template <typename Graph>

  inline int countEdges(const Graph& g) {

    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);

  }

  template <typename Graph, typename DegIt>

  inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {

    int num = 0;

    for (DegIt it(_g, _n); it != INVALID; ++it) {

      ++num;

    }

    return num;

  }

  /// \brief Function to count the number of the out-arcs from node \c n.

  ///

  /// This function counts the number of the out-arcs from node \c n

  /// in the graph.  

  template <typename Graph>

  inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {

    return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);

  }

  /// \brief Function to count the number of the in-arcs to node \c n.

  ///

  /// This function counts the number of the in-arcs to node \c n

  /// in the graph.  

  template <typename Graph>

  inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {

    return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);

  }

  /// \brief Function to count the number of the inc-edges to node \c n.

  ///

  /// This function counts the number of the inc-edges to node \c n

  /// in the graph.  

  template <typename Graph>

  inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {

    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);

  }

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct FindArcSelector {

      typedef typename Graph::Node Node;

      typedef typename Graph::Arc Arc;

      static Arc find(const Graph &g, Node u, Node v, Arc e) {

        if (e == INVALID) {

          g.firstOut(e, u);

        } else {

          g.nextOut(e);

        }

        while (e != INVALID && g.target(e) != v) {

          g.nextOut(e);

        }

        return e;

      }

    };

    template <typename Graph>

    struct FindArcSelector<

      Graph, 

      typename enable_if<typename Graph::FindEdgeTag, void>::type> 

    {

      typedef typename Graph::Node Node;

      typedef typename Graph::Arc Arc;

      static Arc find(const Graph &g, Node u, Node v, Arc prev) {

        return g.findArc(u, v, prev);

      }

    };    

  }

    typedef typename Digraph::Arc Arc;

    virtual void add(const Arc& arc) {

      ++_deg[_digraph.target(arc)];

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        ++_deg[_digraph.target(arcs[i])];

      }

    }

    virtual void erase(const Arc& arc) {

      --_deg[_digraph.target(arc)];

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        --_deg[_digraph.target(arcs[i])];

      }

    }

    virtual void build() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = countInArcs(_digraph, it);

      }      

    }

    virtual void clear() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = 0;

      }

    }

  private:

    const Digraph& _digraph;

    AutoNodeMap _deg;

  };

  /// \brief Map of the node out-degrees.

  ///

  /// This map returns the out-degree of a node. Once it is constructed,

  /// the degrees are stored in a standard NodeMap, so each query is done

  /// in constant time. On the other hand, the values are updated automatically

  /// whenever the digraph changes.

  ///

  /// \warning Besides addNode() and addArc(), a digraph structure may provide

  /// alternative ways to modify the digraph. The correct behavior of OutDegMap

  /// is not guarantied if these additional features are used. For example

  /// the functions \ref ListDigraph::changeSource() "changeSource()",

  /// \ref ListDigraph::changeTarget() "changeTarget()" and

  /// \ref ListDigraph::reverseArc() "reverseArc()"

  /// of \ref ListDigraph will \e not update the degree values correctly.

  ///

  /// \sa InDegMap

  template <typename _Digraph>

  class OutDegMap  

    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>

      ::ItemNotifier::ObserverBase {

  public:

    typedef _Digraph Digraph;

    typedef int Value;

    typedef typename Digraph::Node Key;

    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>

    ::ItemNotifier::ObserverBase Parent;

  private:

    class AutoNodeMap : public DefaultMap<Digraph, Key, int> {

    public:

      typedef DefaultMap<Digraph, Key, int> Parent;

      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}

      virtual void add(const Key& key) {

	Parent::add(key);

	Parent::set(key, 0);

      }

      virtual void add(const std::vector<Key>& keys) {

	Parent::add(keys);

	for (int i = 0; i < int(keys.size()); ++i) {

	  Parent::set(keys[i], 0);

	}

      }

      virtual void build() {

	Parent::build();

	Key it;

	typename Parent::Notifier* nf = Parent::notifier();

	for (nf->first(it); it != INVALID; nf->next(it)) {

	  Parent::set(it, 0);

	}

      }

    };

  public:

    /// \brief Constructor.

    ///

    /// Constructor for creating out-degree map.

    explicit OutDegMap(const Digraph& digraph) 

      : _digraph(digraph), _deg(digraph) {

      Parent::attach(_digraph.notifier(typename Digraph::Arc()));

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = countOutArcs(_digraph, it);

      }

    }

    /// Gives back the out-degree of a Node.

    int operator[](const Key& key) const {

      return _deg[key];

    }

  protected:

    typedef typename Digraph::Arc Arc;

    virtual void add(const Arc& arc) {

      ++_deg[_digraph.source(arc)];

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        ++_deg[_digraph.source(arcs[i])];

      }

    }

    virtual void erase(const Arc& arc) {

      --_deg[_digraph.source(arc)];

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        --_deg[_digraph.source(arcs[i])];

      }

    }

    virtual void build() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = countOutArcs(_digraph, it);

      }      

    }

    virtual void clear() {

      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {

	_deg[it] = 0;

      }

    }

  private:

    const Digraph& _digraph;

    AutoNodeMap _deg;

  };

  ///Dynamic arc look up between given endpoints.

  ///\ingroup gutils

  ///Using this class, you can find an arc in a digraph from a given

  ///source to a given target in amortized time <em>O(log d)</em>,

  ///where <em>d</em> is the out-degree of the source node.

  ///

  ///It is possible to find \e all parallel arcs between two nodes with

  ///the \c findFirst() and \c findNext() members.

  ///

  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your

  ///digraph is not changed so frequently.

  ///

  ///This class uses a self-adjusting binary search tree, Sleator's

  ///and Tarjan's Splay tree for guarantee the logarithmic amortized

  ///time bound for arc lookups. This class also guarantees the

  ///optimal time bound in a constant factor for any distribution of

  ///queries.

  ///

  ///\param G The type of the underlying digraph.  

  ///

  ///\sa ArcLookUp  

  ///\sa AllArcLookUp  

  template<class G>

  class DynArcLookUp 

    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase

  {

  public:

    typedef typename ItemSetTraits<G, typename G::Arc>

    ::ItemNotifier::ObserverBase Parent;

    typedef G Digraph;

  protected:

    class AutoNodeMap : public DefaultMap<G, Node, Arc> {

    public:

      typedef DefaultMap<G, Node, Arc> Parent;

      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}

      virtual void add(const Node& node) {

	Parent::add(node);

	Parent::set(node, INVALID);

      }

      virtual void add(const std::vector<Node>& nodes) {

	Parent::add(nodes);

	for (int i = 0; i < int(nodes.size()); ++i) {

	  Parent::set(nodes[i], INVALID);

	}

      }

      virtual void build() {

	Parent::build();

	Node it;

	typename Parent::Notifier* nf = Parent::notifier();

	for (nf->first(it); it != INVALID; nf->next(it)) {

	  Parent::set(it, INVALID);

	}

      }

    };

    const Digraph &_g;

    AutoNodeMap _head;

    typename Digraph::template ArcMap<Arc> _parent;

    typename Digraph::template ArcMap<Arc> _left;

    typename Digraph::template ArcMap<Arc> _right;

    class ArcLess {

      const Digraph &g;

    public:

      ArcLess(const Digraph &_g) : g(_g) {}

      bool operator()(Arc a,Arc b) const 

      {

	return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database.

    DynArcLookUp(const Digraph &g) 

      : _g(g),_head(g),_parent(g),_left(g),_right(g) 

    { 

      Parent::attach(_g.notifier(typename Digraph::Arc()));

      refresh(); 

    }

  protected:

    virtual void add(const Arc& arc) {

      insert(arc);

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

	insert(arcs[i]);

      }

    }

    virtual void erase(const Arc& arc) {

      remove(arc);

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

	remove(arcs[i]);

      }     

    }

    virtual void build() {

      refresh();

    }

    virtual void clear() {

      for(NodeIt n(_g);n!=INVALID;++n) {

	_head.set(n, INVALID);

      }

    }

    void insert(Arc arc) {

      Node s = _g.source(arc);

      Node t = _g.target(arc);

      _left.set(arc, INVALID);

      _right.set(arc, INVALID);

      Arc e = _head[s];

      if (e == INVALID) {

	_head.set(s, arc);

	_parent.set(arc, INVALID);

	return;

      }

      while (true) {

	if (t < _g.target(e)) {

	  if (_left[e] == INVALID) {

	    _left.set(e, arc);

	    _parent.set(arc, e);

	    splay(arc);

	    return;

	  } else {

	    e = _left[e];

	  }

	} else {

	  if (_right[e] == INVALID) {

	    _right.set(e, arc);

	    _parent.set(arc, e);

	    splay(arc);

	    return;

	  } else {

	    e = _right[e];

	  }

	}

      }

    }

    void remove(Arc arc) {

      if (_left[arc] == INVALID) {

	if (_right[arc] != INVALID) {

	  _parent.set(_right[arc], _parent[arc]);

	}

	if (_parent[arc] != INVALID) {

	  if (_left[_parent[arc]] == arc) {

	    _left.set(_parent[arc], _right[arc]);

	  } else {

	    _right.set(_parent[arc], _right[arc]);

	  }

	} else {

	  _head.set(_g.source(arc), _right[arc]);

	}

      } else if (_right[arc] == INVALID) {

	_parent.set(_left[arc], _parent[arc]);

	if (_parent[arc] != INVALID) {

	  if (_left[_parent[arc]] == arc) {

	    _left.set(_parent[arc], _left[arc]);

	  } else {

	    _right.set(_parent[arc], _left[arc]);

	  }

	} else {

	  _head.set(_g.source(arc), _left[arc]);

	}

      } else {

	Arc e = _left[arc];

	if (_right[e] != INVALID) {

	  e = _right[e];	  

	  while (_right[e] != INVALID) {

	    e = _right[e];

	  }

	  Arc s = _parent[e];

	  _right.set(_parent[e], _left[e]);

	  if (_left[e] != INVALID) {

	    _parent.set(_left[e], _parent[e]);

	  }

	  _left.set(e, _left[arc]);

	  _parent.set(_left[arc], e);

	  _right.set(e, _right[arc]);

	  _parent.set(_right[arc], e);

	  _parent.set(e, _parent[arc]);

	  if (_parent[arc] != INVALID) {

	    if (_left[_parent[arc]] == arc) {

	      _left.set(_parent[arc], e);

	    } else {

	      _right.set(_parent[arc], e);

	    }

	  }

	  splay(s);

	} else {

	  _right.set(e, _right[arc]);

	  _parent.set(_right[arc], e);

	  if (_parent[arc] != INVALID) {

	    if (_left[_parent[arc]] == arc) {

	      _left.set(_parent[arc], e);

	    } else {

	      _right.set(_parent[arc], e);

	    }

	  _left.set(_parent[v], v);

	}

      }

      if (_left[w] != INVALID){

	_parent.set(_left[w], w);

      }

    }

    void zag(Arc v) {        

      Arc w = _parent[v];

      _parent.set(v, _parent[w]);

      _parent.set(w, v);

      _right.set(w, _left[v]);

      _left.set(v, w);

      if (_parent[v] != INVALID){

	if (_left[_parent[v]] == w) {

	  _left.set(_parent[v], v);

	} else {

	  _right.set(_parent[v], v);

	}

      }

      if (_right[w] != INVALID){

	_parent.set(_right[w], w);

      }

    }

    void splay(Arc v) {

      while (_parent[v] != INVALID) {

	if (v == _left[_parent[v]]) {

	  if (_parent[_parent[v]] == INVALID) {

	    zig(v);

	  } else {

	    if (_parent[v] == _left[_parent[_parent[v]]]) {

	      zig(_parent[v]);

	      zig(v);

	    } else {

	      zig(v);

	      zag(v);

	    }

	  }

	} else {

	  if (_parent[_parent[v]] == INVALID) {

	    zag(v);

	  } else {

	    if (_parent[v] == _left[_parent[_parent[v]]]) {

	      zag(v);

	      zig(v);

	    } else {

	      zag(_parent[v]);

	      zag(v);

	    }

	  }

	}

      }

      _head[_g.source(v)] = v;

    }

  public:

    ///Find an arc between two nodes.

    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where

    /// <em>d</em> is the number of outgoing arcs of \c s.

    ///\param s The source node

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    Arc operator()(Node s, Node t) const

    {

      Arc a = _head[s];

      while (true) {

	if (_g.target(a) == t) {

	  const_cast<DynArcLookUp&>(*this).splay(a);

	  return a;

	} else if (t < _g.target(a)) {

	  if (_left[a] == INVALID) {

	    const_cast<DynArcLookUp&>(*this).splay(a);

	    return INVALID;

	  } else {

	    a = _left[a];

	  }

	} else  {

	  if (_right[a] == INVALID) {

	    const_cast<DynArcLookUp&>(*this).splay(a);

	    return INVALID;

	  } else {

	    a = _right[a];

	  }

	}

      }

    }

    ///Find the first arc between two nodes.

    ///Find the first arc between two nodes in time

    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of

    /// outgoing arcs of \c s.  

    ///\param s The source node 

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists, \ref INVALID

    /// otherwise.

    Arc findFirst(Node s, Node t) const

    {

      Arc a = _head[s];

      Arc r = INVALID;

      while (true) {

	if (_g.target(a) < t) {

	  if (_right[a] == INVALID) {

	    const_cast<DynArcLookUp&>(*this).splay(a);

	    return r;

	  } else {

	    a = _right[a];

	  }

	} else {

	  if (_g.target(a) == t) {

	    r = a;

	  }

	  if (_left[a] == INVALID) {

	    const_cast<DynArcLookUp&>(*this).splay(a);

	    return r;

	  } else {

	    a = _left[a];

	  }

	}

      }

    }

    ///Find the next arc between two nodes.

    ///Find the next arc between two nodes in time

    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of

    /// outgoing arcs of \c s.  

    ///\param s The source node 

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists, \ref INVALID

    /// otherwise.

    ///\note If \c e is not the result of the previous \c findFirst()

    ///operation then the amorized time bound can not be guaranteed.

#ifdef DOXYGEN

    Arc findNext(Node s, Node t, Arc a) const

#else

    Arc findNext(Node, Node t, Arc a) const

#endif

    {

      if (_right[a] != INVALID) {

	a = _right[a];

	while (_left[a] != INVALID) {

	  a = _left[a];

	}

	const_cast<DynArcLookUp&>(*this).splay(a);

      } else {

	while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {

	  a = _parent[a];

	}

	if (_parent[a] == INVALID) {

	  return INVALID;

	} else {

	  a = _parent[a];

	  const_cast<DynArcLookUp&>(*this).splay(a);

	}

      }

      if (_g.target(a) == t) return a;

      else return INVALID;    

    }

  };

  ///Fast arc look up between given endpoints.

  ///\ingroup gutils

  ///Using this class, you can find an arc in a digraph from a given

  ///source to a given target in time <em>O(log d)</em>,

  ///where <em>d</em> is the out-degree of the source node.

  ///

  ///It is not possible to find \e all parallel arcs between two nodes.

  ///Use \ref AllArcLookUp for this purpose.

  ///

  ///\warning This class is static, so you should refresh() (or at least

  ///refresh(Node)) this data structure

  ///whenever the digraph changes. This is a time consuming (superlinearly

  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).

  ///

  ///\param G The type of the underlying digraph.

  ///

  ///\sa DynArcLookUp

  ///\sa AllArcLookUp  

  template<class G>

  class ArcLookUp 

  {

  public:

    typedef G Digraph;

  protected:

    const Digraph &_g;

    typename Digraph::template NodeMap<Arc> _head;

    typename Digraph::template ArcMap<Arc> _left;

    typename Digraph::template ArcMap<Arc> _right;

    class ArcLess {

      const Digraph &g;

    public:

      ArcLess(const Digraph &_g) : g(_g) {}

      bool operator()(Arc a,Arc b) const 

      {

	return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database, which remains valid until the digraph

    ///changes.

    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}

  private:

    Arc refreshRec(std::vector<Arc> &v,int a,int b) 

    {

      int m=(a+b)/2;

      Arc me=v[m];

      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;

      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;

      return me;

    }

  public:

    ///Refresh the data structure at a node.

    ///Build up the search database of node \c n.

    ///

    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

    ///the number of the outgoing arcs of \c n.

    void refresh(Node n) 

    {

      std::vector<Arc> v;

      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);

      if(v.size()) {

	std::sort(v.begin(),v.end(),ArcLess(_g));

	_head[n]=refreshRec(v,0,v.size()-1);

      }

      else _head[n]=INVALID;

    }

    ///Refresh the full data structure.

    ///Build up the full search database. In fact, it simply calls

    ///\ref refresh(Node) "refresh(n)" for each node \c n.

    ///

    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is

    ///the number of the arcs of \c n and <em>D</em> is the maximum

    ///out-degree of the digraph.

    void refresh() 

    {

      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    }

    ///Find an arc between two nodes.

    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where

    /// <em>d</em> is the number of outgoing arcs of \c s.

    ///\param s The source node

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then

    ///\ref refresh(Node) "refresh(n)" is enough.

    ///

    Arc operator()(Node s, Node t) const

    {

      Arc e;

      for(e=_head[s];

	  e!=INVALID&&_g.target(e)!=t;

	  e = t < _g.target(e)?_left[e]:_right[e]) ;

      return e;

    }

  };

  ///Fast look up of all arcs between given endpoints.

  ///\ingroup gutils

  ///This class is the same as \ref ArcLookUp, with the addition

  ///that it makes it possible to find all arcs between given endpoints.

  ///

  ///\warning This class is static, so you should refresh() (or at least

  ///refresh(Node)) this data structure

  ///whenever the digraph changes. This is a time consuming (superlinearly

  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).

  ///

  ///\param G The type of the underlying digraph.

  ///

  ///\sa DynArcLookUp

  ///\sa ArcLookUp  

  template<class G>

  class AllArcLookUp : public ArcLookUp<G>

  {

    using ArcLookUp<G>::_g;

    using ArcLookUp<G>::_right;

    using ArcLookUp<G>::_left;

    using ArcLookUp<G>::_head;

    typedef G Digraph;

    typename Digraph::template ArcMap<Arc> _next;

    Arc refreshNext(Arc head,Arc next=INVALID)

    {

      if(head==INVALID) return next;

      else {

	next=refreshNext(_right[head],next);

// 	_next[head]=next;

	_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))

	  ? next : INVALID;

	return refreshNext(_left[head],head);

      }

    }

    void refreshNext()

    {

      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);

    }

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database, which remains valid until the digraph

    ///changes.

    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}

    ///Refresh the data structure at a node.

    ///Build up the search database of node \c n.

    ///

    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

    ///the number of the outgoing arcs of \c n.

    void refresh(Node n) 

    {

      ArcLookUp<G>::refresh(n);

      refreshNext(_head[n]);