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:
java.util.Iterator<V>
public class RandomWalkVertexIterator<V,​E>
extends java.lang.Object
implements java.util.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, java.util.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 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, java.util.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 java.util.Iterator<V>

    • next

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