datarouter-node/src/main/java/org/onap/dmaap/datarouter/node/PathFinder.java

   1 /*******************************************************************************
   2  * ============LICENSE_START==================================================
   3  * * org.onap.dmaap
   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
  10  * *
  11  *  *      http://www.apache.org/licenses/LICENSE-2.0
  12  * *
  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====================================================
  19  * *
  20  * * ECOMP is a trademark and service mark of AT&T Intellectual Property.
  21  * *
  22  ******************************************************************************/
  23
  24
  25 package org.onap.dmaap.datarouter.node;
  26
  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;
  32
  33 /**
  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
  36  */
  37
  38 public class PathFinder {
  39
  40     private ArrayList<String> errors = new ArrayList<>();
  41     private HashMap<String, String> routes = new HashMap<>();
  42
  43     /**
  44      * Find routes from a specified origin to all of the nodes given a set of specified next hops.
  45      *
  46      * @param origin where we start
  47      * @param nodes where we can go
  48      * @param hops detours along the way
  49      */
  50     public 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) {
  54             known.add(n);
  55             ht.put(n, new HashMap<>());
  56         }
  57         for (NodeConfig.ProvHop ph : hops) {
  58             Hop h = getHop(known, ht, ph);
  59             if (h == null) {
  60                 continue;
  61             }
  62             if (ph.getVia().equals(ph.getTo())) {
  63                 errors.add(ph + " gives destination as via");
  64                 h.bad = true;
  65             }
  66         }
  67         for (String n : known) {
  68             if (n.equals(origin)) {
  69                 routes.put(n, "");
  70             }
  71             routes.put(n, plot(origin, n, ht.get(n)) + "/");
  72         }
  73     }
  74
  75     /**
  76      * Get list of errors encountered while finding paths
  77      *
  78      * @return array of error descriptions
  79      */
  80     public String[] getErrors() {
  81         return (errors.toArray(new String[errors.size()]));
  82     }
  83
  84     /**
  85      * Get the route from this node to the specified node
  86      *
  87      * @param destination node
  88      * @return list of node names separated by and ending with "/"
  89      */
  90     public String getPath(String destination) {
  91         String ret = routes.get(destination);
  92         if (ret == null) {
  93             return ("");
  94         }
  95         return (ret);
  96     }
  97
  98     private String plot(String from, String to, HashMap<String, Hop> info) {
  99         Hop nh = info.get(from);
 100         if (nh == null || nh.bad) {
 101             return (to);
 102         }
 103         if (nh.mark) {
 104             while (!nh.bad) {
 105                 nh.bad = true;
 106                 errors.add(nh.basis + " is part of a cycle");
 107                 nh = info.get(nh.basis.getVia());
 108             }
 109             return (to);
 110         }
 111         nh.mark = true;
 112         String x = plot(nh.basis.getVia(), to, info);
 113         nh.mark = false;
 114         if (nh.bad) {
 115             return (to);
 116         }
 117         return (nh.basis.getVia() + "/" + x);
 118     }
 119
 120     @Nullable
 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");
 124             return null;
 125         }
 126         if (!known.contains(ph.getTo())) {
 127             errors.add(ph + " references unknown destination node");
 128             return null;
 129         }
 130         HashMap<String, Hop> ht2 = ht.get(ph.getTo());
 131         Hop h = ht2.get(ph.getFrom());
 132         if (h != null) {
 133             h.bad = true;
 134             errors.add(ph + " gives duplicate next hop - previous via was " + h.basis.getVia());
 135             return null;
 136         }
 137         h = new Hop();
 138         h.basis = ph;
 139         ht2.put(ph.getFrom(), h);
 140         if (!known.contains(ph.getVia())) {
 141             errors.add(ph + " references unknown via node");
 142             h.bad = true;
 143             return null;
 144         }
 145         return h;
 146     }
 147
 148     private static class Hop {
 149
 150         boolean mark;
 151         boolean bad;
 152         NodeConfig.ProvHop basis;
 153     }
 154 }