AllArcLookUp< GR > Class Template Reference

---

Detailed Description

template<class GR>
class lemon::AllArcLookUp< GR >

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

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

ArcLookUp

#include <lemon/core.h>

Inheritance diagram for AllArcLookUp< GR >:

List of all members.

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

---

Constructor & Destructor Documentation

AllArcLookUp

(

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 from ArcLookUp< 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 from ArcLookUp< GR >.

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

Find an arc between two nodes.

Parameters:

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

Returns:

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

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

       AllArcLookUp<ListDigraph> ae(g);
       ...
       int n = 0;
       for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;

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

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.