diff options
Diffstat (limited to 'framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java')
-rw-r--r-- | framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java | 97 |
1 files changed, 97 insertions, 0 deletions
diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java new file mode 100644 index 00000000..b1892ee1 --- /dev/null +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java @@ -0,0 +1,97 @@ +/* + * 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.ArrayList; +import java.util.Comparator; +import java.util.Set; + +/** + * Dijkstra shortest-path graph search algorithm capable of finding not just + * one, but all shortest paths between the source and destinations. + */ +public class DijkstraGraphSearch<V extends Vertex, E extends Edge<V>> + 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); + + // 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); + + if (graph.getEdges().isEmpty()) { + result.buildPaths(); + return result; + } + + // Use the min priority queue to progressively find each nearest + // vertex until we reach the desired destination, if one was given, + // or until we reach all possible destinations. + Heap<V> minQueue = createMinQueue(graph.getVertexes(), + new PathCostComparator(result)); + while (!minQueue.isEmpty()) { + // Get the nearest vertex + V nearest = minQueue.extractExtreme(); + if (nearest.equals(dst)) { + break; + } + + // Find its cost and use it to determine if the vertex is reachable. + double cost = result.cost(nearest); + if (cost < Double.MAX_VALUE) { + // If the vertex is reachable, relax all its egress edges. + for (E e : graph.getEdgesFrom(nearest)) { + result.relaxEdge(e, cost, weight, true); + } + } + + // Re-prioritize the min queue. + minQueue.heapify(); + } + + // Now construct a set of paths from the results. + result.buildPaths(); + return result; + } + + // Compares path weights using their accrued costs; used for sorting the + // min priority queue. + private final class PathCostComparator implements Comparator<V> { + private final DefaultResult result; + + private PathCostComparator(DefaultResult result) { + this.result = result; + } + + @Override + public int compare(V v1, V v2) { + double delta = result.cost(v2) - result.cost(v1); + return delta < 0 ? -1 : (delta > 0 ? 1 : 0); + } + } + + // Creates a min priority queue from the specified vertexes and comparator. + private Heap<V> createMinQueue(Set<V> vertexes, Comparator<V> comparator) { + return new Heap<>(new ArrayList<>(vertexes), comparator); + } + +} |