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.
GR | The type of the underlying digraph. |
#include <lemon/core.h>
Public Types | |
typedef GR | Digraph |
The Digraph type. | |
Public Member Functions | |
DynArcLookUp (const Digraph &g) | |
Constructor. | |
Arc | operator() (Node s, Node t, Arc p=INVALID) const |
Find an arc between two nodes. |
DynArcLookUp | ( | const Digraph & | g | ) | [inline] |
Constructor.
It builds up the search database.
Arc operator() | ( | Node | s, |
Node | t, | ||
Arc | p = INVALID |
||
) | const [inline] |
Find an arc between two nodes.
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. |
s
to t
after p
or INVALID if there is no more.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 arcs take at most O(logd) amortized time, specifically, the time complexity of the lookups is equal to the optimal search tree implementation for the current query distribution in a constant factor.