ms/controllerblueprints/modules/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/utils/TopologicalSortingUtils.kt

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