Create BreadthFirstSearch.java using the following: Fronter.java, Location.java,
ID: 3885276 • Letter: C
Question
Create BreadthFirstSearch.java using the following:
Fronter.java, Location.java, Map.java, Waypoint.java, Road.java, Pzero.java
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 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 Waypoint object from the search tree that corresponds to the target destina- tion, or null if no solution was found
• an integer instance variable called expansionCount that contains the number of node expansions performed during the last call to the search method
Any help would be greatly appreciated, I haven't worked with java in over a year and I am lost.
//
// Frontier
//
// This class implements either a FIFO list (a queue) or a LIFO list (a stack)
// of Waypoint objects, with the kind of list determined by which method is
// used to insert new Waypoint nodes 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 Waypoint
// objects or lists of multiple Waypoint objects. This class is intended to
// to be used to implement the frontier (i.e., the "fringe" or "open list") of
// 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.)
//
import java.util.*;
public class Frontier {
List fringe;
// Default constructor ...
public Frontier() {
fringe = new LinkedList();
}
// isEmpty -- Return true if and only if there are currently no nodes in
// the frontier.
public boolean isEmpty() {
return (fringe.isEmpty());
}
// removeTop -- Return the Waypoint object at the top of the frontier
// list. Also, remove this node from the frontier. Return null if the
// frontier is empty.
public Waypoint removeTop() {
if (fringe.isEmpty()) {
return (null);
} else {
Waypoint top = fringe.get(0);
fringe.remove(0);
return (top);
}
}
// addToTop -- Add the given Waypoint object to the top of the frontier
// list.
public void addToTop(Waypoint wp) {
fringe.add(0, wp);
}
// addToTop -- Add the given list of Waypoint objects to the top of the
// frontier list.
public void addToTop(List points) {
for (Waypoint wp : points) {
addToTop(wp);
}
}
// addToBottom -- Add the given Waypoint object to the bottom of the
// frontier list.
public void addToBottom(Waypoint wp) {
fringe.add(wp);
}
// addToBottom -- Add the given list of Waypoint objects to the bottom of
// the frontier list.
public void addToBottom(List points) {
for (Waypoint wp : points) {
addToBottom(wp);
}
}
// contains -- Return true if and only if the frontier contains a
// Waypoint with the given Location name.
public boolean contains(String name) {
// This linear search is very inefficient, but it cannot be avoided
// without maintaining a parallel data structure containing the
// fringe members (e.g., a HashSet).
for (Waypoint element : fringe)
if (name.equals(element.loc.name))
return (true);
// The location was not found in the fringe ...
return (false);
}
// contains -- Return true if and only if the frontier contains a
// Waypoint 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 Waypoint (with regard to the Location) to the one provided
// as an argument.
public boolean contains(Waypoint wp) {
return (contains(wp.loc));
}
}
//
// 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).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 ...
return (true);
} else {
// 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
//
// 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);
return (false);
}
r.toLocation = findLocation(r.toLocationName);
if (r.toLocation == null) {
System.err.printf("The location, %s, is not known. ",
r.toLocationName);
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());
}
}
//
// Waypoint
//
// 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 "previous" node), and a collection of children
// nodes (i.e., the "options" for the next step) which remains empty until the
// node is expanded. Each Waypoint node 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 "options" list of children of this
// node, using information embedded in this node's Location object. Second,
// the "reportSolution" recursive method uses the "previous" 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
//
import java.io.*;
import java.util.*;
public class Waypoint {
public Location loc;
public Waypoint previous;
public List options;
public int depth = 0;
public double partialPathCost = 0.0;
// Default constructor ...
public Waypoint() {
this.options = new ArrayList();
}
// Constructor with Location object specified ...
public Waypoint(Location loc) {
this();
this.loc = loc;
}
// Constructor with Location object and parent node specified ...
public Waypoint(Location loc, Waypoint previous) {
this(loc);
this.previous = previous;
}
// expand -- Fill in the collection of children of this node, stored in
// it's "options" 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() {
options.removeAll(options);
for (Road r : loc.roads) {
Waypoint option = new Waypoint(r.toLocation, this);
option.depth = this.depth + 1;
option.partialPathCost = this.partialPathCost + r.cost;
options.add(option);
}
}
// isFinalDestination -- Return true if and only if the name of the
// location corresponding to this node matches the provided argument.
public boolean isFinalDestination(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 (previous == 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 ...
previous.reportSolution(str);
// Now report the road segment to this point ...
out.printf("TAKE ");
(previous.loc.findRoad(loc)).write(str, true);
out.printf(". ");
}
}
}
//
// 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).useDelimiter("\s+");
if (!inScanner.hasNext()) return (false);
name = inScanner.next();
if (!inScanner.hasNext()) return (false);
fromLocationName = inScanner.next();
fromLocation = null;
if (!inScanner.hasNext()) return (false);
toLocationName = inScanner.next();
toLocation = null;
if (!inScanner.hasNextDouble()) return (false);
cost = inScanner.nextDouble();
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);
}
}
}
//
// 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 -- Sun Feb 11 18:50:04 PST 2007
//
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;
Waypoint 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 ...
}
}
}
Sample Input/Output:
UNINFORMED SEARCH ALGORITHM COMPARISON
Enter the name of the location file:
INPUT-> small-locations.dat
Enter the name of the road file:
INPUT -> small-roads.dat
Enter the name of the initial location:
INPUT ->home
Enter the name of the destination location:
INPUT-> bookstore
TESTING BFS WITHOUT REPEATED STATE CHECKING
Solution:
START AT home.
TAKE central FROM home TO bus-station.
TAKE highway-north FROM bus-station TO fast-food.
TAKE highway-east FROM fast-food TO bookstore.
Path Cost = 15.300000.
Number of Node Expansions = 63.
TESTING BFS WITH REPEATED STATE CHECKING
Solution:
START AT home.
TAKE central FROM home TO bus-station.
TAKE highway-north FROM bus-station TO fast-food.
TAKE highway-east FROM fast-food TO bookstore.
Path Cost = 15.300000.
Number of Node Expansions = 12.
TESTING DFS WITHOUT REPEATED STATE CHECKING
Solution:
None found.
Number of Node Expansions = 1000.
TESTING DFS WITH REPEATED STATE CHECKING
Solution:
START AT home.
TAKE central FROM home TO bus-station.
TAKE stadium-street FROM bus-station TO stadium.
TAKE gravel-road FROM stadium TO ranch.
TAKE old-highway FROM ranch TO diner.
TAKE access-road FROM diner TO bookstore.
Path Cost = 71.800000.
Number of Node Expansions = 6.
ALGORITHM COMPARISON COMPLETE
Explanation / Answer
Pzero.java
--------------------------------------------
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;
Waypoint 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 ...
}
}
}
------------------------------------------------------------------------------
BFSearch.java
----------------------------------------------
import java.util.*; // libraries that are needed for the program to run
public class BFSearch // Class declaration
{
// Initialization of global variables
private int depthLimit; // Stores the limit of depth that the waypoint can reach before being considered a failure
private Map myMap; // Stores the map that will be searched
private String start; // Stores the starting position
private String destination; // Stores the ending position
public int expansionCount; // Stores the number of expansions that occur during a search
// constructor takes in the map, starting location name, ending location name, and the limit for a node's depth
public BFSearch(Map my_Map, String start_Loc, String dest_Loc, int depth_Limit) {
this.myMap = my_Map; // Set the map used in the search as the one used in the main program
this.start = start_Loc; // Set the starting location to the one the user enters
this.destination = dest_Loc; // Set the destination location to the one the user enters
this.depthLimit = depth_Limit; // Set the node depth limit to the what is specified in the main program
}
// The search program that applies breadth-first search
public Waypoint search(boolean rpt_State_Check) // Takes in a boolean and returns the destination node if it is found
{
expansionCount = 0; // Sets the expansion count to zero every time a new search starts
Waypoint node = new Waypoint(myMap.findLocation(this.start)); // Define a waypoint that is the starting place. It is defined by the location given by the name of the starting location
Frontier frontier = new Frontier(); // The frontier is where children nodes are stored
frontier.addToBottom(node); // Breadth first search uses a queue, so all new nodes should be added to the bottom of the frontier
if (rpt_State_Check == true) // If the search is being conducted with repeated state checking
{
HashSet<String> explored = new HashSet<String>(); // Created a storage unit for the explored nodes to be placed and checked
explored.add(node.loc.name); // Adds the first node to explored so that it is never explored again redundantly
while (!frontier.isEmpty() && node.depth < this.depthLimit - 1) // Loops so long as the frontier is not empty and depth limit is not reached
{ // If they are, then the search is deemed a failure
node = frontier.removeTop(); // This function sets node to the shallowest child node, which will be at the top of the stack
if (node.isFinalDestination(this.destination)) // Should the destination be found, it will be returned as a successful search
return node;
explored.add(node.loc.name); // If the destination node is not found, the current node will be added to the explored set so that the program will forgo searching the node again
node.expand(); // Expands the current node so that its children nodes may possibly added to the frontier
expansionCount++; // Increment the expansion count every time a node is expanded
for (Waypoint x : node.options) // Loops through all the children nodes of node
{
// The condition for a child node to be added to the frontier is that it has not already been explored and it is not already in the frontier
if (!explored.contains(x.loc.name) && !frontier.contains(x))
frontier.addToBottom(x); // Breadth first search uses a queue, so all new nodes should be added to the bottom
}
}
return null; // Signifies that the search has failed
} else // If the repeated state checking is not being conducted
{
while (!frontier.isEmpty() && node.depth < this.depthLimit - 1) // Loops so long as the frontier is not empty and depth limit is not reached
{ // If they are, then the search is deemed a failure
node = frontier.removeTop(); // This function sets node to the shallowest child node, which will be at the top of the stack
if (node.isFinalDestination(this.destination)) // Should the destination be found, it will be returned as a successful search
return node;
node.expand(); // Expands the current node so that its children nodes may possibly added to the frontier
expansionCount++; // Increment the expansion count every time a node is expanded
frontier.addToBottom(node.options); // Breadth first search uses a queue, so all new nodes should be added to the bottom
}
return null; // Signifies that the search has failed
}
}
}
--------------------------------------------------------------------------
DFSearch.java
------------------------------------------
import java.util.*; // libraries that are needed for the program to run
public class DFSearch
{
// Initialization of global variables
private int depthLimit; // Stores the limit of depth that the waypoint can reach before being considered a failure
private Map myMap; // Stores the map that will be searched
private String start; // Stores the starting position
private String destination; // Stores the ending position
public int expansionCount; // Stores the number of expansions that occur during a search
public DFSearch(Map my_Map, String start_Loc, String dest_Loc, int depth_Limit)
{
this.myMap = my_Map; // Set the map used in the search as the one used in the main program
this.start = start_Loc; // Set the starting location to the one the user enters
this.destination = dest_Loc; // Set the destination location to the one the user enters
this.depthLimit = depth_Limit; // Set the node depth limit to the what is specified in the main program
}
// The search program that applies depth-first search
public Waypoint search(boolean rpt_State_Check ) // Takes in a boolean and returns the destination node if it is found
{
expansionCount = 0;
Waypoint node = new Waypoint(myMap.findLocation(this.start)); // Define a waypoint that is the starting place. It is defined by the location given by the name of the starting location
Frontier frontier = new Frontier(); // The frontier is where children nodes are stored
frontier.addToTop(node); // Depth-first search uses a stack, all new nodes will be added to the top of the frontier
if(rpt_State_Check == true) // If the search is being conducted with repeated state checking
{
HashSet<String>explored = new HashSet<String>(); // Created a storage unit for the explored nodes to be placed and checked
explored.add(node.loc.name); // Adds the first node to explored so that it is never explored again redundantly
while(!frontier.isEmpty() && node.depth < this.depthLimit-1) // Loops so long as the frontier is not empty and depth limit is not reached
{ // If they are, then the search is deemed a failure
node = frontier.removeTop(); // This function sets node to the shallowest child node, which will be at the top of the stack
if(node.isFinalDestination(this.destination)) // Should the destination be found, it will be returned as a successful search
return node;
explored.add(node.loc.name); // If the destination node is not found, the current node will be added to the explored set so that the program will forgo searching the node again
node.expand(); // Expands the current node so that its children nodes may possibly added to the frontier
expansionCount++; // Increment the expansion count every time a node is expanded
for(Waypoint x: node.options) // Loops through all the children nodes of node
{
// The condition for a child node to be added to the frontier is that it has not already been explored and it is not already in the frontier
if(!explored.contains(x.loc.name) && !frontier.contains(x))
frontier.addToTop(x); // Depth-first search uses a stack, all new nodes will be added to the top of the frontier
}
}
return null; // Signifies that the search has failed
}
else // If the repeated state checking is not being conducted
{
while(!frontier.isEmpty() && node.depth < this.depthLimit-1) // Loops so long as the frontier is not empty and depth limit is not reached
{ // If they are, then the search is deemed a failure
node = frontier.removeTop(); // This function sets node to the shallowest child node, which will be at the top of the stack
if(node.isFinalDestination(this.destination)) // Should the destination be found, it will be returned as a successful search
return node;
node.expand(); // Expands the current node so that its children nodes may possibly added to the frontier
expansionCount++; // Increment the expansion count every time a node is expanded
frontier.addToTop(node.options);// Depth-first search uses a stack, all new nodes will be added to the top of the frontier
}
return null; // Signifies that the search has failed
}
}
}
----------------------------------------------------------------------------------------
Frontier.java
---------------------------------
import java.util.*;
public class Frontier {
List<Waypoint> fringe;
// Default constructor ...
public Frontier() {
fringe = new LinkedList<Waypoint>();
}
// isEmpty -- Return true if and only if there are currently no nodes in
// the frontier.
public boolean isEmpty() {
return (fringe.isEmpty());
}
// removeTop -- Return the Waypoint object at the top of the frontier
// list. Also, remove this node from the frontier. Return null if the
// frontier is empty.
public Waypoint removeTop() {
if (fringe.isEmpty()) {
return (null);
} else {
Waypoint top = fringe.get(0);
fringe.remove(0);
return (top);
}
}
// addToTop -- Add the given Waypoint object to the top of the frontier
// list.
public void addToTop(Waypoint wp) {
fringe.add(0, wp);
}
// addToTop -- Add the given list of Waypoint objects to the top of the
// frontier list.
public void addToTop(List<Waypoint> points) {
for (Waypoint wp : points) {
addToTop(wp);
}
}
// addToBottom -- Add the given Waypoint object to the bottom of the
// frontier list.
public void addToBottom(Waypoint wp) {
fringe.add(wp);
}
// addToBottom -- Add the given list of Waypoint objects to the bottom of
// the frontier list.
public void addToBottom(List<Waypoint> points) {
for (Waypoint wp : points) {
addToBottom(wp);
}
}
// contains -- Return true if and only if the frontier contains a
// Waypoint with the given Location name.
public boolean contains(String name) {
// This linear search is very inefficient, but it cannot be avoided
// without maintaining a parallel data structure containing the
// fringe members (e.g., a HashSet).
for (Waypoint element : fringe)
if (name.equals(element.loc.name))
return (true);
// The location was not found in the fringe ...
return (false);
}
// contains -- Return true if and only if the frontier contains a
// Waypoint 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 Waypoint (with regard to the Location) to the one provided
// as an argument.
public boolean contains(Waypoint wp) {
return (contains(wp.loc));
}
}
-------------------------------------------------------------------------------
Location.java
----------------------------------------
import java.io.*;
import java.util.*;
public class Location {
public String name = "";
public double longitude = 0.0;
public double latitude = 0.0;
public List<Road> roads;
// Default constructor ...
public Location() {
this.roads = new ArrayList<Road>();
}
// 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.
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).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 ...
return (true);
} else {
// 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.
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
-------------------------------------
import java.io.*;
import java.util.*;
public class Map {
String locationFilename = "locations.dat";
String roadFilename = "roads.dat";
List<Location> locations;
// Default constructor ...
public Map() {
this.locations = new ArrayList<Location>();
}
// 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.
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);
return (false);
}
r.toLocation = findLocation(r.toLocationName);
if (r.toLocation == null) {
System.err.printf("The location, %s, is not known. ",
r.toLocationName);
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());
}
}
--------------------------------------------------------------
Road.java
----------------------------------------
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.
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).useDelimiter("\s+");
if (!inScanner.hasNext()) return (false);
name = inScanner.next();
if (!inScanner.hasNext()) return (false);
fromLocationName = inScanner.next();
fromLocation = null;
if (!inScanner.hasNext()) return (false);
toLocationName = inScanner.next();
toLocation = null;
if (!inScanner.hasNextDouble()) return (false);
cost = inScanner.nextDouble();
return (true);
} catch (IOException e) {
// Something went wrong ...
return (false);
}
}
// write -- Write a description of this Road object to the given stream.
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);
}
}
}
--------------------------------------------------------------------------------------
WayPoint.java
-------------------------------------------
import java.io.*;
import java.util.*;
public class Waypoint {
public Location loc;
public Waypoint previous;
public List<Waypoint> options;
public int depth = 0;
public double partialPathCost = 0.0;
// Default constructor ...
public Waypoint() {
this.options = new ArrayList<Waypoint>();
}
// Constructor with Location object specified ...
public Waypoint(Location loc) {
this();
this.loc = loc;
}
// Constructor with Location object and parent node specified ...
public Waypoint(Location loc, Waypoint previous) {
this(loc);
this.previous = previous;
}
// expand -- Fill in the collection of children of this node, stored in
// it's "options" 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() {
options.removeAll(options);
for (Road r : loc.roads) {
Waypoint option = new Waypoint(r.toLocation, this);
option.depth = this.depth + 1;
option.partialPathCost = this.partialPathCost + r.cost;
options.add(option);
}
}
// isFinalDestination -- Return true if and only if the name of the
// location corresponding to this node matches the provided argument.
public boolean isFinalDestination(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 (previous == 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 ...
previous.reportSolution(str);
// Now report the road segment to this point ...
out.printf("TAKE ");
(previous.loc.findRoad(loc)).write(str, true);
out.printf(". ");
}
}
}
------------------------------------------------------------------------
locations.dat
---------------------------------------------
home 32.1 54.4
corner-store 37.9 58.2
school 42.0 55.5
fire-station 28.1 50.3
coffee-shop 36.6 49.8
bus-station 42.0 50.0
stadium 59.9 49.1
ranch 67.7 44.0
park 86.0 42.0
donut-shop 37.6 41.9
police-station 27.7 36.5
grocery-store 34.1 39.9
fast-food 48.0 36.4
gym 35.3 32.3
diner 69.0 32.0
car-dealer 47.7 22.2
bookstore 64.0 24.2
truck-stop 66.6 18.1
factory 31.9 28.2
---------------------------------------------------------------------------------
roads.dat
---------------------------------------
path home corner-store 3.1
path corner-store home 3.1
sidewalk home fire-station 3.3
sidewalk fire-station home 3.3
north-street corner-store school 4.2
north-street school corner-store 4.2
hill-street home coffee-shop 3.6
hill-street coffee-shop home 3.6
narrows fire-station coffee-shop 5.1
narrows coffee-shop fire-station 5.1
central home bus-station 6.9
central bus-station home 6.9
elm-street school bus-station 5.8
elm-street bus-station school 5.8
the-avenue coffee-shop bus-station 4.9
the-avenue bus-station coffee-shop 4.9
back-street fire-station police-station 9.9
back-street police-station fire-station 9.9
side-street coffee-shop donut-shop 6.6
side-street donut-shop coffee-shop 6.6
lower-main police-station grocery-store 3.9
lower-main grocery-store police-station 3.9
upper-main grocery-store donut-shop 3.7
upper-main donut-shop grocery-store 3.7
alley grocery-store gym 4.2
alley gym grocery-store 4.2
grimey-place police-station factory 6.3
grimey-place factory police-station 6.3
damp-drive factory gym 4.9
damp-drive gym factory 4.9
long-drive gym car-dealer 13.0
long-drive car-dealer gym 13.0
back-road car-dealer truck-stop 15.3
back-road truck-stop car-dealer 15.3
highway-north bus-station fast-food 4.2
highway-north fast-food bus-station 4.2
highway-east fast-food bookstore 4.2
highway-east bookstore fast-food 4.2
highway-south bookstore truck-stop 1.4
highway-south truck-stop bookstore 1.4
overgrown-path fast-food car-dealer 27.9
overgrown-path car-dealer fast-food 27.9
hill-pass school stadium 18.1
hill-pass stadium school 18.1
stadium-street bus-station stadium 16.0
stadium-street stadium bus-station 16.0
gravel-road stadium ranch 15.4
gravel-road ranch stadium 15.4
old-highway ranch diner 19.1
old-highway diner ranch 19.1
dirt-road ranch park 35.5
dirt-road park ranch 35.5
access-road diner bookstore 14.4
access-road bookstore diner 14.4
----------------------------------------------------------------------
log-home-to-bookstore.text
--------------------------------------------
UNINFORMED SEARCH ALGORITHM COMPARISON
Enter the name of the location file:
small-locations.dat
Enter the name of the road file:
small-roads.dat
Enter the name of the initial location:
home
Enter the name of the destination location:
bookstore
TESTING BFS WITHOUT REPEATED STATE CHECKING
Solution:
START AT home.
TAKE central FROM home TO bus-station.
TAKE highway-north FROM bus-station TO fast-food.
TAKE highway-east FROM fast-food TO bookstore.
Path Cost = 15.300000.
Number of Node Expansions = 63.
TESTING BFS WITH REPEATED STATE CHECKING
Solution:
START AT home.
TAKE central FROM home TO bus-station.
TAKE highway-north FROM bus-station TO fast-food.
TAKE highway-east FROM fast-food TO bookstore.
Path Cost = 15.300000.
Number of Node Expansions = 12.
TESTING DFS WITHOUT REPEATED STATE CHECKING
Solution:
None found.
Number of Node Expansions = 1000.
TESTING DFS WITH REPEATED STATE CHECKING
Solution:
START AT home.
TAKE central FROM home TO bus-station.
TAKE stadium-street FROM bus-station TO stadium.
TAKE gravel-road FROM stadium TO ranch.
TAKE old-highway FROM ranch TO diner.
TAKE access-road FROM diner TO bookstore.
Path Cost = 71.800000.
Number of Node Expansions = 6.
ALGORITHM COMPARISON COMPLETE