+++ /dev/null
-/*\r
- * Copyright © 2017-2018 AT&T Intellectual Property.\r
- * Modifications Copyright © 2018 IBM.\r
- * \r
- * Licensed under the Apache License, Version 2.0 (the "License");\r
- * you may not use this file except in compliance with the License.\r
- * You may obtain a copy of the License at\r
- * \r
- * http://www.apache.org/licenses/LICENSE-2.0\r
- * \r
- * Unless required by applicable law or agreed to in writing, software\r
- * distributed under the License is distributed on an "AS IS" BASIS,\r
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
- * See the License for the specific language governing permissions and\r
- * limitations under the License.\r
- */\r
-\r
-package org.onap.ccsdk.features.model.utils;\r
-\r
-import java.util.ArrayList;\r
-import java.util.HashMap;\r
-import java.util.LinkedList;\r
-import java.util.List;\r
-import java.util.Map;\r
-import java.util.Queue;\r
-import java.util.Stack;\r
-\r
-public class TopologicalSortingUtils<V> {\r
-\r
- /**\r
- * The implementation here is basically an adjacency list, but instead of an array of lists, a Map\r
- * is used to map each vertex to its list of adjacent vertices.\r
- */\r
- private Map<V, List<V>> neighbors = new HashMap<>();\r
-\r
- /**\r
- * String representation of graph.\r
- */\r
- @Override\r
- public String toString() {\r
- StringBuilder s = new StringBuilder();\r
- neighbors.forEach((v, vs) -> s.append("\n " + v + " -> " + vs));\r
- return s.toString();\r
- }\r
-\r
- public Map<V, List<V>> getNeighbors() {\r
- return neighbors;\r
- }\r
-\r
- /**\r
- * Add a vertex to the graph. Nothing happens if vertex is already in graph.\r
- */\r
- public void add(V vertex) {\r
- if (neighbors.containsKey(vertex))\r
- return;\r
- neighbors.put(vertex, new ArrayList<V>());\r
- }\r
-\r
- /**\r
- * True iff graph contains vertex.\r
- */\r
- public boolean contains(V vertex) {\r
- return neighbors.containsKey(vertex);\r
- }\r
-\r
- /**\r
- * Add an edge to the graph; if either vertex does not exist, it's added. This implementation allows\r
- * the creation of multi-edges and self-loops.\r
- */\r
- public void add(V from, V to) {\r
- this.add(from);\r
- this.add(to);\r
- neighbors.get(from).add(to);\r
- }\r
-\r
- /**\r
- * Remove an edge from the graph. Nothing happens if no such edge.\r
- *\r
- * @throws IllegalArgumentException if either vertex doesn't exist.\r
- */\r
- public void remove(V from, V to) {\r
- if (!(this.contains(from) && this.contains(to)))\r
- throw new IllegalArgumentException("Nonexistent vertex");\r
- neighbors.get(from).remove(to);\r
- }\r
-\r
- /**\r
- * Report (as a Map) the out-degree of each vertex.\r
- */\r
- public Map<V, Integer> outDegree() {\r
- Map<V, Integer> result = new HashMap<>();\r
- neighbors.forEach((v, vs) -> result.put(v, vs.size()));\r
- return result;\r
- }\r
-\r
- /**\r
- * Report (as a Map) the in-degree of each vertex.\r
- */\r
- public Map<V, Integer> inDegree() {\r
- Map<V, Integer> result = new HashMap<>();\r
- for (V v : neighbors.keySet())\r
- result.put(v, 0); // All in-degrees are 0\r
-\r
- neighbors.forEach((from, vs) -> vs.forEach(to -> result.put(to, result.get(to) + 1) // Increment in-degree\r
- ));\r
-\r
- return result;\r
- }\r
-\r
- /**\r
- * Report (as a List) the topological sort of the vertices; null for no such sort.\r
- */\r
- @SuppressWarnings({"squid:S1149", "squid:S1168"})\r
- public List<V> topSort() {\r
- Map<V, Integer> degree = inDegree();\r
- // Determine all vertices with zero in-degree\r
- Stack<V> zeroVerts = new Stack<>(); // Stack as good as any here\r
-\r
- degree.forEach((v, vs) -> {\r
- if (vs == 0)\r
- zeroVerts.push(v);\r
- });\r
-\r
- // Determine the topological order\r
- List<V> result = new ArrayList<>();\r
- while (!zeroVerts.isEmpty()) {\r
- V v = zeroVerts.pop(); // Choose a vertex with zero in-degree\r
- result.add(v); // Vertex v is next in topol order\r
- // "Remove" vertex v by updating its neighbors\r
- for (V neighbor : neighbors.get(v)) {\r
- degree.put(neighbor, degree.get(neighbor) - 1);\r
- // Remember any vertices that now have zero in-degree\r
- if (degree.get(neighbor) == 0)\r
- zeroVerts.push(neighbor);\r
- }\r
- }\r
- // Check that we have used the entire graph (if not, there was a cycle)\r
- if (result.size() != neighbors.size())\r
- return null;\r
- return result;\r
- }\r
-\r
- /**\r
- * True iff graph is a dag (directed acyclic graph).\r
- */\r
- public boolean isDag() {\r
- return topSort() != null;\r
- }\r
-\r
- /**\r
- * Report (as a Map) the bfs distance to each vertex from the start vertex. The distance is an\r
- * Integer; the value null is used to represent infinity (implying that the corresponding node\r
- * cannot be reached).\r
- */\r
- public Map bfsDistance(V start) {\r
- Map<V, Integer> distance = new HashMap<>();\r
- // Initially, all distance are infinity, except start node\r
- for (V v : neighbors.keySet())\r
- distance.put(v, null);\r
- distance.put(start, 0);\r
- // Process nodes in queue order\r
- Queue<V> queue = new LinkedList<>();\r
- queue.offer(start); // Place start node in queue\r
- while (!queue.isEmpty()) {\r
- V v = queue.remove();\r
- int vDist = distance.get(v);\r
- // Update neighbors\r
- for (V neighbor : neighbors.get(v)) {\r
- if (distance.get(neighbor) != null)\r
- continue; // Ignore if already done\r
- distance.put(neighbor, vDist + 1);\r
- queue.offer(neighbor);\r
- }\r
- }\r
- return distance;\r
- }\r
-\r
- /**\r
- * Main program (for testing). public static void main (String[] args) { // Create a Graph with\r
- * Integer nodes TopologicalSortingUtils<String> graph = new TopologicalSortingUtils<String>();\r
- * graph.add("bundle-id", "bundle-mac"); graph.add("bundle-id", "bundle-ip");\r
- * graph.add("bundle-mac", "bundle-ip"); graph.add("bundle-ip", "bundle-mac");\r
- * System.out.println("The current graph: " + graph); System.out.println("In-degrees: " +\r
- * graph.inDegree()); System.out.println("Out-degrees: " + graph.outDegree()); System.out.println("A\r
- * topological sort of the vertices: " + graph.topSort()); System.out.println("The graph " +\r
- * (graph.isDag()?"is":"is not") + " a dag"); }\r
- */\r
-}\r
Code Review / ccsdk / features.git / blobdiff