DynEdgeLookUp< G > Class Template Reference
[Graph Maps, Basic Graph Utilities]

---

Detailed Description

template<class G>
class lemon::DynEdgeLookUp< G >

Using this class, you can find an edge in a graph from a given source to a given target in amortized time O(log d), where d is the out-degree of the source node.

It is possible to find all parallel edges between two nodes with the findFirst() and findNext() members.

See the EdgeLookUp and AllEdgeLookUp classes if your graph do not changed so frequently.

This class uses a self-adjusting binary search tree, Sleator's and Tarjan's Splay tree for guarantee the logarithmic amortized time bound for edge lookups. This class also guarantees the optimal time bound in a constant factor for any distribution of queries.

Parameters:

G

The type of the underlying graph.

See also:

EdgeLookUp

AllEdgeLookUp

#include <lemon/graph_utils.h>

List of all members.

Public Member Functions
	DynEdgeLookUp (const Graph &g)
	Constructor.
Edge	operator() (Node s, Node t) const
	Find an edge between two nodes.
Edge	findFirst (Node s, Node t) const
	Find the first edge between two nodes.
Edge	findNext (Node s, Node t, Edge e) const
	Find the next edge between two nodes.

---

Constructor & Destructor Documentation

DynEdgeLookUp

(

const Graph &

g

)

[inline]

Constructor.

It builds up the search database.

---

Member Function Documentation

Edge operator()	(	Node	s,
		Node	t
	)			const [inline]

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

Parameters:

	s	The source node
	t	The target node

Returns:

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

Edge findFirst	(	Node	s,
		Node	t
	)			const [inline]

Find the first edge between two nodes in time O(logd), where d is the number of outgoing edges of s.

Parameters:

	s	The source node
	t	The target node

Returns:

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

Edge findNext	(	Node	s,
		Node	t,
		Edge	e
	)			const [inline]

Find the next edge between two nodes in time O(logd), where d is the number of outgoing edges of s.

Parameters:

	s	The source node
	t	The target node

Returns:

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

Note:

If e is not the result of the previous findFirst() operation then the amorized time bound can not be guaranteed.