summaryrefslogtreecommitdiffstats
path: root/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
diff options
context:
space:
mode:
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.java316
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");
- }
-
-}