Loading...
Searching...
No Matches
AllArcLookUp< GR > Class Template Reference
Tools and Utilities » Basic Graph Utilities

## 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 >:
[legend]

## Public Types

typedef GR | Digraph
| The Digraph type.
Public Types inherited from ArcLookUp< GR >
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.
Public Member Functions inherited from ArcLookUp< GR >
| 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

## AllArcLookUp()

template<class GR>

AllArcLookUp | ( | const Digraph & | g | ) |

inline

Constructor.

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

## Member Function Documentation

## refresh() [1/2]

template<class GR>

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`.

## refresh() [2/2]

template<class 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.

## operator()()

template<class 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++;
lemon::INVALID
const Invalid INVALID
Invalid iterators.
Definition base.cc:32
lemon::AllArcLookUp::AllArcLookUp
AllArcLookUp(const Digraph &g)
Constructor.
Definition core.h:2425

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.