Added graph-related utility code.
diff --git a/utils/misc/src/main/java/org/onlab/graph/Heap.java b/utils/misc/src/main/java/org/onlab/graph/Heap.java
new file mode 100644
index 0000000..da1ef45
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/Heap.java
@@ -0,0 +1,193 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Objects;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Implementation of an array-backed heap structure whose sense of order is
+ * imposed by the provided comparator.
+ * <p/>
+ * While this provides similar functionality to {@link java.util.PriorityQueue}
+ * data structure, one key difference is that external entities can control
+ * when to restore the heap property, which is done through invocation of the
+ * {@link #heapify} method.
+ * <p/>
+ * This class is not thread-safe and care must be taken to prevent concurrent
+ * modifications.
+ *
+ * @param <T> type of the items on the heap
+ */
+public class Heap<T> {
+
+ private static final String E_HEAP_READONLY = "Heap iterator is read-only";
+ private static final String E_HEAP_END = "Heap iterator reached end of heap";
+
+ private final List<T> data;
+ private final Comparator<T> comparator;
+
+ /**
+ * Creates a new heap backed by the specified list. In the interest of
+ * efficiency, the list should be array-backed. Also, for the same reason,
+ * the data is not copied and therefore, the caller must assure that the
+ * backing data is not altered in any way.
+ *
+ * @param data backing data list
+ * @param comparator comparator for ordering the heap items
+ */
+ public Heap(List<T> data, Comparator<T> comparator) {
+ this.data = checkNotNull(data, "Data cannot be null");
+ this.comparator = checkNotNull(comparator, "Comparator cannot be null");
+ heapify();
+ }
+
+ /**
+ * Restores the heap property by re-arranging the elements in the backing
+ * array as necessary following any heap modifications.
+ */
+ public void heapify() {
+ for (int i = data.size() / 2; i >= 0; i--) {
+ heapify(i);
+ }
+ }
+
+ /**
+ * Returns the current size of the heap.
+ *
+ * @return number of items in the heap
+ */
+ public int size() {
+ return data.size();
+ }
+
+ /**
+ * Returns true if there are no items in the heap.
+ *
+ * @return true if heap is empty
+ */
+ public boolean isEmpty() {
+ return data.isEmpty();
+ }
+
+ /**
+ * Returns the most extreme item in the heap.
+ *
+ * @return heap extreme or null if the heap is empty
+ */
+ public T extreme() {
+ return data.isEmpty() ? null : data.get(0);
+ }
+
+ /**
+ * Extracts and returns the most extreme item from the heap.
+ *
+ * @return heap extreme or null if the heap is empty
+ */
+ public T extractExtreme() {
+ if (!isEmpty()) {
+ T extreme = extreme();
+
+ data.set(0, data.get(data.size() - 1));
+ data.remove(data.size() - 1);
+ heapify();
+ return extreme;
+ }
+ return null;
+ }
+
+ /**
+ * Inserts the specified item into the heap and returns the modified heap.
+ *
+ * @param item item to be inserted
+ * @return the heap self
+ * @throws IllegalArgumentException if the heap is already full
+ */
+ public Heap<T> insert(T item) {
+ data.add(item);
+ bubbleUp();
+ return this;
+ }
+
+ /**
+ * Returns iterator to traverse the heap level-by-level. This iterator
+ * does not permit removal of items.
+ *
+ * @return non-destructive heap iterator
+ */
+ public Iterator<T> iterator() {
+ return ImmutableList.copyOf(data).iterator();
+ }
+
+ // Bubbles up the last item in the heap to its proper position to restore
+ // the heap property.
+ private void bubbleUp() {
+ int child = data.size() - 1;
+ while (child > 0) {
+ int parent = child / 2;
+ if (comparator.compare(data.get(child), data.get(parent)) < 0) {
+ break;
+ }
+ swap(child, parent);
+ child = parent;
+ }
+ }
+
+ // Restores the heap property of the specified heap layer.
+ private void heapify(int i) {
+ int left = 2 * i + 1;
+ int right = 2 * i;
+ int extreme = i;
+
+ if (left < data.size() &&
+ comparator.compare(data.get(extreme), data.get(left)) < 0) {
+ extreme = left;
+ }
+
+ if (right < data.size() &&
+ comparator.compare(data.get(extreme), data.get(right)) < 0) {
+ extreme = right;
+ }
+
+ if (extreme != i) {
+ swap(i, extreme);
+ heapify(extreme);
+ }
+ }
+
+ // Swaps two heap items identified by their respective indexes.
+ private void swap(int i, int k) {
+ T aux = data.get(i);
+ data.set(i, data.get(k));
+ data.set(k, aux);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof Heap) {
+ Heap that = (Heap) obj;
+ return this.getClass() == that.getClass() &&
+ Objects.equals(this.comparator, that.comparator) &&
+ Objects.deepEquals(this.data, that.data);
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(comparator, data);
+ }
+
+ @Override
+ public String toString() {
+ return com.google.common.base.Objects.toStringHelper(this)
+ .add("data", data)
+ .add("comparator", comparator)
+ .toString();
+ }
+
+}