AllArcLookUp
Declared in lemon/core.h, in the group Basic Graph Utilities; the same class on the Doxygen site.
-
template< class GR >
class AllArcLookUp : public lemon::ArcLookUp< GR > Fast look-up of all arcs between given endpoints.
This class is the same as ArcLookUp, with the addition that it makes it possible to find all parallel arcs between given endpoints.
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.
Public Functions
-
inline AllArcLookUp( const Digraph & g )
Constructor.
It builds up the search database, which remains valid until the digraph changes.
-
inline void refresh( Node n )
Refresh the 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 , Arc prev = INVALID ) const
Find an arc between two nodes.
For example, you can count the number of arcs from
utovin the following way.AllArcLookUp< ListDigraph > ae( g ); ... int n = 0; for( Arc a = ae( u , v ) ; a != INVALID ; a = ae( u , v , a ) ) n++;
Finding the first arc take O(logd) time, where d is the number of outgoing arcs of
s. Then the consecutive arcs are found in constant time.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.
prev – The previous arc between
sandt. It it is INVALID or not given, the operator finds the first appropriate arc.
- Returns:
An arc from
stotafterprevor INVALID if there is no more.