Vector cost proposed to TST on 2016-07-13
First part implemented: weight interface introduced and integrated, default weight implementation added.
Change-Id: Ia46f1b44139069aa171a3c13faf168351bd7cc56
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
index 65bc741..dcf951e 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractEdgeTest.java
@@ -28,9 +28,9 @@
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))
+ .addEqualityGroup(new TestEdge(v1, v2),
+ new TestEdge(v1, v2))
+ .addEqualityGroup(new TestEdge(v2, v1))
.testEquals();
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
index e585449..fa0d522 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
@@ -18,7 +18,6 @@
import org.junit.Test;
import static com.google.common.collect.ImmutableSet.of;
-import static org.junit.Assert.assertEquals;
/**
* Base for all graph search tests.
@@ -35,27 +34,19 @@
@Test(expected = IllegalArgumentException.class)
public void noSuchSourceArgument() {
graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
- of(new TestEdge(B, C, 1))),
- A, H, weight, 1);
+ of(new TestEdge(B, C))),
+ A, H, weigher, 1);
}
@Test(expected = NullPointerException.class)
public void nullGraphArgument() {
- graphSearch().search(null, A, H, weight, 1);
+ graphSearch().search(null, A, H, weigher, 1);
}
@Test(expected = NullPointerException.class)
public void nullSourceArgument() {
graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
- of(new TestEdge(B, C, 1))),
- null, H, weight, 1);
+ of(new TestEdge(B, C))),
+ null, H, weigher, 1);
}
-
- @Test
- public void samenessThreshold() {
- AbstractGraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- search.setSamenessThreshold(0.3);
- assertEquals("incorrect threshold", 0.3, search.samenessThreshold(), 0.01);
- }
-
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
index 9089550..f795027 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AdjacencyListsGraphTest.java
@@ -37,9 +37,11 @@
private static final TestVertex G = new TestVertex("G");
private final Set<TestEdge> edges =
- ImmutableSet.of(new TestEdge(A, B, 1), new TestEdge(B, C, 1),
- new TestEdge(C, D, 1), new TestEdge(D, A, 1),
- new TestEdge(B, D, 1));
+ ImmutableSet.of(new TestEdge(A, B),
+ new TestEdge(B, C),
+ new TestEdge(C, D),
+ new TestEdge(D, A),
+ new TestEdge(B, D));
@Test
public void equality() {
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 cfa313c..0a36d77 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -36,13 +36,13 @@
@Test
@Override
public void defaultGraphTest() {
- executeDefaultTest(7, 5, 5.0);
+ executeDefaultTest(7, 5, new TestDoubleWeight(5.0));
}
@Test
public void defaultHopCountWeight() {
- weight = null;
- executeDefaultTest(10, 3, 3.0);
+ weigher = null;
+ executeDefaultTest(10, 3, new ScalarWeight(3.0));
}
@Test
@@ -51,25 +51,25 @@
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));
+ edges.add(new TestEdge(G, Z, new TestDoubleWeight(1.0)));
+ edges.add(new TestEdge(Z, G, new TestDoubleWeight(-2.0)));
graph = new AdjacencyListsGraph<>(vertexes, edges);
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight, ALL_PATHS).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weigher, ALL_PATHS).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", 5, p.edges().size());
- assertEquals("incorrect path cost", 5.0, p.cost(), 0.1);
+ assertEquals("incorrect path cost", new TestDoubleWeight(5), p.cost());
- paths = search.search(graph, A, G, weight, ALL_PATHS).paths();
+ paths = search.search(graph, A, G, weigher, ALL_PATHS).paths();
assertEquals("incorrect paths count", 0, paths.size());
- paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
+ paths = search.search(graph, A, null, weigher, ALL_PATHS).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 3d02dc1..c19268c 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -34,31 +34,31 @@
@Test
public void defaultGraphTest() {
- executeDefaultTest(7, 3, 8.0);
+ executeDefaultTest(7, 3, new TestDoubleWeight(8.0));
}
@Test
public void defaultHopCountWeight() {
- weight = null;
- executeDefaultTest(7, 3, 3.0);
+ weigher = null;
+ executeDefaultTest(7, 3, new ScalarWeight(3.0));
}
// Executes the default test
- protected void executeDefaultTest(int pathCount, int pathLength, double pathCost) {
+ protected void executeDefaultTest(int pathCount, int pathLength, Weight pathCost) {
graph = new AdjacencyListsGraph<>(vertexes(), edges());
GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
Set<Path<TestVertex, TestEdge>> paths =
- search.search(graph, A, H, weight, ALL_PATHS).paths();
+ search.search(graph, A, H, weigher, ALL_PATHS).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", pathLength, p.edges().size());
- assertEquals("incorrect path cost", pathCost, p.cost(), 0.1);
+ assertEquals("incorrect path cost", pathCost, p.cost());
- paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
+ paths = search.search(graph, A, null, weigher, ALL_PATHS).paths();
printPaths(paths);
assertEquals("incorrect paths count", pathCount, paths.size());
}
@@ -67,16 +67,16 @@
protected void executeSearch(GraphPathSearch<TestVertex, TestEdge> search,
Graph<TestVertex, TestEdge> graph,
TestVertex src, TestVertex dst,
- EdgeWeight<TestVertex, TestEdge> weight,
- int pathCount, double pathCost) {
+ EdgeWeigher<TestVertex, TestEdge> weigher,
+ int pathCount, Weight pathCost) {
GraphPathSearch.Result<TestVertex, TestEdge> result =
- search.search(graph, src, dst, weight, ALL_PATHS);
+ search.search(graph, src, dst, weigher, ALL_PATHS);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
printPaths(paths);
assertEquals("incorrect paths count", pathCount, paths.size());
if (pathCount > 0) {
Path<TestVertex, TestEdge> path = paths.iterator().next();
- assertEquals("incorrect path cost", pathCost, path.cost(), 0.1);
+ assertEquals("incorrect path cost", pathCost, path.cost());
}
}
@@ -84,16 +84,16 @@
protected void executeSinglePathSearch(GraphPathSearch<TestVertex, TestEdge> search,
Graph<TestVertex, TestEdge> graph,
TestVertex src, TestVertex dst,
- EdgeWeight<TestVertex, TestEdge> weight,
- int pathCount, double pathCost) {
+ EdgeWeigher<TestVertex, TestEdge> weigher,
+ int pathCount, Weight pathCost) {
GraphPathSearch.Result<TestVertex, TestEdge> result =
- search.search(graph, src, dst, weight, 1);
+ search.search(graph, src, dst, weigher, 1);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
printPaths(paths);
assertEquals("incorrect paths count", Math.min(pathCount, 1), paths.size());
if (pathCount > 0) {
Path<TestVertex, TestEdge> path = paths.iterator().next();
- assertEquals("incorrect path cost", pathCost, path.cost(), 0.1);
+ assertEquals("incorrect path cost", pathCost, path.cost());
}
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java b/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
index 89b7201..d196fa0 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DefaultMutablePathTest.java
@@ -30,11 +30,13 @@
@Test
public void equality() {
DefaultPath<TestVertex, TestEdge> p1 =
- new DefaultPath<>(of(new TestEdge(A, B, 1),
- new TestEdge(B, C, 1)), 2.0);
+ new DefaultPath<>(of(new TestEdge(A, B),
+ new TestEdge(B, C)),
+ new TestDoubleWeight(2.0));
DefaultPath<TestVertex, TestEdge> p2 =
- new DefaultPath<>(of(new TestEdge(A, B, 1),
- new TestEdge(B, D, 1)), 2.0);
+ new DefaultPath<>(of(new TestEdge(A, B),
+ new TestEdge(B, D)),
+ new TestDoubleWeight(2.0));
new EqualsTester().addEqualityGroup(new DefaultMutablePath<>(p1),
new DefaultMutablePath<>(p1))
.addEqualityGroup(new DefaultMutablePath<>(p2))
@@ -47,61 +49,62 @@
assertNull("src should be null", p.src());
assertNull("dst should be null", p.dst());
assertEquals("incorrect edge count", 0, p.edges().size());
- assertEquals("incorrect path cost", 0.0, p.cost(), 0.1);
+ assertEquals("incorrect path cost", null, p.cost());
}
@Test
public void pathCost() {
MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
- p.setCost(4);
- assertEquals("incorrect path cost", 4.0, p.cost(), 0.1);
+ Weight weight = new TestDoubleWeight(4);
+ p.setCost(weight);
+ assertEquals("incorrect path cost", weight, p.cost());
}
private void validatePath(Path<TestVertex, TestEdge> p,
TestVertex src, TestVertex dst, int length) {
- validatePath(p, src, dst, length, 0.0);
+ validatePath(p, src, dst, length, null);
}
@Test
public void insertEdge() {
MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
- p.insertEdge(new TestEdge(B, C, 1));
- p.insertEdge(new TestEdge(A, B, 1));
+ p.insertEdge(new TestEdge(B, C));
+ p.insertEdge(new TestEdge(A, B));
validatePath(p, A, C, 2);
}
@Test
public void appendEdge() {
MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
- p.appendEdge(new TestEdge(A, B, 1));
- p.appendEdge(new TestEdge(B, C, 1));
+ p.appendEdge(new TestEdge(A, B));
+ p.appendEdge(new TestEdge(B, C));
validatePath(p, A, C, 2);
}
@Test
public void removeEdge() {
MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
- p.appendEdge(new TestEdge(A, B, 1));
- p.appendEdge(new TestEdge(B, C, 1));
- p.appendEdge(new TestEdge(C, C, 2));
- p.appendEdge(new TestEdge(C, D, 1));
+ p.appendEdge(new TestEdge(A, B));
+ p.appendEdge(new TestEdge(B, C));
+ p.appendEdge(new TestEdge(C, C));
+ p.appendEdge(new TestEdge(C, D));
validatePath(p, A, D, 4);
- p.removeEdge(new TestEdge(A, B, 1));
+ p.removeEdge(new TestEdge(A, B));
validatePath(p, B, D, 3);
- p.removeEdge(new TestEdge(C, C, 2));
+ p.removeEdge(new TestEdge(C, C));
validatePath(p, B, D, 2);
- p.removeEdge(new TestEdge(C, D, 1));
+ p.removeEdge(new TestEdge(C, D));
validatePath(p, B, C, 1);
}
@Test
public void toImmutable() {
MutablePath<TestVertex, TestEdge> p = new DefaultMutablePath<>();
- p.appendEdge(new TestEdge(A, B, 1));
- p.appendEdge(new TestEdge(B, C, 1));
+ p.appendEdge(new TestEdge(A, B));
+ p.appendEdge(new TestEdge(B, C));
validatePath(p, A, C, 2);
assertEquals("immutables should equal", p.toImmutable(), p.toImmutable());
diff --git a/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java b/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
index bcfe35c..891a768 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DefaultPathTest.java
@@ -30,28 +30,29 @@
@Test
public void equality() {
- List<TestEdge> edges = of(new TestEdge(A, B, 1), new TestEdge(B, C, 1));
- new EqualsTester().addEqualityGroup(new DefaultPath<>(edges, 2.0),
- new DefaultPath<>(edges, 2.0))
- .addEqualityGroup(new DefaultPath<>(edges, 3.0))
+ List<TestEdge> edges = of(new TestEdge(A, B), new TestEdge(B, C));
+ new EqualsTester().addEqualityGroup(new DefaultPath<>(edges, new TestDoubleWeight(2.0)),
+ new DefaultPath<>(edges, new TestDoubleWeight(2.0)))
+ .addEqualityGroup(new DefaultPath<>(edges, new TestDoubleWeight(3.0)))
.testEquals();
}
@Test
public void basics() {
- Path<TestVertex, TestEdge> p = new DefaultPath<>(of(new TestEdge(A, B, 1),
- new TestEdge(B, C, 1)), 2.0);
- validatePath(p, A, C, 2, 2.0);
+ Path<TestVertex, TestEdge> p = new DefaultPath<>(of(new TestEdge(A, B),
+ new TestEdge(B, C)),
+ new TestDoubleWeight(2.0));
+ validatePath(p, A, C, 2, new TestDoubleWeight(2.0));
}
// Validates the path against expected attributes
protected void validatePath(Path<TestVertex, TestEdge> p,
TestVertex src, TestVertex dst,
- int length, double cost) {
+ int length, Weight cost) {
assertEquals("incorrect path length", length, p.edges().size());
assertEquals("incorrect source", src, p.src());
assertEquals("incorrect destination", dst, p.dst());
- assertEquals("incorrect path cost", cost, p.cost(), 0.1);
+ assertEquals("incorrect path cost", cost, p.cost());
}
}
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 e164f7e..e855b33 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
@@ -36,24 +36,25 @@
@Test
public void defaultGraphTest() {
- executeDefaultTest(3, 6, 5.0, 12.0);
+ executeDefaultTest(3, 6, new TestDoubleWeight(5.0), new TestDoubleWeight(12.0));
executeBroadSearch();
}
@Test
public void defaultHopCountWeight() {
- weight = null;
- executeDefaultTest(3, 6, 3.0, 6.0);
+ weigher = null;
+ executeDefaultTest(3, 6, new ScalarWeight(3.0), new ScalarWeight(6.0));
executeBroadSearch();
}
protected void executeDefaultTest(int minLength, int maxLength,
- double minCost, double maxCost) {
+ Weight minCost, Weight maxCost) {
graph = new AdjacencyListsGraph<>(vertexes(), edges());
DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(graph, A, H, weight, 1);
+ (DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult)
+ search.search(graph, A, H, weigher, 1);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
assertEquals("incorrect path count", 1, paths.size());
@@ -66,7 +67,8 @@
assertTrue("incorrect path length " + l,
minLength <= l && l <= maxLength);
assertTrue("incorrect path cost " + path.cost(),
- minCost <= path.cost() && path.cost() <= maxCost);
+ path.cost().compareTo(minCost) >= 0 &&
+ path.cost().compareTo(maxCost) <= 0);
System.out.println(result.edges());
printPaths(paths);
@@ -78,7 +80,8 @@
// Perform narrow path search to a specific destination.
DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
- search.search(graph, A, null, weight, ALL_PATHS);
+ (DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult)
+ search.search(graph, A, null, weigher, ALL_PATHS);
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 f2a19b8..cfd0a4b 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -37,99 +37,105 @@
@Test
@Override
public void defaultGraphTest() {
- executeDefaultTest(7, 5, 5.0);
+ executeDefaultTest(7, 5, new TestDoubleWeight(5.0));
}
@Test
@Override
public void defaultHopCountWeight() {
- weight = null;
- executeDefaultTest(10, 3, 3.0);
+ weigher = null;
+ executeDefaultTest(10, 3, new ScalarWeight(3.0));
}
@Test
public void noPath() {
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)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(B, A, W1),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, C, W1)));
GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
- Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight, 1).paths();
+ Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weigher, 1).paths();
printPaths(paths);
assertEquals("incorrect paths count", 1, paths.size());
- assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+ assertEquals("incorrect path cost", new TestDoubleWeight(1.0), paths.iterator().next().cost());
- paths = gs.search(graph, A, D, weight, 1).paths();
+ paths = gs.search(graph, A, D, weigher, 1).paths();
printPaths(paths);
assertEquals("incorrect paths count", 0, paths.size());
- paths = gs.search(graph, A, null, weight, 1).paths();
+ paths = gs.search(graph, A, null, weigher, 1).paths();
printPaths(paths);
assertEquals("incorrect paths count", 1, paths.size());
- assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
+ assertEquals("incorrect path cost", new TestDoubleWeight(1.0), paths.iterator().next().cost());
}
@Test
public void simpleMultiplePath() {
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);
- executeSinglePathSearch(graphSearch(), graph, A, D, weight, 1, 2.0);
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, W1),
+ new TestEdge(B, D, W1),
+ new TestEdge(C, D, W1)));
+ executeSearch(graphSearch(), graph, A, D, weigher, 2, W2);
+ executeSinglePathSearch(graphSearch(), graph, A, D, weigher, 1, W2);
}
@Test
public void denseMultiplePath() {
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);
- executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, W1),
+ new TestEdge(B, D, W1),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, E, W1),
+ new TestEdge(D, F, W1),
+ new TestEdge(E, G, W1),
+ new TestEdge(F, G, W1),
+ new TestEdge(A, G, W4)));
+ executeSearch(graphSearch(), graph, A, G, weigher, 5, W4);
+ executeSinglePathSearch(graphSearch(), graph, A, G, weigher, 1, W4);
}
@Test
public void dualEdgeMultiplePath() {
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);
- executeSinglePathSearch(graphSearch(), graph, A, E, weight, 1, 3.0);
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, W3),
+ new TestEdge(B, D, W2),
+ new TestEdge(B, C, W1),
+ new TestEdge(B, E, W4),
+ new TestEdge(C, E, W1),
+ new TestEdge(D, H, W5),
+ new TestEdge(D, E, W1),
+ new TestEdge(E, F, W1),
+ new TestEdge(F, D, W1),
+ new TestEdge(F, G, W1),
+ new TestEdge(F, H, W1),
+ new TestEdge(A, E, W3),
+ new TestEdge(B, D, W1)));
+ executeSearch(graphSearch(), graph, A, E, weigher, 3, W3);
+ executeSinglePathSearch(graphSearch(), graph, A, E, weigher, 1, W3);
}
@Test
public void negativeWeights() {
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(D, A, -2),
- 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(G, A, -5),
- new TestEdge(A, G, 4)));
- executeSearch(graphSearch(), graph, A, G, weight, 3, 4.0);
- executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
+ of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, NW1),
+ new TestEdge(B, D, W1),
+ new TestEdge(D, A, NW2),
+ new TestEdge(C, D, W1),
+ new TestEdge(D, E, W1),
+ new TestEdge(D, F, W1),
+ new TestEdge(E, G, W1),
+ new TestEdge(F, G, W1),
+ new TestEdge(G, A, NW5),
+ new TestEdge(A, G, W4)));
+ executeSearch(graphSearch(), graph, A, G, weigher, 3, new TestDoubleWeight(4.0));
+ executeSinglePathSearch(graphSearch(), graph, A, G, weigher, 1, new TestDoubleWeight(4.0));
}
- @Test
public void disconnectedPerf() {
disconnected();
disconnected();
@@ -143,8 +149,6 @@
disconnected();
}
-
- @Test
public void disconnected() {
Set<TestVertex> vertexes = new HashSet<>();
for (int i = 0; i < 200; i++) {
@@ -155,7 +159,7 @@
long start = System.nanoTime();
for (TestVertex src : vertexes) {
- executeSearch(graphSearch(), graph, src, null, null, 0, 0);
+ executeSearch(graphSearch(), graph, src, null, null, 0, new TestDoubleWeight(0));
}
long end = System.nanoTime();
DecimalFormat fmt = new DecimalFormat("#,###");
diff --git a/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java b/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java
index b5a415f..4d49048 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DisjointPathPairTest.java
@@ -16,6 +16,7 @@
package org.onlab.graph;
import static org.junit.Assert.*;
+import static org.onlab.graph.GraphTest.W1;
import org.junit.Test;
@@ -32,15 +33,15 @@
private static final TestVertex C = new TestVertex("C");
private static final TestVertex D = new TestVertex("D");
- private static final TestEdge AB = new TestEdge(A, B, 1.0);
- private static final TestEdge BC = new TestEdge(B, C, 1.0);
- private static final TestEdge AD = new TestEdge(A, D, 1.0);
- private static final TestEdge DC = new TestEdge(D, C, 1.0);
+ private static final TestEdge AB = new TestEdge(A, B);
+ private static final TestEdge BC = new TestEdge(B, C);
+ private static final TestEdge AD = new TestEdge(A, D);
+ private static final TestEdge DC = new TestEdge(D, C);
- private static final Path<TestVertex, TestEdge> ABC
- = new DefaultPath<>(ImmutableList.of(AB, BC), 1.0);
- private static final Path<TestVertex, TestEdge> ADC
- = new DefaultPath<>(ImmutableList.of(AD, DC), 1.0);
+ private static final Path<TestVertex, TestEdge> ABC =
+ new DefaultPath<>(ImmutableList.of(AB, BC), W1);
+ private static final Path<TestVertex, TestEdge> ADC =
+ new DefaultPath<>(ImmutableList.of(AD, DC), W1);
@Test
public void testSwappingPrimarySecondaryDoesntImpactHashCode() {
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 6acc986..d860928 100644
--- a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -34,14 +34,34 @@
static final TestVertex H = new TestVertex("H");
static final TestVertex Z = new TestVertex("Z");
+ static final TestDoubleWeight ZW = new TestDoubleWeight(0);
+ static final TestDoubleWeight NW5 = new TestDoubleWeight(-5);
+ static final TestDoubleWeight NW2 = new TestDoubleWeight(-2);
+ static final TestDoubleWeight NW1 = new TestDoubleWeight(-1);
+ static final TestDoubleWeight W1 = new TestDoubleWeight(1);
+ static final TestDoubleWeight W2 = new TestDoubleWeight(2);
+ static final TestDoubleWeight W3 = new TestDoubleWeight(3);
+ static final TestDoubleWeight W4 = new TestDoubleWeight(4);
+ static final TestDoubleWeight W5 = new TestDoubleWeight(5);
+
protected Graph<TestVertex, TestEdge> graph;
- protected EdgeWeight<TestVertex, TestEdge> weight =
- new EdgeWeight<TestVertex, TestEdge>() {
+ protected EdgeWeigher<TestVertex, TestEdge> weigher =
+ new EdgeWeigher<TestVertex, TestEdge>() {
@Override
- public double weight(TestEdge edge) {
+ public Weight weight(TestEdge edge) {
return edge.weight();
}
+
+ @Override
+ public Weight getInitialWeight() {
+ return ZW;
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return TestDoubleWeight.NON_VIABLE_WEIGHT;
+ }
};
protected void printPaths(Set<Path<TestVertex, TestEdge>> paths) {
@@ -55,12 +75,18 @@
}
protected Set<TestEdge> edges() {
- return 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));
+ return of(new TestEdge(A, B, W1),
+ new TestEdge(A, C, W3),
+ new TestEdge(B, D, W2),
+ new TestEdge(B, C, W1),
+ new TestEdge(B, E, W4),
+ new TestEdge(C, E, W1),
+ new TestEdge(D, H, W5),
+ new TestEdge(D, E, W1),
+ new TestEdge(E, F, W1),
+ new TestEdge(F, D, W1),
+ new TestEdge(F, G, W1),
+ new TestEdge(F, H, W1));
}
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
index 2b7c8d1..ed92be9 100644
--- a/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/KShortestPathsSearchTest.java
@@ -41,12 +41,12 @@
@Test
public void noPath() {
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)));
+ of(new TestEdge(A, B),
+ new TestEdge(B, A),
+ new TestEdge(C, D),
+ new TestEdge(D, C)));
KShortestPathsSearch<TestVertex, TestEdge> kShortestPathsSearch = new KShortestPathsSearch<>();
- GraphPathSearch.Result<TestVertex, TestEdge> result = kShortestPathsSearch.search(graph, A, D, weight, 1);
+ GraphPathSearch.Result<TestVertex, TestEdge> result = kShortestPathsSearch.search(graph, A, D, weigher, 1);
Set<Path<TestVertex, TestEdge>> resultPathSet = result.paths();
assertTrue("There should not be any paths.", resultPathSet.isEmpty());
}
@@ -55,11 +55,11 @@
public void testSinglePath() {
//Tests that there is only a single path possible between A and B
graph = new AdjacencyListsGraph<>(vertexes(), edges());
- this.result = kShortestPathsSearch.search(graph, A, B, weight, 2);
+ this.result = kShortestPathsSearch.search(graph, A, B, weigher, 2);
Iterator<Path<TestVertex, TestEdge>> itr = result.paths().iterator();
assertEquals("incorrect paths count", 1, result.paths().size());
List<TestEdge> correctEdgeList = Lists.newArrayList();
- correctEdgeList.add(new TestEdge(A, B, 1));
+ correctEdgeList.add(new TestEdge(A, B, W1));
assertTrue("That wrong path was returned.",
edgeListsAreEqual(correctEdgeList, result.paths().iterator().next().edges()));
}
@@ -67,16 +67,16 @@
@Test
public void testTwoPath() {
//Tests that there are only two paths between A and C and that they are returned in the correct order
- result = kShortestPathsSearch.search(graph, A, C, weight, 3);
+ result = kShortestPathsSearch.search(graph, A, C, weigher, 3);
assertTrue("There are an unexpected number of paths.", result.paths().size() == 2);
Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator();
List<TestEdge> correctEdgeList = Lists.newArrayList();
- correctEdgeList.add(new TestEdge(A, B, 1));
- correctEdgeList.add(new TestEdge(B, C, 1));
+ correctEdgeList.add(new TestEdge(A, B, W1));
+ correctEdgeList.add(new TestEdge(B, C, W1));
assertTrue("The first path from A to C was incorrect.",
edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
correctEdgeList.clear();
- correctEdgeList.add(new TestEdge(A, C, 3));
+ correctEdgeList.add(new TestEdge(A, C, W3));
assertTrue("The second path from A to C was incorrect.",
edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
}
@@ -85,23 +85,23 @@
public void testFourPath() {
//Tests that there are only four paths between A and E and that they are returned in the correct order
//Also tests the special case where some correct solutions are equal
- result = kShortestPathsSearch.search(graph, A, E, weight, 5);
+ result = kShortestPathsSearch.search(graph, A, E, weigher, 5);
assertTrue("There are an unexpected number of paths.", result.paths().size() == 4);
Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator();
List<TestEdge> correctEdgeList = Lists.newArrayList();
- correctEdgeList.add(new TestEdge(A, B, 1));
- correctEdgeList.add(new TestEdge(B, C, 1));
- correctEdgeList.add(new TestEdge(C, E, 1));
+ correctEdgeList.add(new TestEdge(A, B, W1));
+ correctEdgeList.add(new TestEdge(B, C, W1));
+ correctEdgeList.add(new TestEdge(C, E, W1));
assertTrue("The first path from A to E was incorrect.",
edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
correctEdgeList.clear();
//There are two paths of equal length that should hold positions two and three
List<TestEdge> alternateCorrectEdgeList = Lists.newArrayList();
- correctEdgeList.add(new TestEdge(A, C, 3));
- correctEdgeList.add(new TestEdge(C, E, 1));
- alternateCorrectEdgeList.add(new TestEdge(A, B, 1));
- alternateCorrectEdgeList.add(new TestEdge(B, D, 2));
- alternateCorrectEdgeList.add(new TestEdge(D, E, 1));
+ correctEdgeList.add(new TestEdge(A, C, W3));
+ correctEdgeList.add(new TestEdge(C, E, W1));
+ alternateCorrectEdgeList.add(new TestEdge(A, B, W1));
+ alternateCorrectEdgeList.add(new TestEdge(B, D, W2));
+ alternateCorrectEdgeList.add(new TestEdge(D, E, W1));
List<TestEdge> candidateOne = edgeListIterator.next().edges();
List<TestEdge> candidateTwo = edgeListIterator.next().edges();
if (candidateOne.size() == 2) {
@@ -116,8 +116,8 @@
edgeListsAreEqual(candidateTwo, correctEdgeList));
}
correctEdgeList.clear();
- correctEdgeList.add(new TestEdge(A, B, 1));
- correctEdgeList.add(new TestEdge(B, E, 4));
+ correctEdgeList.add(new TestEdge(A, B, W1));
+ correctEdgeList.add(new TestEdge(B, E, W4));
assertTrue("The fourth path rom A to E was incorrect",
edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
@@ -128,16 +128,16 @@
//H is a sink in this topology, insure there are no paths from it to any other location
for (TestVertex vertex : vertexes()) {
assertTrue("There should be no paths from vertex H to any other node.",
- kShortestPathsSearch.search(graph, H, vertex, weight, 1).paths().size() == 0);
+ kShortestPathsSearch.search(graph, H, vertex, weigher, 1).paths().size() == 0);
}
}
@Test
public void testLimitPathSetSize() {
//Checks to make sure that no more than K paths are returned
- result = kShortestPathsSearch.search(graph, A, E, weight, 3);
+ result = kShortestPathsSearch.search(graph, A, E, weigher, 3);
assertTrue("There are an unexpected number of paths.", result.paths().size() == 3);
- result = kShortestPathsSearch.search(graph, A, G, weight, 1);
+ result = kShortestPathsSearch.search(graph, A, G, weigher, 1);
assertTrue("There are an unexpected number of paths.", result.paths().size() == 1);
}
@@ -157,47 +157,45 @@
* +---+ +---+ +---+ +---+
*/
graph = new AdjacencyListsGraph<>(of(A, B, C, D, E, F, G, H), of(
- new TestEdge(A, B, 1),
- new TestEdge(B, A, 1),
- new TestEdge(B, C, 1),
- new TestEdge(C, B, 1),
- new TestEdge(C, D, 1),
- new TestEdge(D, C, 1),
- new TestEdge(D, E, 1),
- new TestEdge(E, D, 1),
- new TestEdge(E, H, 1),
- new TestEdge(H, E, 1),
- new TestEdge(H, G, 1),
- new TestEdge(G, H, 1),
- new TestEdge(G, F, 1),
- new TestEdge(F, G, 1),
- new TestEdge(F, B, 1),
- new TestEdge(B, F, 1)
+ new TestEdge(A, B),
+ new TestEdge(B, A),
+ new TestEdge(B, C),
+ new TestEdge(C, B),
+ new TestEdge(C, D),
+ new TestEdge(D, C),
+ new TestEdge(D, E),
+ new TestEdge(E, D),
+ new TestEdge(E, H),
+ new TestEdge(H, E),
+ new TestEdge(H, G),
+ new TestEdge(G, H),
+ new TestEdge(G, F),
+ new TestEdge(F, G),
+ new TestEdge(F, B),
+ new TestEdge(B, F)
));
- weight = edge -> 1.0;
-
//Tests that there are only two paths between A and G and that they are returned in the correct order
- result = kShortestPathsSearch.search(graph, A, G, weight, 5);
+ result = kShortestPathsSearch.search(graph, A, G, weigher, 5);
assertEquals("There are an unexpected number of paths.", 2, result.paths().size());
Iterator<Path<TestVertex, TestEdge>> edgeListIterator = result.paths().iterator();
List<TestEdge> correctEdgeList = Lists.newArrayList();
- correctEdgeList.add(new TestEdge(A, B, 1));
- correctEdgeList.add(new TestEdge(B, F, 1));
- correctEdgeList.add(new TestEdge(F, G, 1));
+ correctEdgeList.add(new TestEdge(A, B));
+ correctEdgeList.add(new TestEdge(B, F));
+ correctEdgeList.add(new TestEdge(F, G));
assertTrue("The first path from A to G was incorrect.",
edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
correctEdgeList.clear();
- correctEdgeList.add(new TestEdge(A, B, 1));
- correctEdgeList.add(new TestEdge(B, C, 1));
- correctEdgeList.add(new TestEdge(C, D, 1));
- correctEdgeList.add(new TestEdge(D, E, 1));
- correctEdgeList.add(new TestEdge(E, H, 1));
- correctEdgeList.add(new TestEdge(H, G, 1));
+ correctEdgeList.add(new TestEdge(A, B));
+ correctEdgeList.add(new TestEdge(B, C));
+ correctEdgeList.add(new TestEdge(C, D));
+ correctEdgeList.add(new TestEdge(D, E));
+ correctEdgeList.add(new TestEdge(E, H));
+ correctEdgeList.add(new TestEdge(H, G));
assertTrue("The second path from A to G was incorrect.",
edgeListsAreEqual(edgeListIterator.next().edges(), correctEdgeList));
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java
index 98b014c..07e4d05 100644
--- a/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/SrlgGraphSearchTest.java
@@ -39,7 +39,7 @@
}
public void setDefaultWeights() {
- weight = null;
+ weigher = null;
}
@Override
@@ -53,10 +53,10 @@
@Test
public void onePathPair() {
setDefaultWeights();
- TestEdge aB = new TestEdge(A, B, 1);
- TestEdge bC = new TestEdge(B, C, 1);
- TestEdge aD = new TestEdge(A, D, 1);
- TestEdge dC = new TestEdge(D, C, 1);
+ TestEdge aB = new TestEdge(A, B);
+ TestEdge bC = new TestEdge(B, C);
+ TestEdge aD = new TestEdge(A, D);
+ TestEdge dC = new TestEdge(D, C);
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
of(aB, bC, aD, dC));
Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -65,7 +65,7 @@
riskProfile.put(aD, 1);
riskProfile.put(dC, 1);
SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile);
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weigher, ALL_PATHS).paths();
System.out.println("\n\n\n" + paths + "\n\n\n");
assertEquals("one disjoint path pair found", 1, paths.size());
checkIsDisjoint(paths.iterator().next(), riskProfile);
@@ -90,12 +90,12 @@
@Test
public void complexGraphTest() {
setDefaultWeights();
- TestEdge aB = new TestEdge(A, B, 1);
- TestEdge bC = new TestEdge(B, C, 1);
- TestEdge aD = new TestEdge(A, D, 1);
- TestEdge dC = new TestEdge(D, C, 1);
- TestEdge cE = new TestEdge(C, E, 1);
- TestEdge bE = new TestEdge(B, E, 1);
+ TestEdge aB = new TestEdge(A, B);
+ TestEdge bC = new TestEdge(B, C);
+ TestEdge aD = new TestEdge(A, D);
+ TestEdge dC = new TestEdge(D, C);
+ TestEdge cE = new TestEdge(C, E);
+ TestEdge bE = new TestEdge(B, E);
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
of(aB, bC, aD, dC, cE, bE));
Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -106,18 +106,18 @@
riskProfile.put(cE, 2);
riskProfile.put(bE, 3);
SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(4, riskProfile);
- search.search(graph, A, E, weight, ALL_PATHS).paths();
+ search.search(graph, A, E, weigher, ALL_PATHS).paths();
}
@Test
public void multiplePathGraphTest() {
setDefaultWeights();
- TestEdge aB = new TestEdge(A, B, 1);
- TestEdge bE = new TestEdge(B, E, 1);
- TestEdge aD = new TestEdge(A, D, 1);
- TestEdge dE = new TestEdge(D, E, 1);
- TestEdge aC = new TestEdge(A, C, 1);
- TestEdge cE = new TestEdge(C, E, 1);
+ TestEdge aB = new TestEdge(A, B);
+ TestEdge bE = new TestEdge(B, E);
+ TestEdge aD = new TestEdge(A, D);
+ TestEdge dE = new TestEdge(D, E);
+ TestEdge aC = new TestEdge(A, C);
+ TestEdge cE = new TestEdge(C, E);
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
of(aB, bE, aD, dE, aC, cE));
Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -128,7 +128,7 @@
riskProfile.put(aC, 4);
riskProfile.put(cE, 5);
SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(6, riskProfile);
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weigher, ALL_PATHS).paths();
assertTrue("> one disjoint path pair found", paths.size() >= 1);
checkIsDisjoint(paths.iterator().next(), riskProfile);
}
@@ -136,10 +136,10 @@
@Test
public void onePath() {
setDefaultWeights();
- TestEdge aB = new TestEdge(A, B, 1);
- TestEdge bC = new TestEdge(B, C, 1);
- TestEdge aD = new TestEdge(A, D, 1);
- TestEdge dC = new TestEdge(D, C, 1);
+ TestEdge aB = new TestEdge(A, B);
+ TestEdge bC = new TestEdge(B, C);
+ TestEdge aD = new TestEdge(A, D);
+ TestEdge dC = new TestEdge(D, C);
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
of(aB, bC, aD, dC));
Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -148,7 +148,7 @@
riskProfile.put(aD, 1);
riskProfile.put(dC, 0);
SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile);
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weigher, ALL_PATHS).paths();
System.out.println(paths);
assertTrue("no disjoint path pairs found", paths.size() == 0);
}
@@ -156,10 +156,10 @@
@Test
public void noPath() {
setDefaultWeights();
- TestEdge aB = new TestEdge(A, B, 1);
- TestEdge bC = new TestEdge(B, C, 1);
- TestEdge aD = new TestEdge(A, D, 1);
- TestEdge dC = new TestEdge(D, C, 1);
+ TestEdge aB = new TestEdge(A, B);
+ TestEdge bC = new TestEdge(B, C);
+ TestEdge aD = new TestEdge(A, D);
+ TestEdge dC = new TestEdge(D, C);
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
of(aB, bC, aD, dC));
Map<TestEdge, Integer> riskProfile = new HashMap<>();
@@ -168,7 +168,7 @@
riskProfile.put(aD, 1);
riskProfile.put(dC, 0);
SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile);
- Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths();
+ Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weigher, ALL_PATHS).paths();
assertTrue("no disjoint path pairs found", paths.size() == 0);
}
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
index a86546a..5d0a032 100644
--- a/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/SuurballeGraphSearchTest.java
@@ -34,17 +34,6 @@
return new SuurballeGraphSearch<>();
}
- public void setWeights() {
- weight = new EdgeWeight<TestVertex, TestEdge>() {
- @Override
- public double weight(TestEdge edge) {
- return edge.weight();
- }
- };
- }
- public void setDefaultWeights() {
- weight = null;
- }
@Override
public void defaultGraphTest() {
@@ -57,41 +46,38 @@
@Test
public void basicGraphTest() {
- setDefaultWeights();
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, C, 1),
- new TestEdge(A, D, 1),
- new TestEdge(D, C, 1)));
- executeSearch(graphSearch(), graph, A, C, weight, 1, 4.0);
+ of(new TestEdge(A, B),
+ new TestEdge(B, C),
+ new TestEdge(A, D),
+ new TestEdge(D, C)));
+ executeSearch(graphSearch(), graph, A, C, null, 1, new ScalarWeight(4.0));
}
@Test
public void multiplePathOnePairGraphTest() {
- setWeights();
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, C, 1),
- new TestEdge(A, D, 1),
- new TestEdge(D, C, 1),
- new TestEdge(B, E, 2),
- new TestEdge(C, E, 1)));
- executeSearch(graphSearch(), graph, A, E, weight, 1, 6.0);
+ of(new TestEdge(A, B, W1),
+ new TestEdge(B, C, W1),
+ new TestEdge(A, D, W1),
+ new TestEdge(D, C, W1),
+ new TestEdge(B, E, W2),
+ new TestEdge(C, E, W1)));
+ executeSearch(graphSearch(), graph, A, E, weigher, 1, new TestDoubleWeight(6.0));
}
@Test
public void multiplePathsMultiplePairs() {
- setWeights();
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, E, 1),
- new TestEdge(A, C, 1),
- new TestEdge(C, E, 1),
- new TestEdge(A, D, 1),
- new TestEdge(D, E, 1),
- new TestEdge(A, E, 2)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(B, E, W1),
+ new TestEdge(A, C, W1),
+ new TestEdge(C, E, W1),
+ new TestEdge(A, D, W1),
+ new TestEdge(D, E, W1),
+ new TestEdge(A, E, W2)));
GraphPathSearch.Result<TestVertex, TestEdge> result =
- graphSearch().search(graph, A, E, weight, GraphPathSearch.ALL_PATHS);
+ graphSearch().search(graph, A, E, weigher, GraphPathSearch.ALL_PATHS);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
System.out.println("\n\n" + paths + "\n\n\ndone\n");
assertEquals("incorrect paths count", 3, paths.size());
@@ -101,27 +87,25 @@
@Test
public void differingPrimaryAndBackupPathLengths() {
- setWeights();
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, C, 1),
- new TestEdge(A, D, 1),
- new TestEdge(D, C, 1),
- new TestEdge(B, E, 1),
- new TestEdge(C, E, 1)));
- executeSearch(graphSearch(), graph, A, E, weight, 1, 5.0);
+ of(new TestEdge(A, B),
+ new TestEdge(B, C),
+ new TestEdge(A, D),
+ new TestEdge(D, C),
+ new TestEdge(B, E),
+ new TestEdge(C, E)));
+ executeSearch(graphSearch(), graph, A, E, weigher, 1, new TestDoubleWeight(5.0));
}
@Test
public void onePath() {
- setWeights();
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, C, 1),
- new TestEdge(A, C, 4),
- new TestEdge(C, D, 1)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(B, C, W1),
+ new TestEdge(A, C, W4),
+ new TestEdge(C, D, W1)));
GraphPathSearch.Result<TestVertex, TestEdge> result =
- graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+ graphSearch().search(graph, A, D, weigher, GraphPathSearch.ALL_PATHS);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
assertEquals("incorrect paths count", 1, paths.size());
DisjointPathPair<TestVertex, TestEdge> dpp = (DisjointPathPair<TestVertex, TestEdge>) paths.iterator().next();
@@ -130,24 +114,22 @@
@Test
public void noPath() {
- setWeights();
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
- of(new TestEdge(A, B, 1),
- new TestEdge(B, C, 1),
- new TestEdge(A, C, 4)));
+ of(new TestEdge(A, B, W1),
+ new TestEdge(B, C, W1),
+ new TestEdge(A, C, W4)));
GraphPathSearch.Result<TestVertex, TestEdge> result =
- graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+ graphSearch().search(graph, A, D, weigher, GraphPathSearch.ALL_PATHS);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
assertEquals("incorrect paths count", paths.size(), 0);
}
@Test
public void disconnected() {
- setWeights();
Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D),
of());
GraphPathSearch.Result<TestVertex, TestEdge> result =
- graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS);
+ graphSearch().search(graph, A, D, weigher, GraphPathSearch.ALL_PATHS);
Set<Path<TestVertex, TestEdge>> paths = result.paths();
assertEquals("incorrect paths count", 0, paths.size());
}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
index 2b6dec0..a3f47f5 100644
--- a/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/TarjanGraphSearchTest.java
@@ -49,14 +49,14 @@
@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)));
+ of(new TestEdge(A, B),
+ new TestEdge(B, C),
+ new TestEdge(C, D),
+ new TestEdge(D, E),
+ new TestEdge(E, F),
+ new TestEdge(F, G),
+ new TestEdge(G, H),
+ new TestEdge(H, A)));
TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
@@ -67,14 +67,14 @@
@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)));
+ of(new TestEdge(A, B),
+ new TestEdge(B, C),
+ new TestEdge(C, D),
+ new TestEdge(D, A),
+ new TestEdge(E, F),
+ new TestEdge(F, G),
+ new TestEdge(G, H),
+ new TestEdge(H, E)));
TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
validate(result, 2);
@@ -85,15 +85,15 @@
@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)));
+ of(new TestEdge(A, B),
+ new TestEdge(B, C),
+ new TestEdge(C, D),
+ new TestEdge(D, A),
+ new TestEdge(E, F),
+ new TestEdge(F, G),
+ new TestEdge(G, H),
+ new TestEdge(H, E),
+ new TestEdge(B, E)));
TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
SccResult<TestVertex, TestEdge> result = gs.search(graph, null);
validate(result, 2);
@@ -104,19 +104,21 @@
@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)));
+ of(new TestEdge(A, B),
+ new TestEdge(B, C),
+ new TestEdge(C, D),
+ new TestEdge(D, A),
+ new TestEdge(E, F),
+ new TestEdge(F, G),
+ new TestEdge(G, H),
+ new TestEdge(H, E),
+ new TestEdge(B, E,
+ weigher.getNonViableWeight()),
+ new TestEdge(E, B,
+ weigher.getNonViableWeight())));
TarjanGraphSearch<TestVertex, TestEdge> gs = new TarjanGraphSearch<>();
- SccResult<TestVertex, TestEdge> result = gs.search(graph, weight);
+ SccResult<TestVertex, TestEdge> result = gs.search(graph, weigher);
validate(result, 2);
validate(result, 0, 4, 4);
validate(result, 1, 4, 4);
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java b/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java
new file mode 100644
index 0000000..54f9f17
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/TestDoubleWeight.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onlab.graph;
+
+import com.google.common.math.DoubleMath;
+
+import java.util.Objects;
+
+/**
+ * Test weight (based on double).
+ */
+public class TestDoubleWeight implements Weight {
+
+ /**
+ * Instance of negative test weight.
+ */
+ public static final TestDoubleWeight NEGATIVE_WEIGHT = new TestDoubleWeight(-1);
+
+ /**
+ * Instance of test weight to mark links/paths which
+ * can not be traversed.
+ */
+ public static final TestDoubleWeight NON_VIABLE_WEIGHT =
+ new TestDoubleWeight(Double.POSITIVE_INFINITY);
+
+ private final double value;
+
+ /**
+ * Creates a new test weight with the given double value.
+ * @param value double weight
+ */
+ public TestDoubleWeight(double value) {
+ this.value = value;
+ }
+
+ @Override
+ public Weight merge(Weight otherWeight) {
+ return new TestDoubleWeight(value + ((TestDoubleWeight) otherWeight).value);
+ }
+
+ @Override
+ public Weight subtract(Weight otherWeight) {
+ return new TestDoubleWeight(value - ((TestDoubleWeight) otherWeight).value);
+ }
+
+ @Override
+ public boolean isViable() {
+ return this != NON_VIABLE_WEIGHT;
+ }
+
+ @Override
+ public int compareTo(Weight otherWeight) {
+ return Double.compare(value, ((TestDoubleWeight) otherWeight).value);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ return (DoubleMath.fuzzyEquals(value, ((TestDoubleWeight) obj).value, 0.1));
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(value);
+ }
+
+ @Override
+ public boolean isNegative() {
+ return value < 0;
+ }
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
index 7b48767..874b5eb 100644
--- a/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
+++ b/utils/misc/src/test/java/org/onlab/graph/TestEdge.java
@@ -18,32 +18,45 @@
import java.util.Objects;
import static com.google.common.base.MoreObjects.toStringHelper;
+import static org.onlab.graph.GraphTest.W1;
/**
* Test edge.
*/
public class TestEdge extends AbstractEdge<TestVertex> {
- private final double weight;
+ private final Weight weight;
/**
- * Creates a new edge between the specified source and destination vertexes.
+ * Creates a new edge between the specified source and destination vertexes
+ * with the given weight.
*
* @param src source vertex
* @param dst destination vertex
* @param weight edge weight
*/
- public TestEdge(TestVertex src, TestVertex dst, double weight) {
+ public TestEdge(TestVertex src, TestVertex dst, Weight weight) {
super(src, dst);
this.weight = weight;
}
/**
+ * Creates a new edge between the specified source and destination vertexes
+ * with the default weight.
+ *
+ * @param src source vertex
+ * @param dst destination vertext
+ */
+ public TestEdge(TestVertex src, TestVertex dst) {
+ this(src, dst, W1);
+ }
+
+ /**
* Returns the edge weight.
*
* @return edge weight
*/
- public double weight() {
+ public Weight weight() {
return weight;
}