Question

Create a class, Drone Router, that will determine the best (i.e. minimum cost) path between the distribution center and a specified waypoint. The DroneRouter class will implement the edu.metrostate.ics340.p3.Router interface (provided). Feature Specification Information Class Drone Router implements edu.metrostate.ics 340.p3. Router Constructors Drone Router() No-argument constructor Methods Input See Javadoc of Router.java Text file with format: Waypointi Waypoint2 routeCost Elements: Waypoint1: String Waypoint2 : String routeCost: int > 0 Delimiter space Output None, besides method return values Third Party You should review the Google Guava library for useful classes

the class is supoose to implement the provided interface Router implemement the methods as per the interface. Also provide junit test cases and test with a test file. please write in java its for a graph implementation. the interface is provided.

Answer 1

Working code implemented in Java and appropriate comments provided for better understanding:

Here I am attaching code for these 3 files:

• Router.java
• DroneRouterTest.java

package(package name is package):

• DroneRouter.java

Source code for Router.java:

public interface Router {

   /**
   * Value indicating there is no path from the source to the specified
   * destination
   */
   int NO_ROUTE = -1;

   /**
   * Loads the file containing waypoints pairs and the cost to travel between
   * them.
   *
   * @param routesFilePath path to the routes file
   * @param source the waypoint that is the source location, that is, the
   * starting point of all routs
   * @throws IllegalArgumentException if the file is not accessible or the source
   * location does not exist
   */
   void loadRoutes(String routesFilePath, String source);

   /**
   * Returns the route from the designated source waypoint to the specified
   * destination
   *
   * @param destination endpoint of route
   * @return array of waypoints representing the least expensive route from the
   * source to the destination (inclusive). The array is empty if no path
   * exists.
   * @throws IllegalArgumentException if destination does not exist in the route
   * file
   */
   String[] getRoute(String destination);

   /**
   * Returns the cost of the shortest route from the designated source waypoint to
   * the specified destination
   *
   * @param destination endpoint of route from the source waypoint
   * @return the cost in units, or {@link NO_ROUTE} if no route exists from the
   * source to the specified destination
   * @throws IllegalArgumentException if destination does not exist in the route
   * file
   * @throws NullPointerException if destination is {@code null}
   */
   int getPathCost(String destination);

}

Code Screenshots:

public interface Router í Value indicating there is no path from the source to the specified * destination int NO_ROUTE -1; Loads the file containing waypoints pairs and the cost to travel between * them. @param routesFilePath path to the routes file * @param source the waypoint that is the source location, that is, the starting point of all routs @throws IllegalArgumentException if the file is not accessible or the source location does not exist void loadRoutes(String routesFilePath, String source); 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 /** * Returns the route from the designated source waypoint to the specified * destination @param destination endpoint of route * @return array of waypoints representing the least expensive route from the source to the destination (inclusive). The array is empty if no path exists. @throws IllegalArgumentException if destination does not exist in the route file String[] getRoute(String destination); /** * Returns the cost of the shortest route from the designated source waypoint to * the specified destination 40 @param destination endpoint of route from the source waypoint @return the cost in units, or {@link NO_ROUTE} if no route exists from the source to the specified destination @throws IllegalArgumentException if destination does not exist in the route file @throws NullPointerException if destination is {@code null} 41 42 43 44 45 46 47 48 int getPathCost(String destination);

Source code for DroneRouterTest.java:

import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.Test;

import edu.metrostate.ics340.p3.msr812.DroneRouter;

class DroneRouterTest {

   @Test
   void test() {
       Router router = new DroneRouter();
       router.loadRoutes("routes0.txt", "A");
       assertArrayEquals(new String[] { "A", "B", "G" }, router.getRoute("G"));
       assertEquals(17, router.getPathCost("G"));
       assertThrows(IllegalArgumentException.class, () -> router.getRoute("Z"));
       assertArrayEquals(new String[] {}, router.getRoute("M"));
       assertEquals(Router.NO_ROUTE, router.getPathCost("M"));
   }

   @Test
   void test2() {
       Router router = new DroneRouter();
       router.loadRoutes("routes1.txt", "CHI");
       assertArrayEquals(new String[] { "CHI", "MSP", "DEN", "LAS" }, router.getRoute("LAS"));
       assertEquals(2600, router.getPathCost("DEN"));
       assertThrows(IllegalArgumentException.class, () -> router.getRoute("Z"));
       assertArrayEquals(new String[] {}, router.getRoute("STP"));
       assertEquals(Router.NO_ROUTE, router.getPathCost("STP"));
   }
}
Code Screenshots:

import static org.junit.jupiter.api.Assertions.assertArrayEquals; import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertThrows; import org.junit.jupiter.api.Test; import edu.metrostate.ics340.p3.msr812.Drone Router; class DroneRouterTest { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 v 24 25 26 27 28 29 30 31 32 33 @Test void test() { Router router = new DroneRouter(); router.loadRoutes ("routese.txt", "A"); assertArrayEquals(new String[] { "A", "B", "G" }, router.getRoute("G")); assertEquals(17, router.getPathCost("G")); assertThrows(IllegalArgumentException.class, () -> router.getRoute("Z")); assertArrayEquals(new String[] {}, router.getRoute("M")); assertEquals(Router.NO_ROUTE, router.getPathcost("M")); } @Test void test2() { Router router = new DroneRouter(); router.loadRoutes("routes1.txt", "CHI"); assertArrayEquals(new String[] { "CHI", "MSP", "DEN", "LAS" }, router.getRoute("LAS")); assertEquals(2600, router.getPathCost("DEN")); assertThrows (IllegalArgumentException.class, () -> router.getRoute("Z")); assertArrayEquals(new String[] {}, router.getRoute("STP")); assertEquals(Router.NO_ROUTE, router.getPathcost("STP")); }

Source code for DroneRouter.java:

package package;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.NavigableSet;
import java.util.Scanner;
import java.util.TreeSet;

import package.Router;

/*
* This DroneRouter class implements the Router interface. This class is
* responsible for interfacing between user command input and with the Dijsktra
* Algorithm. This class has inner classes of Graph, Edge, and Vertex.
*/
public class DroneRouter implements Router {

   // Saves the Drone starting point.
   private String startingPoint;
   // Graph array which holds all the paths/edges
   private Graph.Edge[] GRAPH = null;

   // Constructor for DroneRouter
   public DroneRouter() {
   }

   /*
   * Finds absolute file path, use buffered reader to count lines to instantiate
   * the Graph.Edge GRAPH array's length.
   *
   * Uses scanner to scan each line and create a edges into Graph.Edge GRAPH
   *
   * @param routesFilePath path to routing file
   *
   * @param startingPoint the initial starting point of the drone
   */
   @Override
   public void loadRoutes(String routesFilePath, String startingPoint) {
       this.startingPoint = startingPoint;
       String sentence = "";
       File file = new File(routesFilePath).getAbsoluteFile();

       BufferedReader reader = null;
       try {
           reader = new BufferedReader(new FileReader(file));
           int lines = 0;
           while (reader.readLine() != null)
               lines++;
           reader.close();
           GRAPH = new Graph.Edge[lines];
       } catch (IOException e1) {
           throw new IllegalArgumentException("Illegal Argument Exception, File Not Found: " + routesFilePath);
       }

       try {
           int counter = 0;
           Scanner input = new Scanner(file);
           while (input.hasNextLine()) {
               sentence = input.nextLine();
               String[] values = sentence.split("\\s+");
               GRAPH[counter] = new Graph.Edge(values[0], values[1], Integer.parseInt(values[2]));
               counter++;
           }
           input.close();

       } catch (FileNotFoundException e) {
           e.printStackTrace();
       }
   }

   /*
   * Finds route. Creates an instance of Graph with the provided Graph.Edge GRAPH
   * made by routing file. Runes the dijkstra algorithm in respect to the starting
   * point given iniitally.
   *
   * @param destination to find path to.
   */
   @Override
   public String[] getRoute(String destination) {
       Graph g = new Graph(GRAPH);
       g.dijkstra(startingPoint);

       return g.printPath(destination);
   }

   /*
   * Finds cost. Creates an instance of Graph with the provided Graph.Edge GRAPH
   * made by routing file. Runes the dijkstra algorithm in respect to the starting
   * point given iniitally.
   *
   * @param destination to find path to.
   */
   @Override
   public int getPathCost(String destination) {
       Graph g = new Graph(GRAPH);
       g.dijkstra(startingPoint);

       return g.printCost(destination);
   }
}

class Graph {
   // mapping of vertex names to Vertex objects, built from a set of Edges
   private final Map<String, Vertex> graph;
   private static ArrayList<String> temp = new ArrayList<String>();
   private static int cost = 0;

   /**
   * One edge of the graph (only used by Graph constructor)
   */
   public static class Edge {
       public final String source, destination;
       public final int weight;

       public Edge(String source, String destination, int weight) {
           this.source = source;
           this.destination = destination;
           this.weight = weight;
       }
   }

   /**
   * One vertex of the graph, with mappings of neighboring vertexes
   */
   public static class Vertex implements Comparable<Vertex> {
       public final String name;
       // MAX_VALUE assumed to be infinity
       public int weight = Integer.MAX_VALUE;
       public Vertex previous = null;
       public final Map<Vertex, Integer> neighbours = new HashMap<>();

       public Vertex(String name) {
           this.name = name;
       }

       /*
       * Will traverse and calculate which paths are taken to get from source to
       * destination. Will add the node/edge to a temp arraylist. Arraylist is
       * converted to array and returned.
       *
       * Will return an empty array if null edge.
       */
       private String[] printPath() {

           if (this == this.previous) {
               temp.add(this.name);
           } else if (this.previous == null) {
               String[] emptyArray = new String[0];
               return emptyArray;
           } else {
               this.previous.printPath();
               temp.add(this.name);
           }
           String[] path = new String[temp.size()];
           path = temp.toArray(path);
           return path;
       }

       /*
       * Will traverse and calculate which costs are taken to get from source to
       * destination. Will add the node/edge to a running tally.
       *
       * Will return -1 if null.
       */
       private int printCost() {
           if (this == this.previous) {
               cost += this.weight;
           } else if (this.previous == null) {
               return Router.NO_ROUTE;
           } else {
               this.previous.printPath();
               cost += this.weight;
           }
           return cost;
       }

       public int compareTo(Vertex other) {
           if (weight == other.weight)
               return name.compareTo(other.name);

           return Integer.compare(weight, other.weight);
       }
   }

   /**
   * Builds a graph from a set of edges
   */
   public Graph(Edge[] edges) {
       graph = new HashMap<>(edges.length);

       // one pass to find all vertices
       for (Edge e : edges) {
           if (!graph.containsKey(e.source))
               graph.put(e.source, new Vertex(e.source));
           if (!graph.containsKey(e.destination))
               graph.put(e.destination, new Vertex(e.destination));
       }

       // another pass to set neighbouring vertices
       for (Edge e : edges) {
           graph.get(e.source).neighbours.put(graph.get(e.destination), e.weight);
           // graph.get(e.destination).neighbours.put(graph.get(e.source), e.weight); //
           // also do this for
           // an undirected graph
       }
   }

   /**
   * Runs dijkstras algorithm with the startPoint specified earlier.
   *
   * @param startingPoint the vertex to start on.
   */
   public void dijkstra(String startingPoint) {
       if (!graph.containsKey(startingPoint)) {
           throw new IllegalArgumentException("Illegal Argument Exception on value: " + startingPoint);
       }
       final Vertex source = graph.get(startingPoint);
       NavigableSet<Vertex> q = new TreeSet<>();

       // set-up vertices
       for (Vertex v : graph.values()) {
           v.previous = v == source ? source : null;
           v.weight = v == source ? 0 : Integer.MAX_VALUE;
           q.add(v);
       }
       dijkstra(q);
   }

   /**
   * Implementation of dijkstra's algorithm using a binary heap.
   */
   private void dijkstra(final NavigableSet<Vertex> q) {
       Vertex u, v;
       while (!q.isEmpty()) {
           // vertex with shortest weightance (first iteration will return source)
           u = q.pollFirst();
           if (u.weight == Integer.MAX_VALUE)
               break; // we can ignore u (and any other remaining vertices) since they are unreachable

           // look at weightances to each neighbour
           for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
               v = a.getKey(); // the neighbour in this iteration

               final int alternateDist = u.weight + a.getValue();
               if (alternateDist < v.weight) { // shorter path to neighbour found
                   q.remove(v);
                   v.weight = alternateDist;
                   v.previous = u;
                   q.add(v);
               }
           }
       }
   }

   /**
   * Helper method to get the path of the vertices taken from stratingPoint to
   * destination
   *
   * @param destination
   * @return array
   */
   public String[] printPath(String destination) {
       if (!graph.containsKey(destination)) {
           throw new IllegalArgumentException("Invalid Destination, " + destination);
       } else {
           Graph.temp = new ArrayList<String>();
           return graph.get(destination).printPath();
       }
   }

   /**
   * Helper method to get the cost of the vertices taken from stratingPoint to
   * destination
   *
   * @param destination
   * @return cost
   */
   public int printCost(String destination) {
       if (!graph.containsKey(destination)) {
           throw new IllegalArgumentException("Invalid Destination, " + destination);
       } else {
           Graph.cost = 0;
           return graph.get(destination).printCost();
       }
   }
}

Code Screenshots:

1 m * package package; 2 3 import java.io.BufferedReader; 4 import java.io.File; 5 import java.io.FileNotFoundException; 6 import java.io.FileReader; 7 import java.io.IOException; g 8 import java.util.ArrayList; 9 9 import java.util.HashMap; 1A 10 import java.util.Map; 11 import java.util.NavigableSet; 12 12 import java.util.Scanner; 13 import java.util.TreeSet; 14 12 15 import package.Router; 16 17 v /* 10 18 * This DroneRouter class implements the Router interface. This class is 10 19 responsible for interfacing between user command input and with the Dijsktra ba 20 Algorithm. This class has inner classes of Graph, Edge, and Vertex. 24 21 22 public class DroneRouter implements Router { 23 24 24 // Saves the Drone starting point. 25 private String startingPoint; 20 26 Il Graph array which holds all the path edges 27 private Graph.Edge [] GRAPH = null; 28 29 // Constructor for Drone Router 30 public DroneRouter() { 31 32 - 33 /* 34 * Finds absolute file path, use buffered reader to count lines to instantiate . 35 * the Graph. Edge GRAPH array's length. 30 36 37 > * Uses scanner to scan each line and create a edges into Graph. Edge GRAPH 38 39 * @param routesFilePath path to routing file 40 Te 41 * @param startingPoint the initial starting point of the drone T 42 Ta 43 @Override T 44 v public void loadRoutes (String routesFilePath, String startingPoint) { 45 this.starting point = startingPoint; T 46 Te String sentence 47 TE File file = new File(routesFilePath).getAbsoluteFile(); 48 Te 49 BufferedReader reader = null; 50 try { 51 reader new BufferedReader(new FileReader(file)); 52 int lines = 0; - 53 while (reader.readLine() != null) 54 linesH; 55 reader.close(); 56 GRAPH = new Graph.Edge[lines]; 57 } catch (IOException el) { throw new IllegalArgumentException("Illegal Argument Exception, File Not Found: " 59 } 60 } 58 + routesFilePath);

try { int counter @; Scanner input new Scanner(file); while (input.hasNextLine()) { sentence input.nextLine(); String[] values sentence.split("\\s+"); GRAPH[counter] = new Graph.Edge(values[0], values[1], Integer.parseInt(values[2])); counter++; } input.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } } Finds route. Creates an instance of Graph with the provided Graph. Edge GRAPH * made by routing file. Runes the dijkstra algorithm in respect to the starting * point given iniitally. * @param destination to find path to. @Override public String[] getRoute(String destination) { Graph g = new Graph(GRAPH); g.dijkstra(startingPoint); return g.printPath(destination); 61 62 63 64 65 66 -- 67 68 co 69 70 - 71 . 72 - 73 - 74 75 76 19 77 20 78 - 79 80 81 82 83 84 85 86 87 88 89 90 91 91 02 92 93 02 A 94 OS 95 06 96 07 97 ag 98 ga 99 100 101 101 102 102 103 194 104 195 105 186 100 107 107 188 108 400 109 440 110 444 111 44 112 443 113 114 114 115 116 117 118 119 120 نہا /* * Finds cost. Creates an instance of Graph with the provided Graph. Edge GRAPH * made by routing file. Runes the dijkstra algorithm in respect to the starting point given iniitally. * @param destination to find path to. @Override public int getPathcost(String destination) { Graph g = new Graph(GRAPH); g.dijkstra(startingPoint); return g.printCost (destination); } } class Graph { // mapping of vertex names to Vertex objects, built from a set of Edges private final Map<String, Vertex> graph; private static ArrayList<String> temp = new ArrayList<String>(); private static int cost = 0; /** * One edge of the graph (only used by Graph constructor) public static class Edge { public final String source, destination; public final int weight;

121 v public Edge(String source, String destination, int weight) { this.source source; this.destination destination; this.weight = weight; } } /** * One vertex of the graph, with mappings of neighboring vertexes */ public static class Vertex implements Comparable<Vertex> { public final String name; // MAX_VALUE assumed to be infinity public int weight Integer.MAX_VALUE; public Vertex previous null; public final Map<Vertex, Integer> neighbours = new HashMap<>(); public Vertex(String name) { this.name = name; } /* * Will traverse and calculate which paths are taken to get from source to destination. Will add the node/edge to a temp arraylist. Arraylist is converted to array and returned. 122 123 124 124 125 126 125 120 127 127 128 129 129 130 130 131 131 132 132 432 133 124 134 100 135 136 136 42 137 40 138 100 139 10 140 24 141 142 v 44 143 144 145 145 116 146 12 147 120 148 149 v 150 151 152 153 v 154 155 ar 156 157 12 158 159 160 100 161 102 162 163 - 164 10 165 166 167 168 100 169 - 170 171 12 172 25. 173 - 174 -- 175 . Will return an empty array if null edge. * private String[] printPath() { if (this == this.previous) { temp.add(this.name); } else if (this.previous null) { String[] emptyArray new String[@]; return emptyArray; } else { this.previous.printPath(); temp.add(this.name); String[] path = new String[temp.size()]; path temp.toArray(path); return path; } } * Will traverse and calculate which costs are taken to get from source to destination. Will add the node/edge to a running tally. * Will return -1 if null. private int printCost() { if (this this.previous) { cost += this.weight; } else if (this.previous null) { return Router.NO_ROUTE; } else { this.previous.printPath(); cost += this.weight; 176 177 178 179 180 } return cost;

public int compareTo(Vertex other) { if (weight other.weight) return name.compareTo(other.name); return Integer.compare (weight, other weight); } } /** * Builds a graph from a set of edges */ public Graph(Edge [] edges) { graph = new HashMap<> (edges.length); // one pass to find all vertices for (Edge e edges) { if (graph.containsKey(e. source)) graph.put(e. source, new Vertex(e.source)); if (graph.containskey (e.destination)) graph.put(e.destination, new Vertex(e.destination)); بها 181 182 183 103 184 104 103 185 186 104 187 107 188 100 189 190 130 191 132 192 193 194 *** 193 195 196 130 197 198 - 130 199 13 200 200 201 201 202 203 204 205 205 206 207 208 209 210 211 212 213 214 215 216 14 217 218 219 12 220 221 222 13 223 12 224 225 100 226 102 227 v 100 228 100 229 230 231 . 232 w 233 234 * 235 236 237 238 239 // another pass to set neighbouring vertices for (Edge e edges) { graph.get(e.source).neighbours.put(graph.get(e.destination), e.weight); Il graph.get(e.destination).neighbours.put(graph.get(e.source), e.weight); // // also do this for // an undirected graph Runs dijkstras algorithm with the startPoint specified earlier. @param startingPoint the vertex to start on. * public void dijkstra(String startingPoint) { if (graph.containskey (startingPoint)) { throw new IllegalArgumentException("Illegal Argument Exception on value: ". final Vertex source graph.get(startingPoint); NavigableSet<Vertex> q = new Treeset<>(); startingPoint); } // set-up vertices for (Vertex v graph.values()) { v.previous V source source null; v.weight V == source Integer.MAX_VALUE; q.add(v); dijkstra(q); } /** * Implementation of dijkstra's algorithm using a binary heap. *) private void dijkstra(final Navigableset Vertex> 0) { Vertex u, V; while (!q.isEmpty()) { 240

U = // vertex with shortest weightance (first iteration will return source) q.pollFirst(); if (u.weight Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable // look at weightances to each neighbour for (Map.Entry<vertex, Integer a : u.neighbours.entrySet()) { V = a.getKey(); // the neighbour in this iteration final int alternateDist = u.weight + a.getValue(); if (alternateDist <v.weight) { shorter path to neighbour found q.remove(v); v.weight = alternateDist; v.previous = u; q.add(v); } } } Helper method to get the path of the vertices taken from stratingPoint to * destination 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 @param destination @return array public String[] printPath(String destination) { if (graph.containsKey(destination)) { throw new IllegalArgumentException("Invalid Destination, } else { Graph.temp = new ArrayList<String>(); return graph.get(destination).printPath(); + destination); ܝܟ } /** Helper method to get the cost of the vertices taken from stratingPoint to destination @param destination @return cost public int printCost(String destination) { if (graph.containskey (destination)) { throw new IllegalArgumentException("Invalid Destination, destination); } else { Graph.cost = 0; return graph.get(destination).printCost(); } } }

Input Files:

routes0.txt:

A B 5
B C 10
B G 12
G C 5
C D 15
C E 2
D F 4
G E 2
E F 2
A E 3
L M 10

routes1.txt:

CHI MSP 2400
DEN LAS 1400
NYC DZS 8300
STP MSP 30
LAS DZS 200
NYC CHI 100
MSP DEN 200

Input Screenshots:

x routes.txt - No... File Edit Format View Help AB 5 B C 10 B G 12 GC 5 CD 15 CE 2 DF4 GE 2 EF 2 AE 3 L M 10 routes 1.txt -.. File Edit Format View Help CHI MSP 2400 DEN LAS 1400 NYC DZS 8300 STP MSP 30 LAS DZS 200 NYC CHI 100 MSP DEN 200 10 Windows (CRLF) UTF-8 Windows (CRLF) UTF-8

Note: Output is None, besides method return values. That's why I am not uploading any output for this problem.

Hope it helps, if you like the answer give it a thumbs up. Thank you.