Package com.jgalgo.alg.traversal

Interface RandomWalkIter<V,E>

Type Parameters:

V - the vertices type

E - the edges type

All Superinterfaces:

Iterator<V>, RandomizedAlgorithm

All Known Subinterfaces:

RandomWalkIter.Int

public interface RandomWalkIter<V,E>
extends Iterator<V>, RandomizedAlgorithm

Random walk iterator.

A random walk iterator is an iterator that starts at a given vertex and randomly choose an edge to traverse at each step. The iterator returns the vertices visited by the random walk in the order they were visited. The iterator may return the same vertex multiple times. The iterator can keep advancing as long as there are out going edges (with non zero weight in the weighted case) from the current vertex. Each out going edge can be chosen with equal probability, or with probability proportional to a given edge weight function.

To get a deterministic random walk, set the iterator seed using RandomizedAlgorithm.setSeed(long).

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	RandomWalkIter.Int	A random walk iterator for IntGraph.

Method Summary

Modifier and Type	Method	Description
boolean	hasNext()	Check whether there is a vertex the iterator can advance to from the current vertex.
E	lastEdge()	Get the edge that led to the last vertex returned by next().
static <V,E> RandomWalkIter<V,E>	newInstance(Graph<V,E> g, V source)	Create a new random walk iterator.
static <V,E> RandomWalkIter<V,E>	newInstance(Graph<V,E> g, V source, WeightFunction<E> weights)	Create a new weighted random walk iterator.
V	next()	Advance the iterator from the current vertex along one of its out edges and return the vertex reached.

Methods inherited from interface java.util.Iterator

forEachRemaining, remove

Methods inherited from interface com.jgalgo.alg.common.RandomizedAlgorithm

setSeed

Method Detail

hasNext

boolean hasNext()

Check whether there is a vertex the iterator can advance to from the current vertex.

Specified by:

hasNext in interface Iterator<V>

next

V next()

Advance the iterator from the current vertex along one of its out edges and return the vertex reached.

Specified by:

next in interface Iterator<V>

lastEdge

E lastEdge()

Get the edge that led to the last vertex returned by next().

The behavior is undefined if next() was not called yet.

Returns:

the edge that led to the last vertex returned by next()

newInstance

static <V,E> RandomWalkIter<V,E> newInstance(Graph<V,E> g,
                                                         V source)

Create a new random walk iterator.

If the graph is an IntGraph, the returned iterator will be an instance of RandomWalkIter.Int.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

source - a source vertex

Returns:

a new random walk iterator

Throws:

NoSuchVertexException - if source is not a vertex in g

newInstance

static <V,E> RandomWalkIter<V,E> newInstance(Graph<V,E> g,
                                                         V source,
                                                         WeightFunction<E> weights)

Create a new weighted random walk iterator.

The iterator will choose the next vertex to advance to with probability proportional to the weight of the edge that led to it. The edges weights must be non negative.

If the graph is an IntGraph, the returned iterator will be an instance of RandomWalkIter.Int.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

source - a source vertex

weights - an edge weight function

Returns:

a new weighted random walk iterator

Throws:

NoSuchVertexException - if source is not a vertex in g