diff options
Diffstat (limited to 'framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java')
-rw-r--r-- | framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java | 316 |
1 files changed, 0 insertions, 316 deletions
diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java deleted file mode 100644 index e7e2c40d..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java +++ /dev/null @@ -1,316 +0,0 @@ -/* - * Copyright 2014-2015 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 java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.Map; -import java.util.Set; - -import static com.google.common.base.Preconditions.checkArgument; -import static com.google.common.base.Preconditions.checkNotNull; - -/** - * Basis for various graph path search algorithm implementations. - * - * @param <V> vertex type - * @param <E> edge type - */ -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. - */ - protected class DefaultResult implements Result<V, E> { - - 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, Set<E>> parents = new HashMap<>(); - protected final int maxPaths; - - /** - * Creates the result of a single-path search. - * - * @param src path source - * @param dst optional path destination - */ - public DefaultResult(V src, V dst) { - this(src, dst, 1); - } - - /** - * Creates the result of path search. - * - * @param src path source - * @param dst optional path destination - * @param maxPaths optional limit of number of paths; - * {@link GraphPathSearch#ALL_PATHS} if no limit - */ - public DefaultResult(V src, V dst, int maxPaths) { - checkNotNull(src, "Source cannot be null"); - this.src = src; - this.dst = dst; - this.maxPaths = maxPaths; - } - - @Override - public V src() { - return src; - } - - @Override - public V dst() { - return dst; - } - - @Override - public Set<Path<V, E>> paths() { - return paths; - } - - @Override - public Map<V, Double> costs() { - return costs; - } - - @Override - public Map<V, Set<E>> parents() { - return parents; - } - - /** - * Indicates whether or not the given vertex has a cost yet. - * - * @param v vertex to test - * @return true if the vertex has cost already - */ - boolean hasCost(V v) { - return costs.get(v) != null; - } - - /** - * Returns the current cost to reach the specified vertex. - * - * @param v vertex to reach - * @return cost to reach the vertex - */ - double cost(V v) { - Double c = costs.get(v); - return c == null ? Double.MAX_VALUE : c; - } - - /** - * Updates the cost of the vertex using its existing cost plus the - * cost to traverse the specified edge. If the search is in single - * path mode, only one path will be accrued. - * - * @param vertex vertex to update - * @param edge edge through which vertex is reached - * @param cost current cost to reach the vertex from the source - * @param replace true to indicate that any accrued edges are to be - * cleared; false to indicate that the edge should be - * added to the previously accrued edges as they yield - * the same cost - */ - void updateVertex(V vertex, E edge, double cost, boolean replace) { - costs.put(vertex, cost); - if (edge != null) { - Set<E> edges = parents.get(vertex); - if (edges == null) { - edges = new HashSet<>(); - parents.put(vertex, edges); - } - if (replace) { - edges.clear(); - } - if (maxPaths == ALL_PATHS || edges.size() < maxPaths) { - edges.add(edge); - } - } - } - - /** - * Removes the set of parent edges for the specified vertex. - * - * @param v vertex - */ - void removeVertex(V v) { - parents.remove(v); - } - - /** - * If possible, relax the specified edge using the supplied base cost - * and edge-weight function. - * - * @param edge edge to be relaxed - * @param cost base cost to reach the edge destination vertex - * @param ew optional edge weight function - * @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... 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]) { - return false; - } - - double newCost = cost + hopCost; - boolean relaxed = newCost < oldCost; - boolean same = Math.abs(newCost - oldCost) <= samenessThreshold; - if (same || relaxed) { - updateVertex(v, edge, newCost, !same); - } - return relaxed; - } - - /** - * Builds a set of paths for the specified src/dst vertex pair. - */ - protected void buildPaths() { - Set<V> destinations = new HashSet<>(); - if (dst == null) { - destinations.addAll(costs.keySet()); - } else { - destinations.add(dst); - } - - // Build all paths between the source and all requested destinations. - for (V v : destinations) { - // Ignore the source, if it is among the destinations. - if (!v.equals(src)) { - buildAllPaths(this, src, v, maxPaths); - } - } - } - - } - - /** - * Builds a set of all paths between the source and destination using the - * graph search result by applying breadth-first search through the parent - * edges and vertex costs. - * - * @param result graph search result - * @param src source vertex - * @param dst destination vertex - * @param maxPaths limit on the number of paths built; - * {@link GraphPathSearch#ALL_PATHS} if no limit - */ - private void buildAllPaths(DefaultResult result, V src, V dst, int maxPaths) { - DefaultMutablePath<V, E> basePath = new DefaultMutablePath<>(); - basePath.setCost(result.cost(dst)); - - Set<DefaultMutablePath<V, E>> pendingPaths = new HashSet<>(); - pendingPaths.add(basePath); - - while (!pendingPaths.isEmpty() && - (maxPaths == ALL_PATHS || result.paths.size() < maxPaths)) { - Set<DefaultMutablePath<V, E>> frontier = new HashSet<>(); - - for (DefaultMutablePath<V, E> path : pendingPaths) { - // For each pending path, locate its first vertex since we - // will be moving backwards from it. - V firstVertex = firstVertex(path, dst); - - // If the first vertex is our expected source, we have reached - // the beginning, so add the this path to the result paths. - if (firstVertex.equals(src)) { - path.setCost(result.cost(dst)); - result.paths.add(new DefaultPath<>(path.edges(), path.cost())); - - } else { - // If we have not reached the beginning, i.e. the source, - // fetch the set of edges leading to the first vertex of - // this pending path; if there are none, abandon processing - // this path for good. - Set<E> firstVertexParents = result.parents.get(firstVertex); - if (firstVertexParents == null || firstVertexParents.isEmpty()) { - break; - } - - // Now iterate over all the edges and for each of them - // cloning the current path and then insert that edge to - // the path and then add that path to the pending ones. - // When processing the last edge, modify the current - // pending path rather than cloning a new one. - Iterator<E> edges = firstVertexParents.iterator(); - while (edges.hasNext()) { - E edge = edges.next(); - boolean isLast = !edges.hasNext(); - DefaultMutablePath<V, E> pendingPath = isLast ? path : new DefaultMutablePath<>(path); - pendingPath.insertEdge(edge); - frontier.add(pendingPath); - } - } - } - - // All pending paths have been scanned so promote the next frontier - pendingPaths = frontier; - } - } - - // Returns the first vertex of the specified path. This is either the source - // of the first edge or, if there are no edges yet, the given destination. - private V firstVertex(Path<V, E> path, V dst) { - return path.edges().isEmpty() ? dst : path.edges().get(0).src(); - } - - /** - * Checks the specified path search arguments for validity. - * - * @param graph graph; must not be null - * @param src source vertex; must not be null and belong to graph - * @param dst optional target vertex; must belong to graph - */ - protected void checkArguments(Graph<V, E> graph, V src, V dst) { - checkNotNull(graph, "Graph cannot be null"); - checkNotNull(src, "Source cannot be null"); - Set<V> vertices = graph.getVertexes(); - checkArgument(vertices.contains(src), "Source not in the graph"); - checkArgument(dst == null || vertices.contains(dst), - "Destination not in graph"); - } - -} |