ArcLookUp< GR > Class Template Reference

---

Detailed Description

template<class GR>
class lemon::ArcLookUp< GR >

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

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

Warning:

This class is static, so you should call refresh() (or at least refresh(Node)) to refresh this data structure whenever the digraph changes. This is a time consuming (superlinearly proportional (O(m logm)) to the number of arcs).

Template Parameters:

GR	The type of the underlying digraph.

See also:

DynArcLookUp

AllArcLookUp

#include <lemon/core.h>

Inheritance diagram for ArcLookUp< GR >:

List of all members.

Public Types
typedef GR	Digraph
	The Digraph type.
Public Member Functions
	ArcLookUp (const Digraph &g)
	Constructor.
void	refresh (Node n)
	Refresh the search data structure at a node.
void	refresh ()
	Refresh the full data structure.
Arc	operator() (Node s, Node t) const
	Find an arc between two nodes.

---

Constructor & Destructor Documentation

ArcLookUp

(

const Digraph &

g

)

[inline]

Constructor.

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

---

Member Function Documentation

void refresh

(

Node

n

)

[inline]

Build up the search database of node n.

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

Reimplemented in AllArcLookUp< GR >.

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(m logD), where m is the number of the arcs in the digraph and D is the maximum out-degree of the digraph.

Reimplemented in AllArcLookUp< GR >.

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

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

Parameters:

s	The source node.
t	The target node.

Returns:

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

Warning:

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