Class 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
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      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
      • 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 Detail

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