2 * Copyright © 2017-2018 AT&T Intellectual Property.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package org.onap.ccsdk.cds.controllerblueprints.core.utils
19 import java.util.ArrayList
20 import java.util.HashMap
21 import java.util.LinkedList
22 import java.util.Stack
27 * @author Brinda Santh
29 class TopologicalSortingUtils<V> {
31 private val neighbors: MutableMap<V, MutableList<V>> = hashMapOf()
34 get() = topSort() != null
36 override fun toString(): String {
37 val s = StringBuffer()
38 for (v in neighbors.keys)
39 s.append("\n " + v + " -> " + neighbors[v])
43 fun getNeighbors(): Map<V, List<V>> {
48 if (neighbors.containsKey(vertex))
50 neighbors[vertex] = arrayListOf()
53 operator fun contains(vertex: V): Boolean {
54 return neighbors.containsKey(vertex)
57 fun add(from: V, to: V) {
60 neighbors[from]?.add(to)
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)
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
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
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)
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)
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
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)
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]!!
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)