fr.inria.opengve.bridge.algorithms.common
Class RandomWalk<V,E extends Link<V>,G extends Graph<V,E>>

java.lang.Object
  fr.inria.opengve.bridge.algorithms.common.RandomWalk<V,E,G>

Type Parameters:

V - The type of vertices

E - The type of links.

public abstract class RandomWalk<V,E extends Link<V>,G extends Graph<V,E>>
extends java.lang.Object

Author:

fabrice.peix@sophia.inria.fr

Constructor Summary

RandomWalk(G g)
Initialize random walk generator for a given graph and from a given vertex.

RandomWalk(G g, long seed)
Initialize random walk generator for a given graph and from a given vertex.

Method Summary

protected double[]	computeProbability(E previousEdge, java.util.Vector<E> edgeVector) This method give the probability of each edge present in a given vector.
abstract Path<V,E>	createPath() Create a new empty path.
long	getInitialSeed() Return the seed used to initialize this random walk.
Path<V,E>	getNextPath(V source, V destination) Give the next random walk.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RandomWalk

public RandomWalk(G g)

Initialize random walk generator for a given graph and from a given vertex.

Parameters:

g - The graph on which random walk is done.

RandomWalk

public RandomWalk(G g,
                  long seed)

Initialize random walk generator for a given graph and from a given vertex.

Parameters:

g - The graph on which random walk is done.

seed - The value used to initialize random generator.

Method Detail

createPath

public abstract Path<V,E> createPath()

Create a new empty path. The type of path directed or not is the same than the given graph.

Returns:

A new empty path.

getNextPath

public Path<V,E> getNextPath(V source,
                             V destination)

Give the next random walk.

Parameters:

source - The begining of the random walk.

destination - The destination of the ramdom walk.

Returns:

A path from source to destination.

computeProbability

protected double[] computeProbability(E previousEdge,
                                      java.util.Vector<E> edgeVector)

This method give the probability of each edge present in a given vector. The result array have the same size that the given one. The contents of the returned array (result) is interpreted as follow :
result[0] is the probability of the edge edgeArray[0] to be choosen
result[1] - result[0] is the probability of the edge edgeArray[1] to be choosen
result[2] - (result[0] + result[1]) is the probability of the edge edgeArray[2] to be choosen
...
In practice the code that choose the next edge is :
private E chooseNextEdge(Vector< E> edgeArray,Random randomGenerator) {
double[] probability = computeProbability(edgeArray);
double randValue = randomGenerator.nextDouble(); // Give a double value between 0.0 and 1.0
for (int i = 0; i < probability.length; i++ ) {
if (randValue <= probability[i]) { return edgeArray.get(i); }
}
// Never reach (just for java error)
return null;
}
So, to be sure that an edge is choosen the last element of result (result[result.lenght-1]) must be equal to 1 (one).

By default this method implementation give the same probability to all the edges but each class extending this one can override this method to change probability computation.

Parameters:

previousEdge - The previously choosed edge or null if none.

edgeVector - The vector of edge for which we want to compute probability.

Returns:

An array containing probability of each edges.

getInitialSeed

public long getInitialSeed()

Return the seed used to initialize this random walk.

Returns:

The seed used to initialize this random walk.