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/main/java/org/onlab/graph/AbstractGraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index 01f17efa..95f99dc 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -33,27 +33,6 @@
public abstract class AbstractGraphPathSearch<V extends Vertex, E extends Edge<V>>
implements GraphPathSearch<V, E> {
- private double samenessThreshold = Double.MIN_VALUE;
-
- /**
- * Sets a new sameness threshold for comparing cost values; default is
- * is {@link Double#MIN_VALUE}.
- *
- * @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.
@@ -63,7 +42,7 @@
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, Weight> costs = new HashMap<>();
protected final Map<V, Set<E>> parents = new HashMap<>();
protected final int maxPaths;
@@ -108,7 +87,7 @@
}
@Override
- public Map<V, Double> costs() {
+ public Map<V, Weight> costs() {
return costs;
}
@@ -124,18 +103,20 @@
* @return true if the vertex has cost already
*/
boolean hasCost(V v) {
- return costs.get(v) != null;
+ return costs.containsKey(v);
}
/**
* Returns the current cost to reach the specified vertex.
+ * If the vertex has not been accessed yet, it has no cost
+ * associated and null will be returned.
*
* @param v vertex to reach
- * @return cost to reach the vertex
+ * @return weight cost to reach the vertex if already accessed;
+ * null otherwise
*/
- double cost(V v) {
- Double c = costs.get(v);
- return c == null ? Double.MAX_VALUE : c;
+ Weight cost(V v) {
+ return costs.get(v);
}
/**
@@ -151,7 +132,7 @@
* added to the previously accrued edges as they yield
* the same cost
*/
- void updateVertex(V vertex, E edge, double cost, boolean replace) {
+ void updateVertex(V vertex, E edge, Weight cost, boolean replace) {
costs.put(vertex, cost);
if (edge != null) {
Set<E> edges = parents.get(vertex);
@@ -187,22 +168,27 @@
* @param forbidNegatives if true negative values will forbid the link
* @return true if the edge was relaxed; false otherwise
*/
- boolean relaxEdge(E edge, double cost, EdgeWeight<V, E> ew,
+ boolean relaxEdge(E edge, Weight cost, EdgeWeigher<V, E> ew,
boolean... forbidNegatives) {
V v = edge.dst();
- double oldCost = cost(v);
- double hopCost = ew == null ? 1.0 : ew.weight(edge);
- if (hopCost < 0 && forbidNegatives.length == 1 && forbidNegatives[0]) {
+
+ Weight hopCost = ew.weight(edge);
+ if ((!hopCost.isViable()) ||
+ (hopCost.isNegative() && forbidNegatives.length == 1 && forbidNegatives[0])) {
return false;
}
+ Weight newCost = cost.merge(hopCost);
- double newCost = cost + hopCost;
- boolean relaxed = newCost < oldCost;
- boolean same = Math.abs(newCost - oldCost) <= samenessThreshold;
- if (same || relaxed) {
- updateVertex(v, edge, newCost, !same);
+ int compareResult = -1;
+ if (hasCost(v)) {
+ Weight oldCost = cost(v);
+ compareResult = newCost.compareTo(oldCost);
}
- return relaxed;
+
+ if (compareResult <= 0) {
+ updateVertex(v, edge, newCost, compareResult < 0);
+ }
+ return compareResult < 0;
}
/**
@@ -328,4 +314,16 @@
"Destination not in graph");
}
+ @Override
+ public Result<V, E> search(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
+ checkArguments(graph, src, dst);
+
+ return internalSearch(graph, src, dst,
+ weigher != null ? weigher : new DefaultEdgeWeigher<>(),
+ maxPaths);
+ }
+
+ protected abstract Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths);
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
index 88aca6b..9bd6c63 100644
--- a/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
@@ -23,22 +23,21 @@
extends AbstractGraphPathSearch<V, E> {
@Override
- public Result<V, E> search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths) {
- checkArguments(graph, src, dst);
+ protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
// Prepare the graph search result.
DefaultResult result = new DefaultResult(src, dst, maxPaths);
// The source vertex has cost 0, of course.
- result.updateVertex(src, null, 0.0, true);
+ result.updateVertex(src, null, weigher.getInitialWeight(), true);
int max = graph.getVertexes().size() - 1;
for (int i = 0; i < max; i++) {
// Relax, if possible, all egress edges of the current vertex.
for (E edge : graph.getEdges()) {
if (result.hasCost(edge.src())) {
- result.relaxEdge(edge, result.cost(edge.src()), weight);
+ result.relaxEdge(edge, result.cost(edge.src()), weigher);
}
}
}
@@ -46,7 +45,7 @@
// Remove any vertexes reached by traversing edges with negative weights.
for (E edge : graph.getEdges()) {
if (result.hasCost(edge.src())) {
- if (result.relaxEdge(edge, result.cost(edge.src()), weight)) {
+ if (result.relaxEdge(edge, result.cost(edge.src()), weigher)) {
result.removeVertex(edge.dst());
}
}
@@ -56,5 +55,4 @@
result.buildPaths();
return result;
}
-
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
index 48bfe03..c5b0f4f 100644
--- a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
@@ -25,16 +25,15 @@
extends AbstractGraphPathSearch<V, E> {
@Override
- public Result<V, E> search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths) {
- checkArguments(graph, src, dst);
+ protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
// Prepare the graph result.
DefaultResult result = new DefaultResult(src, dst, maxPaths);
// Setup the starting frontier with the source as the sole vertex.
Set<V> frontier = new HashSet<>();
- result.updateVertex(src, null, 0.0, true);
+ result.updateVertex(src, null, weigher.getInitialWeight(), true);
frontier.add(src);
boolean reachedEnd = false;
@@ -44,14 +43,14 @@
// Visit all vertexes in the current frontier.
for (V vertex : frontier) {
- double cost = result.cost(vertex);
+ Weight 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.
- double newCost = cost + (weight == null ? 1.0 : weight.weight(edge));
+ Weight newCost = cost.merge(weigher.weight(edge));
result.updateVertex(nextVertex, edge, newCost, true);
// If we have reached our intended destination, bail.
if (nextVertex.equals(dst)) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultEdgeWeigher.java b/utils/misc/src/main/java/org/onlab/graph/DefaultEdgeWeigher.java
new file mode 100644
index 0000000..e280391
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultEdgeWeigher.java
@@ -0,0 +1,53 @@
+/*
+ * 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;
+
+/**
+ * Default weigher returns identical weight for every graph edge. Basically it
+ * is a hop count weigher.
+ * Produces weights of {@link ScalarWeight} type.
+ *
+ * @param <V> vertex type
+ * @param <E> edge type
+ */
+public class DefaultEdgeWeigher<V extends Vertex, E extends Edge<V>>
+ implements EdgeWeigher<V, E> {
+
+ /**
+ * Common weight value for any link.
+ */
+ protected static final double HOP_WEIGHT_VALUE = 1;
+ /**
+ * Weight value for null path (without links).
+ */
+ protected static final double NULL_WEIGHT_VALUE = 0;
+
+ @Override
+ public Weight weight(E edge) {
+ return new ScalarWeight(HOP_WEIGHT_VALUE);
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return new ScalarWeight(NULL_WEIGHT_VALUE);
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return ScalarWeight.NON_VIABLE_WEIGHT;
+ }
+}
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 b6c5e38..c8f8f86 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
@@ -31,7 +31,7 @@
public class DefaultMutablePath<V extends Vertex, E extends Edge<V>> implements MutablePath<V, E> {
private final List<E> edges = new ArrayList<>();
- private double cost = 0.0;
+ private Weight cost;
/**
* Creates a new empty path.
@@ -61,7 +61,7 @@
}
@Override
- public double cost() {
+ public Weight cost() {
return cost;
}
@@ -71,7 +71,7 @@
}
@Override
- public void setCost(double cost) {
+ public void setCost(Weight cost) {
this.cost = cost;
}
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 c1aa802..4a29adf 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
@@ -33,15 +33,15 @@
private final V src;
private final V dst;
private final List<E> edges;
- private double cost = 0.0;
+ private Weight cost;
/**
* 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
+ * @param cost path cost as a weight object
*/
- public DefaultPath(List<E> edges, double cost) {
+ public DefaultPath(List<E> edges, Weight cost) {
checkNotNull(edges, "Edges list must not be null");
checkArgument(!edges.isEmpty(), "There must be at least one edge");
this.edges = ImmutableList.copyOf(edges);
@@ -61,7 +61,7 @@
}
@Override
- public double cost() {
+ public Weight cost() {
return cost;
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
index 218ce39..a5b33b3 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java
@@ -35,15 +35,14 @@
}
@Override
- public SpanningTreeResult search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths) {
- checkArguments(graph, src, dst);
+ protected SpanningTreeResult internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
// Prepare the search result.
SpanningTreeResult result = new SpanningTreeResult(src, dst, maxPaths);
// The source vertex has cost 0, of course.
- result.updateVertex(src, null, 0.0, true);
+ result.updateVertex(src, null, weigher.getInitialWeight(), true);
// Track finished vertexes and keep a stack of vertexes that have been
// started; start this stack with the source on it.
@@ -58,7 +57,7 @@
break;
}
- double cost = result.cost(vertex);
+ Weight cost = result.cost(vertex);
boolean tangent = false;
// Visit all egress edges of the current vertex.
@@ -74,7 +73,7 @@
// If this vertex have not finished this vertex yet,
// not started it, then start it as a tree-edge.
result.markEdge(edge, EdgeType.TREE_EDGE);
- double newCost = cost + (weight == null ? 1.0 : weight.weight(edge));
+ Weight newCost = cost.merge(weigher.weight(edge));
result.updateVertex(nextVertex, edge, newCost, true);
stack.push(nextVertex);
tangent = true;
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 4990718..0dd1898 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -27,16 +27,15 @@
extends AbstractGraphPathSearch<V, E> {
@Override
- public Result<V, E> search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths) {
- checkArguments(graph, src, dst);
+ protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
// Use the default result to remember cumulative costs and parent
// edges to each each respective vertex.
DefaultResult result = new DefaultResult(src, dst, maxPaths);
// Cost to reach the source vertex is 0 of course.
- result.updateVertex(src, null, 0.0, false);
+ result.updateVertex(src, null, weigher.getInitialWeight(), false);
if (graph.getEdges().isEmpty()) {
result.buildPaths();
@@ -56,11 +55,12 @@
}
// Find its cost and use it to determine if the vertex is reachable.
- double cost = result.cost(nearest);
- if (cost < Double.MAX_VALUE) {
+ if (result.hasCost(nearest)) {
+ Weight cost = result.cost(nearest);
+
// If the vertex is reachable, relax all its egress edges.
for (E e : graph.getEdgesFrom(nearest)) {
- result.relaxEdge(e, cost, weight, true);
+ result.relaxEdge(e, cost, weigher, true);
}
}
@@ -84,8 +84,16 @@
@Override
public int compare(V v1, V v2) {
- double delta = result.cost(v2) - result.cost(v1);
- return delta < 0 ? -1 : (delta > 0 ? 1 : 0);
+ //not accessed vertices should be pushed to the back of the queue
+ if (!result.hasCost(v1) && !result.hasCost(v2)) {
+ return 0;
+ } else if (!result.hasCost(v1)) {
+ return -1;
+ } else if (!result.hasCost(v2)) {
+ return 1;
+ }
+
+ return result.cost(v2).compareTo(result.cost(v1));
}
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
index 1e8d3d6..6436ad4 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java
@@ -73,8 +73,8 @@
}
@Override
- public double cost() {
- return hasBackup() ? primary.cost() + secondary.cost() : primary.cost();
+ public Weight cost() {
+ return hasBackup() ? primary.cost().merge(secondary.cost()) : primary.cost();
}
@Override
diff --git a/utils/misc/src/main/java/org/onlab/graph/EdgeWeigher.java b/utils/misc/src/main/java/org/onlab/graph/EdgeWeigher.java
new file mode 100644
index 0000000..f52c4dd
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/EdgeWeigher.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2014-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;
+
+/**
+ * Abstraction of a graph edge weight function.
+ */
+public interface EdgeWeigher<V extends Vertex, E extends Edge<V>> {
+
+ /**
+ * Returns the weight of the given edge.
+ *
+ * @param edge edge to be weighed
+ * @return edge weight
+ */
+ Weight weight(E edge);
+
+ /**
+ * Returns initial weight value (i.e. weight of a "path" starting and
+ * terminating in the same vertex; typically 0 value is used).
+ *
+ * @return null path weight
+ */
+ Weight getInitialWeight();
+
+ /**
+ * Returns weight of a link/path that should be skipped
+ * (can be considered as an infinite weight).
+ *
+ * @return non viable weight
+ */
+ Weight getNonViableWeight();
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java b/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java
deleted file mode 100644
index 5b1c806..0000000
--- a/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * Copyright 2014-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;
-
-/**
- * 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/GAOrganism.java b/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
index 4deed2fa..1384c9a 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java
@@ -28,7 +28,7 @@
*
* @return fitness of organism
*/
- double fitness();
+ Comparable fitness();
/**
* A method that slightly mutates an organism.
diff --git a/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java b/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
index 5f9dfcc..4017485 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java
@@ -33,15 +33,8 @@
* 25% (as well as some "random" newcomers).
*/
void step() {
- Collections.sort(this, (org1, org2) -> {
- double d = org1.fitness() - org2.fitness();
- if (d < 0) {
- return -1;
- } else if (d == 0) {
- return 0;
- }
- return 1;
- });
+ Collections.sort(this, (org1, org2) ->
+ org1.fitness().compareTo(org2.fitness()));
int maxSize = size();
for (int i = size() - 1; i > maxSize / 4; i--) {
remove(i);
diff --git a/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
index d5513a7..1c1099d 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java
@@ -66,7 +66,7 @@
*
* @return map of vertex to path cost bindings
*/
- Map<V, Double> costs();
+ Map<V, Weight> costs();
}
/**
@@ -76,12 +76,12 @@
* @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
+ * @param weigher optional edge-weigher; if null, {@link DefaultEdgeWeigher}
+ * will be used (assigns equal weights to all links)
* @param maxPaths limit on number of paths; {@link GraphPathSearch#ALL_PATHS} if no limit
* @return search results
*/
Result<V, E> search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths);
+ EdgeWeigher<V, E> weigher, int maxPaths);
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
index 4ef6e6d..6f0d606 100644
--- a/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java
@@ -32,12 +32,12 @@
/**
* 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
+ * @param graph graph to be searched
+ * @param weigher optional edge-weigher; if null, {@link DefaultEdgeWeigher}
+ * will be used (assigns equal weights to all links)
*
* @return search results
*/
- Result search(Graph<V, E> graph, EdgeWeight<V, E> weight);
+ Result search(Graph<V, E> graph, EdgeWeigher<V, E> weigher);
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java b/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
index c07b00a..00bda43 100644
--- a/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/KShortestPathsSearch.java
@@ -40,11 +40,9 @@
private final Logger log = getLogger(getClass());
@Override
- public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) {
- checkNotNull(src);
- checkNotNull(dst);
- //The modified edge weight removes any need to modify the original graph
- InnerEdgeWeighter modifiedWeighter = new InnerEdgeWeighter(checkNotNull(weight));
+ protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst, EdgeWeigher<V, E> weigher, int maxPaths) {
+ //The modified edge weigher removes any need to modify the original graph
+ InnerEdgeWeigher modifiedWeighter = new InnerEdgeWeigher(checkNotNull(weigher));
checkArgument(maxPaths != ALL_PATHS, "KShortestPath search cannot" +
"be used with ALL_PATHS.");
checkArgument(maxPaths > 0, "The max number of paths must be greater" +
@@ -87,11 +85,11 @@
if (!dijkstraResults.isEmpty()) {
Path<V, E> spurPath = dijkstraResults.iterator().next();
List<E> totalPath = new ArrayList<>(rootPathEdgeList);
- spurPath.edges().forEach(e -> totalPath.add(e));
- //The following line must use the original weighter not the modified weighter because the modified
- //weighter will count -1 values used for modifying the graph and return an inaccurate cost.
+ spurPath.edges().forEach(totalPath::add);
+ //The following line must use the original weigher not the modified weigher because the modified
+ //weigher will count -1 values used for modifying the graph and return an inaccurate cost.
potentialPaths.add(new DefaultPath<V, E>(totalPath,
- calculatePathCost(weight, totalPath)));
+ calculatePathCost(weigher, totalPath)));
}
//Restore all removed paths and nodes
@@ -125,10 +123,10 @@
return true;
}
- private Double calculatePathCost(EdgeWeight<V, E> weighter, List<E> edges) {
- Double totalCost = 0.0;
+ private Weight calculatePathCost(EdgeWeigher<V, E> weighter, List<E> edges) {
+ Weight totalCost = weighter.getInitialWeight();
for (E edge : edges) {
- totalCost += weighter.weight(edge);
+ totalCost = totalCost.merge(weighter.weight(edge));
}
return totalCost;
}
@@ -136,23 +134,31 @@
/**
* Weights edges to make them inaccessible if set, otherwise returns the result of the original EdgeWeight.
*/
- private class InnerEdgeWeighter implements EdgeWeight<V, E> {
+ private final class InnerEdgeWeigher implements EdgeWeigher<V, E> {
private Set<E> removedEdges = Sets.newConcurrentHashSet();
- private EdgeWeight<V, E> innerEdgeWeight;
+ private EdgeWeigher<V, E> innerEdgeWeigher;
- public InnerEdgeWeighter(EdgeWeight<V, E> weight) {
- this.innerEdgeWeight = weight;
+ private InnerEdgeWeigher(EdgeWeigher<V, E> weigher) {
+ this.innerEdgeWeigher = weigher;
}
@Override
- public double weight(E edge) {
+ public Weight weight(E edge) {
if (removedEdges.contains(edge)) {
- //THIS RELIES ON THE LOCAL DIJKSTRA ALGORITHM AVOIDING NEGATIVES
- return -1;
- } else {
- return innerEdgeWeight.weight(edge);
+ return innerEdgeWeigher.getNonViableWeight();
}
+ return innerEdgeWeigher.weight(edge);
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return innerEdgeWeigher.getInitialWeight();
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return innerEdgeWeigher.getNonViableWeight();
}
}
@@ -184,7 +190,7 @@
@Override
public int compare(Path<V, E> pathOne, Path<V, E> pathTwo) {
- int comparisonValue = Double.compare(pathOne.cost(), pathTwo.cost());
+ int comparisonValue = pathOne.cost().compareTo(pathTwo.cost());
if (comparisonValue != 0) {
return comparisonValue;
} else if (edgeListsAreEqual(pathOne.edges(), pathTwo.edges())) {
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 22412b1..3a3b479 100644
--- a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
@@ -46,11 +46,11 @@
void removeEdge(E edge);
/**
- * Sets the total path cost as a unit-less double.
+ * Sets the total path cost as a weight object.
*
* @param cost new path cost
*/
- void setCost(double cost);
+ void setCost(Weight cost);
/**
* Returns an immutable copy of this path.
diff --git a/utils/misc/src/main/java/org/onlab/graph/Path.java b/utils/misc/src/main/java/org/onlab/graph/Path.java
index 0f74aae..85ac420 100644
--- a/utils/misc/src/main/java/org/onlab/graph/Path.java
+++ b/utils/misc/src/main/java/org/onlab/graph/Path.java
@@ -36,10 +36,10 @@
List<E> edges();
/**
- * Returns the total cost of the path as a unit-less number.
+ * Returns the total cost of the path as a weight object.
*
- * @return path cost as a unit-less number
+ * @return path cost as a weight object
*/
- double cost();
+ Weight cost();
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/ScalarWeight.java b/utils/misc/src/main/java/org/onlab/graph/ScalarWeight.java
new file mode 100644
index 0000000..ccf0c2a
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/ScalarWeight.java
@@ -0,0 +1,122 @@
+/*
+ * 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 static com.google.common.base.MoreObjects.toStringHelper;
+
+import com.google.common.math.DoubleMath;
+
+import java.util.Objects;
+
+/**
+ * Weight implementation based on a double value.
+ */
+public class ScalarWeight implements Weight {
+
+ /**
+ * Instance of scalar weight to mark links/paths which
+ * can not be traversed.
+ */
+ public static final ScalarWeight NON_VIABLE_WEIGHT =
+ new ScalarWeight(Double.POSITIVE_INFINITY);
+
+ private static double samenessThreshold = Double.MIN_VALUE;
+
+ private double value;
+
+ /**
+ * Creates a new scalar weight with the given double value.
+ * @param value double value
+ */
+ public ScalarWeight(double value) {
+ this.value = value;
+ }
+
+ @Override
+ public Weight merge(Weight otherWeight) {
+ return new ScalarWeight(value + ((ScalarWeight) otherWeight).value);
+ }
+
+ @Override
+ public Weight subtract(Weight otherWeight) {
+ return new ScalarWeight(value - ((ScalarWeight) otherWeight).value);
+ }
+
+ @Override
+ public boolean isViable() {
+ return this != NON_VIABLE_WEIGHT;
+ }
+
+ @Override
+ public int compareTo(Weight otherWeight) {
+ //check equality with samenessThreshold
+ if (equals(otherWeight)) {
+ return 0;
+ }
+ return Double.compare(value, ((ScalarWeight) otherWeight).value);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ return ((obj instanceof ScalarWeight) &&
+ (DoubleMath.fuzzyEquals(value, ((ScalarWeight) obj).value,
+ samenessThreshold)));
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(value);
+ }
+
+ @Override
+ public boolean isNegative() {
+ return value < 0;
+ }
+
+ @Override
+ public String toString() {
+ return toStringHelper(this).add("value", value).toString();
+ }
+
+ /**
+ * Returns inner double value.
+ *
+ * @return double value
+ */
+ public double value() {
+ return value;
+ }
+
+ /**
+ * Sets a new sameness threshold for comparing cost values; default is
+ * is {@link Double#MIN_VALUE}.
+ *
+ * @param threshold fractional double value
+ */
+ public static void setSamenessThreshold(double threshold) {
+ samenessThreshold = threshold;
+ }
+
+ /**
+ * Returns the current sameness threshold for comparing cost values.
+ *
+ * @return current threshold
+ */
+ public static double samenessThreshold() {
+ return samenessThreshold;
+ }
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
index 5ac35a0..82107ca 100644
--- a/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java
@@ -46,7 +46,7 @@
Graph<V, E> orig;
V src, dst;
- EdgeWeight<V, E> weight;
+ EdgeWeigher<V, E> weigher;
/**
* Creates an SRLG graph search object with the given number
@@ -86,22 +86,18 @@
}
@Override
- public Result<V, E> search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths) {
+ protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
if (maxPaths == ALL_PATHS) {
maxPaths = POPSIZE;
}
if (useSuurballe) {
- return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS);
+ return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weigher, ALL_PATHS);
}
- if (weight == null) {
- weight = edge -> 1;
- }
- checkArguments(graph, src, dst);
orig = graph;
this.src = src;
this.dst = dst;
- this.weight = weight;
+ this.weigher = weigher;
List<Subset> best = new GAPopulation<Subset>()
.runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups]));
Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>();
@@ -109,7 +105,7 @@
dpps.addAll(s.buildPaths());
}
Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>()
- .search(orig, src, dst, weight, 1);
+ .search(orig, src, dst, weigher, 1);
return new Result<V, E>() {
final DefaultResult search = (DefaultResult) firstDijkstra;
@@ -127,7 +123,7 @@
}
return pathsD;
}
- public Map<V, Double> costs() {
+ public Map<V, Weight> costs() {
return search.costs();
}
@@ -141,15 +137,25 @@
//finds the shortest path in the graph given a subset of edge types to use
private Result<V, E> findShortestPathFromSubset(boolean[] subset) {
Graph<V, E> graph = orig;
- EdgeWeight<V, E> modified = new EdgeWeight<V, E>() {
+ EdgeWeigher<V, E> modified = new EdgeWeigher<V, E>() {
final boolean[] subsetF = subset;
@Override
- public double weight(E edge) {
+ public Weight weight(E edge) {
if (subsetF[riskGrouping.get(edge)]) {
- return weight.weight(edge);
+ return weigher.weight(edge);
}
- return INF;
+ return weigher.getNonViableWeight();
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return weigher.getInitialWeight();
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return weigher.getNonViableWeight();
}
};
@@ -181,13 +187,13 @@
}
@Override
- public double fitness() {
+ public Comparable fitness() {
Set<Path<V, E>> paths1 = findShortestPathFromSubset(subset).paths();
Set<Path<V, E>> paths2 = findShortestPathFromSubset(not).paths();
if (paths1.isEmpty() || paths2.isEmpty()) {
- return INF;
+ return weigher.getNonViableWeight();
}
- return paths1.iterator().next().cost() + paths2.iterator().next().cost();
+ return paths1.iterator().next().cost().merge(paths2.iterator().next().cost());
}
@Override
@@ -236,13 +242,7 @@
public Set<DisjointPathPair> buildPaths() {
Set<DisjointPathPair> dpps = new HashSet<>();
for (Path<V, E> path1: findShortestPathFromSubset(subset).paths()) {
- if (path1.cost() >= INF) {
- continue;
- }
for (Path<V, E> path2: findShortestPathFromSubset(not).paths()) {
- if (path2.cost() >= INF) {
- continue;
- }
DisjointPathPair<V, E> dpp = new DisjointPathPair<>(path1, path2);
dpps.add(dpp);
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
index f517d5a..d945192 100644
--- a/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
@@ -34,8 +34,8 @@
public class SuurballeGraphSearch<V extends Vertex, E extends Edge<V>> extends DijkstraGraphSearch<V, E> {
@Override
- public Result<V, E> search(Graph<V, E> graph, V src, V dst,
- EdgeWeight<V, E> weight, int maxPaths) {
+ protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst,
+ EdgeWeigher<V, E> weigher, int maxPaths) {
// FIXME: This method needs to be refactored as it is difficult to follow and debug.
// FIXME: There is a defect here triggered by 3+ edges between the same vertices,
@@ -46,13 +46,12 @@
// This class needs to filter its own results to make sure that the
// paths are indeed disjoint. Temporary fix for this is provided, but
// the issue needs to be addressed through refactoring.
- if (weight == null) {
- weight = edge -> 1;
- }
- final EdgeWeight weightf = weight;
- DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS);
- DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS);
+ EdgeWeigher weightf = weigher;
+ DefaultResult firstDijkstraS = (DefaultResult) super.internalSearch(
+ graph, src, dst, weigher, ALL_PATHS);
+ DefaultResult firstDijkstra = (DefaultResult) super.internalSearch(
+ graph, src, null, weigher, ALL_PATHS);
//choose an arbitrary shortest path to run Suurballe on
Path<V, E> shortPath = null;
@@ -65,11 +64,43 @@
for (Path p: firstDijkstraS.paths()) {
shortPath = p;
//transforms the graph so tree edges have 0 weight
- EdgeWeight<V, E> modified = edge ->
- edge instanceof ReverseEdge ? 0 :
- weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst());
- EdgeWeight<V, E> modified2 = edge ->
- weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst());
+ EdgeWeigher<V, E> modified = new EdgeWeigher<V, E>() {
+ @Override
+ public Weight weight(E edge) {
+ return edge instanceof ReverseEdge ?
+ weightf.getInitialWeight() :
+ weightf.weight(edge).merge(firstDijkstra.cost(edge.src()))
+ .subtract(firstDijkstra.cost(edge.dst()));
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return weightf.getInitialWeight();
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return weightf.getNonViableWeight();
+ }
+ };
+
+ EdgeWeigher<V, E> modified2 = new EdgeWeigher<V, E>() {
+ @Override
+ public Weight weight(E edge) {
+ return weightf.weight(edge).merge(firstDijkstra.cost(edge.src()))
+ .subtract(firstDijkstra.cost(edge.dst()));
+ }
+
+ @Override
+ public Weight getInitialWeight() {
+ return weightf.getInitialWeight();
+ }
+
+ @Override
+ public Weight getNonViableWeight() {
+ return weightf.getNonViableWeight();
+ }
+ };
//create a residual graph g' by removing all src vertices and reversing 0 length path edges
MutableGraph<V, E> gt = mutableCopy(graph);
@@ -114,11 +145,13 @@
}
}
//Actually build the final result
- DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS);
+ DefaultResult lastSearch = (DefaultResult)
+ super.internalSearch(roundTrip, src, dst, weigher, ALL_PATHS);
Path<V, E> primary = lastSearch.paths().iterator().next();
primary.edges().forEach(roundTrip::removeEdge);
- Set<Path<V, E>> backups = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths();
+ Set<Path<V, E>> backups = super.internalSearch(roundTrip, src, dst,
+ weigher, ALL_PATHS).paths();
// Find first backup path that does not share any nodes with the primary
for (Path<V, E> backup : backups) {
@@ -220,7 +253,7 @@
}
@Override
- public Map<V, Double> costs() {
+ public Map<V, Weight> costs() {
return searchResult.costs();
}
}
diff --git a/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
index 94cb609..ad07d4b 100644
--- a/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java
@@ -37,17 +37,17 @@
* SCCs within the graph.
* </p>
* <p>
- * To prevent traversal of an edge, the {@link EdgeWeight#weight} should
- * return a negative value as an edge weight.
+ * To prevent traversal of an edge, the {@link EdgeWeigher#weight} should
+ * return a negative value as an edge weigher.
* </p>
*/
@Override
- public SccResult<V, E> search(Graph<V, E> graph, EdgeWeight<V, E> weight) {
+ public SccResult<V, E> search(Graph<V, E> graph, EdgeWeigher<V, E> weigher) {
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);
+ connect(graph, vertex, weigher, result);
}
}
return result.build();
@@ -56,14 +56,14 @@
/**
* 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
+ * @param graph graph to search
+ * @param vertex current vertex to scan and connect
+ * @param weigher optional edge weigher
+ * @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,
+ EdgeWeigher<V, E> weigher,
SccResult<V, E> result) {
VertexData<V> data = result.addData(vertex);
@@ -71,8 +71,8 @@
for (E edge : graph.getEdgesFrom(vertex)) {
V nextVertex = edge.dst();
- // If edge weight is negative, skip it.
- if (weight != null && weight.weight(edge) < 0) {
+ // If edge is not viable, skip it.
+ if (weigher != null && !weigher.weight(edge).isViable()) {
continue;
}
@@ -80,7 +80,7 @@
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);
+ nextData = connect(graph, nextVertex, weigher, result);
data.lowLink = Math.min(data.lowLink, nextData.lowLink);
} else if (result.visited(nextData)) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/Weight.java b/utils/misc/src/main/java/org/onlab/graph/Weight.java
new file mode 100644
index 0000000..9f5326d
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/Weight.java
@@ -0,0 +1,55 @@
+/*
+ * 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;
+
+/**
+ * Abstraction of a graph edge weight.
+ */
+public interface Weight extends Comparable<Weight> {
+
+ /**
+ * Merges the given weight with this one returning a new aggregated
+ * weight.
+ *
+ * @param otherWeight weight to add
+ * @return aggregated weight
+ */
+ Weight merge(Weight otherWeight);
+
+ /**
+ * Subtracts the given weight from this one and produces a new weight.
+ *
+ * @param otherWeight weight to subtract
+ * @return residual weight
+ */
+ Weight subtract(Weight otherWeight);
+
+ /**
+ * Returns true if the weighted subject (link/path) can be traversed; false otherwise.
+ *
+ * @return true if weight is adequate, false if weight is infinite
+ */
+ boolean isViable();
+
+ /**
+ * Returns true if the weight is negative (means that aggregated
+ * path cost will decrease if we add weighted subject to it).
+ *
+ * @return true if the weight is negative, false otherwise
+ */
+ boolean isNegative();
+}