Package com.jgalgo.alg.common

Interface RandomizedAlgorithm

All Known Subinterfaces:
RandomWalkIter<V,E>, RandomWalkIter.Int
All Known Implementing Classes:
ColoringGreedy, DominatingSetAlgoGreedy, KEdgeConnectedComponentsWang, MinimumSpanningTreeKargerKleinTarjan
public interface RandomizedAlgorithm
Randomized algorithm interface.

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables. In many cases randomized algorithm are much simpler than their deterministic counterparts, and can achieve same or better performance.

One drawback of randomized algorithms is that they are more complicated to debug and analyze. In particular, their output is not deterministic, and may vary each time the algorithm is run. Therefore, randomized algorithms can be forced to use the same seed for the random number generator, in order to get the same output each time the algorithm is run. The seed can be set using the setSeed(long) method.

One can check if a JGAlgo algorithm is indeed a randomized algorithm by checking if it implements this interface.

Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    setSeed(long seed)
    Sets the seed for the random number generator.

  • Method Details

    • setSeed

      void setSeed(long seed)
      Sets the seed for the random number generator.

      The algorithm will use the same seed for the random number generator, in order to perform deterministically. Note that if methods of the algorithm are called multiple times, the seed should be set before each call.

      Parameters:
      seed - the seed for the random number generator.