diff options
Diffstat (limited to 'framework/src/onos/utils/misc/src/main/java/org/onlab/graph')
28 files changed, 0 insertions, 3234 deletions
diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractEdge.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractEdge.java deleted file mode 100644 index 3e8960e6..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AbstractEdge.java +++ /dev/null @@ -1,76 +0,0 @@ -/* - * Copyright 2014 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.Objects; - -import static com.google.common.base.MoreObjects.toStringHelper; -import static com.google.common.base.Preconditions.checkNotNull; - -/** - * Abstract graph edge implementation. - */ -public abstract class AbstractEdge<V extends Vertex> implements Edge<V> { - - private final V src; - private final V dst; - - /** - * Creates a new edge between the specified source and destination vertexes. - * - * @param src source vertex - * @param dst destination vertex - */ - public AbstractEdge(V src, V dst) { - this.src = checkNotNull(src, "Source vertex cannot be null"); - this.dst = checkNotNull(dst, "Destination vertex cannot be null"); - } - - @Override - public V src() { - return src; - } - - @Override - public V dst() { - return dst; - } - - @Override - public int hashCode() { - return Objects.hash(src, dst); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof AbstractEdge) { - final AbstractEdge other = (AbstractEdge) obj; - return Objects.equals(this.src, other.src) && Objects.equals(this.dst, other.dst); - } - return false; - } - - @Override - public String toString() { - return toStringHelper(this) - .add("src", src) - .add("dst", dst) - .toString(); - } -} 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"); - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java deleted file mode 100644 index 3890dcf8..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/AdjacencyListsGraph.java +++ /dev/null @@ -1,122 +0,0 @@ -/* - * Copyright 2014 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 com.google.common.collect.ImmutableSet; -import com.google.common.collect.ImmutableSetMultimap; - -import java.util.Objects; -import java.util.Set; - -import static com.google.common.base.MoreObjects.toStringHelper; -import static com.google.common.base.Preconditions.checkNotNull; - -/** - * Immutable graph implemented using adjacency lists. - * - * @param <V> vertex type - * @param <E> edge type - */ -public class AdjacencyListsGraph<V extends Vertex, E extends Edge<V>> - implements Graph<V, E> { - - private final Set<V> vertexes; - private final Set<E> edges; - - private final ImmutableSetMultimap<V, E> sources; - private final ImmutableSetMultimap<V, E> destinations; - - /** - * Creates a graph comprising of the specified vertexes and edges. - * - * @param vertexes set of graph vertexes - * @param edges set of graph edges - */ - public AdjacencyListsGraph(Set<V> vertexes, Set<E> edges) { - checkNotNull(vertexes, "Vertex set cannot be null"); - checkNotNull(edges, "Edge set cannot be null"); - - // Record ingress/egress edges for each vertex. - ImmutableSetMultimap.Builder<V, E> srcMap = ImmutableSetMultimap.builder(); - ImmutableSetMultimap.Builder<V, E> dstMap = ImmutableSetMultimap.builder(); - - // Also make sure that all edge end-points are added as vertexes - ImmutableSet.Builder<V> actualVertexes = ImmutableSet.builder(); - actualVertexes.addAll(vertexes); - - for (E edge : edges) { - srcMap.put(edge.src(), edge); - actualVertexes.add(edge.src()); - dstMap.put(edge.dst(), edge); - actualVertexes.add(edge.dst()); - } - - // Make an immutable copy of the edge and vertex sets - this.edges = ImmutableSet.copyOf(edges); - this.vertexes = actualVertexes.build(); - - // Build immutable copies of sources and destinations edge maps - sources = srcMap.build(); - destinations = dstMap.build(); - } - - @Override - public Set<V> getVertexes() { - return vertexes; - } - - @Override - public Set<E> getEdges() { - return edges; - } - - @Override - public Set<E> getEdgesFrom(V src) { - return sources.get(src); - } - - @Override - public Set<E> getEdgesTo(V dst) { - return destinations.get(dst); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof AdjacencyListsGraph) { - AdjacencyListsGraph that = (AdjacencyListsGraph) obj; - return this.getClass() == that.getClass() && - Objects.equals(this.vertexes, that.vertexes) && - Objects.equals(this.edges, that.edges); - } - return false; - } - - @Override - public int hashCode() { - return Objects.hash(vertexes, edges); - } - - @Override - public String toString() { - return toStringHelper(this) - .add("vertexes", vertexes) - .add("edges", edges) - .toString(); - } -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java deleted file mode 100644 index dc741f73..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java +++ /dev/null @@ -1,60 +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; - -/** - * Bellman-Ford graph search algorithm for locating shortest-paths in - * directed graphs that may contain negative cycles. - */ -public class BellmanFordGraphSearch<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); - - // Prepare the graph search result. - DefaultResult result = new DefaultResult(src, dst, maxPaths); - - // The source vertex has cost 0, of course. - result.updateVertex(src, null, 0.0, true); - - int max = graph.getVertexes().size() - 1; - for (int i = 0; i < max; i++) { - // Relax, if possible, all egress edges of the current vertex. - for (E edge : graph.getEdges()) { - if (result.hasCost(edge.src())) { - result.relaxEdge(edge, result.cost(edge.src()), weight); - } - } - } - - // Remove any vertexes reached by traversing edges with negative weights. - for (E edge : graph.getEdges()) { - if (result.hasCost(edge.src())) { - if (result.relaxEdge(edge, result.cost(edge.src()), weight)) { - result.removeVertex(edge.dst()); - } - } - } - - // Finally, but the paths on the search result and return. - result.buildPaths(); - return result; - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java deleted file mode 100644 index 40c8735b..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java +++ /dev/null @@ -1,79 +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.HashSet; -import java.util.Set; - -/** - * Implementation of the BFS algorithm. - */ -public class BreadthFirstSearch<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); - - // Prepare the graph result. - DefaultResult result = new DefaultResult(src, dst, maxPaths); - - // Setup the starting frontier with the source as the sole vertex. - Set<V> frontier = new HashSet<>(); - result.updateVertex(src, null, 0.0, true); - frontier.add(src); - - boolean reachedEnd = false; - while (!reachedEnd && !frontier.isEmpty()) { - // Prepare the next frontier. - Set<V> next = new HashSet<>(); - - // Visit all vertexes in the current frontier. - for (V vertex : frontier) { - double cost = result.cost(vertex); - - // Visit all egress edges of the current frontier vertex. - for (E edge : graph.getEdgesFrom(vertex)) { - V nextVertex = edge.dst(); - if (!result.hasCost(nextVertex)) { - // If this vertex has not been visited yet, update it. - double newCost = cost + (weight == null ? 1.0 : weight.weight(edge)); - result.updateVertex(nextVertex, edge, newCost, true); - // If we have reached our intended destination, bail. - if (nextVertex.equals(dst)) { - reachedEnd = true; - break; - } - next.add(nextVertex); - } - - if (reachedEnd) { - break; - } - } - } - - // Promote the next frontier. - frontier = next; - } - - // Finally, but the paths on the search result and return. - result.buildPaths(); - return result; - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java deleted file mode 100644 index ad7e8402..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java +++ /dev/null @@ -1,136 +0,0 @@ -/* - * Copyright 2014 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 com.google.common.collect.ImmutableList; - -import java.util.ArrayList; -import java.util.List; -import java.util.Objects; - -import static com.google.common.base.MoreObjects.toStringHelper; -import static com.google.common.base.Preconditions.checkArgument; -import static com.google.common.base.Preconditions.checkNotNull; - -/** - * Simple concrete implementation of a directed graph path. - */ -public class DefaultMutablePath<V extends Vertex, E extends Edge<V>> implements MutablePath<V, E> { - - private final List<E> edges = new ArrayList<>(); - private double cost = 0.0; - - /** - * Creates a new empty path. - */ - public DefaultMutablePath() { - } - - /** - * Creates a new path as a copy of another path. - * - * @param path path to be copied - */ - public DefaultMutablePath(Path<V, E> path) { - checkNotNull(path, "Path cannot be null"); - this.cost = path.cost(); - edges.addAll(path.edges()); - } - - @Override - public V src() { - return edges.isEmpty() ? null : edges.get(0).src(); - } - - @Override - public V dst() { - return edges.isEmpty() ? null : edges.get(edges.size() - 1).dst(); - } - - @Override - public double cost() { - return cost; - } - - @Override - public List<E> edges() { - return ImmutableList.copyOf(edges); - } - - @Override - public void setCost(double cost) { - this.cost = cost; - } - - @Override - public Path<V, E> toImmutable() { - return new DefaultPath<>(edges, cost); - } - - @Override - public void insertEdge(E edge) { - checkNotNull(edge, "Edge cannot be null"); - checkArgument(edges.isEmpty() || src().equals(edge.dst()), - "Edge destination must be the same as the current path source"); - edges.add(0, edge); - } - - @Override - public void appendEdge(E edge) { - checkNotNull(edge, "Edge cannot be null"); - checkArgument(edges.isEmpty() || dst().equals(edge.src()), - "Edge source must be the same as the current path destination"); - edges.add(edge); - } - - @Override - public void removeEdge(E edge) { - checkArgument(edge.src().equals(edge.dst()) || - edges.indexOf(edge) == 0 || - edges.lastIndexOf(edge) == edges.size() - 1, - "Edge must be at start or end of path, or it must be a cyclic edge"); - edges.remove(edge); - } - - @Override - public String toString() { - return toStringHelper(this) - .add("src", src()) - .add("dst", dst()) - .add("cost", cost) - .add("edges", edges) - .toString(); - } - - @Override - public int hashCode() { - return Objects.hash(edges, cost); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof DefaultMutablePath) { - final DefaultMutablePath other = (DefaultMutablePath) obj; - return Objects.equals(this.cost, other.cost) && - Objects.equals(this.edges, other.edges); - } - return false; - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java deleted file mode 100644 index 816fb161..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java +++ /dev/null @@ -1,103 +0,0 @@ -/* - * Copyright 2014 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 com.google.common.collect.ImmutableList; - -import java.util.Collections; -import java.util.List; -import java.util.Objects; - -import static com.google.common.base.MoreObjects.toStringHelper; -import static com.google.common.base.Preconditions.checkArgument; -import static com.google.common.base.Preconditions.checkNotNull; - -/** - * Simple concrete implementation of a directed graph path. - */ -public class DefaultPath<V extends Vertex, E extends Edge<V>> implements Path<V, E> { - - private final V src; - private final V dst; - private final List<E> edges; - private double cost = 0.0; - - /** - * Creates a new path from the specified list of edges and cost. - * - * @param edges list of path edges - * @param cost path cost as a unit-less number - */ - public DefaultPath(List<E> edges, double cost) { - checkNotNull(edges, "Edges list must not be null"); - checkArgument(!edges.isEmpty(), "There must be at least one edge"); - this.edges = ImmutableList.copyOf(edges); - this.src = edges.get(0).src(); - this.dst = edges.get(edges.size() - 1).dst(); - this.cost = cost; - } - - @Override - public V src() { - return src; - } - - @Override - public V dst() { - return dst; - } - - @Override - public double cost() { - return cost; - } - - @Override - public List<E> edges() { - return Collections.unmodifiableList(edges); - } - - @Override - public String toString() { - return toStringHelper(this) - .add("src", src) - .add("dst", dst) - .add("cost", cost) - .add("edges", edges) - .toString(); - } - - @Override - public int hashCode() { - return Objects.hash(src, dst, edges, cost); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof DefaultPath) { - final DefaultPath other = (DefaultPath) obj; - return Objects.equals(this.src, other.src) && - Objects.equals(this.dst, other.dst) && - Objects.equals(this.cost, other.cost) && - Objects.equals(this.edges, other.edges); - } - return false; - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java deleted file mode 100644 index 91b5108f..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DepthFirstSearch.java +++ /dev/null @@ -1,183 +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.Map; -import java.util.Set; -import java.util.Stack; - -/** - * DFS graph search algorithm implemented via iteration rather than recursion. - */ -public class DepthFirstSearch<V extends Vertex, E extends Edge<V>> - extends AbstractGraphPathSearch<V, E> { - - /** - * Graph edge types as classified by the DFS algorithm. - */ - public static enum EdgeType { - TREE_EDGE, FORWARD_EDGE, BACK_EDGE, CROSS_EDGE - } - - @Override - public SpanningTreeResult search(Graph<V, E> graph, V src, V dst, - EdgeWeight<V, E> weight, int maxPaths) { - checkArguments(graph, src, dst); - - // Prepare the search result. - SpanningTreeResult result = new SpanningTreeResult(src, dst, maxPaths); - - // The source vertex has cost 0, of course. - result.updateVertex(src, null, 0.0, true); - - // Track finished vertexes and keep a stack of vertexes that have been - // started; start this stack with the source on it. - Set<V> finished = new HashSet<>(); - Stack<V> stack = new Stack<>(); - stack.push(src); - - while (!stack.isEmpty()) { - V vertex = stack.peek(); - if (vertex.equals(dst)) { - // If we have reached our destination, bail. - break; - } - - double cost = result.cost(vertex); - boolean tangent = false; - - // Visit all egress edges of the current vertex. - for (E edge : graph.getEdgesFrom(vertex)) { - // If we have seen the edge already, skip it. - if (result.isEdgeMarked(edge)) { - continue; - } - - // Examine the destination of the current edge. - V nextVertex = edge.dst(); - if (!result.hasCost(nextVertex)) { - // If this vertex have not finished this vertex yet, - // not started it, then start it as a tree-edge. - result.markEdge(edge, EdgeType.TREE_EDGE); - double newCost = cost + (weight == null ? 1.0 : weight.weight(edge)); - result.updateVertex(nextVertex, edge, newCost, true); - stack.push(nextVertex); - tangent = true; - break; - - } else if (!finished.contains(nextVertex)) { - // We started the vertex, but did not yet finish it, so - // it must be a back-edge. - result.markEdge(edge, EdgeType.BACK_EDGE); - } else { - // The target has been finished already, so what we have - // here is either a forward-edge or a cross-edge. - result.markEdge(edge, isForwardEdge(result, edge) ? - EdgeType.FORWARD_EDGE : EdgeType.CROSS_EDGE); - } - } - - // If we have not been sent on a tangent search and reached the - // end of the current scan normally, mark the node as finished - // and pop it off the vertex stack. - if (!tangent) { - finished.add(vertex); - stack.pop(); - } - } - - // Finally, but the paths on the search result and return. - result.buildPaths(); - return result; - } - - /** - * Determines whether the specified edge is a forward edge using the - * accumulated set of parent edges for each vertex. - * - * @param result search result - * @param edge edge to be classified - * @return true if the edge is a forward edge - */ - protected boolean isForwardEdge(DefaultResult result, E edge) { - // Follow the parent edges until we hit the edge source vertex - V target = edge.src(); - V vertex = edge.dst(); - Set<E> parentEdges; - while ((parentEdges = result.parents.get(vertex)) != null) { - for (E parentEdge : parentEdges) { - vertex = parentEdge.src(); - if (vertex.equals(target)) { - return true; - } - } - } - return false; - } - - /** - * Graph search result which includes edge classification for building - * a spanning tree. - */ - public class SpanningTreeResult extends DefaultResult { - - protected final Map<E, EdgeType> edges = new HashMap<>(); - - /** - * Creates a new spanning tree result. - * - * @param src search source - * @param dst optional search destination - * @param maxPaths limit on the number of paths - */ - public SpanningTreeResult(V src, V dst, int maxPaths) { - super(src, dst, maxPaths); - } - - /** - * Returns the map of edge type. - * - * @return edge to edge type bindings - */ - public Map<E, EdgeType> edges() { - return edges; - } - - /** - * Indicates whether or not the edge has been marked with type. - * - * @param edge edge to test - * @return true if the edge has been marked already - */ - boolean isEdgeMarked(E edge) { - return edges.containsKey(edge); - } - - /** - * Marks the edge with the specified type. - * - * @param edge edge to mark - * @param type edge type - */ - void markEdge(E edge, EdgeType type) { - edges.put(edge, type); - } - - } - -} 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 deleted file mode 100644 index b1892ee1..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java +++ /dev/null @@ -1,97 +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.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); - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java deleted file mode 100644 index dfa150e3..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java +++ /dev/null @@ -1,137 +0,0 @@ -/* - * Copyright 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.List; -import java.util.Objects; - -import static com.google.common.base.MoreObjects.toStringHelper; - -/** - * Pair of disjoint paths. - * - * @param <V> type of vertex - * @param <E> type of edge - */ -public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Path<V, E> { - - private final Path<V, E> primary, secondary; - private boolean primaryActive = true; - - /** - * Creates a disjoint path pair from two paths. - * - * @param primary primary path - * @param secondary secondary path - */ - public DisjointPathPair(Path<V, E> primary, Path<V, E> secondary) { - this.primary = primary; - this.secondary = secondary; - } - - @Override - public V src() { - return primary.src(); - } - - @Override - public V dst() { - return primary.dst(); - } - - /** - * Returns the primary path. - * - * @return primary path - */ - public Path<V, E> primary() { - return primary; - } - - /** - * Returns the secondary path. - * - * @return primary path - */ - public Path<V, E> secondary() { - return secondary; - } - - @Override - public double cost() { - return hasBackup() ? primary.cost() + secondary.cost() : primary.cost(); - } - - @Override - public List<E> edges() { - return primaryActive || !hasBackup() ? primary.edges() : secondary.edges(); - } - - /** - * Checks if this path pair contains a backup/secondary path. - * - * @return boolean representing whether it has backup - */ - public boolean hasBackup() { - return secondary != null; - } - - @Override - public String toString() { - return toStringHelper(this) - .add("src", src()) - .add("dst", dst()) - .add("cost", cost()) - .add("edges", edges()) - .toString(); - } - - @Override - public int hashCode() { - // Note: DisjointPathPair with primary and secondary swapped - // must result in same hashCode - return hasBackup() ? primary.hashCode() + secondary.hashCode() : - Objects.hash(primary); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof DisjointPathPair) { - final DisjointPathPair other = (DisjointPathPair) obj; - return Objects.equals(this.src(), other.src()) && - Objects.equals(this.dst(), other.dst()) && - (Objects.equals(this.primary, other.primary) && - Objects.equals(this.secondary, other.secondary)) || - (Objects.equals(this.primary, other.secondary) && - Objects.equals(this.secondary, other.primary)); - } - return false; - } - - /** - * Returns number of paths inside this path pair object. - * - * @return number of paths - */ - public int size() { - return hasBackup() ? 2 : 1; - } -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Edge.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Edge.java deleted file mode 100644 index 1bbfbf99..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Edge.java +++ /dev/null @@ -1,39 +0,0 @@ -/* - * Copyright 2014 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; - -/** - * Representation of a graph edge. - * - * @param <V> vertex type - */ -public interface Edge<V extends Vertex> { - - /** - * Returns the edge source vertex. - * - * @return source vertex - */ - V src(); - - /** - * Returns the edge destination vertex. - * - * @return destination vertex - */ - V dst(); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java deleted file mode 100644 index 975b59c7..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/EdgeWeight.java +++ /dev/null @@ -1,31 +0,0 @@ -/* - * Copyright 2014 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; - -/** - * Abstraction of a graph edge weight function. - */ -public interface EdgeWeight<V extends Vertex, E extends Edge<V>> { - - /** - * Returns the weight of the given edge as a unit-less number. - * - * @param edge edge to be weighed - * @return edge weight as a unit-less number - */ - double weight(E edge); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java deleted file mode 100644 index a0e0570d..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GAOrganism.java +++ /dev/null @@ -1,53 +0,0 @@ -/* - * Copyright 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; - -/** - * Interface representing an "organism": a specific solution - * to a problem where solutions can be evaluated in terms - * of fitness. These organisms can be used to represent any - * class of problem that genetic algorithms can be run on. - */ -interface GAOrganism { - /** - * A fitness function that determines how - * optimal a given organism is. - * - * @return fitness of organism - */ - double fitness(); - - /** - * A method that slightly mutates an organism. - */ - void mutate(); - - /** - * Creates a new random organism. - * - * @return random GAOrganism - */ - GAOrganism random(); - - /** - * Returns a child organism that is the result - * of "crossing" this organism with another. - * - * @param other Other organism to cross with - * @return child organism - */ - GAOrganism crossWith(GAOrganism other); -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java deleted file mode 100644 index c5fa9b45..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GAPopulation.java +++ /dev/null @@ -1,90 +0,0 @@ -/* - * Copyright 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.Collections; -import java.util.List; -import java.util.Random; - -/** - * Represents a population of GAOrganisms. This class can be used - * to run a genetic algorithm on the population and return the fittest solutions. - */ -class GAPopulation<Organism extends GAOrganism> extends ArrayList<Organism> { - Random r = new Random(); - - /** - * Steps the population through one generation. The 75% least fit - * organisms are killed off and replaced with the children of the - * 25% (as well as some "random" newcomers). - */ - void step() { - Collections.sort(this, (org1, org2) -> { - double d = org1.fitness() - org2.fitness(); - if (d < 0) { - return -1; - } else if (d == 0) { - return 0; - } - return 1; - }); - int maxSize = size(); - for (int i = size() - 1; i > maxSize / 4; i--) { - remove(i); - } - for (Organism org: this) { - if (r.nextBoolean()) { - org.mutate(); - } - } - while (size() < maxSize * 4 / 5) { - Organism org1 = get(r.nextInt(size())); - Organism org2 = get(r.nextInt(size())); - add((Organism) org1.crossWith(org2)); - } - - while (size() < maxSize) { - Organism org1 = get(r.nextInt(size())); - add((Organism) org1.random()); - } - } - - /** - * Runs GA for the specified number of iterations, and returns - * a sample of the resulting population of solutions. - * - * @param generations Number of generations to run GA for - * @param populationSize Population size of GA - * @param sample Number of solutions to ask for - * @param template Template GAOrganism to seed the population with - * @return ArrayList containing sample number of organisms - */ - List<Organism> runGA(int generations, int populationSize, int sample, Organism template) { - for (int i = 0; i < populationSize; i++) { - add((Organism) template.random()); - } - - for (int i = 0; i < generations; i++) { - step(); - } - for (int i = size() - 1; i >= sample; i--) { - remove(i); - } - return new ArrayList<>(this); - } -} - diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Graph.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Graph.java deleted file mode 100644 index bc7853ec..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Graph.java +++ /dev/null @@ -1,59 +0,0 @@ -/* - * Copyright 2014 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.Set; - -/** - * Abstraction of a directed graph structure. - * - * @param <V> vertex type - * @param <E> edge type - */ -public interface Graph<V extends Vertex, E extends Edge> { - - /** - * Returns the set of vertexes comprising the graph. - * - * @return set of vertexes - */ - Set<V> getVertexes(); - - /** - * Returns the set of edges comprising the graph. - * - * @return set of edges - */ - Set<E> getEdges(); - - /** - * Returns all edges leading out from the specified source vertex. - * - * @param src source vertex - * @return set of egress edges; empty if no such edges - */ - Set<E> getEdgesFrom(V src); - - /** - * Returns all edges leading towards the specified destination vertex. - * - * @param dst destination vertex - * @return set of ingress vertexes; empty if no such edges - */ - Set<E> getEdgesTo(V dst); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java deleted file mode 100644 index caebce47..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GraphPathSearch.java +++ /dev/null @@ -1,87 +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.Map; -import java.util.Set; - -/** - * Representation of a graph path search algorithm. - * - * @param <V> vertex type - * @param <E> edge type - */ -public interface GraphPathSearch<V extends Vertex, E extends Edge<V>> { - - static int ALL_PATHS = -1; - - /** - * Abstraction of a path search result. - */ - interface Result<V extends Vertex, E extends Edge<V>> { - - /** - * Returns the search source. - * - * @return search source - */ - V src(); - - /** - * Returns the search destination, if was was given. - * - * @return optional search destination - */ - V dst(); - - /** - * Returns the set of paths produced as a result of the graph search. - * - * @return set of paths - */ - Set<Path<V, E>> paths(); - - /** - * Returns bindings of each vertex to its parent edges in the path. - * - * @return map of vertex to its parent edge bindings - */ - Map<V, Set<E>> parents(); - - /** - * Return a bindings of each vertex to its cost in the path. - * - * @return map of vertex to path cost bindings - */ - Map<V, Double> costs(); - } - - /** - * Searches the specified graph for paths between vertices. - * - * @param graph graph to be searched - * @param src optional source vertex - * @param dst optional destination vertex; if null paths to all vertex - * destinations will be searched - * @param weight optional edge-weight; if null cost of each edge will be - * assumed to be 1.0 - * @param maxPaths limit on number of paths; {@link GraphPathSearch#ALL_PATHS} if no limit - * @return search results - */ - Result<V, E> search(Graph<V, E> graph, V src, V dst, - EdgeWeight<V, E> weight, int maxPaths); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java deleted file mode 100644 index ca369a7d..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/GraphSearch.java +++ /dev/null @@ -1,43 +0,0 @@ -/* - * Copyright 2014 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; - -/** - * Representation of a graph search algorithm and its outcome. - * - * @param <V> vertex type - * @param <E> edge type - */ -public interface GraphSearch<V extends Vertex, E extends Edge<V>> { - - /** - * Notion of a graph search result. - */ - interface Result<V extends Vertex, E extends Edge<V>> { - } - - /** - * Searches the specified graph. - * - * @param graph graph to be searched - * @param weight optional edge-weight; if null cost of each edge will be - * assumed to be 1.0 - * - * @return search results - */ - Result search(Graph<V, E> graph, EdgeWeight<V, E> weight); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Heap.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Heap.java deleted file mode 100644 index ebb1a60b..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Heap.java +++ /dev/null @@ -1,211 +0,0 @@ -/* - * Copyright 2014 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 com.google.common.collect.ImmutableList; - -import java.util.Comparator; -import java.util.Iterator; -import java.util.List; -import java.util.Objects; - -import static com.google.common.base.MoreObjects.toStringHelper; -import static com.google.common.base.Preconditions.checkNotNull; - -/** - * Implementation of an array-backed heap structure whose sense of order is - * imposed by the provided comparator. - * <p> - * While this provides similar functionality to {@link java.util.PriorityQueue} - * data structure, one key difference is that external entities can control - * when to restore the heap property, which is done through invocation of the - * {@link #heapify} method. - * </p> - * <p> - * This class is not thread-safe and care must be taken to prevent concurrent - * modifications. - * </p> - * - * @param <T> type of the items on the heap - */ -public class Heap<T> { - - private final List<T> data; - private final Comparator<T> comparator; - - /** - * Creates a new heap backed by the specified list. In the interest of - * efficiency, the list should be array-backed. Also, for the same reason, - * the data is not copied and therefore, the caller must assure that the - * backing data is not altered in any way. - * - * @param data backing data list - * @param comparator comparator for ordering the heap items - */ - public Heap(List<T> data, Comparator<T> comparator) { - this.data = checkNotNull(data, "Data cannot be null"); - this.comparator = checkNotNull(comparator, "Comparator cannot be null"); - heapify(); - } - - /** - * Restores the heap property by re-arranging the elements in the backing - * array as necessary following any heap modifications. - */ - public void heapify() { - for (int i = data.size() / 2; i >= 0; i--) { - heapify(i); - } - } - - /** - * Returns the current size of the heap. - * - * @return number of items in the heap - */ - public int size() { - return data.size(); - } - - /** - * Returns true if there are no items in the heap. - * - * @return true if heap is empty - */ - public boolean isEmpty() { - return data.isEmpty(); - } - - /** - * Returns the most extreme item in the heap. - * - * @return heap extreme or null if the heap is empty - */ - public T extreme() { - return data.isEmpty() ? null : data.get(0); - } - - /** - * Extracts and returns the most extreme item from the heap. - * - * @return heap extreme or null if the heap is empty - */ - public T extractExtreme() { - if (!isEmpty()) { - T extreme = extreme(); - - data.set(0, data.get(data.size() - 1)); - data.remove(data.size() - 1); - heapify(); - return extreme; - } - return null; - } - - /** - * Inserts the specified item into the heap and returns the modified heap. - * - * @param item item to be inserted - * @return the heap self - * @throws IllegalArgumentException if the heap is already full - */ - public Heap<T> insert(T item) { - data.add(item); - bubbleUp(); - return this; - } - - /** - * Returns iterator to traverse the heap level-by-level. This iterator - * does not permit removal of items. - * - * @return non-destructive heap iterator - */ - public Iterator<T> iterator() { - return ImmutableList.copyOf(data).iterator(); - } - - // Bubbles up the last item in the heap to its proper position to restore - // the heap property. - private void bubbleUp() { - int child = data.size() - 1; - while (child > 0) { - int parent = child / 2; - if (comparator.compare(data.get(child), data.get(parent)) < 0) { - break; - } - swap(child, parent); - child = parent; - } - } - - // Restores the heap property of the specified heap layer. - private void heapify(int i) { - int left = 2 * i + 1; - int right = 2 * i; - int extreme = i; - - if (left < data.size() && - comparator.compare(data.get(extreme), data.get(left)) < 0) { - extreme = left; - } - - if (right < data.size() && - comparator.compare(data.get(extreme), data.get(right)) < 0) { - extreme = right; - } - - if (extreme != i) { - swap(i, extreme); - heapify(extreme); - } - } - - // Swaps two heap items identified by their respective indexes. - private void swap(int i, int k) { - T aux = data.get(i); - data.set(i, data.get(k)); - data.set(k, aux); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof Heap) { - Heap that = (Heap) obj; - return this.getClass() == that.getClass() && - Objects.equals(this.comparator, that.comparator) && - Objects.deepEquals(this.data, that.data); - } - return false; - } - - @Override - public int hashCode() { - return Objects.hash(comparator, data); - } - - @Override - public String toString() { - return toStringHelper(this) - .add("data", data) - .add("comparator", comparator) - .toString(); - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/KshortestPathSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/KshortestPathSearch.java deleted file mode 100644 index 820e912c..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/KshortestPathSearch.java +++ /dev/null @@ -1,286 +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.ArrayList; -//import java.util.HashMap; -import java.util.Iterator; -import java.util.List; -//import java.util.Map; -//import java.util.PriorityQueue; -import java.util.Set; - -import static org.onlab.graph.GraphPathSearch.ALL_PATHS; - -/** - * K-shortest-path graph search algorithm capable of finding not just one, - * but K shortest paths with ascending order between the source and destinations. - */ - -public class KshortestPathSearch<V extends Vertex, E extends Edge<V>> { - - // Define class variables. - private Graph<V, E> immutableGraph; - private MutableGraph<V, E> mutableGraph; - private List<List<E>> pathResults = new ArrayList<List<E>>(); - private List<List<E>> pathCandidates = new ArrayList<List<E>>(); - private V source; - private V sink; - private int numK = 0; - private EdgeWeight<V, E> weight = null; - // private PriorityQueue<List<E>> pathCandidates = new PriorityQueue<List<E>>(); - - // Initialize the graph. - public KshortestPathSearch(Graph<V, E> graph) { - immutableGraph = graph; - mutableGraph = new MutableAdjacencyListsGraph<>(graph.getVertexes(), - graph.getEdges()); - } - - public List<List<E>> search(V src, - V dst, - EdgeWeight<V, E> wei, - int k) { - - weight = wei; - source = src; - sink = dst; - numK = k; - // pathCandidates = new PriorityQueue<List<E>>(); - - pathResults.clear(); - pathCandidates.clear(); - - // Double check the parameters - checkArguments(immutableGraph, src, dst, numK); - - // DefaultResult result = new DefaultResult(src, dst); - - searchKShortestPaths(); - - return pathResults; - } - - private void checkArguments(Graph<V, E> graph, V src, V dst, int k) { - if (graph == null) { - throw new NullPointerException("graph is null"); - } - if (!graph.getVertexes().contains(src)) { - throw new NullPointerException("source node does not exist"); - } - if (!graph.getVertexes().contains(dst)) { - throw new NullPointerException("target node does not exist"); - } - if (k <= 0) { - throw new NullPointerException("K is negative or 0"); - } - if (weight == null) { - throw new NullPointerException("the cost matrix is null"); - } - } - - private void searchKShortestPaths() { - // Step 1: find the shortest path. - List<E> shortestPath = searchShortestPath(immutableGraph, source, sink); - // no path exists, exit. - if (shortestPath == null) { - return; - } - - // Step 2: update the results. - pathResults.add(shortestPath); - // pathCandidates.add(shortestPath); - - // Step 3: find the other K-1 paths. - while (/*pathCandidates.size() > 0 &&*/pathResults.size() < numK) { - // 3.1 the spur node ranges from the first node to the last node in the previous k-shortest path. - List<E> lastPath = pathResults.get(pathResults.size() - 1); - for (int i = 0; i < lastPath.size(); i++) { - // 3.1.1 convert the graph into mutable. - convertGraph(); - // 3.1.2 transform the graph. - List<E> rootPath = createSpurNode(lastPath, i); - transformGraph(rootPath); - // 3.1.3 find the deviation node. - V devNode; - devNode = getDevNode(rootPath); - List<E> spurPath; - // 3.1.4 find the shortest path in the transformed graph. - spurPath = searchShortestPath(mutableGraph, devNode, sink); - // 3.1.5 update the path candidates. - if (spurPath != null) { - // totalPath = rootPath + spurPath; - rootPath.addAll(spurPath); - pathCandidates.add(rootPath); - } - } - // 3.2 if there is no spur path, exit. - if (pathCandidates.size() == 0) { - break; - } - // 3.3 add the path into the results. - addPathResult(); - } - } - - @SuppressWarnings({ "rawtypes", "unchecked" }) - private List<E> searchShortestPath(Graph<V, E> graph, V src, V dst) { - // Determine the shortest path from the source to the destination by using the Dijkstra algorithm. - DijkstraGraphSearch dijkstraAlg = new DijkstraGraphSearch(); - Set<Path> paths = dijkstraAlg.search(graph, src, dst, weight, ALL_PATHS).paths(); - Iterator<Path> itr = paths.iterator(); - if (!itr.hasNext()) { - return null; - } - // return the first shortest path only. - return (List<E>) itr.next().edges(); - } - - private void convertGraph() { - // clear the mutableGraph first - if (mutableGraph != null) { - ((MutableAdjacencyListsGraph) mutableGraph).clear(); - } - - // create a immutableGraph - Set<E> copyEa = immutableGraph.getEdges(); - Set<V> copyVa = immutableGraph.getVertexes(); - for (V vertex : copyVa) { - mutableGraph.addVertex(vertex); - } - for (E edge : copyEa) { - mutableGraph.addEdge(edge); - } - } - - private V getDevNode(List<E> path) { - V srcA; - V dstB; - - if (path.size() == 0) { - return source; - } - - E temp1 = path.get(path.size() - 1); - srcA = temp1.src(); - dstB = temp1.dst(); - - if (path.size() == 1) { - if (srcA.equals(source)) { - return dstB; - } else { - return srcA; - } - } else { - E temp2 = path.get(path.size() - 2); - if (srcA.equals(temp2.src()) || srcA.equals(temp2.dst())) { - return dstB; - } else { - return srcA; - } - } - } - - private List<E> createSpurNode(List<E> path, int n) { - List<E> root = new ArrayList<E>(); - - for (int i = 0; i < n; i++) { - root.add(path.get(i)); - } - return root; - } - - private void transformGraph(List<E> rootPath) { - List<E> prePath; - //remove edges - for (int i = 0; i < pathResults.size(); i++) { - prePath = pathResults.get(i); - if (prePath.size() == 1) { - mutableGraph.removeEdge(prePath.get(0)); - } else if (comparePath(rootPath, prePath)) { - for (int j = 0; j <= rootPath.size(); j++) { - mutableGraph.removeEdge(prePath.get(j)); - } - } - } - for (int i = 0; i < pathCandidates.size(); i++) { - prePath = pathCandidates.get(i); - if (prePath.size() == 1) { - mutableGraph.removeEdge(prePath.get(0)); - } else if (comparePath(rootPath, prePath)) { - for (int j = 0; j <= rootPath.size(); j++) { - mutableGraph.removeEdge(prePath.get(j)); - } - } - } - - if (rootPath.size() == 0) { - return; - } - - //remove nodes - List<V> nodes = new ArrayList<V>(); - nodes.add(source); - V pre = source; - V srcA; - V dstB; - for (int i = 0; i < rootPath.size() - 1; i++) { - E temp = rootPath.get(i); - srcA = temp.src(); - dstB = temp.dst(); - - if (srcA.equals(pre)) { - nodes.add(dstB); - pre = dstB; - } else { - nodes.add(srcA); - pre = srcA; - } - } - for (int i = 0; i < nodes.size(); i++) { - mutableGraph.removeVertex(nodes.get(i)); - } - } - - private boolean comparePath(List<E> path1, List<E> path2) { - if (path1.size() > path2.size()) { - return false; - } - if (path1.size() == 0) { - return true; - } - for (int i = 0; i < path1.size(); i++) { - if (path1.get(i) != path2.get(i)) { - return false; - } - } - return true; - } - - private void addPathResult() { - List<E> sp; - sp = pathCandidates.get(0); - for (int i = 1; i < pathCandidates.size(); i++) { - if (sp.size() > pathCandidates.get(i).size()) { - sp = pathCandidates.get(i); - } - } - pathResults.add(sp); - // Log.info(sp.toString()); - pathCandidates.remove(sp); - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutableAdjacencyListsGraph.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutableAdjacencyListsGraph.java deleted file mode 100644 index 87571c4b..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutableAdjacencyListsGraph.java +++ /dev/null @@ -1,160 +0,0 @@ -/* - * Copyright 2014 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 static com.google.common.base.MoreObjects.toStringHelper; - -import java.util.HashSet; -import java.util.Objects; -import java.util.Set; - -import com.google.common.collect.HashMultimap; -import com.google.common.collect.SetMultimap; - -public class MutableAdjacencyListsGraph<V extends Vertex, E extends Edge<V>> -implements MutableGraph<V, E> { - private Set<V> vertexes = new HashSet<V>(); - private Set<E> edges = new HashSet<E>(); - - private SetMultimap<V, E> sources = HashMultimap.create(); - private SetMultimap<V, E> destinations = HashMultimap.create(); - - /** - * Creates a graph comprising of the specified vertexes and edges. - * - * @param vertex set of graph vertexes - * @param edge set of graph edges - */ - public MutableAdjacencyListsGraph(Set<V> vertex, Set<E> edge) { - vertexes.addAll(vertex); - edges.addAll(edge); - for (E e : edge) { - sources.put(e.src(), e); - vertexes.add(e.src()); - destinations.put(e.dst(), e); - vertexes.add(e.dst()); - } - } - - @Override - public Set<V> getVertexes() { - return vertexes; - } - - @Override - public Set<E> getEdges() { - return edges; - } - - @Override - public Set<E> getEdgesFrom(V src) { - return sources.get(src); - } - - @Override - public Set<E> getEdgesTo(V dst) { - return destinations.get(dst); - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj instanceof MutableAdjacencyListsGraph) { - MutableAdjacencyListsGraph that = (MutableAdjacencyListsGraph) obj; - return this.getClass() == that.getClass() && - Objects.equals(this.vertexes, that.vertexes) && - Objects.equals(this.edges, that.edges); - } - return false; - } - - @Override - public int hashCode() { - return Objects.hash(vertexes, edges); - } - - @Override - public String toString() { - return toStringHelper(this) - .add("vertexes", vertexes) - .add("edges", edges) - .toString(); - } - - - @Override - public void addVertex(V vertex) { - if (vertexes != null) { - if (!vertexes.contains(vertex)) { - vertexes.add(vertex); - } - } - } - - @Override - public void removeVertex(V vertex) { - if (vertexes != null && edges != null) { - if (vertexes.contains(vertex)) { - vertexes.remove(vertex); - Set<E> srcEdgesList = sources.get(vertex); - Set<E> dstEdgesList = destinations.get(vertex); - edges.removeAll(srcEdgesList); - edges.removeAll(dstEdgesList); - sources.remove(vertex, srcEdgesList); - sources.remove(vertex, dstEdgesList); - } - } - } - - @Override - public void addEdge(E edge) { - if (edges != null) { - if (!edges.contains(edge)) { - edges.add(edge); - sources.put(edge.src(), edge); - destinations.put(edge.dst(), edge); - } - } - } - - @Override - public void removeEdge(E edge) { - if (edges != null) { - if (edges.contains(edge)) { - edges.remove(edge); - sources.remove(edge.src(), edge); - destinations.remove(edge.dst(), edge); - } - } - } - - @Override - public Graph<V, E> toImmutable() { - return null; - } - - /** - * Clear the graph. - */ - public void clear() { - edges.clear(); - vertexes.clear(); - sources.clear(); - destinations.clear(); - } -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutableGraph.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutableGraph.java deleted file mode 100644 index bd2b600c..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutableGraph.java +++ /dev/null @@ -1,59 +0,0 @@ -/* - * Copyright 2014 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; - -/** - * Abstraction of a mutable graph that can be constructed gradually. - */ -public interface MutableGraph<V extends Vertex, E extends Edge> extends Graph<V, E> { - - /** - * Adds the specified vertex to this graph. - * - * @param vertex new vertex - */ - void addVertex(V vertex); - - /** - * Removes the specified vertex from the graph. - * - * @param vertex vertex to be removed - */ - void removeVertex(V vertex); - - /** - * Adds the specified edge to this graph. If the edge vertexes are not - * already in the graph, they will be added as well. - * - * @param edge new edge - */ - void addEdge(E edge); - - /** - * Removes the specified edge from the graph. - * - * @param edge edge to be removed - */ - void removeEdge(E edge); - - /** - * Returns an immutable copy of this graph. - * - * @return immutable copy - */ - Graph<V, E> toImmutable(); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutablePath.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutablePath.java deleted file mode 100644 index 5cd8fd0e..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/MutablePath.java +++ /dev/null @@ -1,62 +0,0 @@ -/* - * Copyright 2014 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; - -/** - * Abstraction of a mutable path that allows gradual construction. - */ -public interface MutablePath<V extends Vertex, E extends Edge<V>> extends Path<V, E> { - - /** - * Inserts a new edge at the beginning of this path. The edge must be - * adjacent to the prior start of the path. - * - * @param edge edge to be inserted - */ - void insertEdge(E edge); - - /** - * Appends a new edge at the end of the this path. The edge must be - * adjacent to the prior end of the path. - * - * @param edge edge to be inserted - */ - void appendEdge(E edge); - - /** - * Removes the specified edge. This edge must be either at the start or - * at the end of the path, or it must be a cyclic edge in order not to - * violate the contiguous path property. - * - * @param edge edge to be removed - */ - void removeEdge(E edge); - - /** - * Sets the total path cost as a unit-less double. - * - * @param cost new path cost - */ - void setCost(double cost); - - /** - * Returns an immutable copy of this path. - * - * @return immutable copy - */ - Path<V, E> toImmutable(); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Path.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Path.java deleted file mode 100644 index ed9aa2c9..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Path.java +++ /dev/null @@ -1,45 +0,0 @@ -/* - * Copyright 2014 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.List; - -/** - * Representation of a path in a graph as a sequence of edges. Paths are - * assumed to be continuous, where adjacent edges must share a vertex. - * - * @param <V> vertex type - * @param <E> edge type - */ -public interface Path<V extends Vertex, E extends Edge<V>> extends Edge<V> { - - /** - * Returns the list of edges comprising the path. Adjacent edges will - * share the same vertex, meaning that a source of one edge, will be the - * same as the destination of the prior edge. - * - * @return list of path edges - */ - List<E> edges(); - - /** - * Returns the total cost of the path as a unit-less number. - * - * @return path cost as a unit-less number - */ - double cost(); - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java deleted file mode 100644 index fa3d0ddf..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SrlgGraphSearch.java +++ /dev/null @@ -1,253 +0,0 @@ -/* - * Copyright 2014 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.Map; -import java.util.List; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Set; -import java.util.Random; - - -/** - * SRLG Graph Search finds a pair of paths with disjoint risk groups; i.e - * if one path goes through an edge in risk group 1, the other path will go - * through no edges in risk group 1. - */ -public class SrlgGraphSearch<V extends Vertex, E extends Edge<V>> - extends AbstractGraphPathSearch<V, E> { - - static final int ITERATIONS = 100; - static final int POPSIZE = 50; - - boolean useSuurballe = false; - - static final double INF = 100000000.0; - - int numGroups; - Map<E, Integer> riskGrouping; - - Graph<V, E> orig; - V src, dst; - EdgeWeight<V, E> weight; - - /** - * Creates an SRLG graph search object with the given number - * of groups and given risk mapping. - * - * @param groups the number of disjoint risk groups - * @param grouping map linking edges to integral group assignments - */ - public SrlgGraphSearch(int groups, Map<E, Integer> grouping) { - numGroups = groups; - riskGrouping = grouping; - } - - /** - * Creates an SRLG graph search object from a map, inferring - * the number of groups and creating an integral mapping. - * - * @param grouping map linking edges to object group assignments, - * with same-group status linked to equality - */ - public SrlgGraphSearch(Map<E, Object> grouping) { - if (grouping == null) { - useSuurballe = true; - return; - } - numGroups = 0; - HashMap<Object, Integer> tmpMap = new HashMap<>(); - riskGrouping = new HashMap<>(); - for (E key: grouping.keySet()) { - Object value = grouping.get(key); - if (!tmpMap.containsKey(value)) { - tmpMap.put(value, numGroups); - numGroups++; - } - riskGrouping.put(key, tmpMap.get(value)); - } - } - - @Override - public Result<V, E> search(Graph<V, E> graph, V src, V dst, - EdgeWeight<V, E> weight, int maxPaths) { - if (maxPaths == ALL_PATHS) { - maxPaths = POPSIZE; - } - if (useSuurballe) { - return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS); - } - if (weight == null) { - weight = edge -> 1; - } - checkArguments(graph, src, dst); - orig = graph; - this.src = src; - this.dst = dst; - this.weight = weight; - List<Subset> best = new GAPopulation<Subset>() - .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups])); - Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>(); - for (Subset s: best) { - dpps.addAll(s.buildPaths()); - } - Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>() - .search(orig, src, dst, weight, 1); - return new Result<V, E>() { - final DefaultResult search = (DefaultResult) firstDijkstra; - - public V src() { - return src; - } - public V dst() { - return dst; - - } - public Set<Path<V, E>> paths() { - Set<Path<V, E>> pathsD = new HashSet<>(); - for (DisjointPathPair<V, E> path: dpps) { - pathsD.add(path); - } - return pathsD; - } - public Map<V, Double> costs() { - return search.costs(); - - } - public Map<V, Set<E>> parents() { - return search.parents(); - - } - }; - } - - //finds the shortest path in the graph given a subset of edge types to use - private Result<V, E> findShortestPathFromSubset(boolean[] subset) { - Graph<V, E> graph = orig; - EdgeWeight<V, E> modified = new EdgeWeight<V, E>() { - final boolean[] subsetF = subset; - - @Override - public double weight(E edge) { - if (subsetF[riskGrouping.get(edge)]) { - return weight.weight(edge); - } - return INF; - } - }; - - Result<V, E> res = new DijkstraGraphSearch<V, E>().search(graph, src, dst, modified, 1); - return res; - } - /** - * A subset is a type of GA organism that represents a subset of allowed shortest - * paths (and its complement). Its fitness is determined by the sum of the weights - * of the first two shortest paths. - */ - class Subset implements GAOrganism { - - boolean[] subset; - boolean[] not; - Random r = new Random(); - - /** - * Creates a Subset from the given subset array. - * - * @param sub subset array - */ - public Subset(boolean[] sub) { - subset = sub.clone(); - not = new boolean[subset.length]; - for (int i = 0; i < subset.length; i++) { - not[i] = !subset[i]; - } - } - - @Override - public double fitness() { - Set<Path<V, E>> paths1 = findShortestPathFromSubset(subset).paths(); - Set<Path<V, E>> paths2 = findShortestPathFromSubset(not).paths(); - if (paths1.size() == 0 || paths2.size() == 0) { - return INF; - } - return paths1.iterator().next().cost() + paths2.iterator().next().cost(); - } - - @Override - public void mutate() { - int turns = r.nextInt((int) Math.sqrt(subset.length)); - while (turns > 0) { - int choose = r.nextInt(subset.length); - subset[choose] = !subset[choose]; - not[choose] = !not[choose]; - turns--; - } - } - - @Override - public GAOrganism crossWith(GAOrganism org) { - if (!(org.getClass().equals(getClass()))) { - return this; - } - Subset other = (Subset) (org); - boolean[] sub = new boolean[subset.length]; - for (int i = 0; i < subset.length; i++) { - sub[i] = subset[i]; - if (r.nextBoolean()) { - sub[i] = other.subset[i]; - } - } - return new Subset(sub); - } - - @Override - public GAOrganism random() { - boolean[] sub = new boolean[subset.length]; - for (int i = 0; i < sub.length; i++) { - sub[i] = r.nextBoolean(); - } - return new Subset(sub); - } - - /** - * Builds the set of disjoint path pairs for a given subset - * using Dijkstra's algorithm on both the subset and complement - * and returning all pairs with one from each set. - * - * @return all shortest disjoint paths given this subset - */ - public Set<DisjointPathPair> buildPaths() { - Set<DisjointPathPair> dpps = new HashSet<>(); - for (Path<V, E> path1: findShortestPathFromSubset(subset).paths()) { - if (path1.cost() >= INF) { - continue; - } - for (Path<V, E> path2: findShortestPathFromSubset(not).paths()) { - if (path2.cost() >= INF) { - continue; - } - DisjointPathPair<V, E> dpp = new DisjointPathPair<>(path1, path2); - dpps.add(dpp); - } - } - return dpps; - } - } -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java deleted file mode 100644 index 76591c82..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java +++ /dev/null @@ -1,193 +0,0 @@ -/* - * Copyright 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.Set; -import java.util.List; -import java.util.Map; -import java.util.HashMap; -import java.util.HashSet; -import java.util.stream.Collectors; - -/** - * Suurballe shortest-path graph search algorithm capable of finding both - * a shortest path, as well as a backup shortest path, between a source and a destination - * such that the sum of the path lengths is minimized. - */ -public class SuurballeGraphSearch<V extends Vertex, E extends Edge<V>> extends DijkstraGraphSearch<V, E> { - - @Override - public Result<V, E> search(Graph<V, E> graph, V src, V dst, - EdgeWeight<V, E> weight, int maxPaths) { - - if (weight == null) { - weight = edge -> 1; - } - - List<DisjointPathPair<V, E>> dpps = new ArrayList<>(); - - final EdgeWeight weightf = weight; - DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS); - DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS); - - //choose an arbitrary shortest path to run Suurballe on - Path<V, E> shortPath = null; - if (firstDijkstraS.paths().size() == 0) { - return firstDijkstraS; - } - for (Path p: firstDijkstraS.paths()) { - shortPath = p; - //transforms the graph so tree edges have 0 weight - EdgeWeight<V, Edge<V>> modified = edge -> { - if (classE().isInstance(edge)) { - return weightf.weight((E) (edge)) + firstDijkstra.cost(edge.src()) - - firstDijkstra.cost(edge.dst()); - } - return 0; - }; - EdgeWeight<V, E> modified2 = edge -> - weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); - - //create a residual graph g' by removing all src vertices and reversing 0 length path edges - MutableGraph<V, Edge<V>> gt = mutableCopy(graph); - - Map<Edge<V>, E> revToEdge = new HashMap<>(); - graph.getEdgesTo(src).forEach(gt::removeEdge); - for (E edge: shortPath.edges()) { - gt.removeEdge(edge); - Edge<V> reverse = new Edge<V>() { - final Edge<V> orig = edge; - public V src() { - return orig.dst(); - } - public V dst() { - return orig.src(); - } - public String toString() { - return "ReversedEdge " + "src=" + src() + " dst=" + dst(); - } - }; - revToEdge.put(reverse, edge); - gt.addEdge(reverse); - } - - //rerun dijkstra on the temporary graph to get a second path - Result<V, Edge<V>> secondDijkstra; - secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS); - - Path<V, Edge<V>> residualShortPath = null; - if (secondDijkstra.paths().size() == 0) { - dpps.add(new DisjointPathPair<V, E>(shortPath, null)); - continue; - } - - for (Path p2: secondDijkstra.paths()) { - residualShortPath = p2; - - MutableGraph<V, E> roundTrip = mutableCopy(graph); - - List<E> tmp = roundTrip.getEdges().stream().collect(Collectors.toList()); - - tmp.forEach(roundTrip::removeEdge); - - shortPath.edges().forEach(roundTrip::addEdge); - - if (residualShortPath != null) { - for (Edge<V> edge: residualShortPath.edges()) { - if (classE().isInstance(edge)) { - roundTrip.addEdge((E) edge); - } else { - roundTrip.removeEdge(revToEdge.get(edge)); - } - } - } - //Actually build the final result - DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS); - Path<V, E> path1 = lastSearch.paths().iterator().next(); - path1.edges().forEach(roundTrip::removeEdge); - - Set<Path<V, E>> bckpaths = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths(); - Path<V, E> backup = null; - if (bckpaths.size() != 0) { - backup = bckpaths.iterator().next(); - } - - dpps.add(new DisjointPathPair<>(path1, backup)); - } - } - - for (int i = dpps.size() - 1; i > 0; i--) { - if (dpps.get(i).size() <= 1) { - dpps.remove(i); - } - } - - return new Result<V, E>() { - final DefaultResult search = firstDijkstra; - - public V src() { - return src; - } - public V dst() { - return dst; - } - public Set<Path<V, E>> paths() { - Set<Path<V, E>> pathsD = new HashSet<>(); - int paths = 0; - for (DisjointPathPair<V, E> path: dpps) { - pathsD.add((Path<V, E>) path); - paths++; - if (paths == maxPaths) { - break; - } - } - return pathsD; - } - public Map<V, Double> costs() { - return search.costs(); - } - public Map<V, Set<E>> parents() { - return search.parents(); - } - }; - } - - private Class<?> clazzV; - - public Class<?> classV() { - return clazzV; - } - - private Class<?> clazzE; - - public Class<?> classE() { - return clazzE; - } - /** - * Creates a mutable copy of an immutable graph. - * - * @param graph immutable graph - * @return mutable copy - */ - public MutableGraph mutableCopy(Graph<V, E> graph) { - clazzV = graph.getVertexes().iterator().next().getClass(); - clazzE = graph.getEdges().iterator().next().getClass(); - return new MutableAdjacencyListsGraph<V, E>(graph.getVertexes(), graph.getEdges()); - } -} - diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java deleted file mode 100644 index 1c436d94..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java +++ /dev/null @@ -1,212 +0,0 @@ -/* - * Copyright 2014 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.Collections; -import java.util.HashMap; -import java.util.HashSet; -import java.util.List; -import java.util.Map; -import java.util.Set; - -/** - * Tarjan algorithm for searching a graph and producing results describing - * the graph SCC (strongly-connected components). - */ -public class TarjanGraphSearch<V extends Vertex, E extends Edge<V>> - implements GraphSearch<V, E> { - - /** - * {@inheritDoc} - * <p> - * This implementation produces results augmented with information on - * SCCs within the graph. - * </p> - * <p> - * To prevent traversal of an edge, the {@link EdgeWeight#weight} should - * return a negative value as an edge weight. - * </p> - */ - @Override - public SccResult<V, E> search(Graph<V, E> graph, EdgeWeight<V, E> weight) { - SccResult<V, E> result = new SccResult<>(graph); - for (V vertex : graph.getVertexes()) { - VertexData data = result.data(vertex); - if (data == null) { - connect(graph, vertex, weight, result); - } - } - return result.build(); - } - - /** - * Scans the specified graph, using recursion, and produces SCC results. - * - * @param graph graph to search - * @param vertex current vertex to scan and connect - * @param weight optional edge weight - * @param result graph search result - * @return augmentation vertexData for the current vertex - */ - private VertexData<V> connect(Graph<V, E> graph, V vertex, - EdgeWeight<V, E> weight, - SccResult<V, E> result) { - VertexData<V> data = result.addData(vertex); - - // Scan through all egress edges of the current vertex. - for (E edge : graph.getEdgesFrom(vertex)) { - V nextVertex = edge.dst(); - - // If edge weight is negative, skip it. - if (weight != null && weight.weight(edge) < 0) { - continue; - } - - // Attempt to get the augmentation vertexData for the next vertex. - VertexData<V> nextData = result.data(nextVertex); - if (nextData == null) { - // Next vertex has not been visited yet, so do this now. - nextData = connect(graph, nextVertex, weight, result); - data.lowLink = Math.min(data.lowLink, nextData.lowLink); - - } else if (result.visited(nextData)) { - // Next vertex has been visited, which means it is in the - // same cluster as the current vertex. - data.lowLink = Math.min(data.lowLink, nextData.index); - } - } - - if (data.lowLink == data.index) { - result.addCluster(data); - } - return data; - } - - /** - * Graph search result augmented with SCC vertexData. - */ - public static final class SccResult<V extends Vertex, E extends Edge<V>> - implements Result { - - private final Graph<V, E> graph; - private List<Set<V>> clusterVertexes = new ArrayList<>(); - private List<Set<E>> clusterEdges = new ArrayList<>(); - - private int index = 0; - private final Map<V, VertexData<V>> vertexData = new HashMap<>(); - private final List<VertexData<V>> visited = new ArrayList<>(); - - private SccResult(Graph<V, E> graph) { - this.graph = graph; - } - - /** - * Returns the number of SCC clusters in the graph. - * - * @return number of clusters - */ - public int clusterCount() { - return clusterEdges.size(); - } - - /** - * Returns the list of strongly connected vertex clusters. - * - * @return list of strongly connected vertex sets - */ - public List<Set<V>> clusterVertexes() { - return clusterVertexes; - } - - /** - * Returns the list of edges linking strongly connected vertex clusters. - * - * @return list of strongly connected edge sets - */ - public List<Set<E>> clusterEdges() { - return clusterEdges; - } - - // Gets the augmentation vertexData for the specified vertex - private VertexData<V> data(V vertex) { - return vertexData.get(vertex); - } - - // Adds augmentation vertexData for the specified vertex - private VertexData<V> addData(V vertex) { - VertexData<V> d = new VertexData<>(vertex, index); - vertexData.put(vertex, d); - visited.add(0, d); - index++; - return d; - } - - // Indicates whether the given vertex has been visited - private boolean visited(VertexData data) { - return visited.contains(data); - } - - // Adds a new cluster for the specified vertex - private void addCluster(VertexData data) { - Set<V> vertexes = findClusterVertices(data); - clusterVertexes.add(vertexes); - clusterEdges.add(findClusterEdges(vertexes)); - } - - private Set<V> findClusterVertices(VertexData data) { - VertexData<V> nextVertexData; - Set<V> vertexes = new HashSet<>(); - do { - nextVertexData = visited.remove(0); - vertexes.add(nextVertexData.vertex); - } while (data != nextVertexData); - return Collections.unmodifiableSet(vertexes); - } - - private Set<E> findClusterEdges(Set<V> vertexes) { - Set<E> edges = new HashSet<>(); - for (V vertex : vertexes) { - for (E edge : graph.getEdgesFrom(vertex)) { - if (vertexes.contains((edge.dst()))) { - edges.add(edge); - } - } - } - return Collections.unmodifiableSet(edges); - } - - public SccResult<V, E> build() { - clusterVertexes = Collections.unmodifiableList(clusterVertexes); - clusterEdges = Collections.unmodifiableList(clusterEdges); - return this; - } - } - - // Augments the vertex to assist in determining SCC clusters. - private static final class VertexData<V extends Vertex> { - final V vertex; - int index; - int lowLink; - - private VertexData(V vertex, int index) { - this.vertex = vertex; - this.index = index; - this.lowLink = index; - } - } - -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Vertex.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Vertex.java deleted file mode 100644 index 80e3e7df..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/Vertex.java +++ /dev/null @@ -1,22 +0,0 @@ -/* - * Copyright 2014 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; - -/** - * Representation of a graph vertex. - */ -public interface Vertex { -} diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/package-info.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/package-info.java deleted file mode 100644 index 2ee949d2..00000000 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/package-info.java +++ /dev/null @@ -1,20 +0,0 @@ -/* - * Copyright 2014 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. - */ - -/** - * Graph abstractions and graph path finding algorithms. - */ -package org.onlab.graph; |