1 /*******************************************************************************
2 * ============LICENSE_START==================================================
4 * * ===========================================================================
5 * * Copyright © 2017 AT&T Intellectual Property. All rights reserved.
6 * * ===========================================================================
7 * * Licensed under the Apache License, Version 2.0 (the "License");
8 * * you may not use this file except in compliance with the License.
9 * * You may obtain a copy of the License at
11 * * http://www.apache.org/licenses/LICENSE-2.0
13 * * Unless required by applicable law or agreed to in writing, software
14 * * distributed under the License is distributed on an "AS IS" BASIS,
15 * * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * * See the License for the specific language governing permissions and
17 * * limitations under the License.
18 * * ============LICENSE_END====================================================
20 * * ECOMP is a trademark and service mark of AT&T Intellectual Property.
22 ******************************************************************************/
25 package org.onap.dmaap.datarouter.node;
27 import java.util.ArrayList;
28 import java.util.HashMap;
29 import java.util.HashSet;
30 import org.jetbrains.annotations.Nullable;
31 import org.onap.dmaap.datarouter.node.NodeConfig.ProvHop;
34 * Given a set of node names and next hops, identify and ignore any cycles and figure out the sequence of next hops to
35 * get from this node to any other node.
40 private ArrayList<String> errors = new ArrayList<>();
41 private HashMap<String, String> routes = new HashMap<>();
44 * Find routes from a specified origin to all of the nodes given a set of specified next hops.
46 * @param origin where we start
47 * @param nodes where we can go
48 * @param hops detours along the way
50 PathFinder(String origin, String[] nodes, NodeConfig.ProvHop[] hops) {
51 HashSet<String> known = new HashSet<>();
52 HashMap<String, HashMap<String, Hop>> ht = new HashMap<>();
53 for (String n : nodes) {
55 ht.put(n, new HashMap<>());
57 for (NodeConfig.ProvHop ph : hops) {
58 Hop hop = getHop(known, ht, ph);
62 if (ph.getVia().equals(ph.getTo())) {
63 errors.add(ph + " gives destination as via");
67 for (String n : known) {
68 if (n.equals(origin)) {
71 routes.put(n, plot(origin, n, ht.get(n)) + "/");
76 * Get list of errors encountered while finding paths.
78 * @return array of error descriptions
80 String[] getErrors() {
81 return (errors.toArray(new String[0]));
85 * Get the route from this node to the specified node.
87 * @param destination node
88 * @return list of node names separated by and ending with "/"
90 String getPath(String destination) {
91 String ret = routes.get(destination);
98 private String plot(String from, String to, HashMap<String, Hop> info) {
99 Hop nh = info.get(from);
100 if (nh == null || nh.bad) {
106 errors.add(nh.basis + " is part of a cycle");
107 nh = info.get(nh.basis.getVia());
112 String route = plot(nh.basis.getVia(), to, info);
117 return (nh.basis.getVia() + "/" + route);
121 private Hop getHop(HashSet<String> known, HashMap<String, HashMap<String, Hop>> ht, ProvHop ph) {
122 if (!known.contains(ph.getFrom())) {
123 errors.add(ph + " references unknown from node");
126 if (!known.contains(ph.getTo())) {
127 errors.add(ph + " references unknown destination node");
130 HashMap<String, Hop> ht2 = ht.get(ph.getTo());
131 Hop hop = ht2.get(ph.getFrom());
134 errors.add(ph + " gives duplicate next hop - previous via was " + hop.basis.getVia());
139 ht2.put(ph.getFrom(), hop);
140 if (!known.contains(ph.getVia())) {
141 errors.add(ph + " references unknown via node");
148 private static class Hop {
152 NodeConfig.ProvHop basis;