summaryrefslogtreecommitdiffstats
path: root/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java
diff options
context:
space:
mode:
Diffstat (limited to 'core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java')
-rw-r--r--core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java377
1 files changed, 377 insertions, 0 deletions
diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java
new file mode 100644
index 000000000..11611346b
--- /dev/null
+++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java
@@ -0,0 +1,377 @@
+package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph;
+
+import java.util.*;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+/**
+ * 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>> {
+
+ static int ALL_PATHS = -1;
+ /**
+ * Default path search result that uses the DefaultPath to convey paths
+ * in a graph.
+ */
+ public class Result {
+
+ private final V src;
+ private final V dst;
+ protected final Set<Path<V, E>> paths = new HashSet<>();
+ protected final Map<V, Weight> 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 Result(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 #ALL_PATHS} if no limit
+ */
+ public Result(V src, V dst, int maxPaths) {
+ checkNotNull(src, "Source cannot be null");
+ this.src = src;
+ this.dst = dst;
+ this.maxPaths = maxPaths;
+ }
+
+
+ public V src() {
+ return src;
+ }
+
+
+ public V dst() {
+ return dst;
+ }
+
+
+ public Set<Path<V, E>> paths() {
+ return paths;
+ }
+
+ public Map<V, Weight> costs() {
+ return costs;
+ }
+
+ 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
+ */
+ public boolean hasCost(V v) {
+ 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 weight cost to reach the vertex if already accessed;
+ * null otherwise
+ */
+ public Weight cost(V v) {
+ return costs.get(v);
+ }
+
+ /**
+ * 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
+ */
+ public void updateVertex(V vertex, E edge, Weight 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
+ */
+ public boolean relaxEdge(E edge, Weight cost, EdgeWeigher<V, E> ew,
+ boolean... forbidNegatives) {
+ V v = edge.dst();
+
+ Weight hopCost = ew.weight(edge);
+ if ((!hopCost.isViable()) ||
+ (hopCost.isNegative() && forbidNegatives.length == 1 && forbidNegatives[0])) {
+ return false;
+ }
+ Weight newCost = cost.merge(hopCost);
+
+ int compareResult = -1;
+ if (hasCost(v)) {
+ Weight oldCost = cost(v);
+ compareResult = newCost.compareTo(oldCost);
+ }
+
+ if (compareResult <= 0) {
+ updateVertex(v, edge, newCost, compareResult < 0);
+ }
+ return compareResult < 0;
+ }
+
+ /**
+ * Builds a set of paths for the specified src/dst vertex pair.
+ */
+ public 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 #ALL_PATHS} if no limit
+ */
+ private void buildAllPaths(Result 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();
+ // Exclude any looping paths
+ if (!isInPath(edge, path)) {
+ 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;
+ }
+ }
+
+ /**
+ * Indicates whether or not the specified edge source is already visited
+ * in the specified path.
+ *
+ * @param edge edge to test
+ * @param path path to test
+ * @return true if the edge.src() is a vertex in the path already
+ */
+ private boolean isInPath(E edge, DefaultMutablePath<V, E> path) {
+ return path.edges().stream().anyMatch(e -> edge.src().equals(e.dst()));
+ }
+
+ // 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");
+ }
+
+ public Result 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 Result 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.
+ Result result = new Result(src, dst, maxPaths);
+
+ // Cost to reach the source vertex is 0 of course.
+ result.updateVertex(src, null, weigher.getInitialWeight(), 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.
+ 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, weigher, 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 Result result;
+
+ private PathCostComparator(Result result) {
+ this.result = result;
+ }
+
+ @Override
+ public int compare(V v1, V v2) {
+ //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));
+ }
+ }
+
+ // 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);
+ }
+
+}