ms/controllerblueprints/modules/core/src/main/kotlin/org/onap/ccsdk/apps/controllerblueprints/core/utils/TopologicalSortingUtils.kt

   1 /*\r
   2  * Copyright © 2017-2018 AT&T Intellectual Property.\r
   3  *\r
   4  * Licensed under the Apache License, Version 2.0 (the "License");\r
   5  * you may not use this file except in compliance with the License.\r
   6  * You may obtain a copy of the License at\r
   7  *\r
   8  *     http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  * Unless required by applicable law or agreed to in writing, software\r
  11  * distributed under the License is distributed on an "AS IS" BASIS,\r
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  * See the License for the specific language governing permissions and\r
  14  * limitations under the License.\r
  15  */\r
  16 \r
  17 package org.onap.ccsdk.apps.controllerblueprints.core.utils\r
  18 \r
  19 import java.util.*\r
  20 \r
  21 /**\r
  22  *\r
  23  *\r
  24  * @author Brinda Santh\r
  25  */\r
  26 class TopologicalSortingUtils<V> {\r
  27 \r
  28     private val neighbors: MutableMap<V, MutableList<V>> = hashMapOf()\r
  29 \r
  30     val isDag: Boolean\r
  31         get() = topSort() != null\r
  32 \r
  33     override fun toString(): String {\r
  34         val s = StringBuffer()\r
  35         for (v in neighbors.keys)\r
  36             s.append("\n    " + v + " -> " + neighbors[v])\r
  37         return s.toString()\r
  38     }\r
  39 \r
  40     fun getNeighbors(): Map<V, List<V>> {\r
  41         return neighbors\r
  42     }\r
  43 \r
  44     fun add(vertex: V) {\r
  45         if (neighbors.containsKey(vertex))\r
  46             return\r
  47         neighbors[vertex] = arrayListOf()\r
  48     }\r
  49 \r
  50     operator fun contains(vertex: V): Boolean {\r
  51         return neighbors.containsKey(vertex)\r
  52     }\r
  53 \r
  54     fun add(from: V, to: V) {\r
  55         this.add(from)\r
  56         this.add(to)\r
  57         neighbors[from]?.add(to)\r
  58     }\r
  59 \r
  60     fun remove(from: V, to: V) {\r
  61         if (!(this.contains(from) && this.contains(to)))\r
  62             throw IllegalArgumentException("Nonexistent vertex")\r
  63         neighbors[from]?.remove(to)\r
  64     }\r
  65 \r
  66     fun outDegree(): Map<V, Int> {\r
  67         var result: MutableMap<V, Int> = hashMapOf()\r
  68         for (v in neighbors.keys)\r
  69             result[v] = neighbors[v]!!.size\r
  70         return result\r
  71     }\r
  72 \r
  73 \r
  74     fun inDegree(): MutableMap<V, Int> {\r
  75         val result = HashMap<V, Int>()\r
  76         for (v in neighbors.keys)\r
  77             result[v] = 0       // All in-degrees are 0\r
  78         for (from in neighbors.keys) {\r
  79             for (to in neighbors[from]!!) {\r
  80                 result[to] = result[to]!! + 1           // Increment in-degree\r
  81             }\r
  82         }\r
  83         return result\r
  84     }\r
  85 \r
  86     fun topSort(): List<V>? {\r
  87         val degree = inDegree()\r
  88         // Determine all vertices with zero in-degree\r
  89         val zeroVerts = Stack<V>()        // Stack as good as any here\r
  90         for (v in degree.keys) {\r
  91             if (degree[v] == 0) zeroVerts.push(v)\r
  92         }\r
  93         // Determine the topological order\r
  94         val result = ArrayList<V>()\r
  95         while (!zeroVerts.isEmpty()) {\r
  96             val v = zeroVerts.pop()                  // Choose a vertex with zero in-degree\r
  97             result.add(v)                          // Vertex v is next in topol order\r
  98             // "Remove" vertex v by updating its neighbors\r
  99             for (neighbor in neighbors[v]!!) {\r
 100                 degree[neighbor] = degree[neighbor]!! - 1\r
 101                 // Remember any vertices that now have zero in-degree\r
 102                 if (degree[neighbor] == 0) zeroVerts.push(neighbor)\r
 103             }\r
 104         }\r
 105         // Check that we have used the entire graph (if not, there was a cycle)\r
 106         return if (result.size != neighbors.size) null else result\r
 107     }\r
 108 \r
 109 \r
 110     fun bfsDistance(start: V): Map<*, *> {\r
 111         var distance: MutableMap<V, Int> = hashMapOf()\r
 112         // Initially, all distance are infinity, except start node\r
 113         for (v in neighbors.keys)\r
 114             distance[v] = -1\r
 115         distance[start] = 0\r
 116         // Process nodes in queue order\r
 117         val queue = LinkedList<V>()\r
 118         queue.offer(start)                                    // Place start node in queue\r
 119         while (!queue.isEmpty()) {\r
 120             val v = queue.remove()\r
 121             val vDist = distance[v]!!\r
 122             // Update neighbors\r
 123             for (neighbor in neighbors[v]!!) {\r
 124                 if (distance[neighbor] != null) continue  // Ignore if already done\r
 125                 distance[neighbor] = vDist + 1\r
 126                 queue.offer(neighbor)\r
 127             }\r
 128         }\r
 129         return distance\r
 130     }\r
 131 }