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