src/MySearcher.java

   1 import java.io.File;
   2 import java.io.IOException;
   3 import java.util.List;
   4 import java.util.LinkedList;
   5 import java.util.PriorityQueue;
   6 import java.util.Enumeration;
   7 import org.jdom.*;
   8
   9 /**
  10  * Denna klass implementerar olika sökalgoritmer för att hitta vägar
  11  * mellan två platser på en karta.
  12  */
  13 public class MySearcher extends MapSearcher {
  14    private Graph map;
  15
  16    /**
  17     * Skapar en ny MySearcher-instans.
  18     */
  19    public MySearcher () {
  20       super ();
  21    }
  22
  23    /**
  24     * Specificerar kartan utifrån en fil i XML-format.
  25     *
  26     * @param map Den XML-fil som representerar kartan.
  27     */
  28    public void setMap(File mapFile) {
  29       Document doc;
  30       List<Element> cityElements;
  31       try {
  32          doc = loadXmlMap(mapFile);
  33          cityElements = doc.getRootElement().getChildren();
  34          map = new Graph(cityElements.size(), 5);
  35
  36          // Iterate through cityElements
  37          for (Element cityElement: cityElements) {
  38             map.insertNode(cityElement.getAttributeValue("id"),
  39                            Integer.parseInt(cityElement.getAttributeValue("x")),
  40                            Integer.parseInt(cityElement.getAttributeValue("y")));
  41          }
  42
  43          // Iterate through cityElements once more to add roads
  44          for (Element cityElement: cityElements) {
  45             GraphNode cityNode = map.getNode(cityElement.getAttributeValue("id"));
  46
  47             // Iterate through roadElements in this cityElement
  48             List<Element> roadElements = cityElement.getChildren();
  49             for (Element roadElement: roadElements) {
  50                GraphNode nodeAtEndOfRoad = map.getNode(roadElement.getAttributeValue("to"));
  51                Double distance = Math.hypot((cityNode.getX() - nodeAtEndOfRoad.getX()),
  52                                             (cityNode.getY() - nodeAtEndOfRoad.getY()));
  53                Double time = distance /
  54                   (Double.parseDouble(roadElement.getAttributeValue("speed")) / 3.6);
  55                map.insertEdge(cityNode.getName(),
  56                               nodeAtEndOfRoad.getName(),
  57                               time);
  58             }
  59          }
  60       }
  61       catch (IOException e) {
  62          System.err.println ("Could not read/find file.");
  63          System.exit(1);
  64       }
  65       catch (JDOMException e) {
  66          System.err.println (e.getMessage());
  67          System.exit(1);
  68       }
  69       catch (NumberFormatException e) {
  70          System.err.println ("Coordinates cannot be parsed. Check XML-file for errors.");
  71          System.exit(1);
  72       }
  73    }
  74
  75    /**
  76     * Utför sökning med Greedy Search.
  77     *
  78     * @param from Den plats sökningen börjar från.
  79     * @param to Den plats sökningen avslutas på.
  80     * @return En sträng som representerar vägen från start till mål.
  81     */
  82    public String greedySearch (String from, String to) {
  83       String pathToGoal = "",
  84          expandedNodes = "";
  85       // 1. Set N to be a sorted list of initial nodes;
  86       PriorityQueue<GraphNode> queue =
  87          new PriorityQueue<GraphNode>(this.map.size());
  88       // Set fromNodes distance to 0.0
  89       map.getNode(from).setDistance(0.0);
  90       queue.add(map.getNode(from));
  91       GraphNode n;
  92       while (!queue.isEmpty()) { // 2. If N is empty,
  93          // 3. set n to be the first node in N, and remove n from N;
  94          n = queue.poll();
  95          // store expander
  96          expandedNodes += n.getName() + (n == map.getNode(to) ? "" : ", ");
  97          n.visit();
  98          // 4. If n is the goal node, exit and signal success;
  99          if (n == this.map.getNode(to)) {
 100             pathToGoal = n.getName(); // Goal
 101             n = n.getParent();
 102
 103             while (n != map.getNode(from)) {
 104                pathToGoal = n.getName() + ", " + pathToGoal;
 105                n = n.getParent();
 106             }
 107             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 108             System.out.println("\nAll visited nodes:\n" + expandedNodes + "\n\n");
 109             return "Path to goal:\n" + pathToGoal + "\n";
 110          }
 111          // 5. Otherwise add the children of n to N,
 112          GraphNode neighbour;
 113          for (Enumeration<GraphNode> e = n.getNeighbours();
 114               e.hasMoreElements();) {
 115             neighbour = e.nextElement();
 116             neighbour.setDistance(neighbour.setDistanceToGoal(map.getNode(to)));
 117             if (!neighbour.isVisited() && !queue.contains(neighbour)) {
 118                neighbour.setParent(n);
 119                queue.add(neighbour);
 120             }
 121             // and return to step 2. (end of loop)
 122          }
 123       }
 124       // 2. ... exit and signal failure
 125       return "Goal not found!\n";
 126    }
 127
 128    /**
 129     * Utför sökning med A*.
 130     *
 131     * @param from Den plats sökningen börjar från.
 132     * @param to Den plats sökningen avslutas på.
 133     * @param fastest Om <code>true</code>, hitta snabbaste vägen,
 134     * annars den kortaste.
 135     */
 136    public String aStar (String from, String to, boolean fastest) {
 137       String pathToGoal = "",
 138          expandedNodes = "";
 139       // 1. Set N to be a sorted list of initial nodes;
 140       PriorityQueue<GraphNode> queue =
 141          new PriorityQueue<GraphNode>(this.map.size());
 142       // Set fromNodes distance to 0.0
 143       map.getNode(from).setDistance(0.0);
 144       queue.add(map.getNode(from));
 145       GraphNode n;
 146       while (!queue.isEmpty()) { // 2. If N is empty,
 147          // 3. set n to be the first node in N, and remove n from N;
 148          n = queue.poll();
 149          // store expander
 150          expandedNodes += n.getName() + (n == map.getNode(to) ? "" : ", ");
 151          n.visit();
 152          // 4. If n is the goal node, exit and signal success;
 153          if (n == this.map.getNode(to)) {
 154             pathToGoal = n.getName(); // Goal
 155             n = n.getParent();
 156
 157             while (n != map.getNode(from)) {
 158                pathToGoal = n.getName() + ", " + pathToGoal;
 159                n = n.getParent();
 160             }
 161             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 162             System.out.println("\nAll visited nodes:\n" + expandedNodes + "\n\n");
 163             return "Path to goal:\n" + pathToGoal + "\n";
 164          }
 165          // 5. Otherwise add the children of n to N,
 166          GraphNode neighbour;
 167          for (Enumeration<GraphNode> e = n.getNeighbours();
 168               e.hasMoreElements();) {
 169             neighbour = e.nextElement();
 170             neighbour.setDistance(n.getDistance()
 171                                   + n.getWeight(neighbour)
 172                                   + neighbour.setDistanceToGoal(map.getNode(to)));
 173             // sort the nodes in N according to the value on their
 174             // evaluation function
 175             if (!neighbour.isVisited() && !queue.contains(neighbour)) {
 176                neighbour.setParent(n);
 177                queue.add(neighbour);
 178             }
 179             // and return to step 2. (end of loop)
 180          }
 181       }
 182       System.out.println();
 183       // 2. ... exit and signal failure
 184       return "Goal not found!\n";
 185    }
 186
 187    /**
 188     * Utför bredden-förstsökning.
 189     *
 190     * @param from Den plats sökningen börjar från.
 191     * @param to Den plats sökningen avslutas på.
 192     */
 193    public String breadthFirst (String from, String to) {
 194       /*
 195        * Comments fetched from
 196        * http://en.wikipedia.org/wiki/Breadth-first_search
 197        * at Tue Oct 14 12:57:18 2008
 198        */
 199       LinkedList<GraphNode> q = new LinkedList<GraphNode>();
 200       String expandedNodes = "";
 201       String pathToGoal = "";
 202       // 1. Put the root node on the queue.
 203       q.add(map.getNode(from));
 204       while (!q.isEmpty()) {
 205          // 2. Pull a node from the beginning of the queue and examine it.
 206          GraphNode n = q.removeFirst();
 207          n.visit();
 208
 209          //   * If the searched element is found in this node, quit
 210          //   * the search and return a result.
 211          if (n.getName().equals(to)) {
 212             expandedNodes += to;
 213
 214             pathToGoal = n.getName(); // Goal
 215             n = n.getParent();
 216
 217             while (n != map.getNode(from)) {
 218                pathToGoal = n.getName() + ", " + pathToGoal;
 219                n = n.getParent();
 220             }
 221             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 222             System.out.println("\nAll visited nodes:\n" + expandedNodes + "\n\n");
 223             return "Path to goal:\n" + pathToGoal + "\n";
 224          }
 225          //   * Otherwise push all the (so-far-unexamined) successors
 226          //   * (the direct child nodes) of this node into the end of
 227          //   * the queue, if there are any.
 228          else {
 229             for (Enumeration e = n.getNeighbours(); e.hasMoreElements();) {
 230                GraphNode neighbour = (GraphNode) e.nextElement();
 231                if (!neighbour.isVisited()) {
 232                   neighbour.setParent(n);
 233                   q.add(neighbour);
 234                }
 235             }
 236          }
 237          expandedNodes += n.getName() + ", ";
 238       }
 239       return "Goal not found!\n";
 240    }
 241
 242    /**
 243     * Utför djupet-förstsökning.
 244     *
 245     * @param from Den plats sökningen börjar från.
 246     * @param to Den plats sökningen avslutas på.
 247     */
 248    public String depthFirst (String from, String to) {
 249       LinkedList<GraphNode> s = new LinkedList<GraphNode>();
 250       String expandedNodes = "";
 251       String pathToGoal = "";
 252       // 1. Push the root node onto the stack.
 253       s.add(map.getNode(from));
 254       while (!s.isEmpty()) {
 255          // 2. Pop a node from the stack
 256          GraphNode n = s.removeLast();
 257          //   * Mark this node as visited
 258          n.visit();
 259          //   * If the searched element is found in this node, quit
 260          //   * the search and return a result.
 261          if (n.getName().equals(to)) {
 262             expandedNodes += n.getName();
 263             pathToGoal = n.getName(); // Goal
 264             n = n.getParent();
 265
 266             while (n != map.getNode(from)) {
 267                pathToGoal = n.getName() + ", " + pathToGoal;
 268                n = n.getParent();
 269             }
 270             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 271             System.out.println("\nAll visited nodes:\n" + expandedNodes + "\n\n");
 272             return "Path to goal:\n" + pathToGoal + "\n";
 273          }
 274          //   * Otherwise push all the unvisited connecting nodes of n
 275          else {
 276             for (Enumeration e = n.getNeighbours();
 277                  e.hasMoreElements();) {
 278                GraphNode neighbour = (GraphNode) e.nextElement();
 279                if (!neighbour.isVisited()) {
 280                   neighbour.setParent(n);
 281                   s.add(neighbour);
 282                }
 283             }
 284          }
 285          expandedNodes += n.getName() + ", ";
 286       }
 287       return "Goal not found!\n";
 288    }
 289
 290    public String toString() {
 291       return map.toString();
 292    }
 293 }