Class RandomWalkIterator<V,​E>

  • Type Parameters:
    V - vertex type
    E - edge type
    All Implemented Interfaces:
    java.util.Iterator<V>, GraphIterator<V,​E>

    public class RandomWalkIterator<V,​E>
    extends AbstractGraphIterator<V,​E>
    A random-walk iterator for a directed and an undirected graph. At each step selected a randomly (uniformly distributed) edge out of the current vertex edges (in case of directed graph - from the outgoing edges), and follows it to the next vertex. In case a weighted walk is desired (and in case the graph is weighted), edges are selected with probability respective to its weight (out of the total weight of the edges). Walk can be bounded by number of steps (default Long#MAX_VALUE . When the bound is reached the iterator is considered exhausted. Calling next() on exhausted iterator will throw NoSuchElementException. In case a sink (i.e. no edges) vertex is reached, iterator will return null and consecutive calls to next() will throw NoSuchElementException. For this iterator to work correctly the graph must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.
    • Field Detail

      • currentVertex

        private V currentVertex
      • graph

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

        private final boolean isWeighted
      • sinkReached

        private boolean sinkReached
      • maxSteps

        private long maxSteps
      • random

        private java.util.Random random
    • Constructor Detail

      • RandomWalkIterator

        public RandomWalkIterator​(Graph<V,​E> graph)
        Creates a new iterator for the specified graph. Iteration will start at arbitrary vertex. Walk is un-weighted and bounded by Long#MAX_VALUE steps.
        Parameters:
        graph - the graph to be iterated.
        Throws:
        java.lang.IllegalArgumentException - if graph==null or does not contain startVertex
      • RandomWalkIterator

        public RandomWalkIterator​(Graph<V,​E> graph,
                                  V startVertex)
        Creates a new iterator for the specified graph. Iteration will start at the specified start vertex. If the specified start vertex is null, Iteration will start at an arbitrary graph vertex. Walk is un-weighted and bounded by Long#MAX_VALUE steps.
        Parameters:
        graph - the graph to be iterated.
        startVertex - the vertex iteration to be started.
        Throws:
        java.lang.IllegalArgumentException - if graph==null or does not contain startVertex
      • RandomWalkIterator

        public RandomWalkIterator​(Graph<V,​E> graph,
                                  V startVertex,
                                  boolean isWeighted)
        Creates a new iterator for the specified graph. Iteration will start at the specified start vertex. If the specified start vertex is null, Iteration will start at an arbitrary graph vertex. Walk is bounded by Long#MAX_VALUE steps.
        Parameters:
        graph - the graph to be iterated.
        startVertex - the vertex iteration to be started.
        isWeighted - set to true if a weighted walk is desired.
        Throws:
        java.lang.IllegalArgumentException - if graph==null or does not contain startVertex
      • RandomWalkIterator

        public RandomWalkIterator​(Graph<V,​E> graph,
                                  V startVertex,
                                  boolean isWeighted,
                                  long maxSteps)
        Creates a new iterator for the specified graph. Iteration will start at the specified start vertex. If the specified start vertex is null, Iteration will start at an arbitrary graph vertex. Walk is bounded by the provided number steps.
        Parameters:
        graph - the graph to be iterated.
        startVertex - the vertex iteration to be started.
        isWeighted - set to true if a weighted walk is desired.
        maxSteps - number of steps before walk is exhausted.
        Throws:
        java.lang.IllegalArgumentException - if graph==null or does not contain startVertex
    • Method Detail

      • isExhausted

        protected boolean isExhausted()
        Check if this walk is exhausted. Calling next() on exhausted iterator will throw NoSuchElementException.
        Returns:
        trueif this iterator is exhausted, false otherwise.
      • encounterVertex

        protected void encounterVertex​(V vertex,
                                       E edge)
        Update data structures every time we see a vertex.
        Parameters:
        vertex - the vertex encountered
        edge - the edge via which the vertex was encountered, or null if the vertex is a starting point
      • hasNext

        public boolean hasNext()
        See Also:
        Iterator.hasNext()
      • next

        public V next()
        See Also:
        Iterator.next()
      • drawEdge

        private E drawEdge​(java.util.Set<? extends E> edges)
        Randomly draws an edges out of the provided set. In case of un-weighted walk, edge will be selected with uniform distribution across all outgoing edges. In case of a weighted walk, edge will be selected with probability respective to its weight across all outgoing edges.
        Parameters:
        edges - the set to select the edge from
        Returns:
        the drawn edges or null if set is empty.
      • getTotalWeight

        private double getTotalWeight​(java.util.Collection<E> edges)