gerrit.onap Code Review - ccsdk/cds.git/blob

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