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;
30 * Given a set of node names and next hops, identify and ignore any cycles and figure out the sequence of next hops to get from this node to any other node
33 public class PathFinder {
34 private static class Hop {
37 public NodeConfig.ProvHop basis;
40 private Vector<String> errors = new Vector<String>();
41 private Hashtable<String, String> routes = new Hashtable<String, String>();
44 * Get list of errors encountered while finding paths
46 * @return array of error descriptions
48 public String[] getErrors() {
49 return (errors.toArray(new String[errors.size()]));
53 * Get the route from this node to the specified node
55 * @param destination node
56 * @return list of node names separated by and ending with "/"
58 public String getPath(String destination) {
59 String ret = routes.get(destination);
66 private String plot(String from, String to, Hashtable<String, Hop> info) {
67 Hop nh = info.get(from);
68 if (nh == null || nh.bad) {
75 errors.add(nh.basis + " is part of a cycle");
76 nh = info.get(nh.basis.getVia());
81 String x = plot(nh.basis.getVia(), to, info);
86 return (nh.basis.getVia() + "/" + x);
90 * Find routes from a specified origin to all of the nodes given a set of specified next hops.
92 * @param origin where we start
93 * @param nodes where we can go
94 * @param hops detours along the way
96 public PathFinder(String origin, String[] nodes, NodeConfig.ProvHop[] hops) {
97 HashSet<String> known = new HashSet<String>();
98 Hashtable<String, Hashtable<String, Hop>> ht = new Hashtable<String, Hashtable<String, Hop>>();
99 for (String n : nodes) {
101 ht.put(n, new Hashtable<String, Hop>());
103 for (NodeConfig.ProvHop ph : hops) {
104 if (!known.contains(ph.getFrom())) {
105 errors.add(ph + " references unknown from node");
108 if (!known.contains(ph.getTo())) {
109 errors.add(ph + " references unknown destination node");
112 Hashtable<String, Hop> ht2 = ht.get(ph.getTo());
113 Hop h = ht2.get(ph.getFrom());
116 errors.add(ph + " gives duplicate next hop - previous via was " + h.basis.getVia());
121 ht2.put(ph.getFrom(), h);
122 if (!known.contains(ph.getVia())) {
123 errors.add(ph + " references unknown via node");
127 if (ph.getVia().equals(ph.getTo())) {
128 errors.add(ph + " gives destination as via");
133 for (String n : known) {
134 if (n.equals(origin)) {
137 routes.put(n, plot(origin, n, ht.get(n)) + "/");