![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
Dynamic arc look-up between given endpoints. More...
#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. | |
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. |
|
inline |
Constructor.
It builds up the search database.
|
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.
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.