diff options
Diffstat (limited to 'ms')
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") + } +} |