### Background Information

There are three ways to implement best first search:

- Uniform cost search makes decisions about the node to search based only on the distance it took to reach that node so far.
- Greedy search makes decision about the node to search based only on the heuristic (e.g. the straight-line distance from the node to the destination)
- A* search takes account of both the distance so far and the heuristic

### Task to Complete

Develop a program to find the shortest path between any two cities in Romania. This program must:

- be able to store a graph of nodes, and each node can have any number of adjacencies
- be able to find the shortest path between two cities using best first search (A* search, uniform cost search, and greedy search)
- display the result using graphics and be interactive with the user

### October 24th, 2016 – Node, Graph, and GraphSearcher Classes

- Create the class
*Node*to hold the nodes in the graph, that will:- have a
*List<Edge>**adjacent*of all its*Edges* - have a
*String data*to store the data - have relevant accessor and mutator methods for the variables above
- have the method
*connect**(Node n, int d)*to add a new*Edge*with distance*d*to both the*adjacents*of itself and of*n*

- have a
- Create the class
*Edge*to hold the connections between the*Nodes*that has:*Nodes n1*and*n2*that store the two nodes connected by this adjacency- an integer
*distance*and an accessor method for it - a
*getOther(Node)*that returns the*Node*other than the*Node*passed as the parameter

- Create the class
*Graph*to represent the graph used to store the nodes, which has:- the
*List<Node>**List<Edge>*to store all the nodes and edges of the graph - a
*createRomaniaGraph()*method which sets up a preset Romania graph by creating*Nodes*and connecting them

- the
- Create the “singleton” class
*GraphSearcher*to search a graph, with:- a
*static getInstance()*method (part of the “singleton” setup) - the
*Nodes startNode*and*destNode*to store the starting point and destination of the search - accessor and mutator methods for
*startNode*and*destNode* - a
*PriorityQueue<Node>**fringe*to store the*Nodes*that need to be checked - a
*List<Node> visited*to store the*Nodes*that have already been checked - the
*bestFirstSearch(Graph g)*method that carries out the search

- a

### October 26th, 2016 – Pathfinding Algorithms

- Adding to the
*Node*class by:- having it
*implement Comparable*and*Comparator*so it can be sorted by*PriorityQueue* - adding the variables
*distance*and its accessor/mutator methods - adding a
*getCost()*method that returns*distance*(just for now)

- having it
- Adding to the
*GraphSearcher*class by:- adding an
*addToFringe(Node)*method that adds the passed in*Node*to*fringe* - because a
*PriorityQueue*won’t resort itself if the contents of one of its elements is changed, also adding an*reAddToFringe(Node)*method that takes out the said*Node*and adds it back in again so that the*PriorityQueue*is properly sorted - adding a
*retrace(Node n)*method to*GraphSearcher*that will retrace the path that*n*was found with, through:- having each
*Node*store another*Node parent*, which will be filled with whichever*Node*called on this*Node*first - recursively calling the
*getParent()*method of each successive*Node*, storing them in a*List<Node> path*, and returning*path*

- having each

- adding an
- Adding an
*expand()*method to*Node*which:- loops through
*adjacents*, and storing each*Node*at the other side of the*Edge*in a temporary variable*other* - checks if
*other*was already visited, and if so, moving onto the next iteration of the loops - checks if
*other*is already in*GraphSearcher*‘s*fringe*, and if not:- setting
*other*‘s*distance*to its own*distance*plus the*distance*of the*Edge*connecting them - setting
*other*‘s*parent*to itself - adding
*other*to*fringe*using the*addToFringe()*method

- setting
- if
*other*is already in*fringe*, then:- checking if
*other*‘s*distance*is shorter than the new*distance*calculated from itself (see point above), and if so, moving onto the next iteration - if not, then setting
*other*‘s*distance*to the shorter one, setting*other*‘s*parent*to itself, and calling the*reAddToFringe()*method on it

- checking if

- loops through
- Implementing the
*bestFirstSearch(Graph g)*method by:- instantiating
*fringe*and*visited*, and adding*startNode*to*fringe* - if
*fringe*is empty, then returning*null* - otherwise, checking the top item in
*fringe*using*PriorityQueue*‘s*poll()*method- if the top item is
*destNode*, then returning the*retrace()*of that*Node* - if not, then moving that
*Node*to*visited*, and calling its*expand()*method

- if the top item is

- instantiating

### November 1st, 2016 – Heuristics and Graphics Display

- Implementing herusitics through:
- the variables
*lat*and*lon*, which store the latitude and longitude of the city, to be set in the constructor - the method
*getHeuristic()*which uses the “haversine” formula to calculate the straight-line distance from this*Node*to*destNode*(accesses through*GraphSearcher*‘s accessor methods) - adding a variable in
*GraphSearcher*called*searchType*, along with its accessor methods - in
*Node*‘s*getCost()*, if*searchType*is 1, returning*distance*plus*getHeuristic()*; if*searchType*is 2, returning*distance*; and if*searchType*is 3, returning*heuristic*(these three represent A*, uniform cost, and greedy search, respectively)

- the variables
- Adding methods for displaying in the various classes, including:
*drawNode()*,*drawLabel()*, and*fillNode()*in*Node*that draw the*Node*on a*Graphics2D*object at a location set when the*Node*is constructed*drawEdge()*,*drawLabel()*in*Edge*that have similar purposes- a
*displayGraph()*method in*Graph*which loops through the*Lists*of*Nodes*and*Edges*and displays them

- Adding a
*mouseOn*method in*Graph*that checks if the mouse cursor is on any*Node*, returning the*Node*the mouse is on, or*null*if on nothing - Creating a “singleton”
*Display*method used to display the map and deal with user interaction, which:- extends
*JFrame*and holds a*JPanel*to store its contents - implements
*MouseMotionListener*,*MouseListener*, and*KeyListener*for user input - has variables
*mouseX*and*mouseY*which are updated based on the location of the mouse cursor - has a
*List<Node>**path*which is full if a search has been done and empty if no search has been done yet - has a
*public*method*paint()*which:- creates a new
*BufferedImage* - on that
*BufferedImage*, uses*Graph*‘s*displayGraph()*method to display the graph - fills in a
*Node*that the mouse is hovering on with a different color, using the*mouseOn*method - if
*path*has contents, then filling the*Nodes*in*path*with a different color - displaying the
*distance*of the last*Node*in*path*if it exists (representing the distance of the path found) - paints the
*BufferedImage*onto the*JPanel*

- creates a new
- has various mouse controls, including clicking on
*Nodes*to set them as*startNode*or*destNode*in*GraphSearcher* - has various keyboard controls, including:
- pressing 1, 2, and 3 to carry out the three different searches
- pressing ‘d’ to display the labels of the
*Nodes*and*Edges*

- extends
- At this point, the program is pretty much complete.

Advertisements