Package org.jgrapht.traverse
Class RandomWalkIterator<V,E>
- java.lang.Object
-
- org.jgrapht.traverse.AbstractGraphIterator<V,E>
-
- org.jgrapht.traverse.RandomWalkIterator<V,E>
-
- Type Parameters:
V
- vertex typeE
- 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 (defaultLong#MAX_VALUE
. When the bound is reached the iterator is considered exhausted. Callingnext()
on exhausted iterator will throwNoSuchElementException
. In case a sink (i.e. no edges) vertex is reached, iterator will return null and consecutive calls tonext()
will throwNoSuchElementException
. 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.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class org.jgrapht.traverse.AbstractGraphIterator
AbstractGraphIterator.DirectedSpecifics<VV,EE>, AbstractGraphIterator.FlyweightEdgeEvent<VV,localE>, AbstractGraphIterator.FlyweightVertexEvent<VV>, AbstractGraphIterator.Specifics<VV,EE>, AbstractGraphIterator.UndirectedSpecifics<VV,EE>
-
-
Field Summary
Fields Modifier and Type Field Description private V
currentVertex
private Graph<V,E>
graph
private boolean
isWeighted
private long
maxSteps
private java.util.Random
random
private boolean
sinkReached
-
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
nListeners, reusableEdgeEvent, reusableVertexEvent, specifics
-
-
Constructor Summary
Constructors Constructor Description RandomWalkIterator(Graph<V,E> graph)
Creates a new iterator for the specified graph.RandomWalkIterator(Graph<V,E> graph, V startVertex)
Creates a new iterator for the specified graph.RandomWalkIterator(Graph<V,E> graph, V startVertex, boolean isWeighted)
Creates a new iterator for the specified graph.RandomWalkIterator(Graph<V,E> graph, V startVertex, boolean isWeighted, long maxSteps)
Creates a new iterator for the specified graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private EdgeTraversalEvent<E>
createEdgeTraversalEvent(E edge)
private VertexTraversalEvent<V>
createVertexTraversalEvent(V vertex)
private E
drawEdge(java.util.Set<? extends E> edges)
Randomly draws an edges out of the provided set.protected void
encounterVertex(V vertex, E edge)
Update data structures every time we see a vertex.private double
getTotalWeight(java.util.Collection<E> edges)
boolean
hasNext()
protected boolean
isExhausted()
Check if this walk is exhausted.V
next()
-
Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator
addTraversalListener, createGraphSpecifics, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, isCrossComponentTraversal, isReuseEvents, remove, removeTraversalListener, setCrossComponentTraversal, setReuseEvents
-
-
-
-
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 byLong#MAX_VALUE
steps.- Parameters:
graph
- the graph to be iterated.- Throws:
java.lang.IllegalArgumentException
- ifgraph==null
or does not containstartVertex
-
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 isnull
, Iteration will start at an arbitrary graph vertex. Walk is un-weighted and bounded byLong#MAX_VALUE
steps.- Parameters:
graph
- the graph to be iterated.startVertex
- the vertex iteration to be started.- Throws:
java.lang.IllegalArgumentException
- ifgraph==null
or does not containstartVertex
-
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 isnull
, Iteration will start at an arbitrary graph vertex. Walk is bounded byLong#MAX_VALUE
steps.- Parameters:
graph
- the graph to be iterated.startVertex
- the vertex iteration to be started.isWeighted
- set totrue
if a weighted walk is desired.- Throws:
java.lang.IllegalArgumentException
- ifgraph==null
or does not containstartVertex
-
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 isnull
, 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 totrue
if a weighted walk is desired.maxSteps
- number of steps before walk is exhausted.- Throws:
java.lang.IllegalArgumentException
- ifgraph==null
or does not containstartVertex
-
-
Method Detail
-
isExhausted
protected boolean isExhausted()
Check if this walk is exhausted. Callingnext()
on exhausted iterator will throwNoSuchElementException
.- Returns:
true
if 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 encounterededge
- 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.
-
createEdgeTraversalEvent
private EdgeTraversalEvent<E> createEdgeTraversalEvent(E edge)
-
createVertexTraversalEvent
private VertexTraversalEvent<V> createVertexTraversalEvent(V vertex)
-
getTotalWeight
private double getTotalWeight(java.util.Collection<E> edges)
-
-