Added more unit tests for the graph utilities.
diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
similarity index 98%
rename from utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
rename to utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index b3ebbdb..7dad767 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -15,7 +15,7 @@
* @param <V> vertex type
* @param <E> edge type
*/
-public abstract class AbstractPathSearch<V extends Vertex, E extends Edge<V>>
+public abstract class AbstractGraphPathSearch<V extends Vertex, E extends Edge<V>>
implements GraphPathSearch<V, E> {
private double samenessThreshold = 0.000000001;
diff --git a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
new file mode 100644
index 0000000..66dd33a
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
@@ -0,0 +1,57 @@
+package org.onlab.graph;
+
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * Implementation of the BFS algorithm.
+ */
+public class BreadthFirstSearch<V extends Vertex, E extends Edge<V>>
+ extends AbstractGraphPathSearch<V, E> {
+
+ @Override
+ public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> ew) {
+ checkArguments(graph, src, dst);
+
+ // Prepare the graph result.
+ DefaultResult result = new DefaultResult(src, dst);
+
+ // Setup the starting frontier with the source as the sole vertex.
+ Set<V> frontier = new HashSet<>();
+ result.costs.put(src, 0.0);
+ frontier.add(src);
+
+ search: while (!frontier.isEmpty()) {
+ // Prepare the next frontier.
+ Set<V> next = new HashSet<>();
+
+ // Visit all vertexes in the current frontier.
+ for (V vertex : frontier) {
+ double cost = result.cost(vertex);
+
+ // Visit all egress edges of the current frontier vertex.
+ for (E edge : graph.getEdgesFrom(vertex)) {
+ V nextVertex = edge.dst();
+ if (!result.hasCost(nextVertex)) {
+ // If this vertex has not been visited yet, update it.
+ result.updateVertex(nextVertex, edge,
+ cost + (ew == null ? 1.0 : ew.weight(edge)),
+ true);
+ // If we have reached our intended destination, bail.
+ if (nextVertex.equals(dst))
+ break search;
+ next.add(nextVertex);
+ }
+ }
+ }
+
+ // Promote the next frontier.
+ frontier = next;
+ }
+
+ // Finally, but the paths on the search result and return.
+ result.buildPaths();
+ return result;
+ }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
index 0ef4f98..be7ad18 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
@@ -14,8 +14,6 @@
*/
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;
@@ -32,20 +30,18 @@
*/
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;
+ return edges.isEmpty() ? null : edges.get(0).src();
}
@Override
public V dst() {
- return dst;
+ return edges.isEmpty() ? null : edges.get(edges.size() - 1).dst();
}
@Override
@@ -69,28 +65,35 @@
}
@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");
+ edges.add(0, edge);
+ }
+
+ @Override
public void appendEdge(E edge) {
checkNotNull(edge, "Edge cannot be null");
- checkArgument(edges.isEmpty() || dst.equals(edge.src()),
+ 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);
+ public void removeEdge(E edge) {
+ checkArgument(edge.src().equals(edge.dst()) ||
+ edges.indexOf(edge) == 0 ||
+ edges.lastIndexOf(edge) == edges.size() - 1,
+ "Edge must be at start or end of path, or it must be a cyclic edge");
+ edges.remove(edge);
}
@Override
public String toString() {
return com.google.common.base.Objects.toStringHelper(this)
- .add("src", src)
- .add("dst", dst)
+ .add("src", src())
+ .add("dst", dst())
.add("cost", cost)
.add("edges", edges)
.toString();
@@ -98,19 +101,17 @@
@Override
public int hashCode() {
- return Objects.hash(src, dst, edges, cost);
+ return Objects.hash(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) &&
+ return 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
index b0cd098..d7fc9e8a 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
@@ -73,8 +73,7 @@
public boolean equals(Object obj) {
if (obj instanceof DefaultPath) {
final DefaultPath other = (DefaultPath) obj;
- return super.equals(obj) &&
- Objects.equals(this.src, other.src) &&
+ return Objects.equals(this.src, other.src) &&
Objects.equals(this.dst, other.dst) &&
Objects.equals(this.cost, other.cost) &&
Objects.equals(this.edges, other.edges);
diff --git a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
index 9b27bd8..dc71859 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -9,7 +9,7 @@
* one, but all shortest paths between the source and destinations.
*/
public class DijkstraGraphSearch<V extends Vertex, E extends Edge<V>>
- extends AbstractPathSearch<V, E> {
+ extends AbstractGraphPathSearch<V, E> {
@Override
public Result<V, E> search(Graph<V, E> g, V src, V dst, EdgeWeight<V, E> ew) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
index c0a72c9..2d8420d 100644
--- a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
@@ -22,6 +22,15 @@
void appendEdge(E edge);
/**
+ * Removes the specified edge. This edge must be either at the start or
+ * at the end of the path, or it must be a cyclic edge in order not to
+ * violate the contiguous path property.
+ *
+ * @param edge edge to be removed
+ */
+ void removeEdge(E edge);
+
+ /**
* Sets the total path cost as a unit-less double.
*
* @param cost new path cost