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.config;
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.config.NodeConfig;
32 import org.onap.dmaap.datarouter.node.config.NodeConfig.ProvHop;
35 * Given a set of node names and next hops, identify and ignore any cycles and figure out the sequence of next hops to
36 * get from this node to any other node.
39 public class PathFinder {
41 private final ArrayList<String> errors = new ArrayList<>();
42 private final HashMap<String, String> routes = new HashMap<>();
45 * Find routes from a specified origin to all of the nodes given a set of specified next hops.
47 * @param origin where we start
48 * @param nodes where we can go
49 * @param hops detours along the way
51 public PathFinder(String origin, String[] nodes, NodeConfig.ProvHop[] hops) {
52 HashSet<String> known = new HashSet<>();
53 HashMap<String, HashMap<String, Hop>> ht = new HashMap<>();
54 for (String n : nodes) {
56 ht.put(n, new HashMap<>());
58 for (NodeConfig.ProvHop ph : hops) {
59 Hop hop = getHop(known, ht, ph);
63 if (ph.getVia().equals(ph.getTo())) {
64 errors.add(ph + " gives destination as via");
68 for (String n : known) {
69 if (n.equals(origin)) {
72 routes.put(n, plot(origin, n, ht.get(n)) + "/");
77 * Get list of errors encountered while finding paths.
79 * @return array of error descriptions
81 public String[] getErrors() {
82 return (errors.toArray(new String[0]));
86 * Get the route from this node to the specified node.
88 * @param destination node
89 * @return list of node names separated by and ending with "/"
91 public String getPath(String destination) {
92 String ret = routes.get(destination);
99 private String plot(String from, String to, HashMap<String, Hop> info) {
100 Hop nh = info.get(from);
101 if (nh == null || nh.bad) {
107 errors.add(nh.basis + " is part of a cycle");
108 nh = info.get(nh.basis.getVia());
113 String route = plot(nh.basis.getVia(), to, info);
118 return (nh.basis.getVia() + "/" + route);
122 private Hop getHop(HashSet<String> known, HashMap<String, HashMap<String, Hop>> ht, ProvHop ph) {
123 if (!known.contains(ph.getFrom())) {
124 errors.add(ph + " references unknown from node");
127 if (!known.contains(ph.getTo())) {
128 errors.add(ph + " references unknown destination node");
131 HashMap<String, Hop> ht2 = ht.get(ph.getTo());
132 Hop hop = ht2.get(ph.getFrom());
135 errors.add(ph + " gives duplicate next hop - previous via was " + hop.basis.getVia());
140 ht2.put(ph.getFrom(), hop);
141 if (!known.contains(ph.getVia())) {
142 errors.add(ph + " references unknown via node");
149 private static class Hop {
153 NodeConfig.ProvHop basis;