Breadth first and Depth first are finished, hopefully they work ass supposed

[ailab2.git] / src / MySearcher.java

import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Hashtable;
import java.util.Enumeration;
import org.jdom.*;

/**
 * Beskrivning av klassen.
 */
public class MySearcher extends MapSearcher {
   private Graph map;

   /**
    * Skapar en ny MySearcher-instans.
    */
   public MySearcher () {
      super ();
   }

   /**
    * Specificerar kartan.
    *
    * @param map Den XML-fil som representerar kartan.
    *
    * @TODO fixa this.map.insertEdge() för alla noder.
    */
   public void setMap(File mapFile) {
      Document doc;
      List<Element> cityElements;
      try {
         doc = loadXmlMap(mapFile);
         cityElements = doc.getRootElement().getChildren();
         map = new Graph(cityElements.size(), 5);
         
         // Iterate through cityElements
         for (Element cityElement: cityElements) {
            // Prints names of cities
            String cityName = cityElement.getAttributeValue("id");
            int cityX = Integer.parseInt(cityElement.getAttributeValue("x"));
            int cityY = Integer.parseInt(cityElement.getAttributeValue("y"));
            GraphNode cityNode = map.insertNode(cityName, cityX, cityY);
            //System.out.println(cityName + " at position (" + cityX + ", " + cityY + ")");

            // Iterate through roadElements
            List<Element> roadElements = cityElement.getChildren();
            for (Element roadElement: roadElements) {
               String roadTo = roadElement.getAttributeValue("to");
               Double roadSpeed = Double.parseDouble(roadElement.getAttributeValue("speed"));
               // Prints all roads connected to the current cityElement
               //System.out.println("    road to -> " + roadElement.getAttributeValue("to"));
               Double time = 1.0;
               if (map.isInGraph(roadTo)) { // @FIX declare var in if condition
                  GraphNode roadToNode = map.getNode(roadTo);
                  Double distance = Math.hypot((cityNode.getX() - roadToNode.getX()),
                                               (cityNode.getY() - roadToNode.getY()));
                  time = distance / (roadSpeed / 3.6);
               }
               map.insertEdge(cityName, roadTo, time);
               // @FIX change roadSpeed to time
            }
         }
      }
      catch (IOException e) {
         System.err.println ("Could not read/find file.");
         System.exit(1);
      } catch (JDOMException e) {
         System.err.println ("File is not in valid XML format?");
         System.exit(1);
      } catch (NumberFormatException e) {
         System.err.println ("Coordinates cannot be parsed.");
      }
   }

   /**
    * Utför sökning med Greedy Search.
    *
    * @param from Den plats sökningen börjar från.
    * @param to Den plats sökningen avslutas på.
    */
   public String greedySearch (String from, String to) {
      // 1. Set N to be a sorted list of initial nodes;
      PriorityQueue<GraphNode> bigN =
         new PriorityQueue<GraphNode>(this.map.getNodes());
      GraphNode n;
      while (!bigN.isEmpty()) { // 2. If N is empty,
         // 3. set n to be the first node in N, and remove n from N;
         // 4. If n is a goal node, exit and signal success;
         // 5. Otherwise add the children of n to N, sort the nodes in N
         // according to the value on their evaluation function and return to
         // step 2.
      }
      // 2. ... exit and signal failure
      return null;
   }

   /**
    * Utför sökning med A*.
    *
    * @param from Den plats sökningen börjar från.
    * @param to Den plats sökningen avslutas på.
    * @param fastest Om <code>true</code>, hitta snabbaste vägen,
    * annars den kortaste.
    */
   public String aStar (String from, String to, boolean fastest) {
      // skapa en tabell över hur långt det är från alla platser på
      // kartan till målet för sökningen
      // Hashtable<String, Double> targetDistTable =
      //            new Hashtable<String, Double>(map.size());
      //        // spara ned målnoden
      //        GraphNode targetLocation = map.getNode(to);
      //        GraphNode tempNode;
      //        Enumeration e;
      //        // för alla noder
      //        for (e = map.getNodes(),
      //                 tempNode = (GraphNode) e.nextElement();
      //             e.hasMoreElements(); // medan e har element
      //             tempNode = (GraphNode) e.nextElement()) {
      //            // spara avståndet till målnoden för varje nod
      //            targetDistTable.put(tempNode.getName(),
      //                             Math.hypot(targetLocation.getX()-tempNode.getX(),
      //                                        targetLocation.getY()-tempNode.getY()));
      //}
      /*
       * implementation av aStar.
       */
      return "";
   }

   /**
    * Utför bredden-förstsökning.
    *
    * @param from Den plats sökningen börjar från.
    * @param to Den plats sökningen avslutas på.
    */
   public String breadthFirst (String from, String to) {
      // Comments fetched from
      // http://en.wikipedia.org/wiki/Breadth-first_search
      // at Tue Oct 14 12:57:18 2008
      LinkedList<GraphNode> q = new LinkedList<GraphNode>();
      String expandedNodes = "";
      String pathToGoal = "";
      // 1. Put the root node on the queue.
      q.add(map.getNode(from));
      while (!q.isEmpty()) {
         // 2. Pull a node from the beginning of the queue and examine it.
         GraphNode n = q.removeFirst();
         //   * If the searched element is found in this node, quit
         //   * the search and return a result.
         if (n.getName().equals(to)) {
            expandedNodes += to;
            while (n != map.getNode(from)) {
               pathToGoal = n.getName() + ", " + pathToGoal;
               n = n.getParent();
            }
            pathToGoal = n.getName() + ", " + pathToGoal;
            break;
         }
         //   * Otherwise push all the (so-far-unexamined) successors
         //   * (the direct child nodes) of this node into the end of
         //   * the queue, if there are any.
         else {
            expandedNodes += n.getName() + ", ";
            for (Enumeration e = n.getNeighbours(); e.hasMoreElements();) {
               GraphNode neighbour = (GraphNode) e.nextElement();
               neighbour.setParent(n);
               q.add(neighbour);
            }
         }
         // If the queue is empty, every node on the graph has been
         // examined -- quit the search and return "not found".
         if (q.isEmpty()) {
            return "\nGoal not found!";
         }
      }
      return "\nAll visited nodes:\n" + expandedNodes + "\n\n"
         + "Path to goal:\n" + pathToGoal;
   }

   /**
    * Utför djupet-förstsökning.
    *
    * @param from Den plats sökningen börjar från.
    * @param to Den plats sökningen avslutas på.
    */
   public String depthFirst (String from, String to) {
      LinkedList<GraphNode> s = new LinkedList<GraphNode>();
      String expandedNodes = "";
      String pathToGoal = "";
      // 1. Push the root node onto the stack.
      s.add(map.getNode(from));
      while (!s.isEmpty()) {
         // 2. Pop a node from the stack
         GraphNode n = s.removeLast();
         //   * Mark this node as visited
         n.visit();
         //   * If the searched element is found in this node, quit
         //   * the search and return a result.
         if (n.getName().equals(to)) {
            expandedNodes += to;
            while (n != map.getNode(from)) {
               pathToGoal = n.getName() + ", " + pathToGoal;
               n = n.getParent();
            }
            pathToGoal = n.getName() + ", " + pathToGoal;
            break;
         }
         //   * Otherwise push all the unvisited connecting nodes of n
         else {
            expandedNodes += n.getName() + ", ";
            for (Enumeration e = n.getNeighbours();
                 e.hasMoreElements();) {
               GraphNode neighbour = (GraphNode) e.nextElement();
               if (!neighbour.isVisited()) {
                  neighbour.setParent(n);
                  s.add(neighbour);
               }
            }
         }
         // If the stack is empty, every node on the graph has been
         // examined -- quit the search and return "not found".
         if (s.isEmpty()) {
            return "\nGoal not found!";
         }
      }
      return "\nAll visited nodes:\n" + expandedNodes + "\n"
         + "Path to goal:\n" + pathToGoal;
   }

   public String toString() {
      return map.toString();
   }
}