blueprints-processor/plugin/model-provider/src/main/java/org/onap/ccsdk/config/model/utils/TopologicalSortingUtils.java

   1 /*\r
   2  * Copyright © 2017-2018 AT&T Intellectual Property.\r
   3  * Modifications Copyright © 2018 IBM.\r
   4  * \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
   8  * \r
   9  * http://www.apache.org/licenses/LICENSE-2.0\r
  10  * \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
  16  */\r
  17 \r
  18 package org.onap.ccsdk.config.model.utils;\r
  19 \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
  27 \r
  28 public class TopologicalSortingUtils<V> {\r
  29 \r
  30     /**\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
  33      */\r
  34     private Map<V, List<V>> neighbors = new HashMap<>();\r
  35 \r
  36     /**\r
  37      * String representation of graph.\r
  38      */\r
  39     @Override\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
  44     }\r
  45 \r
  46     public Map<V, List<V>> getNeighbors() {\r
  47         return neighbors;\r
  48     }\r
  49 \r
  50     /**\r
  51      * Add a vertex to the graph. Nothing happens if vertex is already in graph.\r
  52      */\r
  53     public void add(V vertex) {\r
  54         if (neighbors.containsKey(vertex))\r
  55             return;\r
  56         neighbors.put(vertex, new ArrayList<V>());\r
  57     }\r
  58 \r
  59     /**\r
  60      * True iff graph contains vertex.\r
  61      */\r
  62     public boolean contains(V vertex) {\r
  63         return neighbors.containsKey(vertex);\r
  64     }\r
  65 \r
  66     /**\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
  69      */\r
  70     public void add(V from, V to) {\r
  71         this.add(from);\r
  72         this.add(to);\r
  73         neighbors.get(from).add(to);\r
  74     }\r
  75 \r
  76     /**\r
  77      * Remove an edge from the graph. Nothing happens if no such edge.\r
  78      *\r
  79      * @throws IllegalArgumentException if either vertex doesn't exist.\r
  80      */\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
  85     }\r
  86 \r
  87     /**\r
  88      * Report (as a Map) the out-degree of each vertex.\r
  89      */\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
  93         return result;\r
  94     }\r
  95 \r
  96     /**\r
  97      * Report (as a Map) the in-degree of each vertex.\r
  98      */\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
 103 \r
 104         neighbors.forEach((from, vs) -> vs.forEach(to -> result.put(to, result.get(to) + 1) // Increment in-degree\r
 105         ));\r
 106 \r
 107         return result;\r
 108     }\r
 109 \r
 110     /**\r
 111      * Report (as a List) the topological sort of the vertices; null for no such sort.\r
 112      */\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
 118 \r
 119         degree.forEach((v, vs) -> {\r
 120             if (vs == 0)\r
 121                 zeroVerts.push(v);\r
 122         });\r
 123 \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
 135             }\r
 136         }\r
 137         // Check that we have used the entire graph (if not, there was a cycle)\r
 138         if (result.size() != neighbors.size())\r
 139             return null;\r
 140         return result;\r
 141     }\r
 142 \r
 143     /**\r
 144      * True iff graph is a dag (directed acyclic graph).\r
 145      */\r
 146     public boolean isDag() {\r
 147         return topSort() != null;\r
 148     }\r
 149 \r
 150     /**\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
 154      */\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
 173             }\r
 174         }\r
 175         return distance;\r
 176     }\r
 177 \r
 178     /**\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
 187      */\r
 188 }\r