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 Details

    • RandomWalkVertexIterator

      public RandomWalkVertexIterator(Graph<V,E> graph, V vertex)
      Create a new iterator
      Parameters:
      graph - the graph
      vertex - the starting vertex
    • 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
    • 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
  • Method Details

    • hasNext

      public boolean hasNext()
      Specified by:
      hasNext in interface Iterator<V>
    • next

      public V next()
      Specified by:
      next in interface Iterator<V>