Added Tarjan SCC computation algorithm and associated tests.
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);
+ }
+
+}