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