Module org.jgrapht.core

Package org.jgrapht.traverse

Class RandomWalkVertexIterator<V,E>

java.lang.Object

org.jgrapht.traverse.RandomWalkVertexIterator<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

Iterator<V>

public class RandomWalkVertexIterator<V,E>
extends Object
implements Iterator<V>

A random walk iterator. "Given a graph and a starting point, we select a neighbor of it at random, and move to this neighbor; then we select a neighbor of this point at random, and move to it etc. The (random) sequence of points selected this way is a random walk on the graph." This very simple definition, together with a comprehensive survey can be found at: "Lovász, L. (1993). Random walks on graphs: A survey. Combinatorics, Paul erdos is eighty, 2(1), 1-46." In its default variant the probability of selecting an outgoing edge is one over the (out) degree of the vertex. In case the user requests a weighted walk, then the probability of each edge is equal to its weight divided by the total weight of all outgoing edges. The walk can also be bounded by a maximum number of hops (edges traversed). The iterator returns NoSuchElementException when this bound is reached.

Author:

Dimitrios Michail

Constructor Summary

Constructors

Constructor	Description
RandomWalkVertexIterator(Graph<V,E> graph, V vertex)	Create a new iterator
RandomWalkVertexIterator(Graph<V,E> graph, V vertex, long maxHops)	Create a new iterator
RandomWalkVertexIterator(Graph<V,E> graph, V vertex, long maxHops, boolean weighted, Random rng)	Create a new iterator

Method Summary

Modifier and Type	Method	Description
boolean	hasNext()
V	next()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Iterator

forEachRemaining, remove

Constructor Detail

RandomWalkVertexIterator

public RandomWalkVertexIterator(Graph<V,E> graph,
                                V vertex)

Create a new iterator

Parameters:

graph - the graph

vertex - the starting vertex

Throws:

IllegalArgumentException - if graph does not contain vertex

NullPointerException - if either one of graph or vertex is null

RandomWalkVertexIterator

public RandomWalkVertexIterator(Graph<V,E> graph,
                                V vertex,
                                long maxHops)

Create a new iterator

Parameters:

graph - the graph

vertex - the starting vertex

maxHops - maximum hops to perform during the walk

Throws:

IllegalArgumentException - if graph does not contain vertex

NullPointerException - if either one of graph or vertex is null

RandomWalkVertexIterator

public RandomWalkVertexIterator(Graph<V,E> graph,
                                V vertex,
                                long maxHops,
                                boolean weighted,
                                Random rng)

Create a new iterator

Parameters:

graph - the graph

vertex - the starting vertex

maxHops - maximum hops to perform during the walk

weighted - whether to perform a weighted random walk (compute probabilities based on the edge weights)

rng - the random number generator

Throws:

IllegalArgumentException - if graph does not contain vertex

NullPointerException - if either one of graph or vertex is null

Method Detail

hasNext

public boolean hasNext()

Specified by:

hasNext in interface Iterator<V>

next

public V next()

Specified by:

next in interface Iterator<V>