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.
    • Field Detail

      • rng

        private final java.util.Random rng
      • graph

        private final Graph<V,​E> graph
      • weighted

        private final boolean weighted
      • outEdgesTotalWeight

        private final java.util.Map<V,​java.lang.Double> outEdgesTotalWeight
      • maxHops

        private final long maxHops
      • hops

        private long hops
      • nextVertex

        private V nextVertex
    • 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>
      • computeNext

        private void computeNext()