src/MySearcher.java

   1 import java.io.File;
   2 import java.io.IOException;
   3 import java.util.Iterator;
   4 import java.util.List;
   5 import java.util.LinkedList;
   6 import java.util.PriorityQueue;
   7 import java.util.Hashtable;
   8 import java.util.Enumeration;
   9 import org.jdom.*;
  10
  11 /**
  12  * Beskrivning av klassen.
  13  */
  14 public class MySearcher extends MapSearcher {
  15     private Graph map;
  16
  17    /**
  18     * Skapar en ny MySearcher-instans.
  19     */
  20    public MySearcher () {
  21       super ();
  22    }
  23
  24    /**
  25     * Specificerar kartan.
  26     *
  27     * @param map Den XML-fil som representerar kartan.
  28     *
  29     * @TODO fixa this.map.insertEdge() för alla noder.
  30     */
  31    public void setMap(File mapFile) {
  32       Document doc;
  33       List<Element> cityElements;
  34       try {
  35          doc = loadXmlMap(mapFile);
  36          //System.out.println(doc.getRootElement().toString());
  37          cityElements = doc.getRootElement().getChildren();
  38          map = new Graph(cityElements.size(), 5);
  39          // Iterate through cityElements
  40          for (Element cityElement: cityElements) {
  41             // Prints names of cities
  42             String cityName = cityElement.getAttributeValue("id");
  43             int cityX = Integer.parseInt(cityElement.getAttributeValue("x"));
  44             int cityY = Integer.parseInt(cityElement.getAttributeValue("y"));
  45             GraphNode cityNode = map.insertNode(cityName, cityX, cityY);
  46             //System.out.println(cityName + " at position (" + cityX + ", " + cityY + ")");
  47
  48             List<Element> roadElements = cityElement.getChildren();
  49             // Iterate through roadElements
  50             for (Element roadElement: roadElements) {
  51                String roadTo = roadElement.getAttributeValue("to");
  52                Double roadSpeed = Double.parseDouble(roadElement.getAttributeValue("speed"));
  53                // Prints all roads connected to the current cityElement
  54                //System.out.println("    road to -> " + roadElement.getAttributeValue("to"));
  55                Double time = 1.0;
  56                if (map.isInGraph(roadTo)) { // @FIX declare var in if condition
  57                   GraphNode roadToNode = map.getNode(roadTo);
  58                   Double distance = Math.hypot((cityNode.getX() - roadToNode.getX()),
  59                                                (cityNode.getY() - roadToNode.getY()));
  60                   time = distance / (roadSpeed / 3.6);
  61                }
  62                map.insertEdge(cityName, roadTo, time);
  63                // @FIX change roadSpeed to time
  64             }
  65          }
  66       }
  67       catch (IOException e) {
  68          System.err.println ("Could not read/find file.");
  69          System.exit(1);
  70       } catch (JDOMException e) {
  71          System.err.println ("File is not in valid XML format?");
  72          System.exit(1);
  73       } catch (NumberFormatException e) {
  74          System.err.println ("Coordinates cannot be parsed.");
  75       }
  76    }
  77
  78    /**
  79     * Utför sökning med Greedy Search.
  80     *
  81     * @param from Den plats sökningen börjar från.
  82     * @param to Den plats sökningen avslutas på.
  83     */
  84    public String greedySearch (String from, String to) {
  85        // 1. Set N to be a sorted list of initial nodes;
  86        PriorityQueue<GraphNode> bigN =
  87            new PriorityQueue<GraphNode>(this.map.getNodes());
  88        GraphNode n;
  89        while (!bigN.isEmpty()) { // 2. If N is empty,
  90            // 3. set n to be the first node in N, and remove n from N;
  91            // 4. If n is a goal node, exit and signal success;
  92            // 5. Otherwise add the children of n to N, sort the nodes in N
  93            // according to the value on their evaluation function and return to
  94            // step 2.
  95        }
  96        // 2. ... exit and signal failure
  97        return null;
  98    }
  99
 100    /**
 101     * Utför sökning med A*.
 102     *
 103     * @param from Den plats sökningen börjar från.
 104     * @param to Den plats sökningen avslutas på.
 105     * @param fastest Om <code>true</code>, hitta snabbaste vägen,
 106     * annars den kortaste.
 107     */
 108    public String aStar (String from, String to, boolean fastest) {
 109        // skapa en tabell över hur långt det är från alla platser på
 110        // kartan till målet för sökningen
 111        // Hashtable<String, Double> targetDistTable =
 112       //            new Hashtable<String, Double>(map.size());
 113       //        // spara ned målnoden
 114       //        GraphNode targetLocation = map.getNode(to);
 115       //        GraphNode tempNode;
 116       //        Enumeration e;
 117       //        // för alla noder
 118       //        for (e = map.getNodes(),
 119       //                 tempNode = (GraphNode) e.nextElement();
 120       //             e.hasMoreElements(); // medan e har element
 121       //             tempNode = (GraphNode) e.nextElement()) {
 122       //            // spara avståndet till målnoden för varje nod
 123       //            targetDistTable.put(tempNode.getName(),
 124       //                             Math.hypot(targetLocation.getX()-tempNode.getX(),
 125       //                                        targetLocation.getY()-tempNode.getY()));
 126       //}
 127        /*
 128         * implementation av aStar.
 129         */
 130        return "";
 131    }
 132
 133    /**
 134     * Utför bredden-förstsökning.
 135     *
 136     * @param from Den plats sökningen börjar från.
 137     * @param to Den plats sökningen avslutas på.
 138     */
 139    public String breadthFirst (String from, String to) {
 140       // Comments fetched from
 141       // http://en.wikipedia.org/wiki/Breadth-first_search
 142       // at Tue Oct 14 12:57:18 2008
 143       String pathToGoal = "";
 144       LinkedList<GraphNode> queue = new LinkedList();
 145
 146
 147       // 1. Put the root node on the queue.
 148       queue.add(map.getNode(from));
 149       while (!queue.isEmpty()) {
 150          // 2. Pull a node from the beginning of the queue and examine it.
 151          GraphNode tmpNode = queue.removeFirst();
 152          //   * If the searched element is found in this node, quit the search and return a result.
 153          if (tmpNode.getName().equals(to)) {
 154             // Found goal
 155             //return
 156          }
 157
 158          //   * 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.
 159
 160          // 3. If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
 161
 162       }
 163       return "";
 164    }
 165
 166    /**
 167     * Utför djupet-förstsökning.
 168     *
 169     * @param from Den plats sökningen börjar från.
 170     * @param to Den plats sökningen avslutas på.
 171     */
 172    public String depthFirst (String from, String to) {
 173       /*
 174        * implementation av depthFirst.
 175        */
 176       return "";
 177    }
 178
 179    public String toString() {
 180       return map.toString();
 181    }
 182 }