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

   1 /*******************************************************************************\r
   2  * ============LICENSE_START==================================================\r
   3  * * org.onap.dmaap\r
   4  * * ===========================================================================\r
   5  * * Copyright © 2017 AT&T Intellectual Property. All rights reserved.\r
   6  * * ===========================================================================\r
   7  * * Licensed under the Apache License, Version 2.0 (the "License");\r
   8  * * you may not use this file except in compliance with the License.\r
   9  * * You may obtain a copy of the License at\r
  10  * * \r
  11  *  *      http://www.apache.org/licenses/LICENSE-2.0\r
  12  * * \r
  13  *  * Unless required by applicable law or agreed to in writing, software\r
  14  * * distributed under the License is distributed on an "AS IS" BASIS,\r
  15  * * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  16  * * See the License for the specific language governing permissions and\r
  17  * * limitations under the License.\r
  18  * * ============LICENSE_END====================================================\r
  19  * *\r
  20  * * ECOMP is a trademark and service mark of AT&T Intellectual Property.\r
  21  * *\r
  22  ******************************************************************************/\r
  23 \r
  24 \r
  25 package org.onap.dmaap.datarouter.node;\r
  26 \r
  27 import java.util.*;\r
  28 \r
  29 /**\r
  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\r
  31  */\r
  32 \r
  33 public class PathFinder {\r
  34         private static class Hop        {\r
  35                 public boolean  mark;\r
  36                 public boolean  bad;\r
  37                 public NodeConfig.ProvHop       basis;\r
  38         }\r
  39         private Vector<String> errors = new Vector<String>();\r
  40         private Hashtable<String, String> routes = new Hashtable<String, String>();\r
  41         /**\r
  42          *      Get list of errors encountered while finding paths\r
  43          *      @return array of error descriptions\r
  44          */\r
  45         public String[] getErrors() {\r
  46                 return(errors.toArray(new String[errors.size()]));\r
  47         }\r
  48         /**\r
  49          *      Get the route from this node to the specified node\r
  50          *      @param destination node\r
  51          *      @return list of node names separated by and ending with "/"\r
  52          */\r
  53         public String getPath(String destination) {\r
  54                 String ret = routes.get(destination);\r
  55                 if (ret == null) {\r
  56                         return("");\r
  57                 }\r
  58                 return(ret);\r
  59         }\r
  60         private String plot(String from, String to, Hashtable<String, Hop> info) {\r
  61                 Hop nh = info.get(from);\r
  62                 if (nh == null || nh.bad) {\r
  63                         return(to);\r
  64                 }\r
  65                 if (nh.mark) {\r
  66                         // loop detected;\r
  67                         while (!nh.bad) {\r
  68                                 nh.bad = true;\r
  69                                 errors.add(nh.basis + " is part of a cycle");\r
  70                                 nh = info.get(nh.basis.getVia());\r
  71                         }\r
  72                         return(to);\r
  73                 }\r
  74                 nh.mark = true;\r
  75                 String x = plot(nh.basis.getVia(), to, info);\r
  76                 nh.mark = false;\r
  77                 if (nh.bad) {\r
  78                         return(to);\r
  79                 }\r
  80                 return(nh.basis.getVia() + "/" + x);\r
  81         }\r
  82         /**\r
  83          *      Find routes from a specified origin to all of the nodes given a set of specified next hops.\r
  84          *      @param origin   where we start\r
  85          *      @param nodes    where we can go\r
  86          *      @param hops     detours along the way\r
  87          */\r
  88         public PathFinder(String origin, String[] nodes, NodeConfig.ProvHop[] hops) {\r
  89                 HashSet<String> known = new HashSet<String>();\r
  90                 Hashtable<String, Hashtable<String, Hop>> ht = new Hashtable<String, Hashtable<String, Hop>>();\r
  91                 for (String n: nodes) {\r
  92                         known.add(n);\r
  93                         ht.put(n, new Hashtable<String, Hop>());\r
  94                 }\r
  95                 for (NodeConfig.ProvHop ph: hops) {\r
  96                         if (!known.contains(ph.getFrom())) {\r
  97                                 errors.add(ph + " references unknown from node");\r
  98                                 continue;\r
  99                         }\r
 100                         if (!known.contains(ph.getTo())) {\r
 101                                 errors.add(ph + " references unknown destination node");\r
 102                                 continue;\r
 103                         }\r
 104                         Hashtable<String, Hop> ht2 = ht.get(ph.getTo());\r
 105                         Hop h = ht2.get(ph.getFrom());\r
 106                         if (h != null) {\r
 107                                 h.bad = true;\r
 108                                 errors.add(ph + " gives duplicate next hop - previous via was " + h.basis.getVia());\r
 109                                 continue;\r
 110                         }\r
 111                         h = new Hop();\r
 112                         h.basis = ph;\r
 113                         ht2.put(ph.getFrom(), h);\r
 114                         if (!known.contains(ph.getVia())) {\r
 115                                 errors.add(ph + " references unknown via node");\r
 116                                 h.bad = true;\r
 117                                 continue;\r
 118                         }\r
 119                         if (ph.getVia().equals(ph.getTo())) {\r
 120                                 errors.add(ph + " gives destination as via");\r
 121                                 h.bad = true;\r
 122                                 continue;\r
 123                         }\r
 124                 }\r
 125                 for (String n: known) {\r
 126                         if (n.equals(origin)) {\r
 127                                 routes.put(n, "");\r
 128                         }\r
 129                         routes.put(n, plot(origin, n, ht.get(n)) + "/");\r
 130                 }\r
 131         }\r
 132 }\r