DynArcLookUp

Declared in lemon/core.h, in the group Basic Graph Utilities; the same class on the Doxygen site.

template< typename GR >
class DynArcLookUp : protected ObserverBase

Dynamic arc look-up between given endpoints.

Using this class, you can find an arc in a digraph from a given source to a given target in amortized time O(logd), where d is the out-degree of the source node.

It is possible to find all parallel arcs between two nodes with the operator() member.

This is a dynamic data structure. Consider to use ArcLookUp or AllArcLookUp if your digraph is not changed so frequently.

This class uses a self-adjusting binary search tree, the Splay tree of Sleator and Tarjan to guarantee the logarithmic amortized time bound for arc look-ups. This class also guarantees the optimal time bound in a constant factor for any distribution of queries.

See also

ArcLookUp

See also

AllArcLookUp

Template Parameters:

GR – The type of the underlying digraph.

Public Types

typedef GR Digraph

The Digraph type.

Public Functions

inline DynArcLookUp( const Digraph & g )

Constructor.

It builds up the search database.

inline Arc operator()( Node s , Node t , Arc p = INVALID ) const

Find an arc between two nodes.

For example, you can count the number of arcs from

u to v in the following way.
DynArcLookUp< ListDigraph > ae( g );
... int n = 0;
for( Arc a = ae( u , v ) ; a != INVALID ; a = ae( u , v , a ) )
 n++;

Finding the first arc, with p not given, takes at most amortized time O(logd), specifically, the time complexity of these lookups is equal to the optimal search tree implementation for the current query distribution in a constant factor. Finding the arc after p may walk from p up to its successor without splaying that path, hence it takes amortized time O(h + logd), where h ≤ d is the depth of p in the search tree of s.

Note

This is a dynamic data structure, therefore the data structure is updated after each graph alteration. Thus although this data structure is theoretically faster than ArcLookUp and AllArcLookUp, it often provides worse performance than them.

Parameters:
  • s – The source node.

  • t – The target node.

  • p – The previous arc between s and t. It it is INVALID or not given, the operator finds the first appropriate arc.

Returns:

An arc from s to t after p or INVALID if there is no more.

Protected Functions

inline virtual void add( const Arc & arc )
inline virtual void add( const std::vector< Arc > & arcs )
inline virtual void erase( const Arc & arc )
inline virtual void erase( const std::vector< Arc > & arcs )
inline virtual void build()
inline virtual void clear()
inline void insert( Arc arc )
inline void remove( Arc arc )
inline Arc refreshRec( std::vector< Arc > & v , int a , int b )
inline void refresh()
inline void zig( Arc v )
inline void zag( Arc v )
inline void splay( Arc v )

Protected Attributes

const Digraph & _g
AutoNodeMap _head
Digraph::template ArcMap< Arc > _parent
Digraph::template ArcMap< Arc > _left
Digraph::template ArcMap< Arc > _right
class AutoNodeMap : public Type< GR , Node >

Public Functions

inline AutoNodeMap( const GR & digraph )
inline virtual void add( const Node & node )
inline virtual void add( const std::vector< Node > & nodes )
inline virtual void build()
class ArcLess

Public Functions

inline ArcLess( const Digraph & _g )
inline bool operator()( Arc a , Arc b ) const