edu.uci.ics.jung.algorithms.util
Class WeightedChoice<T>

java.lang.Object
  edu.uci.ics.jung.algorithms.util.WeightedChoice<T>

public class WeightedChoice<T>
extends Object

Selects items according to their probability in an arbitrary probability distribution. The distribution is specified by a Map from items (of type T) to weights of type Number, supplied to the constructor; these weights are normalized internally to act as probabilities.

This implementation selects items in O(1) time, and requires O(n) space.

Author:

Joshua O'Madadhain

Field Summary

static double

DEFAULT_THRESHOLD The default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).

Constructor Summary

WeightedChoice(Map<T,? extends Number> item_weights)
Equivalent to this(item_weights, new Random(), DEFAULT_THRESHOLD).

WeightedChoice(Map<T,? extends Number> item_weights, double threshold)
Equivalent to this(item_weights, new Random(), threshold).

WeightedChoice(Map<T,? extends Number> item_weights, Random random)
Equivalent to this(item_weights, random, DEFAULT_THRESHOLD).

WeightedChoice(Map<T,? extends Number> item_weights, Random random, double threshold)
Creates an instance with the specified mapping from items to weights, random number generator, and threshold value.

Method Summary

T	nextItem() Retrieves an item with probability proportional to its weight in the Map provided in the input.
void	setRandomSeed(long seed) Sets the seed used by the internal random number generator.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_THRESHOLD

public static final double DEFAULT_THRESHOLD

The default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).

See Also:

Constant Field Values

Constructor Detail

WeightedChoice

public WeightedChoice(Map<T,? extends Number> item_weights)

Equivalent to this(item_weights, new Random(), DEFAULT_THRESHOLD).

Parameters:

item_weights -

WeightedChoice

public WeightedChoice(Map<T,? extends Number> item_weights,
                      double threshold)

Equivalent to this(item_weights, new Random(), threshold).

WeightedChoice

public WeightedChoice(Map<T,? extends Number> item_weights,
                      Random random)

Equivalent to this(item_weights, random, DEFAULT_THRESHOLD).

WeightedChoice

public WeightedChoice(Map<T,? extends Number> item_weights,
                      Random random,
                      double threshold)

Creates an instance with the specified mapping from items to weights, random number generator, and threshold value.

The mapping defines the weight for each item to be selected; this will be proportional to the probability of its selection.

The random number generator specifies the mechanism which will be used to provide uniform integer and double values.

The threshold indicates default minimum value that is treated as a valid probability (as opposed to rounding error from floating-point operations).

Method Detail

setRandomSeed

public void setRandomSeed(long seed)

Sets the seed used by the internal random number generator.

nextItem

public T nextItem()

Retrieves an item with probability proportional to its weight in the Map provided in the input.