Added graph-related utility code.
diff --git a/utils/misc/pom.xml b/utils/misc/pom.xml
index 5862727..79a0780 100644
--- a/utils/misc/pom.xml
+++ b/utils/misc/pom.xml
@@ -17,6 +17,12 @@
<description>Miscellaneous ON.Lab utilities</description>
<dependencies>
+ <dependency>
+ <groupId>com.google.guava</groupId>
+ <artifactId>guava-testlib</artifactId>
+ <version>17.0</version>
+ <scope>test</scope>
+ </dependency>
</dependencies>
</project>
diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractEdge.java b/utils/misc/src/main/java/org/onlab/graph/AbstractEdge.java
new file mode 100644
index 0000000..7ee86f4
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractEdge.java
@@ -0,0 +1,57 @@
+package org.onlab.graph;
+
+import java.util.Objects;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Abstract graph edge implementation.
+ */
+public abstract class AbstractEdge<V extends Vertex> implements Edge<V> {
+
+ private final V src;
+ private final V dst;
+
+ /**
+ * Creates a new edge between the specified source and destination vertexes.
+ *
+ * @param src source vertex
+ * @param dst destination vertex
+ */
+ public AbstractEdge(V src, V dst) {
+ this.src = checkNotNull(src, "Source vertex cannot be null");
+ this.dst = checkNotNull(dst, "Destination vertex cannot be null");
+ }
+
+ @Override
+ public V src() {
+ return src;
+ }
+
+ @Override
+ public V dst() {
+ return dst;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(src, dst);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof AbstractEdge) {
+ final AbstractEdge other = (AbstractEdge) obj;
+ return Objects.equals(this.src, other.src) && Objects.equals(this.dst, other.dst);
+ }
+ return false;
+ }
+
+ @Override
+ public String toString() {
+ return com.google.common.base.Objects.toStringHelper(this)
+ .add("src", src)
+ .add("dst", dst)
+ .toString();
+ }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
new file mode 100644
index 0000000..b3ebbdb
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
@@ -0,0 +1,273 @@
+package org.onlab.graph;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Basis for various graph path search algorithm implementations.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public abstract class AbstractPathSearch<V extends Vertex, E extends Edge<V>>
+ implements GraphPathSearch<V, E> {
+
+ private double samenessThreshold = 0.000000001;
+
+ /**
+ * Sets a new sameness threshold for comparing cost values; default is
+ * is {@code 0.000000001}.
+ *
+ * @param threshold fractional double value
+ */
+ public void setSamenessThreshold(double threshold) {
+ samenessThreshold = threshold;
+ }
+
+ /**
+ * Returns the current sameness threshold for comparing cost values.
+ *
+ * @return current threshold
+ */
+ public double samenessThreshold() {
+ return samenessThreshold;
+ }
+
+ /**
+ * Default path search result that uses the DefaultPath to convey paths
+ * in a graph.
+ */
+ protected class DefaultResult implements Result<V, E> {
+
+ private final V src;
+ private final V dst;
+ protected final Set<Path<V, E>> paths = new HashSet<>();
+ protected final Map<V, Double> costs = new HashMap<>();
+ protected final Map<V, Set<E>> parents = new HashMap<>();
+
+ /**
+ * Creates the result of path search.
+ *
+ * @param src path source
+ * @param dst optional path destination
+ */
+ public DefaultResult(V src, V dst) {
+ checkNotNull(src, "Source cannot be null");
+ this.src = src;
+ this.dst = dst;
+ }
+
+ @Override
+ public V src() {
+ return src;
+ }
+
+ @Override
+ public V dst() {
+ return dst;
+ }
+
+ @Override
+ public Set<Path<V, E>> paths() {
+ return paths;
+ }
+
+ @Override
+ public Map<V, Double> costs() {
+ return costs;
+ }
+
+ @Override
+ public Map<V, Set<E>> parents() {
+ return parents;
+ }
+
+ /**
+ * Indicates whether or not the given vertex has a cost yet.
+ *
+ * @param v vertex to test
+ * @return true if the vertex has cost already
+ */
+ boolean hasCost(V v) {
+ return costs.get(v) != null;
+ }
+
+ /**
+ * Returns the current cost to reach the specified vertex.
+ *
+ * @return cost to reach the vertex
+ */
+ double cost(V v) {
+ Double c = costs.get(v);
+ return c == null ? Double.MAX_VALUE : c;
+ }
+
+ /**
+ * Updates the cost of the vertex using its existing cost plus the
+ * cost to traverse the specified edge.
+ *
+ * @param v vertex
+ * @param edge edge through which vertex is reached
+ * @param cost current cost to reach the vertex from the source
+ * @param replace true to indicate that any accrued edges are to be
+ * cleared; false to indicate that the edge should be
+ * added to the previously accrued edges as they yield
+ * the same cost
+ */
+ void updateVertex(V v, E edge, double cost, boolean replace) {
+ costs.put(v, cost);
+ if (edge != null) {
+ Set<E> edges = parents.get(v);
+ if (edges == null) {
+ edges = new HashSet<>();
+ parents.put(v, edges);
+ }
+ if (replace) {
+ edges.clear();
+ }
+ edges.add(edge);
+ }
+ }
+
+ /**
+ * Removes the set of parent edges for the specified vertex.
+ *
+ * @param v vertex
+ */
+ void removeVertex(V v) {
+ parents.remove(v);
+ }
+
+ /**
+ * If possible, relax the specified edge using the supplied base cost
+ * and edge-weight function.
+ *
+ * @param e edge to be relaxed
+ * @param cost base cost to reach the edge destination vertex
+ * @param ew optional edge weight function
+ * @return true if the edge was relaxed; false otherwise
+ */
+ boolean relaxEdge(E e, double cost, EdgeWeight<V, E> ew) {
+ V v = e.dst();
+ double oldCost = cost(v);
+ double newCost = cost + (ew == null ? 1.0 : ew.weight(e));
+ boolean relaxed = newCost < oldCost;
+ boolean same = Math.abs(newCost - oldCost) < samenessThreshold;
+ if (same || relaxed) {
+ updateVertex(v, e, newCost, !same);
+ }
+ return relaxed;
+ }
+
+ /**
+ * Builds a set of paths for the specified src/dst vertex pair.
+ */
+ protected void buildPaths() {
+ Set<V> destinations = new HashSet<>();
+ if (dst == null) {
+ destinations.addAll(costs.keySet());
+ } else {
+ destinations.add(dst);
+ }
+
+ // Build all paths between the source and all requested destinations.
+ for (V v : destinations) {
+ // Ignore the source, if it is among the destinations.
+ if (!v.equals(src)) {
+ buildAllPaths(this, src, v);
+ }
+ }
+ }
+
+ }
+
+ /**
+ * Builds a set of all paths between the source and destination using the
+ * graph search result by applying breadth-first search through the parent
+ * edges and vertex costs.
+ *
+ * @param result graph search result
+ * @param src source vertex
+ * @param dst destination vertex
+ */
+ private void buildAllPaths(DefaultResult result, V src, V dst) {
+ DefaultMutablePath<V, E> basePath = new DefaultMutablePath<>();
+ basePath.setCost(result.cost(dst));
+
+ Set<DefaultMutablePath<V, E>> pendingPaths = new HashSet<>();
+ pendingPaths.add(basePath);
+
+ while (!pendingPaths.isEmpty()) {
+ Set<DefaultMutablePath<V, E>> frontier = new HashSet<>();
+
+ for (DefaultMutablePath<V, E> path : pendingPaths) {
+ // For each pending path, locate its first vertex since we
+ // will be moving backwards from it.
+ V firstVertex = firstVertex(path, dst);
+
+ // If the first vertex is our expected source, we have reached
+ // the beginning, so add the this path to the result paths.
+ if (firstVertex.equals(src)) {
+ path.setCost(result.cost(dst));
+ result.paths.add(new DefaultPath<>(path.edges(), path.cost()));
+
+ } else {
+ // If we have not reached the beginning, i.e. the source,
+ // fetch the set of edges leading to the first vertex of
+ // this pending path; if there are none, abandon processing
+ // this path for good.
+ Set<E> firstVertexParents = result.parents.get(firstVertex);
+ if (firstVertexParents == null || firstVertexParents.isEmpty()) {
+ break;
+ }
+
+ // Now iterate over all the edges and for each of them
+ // cloning the current path and then insert that edge to
+ // the path and then add that path to the pending ones.
+ // When processing the last edge, modify the current
+ // pending path rather than cloning a new one.
+ Iterator<E> edges = firstVertexParents.iterator();
+ while (edges.hasNext()) {
+ E edge = edges.next();
+ boolean isLast = !edges.hasNext();
+ DefaultMutablePath<V, E> pendingPath = isLast ? path : new DefaultMutablePath<>(path);
+ pendingPath.insertEdge(edge);
+ frontier.add(pendingPath);
+ }
+ }
+ }
+
+ // All pending paths have been scanned so promote the next frontier
+ pendingPaths = frontier;
+ }
+ }
+
+ // Returns the first vertex of the specified path. This is either the source
+ // of the first edge or, if there are no edges yet, the given destination.
+ private V firstVertex(Path<V, E> path, V dst) {
+ return path.edges().isEmpty() ? dst : path.edges().get(0).src();
+ }
+
+ /**
+ * Checks the specified path search arguments for validity.
+ *
+ * @param graph graph; must not be null
+ * @param src source vertex; must not be null and belong to graph
+ * @param dst optional target vertex; must belong to graph
+ */
+ protected void checkArguments(Graph<V, E> graph, V src, V dst) {
+ checkNotNull(graph, "Graph cannot be null");
+ checkNotNull(src, "Source cannot be null");
+ Set<V> vertices = graph.getVertexes();
+ checkArgument(vertices.contains(src), "Source not in the graph");
+ checkArgument(dst == null || vertices.contains(dst),
+ "Destination not in graph");
+ }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java b/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java
new file mode 100644
index 0000000..a5a1300
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java
@@ -0,0 +1,104 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSetMultimap;
+
+import java.util.Objects;
+import java.util.Set;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Immutable graph implemented using adjacency lists.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public class AdjacencyListsGraph<V extends Vertex, E extends Edge<V>> implements Graph<V, E> {
+
+ private final Set<V> vertexes;
+ private final Set<E> edges;
+
+ private final ImmutableSetMultimap<V, E> sources;
+ private final ImmutableSetMultimap<V, E> destinations;
+
+ private final Set<E> noEdges = ImmutableSet.of();
+
+ /**
+ * Creates a graph comprising of the specified vertexes and edges.
+ *
+ * @param vertexes set of graph vertexes
+ * @param edges set of graph edges
+ */
+ public AdjacencyListsGraph(Set<V> vertexes, Set<E> edges) {
+ checkNotNull(vertexes, "Vertex set cannot be null");
+ checkNotNull(edges, "Edge set cannot be null");
+
+ // Record ingress/egress edges for each vertex.
+ ImmutableSetMultimap.Builder<V, E> srcMap = ImmutableSetMultimap.builder();
+ ImmutableSetMultimap.Builder<V, E> dstMap = ImmutableSetMultimap.builder();
+
+ // Also make sure that all edge end-points are added as vertexes
+ ImmutableSet.Builder<V> actualVertexes = ImmutableSet.builder();
+ actualVertexes.addAll(vertexes);
+
+ for (E edge : edges) {
+ srcMap.put(edge.src(), edge);
+ actualVertexes.add(edge.src());
+ dstMap.put(edge.dst(), edge);
+ actualVertexes.add(edge.dst());
+ }
+
+ // Make an immutable copy of the edge and vertex sets
+ this.edges = ImmutableSet.copyOf(edges);
+ this.vertexes = actualVertexes.build();
+
+ // Build immutable copies of sources and destinations edge maps
+ sources = srcMap.build();
+ destinations = dstMap.build();
+ }
+
+ @Override
+ public Set<V> getVertexes() {
+ return vertexes;
+ }
+
+ @Override
+ public Set<E> getEdges() {
+ return edges;
+ }
+
+ @Override
+ public Set<E> getEdgesFrom(V src) {
+ return sources.get(src);
+ }
+
+ @Override
+ public Set<E> getEdgesTo(V dst) {
+ return destinations.get(dst);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof AdjacencyListsGraph) {
+ AdjacencyListsGraph that = (AdjacencyListsGraph) obj;
+ return this.getClass() == that.getClass() &&
+ Objects.equals(this.vertexes, that.vertexes) &&
+ Objects.equals(this.edges, that.edges);
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(vertexes, edges);
+ }
+
+ @Override
+ public String toString() {
+ return com.google.common.base.Objects.toStringHelper(this)
+ .add("vertexes", vertexes)
+ .add("edges", edges)
+ .toString();
+ }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
new file mode 100644
index 0000000..0ef4f98
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
@@ -0,0 +1,116 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Simple concrete implementation of a directed graph path.
+ */
+public class DefaultMutablePath<V extends Vertex, E extends Edge<V>> implements MutablePath<V, E> {
+
+ private V src = null;
+ private V dst = null;
+ private final List<E> edges = new ArrayList<>();
+ private double cost = 0.0;
+
+ /**
+ * Creates a new empty path.
+ */
+ public DefaultMutablePath() {
+ }
+
+ /**
+ * Creates a new path as a copy of another path.
+ *
+ * @param path path to be copied
+ */
+ public DefaultMutablePath(Path<V, E> path) {
+ checkNotNull(path, "Path cannot be null");
+ this.src = path.src();
+ this.dst = path.dst();
+ this.cost = path.cost();
+ edges.addAll(path.edges());
+ }
+
+ @Override
+ public V src() {
+ return src;
+ }
+
+ @Override
+ public V dst() {
+ return dst;
+ }
+
+ @Override
+ public double cost() {
+ return cost;
+ }
+
+ @Override
+ public List<E> edges() {
+ return ImmutableList.copyOf(edges);
+ }
+
+ @Override
+ public void setCost(double cost) {
+ this.cost = cost;
+ }
+
+ @Override
+ public Path<V, E> toImmutable() {
+ return new DefaultPath<>(edges, cost);
+ }
+
+ @Override
+ public void appendEdge(E edge) {
+ checkNotNull(edge, "Edge cannot be null");
+ checkArgument(edges.isEmpty() || dst.equals(edge.src()),
+ "Edge source must be the same as the current path destination");
+ dst = edge.dst();
+ edges.add(edge);
+ }
+
+ @Override
+ public void insertEdge(E edge) {
+ checkNotNull(edge, "Edge cannot be null");
+ checkArgument(edges.isEmpty() || src.equals(edge.dst()),
+ "Edge destination must be the same as the current path source");
+ src = edge.src();
+ edges.add(0, edge);
+ }
+
+ @Override
+ public String toString() {
+ return com.google.common.base.Objects.toStringHelper(this)
+ .add("src", src)
+ .add("dst", dst)
+ .add("cost", cost)
+ .add("edges", edges)
+ .toString();
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(src, dst, edges, cost);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof DefaultMutablePath) {
+ final DefaultMutablePath other = (DefaultMutablePath) obj;
+ return super.equals(obj) &&
+ Objects.equals(this.src, other.src) &&
+ Objects.equals(this.dst, other.dst) &&
+ Objects.equals(this.cost, other.cost) &&
+ Objects.equals(this.edges, other.edges);
+ }
+ return false;
+ }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
new file mode 100644
index 0000000..b0cd098
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
@@ -0,0 +1,85 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.Collections;
+import java.util.List;
+import java.util.Objects;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * Simple concrete implementation of a directed graph path.
+ */
+public class DefaultPath<V extends Vertex, E extends Edge<V>> implements Path<V, E> {
+
+ private final V src;
+ private final V dst;
+ private final List<E> edges;
+ private double cost = 0.0;
+
+ /**
+ * Creates a new path from the specified list of edges and cost.
+ *
+ * @param edges list of path edges
+ * @param cost path cost as a unit-less number
+ */
+ public DefaultPath(List<E> edges, double cost) {
+ checkNotNull(edges, "Edges list must not be null");
+ checkArgument(!edges.isEmpty(), "There must be at least one edge");
+ this.edges = ImmutableList.copyOf(edges);
+ this.src = edges.get(0).src();
+ this.dst = edges.get(edges.size() - 1).dst();
+ this.cost = cost;
+ }
+
+ @Override
+ public V src() {
+ return src;
+ }
+
+ @Override
+ public V dst() {
+ return dst;
+ }
+
+ @Override
+ public double cost() {
+ return cost;
+ }
+
+ @Override
+ public List<E> edges() {
+ return Collections.unmodifiableList(edges);
+ }
+
+ @Override
+ public String toString() {
+ return com.google.common.base.Objects.toStringHelper(this)
+ .add("src", src)
+ .add("dst", dst)
+ .add("cost", cost)
+ .add("edges", edges)
+ .toString();
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(src, dst, edges, cost);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof DefaultPath) {
+ final DefaultPath other = (DefaultPath) obj;
+ return super.equals(obj) &&
+ Objects.equals(this.src, other.src) &&
+ Objects.equals(this.dst, other.dst) &&
+ Objects.equals(this.cost, other.cost) &&
+ Objects.equals(this.edges, other.edges);
+ }
+ return false;
+ }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
new file mode 100644
index 0000000..9b27bd8
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -0,0 +1,76 @@
+package org.onlab.graph;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Set;
+
+/**
+ * Dijkstra shortest-path graph search algorithm capable of finding not just
+ * one, but all shortest paths between the source and destinations.
+ */
+public class DijkstraGraphSearch<V extends Vertex, E extends Edge<V>>
+ extends AbstractPathSearch<V, E> {
+
+ @Override
+ public Result<V, E> search(Graph<V, E> g, V src, V dst, EdgeWeight<V, E> ew) {
+ checkArguments(g, src, dst);
+
+ // Use the default result to remember cumulative costs and parent
+ // edges to each each respective vertex.
+ DefaultResult result = new DefaultResult(src, dst);
+
+ // Cost to reach the source vertex is 0 of course.
+ result.updateVertex(src, null, 0.0, false);
+
+ // Use the min priority queue to progressively find each nearest
+ // vertex until we reach the desired destination, if one was given,
+ // or until we reach all possible destinations.
+ Heap<V> minQueue = createMinQueue(g.getVertexes(),
+ new PathCostComparator(result));
+ while (!minQueue.isEmpty()) {
+ // Get the nearest vertex
+ V nearest = minQueue.extractExtreme();
+ if (nearest.equals(dst)) {
+ break;
+ }
+
+ // Find its cost and use it to determine if the vertex is reachable.
+ double cost = result.cost(nearest);
+ if (cost < Double.MAX_VALUE) {
+ // If the vertex is reachable, relax all its egress edges.
+ for (E e : g.getEdgesFrom(nearest)) {
+ result.relaxEdge(e, cost, ew);
+ }
+ }
+
+ // Re-prioritize the min queue.
+ minQueue.heapify();
+ }
+
+ // Now construct a set of paths from the results.
+ result.buildPaths();
+ return result;
+ }
+
+ // Compares path weights using their accrued costs; used for sorting the
+ // min priority queue.
+ private final class PathCostComparator implements Comparator<V> {
+ private final DefaultResult result;
+
+ private PathCostComparator(DefaultResult result) {
+ this.result = result;
+ }
+
+ @Override
+ public int compare(V v1, V v2) {
+ double delta = result.cost(v2) - result.cost(v1);
+ return delta < 0 ? -1 : (delta > 0 ? 1 : 0);
+ }
+ }
+
+ // Creates a min priority queue from the specified vertexes and comparator.
+ private Heap<V> createMinQueue(Set<V> vertexes, Comparator<V> comparator) {
+ return new Heap<>(new ArrayList<>(vertexes), comparator);
+ }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/Edge.java b/utils/misc/src/main/java/org/onlab/graph/Edge.java
new file mode 100644
index 0000000..d4031f5
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/Edge.java
@@ -0,0 +1,24 @@
+package org.onlab.graph;
+
+/**
+ * Representation of a graph edge.
+ *
+ * @param <V> vertex type
+ */
+public interface Edge<V extends Vertex> {
+
+ /**
+ * Returns the edge source vertex.
+ *
+ * @return source vertex
+ */
+ V src();
+
+ /**
+ * Returns the edge destination vertex.
+ *
+ * @return destination vertex
+ */
+ V dst();
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java b/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java
new file mode 100644
index 0000000..b0630a0
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java
@@ -0,0 +1,16 @@
+package org.onlab.graph;
+
+/**
+ * Abstraction of a graph edge weight function.
+ */
+public interface EdgeWeight<V extends Vertex, E extends Edge<V>> {
+
+ /**
+ * Returns the weight of the given edge as a unit-less number.
+ *
+ * @param edge edge to be weighed
+ * @return edge weight as a unit-less number
+ */
+ double weight(E edge);
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/Graph.java b/utils/misc/src/main/java/org/onlab/graph/Graph.java
new file mode 100644
index 0000000..137ec8d
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/Graph.java
@@ -0,0 +1,44 @@
+package org.onlab.graph;
+
+
+import java.util.Set;
+
+/**
+ * Abstraction of a directed graph structure.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public interface Graph<V extends Vertex, E extends Edge> {
+
+ /**
+ * Returns the set of vertexes comprising the graph.
+ *
+ * @return set of vertexes
+ */
+ Set<V> getVertexes();
+
+ /**
+ * Returns the set of edges comprising the graph.
+ *
+ * @return set of edges
+ */
+ Set<E> getEdges();
+
+ /**
+ * Returns all edges leading out from the specified source vertex.
+ *
+ * @param src source vertex
+ * @return set of egress edges; empty if no such edges
+ */
+ Set<E> getEdgesFrom(V src);
+
+ /**
+ * Returns all edges leading towards the specified destination vertex.
+ *
+ * @param dst destination vertex
+ * @return set of ingress vertexes; empty if no such edges
+ */
+ Set<E> getEdgesTo(V dst);
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
new file mode 100644
index 0000000..e8df185
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
@@ -0,0 +1,68 @@
+package org.onlab.graph;
+
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Representation of a graph path search algorithm.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public interface GraphPathSearch<V extends Vertex, E extends Edge<V>> {
+
+ /**
+ * Abstraction of a path search result.
+ */
+ public interface Result<V extends Vertex, E extends Edge<V>> {
+
+ /**
+ * Returns the search source.
+ *
+ * @return search source
+ */
+ public V src();
+
+ /**
+ * Returns the search destination, if was was given.
+ *
+ * @return optional search destination
+ */
+ public V dst();
+
+ /**
+ * Returns the set of paths produced as a result of the graph search.
+ *
+ * @return set of paths
+ */
+ Set<Path<V, E>> paths();
+
+ /**
+ * Returns bindings of each vertex to its parent edges in the path.
+ *
+ * @return map of vertex to its parent edge bindings
+ */
+ public Map<V, Set<E>> parents();
+
+ /**
+ * Return a bindings of each vertex to its cost in the path.
+ *
+ * @return map of vertex to path cost bindings
+ */
+ public Map<V, Double> costs();
+ }
+
+ /**
+ * Searches the specified graph.
+ *
+ * @param graph graph to be searched
+ * @param src optional source vertex
+ * @param dst optional destination vertex; if null paths to all vertex
+ * destinations will be searched
+ * @param weight optional edge-weight; if null cost of each edge will be
+ * assumed to be 1.0
+ * @return search results
+ */
+ Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight);
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
new file mode 100644
index 0000000..4686851
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
@@ -0,0 +1,28 @@
+package org.onlab.graph;
+
+/**
+ * Representation of a graph search algorithm and its outcome.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public interface GraphSearch<V extends Vertex, E extends Edge<V>> {
+
+ /**
+ * Notion of a graph search result.
+ */
+ public interface Result<V extends Vertex, E extends Edge<V>> {
+ }
+
+ /**
+ * Searches the specified graph.
+ *
+ * @param graph graph to be searched
+ * @param weight optional edge-weight; if null cost of each edge will be
+ * assumed to be 1.0
+ *
+ * @return search results
+ */
+ Result search(Graph<V, E> graph, EdgeWeight<V, E> weight);
+
+}
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();
+ }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/MutableGraph.java b/utils/misc/src/main/java/org/onlab/graph/MutableGraph.java
new file mode 100644
index 0000000..2974a88
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/MutableGraph.java
@@ -0,0 +1,44 @@
+package org.onlab.graph;
+
+/**
+ * Abstraction of a mutable graph that can be constructed gradually.
+ */
+public interface MutableGraph<V extends Vertex, E extends Edge> extends Graph<V, E> {
+
+ /**
+ * Adds the specified vertex to this graph.
+ *
+ * @param vertex new vertex
+ */
+ void addVertex(V vertex);
+
+ /**
+ * Removes the specified vertex from the graph.
+ *
+ * @param vertex vertex to be removed
+ */
+ void removeVertex(V vertex);
+
+ /**
+ * Adds the specified edge to this graph. If the edge vertexes are not
+ * already in the graph, they will be added as well.
+ *
+ * @param edge new edge
+ */
+ void addEdge(E edge);
+
+ /**
+ * Removes the specified edge from the graph.
+ *
+ * @param edge edge to be removed
+ */
+ void removeEdge(E edge);
+
+ /**
+ * Returns an immutable copy of this graph.
+ *
+ * @return immutable copy
+ */
+ Graph<V, E> toImmutable();
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
new file mode 100644
index 0000000..c0a72c9
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
@@ -0,0 +1,38 @@
+package org.onlab.graph;
+
+/**
+ * Abstraction of a mutable path that allows gradual construction.
+ */
+public interface MutablePath<V extends Vertex, E extends Edge<V>> extends Path<V, E> {
+
+ /**
+ * Inserts a new edge at the beginning of this path. The edge must be
+ * adjacent to the prior start of the path.
+ *
+ * @param edge edge to be inserted
+ */
+ void insertEdge(E edge);
+
+ /**
+ * Appends a new edge at the end of the this path. The edge must be
+ * adjacent to the prior end of the path.
+ *
+ * @param edge edge to be inserted
+ */
+ void appendEdge(E edge);
+
+ /**
+ * Sets the total path cost as a unit-less double.
+ *
+ * @param cost new path cost
+ */
+ void setCost(double cost);
+
+ /**
+ * Returns an immutable copy of this path.
+ *
+ * @return immutable copy
+ */
+ Path<V, E> toImmutable();
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/Path.java b/utils/misc/src/main/java/org/onlab/graph/Path.java
new file mode 100644
index 0000000..35f512b
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/Path.java
@@ -0,0 +1,30 @@
+package org.onlab.graph;
+
+import java.util.List;
+
+/**
+ * Representation of a path in a graph as a sequence of edges. Paths are
+ * assumed to be continuous, where adjacent edges must share a vertex.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public interface Path<V extends Vertex, E extends Edge<V>> extends Edge<V> {
+
+ /**
+ * Returns the list of edges comprising the path. Adjacent edges will
+ * share the same vertex, meaning that a source of one edge, will be the
+ * same as the destination of the prior edge.
+ *
+ * @return list of path edges
+ */
+ List<E> edges();
+
+ /**
+ * Returns the total cost of the path as a unit-less number.
+ *
+ * @return path cost as a unit-less number
+ */
+ double cost();
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/Vertex.java b/utils/misc/src/main/java/org/onlab/graph/Vertex.java
new file mode 100644
index 0000000..09d43b3
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/Vertex.java
@@ -0,0 +1,7 @@
+package org.onlab.graph;
+
+/**
+ * Representation of a graph vertex.
+ */
+public interface Vertex {
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
new file mode 100644
index 0000000..4384a66
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
@@ -0,0 +1,22 @@
+package org.onlab.graph;
+
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+/**
+ * Test of the base edge implementation.
+ */
+public class AbstractEdgeTest {
+
+ @Test
+ public void equality() {
+ TestVertex v1 = new TestVertex("1");
+ TestVertex v2 = new TestVertex("2");
+ new EqualsTester()
+ .addEqualityGroup(new TestEdge(v1, v2, 1),
+ new TestEdge(v1, v2, 1))
+ .addEqualityGroup(new TestEdge(v2, v1, 1))
+ .testEquals();
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java
new file mode 100644
index 0000000..00ba3da
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphSearchTest.java
@@ -0,0 +1,37 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+import org.junit.Test;
+
+/**
+ * Base for all graph search tests.
+ */
+public abstract class AbstractGraphSearchTest extends GraphTest {
+
+ /**
+ * Creates a graph search to be tested.
+ *
+ * @return graph search
+ */
+ protected abstract GraphPathSearch<TestVertex, TestEdge> graphSearch();
+
+ @Test(expected = IllegalArgumentException.class)
+ public void badSource() {
+ graphSearch().search(new AdjacencyListsGraph<>(ImmutableSet.of(B, C),
+ ImmutableSet.of(new TestEdge(B, C, 1))),
+ A, H, weight);
+ }
+
+ @Test(expected = NullPointerException.class)
+ public void nullSource() {
+ graphSearch().search(new AdjacencyListsGraph<>(ImmutableSet.of(B, C),
+ ImmutableSet.of(new TestEdge(B, C, 1))),
+ null, H, weight);
+ }
+
+ @Test(expected = NullPointerException.class)
+ public void nullGraph() {
+ graphSearch().search(null, A, H, weight);
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
new file mode 100644
index 0000000..e61583d
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
@@ -0,0 +1,56 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Tests of the graph implementation.
+ */
+public class AdjacencyListsGraphTest {
+
+ private static final TestVertex A = new TestVertex("A");
+ private static final TestVertex B = new TestVertex("B");
+ private static final TestVertex C = new TestVertex("C");
+ private static final TestVertex D = new TestVertex("D");
+ private static final TestVertex E = new TestVertex("E");
+ private static final TestVertex F = new TestVertex("F");
+ private static final TestVertex G = new TestVertex("G");
+
+ private final Set<TestEdge> edges =
+ ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(A, C, 1),
+ new TestEdge(B, C, 1), new TestEdge(C, D, 1),
+ new TestEdge(D, A, 1));
+
+ @Test
+ public void basics() {
+ Set<TestVertex> vertexes = ImmutableSet.of(A, B, C, D, E, F);
+ AdjacencyListsGraph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(vertexes, edges);
+ assertEquals("incorrect vertex count", 6, graph.getVertexes().size());
+ assertEquals("incorrect edge count", 5, graph.getEdges().size());
+
+ assertEquals("incorrect egress edge count", 2, graph.getEdgesFrom(A).size());
+ assertEquals("incorrect ingress edge count", 1, graph.getEdgesTo(A).size());
+ assertEquals("incorrect ingress edge count", 2, graph.getEdgesTo(C).size());
+ assertEquals("incorrect egress edge count", 1, graph.getEdgesFrom(C).size());
+ }
+
+ @Test
+ public void equality() {
+ Set<TestVertex> vertexes = ImmutableSet.of(A, B, C, D, E, F);
+ Set<TestVertex> vertexes2 = ImmutableSet.of(A, B, C, D, E, F, G);
+
+ AdjacencyListsGraph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(vertexes, edges);
+ AdjacencyListsGraph<TestVertex, TestEdge> same = new AdjacencyListsGraph<>(vertexes, edges);
+ AdjacencyListsGraph<TestVertex, TestEdge> different = new AdjacencyListsGraph<>(vertexes2, edges);
+
+ new EqualsTester()
+ .addEqualityGroup(graph, same)
+ .addEqualityGroup(different)
+ .testEquals();
+ }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
new file mode 100644
index 0000000..ae45750
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -0,0 +1,48 @@
+package org.onlab.graph;
+
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Test of the BFS algorithm.
+ */
+public abstract class BreadthFirstSearchTest extends AbstractGraphSearchTest {
+
+ @Override
+ protected GraphPathSearch<TestVertex, TestEdge> graphSearch() {
+ return null; // new BreadthFirstSearch();
+ }
+
+ @Test
+ public void basics() {
+ runBasics(3, 8.0, 7);
+ }
+
+ @Test
+ public void defaultWeight() {
+ weight = null;
+ runBasics(3, 3.0, 7);
+ }
+
+ protected void runBasics(int expectedLength, double expectedCost, int expectedPaths) {
+ g = new AdjacencyListsGraph<>(vertices(), edges());
+
+ GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths();
+ assertEquals("incorrect paths count", 1, paths.size());
+
+ Path p = paths.iterator().next();
+ assertEquals("incorrect src", A, p.src());
+ assertEquals("incorrect dst", H, p.dst());
+ assertEquals("incorrect path length", expectedLength, p.edges().size());
+ assertEquals("incorrect path cost", expectedCost, p.cost(), 0.1);
+
+ paths = search.search(g, A, null, weight).paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", expectedPaths, paths.size());
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
new file mode 100644
index 0000000..5ee4caa
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -0,0 +1,110 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+import org.junit.Test;
+
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Test of the Dijkstra algorithm.
+ */
+public class DijkstraGraphSearchTest extends BreadthFirstSearchTest {
+
+ @Override
+ protected GraphPathSearch<TestVertex, TestEdge> graphSearch() {
+ return new DijkstraGraphSearch<>();
+ }
+
+ @Test
+ @Override
+ public void basics() {
+ runBasics(5, 5.0, 7);
+ }
+
+ @Test
+ public void defaultWeight() {
+ weight = null;
+ runBasics(3, 3.0, 10);
+ }
+
+ @Test
+ public void noPath() {
+ g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D),
+ ImmutableSet.of(new TestEdge(A, B, 1),
+ new TestEdge(B, A, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, C, 1)));
+
+ GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, B, weight).paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", 1, paths.size());
+ assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+
+ paths = gs.search(g, A, D, weight).paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", 0, paths.size());
+
+ paths = gs.search(g, A, null, weight).paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", 1, paths.size());
+ assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+ }
+
+ @Test
+ public void multiPath1() {
+ g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D),
+ ImmutableSet.of(new TestEdge(A, B, 1),
+ new TestEdge(A, C, 1),
+ new TestEdge(B, D, 1),
+ new TestEdge(C, D, 1)));
+
+ GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, D, weight).paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", 2, paths.size());
+ assertEquals("incorrect path cost", 2.0, paths.iterator().next().cost(), 0.1);
+ }
+
+ @Test
+ public void multiPath2() {
+ g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D, E, F, G),
+ ImmutableSet.of(new TestEdge(A, B, 1),
+ new TestEdge(A, C, 1),
+ new TestEdge(B, D, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, E, 1),
+ new TestEdge(D, F, 1),
+ new TestEdge(E, G, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(A, G, 4)));
+
+ GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+ GraphPathSearch.Result<TestVertex, TestEdge> gsr = gs.search(g, A, G, weight);
+ Set<Path<TestVertex, TestEdge>> paths = gsr.paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", 5, paths.size());
+ assertEquals("incorrect path cost", 4.0, paths.iterator().next().cost(), 0.1);
+ }
+
+ @Test
+ public void multiPath3() {
+ g = new AdjacencyListsGraph<>(ImmutableSet.of(A, B, C, D, E, F, G, H),
+ ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
+ new TestEdge(B, D, 2), new TestEdge(B, C, 1),
+ new TestEdge(B, E, 4), new TestEdge(C, E, 1),
+ new TestEdge(D, H, 5), new TestEdge(D, E, 1),
+ new TestEdge(E, F, 1), new TestEdge(F, D, 1),
+ new TestEdge(F, G, 1), new TestEdge(F, H, 1),
+ new TestEdge(A, E, 3), new TestEdge(B, D, 1)));
+
+ GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(g, A, E, weight).paths();
+ printPaths(paths);
+ assertEquals("incorrect paths count", 3, paths.size());
+ assertEquals("incorrect path cost", 3.0, paths.iterator().next().cost(), 0.1);
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
new file mode 100644
index 0000000..bb91e03
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -0,0 +1,50 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableSet;
+
+import java.util.Set;
+
+/**
+ * Base class for various graph-related tests.
+ */
+public class GraphTest {
+
+ static final TestVertex A = new TestVertex("A");
+ static final TestVertex B = new TestVertex("B");
+ static final TestVertex C = new TestVertex("C");
+ static final TestVertex D = new TestVertex("D");
+ static final TestVertex E = new TestVertex("E");
+ static final TestVertex F = new TestVertex("F");
+ static final TestVertex G = new TestVertex("G");
+ static final TestVertex H = new TestVertex("H");
+
+ protected Graph<TestVertex, TestEdge> g;
+
+ protected EdgeWeight<TestVertex, TestEdge> weight =
+ new EdgeWeight<TestVertex, TestEdge>() {
+ @Override
+ public double weight(TestEdge edge) {
+ return edge.weight();
+ }
+ };
+
+ protected void printPaths(Set<Path<TestVertex, TestEdge>> paths) {
+ for (Path p : paths) {
+ System.out.println(p);
+ }
+ }
+
+ protected Set<TestVertex> vertices() {
+ return ImmutableSet.of(A, B, C, D, E, F, G, H);
+ }
+
+ protected Set<TestEdge> edges() {
+ return ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(A, C, 3),
+ new TestEdge(B, D, 2), new TestEdge(B, C, 1),
+ new TestEdge(B, E, 4), new TestEdge(C, E, 1),
+ new TestEdge(D, H, 5), new TestEdge(D, E, 1),
+ new TestEdge(E, F, 1), new TestEdge(F, D, 1),
+ new TestEdge(F, G, 1), new TestEdge(F, H, 1));
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/HeapTest.java b/utils/misc/src/test/java/org/onlab/graph/HeapTest.java
new file mode 100644
index 0000000..0b1601d
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/HeapTest.java
@@ -0,0 +1,86 @@
+package org.onlab.graph;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Ordering;
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+
+import static org.junit.Assert.*;
+
+/**
+ * Heap data structure tests.
+ */
+public class HeapTest {
+
+ private ArrayList<Integer> data =
+ new ArrayList<>(ImmutableList.of(6, 4, 5, 9, 8, 3, 2, 1, 7, 0));
+
+ private static final Comparator<Integer> ASCENDING = Ordering.natural().reverse();
+ private static final Comparator<Integer> DESCENDING = Ordering.natural();
+
+ @Test
+ public void equality() {
+ new EqualsTester()
+ .addEqualityGroup(new Heap<>(data, ASCENDING),
+ new Heap<>(data, ASCENDING))
+ .addEqualityGroup(new Heap<>(data, DESCENDING))
+ .testEquals();
+ }
+
+ @Test
+ public void ascending() {
+ Heap<Integer> h = new Heap<>(data, ASCENDING);
+ assertEquals("incorrect size", 10, h.size());
+ assertFalse("should not be empty", h.isEmpty());
+ assertEquals("incorrect extreme", (Integer) 0, h.extreme());
+
+ for (int i = 0, n = h.size(); i < n; i++) {
+ assertEquals("incorrect element", (Integer) i, h.extractExtreme());
+ }
+ assertTrue("should be empty", h.isEmpty());
+ }
+
+ @Test
+ public void descending() {
+ Heap<Integer> h = new Heap<>(data, DESCENDING);
+ assertEquals("incorrect size", 10, h.size());
+ assertFalse("should not be empty", h.isEmpty());
+ assertEquals("incorrect extreme", (Integer) 9, h.extreme());
+
+ for (int i = h.size(); i > 0; i--) {
+ assertEquals("incorrect element", (Integer) (i - 1), h.extractExtreme());
+ }
+ assertTrue("should be empty", h.isEmpty());
+ }
+
+ @Test
+ public void empty() {
+ Heap<Integer> h = new Heap<>(new ArrayList<Integer>(), ASCENDING);
+ assertEquals("incorrect size", 0, h.size());
+ assertTrue("should be empty", h.isEmpty());
+ assertNull("no item expected", h.extreme());
+ assertNull("no item expected", h.extractExtreme());
+ }
+
+ @Test
+ public void insert() {
+ Heap<Integer> h = new Heap<>(data, ASCENDING);
+ assertEquals("incorrect size", 10, h.size());
+ h.insert(3);
+ assertEquals("incorrect size", 11, h.size());
+ }
+
+ @Test
+ public void iterator() {
+ Heap<Integer> h = new Heap<>(data, ASCENDING);
+ Iterator<Integer> it = h.iterator();
+ while (it.hasNext()) {
+ int item = it.next();
+ }
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
new file mode 100644
index 0000000..855730a
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
@@ -0,0 +1,46 @@
+package org.onlab.graph;
+
+import java.util.Objects;
+
+/**
+ * Test edge.
+ */
+public class TestEdge extends AbstractEdge<TestVertex> {
+
+ private final double weight;
+
+ /**
+ * Creates a new edge between the specified source and destination vertexes.
+ *
+ * @param src source vertex
+ * @param dst destination vertex
+ * @param weight edge weight
+ */
+ public TestEdge(TestVertex src, TestVertex dst, double weight) {
+ super(src, dst);
+ this.weight = weight;
+ }
+
+ /**
+ * Returns the edge weight.
+ *
+ * @return edge weight
+ */
+ public double weight() {
+ return weight;
+ }
+
+ @Override
+ public int hashCode() {
+ return 31 * super.hashCode() + Objects.hash(weight);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof TestEdge) {
+ final TestEdge other = (TestEdge) obj;
+ return super.equals(obj) && Objects.equals(this.weight, other.weight);
+ }
+ return false;
+ }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestVertex.java b/utils/misc/src/test/java/org/onlab/graph/TestVertex.java
new file mode 100644
index 0000000..2a1c7da
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TestVertex.java
@@ -0,0 +1,37 @@
+package org.onlab.graph;
+
+import java.util.Objects;
+
+import static com.google.common.base.Objects.toStringHelper;
+
+/**
+ * Test vertex.
+ */
+public class TestVertex implements Vertex {
+
+ private final String name;
+
+ public TestVertex(String name) {
+ this.name = name;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this).add("name", name).toString();
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(name);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof TestVertex) {
+ final TestVertex other = (TestVertex) obj;
+ return Objects.equals(this.name, other.name);
+ }
+ return false;
+ }
+
+}