diff options
Diffstat (limited to 'core/sliPluginUtils/provider/src/main/java/org/onap')
22 files changed, 1821 insertions, 2 deletions
diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/SliTopologyUtils.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/SliTopologyUtils.java index 9cfc305c9..5760bdfd4 100644 --- a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/SliTopologyUtils.java +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/SliTopologyUtils.java @@ -17,17 +17,29 @@ */ package org.onap.ccsdk.sli.core.slipluginutils; +import com.google.common.collect.ImmutableSet; +import com.google.gson.JsonArray; +import com.google.gson.JsonElement; +import com.google.gson.JsonObject; +import com.google.gson.JsonParser; import org.apache.commons.lang3.StringUtils; import org.onap.ccsdk.sli.core.sli.SvcLogicContext; import org.onap.ccsdk.sli.core.sli.SvcLogicException; import org.onap.ccsdk.sli.core.sli.SvcLogicJavaPlugin; +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.JsonParserHelper; +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph.DijkstraGraphSearch; +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph.Graph; +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph.Path; +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology.*; +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology.LogicalLink; import org.slf4j.Logger; import org.slf4j.LoggerFactory; +import java.util.ArrayList; +import java.util.List; import java.util.Map; public class SliTopologyUtils implements SvcLogicJavaPlugin { - private static final Logger LOG = LoggerFactory.getLogger(SliTopologyUtils.class); public static final String SUCCESS_CONSTANT = "success"; public static final String FAILURE_CONSTANT = "failure"; @@ -61,8 +73,97 @@ public class SliTopologyUtils implements SvcLogicJavaPlugin { checkParameters(parameters, new String[]{ "pnfs-pfx", "links-pfx", "src-node", "dst-node", "response-pfx"}, LOG); - return SUCCESS_CONSTANT; + boolean outputFullPath = false; + String outputEndToEnd = parameters.get("output-end-to-end-path"); + + if (outputEndToEnd != null && outputEndToEnd.equals("true")){ + outputFullPath = true; + LOG.debug( "OutputEndToEndPath enabled"); + } + + String pnfsStr = ctx.toJsonString(parameters.get("pnfs-pfx")); + String lkStr = ctx.toJsonString(parameters.get("links-pfx")); + + if (pnfsStr.isEmpty()){ + LOG.warn("Pnf Array attributes are empty"); + throw new Exception( "Pnf Array attributes are empty"); + } + + if (lkStr.isEmpty()){ + LOG.warn("Logical-links Array attributes are empty"); + throw new Exception( "Logical-links Array attributes are empty"); + } + + LOG.debug("Pnf Json String is: {}", pnfsStr); + + String srcNodeStr = parameters.get("src-node"); + String dstNodeStr = parameters.get("dst-node"); + + if( srcNodeStr.isEmpty() || dstNodeStr.isEmpty()){ + LOG.warn("Src or Dst node is empty"); + throw new Exception("Src or Dst node is empty"); + } + + JsonParser jp = new JsonParser(); + + JsonArray pnfArr = ((JsonObject) jp.parse(pnfsStr)).getAsJsonArray("pnf"); + JsonArray lkArr = ((JsonObject) jp.parse(lkStr)).getAsJsonArray("logical-link"); + LOG.debug("Creating graph with {} pnf(s) and {} link(s)", pnfArr.size(), lkArr.size()); + Graph<Pnf, LogicalLink> graph = buildGraph(pnfArr, lkArr); + + Pnf src = new Pnf(srcNodeStr); + Pnf dst = new Pnf(dstNodeStr); + + if (!graph.getVertexes().contains(src) || !graph.getVertexes().contains(dst)){ + LOG.warn("Src or Dst node doesn't exist"); + throw new Exception("Src or Dst node doesn't exist"); + } + + DijkstraGraphSearch.Result result = + new DijkstraGraphSearch<Pnf, LogicalLink>().search(graph, src, dst,null, -1); + LOG.debug("Path Computing results: {}", result.paths().toString()); + + if (result.paths().size() > 0){ + JsonObject root = new JsonObject(); + JsonArray solnList = new JsonArray(); + Path<Pnf, LogicalLink> path = (Path<Pnf, LogicalLink>) result.paths().iterator().next(); + for (LogicalLink logicalLink : path.edges()) { + if ( ((OtnLink) logicalLink.underlayLink()).isInnerDomain() && !outputFullPath ){ + //Ignore inner domain links + } else { + JsonObject curLink = new JsonObject(); + String srcNode = logicalLink.src().toString(); + String dstNode = logicalLink.dst().toString(); + String srcPInterface = ((OtnLink) logicalLink.underlayLink()).src().pInterfaceName().getName(); + String dstPInterface = ((OtnLink) logicalLink.underlayLink()).dst().pInterfaceName().getName(); + String linkName = ((OtnLink) logicalLink.underlayLink()).linkName(); + curLink.addProperty("src_node", srcNode); + curLink.addProperty("dst_node", dstNode); + curLink.addProperty("src_pinterface", srcPInterface); + curLink.addProperty("dst_pinterface", dstPInterface); + curLink.addProperty("original_link", linkName); + + solnList.add(curLink); + } + } + root.add("solutions", solnList); + //Write result back to context memory; + String pp = parameters.get("response-pfx").isEmpty() ? "" : parameters.get("response-pfx") + "."; + Map<String, String> mm = null; + mm = JsonParserHelper.convertToProperties(root.toString()); + if (mm != null) { + for (Map.Entry<String, String> entry : mm.entrySet()) { + ctx.setAttribute(pp + entry.getKey(), entry.getValue()); + } + } + LOG.debug("SliTopologyUtils: path computation succeeds in finding the shortest path;" + + " result has been written back into context memory."); + return SUCCESS_CONSTANT; + } else { + LOG.debug("SliTopologyUtils: no valid path found."); + return NOT_FOUND_CONSTANT; + } } catch( Exception e ) { throw new SvcLogicException( "An error occurred in the computePath Execute node", e ); @@ -71,6 +172,85 @@ public class SliTopologyUtils implements SvcLogicJavaPlugin { } } + private static Graph<Pnf, LogicalLink> buildGraph(JsonArray pnfs, JsonArray llks) { + ImmutableSet.Builder pnfSetBlder = ImmutableSet.builder(); + ImmutableSet.Builder lkSetBlder = ImmutableSet.builder(); + + //Create Immutable set of Pnf; + for (int i = 0,e = pnfs.size(); i < e; i++){ + JsonElement pnfName = ((JsonObject) pnfs.get(i)).get("pnf-name"); + + if (pnfName != null){ + String pnfNameStr = pnfName.getAsString(); + + if (pnfNameStr != null && !pnfNameStr.isEmpty()){ + pnfSetBlder.add(new Pnf(pnfNameStr)); + } + + } else { + LOG.debug("SliTopologyUtils: invalid pnf: {}", ((JsonObject) pnfs.get(i)).toString()); + } + } + + //Create Immutable set of Logical-Link + for (int i = 0,e = llks.size(); i < e; i++){ + JsonObject lkRoot = ((JsonObject) llks.get(i)); + JsonElement relationList = lkRoot.get("relationship-list"); + + if (relationList != null) { + JsonElement relationListArray = ((JsonObject) relationList).get("relationship"); + + if (relationListArray != null){ + List<String> pnfNameStrList = new ArrayList<>(); + List<String> pInterfaceStrList= new ArrayList<>(); + + for (int j = 0,k = ((JsonArray) relationListArray).size(); j < k; j++){ + JsonObject relation = ((JsonArray) relationListArray).get(j).getAsJsonObject(); + JsonElement relatedTo = relation.getAsJsonPrimitive("related-to"); + + if (relatedTo != null && relatedTo.getAsString().equals("p-interface")){ + JsonArray data = relation.getAsJsonArray("relationship-data"); + for (int m = 0, n = data.size(); m < n; m++){ + JsonObject dataKeyValue = data.get(m).getAsJsonObject(); + + if (dataKeyValue.get("relationship-key").getAsString().equals("pnf.pnf-name")){ + pnfNameStrList.add(dataKeyValue.get("relationship-value").getAsString()); + } else if (dataKeyValue.get("relationship-key").getAsString() + .equals("p-interface.interface-name")){ + pInterfaceStrList.add(dataKeyValue.get("relationship-value").getAsString()); + } + } + } + } + + if (pnfNameStrList.size() == 2 && pnfNameStrList.size() == 2){ + String pnf1NameStr = pnfNameStrList.get(0); + String pnf2NameStr = pnfNameStrList.get(1); + String pI1NameStr = pInterfaceStrList.get(0); + String pI2NameStr = pInterfaceStrList.get(1); + Pnf pnf1 = new Pnf(pnf1NameStr); + Pnf pnf2 = new Pnf(pnf2NameStr); + PInterfaceName pI1Name = PInterfaceName.of(pI1NameStr); + PInterfaceName pI2Name = PInterfaceName.of(pI2NameStr); + PInterface pI1 = new PInterface(pnf1NameStr, pI1Name); + PInterface pI2 = new PInterface(pnf1NameStr, pI2Name); + String linkName_f = pI1Name.getNetworkId() + "-linkId-" + + pI1Name.getPnfId() + "-" + + pI1Name.getLtpId(); + String linkName_b = pI2Name.getNetworkId() + + "-linkId-" + pI2Name.getPnfId() + + "-" + pI2Name.getLtpId(); + OtnLink link_f = new OtnLink(linkName_f, pI1, pI2); + OtnLink link_b = new OtnLink(linkName_b, pI2, pI1); + lkSetBlder.add(new LogicalLink(pnf1, pnf2, link_f)); + lkSetBlder.add(new LogicalLink(pnf2, pnf1, link_b)); + } + } + } + } + return new Graph<Pnf, LogicalLink>(pnfSetBlder.build(), lkSetBlder.build()); + } + /** * Throws an exception and writes an error to the log file if a required * parameters is not found in the parametersMap. diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/JsonParserHelper.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/JsonParserHelper.java new file mode 100644 index 000000000..4ed0fc83c --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/JsonParserHelper.java @@ -0,0 +1,154 @@ +/*- + * ============LICENSE_START======================================================= + * openECOMP : SDN-C + * ================================================================================ + * Copyright (C) 2017 AT&T Intellectual Property. All rights + * reserved. + * ================================================================================ + * 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. + * ============LICENSE_END========================================================= + */ + +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils; + +import org.apache.commons.lang3.StringUtils; +import org.codehaus.jettison.json.JSONArray; +import org.codehaus.jettison.json.JSONException; +import org.codehaus.jettison.json.JSONObject; +import org.onap.ccsdk.sli.core.sli.SvcLogicException; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.Iterator; +import java.util.Map; + +import static com.google.common.base.Preconditions.checkNotNull; + +public final class JsonParserHelper { + + private static final Logger log = LoggerFactory.getLogger(JsonParserHelper.class); + + private JsonParserHelper() { + // Preventing instantiation of the same. + } + + + private static void handleJsonArray(String key, Map<String, Object> jArrayMap, JSONArray jsonArr) throws JSONException { + JSONObject jsonObj; + JSONArray subJsonArr; + boolean stripKey = false; + + for (int i = 0, length = jsonArr.length(); i < length; i++) { + if (stripKey) + key = key.substring(0, key.length()-3); + + subJsonArr = jsonArr.optJSONArray(i); + if (subJsonArr != null) { + key = StringUtils.trimToEmpty(key) + "[" + i + "]"; + jArrayMap.putIfAbsent(key + "_length", String.valueOf(subJsonArr.length())); + handleJsonArray(key, jArrayMap, subJsonArr); + stripKey = true; + continue; + } + + jsonObj = jsonArr.optJSONObject(i); + if (jsonObj != null) { + Iterator<String> ii = jsonObj.keys(); + while (ii.hasNext()) { + String nodeKey = ii.next(); + String key1 = "[" + i + "]." + nodeKey; + String[] subKey = key1.split(":"); + if (subKey.length == 2) { + jArrayMap.putIfAbsent(subKey[1], jsonObj.get(nodeKey)); + } else { + jArrayMap.putIfAbsent(key1, jsonObj.get(nodeKey)); + } + } + } + else { + jArrayMap.putIfAbsent(StringUtils.trimToEmpty(key), jsonArr); + break; + } + } + } + + @SuppressWarnings("unchecked") + public static Map<String, String> convertToProperties(String s) + throws SvcLogicException { + + checkNotNull(s, "Input should not be null."); + + try { + Map<String, Object> wm = new HashMap<>(); + JSONObject json; + JSONArray jsonArr; + //support top level list in json response + if (s.startsWith("[")) { + jsonArr = new JSONArray(s); + wm.put("_length", String.valueOf(jsonArr.length())); + handleJsonArray(null, wm, jsonArr); + } else { + json = new JSONObject(s); + Iterator<String> ii = json.keys(); + while (ii.hasNext()) { + String key1 = ii.next(); + String[] subKey = key1.split(":"); + if (subKey.length == 2) { + wm.put(subKey[1], json.get(key1)); + } else { + wm.put(key1, json.get(key1)); + } + } + } + + Map<String, String> mm = new HashMap<>(); + while (!wm.isEmpty()) { + for (String key : new ArrayList<>(wm.keySet())) { + Object o = wm.get(key); + wm.remove(key); + + if (o instanceof Boolean || o instanceof Number || o instanceof String) { + mm.put(key, o.toString()); + //log.info("Added property: {} : {}", key, o.toString()); + } else if (o instanceof JSONObject) { + JSONObject jo = (JSONObject) o; + Iterator<String> i = jo.keys(); + while (i.hasNext()) { + String key1 = i.next(); + String[] subKey = key1.split(":"); + if (subKey.length == 2) { + wm.put(key + "." + subKey[1], jo.get(key1)); + } else { + wm.put(key + "." + key1, jo.get(key1)); + } + } + } else if (o instanceof JSONArray) { + JSONArray ja = (JSONArray) o; + mm.put(key + "_length", String.valueOf(ja.length())); + //log.info("Added property: {}_length: {}", key, ja.length()); + + for (int i = 0; i < ja.length(); i++) { + wm.put(key + '[' + i + ']', ja.get(i)); + } + } + } + } + return mm; + } catch (JSONException e) { + throw new SvcLogicException("Unable to convert JSON to properties" + e.getLocalizedMessage(), e); + } + } + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultEdgeWeigher.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultEdgeWeigher.java new file mode 100644 index 000000000..92a9172b2 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultEdgeWeigher.java @@ -0,0 +1,52 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +/** + * Default weigher returns identical weight for every graph edge. Basically it + * is a hop count weigher. + * Produces weights of {@link ScalarWeight} type. + * + * @param <V> vertex type + * @param <E> edge type + */ +public class DefaultEdgeWeigher<V extends Vertex, E extends Edge<V>> + implements EdgeWeigher<V, E> { + + /** + * Common weight value for any link. + */ + protected static final double HOP_WEIGHT_VALUE = 1; + /** + * Weight value for null path (without links). + */ + protected static final double NULL_WEIGHT_VALUE = 0; + + /** + * Default weight based on hop count. + * {@value #HOP_WEIGHT_VALUE} + */ + public static final ScalarWeight DEFAULT_HOP_WEIGHT = + new ScalarWeight(HOP_WEIGHT_VALUE); + + /** + * Default initial weight. + * {@value #NULL_WEIGHT_VALUE} + */ + public static final ScalarWeight DEFAULT_INITIAL_WEIGHT = + new ScalarWeight(NULL_WEIGHT_VALUE); + + @Override + public Weight weight(E edge) { + return DEFAULT_HOP_WEIGHT; + } + + @Override + public Weight getInitialWeight() { + return DEFAULT_INITIAL_WEIGHT; + } + + @Override + public Weight getNonViableWeight() { + return ScalarWeight.NON_VIABLE_WEIGHT; + } +} + diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultMutablePath.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultMutablePath.java new file mode 100644 index 000000000..8d815c38b --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultMutablePath.java @@ -0,0 +1,121 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +import com.google.common.collect.ImmutableList; + +import java.util.ArrayList; +import java.util.List; +import java.util.Objects; + +import static com.google.common.base.MoreObjects.toStringHelper; +import static com.google.common.base.Preconditions.checkArgument; +import static com.google.common.base.Preconditions.checkNotNull; + +/** + * Simple concrete implementation of a directed graph path. + */ +public class DefaultMutablePath<V extends Vertex, E extends Edge<V>> implements MutablePath<V, E> { + + private final List<E> edges = new ArrayList<>(); + private Weight cost; + + /** + * Creates a new empty path. + */ + public DefaultMutablePath() { + } + + /** + * Creates a new path as a copy of another path. + * + * @param path path to be copied + */ + public DefaultMutablePath(Path<V, E> path) { + checkNotNull(path, "Path cannot be null"); + this.cost = path.cost(); + edges.addAll(path.edges()); + } + + @Override + public V src() { + return edges.isEmpty() ? null : edges.get(0).src(); + } + + @Override + public V dst() { + return edges.isEmpty() ? null : edges.get(edges.size() - 1).dst(); + } + + @Override + public Weight cost() { + return cost; + } + + @Override + public List<E> edges() { + return ImmutableList.copyOf(edges); + } + + @Override + public void setCost(Weight cost) { + this.cost = cost; + } + + @Override + public Path<V, E> toImmutable() { + return new DefaultPath<>(edges, cost); + } + + @Override + public void insertEdge(E edge) { + checkNotNull(edge, "Edge cannot be null"); + checkArgument(edges.isEmpty() || src().equals(edge.dst()), + "Edge destination must be the same as the current path source"); + edges.add(0, edge); + } + + @Override + public void appendEdge(E edge) { + checkNotNull(edge, "Edge cannot be null"); + checkArgument(edges.isEmpty() || dst().equals(edge.src()), + "Edge source must be the same as the current path destination"); + edges.add(edge); + } + + @Override + public void removeEdge(E edge) { + checkArgument(edge.src().equals(edge.dst()) || + edges.indexOf(edge) == 0 || + edges.lastIndexOf(edge) == edges.size() - 1, + "Edge must be at start or end of path, or it must be a cyclic edge"); + edges.remove(edge); + } + + @Override + public String toString() { + return toStringHelper(this) + .add("src", src()) + .add("dst", dst()) + .add("cost", cost) + .add("edges", edges) + .toString(); + } + + @Override + public int hashCode() { + return Objects.hash(edges, cost); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof DefaultMutablePath) { + final DefaultMutablePath other = (DefaultMutablePath) obj; + return Objects.equals(this.cost, other.cost) && + Objects.equals(this.edges, other.edges); + } + return false; + } + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultPath.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultPath.java new file mode 100644 index 000000000..9ef00b835 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DefaultPath.java @@ -0,0 +1,87 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +import com.google.common.collect.ImmutableList; + +import java.util.List; +import java.util.Objects; + +import static com.google.common.base.MoreObjects.toStringHelper; +import static com.google.common.base.Preconditions.checkArgument; +import static com.google.common.base.Preconditions.checkNotNull; + +/** + * Simple concrete implementation of a directed graph path. + */ +public class DefaultPath<V extends Vertex, E extends Edge<V>> implements Path<V, E> { + + private final V src; + private final V dst; + private final List<E> edges; + private Weight cost; + + /** + * Creates a new path from the specified list of edges and cost. + * + * @param edges list of path edges + * @param cost path cost as a weight object + */ + public DefaultPath(List<E> edges, Weight cost) { + checkNotNull(edges, "Edges list must not be null"); + checkArgument(!edges.isEmpty(), "There must be at least one edge"); + this.edges = ImmutableList.copyOf(edges); + this.src = edges.get(0).src(); + this.dst = edges.get(edges.size() - 1).dst(); + this.cost = cost; + } + + @Override + public V src() { + return src; + } + + @Override + public V dst() { + return dst; + } + + @Override + public Weight cost() { + return cost; + } + + @Override + public List<E> edges() { + return edges; + } + + @Override + public String toString() { + return toStringHelper(this) + .add("src", src) + .add("dst", dst) + .add("cost", cost) + .add("edges", edges) + .toString(); + } + + @Override + public int hashCode() { + return Objects.hash(src, dst, edges, cost); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof DefaultPath) { + final DefaultPath other = (DefaultPath) obj; + return Objects.equals(this.src, other.src) && + Objects.equals(this.dst, other.dst) && + Objects.equals(this.cost, other.cost) && + Objects.equals(this.edges, other.edges); + } + return false; + } + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java new file mode 100644 index 000000000..11611346b --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/DijkstraGraphSearch.java @@ -0,0 +1,377 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +import java.util.*; + +import static com.google.common.base.Preconditions.checkArgument; +import static com.google.common.base.Preconditions.checkNotNull; + +/** + * Dijkstra shortest-path graph search algorithm capable of finding not just + * one, but all shortest paths between the source and destinations. + */ +public class DijkstraGraphSearch<V extends Vertex, E extends Edge<V>> { + + static int ALL_PATHS = -1; + /** + * Default path search result that uses the DefaultPath to convey paths + * in a graph. + */ + public class Result { + + private final V src; + private final V dst; + protected final Set<Path<V, E>> paths = new HashSet<>(); + protected final Map<V, Weight> costs = new HashMap<>(); + protected final Map<V, Set<E>> parents = new HashMap<>(); + protected final int maxPaths; + + /** + * Creates the result of a single-path search. + * + * @param src path source + * @param dst optional path destination + */ + public Result(V src, V dst) { + this(src, dst, 1); + } + + /** + * Creates the result of path search. + * + * @param src path source + * @param dst optional path destination + * @param maxPaths optional limit of number of paths; + * {@link #ALL_PATHS} if no limit + */ + public Result(V src, V dst, int maxPaths) { + checkNotNull(src, "Source cannot be null"); + this.src = src; + this.dst = dst; + this.maxPaths = maxPaths; + } + + + public V src() { + return src; + } + + + public V dst() { + return dst; + } + + + public Set<Path<V, E>> paths() { + return paths; + } + + public Map<V, Weight> costs() { + return costs; + } + + public Map<V, Set<E>> parents() { + return parents; + } + + /** + * Indicates whether or not the given vertex has a cost yet. + * + * @param v vertex to test + * @return true if the vertex has cost already + */ + public boolean hasCost(V v) { + return costs.containsKey(v); + } + + /** + * Returns the current cost to reach the specified vertex. + * If the vertex has not been accessed yet, it has no cost + * associated and null will be returned. + * + * @param v vertex to reach + * @return weight cost to reach the vertex if already accessed; + * null otherwise + */ + public Weight cost(V v) { + return costs.get(v); + } + + /** + * Updates the cost of the vertex using its existing cost plus the + * cost to traverse the specified edge. If the search is in single + * path mode, only one path will be accrued. + * + * @param vertex vertex to update + * @param edge edge through which vertex is reached + * @param cost current cost to reach the vertex from the source + * @param replace true to indicate that any accrued edges are to be + * cleared; false to indicate that the edge should be + * added to the previously accrued edges as they yield + * the same cost + */ + public void updateVertex(V vertex, E edge, Weight cost, boolean replace) { + costs.put(vertex, cost); + if (edge != null) { + Set<E> edges = parents.get(vertex); + if (edges == null) { + edges = new HashSet<>(); + parents.put(vertex, edges); + } + if (replace) { + edges.clear(); + } + if (maxPaths == ALL_PATHS || edges.size() < maxPaths) { + edges.add(edge); + } + } + } + + /** + * Removes the set of parent edges for the specified vertex. + * + * @param v vertex + */ + void removeVertex(V v) { + parents.remove(v); + } + + /** + * If possible, relax the specified edge using the supplied base cost + * and edge-weight function. + * + * @param edge edge to be relaxed + * @param cost base cost to reach the edge destination vertex + * @param ew optional edge weight function + * @param forbidNegatives if true negative values will forbid the link + * @return true if the edge was relaxed; false otherwise + */ + public boolean relaxEdge(E edge, Weight cost, EdgeWeigher<V, E> ew, + boolean... forbidNegatives) { + V v = edge.dst(); + + Weight hopCost = ew.weight(edge); + if ((!hopCost.isViable()) || + (hopCost.isNegative() && forbidNegatives.length == 1 && forbidNegatives[0])) { + return false; + } + Weight newCost = cost.merge(hopCost); + + int compareResult = -1; + if (hasCost(v)) { + Weight oldCost = cost(v); + compareResult = newCost.compareTo(oldCost); + } + + if (compareResult <= 0) { + updateVertex(v, edge, newCost, compareResult < 0); + } + return compareResult < 0; + } + + /** + * Builds a set of paths for the specified src/dst vertex pair. + */ + public void buildPaths() { + Set<V> destinations = new HashSet<>(); + if (dst == null) { + destinations.addAll(costs.keySet()); + } else { + destinations.add(dst); + } + + // Build all paths between the source and all requested destinations. + for (V v : destinations) { + // Ignore the source, if it is among the destinations. + if (!v.equals(src)) { + buildAllPaths(this, src, v, maxPaths); + } + } + } + + } + /** + * Builds a set of all paths between the source and destination using the + * graph search result by applying breadth-first search through the parent + * edges and vertex costs. + * + * @param result graph search result + * @param src source vertex + * @param dst destination vertex + * @param maxPaths limit on the number of paths built; + * {@link #ALL_PATHS} if no limit + */ + private void buildAllPaths(Result result, V src, V dst, int maxPaths) { + DefaultMutablePath<V, E> basePath = new DefaultMutablePath<>(); + basePath.setCost(result.cost(dst)); + + Set<DefaultMutablePath<V, E>> pendingPaths = new HashSet<>(); + pendingPaths.add(basePath); + + while (!pendingPaths.isEmpty() && + (maxPaths == ALL_PATHS || result.paths.size() < maxPaths)) { + Set<DefaultMutablePath<V, E>> frontier = new HashSet<>(); + + for (DefaultMutablePath<V, E> path : pendingPaths) { + // For each pending path, locate its first vertex since we + // will be moving backwards from it. + V firstVertex = firstVertex(path, dst); + + // If the first vertex is our expected source, we have reached + // the beginning, so add the this path to the result paths. + if (firstVertex.equals(src)) { + path.setCost(result.cost(dst)); + result.paths.add(new DefaultPath<>(path.edges(), path.cost())); + + } else { + // If we have not reached the beginning, i.e. the source, + // fetch the set of edges leading to the first vertex of + // this pending path; if there are none, abandon processing + // this path for good. + Set<E> firstVertexParents = result.parents.get(firstVertex); + if (firstVertexParents == null || firstVertexParents.isEmpty()) { + break; + } + + // Now iterate over all the edges and for each of them + // cloning the current path and then insert that edge to + // the path and then add that path to the pending ones. + // When processing the last edge, modify the current + // pending path rather than cloning a new one. + Iterator<E> edges = firstVertexParents.iterator(); + while (edges.hasNext()) { + E edge = edges.next(); + boolean isLast = !edges.hasNext(); + // Exclude any looping paths + if (!isInPath(edge, path)) { + DefaultMutablePath<V, E> pendingPath = isLast ? path : new DefaultMutablePath<>(path); + pendingPath.insertEdge(edge); + frontier.add(pendingPath); + } + } + } + } + + // All pending paths have been scanned so promote the next frontier + pendingPaths = frontier; + } + } + + /** + * Indicates whether or not the specified edge source is already visited + * in the specified path. + * + * @param edge edge to test + * @param path path to test + * @return true if the edge.src() is a vertex in the path already + */ + private boolean isInPath(E edge, DefaultMutablePath<V, E> path) { + return path.edges().stream().anyMatch(e -> edge.src().equals(e.dst())); + } + + // Returns the first vertex of the specified path. This is either the source + // of the first edge or, if there are no edges yet, the given destination. + private V firstVertex(Path<V, E> path, V dst) { + return path.edges().isEmpty() ? dst : path.edges().get(0).src(); + } + + /** + * Checks the specified path search arguments for validity. + * + * @param graph graph; must not be null + * @param src source vertex; must not be null and belong to graph + * @param dst optional target vertex; must belong to graph + */ + protected void checkArguments(Graph<V, E> graph, V src, V dst) { + checkNotNull(graph, "Graph cannot be null"); + checkNotNull(src, "Source cannot be null"); + Set<V> vertices = graph.getVertexes(); + checkArgument(vertices.contains(src), "Source not in the graph"); + checkArgument(dst == null || vertices.contains(dst), + "Destination not in graph"); + } + + public Result search(Graph<V, E> graph, V src, V dst, + EdgeWeigher<V, E> weigher, int maxPaths) { + checkArguments(graph, src, dst); + + return internalSearch(graph, src, dst, + weigher != null ? weigher : new DefaultEdgeWeigher<>(), + maxPaths); + } + + protected Result internalSearch(Graph<V, E> graph, V src, V dst, + EdgeWeigher<V, E> weigher, int maxPaths) { + + // Use the default result to remember cumulative costs and parent + // edges to each each respective vertex. + Result result = new Result(src, dst, maxPaths); + + // Cost to reach the source vertex is 0 of course. + result.updateVertex(src, null, weigher.getInitialWeight(), false); + + if (graph.getEdges().isEmpty()) { + result.buildPaths(); + return result; + } + + // Use the min priority queue to progressively find each nearest + // vertex until we reach the desired destination, if one was given, + // or until we reach all possible destinations. + Heap<V> minQueue = createMinQueue(graph.getVertexes(), + new PathCostComparator(result)); + while (!minQueue.isEmpty()) { + // Get the nearest vertex + V nearest = minQueue.extractExtreme(); + if (nearest.equals(dst)) { + break; + } + + // Find its cost and use it to determine if the vertex is reachable. + if (result.hasCost(nearest)) { + Weight cost = result.cost(nearest); + + // If the vertex is reachable, relax all its egress edges. + for (E e : graph.getEdgesFrom(nearest)) { + result.relaxEdge(e, cost, weigher, true); + } + } + + // Re-prioritize the min queue. + minQueue.heapify(); + } + + // Now construct a set of paths from the results. + result.buildPaths(); + return result; + } + + // Compares path weights using their accrued costs; used for sorting the + // min priority queue. + private final class PathCostComparator implements Comparator<V> { + private final Result result; + + private PathCostComparator(Result result) { + this.result = result; + } + + @Override + public int compare(V v1, V v2) { + //not accessed vertices should be pushed to the back of the queue + if (!result.hasCost(v1) && !result.hasCost(v2)) { + return 0; + } else if (!result.hasCost(v1)) { + return -1; + } else if (!result.hasCost(v2)) { + return 1; + } + + return result.cost(v2).compareTo(result.cost(v1)); + } + } + + // Creates a min priority queue from the specified vertexes and comparator. + private Heap<V> createMinQueue(Set<V> vertexes, Comparator<V> comparator) { + return new Heap<>(new ArrayList<>(vertexes), comparator); + } + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Edge.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Edge.java new file mode 100644 index 000000000..b178072c2 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Edge.java @@ -0,0 +1,19 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +public interface Edge<V extends Vertex> { + + /** + * Returns the edge source vertex. + * + * @return source vertex + */ + V src(); + + /** + * Returns the edge destination vertex. + * + * @return destination vertex + */ + V dst(); + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/EdgeWeigher.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/EdgeWeigher.java new file mode 100644 index 000000000..008204456 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/EdgeWeigher.java @@ -0,0 +1,31 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +/** + * Abstraction of a graph edge weight function. + */ +public interface EdgeWeigher<V extends Vertex, E extends Edge<V>> { + + /** + * Returns the weight of the given edge. + * + * @param edge edge to be weighed + * @return edge weight + */ + Weight weight(E edge); + + /** + * Returns initial weight value (i.e. weight of a "path" starting and + * terminating in the same vertex; typically 0 value is used). + * + * @return null path weight + */ + Weight getInitialWeight(); + + /** + * Returns weight of a link/path that should be skipped + * (can be considered as an infinite weight). + * + * @return non viable weight + */ + Weight getNonViableWeight(); +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Graph.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Graph.java new file mode 100644 index 000000000..c06309cf9 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Graph.java @@ -0,0 +1,106 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.ImmutableSetMultimap; + +import java.util.Objects; +import java.util.Set; + +import static com.google.common.base.MoreObjects.toStringHelper; +import static com.google.common.base.Preconditions.checkNotNull; + +/** + * Immutable directionless graph implementation using adjacency lists. + * @param <V> + * @param <E> + */ +public class Graph<V extends Vertex, E extends Edge<V>> +{ + + private final Set<V> vertexes; + private final Set<E> edges; + + private final ImmutableSetMultimap<V, E> sources; + private final ImmutableSetMultimap<V, E> destinations; + + /** + * Creates a graph comprising of the specified vertexes and edges. + * + * @param vertexes set of graph vertexes + * @param edges set of graph edges + */ + public Graph(Set<V> vertexes, Set<E> edges) { + checkNotNull(vertexes, "Vertex set cannot be null"); + checkNotNull(edges, "Edge set cannot be null"); + + // Record ingress/egress edges for each vertex. + ImmutableSetMultimap.Builder<V, E> srcMap = ImmutableSetMultimap.builder(); + ImmutableSetMultimap.Builder<V, E> dstMap = ImmutableSetMultimap.builder(); + + // Also make sure that all edge end-points are added as vertexes + ImmutableSet.Builder<V> actualVertexes = ImmutableSet.builder(); + actualVertexes.addAll(vertexes); + + for (E edge : edges) { + srcMap.put(edge.src(), edge); + actualVertexes.add(edge.src()); + dstMap.put(edge.dst(), edge); + actualVertexes.add(edge.dst()); + } + + // Make an immutable copy of the edge and vertex sets + this.edges = ImmutableSet.copyOf(edges); + this.vertexes = actualVertexes.build(); + + // Build immutable copies of sources and destinations edge maps + sources = srcMap.build(); + destinations = dstMap.build(); + } + + + public Set<V> getVertexes() { + return vertexes; + } + + + public Set<E> getEdges() { + return edges; + } + + + public Set<E> getEdgesFrom(V src) { + return sources.get(src); + } + + + public Set<E> getEdgesTo(V dst) { + return destinations.get(dst); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof Graph) { + Graph that = (Graph) obj; + return this.getClass() == that.getClass() && + Objects.equals(this.vertexes, that.vertexes) && + Objects.equals(this.edges, that.edges); + } + return false; + } + + @Override + public int hashCode() { + return Objects.hash(vertexes, edges); + } + + @Override + public String toString() { + return toStringHelper(this) + .add("vertexes", vertexes) + .add("edges", edges) + .toString(); + } +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Heap.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Heap.java new file mode 100644 index 000000000..ded3cb5da --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Heap.java @@ -0,0 +1,197 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +import com.google.common.collect.ImmutableList; + +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; +import java.util.Objects; + +import static com.google.common.base.MoreObjects.toStringHelper; +import static com.google.common.base.Preconditions.checkNotNull; + +/** + * Implementation of an array-backed heap structure whose sense of order is + * imposed by the provided comparator. + * <p> + * While this provides similar functionality to {@link java.util.PriorityQueue} + * data structure, one key difference is that external entities can control + * when to restore the heap property, which is done through invocation of the + * {@link #heapify} method. + * </p> + * <p> + * This class is not thread-safe and care must be taken to prevent concurrent + * modifications. + * </p> + * + * @param <T> type of the items on the heap + */ +public class Heap<T> { + + private final List<T> data; + private final Comparator<T> comparator; + + /** + * Creates a new heap backed by the specified list. In the interest of + * efficiency, the list should be array-backed. Also, for the same reason, + * the data is not copied and therefore, the caller must assure that the + * backing data is not altered in any way. + * + * @param data backing data list + * @param comparator comparator for ordering the heap items + */ + public Heap(List<T> data, Comparator<T> comparator) { + this.data = checkNotNull(data, "Data cannot be null"); + this.comparator = checkNotNull(comparator, "Comparator cannot be null"); + heapify(); + } + + /** + * Restores the heap property by re-arranging the elements in the backing + * array as necessary following any heap modifications. + */ + public void heapify() { + for (int i = data.size() / 2; i >= 0; i--) { + heapify(i); + } + } + + /** + * Returns the current size of the heap. + * + * @return number of items in the heap + */ + public int size() { + return data.size(); + } + + /** + * Returns true if there are no items in the heap. + * + * @return true if heap is empty + */ + public boolean isEmpty() { + return data.isEmpty(); + } + + /** + * Returns the most extreme item in the heap. + * + * @return heap extreme or null if the heap is empty + */ + public T extreme() { + return data.isEmpty() ? null : data.get(0); + } + + /** + * Extracts and returns the most extreme item from the heap. + * + * @return heap extreme or null if the heap is empty + */ + public T extractExtreme() { + if (!isEmpty()) { + T extreme = extreme(); + + data.set(0, data.get(data.size() - 1)); + data.remove(data.size() - 1); + heapify(); + return extreme; + } + return null; + } + + /** + * Inserts the specified item into the heap and returns the modified heap. + * + * @param item item to be inserted + * @return the heap self + * @throws IllegalArgumentException if the heap is already full + */ + public Heap<T> insert(T item) { + data.add(item); + bubbleUp(); + return this; + } + + /** + * Returns iterator to traverse the heap level-by-level. This iterator + * does not permit removal of items. + * + * @return non-destructive heap iterator + */ + public Iterator<T> iterator() { + return ImmutableList.copyOf(data).iterator(); + } + + // Bubbles up the last item in the heap to its proper position to restore + // the heap property. + private void bubbleUp() { + int child = data.size() - 1; + while (child > 0) { + int parent = child / 2; + if (comparator.compare(data.get(child), data.get(parent)) < 0) { + break; + } + swap(child, parent); + child = parent; + } + } + + // Restores the heap property of the specified heap layer. + private void heapify(int i) { + int left = 2 * i + 1; + int right = 2 * i; + int extreme = i; + + if (left < data.size() && + comparator.compare(data.get(extreme), data.get(left)) < 0) { + extreme = left; + } + + if (right < data.size() && + comparator.compare(data.get(extreme), data.get(right)) < 0) { + extreme = right; + } + + if (extreme != i) { + swap(i, extreme); + heapify(extreme); + } + } + + // Swaps two heap items identified by their respective indexes. + private void swap(int i, int k) { + T aux = data.get(i); + data.set(i, data.get(k)); + data.set(k, aux); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof Heap) { + Heap that = (Heap) obj; + return this.getClass() == that.getClass() && + Objects.equals(this.comparator, that.comparator) && + Objects.deepEquals(this.data, that.data); + } + return false; + } + + @Override + public int hashCode() { + return Objects.hash(comparator, data); + } + + @Override + public String toString() { + return toStringHelper(this) + .add("data", data) + .add("comparator", comparator) + .toString(); + } + +} + diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/MutablePath.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/MutablePath.java new file mode 100644 index 000000000..22c419804 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/MutablePath.java @@ -0,0 +1,48 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +/** + * Abstraction of a mutable path that allows gradual construction. + */ +public interface MutablePath<V extends Vertex, E extends Edge<V>> extends Path<V, E> { + + /** + * Inserts a new edge at the beginning of this path. The edge must be + * adjacent to the prior start of the path. + * + * @param edge edge to be inserted + */ + void insertEdge(E edge); + + /** + * Appends a new edge at the end of the this path. The edge must be + * adjacent to the prior end of the path. + * + * @param edge edge to be inserted + */ + void appendEdge(E edge); + + /** + * Removes the specified edge. This edge must be either at the start or + * at the end of the path, or it must be a cyclic edge in order not to + * violate the contiguous path property. + * + * @param edge edge to be removed + */ + void removeEdge(E edge); + + /** + * Sets the total path cost as a weight object. + * + * @param cost new path cost + */ + void setCost(Weight cost); + + /** + * Returns an immutable copy of this path. + * + * @return immutable copy + */ + Path<V, E> toImmutable(); + +} + diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Path.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Path.java new file mode 100644 index 000000000..c8a2ef985 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Path.java @@ -0,0 +1,30 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +import java.util.List; + +/** + * Representation of a path in a graph as a sequence of edges. Paths are + * assumed to be continuous, where adjacent edges must share a vertex. + * + * @param <V> vertex type + * @param <E> edge type + */ +public interface Path<V extends Vertex, E extends Edge<V>> extends Edge<V> { + + /** + * Returns the list of edges comprising the path. Adjacent edges will + * share the same vertex, meaning that a source of one edge, will be the + * same as the destination of the prior edge. + * + * @return list of path edges + */ + List<E> edges(); + + /** + * Returns the total cost of the path as a weight object. + * + * @return path cost as a weight object + */ + Weight cost(); + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/ScalarWeight.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/ScalarWeight.java new file mode 100644 index 000000000..a9c2a0e52 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/ScalarWeight.java @@ -0,0 +1,96 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +import java.util.Objects; + +import static com.google.common.base.MoreObjects.toStringHelper; + +/** + * Weight implementation based on a double value. + */ +public class ScalarWeight implements Weight { + + /** + * Instance of scalar weight to mark links/paths which + * can not be traversed. + */ + public static final ScalarWeight NON_VIABLE_WEIGHT = + new ScalarWeight(Double.POSITIVE_INFINITY); + + private static double samenessThreshold = Double.MIN_VALUE; + + private final double value; + + /** + * Creates a new scalar weight with the given double value. + * @param value double value + * @return scalar weight instance + */ + public static ScalarWeight toWeight(double value) { + return new ScalarWeight(value); + } + + /** + * Creates a new scalar weight with the given double value. + * @param value double value + */ + public ScalarWeight(double value) { + this.value = value; + } + + @Override + public Weight merge(Weight otherWeight) { + return new ScalarWeight(value + ((ScalarWeight) otherWeight).value); + } + + @Override + public Weight subtract(Weight otherWeight) { + return new ScalarWeight(value - ((ScalarWeight) otherWeight).value); + } + + @Override + public boolean isViable() { + return !this.equals(NON_VIABLE_WEIGHT); + } + + @Override + public int compareTo(Weight otherWeight) { + //check equality with samenessThreshold + if (equals(otherWeight)) { + return 0; + } + return Double.compare(value, ((ScalarWeight) otherWeight).value); + } + + @Override + public boolean equals(Object obj) { + return ((obj instanceof ScalarWeight) && + (Math.abs(value - ((ScalarWeight) obj).value) < samenessThreshold) + ); + } + + @Override + public int hashCode() { + return Objects.hash(value); + } + + @Override + public boolean isNegative() { + return value < 0; + } + + @Override + public String toString() { + return toStringHelper(this).add("value", value).toString(); + } + + + /** + * Returns inner double value. + * + * @return double value + */ + public double value() { + return value; + } + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Vertex.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Vertex.java new file mode 100644 index 000000000..21127f437 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Vertex.java @@ -0,0 +1,4 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +public interface Vertex { +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Weight.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Weight.java new file mode 100644 index 000000000..73772ed40 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/graph/Weight.java @@ -0,0 +1,39 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph; + +/** + * Abstraction of a graph edge weight. + */ +public interface Weight extends Comparable<Weight> { + + /** + * Merges the given weight with this one returning a new aggregated + * weight. + * + * @param otherWeight weight to add + * @return aggregated weight + */ + Weight merge(Weight otherWeight); + + /** + * Subtracts the given weight from this one and produces a new weight. + * + * @param otherWeight weight to subtract + * @return residual weight + */ + Weight subtract(Weight otherWeight); + + /** + * Returns true if the weighted subject (link/path) can be traversed; false otherwise. + * + * @return true if weight is adequate, false if weight is infinite + */ + boolean isViable(); + + /** + * Returns true if the weight is negative (means that aggregated + * path cost will decrease if we add weighted subject to it). + * + * @return true if the weight is negative, false otherwise + */ + boolean isNegative(); +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/Link.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/Link.java new file mode 100644 index 000000000..fe6ec1c4f --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/Link.java @@ -0,0 +1,9 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology; + +public interface Link { + + enum Type { + OTN, + ETH + } +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/LogicalLink.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/LogicalLink.java new file mode 100644 index 000000000..47b43e849 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/LogicalLink.java @@ -0,0 +1,51 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology; + +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph.Edge; + +import java.util.Objects; + +import static com.google.common.base.Preconditions.checkNotNull; + +public class LogicalLink implements Edge<Pnf> { + + private final Pnf src; + private final Pnf dst; + private final Link link; + + public LogicalLink (Pnf src, Pnf dst, Link underlayLink) { + this.src = src; + this.dst = dst; + this.link = underlayLink; + } + + public Link underlayLink(){ + return this.link; + } + + @Override + public Pnf src() { + return src; + } + + @Override + public Pnf dst() { + return dst; + } + + @Override + public int hashCode() { + return link.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof LogicalLink) { + final LogicalLink other = (LogicalLink) obj; + return Objects.equals(this.link, other.link); + } + return false; + } +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/OtnLink.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/OtnLink.java new file mode 100644 index 000000000..553a9bd26 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/OtnLink.java @@ -0,0 +1,60 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology; + +import java.util.Objects; + +public class OtnLink implements Link{ + + private final Type type = Type.OTN; + private final PInterface src; + private final PInterface dst; + + + private final String linkName; + + public OtnLink(String linkName, PInterface src, PInterface dst){ + this.linkName = linkName; + this.src = src; + this.dst = dst; + } + + public PInterface src() { + return src; + } + + public PInterface dst() { + return dst; + } + + public String linkName() { + return linkName; + } + + public boolean isInnerDomain(){ + if (src != null && dst != null){ + if (src.pInterfaceName() != null && dst.pInterfaceName() != null){ + if (src.pInterfaceName().getNetworkId() != null + && dst.pInterfaceName().getNetworkId() != null) { + return src.pInterfaceName().getNetworkId().equals(dst.pInterfaceName().getNetworkId()); + } + } + } + return false; + } + + @Override + public boolean equals(Object o){ + if (this == o) { + return true; + } + if (o instanceof OtnLink){ + final OtnLink other = (OtnLink) o; + return Objects.equals(this.linkName, other.linkName); + } + return false; + } + + @Override + public int hashCode(){ + return Objects.hash(linkName, type, src, dst); + } +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PInterface.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PInterface.java new file mode 100644 index 000000000..6b111871d --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PInterface.java @@ -0,0 +1,36 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology; + +import java.util.Objects; + +public class PInterface { + + private final String pnfName; + private final PInterfaceName pInterfaceName; + + public PInterface(String pnfName, PInterfaceName pInterfaceName){ + this.pnfName = pnfName; + this.pInterfaceName = pInterfaceName; + } + + public PInterfaceName pInterfaceName() { + return pInterfaceName; + } + + @Override + public int hashCode(){ + return Objects.hash(pnfName, pInterfaceName); + } + + @Override + public boolean equals(Object o){ + if (this == o){ + return true; + } + if (o instanceof PInterface){ + final PInterface other = (PInterface) o; + return Objects.equals(this.pnfName, other.pnfName) && + Objects.equals(this.pInterfaceName, other.pInterfaceName); + } + return false; + } +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PInterfaceName.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PInterfaceName.java new file mode 100644 index 000000000..cb636a050 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PInterfaceName.java @@ -0,0 +1,82 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology; + +import java.util.Objects; +import java.util.regex.Matcher; +import java.util.regex.Pattern; + +import static com.google.common.base.Preconditions.checkNotNull; + +public class PInterfaceName { + + private final String name; + private final String networkId; + private final String pnfId; + private final String ltpId; + private final boolean parsable; + private final static String pattern = "(.*)-nodeId-([0-9]{1,3}\\.[0-9]{1,3}\\.[0-9]{1,3}\\.[0-9]{1,3})-ltpId-(\\d+)"; + private final static Pattern regex = Pattern.compile(pattern); + + public PInterfaceName (String pInterfaceName){ + this.name = pInterfaceName; + this.networkId = null; + this.pnfId = null; + this.ltpId = null; + this.parsable = false; + } + + public PInterfaceName(String pInterfaceName, String networkId, String pnfId, String ltpId){ + this.name = pInterfaceName; + this.networkId = networkId; + this.pnfId = pnfId; + this.ltpId = ltpId; + this.parsable = true; + } + + public static PInterfaceName of(String pInterfaceName){ + String name = checkNotNull(pInterfaceName); + Matcher m = regex.matcher(name); + if (m.find()) { + checkNotNull(m.group(1)); + checkNotNull(m.group(2)); + checkNotNull(m.group(3)); + return new PInterfaceName(name, m.group(1), m.group(2), m.group(3)); + } else { + return new PInterfaceName(name); + } + } + + public boolean isParsable() { + return parsable; + } + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + PInterfaceName that = (PInterfaceName) o; + return name.equals(that.name); + } + + @Override + public int hashCode() { + return Objects.hash(name); + } + + public String getNetworkId() { + return networkId; + } + + public String getPnfId() { + return pnfId; + } + + public String getLtpId() { + return ltpId; + } + + public String getName() { + return name; + } + + +} diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/Pnf.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/Pnf.java new file mode 100644 index 000000000..749c1d447 --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/Pnf.java @@ -0,0 +1,36 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology; + +import org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.graph.Vertex; + +import java.util.Objects; + +public class Pnf implements Vertex { + + private final String pnfName; + public Pnf(String pnfName){ + this.pnfName = pnfName; + } + + @Override + public int hashCode(){ + return pnfName.hashCode(); + } + + @Override + public String toString() { + return pnfName; + } + + @Override + public boolean equals (Object o){ + if (this == o) { + return true; + } + if (o instanceof Pnf) { + final Pnf other = (Pnf) o; + return Objects.equals(this.pnfName, other.pnfName); + } + return false; + } +} + diff --git a/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PnfName.java b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PnfName.java new file mode 100644 index 000000000..df4ac00cc --- /dev/null +++ b/core/sliPluginUtils/provider/src/main/java/org/onap/ccsdk/sli/core/slipluginutils/slitopologyutils/topology/PnfName.java @@ -0,0 +1,4 @@ +package org.onap.ccsdk.sli.core.slipluginutils.slitopologyutils.topology; + +public class PnfName { +} |