ArcLookUp

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

template< class GR >
class ArcLookUp

Fast 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 time O(logd), where d is the out-degree of the source node.

It is not possible to find all parallel arcs between two nodes. Use AllArcLookUp for this purpose.

See also

DynArcLookUp

See also

AllArcLookUp

Warning

This class is static, so you should call refresh() (or at least refresh(Node)) to refresh this data structure whenever the digraph changes. This is a time consuming (superlinearly proportional (O( m logm )) to the number of arcs).

Template Parameters:

GR – The type of the underlying digraph.

Subclassed by AllArcLookUp< GR >

Public Types

typedef GR Digraph

The Digraph type.

Public Functions

inline ArcLookUp( const Digraph & g )

Constructor.

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

inline void refresh( Node n )

Refresh the search data structure at a node.

Build up the search database of node n.

It runs in time O( d logd ), where d is the number of the outgoing arcs of n.

inline void refresh()

Refresh the full data structure.

Build up the full search database. In fact, it simply calls refresh(n) for each node n.

It runs in time O( m logD ), where m is the number of the arcs in the digraph and D is the maximum out-degree of the digraph.

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

Find an arc between two nodes.

Find an arc between two nodes in time O(logd), where d is the number of outgoing arcs of s.

Warning

If you change the digraph, refresh() must be called before using this operator. If you change the outgoing arcs of a single node n, then refresh(n) is enough.

Parameters:
  • s – The source node.

  • t – The target node.

Returns:

An arc from s to t if there exists, INVALID otherwise.

Protected Attributes

const Digraph & _g
Digraph::template NodeMap< Arc > _head
Digraph::template ArcMap< Arc > _left
Digraph::template ArcMap< Arc > _right
class ArcLess

Public Functions

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