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

---

Detailed Description

template<class G>
class lemon::AllEdgeLookUp< G >

This class is the same as EdgeLookUp, with the addition that it makes it possible to find all edges between given endpoints.

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

EdgeLookUp

#include <lemon/graph_utils.h>

Inheritance diagram for AllEdgeLookUp< G >:

[legend]

List of all members.

Public Member Functions
	AllEdgeLookUp (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, Edge prev=INVALID) const
	Find an edge between two nodes.

---

Constructor & Destructor Documentation

AllEdgeLookUp

(

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 from EdgeLookUp< 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 from EdgeLookUp< G >.

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

Find an edge between two nodes.

Parameters:

	s	The source node
	t	The target node
	prev	The previous edge between s and t. It it is INVALID or not given, the operator finds the first appropriate edge.

Returns:

An edge from s to t after prev or INVALID if there is no more.

For example, you can count the number of edges from u to v in the following way.

       AllEdgeLookUp<ListGraph> ae(g);
       ...
       int n=0;
       for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;

Finding the first edge take O(logd) time, where d is the number of outgoing edges of s. Then, the consecutive edges are found in constant time.

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.