2 * Copyright (c) 2009, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
9 * Created on Jan 8, 2009
12 package edu.uci.ics.jung.algorithms.util;
14 import java.util.ArrayList;
15 import java.util.LinkedList;
16 import java.util.List;
18 import java.util.Queue;
19 import java.util.Random;
22 * Selects items according to their probability in an arbitrary probability
23 * distribution. The distribution is specified by a {@code Map} from
24 * items (of type {@code T}) to weights of type {@code Number}, supplied
25 * to the constructor; these weights are normalized internally to act as
28 * <p>This implementation selects items in O(1) time, and requires O(n) space.
30 * @author Joshua O'Madadhain
32 public class WeightedChoice<T>
34 private List<ItemPair> item_pairs;
35 private Random random;
38 * The default minimum value that is treated as a valid probability
39 * (as opposed to rounding error from floating-point operations).
41 public static final double DEFAULT_THRESHOLD = 0.00000000001;
44 * Equivalent to {@code this(item_weights, new Random(), DEFAULT_THRESHOLD)}.
47 public WeightedChoice(Map<T, ? extends Number> item_weights)
49 this(item_weights, new Random(), DEFAULT_THRESHOLD);
53 * Equivalent to {@code this(item_weights, new Random(), threshold)}.
55 public WeightedChoice(Map<T, ? extends Number> item_weights, double threshold)
57 this(item_weights, new Random(), threshold);
61 * Equivalent to {@code this(item_weights, random, DEFAULT_THRESHOLD)}.
63 public WeightedChoice(Map<T, ? extends Number> item_weights, Random random)
65 this(item_weights, random, DEFAULT_THRESHOLD);
69 * Creates an instance with the specified mapping from items to weights,
70 * random number generator, and threshold value.
72 * <p>The mapping defines the weight for each item to be selected; this
73 * will be proportional to the probability of its selection.
74 * <p>The random number generator specifies the mechanism which will be
75 * used to provide uniform integer and double values.
76 * <p>The threshold indicates default minimum value that is treated as a valid
77 * probability (as opposed to rounding error from floating-point operations).
79 public WeightedChoice(Map<T, ? extends Number> item_weights, Random random,
82 if (item_weights.isEmpty())
83 throw new IllegalArgumentException("Item weights must be non-empty");
85 int item_count = item_weights.size();
86 item_pairs = new ArrayList<ItemPair>(item_count);
89 for (Map.Entry<T, ? extends Number> entry : item_weights.entrySet())
91 double value = entry.getValue().doubleValue();
93 throw new IllegalArgumentException("Weights must be > 0");
96 double bucket_weight = 1.0 / item_weights.size();
98 Queue<ItemPair> light_weights = new LinkedList<ItemPair>();
99 Queue<ItemPair> heavy_weights = new LinkedList<ItemPair>();
100 for (Map.Entry<T, ? extends Number> entry : item_weights.entrySet())
102 double value = entry.getValue().doubleValue() / sum;
103 enqueueItem(entry.getKey(), value, bucket_weight, light_weights, heavy_weights);
106 // repeat until both queues empty
107 while (!heavy_weights.isEmpty() || !light_weights.isEmpty())
109 ItemPair heavy_item = heavy_weights.poll();
110 ItemPair light_item = light_weights.poll();
111 double light_weight = 0;
114 if (light_item != null)
116 light_weight = light_item.weight;
117 light = light_item.light;
119 if (heavy_item != null)
121 heavy = heavy_item.heavy;
122 // put the 'left over' weight from the heavy item--what wasn't
123 // needed to make up the difference between the light weight and
124 // 1/n--back in the appropriate queue
125 double new_weight = heavy_item.weight - (bucket_weight - light_weight);
126 if (new_weight > threshold)
127 enqueueItem(heavy, new_weight, bucket_weight, light_weights, heavy_weights);
129 light_weight *= item_count;
131 item_pairs.add(new ItemPair(light, heavy, light_weight));
134 this.random = random;
138 * Adds key/value to the appropriate queue. Keys with values less than
139 * the threshold get added to {@code light_weights}, all others get added
140 * to {@code heavy_weights}.
142 private void enqueueItem(T key, double value, double threshold,
143 Queue<ItemPair> light_weights, Queue<ItemPair> heavy_weights)
145 if (value < threshold)
146 light_weights.offer(new ItemPair(key, null, value));
148 heavy_weights.offer(new ItemPair(null, key, value));
152 * Sets the seed used by the internal random number generator.
154 public void setRandomSeed(long seed)
156 this.random.setSeed(seed);
160 * Retrieves an item with probability proportional to its weight in the
161 * {@code Map} provided in the input.
165 ItemPair item_pair = item_pairs.get(random.nextInt(item_pairs.size()));
166 if (random.nextDouble() < item_pair.weight)
167 return item_pair.light;
168 return item_pair.heavy;
172 * Manages light object/heavy object/light conditional probability tuples.
174 private class ItemPair
180 private ItemPair(T light, T heavy, double weight)
184 this.weight = weight;
188 public String toString()
190 return String.format("[L:%s, H:%s, %.3f]", light, heavy, weight);