Added Tarjan SCC computation algorithm and associated tests.
diff --git a/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
new file mode 100644
index 0000000..ebd451f
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
@@ -0,0 +1,195 @@
+package org.onlab.graph;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Tarjan algorithm for searching a graph and producing results describing
+ * the graph SCC (strongly-connected components).
+ */
+public class TarjanGraphSearch<V extends Vertex, E extends Edge<V>>
+ implements GraphSearch<V, E> {
+
+ /**
+ * {@inheritDoc}
+ * <p/>
+ * This implementation produces results augmented with information on
+ * SCCs within the graph.
+ * <p/>
+ * To prevent traversal of an edge, the {@link EdgeWeight#weight} should
+ * return a negative value as an edge weight.
+ */
+ @Override
+ public SCCResult<V, E> search(Graph<V, E> graph, EdgeWeight<V, E> weight) {
+ SCCResult<V, E> result = new SCCResult<>(graph);
+ for (V vertex : graph.getVertexes()) {
+ VertexData data = result.data(vertex);
+ if (data == null) {
+ connect(graph, vertex, weight, result);
+ }
+ }
+ return result.build();
+ }
+
+ /**
+ * Scans the specified graph, using recursion, and produces SCC results.
+ *
+ * @param graph graph to search
+ * @param vertex current vertex to scan and connect
+ * @param weight optional edge weight
+ * @param result graph search result
+ * @return augmentation vertexData for the current vertex
+ */
+ private VertexData<V> connect(Graph<V, E> graph, V vertex,
+ EdgeWeight<V, E> weight,
+ SCCResult<V, E> result) {
+ VertexData<V> data = result.addData(vertex);
+
+ // Scan through all egress edges of the current vertex.
+ for (E edge : graph.getEdgesFrom(vertex)) {
+ V nextVertex = edge.dst();
+
+ // If edge weight is negative, skip it.
+ if (weight != null && weight.weight(edge) < 0) {
+ continue;
+ }
+
+ // Attempt to get the augmentation vertexData for the next vertex.
+ VertexData<V> nextData = result.data(nextVertex);
+ if (nextData == null) {
+ // Next vertex has not been visited yet, so do this now.
+ nextData = connect(graph, nextVertex, weight, result);
+ data.lowLink = Math.min(data.lowLink, nextData.lowLink);
+
+ } else if (result.visited(nextData)) {
+ // Next vertex has been visited, which means it is in the
+ // same cluster as the current vertex.
+ data.lowLink = Math.min(data.lowLink, nextData.index);
+ }
+ }
+
+ if (data.lowLink == data.index) {
+ result.addCluster(data);
+ }
+ return data;
+ }
+
+ /**
+ * Graph search result augmented with SCC vertexData.
+ */
+ public static final class SCCResult<V extends Vertex, E extends Edge<V>>
+ implements Result {
+
+ private final Graph<V, E> graph;
+ private List<Set<V>> clusterVertexes = new ArrayList<>();
+ private List<Set<E>> clusterEdges = new ArrayList<>();
+
+ private int index = 0;
+ private final Map<V, VertexData<V>> vertexData = new HashMap<>();
+ private final List<VertexData<V>> visited = new ArrayList<>();
+
+ private SCCResult(Graph<V, E> graph) {
+ this.graph = graph;
+ }
+
+ /**
+ * Returns the number of SCC clusters in the graph.
+ *
+ * @return number of clusters
+ */
+ public int clusterCount() {
+ return clusterEdges.size();
+ }
+
+ /**
+ * Returns the list of strongly connected vertex clusters.
+ *
+ * @return list of strongly connected vertex sets
+ */
+ public List<Set<V>> clusterVertexes() {
+ return clusterVertexes;
+ }
+
+ /**
+ * Returns the list of edges linking strongly connected vertex clusters.
+ *
+ * @return list of strongly connected edge sets
+ */
+ public List<Set<E>> clusterEdges() {
+ return clusterEdges;
+ }
+
+ // Gets the augmentation vertexData for the specified vertex
+ private VertexData<V> data(V vertex) {
+ return vertexData.get(vertex);
+ }
+
+ // Adds augmentation vertexData for the specified vertex
+ private VertexData<V> addData(V vertex) {
+ VertexData<V> d = new VertexData<>(vertex, index);
+ vertexData.put(vertex, d);
+ visited.add(0, d);
+ index++;
+ return d;
+ }
+
+ // Indicates whether the given vertex has been visited
+ private boolean visited(VertexData data) {
+ return visited.contains(data);
+ }
+
+ // Adds a new cluster for the specified vertex
+ private void addCluster(VertexData data) {
+ Set<V> vertexes = findClusterVertices(data);
+ clusterVertexes.add(vertexes);
+ clusterEdges.add(findClusterEdges(vertexes));
+ }
+
+ private Set<V> findClusterVertices(VertexData data) {
+ VertexData<V> nextVertexData;
+ Set<V> vertexes = new HashSet<>();
+ do {
+ nextVertexData = visited.remove(0);
+ vertexes.add(nextVertexData.vertex);
+ } while (data != nextVertexData);
+ return Collections.unmodifiableSet(vertexes);
+ }
+
+ private Set<E> findClusterEdges(Set<V> vertexes) {
+ Set<E> edges = new HashSet<>();
+ for (V vertex : vertexes) {
+ for (E edge : graph.getEdgesFrom(vertex)) {
+ if (vertexes.contains((edge.dst()))) {
+ edges.add(edge);
+ }
+ }
+ }
+ return Collections.unmodifiableSet(edges);
+ }
+
+ public SCCResult<V, E> build() {
+ clusterVertexes = Collections.unmodifiableList(clusterVertexes);
+ clusterEdges = Collections.unmodifiableList(clusterEdges);
+ return this;
+ }
+ }
+
+ // Augments the vertex to assist in determining SCC clusters.
+ private static final class VertexData<V extends Vertex> {
+ final V vertex;
+ int index;
+ int lowLink;
+
+ private VertexData(V vertex, int index) {
+ this.vertex = vertex;
+ this.index = index;
+ this.lowLink = index;
+ }
+ }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
index 4ee9006..96985b5 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -31,17 +31,17 @@
@Test
public void searchGraphWithNegativeCycles() {
- Set<TestVertex> vertexes = new HashSet<>(vertices());
+ Set<TestVertex> vertexes = new HashSet<>(vertexes());
vertexes.add(Z);
Set<TestEdge> edges = new HashSet<>(edges());
edges.add(new TestEdge(G, Z, 1.0));
edges.add(new TestEdge(Z, G, -2.0));
- g = new AdjacencyListsGraph<>(vertexes, edges);
+ graph = new AdjacencyListsGraph<>(vertexes, edges);
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
assertEquals("incorrect paths count", 1, paths.size());
Path p = paths.iterator().next();
@@ -50,10 +50,10 @@
assertEquals("incorrect path length", 5, p.edges().size());
assertEquals("incorrect path cost", 5.0, p.cost(), 0.1);
- paths = search.search(g, A, G, weight).paths();
+ paths = search.search(graph, A, G, weight).paths();
assertEquals("incorrect paths count", 0, paths.size());
- paths = search.search(g, A, null, weight).paths();
+ paths = search.search(graph, A, null, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", 6, paths.size());
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
index f9c752d..d99e485 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -29,10 +29,10 @@
// Executes the default test
protected void executeDefaultTest(int pathCount, int pathLength, double pathCost) {
- g = new AdjacencyListsGraph<>(vertices(), edges());
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
assertEquals("incorrect paths count", 1, paths.size());
Path p = paths.iterator().next();
@@ -41,7 +41,7 @@
assertEquals("incorrect path length", pathLength, p.edges().size());
assertEquals("incorrect path cost", pathCost, p.cost(), 0.1);
- paths = search.search(g, A, null, weight).paths();
+ paths = search.search(graph, A, null, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", pathCount, paths.size());
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
index 8881e84..944919b 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
@@ -33,11 +33,11 @@
protected void executeDefaultTest(int minLength, int maxLength,
double minCost, double maxCost) {
- g = new AdjacencyListsGraph<>(vertices(), edges());
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(g, A, H, weight);
+ search.search(graph, A, H, weight);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
assertEquals("incorrect path count", 1, paths.size());
@@ -57,12 +57,12 @@
}
public void executeBroadSearch() {
- g = new AdjacencyListsGraph<>(vertices(), edges());
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
// Perform narrow path search to a specific destination.
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(g, A, null, weight);
+ search.search(graph, A, null, weight);
assertEquals("incorrect paths count", 7, result.paths().size());
int[] types = new int[]{0, 0, 0, 0};
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
index 1731440..840eddd 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -32,22 +32,22 @@
@Test
public void noPath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, A, 1),
- new TestEdge(C, D, 1),
- new TestEdge(D, C, 1)));
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ 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();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, 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();
+ paths = gs.search(graph, A, D, weight).paths();
printPaths(paths);
assertEquals("incorrect paths count", 0, paths.size());
- paths = gs.search(g, A, null, weight).paths();
+ paths = gs.search(graph, 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);
@@ -55,40 +55,40 @@
@Test
public void simpleMultiplePath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, 1),
- new TestEdge(A, C, 1),
- new TestEdge(B, D, 1),
- new TestEdge(C, D, 1)));
- executeSearch(graphSearch(), g, A, D, weight, 2, 2.0);
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(A, C, 1),
+ new TestEdge(B, D, 1),
+ new TestEdge(C, D, 1)));
+ executeSearch(graphSearch(), graph, A, D, weight, 2, 2.0);
}
@Test
public void denseMultiplePath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
- 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)));
- executeSearch(graphSearch(), g, A, G, weight, 5, 4.0);
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G),
+ 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)));
+ executeSearch(graphSearch(), graph, A, G, weight, 5, 4.0);
}
@Test
public void dualEdgeMultiplePath() {
- g = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H),
- 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)));
- executeSearch(graphSearch(), g, A, E, weight, 3, 3.0);
+ graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H),
+ 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)));
+ executeSearch(graphSearch(), graph, A, E, weight, 3, 3.0);
}
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
index 44b1137..5c930c4 100644
--- a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -19,7 +19,7 @@
static final TestVertex H = new TestVertex("H");
static final TestVertex Z = new TestVertex("Z");
- protected Graph<TestVertex, TestEdge> g;
+ protected Graph<TestVertex, TestEdge> graph;
protected EdgeWeight<TestVertex, TestEdge> weight =
new EdgeWeight<TestVertex, TestEdge>() {
@@ -35,7 +35,7 @@
}
}
- protected Set<TestVertex> vertices() {
+ protected Set<TestVertex> vertexes() {
return of(A, B, C, D, E, F, G, H);
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
new file mode 100644
index 0000000..9bf3acf
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
@@ -0,0 +1,110 @@
+package org.onlab.graph;
+
+import org.junit.Test;
+
+import static com.google.common.collect.ImmutableSet.of;
+import static org.junit.Assert.assertEquals;
+import static org.onlab.graph.TarjanGraphSearch.SCCResult;
+
+/**
+ * Tarjan graph search tests.
+ */
+public class TarjanGraphSearchTest extends GraphTest {
+
+ private void validate(SCCResult<TestVertex, TestEdge> result, int cc) {
+ System.out.println("Cluster count: " + result.clusterVertexes().size());
+ System.out.println("Clusters: " + result.clusterVertexes());
+ assertEquals("incorrect cluster count", cc, result.clusterCount());
+ }
+
+ private void validate(SCCResult<TestVertex, TestEdge> result,
+ int i, int vc, int ec) {
+ assertEquals("incorrect cluster count", vc, result.clusterVertexes().get(i).size());
+ assertEquals("incorrect edge count", ec, result.clusterEdges().get(i).size());
+ }
+
+ @Test
+ public void basic() {
+ graph = new AdjacencyListsGraph<>(vertexes(), edges());
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 6);
+ }
+
+ @Test
+ public void singleCluster() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, E, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, A, 1)));
+
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 1);
+ validate(result, 0, 8, 8);
+ }
+
+ @Test
+ public void twoUnconnectedCluster() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, A, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, E, 1)));
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 2);
+ validate(result, 0, 4, 4);
+ validate(result, 1, 4, 4);
+ }
+
+ @Test
+ public void twoWeaklyConnectedClusters() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, A, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, E, 1),
+ new TestEdge(B, E, 1)));
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, null);
+ validate(result, 2);
+ validate(result, 0, 4, 4);
+ validate(result, 1, 4, 4);
+ }
+
+ @Test
+ public void twoClustersConnectedWithIgnoredEdges() {
+ graph = new AdjacencyListsGraph<>(vertexes(),
+ of(new TestEdge(A, B, 1),
+ new TestEdge(B, C, 1),
+ new TestEdge(C, D, 1),
+ new TestEdge(D, A, 1),
+ new TestEdge(E, F, 1),
+ new TestEdge(F, G, 1),
+ new TestEdge(G, H, 1),
+ new TestEdge(H, E, 1),
+ new TestEdge(B, E, -1),
+ new TestEdge(E, B, -1)));
+
+ TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
+ SCCResult<TestVertex, TestEdge> result = gs.search(graph, weight);
+ validate(result, 2);
+ validate(result, 0, 4, 4);
+ validate(result, 1, 4, 4);
+ }
+
+}