Java, provided with the classes

============================================================================

Frontier.java

// 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.

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.java

// 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.

//

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.java

// 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.

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.java

// 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.

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.java

// 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.

//

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.java

// 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.

//

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);

}

}

}

Activities You are to provide a JavaM class that implements the breadth-first search algorithm and another that implements the depth-first search algorithm. Your provided Java source code must be com- patible with a collection of provided Java 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 ilities, 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 DESearch in a source code file named "DFSearch.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 (ie., 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 search - it returns a Node object from the search tree that corresponds to the target destination, or null if no solution was found a public integer instance variable called expansionCount that contains the number of node expansions performed during the most recent call to the search method Activities You are to provide a JavaM class that implements the breadth-first search algorithm and another that implements the depth-first search algorithm. Your provided Java source code must be com- patible with a collection of provided Java 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 ilities, 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 DESearch in a source code file named "DFSearch.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 (ie., 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 search - it returns a Node object from the search tree that corresponds to the target destination, or null if no solution was found a public integer instance variable called expansionCount that contains the number of node expansions performed during the most recent call to the search method