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
  • 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
    • 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> and List<Edge> to store all the nodes and edges of the graph
    • createRomaniaGraph() method which sets up a preset Romania graph by creating Nodes and connecting them
  • Create the “singleton” class GraphSearcher to search a graph, with:
    • 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
    • PriorityQueue<Node> fringe to store the Nodes that need to be checked
    • List<Node> visited to store the Nodes that have already been checked
    • the bestFirstSearch(Graph g) method that carries out the search

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

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)
  • 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
    • 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 MouseMotionListenerMouseListener, 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
    • 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
  • At this point, the program is pretty much complete.
Advertisements