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

---

Detailed Description

template<class G>
class lemon::EdgeLookUp< G >

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

It is not possible to find all parallel edges between two nodes. Use AllEdgeLookUp for this purpose.

Warning:

This class is static, so you should refresh() (or at least refresh(Node)) this data structure whenever the graph changes. This is a time consuming (superlinearly proportional (O(mlogm)) to the number of edges).

Parameters:

G

The type of the underlying graph.

See also:

DynEdgeLookUp

AllEdgeLookUp

#include <lemon/graph_utils.h>

List of all members.

Public Member Functions
	EdgeLookUp (const Graph &g)
	Constructor.
void	refresh (Node n)
	Refresh the data structure at a node.
void	refresh ()
	Refresh the full data structure.
Edge	operator() (Node s, Node t) const
	Find an edge between two nodes.

---

Constructor & Destructor Documentation

EdgeLookUp

(

const Graph &

g

)

[inline]

Constructor.

It builds up the search database, which remains valid until the graph changes.

---

Member Function Documentation

void refresh

(

Node

n

)

[inline]

Build up the search database of node n.

It runs in time O(dlogd), where d is the number of the outgoing edges of n.

Reimplemented in AllEdgeLookUp< G >.

void refresh

(

)

[inline]

Build up the full search database. In fact, it simply calls refresh(n) for each node n.

It runs in time O(mlogD), where m is the number of the edges of n and D is the maximum out-degree of the graph.

Reimplemented in AllEdgeLookUp< G >.

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.

Warning:

If you change the graph, refresh() must be called before using this operator. If you change the outgoing edges of a single node n, then refresh(n) is enough.