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.ArrayList
  20 import java.util.HashMap
  21 import java.util.LinkedList
  22 import java.util.Stack
  23
  24 /**
  25  *
  26  *
  27  * @author Brinda Santh
  28  */
  29 class TopologicalSortingUtils<V> {
  30
  31     private val neighbors: MutableMap<V, MutableList<V>> = hashMapOf()
  32
  33     val isDag: Boolean
  34         get() = topSort() != null
  35
  36     override fun toString(): String {
  37         val s = StringBuffer()
  38         for (v in neighbors.keys)
  39             s.append("\n    " + v + " -> " + neighbors[v])
  40         return s.toString()
  41     }
  42
  43     fun getNeighbors(): Map<V, List<V>> {
  44         return neighbors
  45     }
  46
  47     fun add(vertex: V) {
  48         if (neighbors.containsKey(vertex))
  49             return
  50         neighbors[vertex] = arrayListOf()
  51     }
  52
  53     operator fun contains(vertex: V): Boolean {
  54         return neighbors.containsKey(vertex)
  55     }
  56
  57     fun add(from: V, to: V) {
  58         this.add(from)
  59         this.add(to)
  60         neighbors[from]?.add(to)
  61     }
  62
  63     fun remove(from: V, to: V) {
  64         if (!(this.contains(from) && this.contains(to)))
  65             throw IllegalArgumentException("Nonexistent vertex")
  66         neighbors[from]?.remove(to)
  67     }
  68
  69     fun outDegree(): Map<V, Int> {
  70         val result: MutableMap<V, Int> = hashMapOf()
  71         for (v in neighbors.keys)
  72             result[v] = neighbors[v]!!.size
  73         return result
  74     }
  75
  76     fun inDegree(): MutableMap<V, Int> {
  77         val result = HashMap<V, Int>()
  78         for (v in neighbors.keys)
  79             result[v] = 0 // All in-degrees are 0
  80         for (from in neighbors.keys) {
  81             for (to in neighbors[from]!!) {
  82                 result[to] = result[to]!! + 1 // Increment in-degree
  83             }
  84         }
  85         return result
  86     }
  87
  88     fun topSort(): List<V>? {
  89         val degree = inDegree()
  90         // Determine all vertices with zero in-degree
  91         val zeroVerts = Stack<V>() // Stack as good as any here
  92         for (v in degree.keys) {
  93             if (degree[v] == 0) zeroVerts.push(v)
  94         }
  95         // Determine the topological order
  96         val result = ArrayList<V>()
  97         while (!zeroVerts.isEmpty()) {
  98             val v = zeroVerts.pop() // Choose a vertex with zero in-degree
  99             result.add(v) // Vertex v is next in topol order
 100             // "Remove" vertex v by updating its neighbors
 101             for (neighbor in neighbors[v]!!) {
 102                 degree[neighbor] = degree[neighbor]!! - 1
 103                 // Remember any vertices that now have zero in-degree
 104                 if (degree[neighbor] == 0) zeroVerts.push(neighbor)
 105             }
 106         }
 107         // Check that we have used the entire graph (if not, there was a cycle)
 108         return if (result.size != neighbors.size) null else result
 109     }
 110
 111     fun bfsDistance(start: V): Map<*, *> {
 112         val distance: MutableMap<V, Int> = hashMapOf()
 113         // Initially, all distance are infinity, except start node
 114         for (v in neighbors.keys)
 115             distance[v] = -1
 116         distance[start] = 0
 117         // Process nodes in queue order
 118         val queue = LinkedList<V>()
 119         queue.offer(start) // Place start node in queue
 120         while (!queue.isEmpty()) {
 121             val v = queue.remove()
 122             val vDist = distance[v]!!
 123             // Update neighbors
 124             for (neighbor in neighbors[v]!!) {
 125                 if (distance[neighbor] != null) continue // Ignore if already done
 126                 distance[neighbor] = vDist + 1
 127                 queue.offer(neighbor)
 128             }
 129         }
 130         return distance
 131     }
 132 }