//

// Frontier

//

// This class implements either a FIFO list (a queue) or a LIFO list (a stack)

// of Node objects, with the kind of list determined by which method is

// used to insert new Node objects into the list. In either case, the

// "removeTop" method extracts and returns the next node to be ejected from

// the list. If the "addToBottom" method is used to insert nodes, then the

// Frontier object will act as a queue. If the "addToTop" method is used to

// insert nodes, then the Frontier object will act as a stack. Both of these

// insertion methods are overloaded to accept either individual Node

// objects or lists of multiple Node objects. This class is intended to

// to be used to implement the frontier (i.e., the "fringe" or "open list")

// of nodes in a search tree.

//

// David Noelle -- Created Sun Feb 11 18:39:40 PST 2007

// Modified Wed Sep 15 00:09:35 PDT 2010

// (Implemented overloaded "contains" function.)

// Modified Tue Sep 11 16:03:41 PDT 2018

// (Improved efficiency of "contains" function.)

//

import java.util.*;

public class Frontier {

List fringe;

Set fringeStateNames;

// Default constructor ...

public Frontier() {

fringe = new LinkedList();

fringeStateNames = new HashSet();

}

// isEmpty -- Return true if and only if there are currently no nodes in

// the frontier.

public boolean isEmpty() {

return (fringe.isEmpty());

}

// removeTop -- Return the Node object at the top of the frontier

// list. Also, remove this node from the frontier. Return null if the

// frontier is empty.

public Node removeTop() {

if (fringe.isEmpty()) {

return (null);

} else {

Node top = fringe.get(0);

fringe.remove(0);

fringeStateNames.remove(top.loc.name);

return (top);

}

}

// addToTop -- Add the given Node object to the top of the frontier

// list.

public void addToTop(Node leaf) {

fringe.add(0, leaf);

fringeStateNames.add(leaf.loc.name);

}

// addToTop -- Add the given list of Node objects to the top of the

// frontier list.

public void addToTop(List leaves) {

for (Node leaf : leaves) {

addToTop(leaf);

}

}

// addToBottom -- Add the given Node object to the bottom of the

// frontier list.

public void addToBottom(Node leaf) {

fringe.add(leaf);

fringeStateNames.add(leaf.loc.name);

}

// addToBottom -- Add the given list of Node objects to the bottom of

// the frontier list.

public void addToBottom(List leaves) {

for (Node leaf : leaves) {

addToBottom(leaf);

}

}

// contains -- Return true if and only if the frontier contains a

// Node with the given Location name.

public boolean contains(String name) {

// This is an efficient way to check the frontier for a node

// with a given state, by using a HashSet.

if (fringeStateNames.contains(name)) {

return (true);

} else {

// The location was not found in the fringe ...

return (false);

}

}

// contains -- Return true if and only if the frontier contains a

// Node with the given Location object as its state.

public boolean contains(Location loc) {

return (contains(loc.name));

}

// contains -- Return true if and only if the frontier contains an

// equivalent Node (with regard to the Location) to the one provided

// as an argument.

public boolean contains(Node leaf) {

return (contains(leaf.loc));

}

}

//Location

// // Location // // This class implements a place on a map. It is a single "state" in the // "state space" to be searched for a short route from one location to // another. Each location includes a textual name, a pair of Cartesian // coordinates, and a collection of Road objects which encode the immediate // routes leading away from this location. Note that textual names are // assumed to be unique; two locations are considered the same if they have // the same name. // // David Noelle -- Sun Feb 11 17:37:21 PST 2007 //

import java.io.*; import java.util.*;

public class Location { public String name = ""; public double longitude = 0.0; public double latitude = 0.0; public List roads;

// Default constructor ... public Location() { this.roads = new ArrayList(); }

// Constructor with location name specified ... public Location(String name) { this(); this.name = name; }

// Constructor with location name and coordinates specified ... public Location(String name, double longitude, double latitude) { this(name); this.longitude = longitude; this.latitude = latitude; }

// equals -- Return true if and only if this location has the same name // as the argument location. public boolean equals(Location loc) { return (loc.name.equals(this.name)); }

// read -- Read a location description from the given stream into this // object. At minimum, a name must be read from the stream. Optionally, // coordinates may also be specified as a pair of double precision // floating point numbers. Return true if at least a name was read and // false otherwise. public boolean read(BufferedReader str) { try { String thisLine = str.readLine(); if (thisLine == null) // No more input, at all ... return (false); Scanner inScanner = new Scanner(thisLine); inScanner.useDelimiter("\\s+"); if (inScanner.hasNext()) { // There is something to read ... name = inScanner.next(); if (inScanner.hasNextDouble()) { // There is a longitude to read ... longitude = inScanner.nextDouble(); if (inScanner.hasNextDouble()) { // There is a latitude to read ... latitude = inScanner.nextDouble(); } } // At least a name was successfully read ... inScanner.close(); return (true); } else { inScanner.close(); // Did not even read a name ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// write -- Write the name of this location to the given stream. If the // "showCoords" argument is true, then also output the Cartesian // coordinates of this location, separated by blanks, on the same line. public void write(OutputStream str, boolean showCoords) { PrintWriter out = new PrintWriter(str, true); out.printf("%s", name); if (showCoords) { out.printf(" %f %f", longitude, latitude); } }

// findRoad -- Search the collection of roads leading out of this // location for one that leads directly to the argument destination // location. Return this Road object if it is found, or null if no // matching road is found. public Road findRoad(Location destination) { for (Road r : roads) { if (r.toLocation.equals(destination)) return (r); } return (null); }

// recordRoad -- Add the given Road object to the collection of roads // leading out of this location. public void recordRoad(Road r) { roads.add(r); }

}

//map

// // Map // // This class implements a simple street map for the purposes of shortest-path // search. It makes use of Location objects to encode specific locations on // the map and Road objects to encode direct connections between locations. // These maps are designed to be read from simple text files. In particular, // two files are needed to specify a map: a location file and a road file. // The location file contains a list of all locations on the map, with one // location per line. The road file contains a list of all road segments on // the map, with one road segment per line. The pathnames of these two files // are stored in the Map object, so the files can be specified in advance of // their being read and parsed. The map is stored as a collection of // Location objects, with each Location being given the responsibility of // maintaining all of the Road objects corresponding to road segments leading // out of it. // // David Noelle -- Sun Feb 11 18:05:18 PST 2007 //

import java.io.*; import java.util.*;

public class Map { String locationFilename = "locations.dat"; String roadFilename = "roads.dat"; List locations;

// Default constructor ... public Map() { this.locations = new ArrayList(); }

// Constructor with filenames specified ... public Map(String locationFilename, String roadFilename) { this(); this.locationFilename = locationFilename; this.roadFilename = roadFilename; }

// setLocationFilename -- Record the given pathname of a location file for // later use during map reading. public void setLocationFilename(String filename) { locationFilename = filename; }

// setRoadFilename -- Record the given pathname of a road file for later // use during map reading. public void setRoadFilename(String filename) { roadFilename = filename; }

// promptForFilenames -- Using the standard output stream and the standard // input stream, prompt the user to input the pathnames for a location // file and for a road file. Record the input pathnames in this Map object // for later use during map reading. Return false on error. public boolean promptForFilenames() { try { InputStreamReader converter = new InputStreamReader(System.in); BufferedReader in = new BufferedReader(converter); String buffer;

System.out.println("Enter the name of the location file:"); buffer = in.readLine(); setLocationFilename(buffer); System.out.println("Enter the name of the road file:"); buffer = in.readLine(); setRoadFilename(buffer); } catch (IOException e) { // Something went wrong ... return (false); } return (true); }

// findLocation -- Search through the collection of locations on // this map for one with the given textual name. Return a reference // to the corresponding Location object, or null if no such location // is found. public Location findLocation(String name) { for (Location loc : locations) { if (loc.name.equals(name)) return (loc); } return (null); }

// recordLocation -- Add the given Location object to the collection of // locations for this map. public void recordLocation(Location loc) { locations.add(loc); }

// readLocations -- Attempt to open the location file specified by the // appropriate pathname stored in this Map object. If this file can // be opened for reading, read a collection of locations from this file // into the Map object's collection of Location objects. Return false // on error. public boolean readLocations() { try { File locFile = new File(locationFilename); if (locFile.exists() && locFile.canRead()) { FileInputStream locFileIn = new FileInputStream(locFile); InputStreamReader locISReader = new InputStreamReader(locFileIn); BufferedReader locBufferedReader = new BufferedReader(locISReader); // Allocate storage for the first location to be read ... Location loc = new Location(); while (loc.read(locBufferedReader)) { // Record location in the map ... recordLocation(loc); // Allocate storage for the next location ... loc = new Location(); } return (true); } else { // The file cannot be read ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// readRoads -- Attempt to open the road file specified by the appropriate // pathname stored in this Map object. If this file can be opened for // reading, read a collection of roads from this file. Generate // corresponding Road objects and store those objects in the appropriate // Location objects in this Map object's collection of locations. Note // that this means that the map must know about all locations on the map // before a road file is read. This can be done by calling the // "readLocations" method before calling this method. Return false on // error. public boolean readRoads() { try { File roadFile = new File(roadFilename); if (roadFile.exists() && roadFile.canRead()) { FileInputStream roadFileIn = new FileInputStream(roadFile); InputStreamReader roadISReader = new InputStreamReader(roadFileIn); BufferedReader roadBufferedReader = new BufferedReader(roadISReader); // Allocate storage for the first road segment ot be read ... Road r = new Road(); while (r.read(roadBufferedReader)) { // Fill in connections to location objects ... r.fromLocation = findLocation(r.fromLocationName); if (r.fromLocation == null) { System.err.printf("The location, %s, is not known. ", r.fromLocationName); roadBufferedReader.close(); return (false); } r.toLocation = findLocation(r.toLocationName); if (r.toLocation == null) { System.err.printf("The location, %s, is not known. ", r.toLocationName); roadBufferedReader.close(); return (false); } // Record the road in the appropriate location ... r.fromLocation.recordRoad(r); // Allocate storage for the next road segment ... r = new Road(); } return (true); } else { // The specified road file could not be read ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// readMap -- Prompt the user for the pathnames of a location file and // a road file, and then read those files into this Map object. Return // false on error. public boolean readMap() { return (promptForFilenames() && readLocations() && readRoads()); }

}

//NODE

// // Node // // This class implements a node in a search tree being constructed to find // a shortest path from one location to another on a map. Each node includes // a reference to the corresponding location "state", a reference to its // parent in the search tree (i.e., the "parent" node), and a collection // of children nodes which remains empty until the node is expanded. Each // Node object also records the depth of the node in the search tree and // the partial path cost from the initial node in the search tree to // this one. This class provides two noteworthy methods. First, the // "expand" method fills in the "children" list of this node, using // information embedded in this node's Location object. Second, the // "reportSolution" recursive method uses the "parent" references of // nodes in the search tree in order to output the path from the // initial node of the search tree to this node. // // David Noelle -- Sun Feb 11 18:26:42 PST 2007 // Modified Tue Sep 11 14:57:53 PDT 2018 //

import java.io.*; import java.util.*;

public class Node { public Location loc; public Node parent; public List children; public int depth = 0; public double partialPathCost = 0.0;

// Default constructor ... public Node() { this.children = new ArrayList(); }

// Constructor with Location object specified ... public Node(Location loc) { this(); this.loc = loc; }

// Constructor with Location object and parent node specified ... public Node(Location loc, Node parent) { this(loc); this.parent = parent; }

// expand -- Fill in the collection of children of this node, stored in // it's "children" variable. Make sure that each child is appropriately // linked into the search tree, and make sure that it's partial path cost // is correctly calculated. public void expand() { children.removeAll(children); for (Road r : loc.roads) { Node child = new Node(r.toLocation, this); child.depth = this.depth + 1; child.partialPathCost = this.partialPathCost + r.cost; children.add(child); } }

// isDestination -- Return true if and only if the name of the // location corresponding to this node matches the provided argument. public boolean isDestination(String destinationName) { return (loc.name.equals(destinationName)); }

// reportSolution -- Output a textual description of the path from the // root of the search tree (i.e., the initial node) to this node, sending // the description to the given stream. Note that this method is // recursive; a recursive call outputs the path up to the parent of this // node before the final road segment in the path is described. public void reportSolution(OutputStream str) { PrintWriter out = new PrintWriter(str, true); if (parent == null) { // This is the starting point ... out.printf("START AT "); loc.write(str, false); out.printf(". "); } else { // First provide the solution up until this point ... parent.reportSolution(str); // Now report the road segment to this point ... out.printf("TAKE "); (parent.loc.findRoad(loc)).write(str, true); out.printf(". "); } }

}

//PZERO

// // Pzero // // This class provides a "main" method that acts as a driver program for // evaluating breadth-first search and depth-first search algorithms, as // applied to shortest-path searches on a map. A Map object is used to // read in and record a map from two files: one containing a list of // locations and the other containing a list of road segments. The user // is then prompted for a starting location on this map and a destination // location. The two search algorithms in question are then tested on the // specified search problem, and the effect of repeated state checking is // also examined. A depth limit is provided to the search algorithms, and // the algorithms are expected to terminate and report failure if that depth // limit is ever reached during search. Summary results are sent to the // standard output stream. // // David Noelle -- Tue Sep 11 16:11:07 PDT 2018 //

import java.io.*;

public class Pzero {

public static void main(String[] args) { try { Map graph = new Map(); InputStreamReader converter = new InputStreamReader(System.in); BufferedReader in = new BufferedReader(converter); String initialLoc; String destinationLoc; Node solution; int limit = 1000; // depth limit, to avoid infinite loops

System.out.println("UNINFORMED SEARCH ALGORITHM COMPARISON"); // Read map ... if (!(graph.readMap())) { System.err.println("Error: Unable to read map."); return; } // Get initial and final locations ... System.out.println("Enter the name of the initial location:"); initialLoc = in.readLine(); System.out.println("Enter the name of the destination location:"); destinationLoc = in.readLine();

// Testing BFS without repeated state checking ... System.out.println("TESTING BFS WITHOUT REPEATED STATE CHECKING"); BFSearch bfs = new BFSearch(graph, initialLoc, destinationLoc, limit); solution = bfs.search(false); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", bfs.expansionCount);

// Testing BFS with repeated state checking ... System.out.println("TESTING BFS WITH REPEATED STATE CHECKING"); solution = bfs.search(true); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", bfs.expansionCount);

// Testing DFS without repeated state checking ... System.out.println("TESTING DFS WITHOUT REPEATED STATE CHECKING"); DFSearch dfs = new DFSearch(graph, initialLoc, destinationLoc, limit); solution = dfs.search(false); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", dfs.expansionCount);

// Testing DFS with repeated state checking ... System.out.println("TESTING DFS WITH REPEATED STATE CHECKING"); solution = dfs.search(true); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", dfs.expansionCount);

// Done ... System.out.println("ALGORITHM COMPARISON COMPLETE"); } catch (IOException e) { // Something went wrong ... } } }

//ROAD

// // Road // // This class implements a segment of road directly connecting two nearby // locations on a map. Thus, Road objects form the "links" between location // "states", and the collection of all Road objects leading out of a given // location provides the result of the "successor function" for that "state". // Each road segment has a name. While it would be nice if these road names // were unique, there is nothing in this or related classes that depends on // road names being unique identifiers. (This is unlike Location names, which // must be unique.) Each Road also maintains the names of "from" and "to" // locations, as well as references to the actual Location objects // corresponding to those locations. (Note that this is slightly redundant, // as the Location objects know their own names, but this redundancy makes // the reading of maps from files a little easier.) Lastly, each Road object // has an incremental path cost: the cost, in either time or distance, of // traversing this road segment. // // David Noelle -- Sun Feb 11 17:53:48 PST 2007 //

import java.io.*; import java.util.*;

public class Road { public String name; public String fromLocationName; public String toLocationName; public Location fromLocation; public Location toLocation; public double cost = 0.0;

// read -- Read a road segment description from the given stream into this // object. Every road segment description must include the following // fields, separated by whitespace: a textual name, a textual "from" // location name, a textual "to" location name, and a double precision // floating point incremental path cost. Return true if and only if all // fields are successfully read. public boolean read(BufferedReader str) { try { String thisLine = str.readLine(); if (thisLine == null) // No more input, at all ... return (false); Scanner inScanner = new Scanner(thisLine); inScanner.useDelimiter("\\s+"); if (!inScanner.hasNext()) { inScanner.close(); return (false); } name = inScanner.next(); if (!inScanner.hasNext()) { inScanner.close(); return (false); } fromLocationName = inScanner.next(); fromLocation = null; if (!inScanner.hasNext()) { inScanner.close(); return (false); } toLocationName = inScanner.next(); toLocation = null; if (!inScanner.hasNextDouble()) { inScanner.close(); return (false); } cost = inScanner.nextDouble(); inScanner.close(); return (true); } catch (IOException e) { // Something went wrong ... return (false); } }

// write -- Write a description of this Road object to the given stream. // If "showLocs" is false, then only write the name of the road segment. // If "showLocs" is true, then generate a more verbose description of // the road segment that includes the names of the "from" and "to" // locations. public void write(OutputStream str, boolean showLocs) { PrintWriter out = new PrintWriter(str, true); if (showLocs) { out.printf("%s FROM %s TO %s", name, fromLocationName, toLocationName); } else { out.printf("%s", name); } }

}

O programming A GitHub-UCMP Mail-bmobley Included discus included discus Tinyos wiring i Project 1 Floo PAOspec (1) + v O file://C/Users/finis/App e 8wekyb3d8bbwe/TempState/Downloads/PAOspec%20(1)pdf You are to provide a Java class that implements the breadth-first search algorithm and another that implements the depth-first search algorithm. Your provided JavaTM source code must be com- patible with a collection of provided JavaM classes that implement simple road maps, allowing your search algorithms to be used to find the shortest routes between locations on such maps. In- deed, your assignment solution will be evaluated by combining your submitted class files with copies of the provided map utility class files and testing the resulting complete program against a variety of test cases. In other words, your solution must work with the provided utilities, without any modifications to these provided files More specifically, you are to provide a class called BFSearch in a source code file named "BFSearch.java", and you are to provide a class called DFSearch in a source code file named "DESearch. java. The first of these classes is to implement a breadth-first search algorithm, and the second is to implement a depth-first search algorithm. Both classes must have the following features a constructor that takes four arguments: 1. a complete Map object, encoding the map to be searched 2. a String providing the name of the starting location 3. a String providing the name of the destination location 4. an integer depth limit for the search if this depth is ever reached during a search (i.e., a node at this depth or deeper is considered for expansion), the search should be completely abandoned and null (indicating search failure) should be returned a method that actually performs the search, called search, with the following properties: - it takes a single boolean argument if this argument is "true", then repeated state checking should be performed, otherwise no such checking should be done during - it retuns a Node object from the search tree that corresponds to the target destination, a public integer instance variable called expansionCount that contains the number of search or null if no solution was found node expansions performed during the most recent call to the search method 11:49 PM O Type here to search 9/25/2018 19 O programming A GitHub-UCMP Mail-bmobley Included discus included discus Tinyos wiring i Project 1 Floo PAOspec (1) + v O file://C/Users/finis/App e 8wekyb3d8bbwe/TempState/Downloads/PAOspec%20(1)pdf You are to provide a Java class that implements the breadth-first search algorithm and another that implements the depth-first search algorithm. Your provided JavaTM source code must be com- patible with a collection of provided JavaM classes that implement simple road maps, allowing your search algorithms to be used to find the shortest routes between locations on such maps. In- deed, your assignment solution will be evaluated by combining your submitted class files with copies of the provided map utility class files and testing the resulting complete program against a variety of test cases. In other words, your solution must work with the provided utilities, without any modifications to these provided files More specifically, you are to provide a class called BFSearch in a source code file named "BFSearch.java", and you are to provide a class called DFSearch in a source code file named "DESearch. java. The first of these classes is to implement a breadth-first search algorithm, and the second is to implement a depth-first search algorithm. Both classes must have the following features a constructor that takes four arguments: 1. a complete Map object, encoding the map to be searched 2. a String providing the name of the starting location 3. a String providing the name of the destination location 4. an integer depth limit for the search if this depth is ever reached during a search (i.e., a node at this depth or deeper is considered for expansion), the search should be completely abandoned and null (indicating search failure) should be returned a method that actually performs the search, called search, with the following properties: - it takes a single boolean argument if this argument is "true", then repeated state checking should be performed, otherwise no such checking should be done during - it retuns a Node object from the search tree that corresponds to the target destination, a public integer instance variable called expansionCount that contains the number of search or null if no solution was found node expansions performed during the most recent call to the search method 11:49 PM O Type here to search 9/25/2018 19