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.HashSet;
28 import java.util.Hashtable;
29 import java.util.Vector;
32 * Given a set of node names and next hops, identify and ignore any cycles and figure out the sequence of next hops to
33 * get from this node to any other node
36 public class PathFinder {
38 private static class Hop {
42 NodeConfig.ProvHop basis;
45 private Vector<String> errors = new Vector<String>();
46 private Hashtable<String, String> routes = new Hashtable<String, String>();
49 * Get list of errors encountered while finding paths
51 * @return array of error descriptions
53 public String[] getErrors() {
54 return (errors.toArray(new String[errors.size()]));
58 * Get the route from this node to the specified node
60 * @param destination node
61 * @return list of node names separated by and ending with "/"
63 public String getPath(String destination) {
64 String ret = routes.get(destination);
71 private String plot(String from, String to, Hashtable<String, Hop> info) {
72 Hop nh = info.get(from);
73 if (nh == null || nh.bad) {
80 errors.add(nh.basis + " is part of a cycle");
81 nh = info.get(nh.basis.getVia());
86 String x = plot(nh.basis.getVia(), to, info);
91 return (nh.basis.getVia() + "/" + x);
95 * Find routes from a specified origin to all of the nodes given a set of specified next hops.
97 * @param origin where we start
98 * @param nodes where we can go
99 * @param hops detours along the way
101 public PathFinder(String origin, String[] nodes, NodeConfig.ProvHop[] hops) {
102 HashSet<String> known = new HashSet<String>();
103 Hashtable<String, Hashtable<String, Hop>> ht = new Hashtable<String, Hashtable<String, Hop>>();
104 for (String n : nodes) {
106 ht.put(n, new Hashtable<String, Hop>());
108 for (NodeConfig.ProvHop ph : hops) {
109 if (!known.contains(ph.getFrom())) {
110 errors.add(ph + " references unknown from node");
113 if (!known.contains(ph.getTo())) {
114 errors.add(ph + " references unknown destination node");
117 Hashtable<String, Hop> ht2 = ht.get(ph.getTo());
118 Hop h = ht2.get(ph.getFrom());
121 errors.add(ph + " gives duplicate next hop - previous via was " + h.basis.getVia());
126 ht2.put(ph.getFrom(), h);
127 if (!known.contains(ph.getVia())) {
128 errors.add(ph + " references unknown via node");
132 if (ph.getVia().equals(ph.getTo())) {
133 errors.add(ph + " gives destination as via");
138 for (String n : known) {
139 if (n.equals(origin)) {
142 routes.put(n, plot(origin, n, ht.get(n)) + "/");