diff options
Diffstat (limited to 'framework/src/onos/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java')
| -rw-r--r-- | framework/src/onos/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java | 212 |
1 files changed, 212 insertions, 0 deletions
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 new file mode 100644 index 00000000..5bf305e6 --- /dev/null +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/TarjanGraphSearch.java @@ -0,0 +1,212 @@ +/* + * 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; + } + } + +} |