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

   1 /*
   2  *  Copyright © 2019 IBM.
   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
  18
  19 import org.onap.ccsdk.cds.controllerblueprints.core.data.EdgeLabel
  20 import org.onap.ccsdk.cds.controllerblueprints.core.data.Graph
  21 import org.onap.ccsdk.cds.controllerblueprints.core.data.Workflow
  22 import org.onap.ccsdk.cds.controllerblueprints.core.utils.WorkflowGraphUtils
  23 import java.util.regex.Pattern
  24
  25 private val graphTokenSeparators = Pattern.compile("[->/]")
  26
  27 /** Convert Blueprint workflow to graph data structure */
  28 fun Workflow.asGraph(): Graph {
  29     return WorkflowGraphUtils.workFlowToGraph(this)
  30 }
  31
  32 fun String.toGraph(): Graph {
  33     if (!startsWith('[') || !endsWith(']')) {
  34         throw IllegalArgumentException("Expected string starting '[' and ending with ']' but it was '$")
  35     }
  36     val tokens = substring(1, length - 1).split(", ").map { it.split(graphTokenSeparators) }
  37     val nodes = tokens.flatMap { it.take(2) }.toCollection(LinkedHashSet())
  38     val edges = tokens.filter { it.size == 3 }.map { Graph.TermForm.Term(it[0], it[1], EdgeLabel.valueOf(it[2])) }
  39     return Graph.labeledDirectedTerms(Graph.TermForm(nodes, edges))
  40 }
  41
  42 fun Graph.toAdjacencyList(): Graph.AdjacencyList<String, EdgeLabel> {
  43     val entries = nodes.values.map { node ->
  44         val links = node.edges.map { Graph.AdjacencyList.Link(it.target(node).id, it.label) }
  45         Graph.AdjacencyList.Entry(node = node.id, links = links)
  46     }
  47     return Graph.AdjacencyList(entries)
  48 }
  49
  50 fun Graph.findAllPaths(from: String, to: String, path: List<String> = emptyList()): List<List<String>> {
  51     if (from == to) return listOf(path + to)
  52     return nodes[from]!!.neighbors()
  53         .filter { !path.contains(it.id) }
  54         .flatMap { findAllPaths(it.id, to, path + from) }
  55 }
  56
  57 fun Graph.findCycles(node: String): List<List<String>> {
  58     fun findCycles(path: List<String>): List<List<String>> {
  59         if (path.size > 3 && path.first() == path.last()) return listOf(path)
  60         return nodes[path.last()]!!.neighbors()
  61             .filterNot { path.tail().contains(it.id) }
  62             .flatMap { findCycles(path + it.id) }
  63     }
  64     return findCycles(listOf(node))
  65 }
  66
  67 fun Graph.startNodes() = this.nodes.values.filter {
  68     val incomingEdges = incomingEdges(it.id)
  69     incomingEdges.isEmpty()
  70 }
  71
  72 fun Graph.endNodes(): Set<Graph.Node> = this.nodes.values.filter {
  73     outgoingEdges(it.id).isEmpty()
  74 }.toSet()
  75
  76 fun Graph.node(node: String) = this.nodes[node]
  77
  78 fun Graph.edge(label: EdgeLabel) =
  79     this.edges.filter { it.label == label }
  80
  81 fun Graph.incomingEdges(node: String) =
  82     this.edges.filter { it.target.id == node }
  83
  84 fun Graph.incomingNodes(node: String) =
  85     this.incomingEdges(node).map { it.source }
  86
  87 fun Graph.outgoingEdges(node: String) =
  88     this.edges.filter { it.source.id == node }
  89
  90 fun Graph.outgoingNodes(node: String) =
  91     this.outgoingEdges(node).map { it.target }
  92
  93 fun Graph.outgoingEdges(node: String, label: EdgeLabel) =
  94     this.edges.filter { it.source.id == node && it.label == label }
  95
  96 fun Graph.outgoingNodes(node: String, label: EdgeLabel) =
  97     this.outgoingEdges(node, label).map { it.target }
  98
  99 fun Graph.outgoingNodesNotInEdgeLabels(node: String, labels: List<EdgeLabel>) =
 100     this.outgoingEdgesNotInLabels(node, labels).map { it.target }
 101
 102 fun Graph.outgoingEdges(node: String, labels: List<EdgeLabel>) =
 103     this.edges.filter { it.source.id == node && labels.contains(it.label) }
 104
 105 fun Graph.outgoingEdgesNotInLabels(node: String, labels: List<EdgeLabel>) =
 106     this.edges.filter { it.source.id == node && !labels.contains(it.label) }
 107
 108 fun Graph.outgoingNodes(node: String, labels: List<EdgeLabel>) =
 109     this.outgoingEdges(node, labels).map { it.target }
 110
 111 fun Graph.isEndNode(node: Graph.Node): Boolean {
 112     return this.endNodes().contains(node)
 113 }
 114
 115 fun <T> List<T>.tail(): List<T> = drop(1)