Public Types | Public Member Functions

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.

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:
GRThe type of the underlying digraph.
See also:

#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)
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]


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.

sThe source node.
tThe target node.
prevThe previous arc between s and t. It it is INVALID or not given, the operator finds the first appropriate arc.
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.

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.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines