2 * Copyright © 2017-2018 AT&T Intellectual Property.
\r
3 * Modifications Copyright © 2018 IBM.
\r
5 * Licensed under the Apache License, Version 2.0 (the "License");
\r
6 * you may not use this file except in compliance with the License.
\r
7 * You may obtain a copy of the License at
\r
9 * http://www.apache.org/licenses/LICENSE-2.0
\r
11 * Unless required by applicable law or agreed to in writing, software
\r
12 * distributed under the License is distributed on an "AS IS" BASIS,
\r
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
\r
14 * See the License for the specific language governing permissions and
\r
15 * limitations under the License.
\r
18 package org.onap.ccsdk.features.model.utils;
\r
20 import java.util.ArrayList;
\r
21 import java.util.HashMap;
\r
22 import java.util.LinkedList;
\r
23 import java.util.List;
\r
24 import java.util.Map;
\r
25 import java.util.Queue;
\r
26 import java.util.Stack;
\r
28 public class TopologicalSortingUtils<V> {
\r
31 * The implementation here is basically an adjacency list, but instead of an array of lists, a Map
\r
32 * is used to map each vertex to its list of adjacent vertices.
\r
34 private Map<V, List<V>> neighbors = new HashMap<>();
\r
37 * String representation of graph.
\r
40 public String toString() {
\r
41 StringBuilder s = new StringBuilder();
\r
42 neighbors.forEach((v, vs) -> s.append("\n " + v + " -> " + vs));
\r
43 return s.toString();
\r
46 public Map<V, List<V>> getNeighbors() {
\r
51 * Add a vertex to the graph. Nothing happens if vertex is already in graph.
\r
53 public void add(V vertex) {
\r
54 if (neighbors.containsKey(vertex))
\r
56 neighbors.put(vertex, new ArrayList<V>());
\r
60 * True iff graph contains vertex.
\r
62 public boolean contains(V vertex) {
\r
63 return neighbors.containsKey(vertex);
\r
67 * Add an edge to the graph; if either vertex does not exist, it's added. This implementation allows
\r
68 * the creation of multi-edges and self-loops.
\r
70 public void add(V from, V to) {
\r
73 neighbors.get(from).add(to);
\r
77 * Remove an edge from the graph. Nothing happens if no such edge.
\r
79 * @throws IllegalArgumentException if either vertex doesn't exist.
\r
81 public void remove(V from, V to) {
\r
82 if (!(this.contains(from) && this.contains(to)))
\r
83 throw new IllegalArgumentException("Nonexistent vertex");
\r
84 neighbors.get(from).remove(to);
\r
88 * Report (as a Map) the out-degree of each vertex.
\r
90 public Map<V, Integer> outDegree() {
\r
91 Map<V, Integer> result = new HashMap<>();
\r
92 neighbors.forEach((v, vs) -> result.put(v, vs.size()));
\r
97 * Report (as a Map) the in-degree of each vertex.
\r
99 public Map<V, Integer> inDegree() {
\r
100 Map<V, Integer> result = new HashMap<>();
\r
101 for (V v : neighbors.keySet())
\r
102 result.put(v, 0); // All in-degrees are 0
\r
104 neighbors.forEach((from, vs) -> vs.forEach(to -> result.put(to, result.get(to) + 1) // Increment in-degree
\r
111 * Report (as a List) the topological sort of the vertices; null for no such sort.
\r
113 @SuppressWarnings({"squid:S1149", "squid:S1168"})
\r
114 public List<V> topSort() {
\r
115 Map<V, Integer> degree = inDegree();
\r
116 // Determine all vertices with zero in-degree
\r
117 Stack<V> zeroVerts = new Stack<>(); // Stack as good as any here
\r
119 degree.forEach((v, vs) -> {
\r
124 // Determine the topological order
\r
125 List<V> result = new ArrayList<>();
\r
126 while (!zeroVerts.isEmpty()) {
\r
127 V v = zeroVerts.pop(); // Choose a vertex with zero in-degree
\r
128 result.add(v); // Vertex v is next in topol order
\r
129 // "Remove" vertex v by updating its neighbors
\r
130 for (V neighbor : neighbors.get(v)) {
\r
131 degree.put(neighbor, degree.get(neighbor) - 1);
\r
132 // Remember any vertices that now have zero in-degree
\r
133 if (degree.get(neighbor) == 0)
\r
134 zeroVerts.push(neighbor);
\r
137 // Check that we have used the entire graph (if not, there was a cycle)
\r
138 if (result.size() != neighbors.size())
\r
144 * True iff graph is a dag (directed acyclic graph).
\r
146 public boolean isDag() {
\r
147 return topSort() != null;
\r
151 * Report (as a Map) the bfs distance to each vertex from the start vertex. The distance is an
\r
152 * Integer; the value null is used to represent infinity (implying that the corresponding node
\r
153 * cannot be reached).
\r
155 public Map bfsDistance(V start) {
\r
156 Map<V, Integer> distance = new HashMap<>();
\r
157 // Initially, all distance are infinity, except start node
\r
158 for (V v : neighbors.keySet())
\r
159 distance.put(v, null);
\r
160 distance.put(start, 0);
\r
161 // Process nodes in queue order
\r
162 Queue<V> queue = new LinkedList<>();
\r
163 queue.offer(start); // Place start node in queue
\r
164 while (!queue.isEmpty()) {
\r
165 V v = queue.remove();
\r
166 int vDist = distance.get(v);
\r
167 // Update neighbors
\r
168 for (V neighbor : neighbors.get(v)) {
\r
169 if (distance.get(neighbor) != null)
\r
170 continue; // Ignore if already done
\r
171 distance.put(neighbor, vDist + 1);
\r
172 queue.offer(neighbor);
\r
179 * Main program (for testing). public static void main (String[] args) { // Create a Graph with
\r
180 * Integer nodes TopologicalSortingUtils<String> graph = new TopologicalSortingUtils<String>();
\r
181 * graph.add("bundle-id", "bundle-mac"); graph.add("bundle-id", "bundle-ip");
\r
182 * graph.add("bundle-mac", "bundle-ip"); graph.add("bundle-ip", "bundle-mac");
\r
183 * System.out.println("The current graph: " + graph); System.out.println("In-degrees: " +
\r
184 * graph.inDegree()); System.out.println("Out-degrees: " + graph.outDegree()); System.out.println("A
\r
185 * topological sort of the vertices: " + graph.topSort()); System.out.println("The graph " +
\r
186 * (graph.isDag()?"is":"is not") + " a dag"); }
\r