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:

  • 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 Details

    • 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