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