Merge "Add blueprints graph models."

3 files changed, 320 insertions, 0 deletions

diff --git a/ms/controllerblueprints/modules/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctions.kt b/ms/controllerblueprints/modules/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctions.kt
new file mode 100644
index 000000000..235c48b66
--- /dev/null
+++ b/ms/controllerblueprints/modules/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctions.kt
@@ -0,0 +1,109 @@
+/*
+ *  Copyright © 2019 IBM.
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package org.onap.ccsdk.cds.controllerblueprints.core
+
+import org.onap.ccsdk.cds.controllerblueprints.core.data.EdgeLabel
+import org.onap.ccsdk.cds.controllerblueprints.core.data.Graph
+import java.util.regex.Pattern
+
+private val graphTokenSeparators = Pattern.compile("[->/]")
+
+fun String.toGraph(): Graph {
+    if (!startsWith('[') || !endsWith(']')) {
+        throw IllegalArgumentException("Expected string starting '[' and ending with ']' but it was '$")
+    }
+    val tokens = substring(1, length - 1).split(", ").map { it.split(graphTokenSeparators) }
+    val nodes = tokens.flatMap { it.take(2) }.toCollection(LinkedHashSet())
+    val edges = tokens.filter { it.size == 3 }.map { Graph.TermForm.Term(it[0], it[1], EdgeLabel.valueOf(it[2])) }
+    return Graph.labeledDirectedTerms(Graph.TermForm(nodes, edges))
+}
+
+fun Graph.toAdjacencyList(): Graph.AdjacencyList<String, EdgeLabel> {
+    val entries = nodes.values.map { node ->
+        val links = node.edges.map { Graph.AdjacencyList.Link(it.target(node).id, it.label) }
+        Graph.AdjacencyList.Entry(node = node.id, links = links)
+    }
+    return Graph.AdjacencyList(entries)
+}
+
+fun Graph.findAllPaths(from: String, to: String, path: List<String> = emptyList()): List<List<String>> {
+    if (from == to) return listOf(path + to)
+    return nodes[from]!!.neighbors()
+            .filter { !path.contains(it.id) }
+            .flatMap { findAllPaths(it.id, to, path + from) }
+}
+
+fun Graph.findCycles(node: String): List<List<String>> {
+    fun findCycles(path: List<String>): List<List<String>> {
+        if (path.size > 3 && path.first() == path.last()) return listOf(path)
+        return nodes[path.last()]!!.neighbors()
+                .filterNot { path.tail().contains(it.id) }
+                .flatMap { findCycles(path + it.id) }
+    }
+    return findCycles(listOf(node))
+}
+
+fun Graph.startNodes() = this.nodes.values.filter {
+    val incomingEdges = incomingEdges(it.id)
+    incomingEdges.isEmpty()
+}
+
+fun Graph.endNodes(): Set<Graph.Node> = this.nodes.values.filter {
+    outgoingEdges(it.id).isEmpty()
+}.toSet()
+
+fun Graph.node(node: String) = this.nodes[node]
+
+fun Graph.edge(label: EdgeLabel) =
+        this.edges.filter { it.label == label }
+
+fun Graph.incomingEdges(node: String) =
+        this.edges.filter { it.target.id == node }
+
+fun Graph.incomingNodes(node: String) =
+        this.incomingEdges(node).map { it.source }
+
+fun Graph.outgoingEdges(node: String) =
+        this.edges.filter { it.source.id == node }
+
+fun Graph.outgoingNodes(node: String) =
+        this.outgoingEdges(node).map { it.target }
+
+fun Graph.outgoingEdges(node: String, label: EdgeLabel) =
+        this.edges.filter { it.source.id == node && it.label == label }
+
+fun Graph.outgoingNodes(node: String, label: EdgeLabel) =
+        this.outgoingEdges(node, label).map { it.target }
+
+fun Graph.outgoingNodesNotInEdgeLabels(node: String, labels: List<EdgeLabel>) =
+        this.outgoingEdgesNotInLabels(node, labels).map { it.target }
+
+fun Graph.outgoingEdges(node: String, labels: List<EdgeLabel>) =
+        this.edges.filter { it.source.id == node && labels.contains(it.label) }
+
+fun Graph.outgoingEdgesNotInLabels(node: String, labels: List<EdgeLabel>) =
+        this.edges.filter { it.source.id == node && !labels.contains(it.label) }
+
+fun Graph.outgoingNodes(node: String, labels: List<EdgeLabel>) =
+        this.outgoingEdges(node, labels).map { it.target }
+
+fun Graph.isEndNode(node: Graph.Node): Boolean {
+    return this.endNodes().contains(node)
+}
+
+fun <T> List<T>.tail(): List<T> = drop(1)
+
diff --git a/ms/controllerblueprints/modules/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/data/BluePrintGraph.kt b/ms/controllerblueprints/modules/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/data/BluePrintGraph.kt
new file mode 100644
index 000000000..9e1b7498e
--- /dev/null
+++ b/ms/controllerblueprints/modules/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/data/BluePrintGraph.kt
@@ -0,0 +1,174 @@
+/*
+ *  Copyright © 2019 IBM.
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package org.onap.ccsdk.cds.controllerblueprints.core.data
+
+enum class EdgeLabel(val id: String) {
+    SUCCESS("success"),
+    FAILURE("failure"),
+    DEFAULT("*")
+}
+
+enum class EdgeStatus(val id: String) {
+    NOT_STARTED("not_started"),
+    EXECUTED("executed"),
+    SKIPPED("skipped")
+}
+
+enum class NodeStatus(val id: String) {
+    NOT_STARTED("not_started"),
+    READY("ready"),
+    EXECUTING("executing"),
+    EXECUTED("executed"),
+    SKIPPED("skipped")
+}
+
+class Graph {
+    val nodes: MutableMap<String, Node> = hashMapOf()
+    val edges: MutableSet<Edge> = mutableSetOf()
+
+    fun addNode(value: String): Node {
+        val node = Node(value)
+        nodes[value] = node
+        return node
+    }
+
+    fun addEdge(source: String, destination: String, label: EdgeLabel) {
+        if (!nodes.containsKey(source)) {
+            addNode(source)
+        }
+        if (!nodes.containsKey(destination)) {
+            addNode(destination)
+        }
+        val edge = Edge(nodes[source]!!, nodes[destination]!!, label)
+        if (!edges.contains(edge)) {
+            edges.add(edge)
+            nodes[source]!!.edges.add(edge)
+        }
+    }
+
+    override fun toString(): String {
+        val standaloneNodes = nodes.values.filter { node -> edges.all { it.source != node && it.target != node } }
+        val s = (edges.map { it.toString() } + standaloneNodes.map { it.toString() }).joinToString()
+        return "[$s]"
+    }
+
+    fun print(): String {
+        val buffer = StringBuffer("Nodes :")
+        nodes.values.forEach {
+            buffer.append("\n\t$it")
+        }
+        buffer.append("\nEdges :")
+        edges.forEach {
+            buffer.append("\n\t$it")
+        }
+        return buffer.toString()
+    }
+
+    override fun equals(other: Any?): Boolean {
+        if (this === other) return true
+        if (other?.javaClass != javaClass) return false
+        other as Graph
+        return nodes == other.nodes && edges == other.edges
+    }
+
+    override fun hashCode() = 31 * nodes.hashCode() + edges.hashCode()
+
+    fun equivalentTo(other: Graph): Boolean {
+        return nodes == other.nodes && edges.all { edge -> other.edges.any { it.equivalentTo(edge) } }
+    }
+
+    data class Node(val id: String, var status: NodeStatus = NodeStatus.NOT_STARTED) {
+        val edges: MutableList<Edge> = ArrayList()
+
+        fun neighbors(): List<Node> = edges.map { edge -> edge.target(this) }
+
+        fun neighbors(label: EdgeLabel): List<Node> = edges.filter { it.label == label }
+                .map { edge -> edge.target(this) }
+
+        fun labelEdges(label: EdgeLabel): List<Edge> = edges.filter { it.label == label }
+
+        override fun toString() = "$id, Status($status)"
+    }
+
+    data class Edge(
+            val source: Node,
+            val target: Node,
+            val label: EdgeLabel,
+            var status: EdgeStatus = EdgeStatus.NOT_STARTED) {
+
+        fun target(node: Node): Node = target
+
+        fun equivalentTo(other: Edge) =
+                (source == other.source && target == other.target)
+                        || (source == other.target && target == other.source)
+
+        override fun toString() =
+                "${source.id}>${target.id}/$label($status)"
+    }
+
+    data class TermForm(val nodes: Collection<String>, val edges: List<Term>) {
+
+        data class Term(val source: String, val target: String, val label: EdgeLabel) {
+            override fun toString() = "Term($source, $target, $label)"
+        }
+    }
+
+    data class AdjacencyList<String, out EdgeLabel>(val entries: List<Entry<String, EdgeLabel>>) {
+        constructor(vararg entries: Entry<String, EdgeLabel>) : this(entries.asList())
+
+        override fun toString() = "AdjacencyList(${entries.joinToString()})"
+
+        data class Entry<out String, out EdgeLabel>(val node: String, val links: List<Link<String, EdgeLabel>> = emptyList<Nothing>()) {
+            constructor(node: String, vararg links: Link<String, EdgeLabel>) : this(node, links.asList())
+
+            override fun toString() = "Entry($node, links[${links.joinToString()}])"
+        }
+
+        data class Link<out String, out EdgeLabel>(val node: String, val label: EdgeLabel) {
+            override fun toString() = if (label == null) "$node" else "$node/$label"
+        }
+    }
+
+    companion object {
+
+        fun labeledDirectedTerms(termForm: TermForm): Graph =
+                createFromTerms(termForm) { graph, n1, n2, value -> graph.addEdge(n1, n2, value) }
+
+        fun labeledDirectedAdjacent(adjacencyList: AdjacencyList<String, EdgeLabel>): Graph =
+                fromAdjacencyList(adjacencyList) { graph, n1, n2, value ->
+                    graph.addEdge(n1, n2, value)
+                }
+
+        private fun createFromTerms(termForm: TermForm,
+                                    addFunction: (Graph, String, String, EdgeLabel) -> Unit): Graph {
+            val graph = Graph()
+            termForm.nodes.forEach { graph.addNode(it) }
+            termForm.edges.forEach { addFunction(graph, it.source, it.target, it.label) }
+            return graph
+        }
+
+        private fun fromAdjacencyList(adjacencyList: AdjacencyList<String, EdgeLabel>,
+                                      addFunction: (Graph, String, String, EdgeLabel) -> Unit): Graph {
+            val graph = Graph()
+            adjacencyList.entries.forEach { graph.addNode(it.node) }
+            adjacencyList.entries.forEach { (node, links) ->
+                links.forEach { addFunction(graph, node, it.node, it.label) }
+            }
+            return graph
+        }
+    }
+}
\ No newline at end of file
diff --git a/ms/controllerblueprints/modules/blueprint-core/src/test/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctionsTest.kt b/ms/controllerblueprints/modules/blueprint-core/src/test/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctionsTest.kt
new file mode 100644
index 000000000..86cb473ae
--- /dev/null
+++ b/ms/controllerblueprints/modules/blueprint-core/src/test/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctionsTest.kt
@@ -0,0 +1,37 @@
+/*
+ *  Copyright © 2019 IBM.
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package org.onap.ccsdk.cds.controllerblueprints.core
+
+import org.junit.Test
+import org.onap.ccsdk.cds.controllerblueprints.core.data.EdgeLabel
+import kotlin.test.assertNotNull
+
+class GraphExtensionFunctionsTest {
+
+    @Test
+    fun testGraph() {
+        val graph = "[p>q/SUCCESS, m>q/SUCCESS, k, p>m/FAILURE, o>p/SUCCESS]".toGraph()
+        assertNotNull(graph, "failed to create graph")
+        assertNotNull(graph.toAdjacencyList(), "failed to adjacency list from graph")
+
+        val neighbors = graph.nodes["p"]!!.neighbors()
+        assertNotNull(neighbors, "failed to neighbors from graph for 'p' node")
+
+        val nodePath = graph.nodes["p"]!!.neighbors(EdgeLabel.SUCCESS)
+        assertNotNull(nodePath, "failed to nodePath from graph for 'p' node 'SUCCESS' label")
+    }
+}