| /* |
| * 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; |
| |
| 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(); |
| // 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"); |
| } |
| |
| } |