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
See also
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 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
stotif there exists, INVALID otherwise.
Protected Attributes
-
class ArcLess