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  * @author "Anton Johansson" <anton.johansson@gmail.com>
  14  * @author "Victor Zamanian" <victor.zamanian@gmail.com>
  15  * @version 1.0
  16  */
  17 public class MySearcher extends MapSearcher {
  18
  19    private Graph map;
  20    private int topSpeed;
  21
  22    /**
  23     * Skapar en ny MySearcher-instans.
  24     */
  25    public MySearcher () {
  26       super ();
  27       topSpeed = 0;
  28    }
  29
  30    /**
  31     * Specificerar kartan utifrån en fil i XML-format. The xml-file
  32     * should look like:
  33     *<pre>
  34     * &lt;?xml version='1.0' encoding='ISO-8859-1' ?&gt;
  35     * &lt;map&gt;
  36     *    &lt;node id="Teg" x="1720099" y="7072732"&gt;
  37     *       &lt;road to="Rondellen" speed="50" /&gt;
  38     *       &lt;road to="Tegsbron" speed="110" /&gt;
  39     *    &lt;/node&gt;
  40     *    ...
  41     * &lt;/map&gt;
  42     *</pre>
  43     * @param mapFile a File containing the xml representation of the
  44     * map.
  45     */
  46    public void setMap(File mapFile) {
  47       Document doc;
  48       List<Element> cityElements;
  49       try {
  50          doc = loadXmlMap(mapFile);
  51          cityElements = doc.getRootElement().getChildren();
  52          map = new Graph(cityElements.size(), 5);
  53
  54          // Iterate through cityElements
  55          for (Element cityElement: cityElements) {
  56             map.insertNode(cityElement.getAttributeValue("id"),
  57                            Integer.parseInt(cityElement.getAttributeValue("x")),
  58                            Integer.parseInt(cityElement.getAttributeValue("y")));
  59          }
  60
  61          // Iterate through cityElements once more to add roads
  62          for (Element cityElement: cityElements) {
  63             GraphNode cityNode = map.getNode(cityElement.getAttributeValue("id"));
  64
  65             // Iterate through roadElements in this cityElement
  66             List<Element> roadElements = cityElement.getChildren();
  67             for (Element roadElement: roadElements) {
  68                GraphNode nodeAtEndOfRoad = map.getNode(roadElement.getAttributeValue("to"));
  69                Double distance = Math.hypot((cityNode.getX() - nodeAtEndOfRoad.getX()),
  70                                             (cityNode.getY() - nodeAtEndOfRoad.getY()));
  71
  72                Road road =
  73                   new Road(Integer.parseInt(roadElement.getAttributeValue("speed")),
  74                            distance);
  75                if (road.getSpeed() > topSpeed) {
  76                   topSpeed = road.getSpeed();
  77                }
  78                map.insertEdge(cityNode.getName(),
  79                               nodeAtEndOfRoad.getName(),
  80                               road);
  81             }
  82          }
  83       }
  84       catch (IOException e) {
  85          System.err.println ("Could not read/find file.");
  86          System.exit(1);
  87       }
  88       catch (JDOMException e) {
  89          System.err.println (e.getMessage());
  90          System.exit(1);
  91       }
  92       catch (NumberFormatException e) {
  93          System.err.println ("Coordinates cannot be parsed. Check XML-file for errors.");
  94          System.exit(1);
  95       }
  96    }
  97
  98    /**
  99     * Utför sökning med Greedy Search.
 100     *
 101     * @param from Den plats sökningen börjar från.
 102     * @param to Den plats sökningen avslutas på.
 103     * @return En text-representation som innhåller sökvägen till
 104     * målet. Ex: nod1, nod2, nod3, mål
 105     */
 106    public String greedySearch (String from, String to) {
 107       String pathToGoal = "",
 108          expandedNodes = "";
 109       // 1. Set N to be a sorted list of initial nodes;
 110       PriorityQueue<GraphNode> queue =
 111          new PriorityQueue<GraphNode>(this.map.size());
 112       // Set fromNodes distance to 0.0
 113       map.getNode(from).setDistanceTraveled(0.0);
 114       queue.add(map.getNode(from));
 115       GraphNode n;
 116       while (!queue.isEmpty()) { // 2. If N is empty,
 117          // 3. set n to be the first node in N, and remove n from N;
 118          n = queue.poll();
 119          // store expander
 120          expandedNodes += n.getName() + (n == map.getNode(to) ? "" : ", ");
 121          n.visit();
 122          // 4. If n is the goal node, exit and signal success;
 123          if (n == this.map.getNode(to)) {
 124             pathToGoal = n.getName(); // Goal
 125             n = n.getParent();
 126
 127             while (n != map.getNode(from)) {
 128                pathToGoal = n.getName() + ", " + pathToGoal;
 129                n = n.getParent();
 130             }
 131             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 132             System.out.println("\nAll expanded nodes:\n" + expandedNodes + "\n\n");
 133             return pathToGoal;
 134          }
 135          // 5. Otherwise add the children of n to N,
 136          GraphNode neighbour;
 137          for (Enumeration<GraphNode> e = n.getNeighbours();
 138               e.hasMoreElements();) {
 139             neighbour = e.nextElement();
 140             neighbour.setEvalFuncVal(neighbour.getDistanceToNode(map.getNode(to)));
 141             if (!neighbour.isVisited() && !queue.contains(neighbour)) {
 142                neighbour.setParent(n);
 143                queue.add(neighbour);
 144             }
 145             // and return to step 2. (end of loop)
 146          }
 147       }
 148       // 2. ... exit and signal failure
 149       return "Goal not found!\n";
 150    }
 151
 152    /**
 153     * Utför sökning med A*.
 154     *
 155     * @param from Den plats sökningen börjar från.
 156     * @param to Den plats sökningen avslutas på.
 157     * @param fastest Om <code>true</code>, hitta snabbaste vägen,
 158     * annars den kortaste.
 159     * @return En text-representation som innhåller sökvägen till
 160     * målet. Ex: nod1, nod2, nod3, mål
 161     */
 162    public String aStar (String from, String to, boolean fastest) {
 163       String pathToGoal = "",
 164          expandedNodes = "";
 165
 166       // 1. Set N to be a sorted list of initial nodes;
 167       PriorityQueue<GraphNode> queue =
 168          new PriorityQueue<GraphNode>(this.map.size());
 169       // Set fromNodes distance to 0.0
 170       map.getNode(from).setDistanceTraveled(0.0);
 171       queue.add(map.getNode(from));
 172
 173       GraphNode n;
 174       while (!queue.isEmpty()) { // 2. If N is empty,
 175          // 3. set n to be the first node in N, and remove n from N;
 176          n = queue.poll();
 177          // store expander
 178          expandedNodes += n.getName() + (n == map.getNode(to) ? "" : ", ");
 179          n.visit();
 180          // 4. If n is the goal node, exit and signal success;
 181          if (n == this.map.getNode(to)) {
 182             pathToGoal = n.getName(); // Goal
 183             n = n.getParent();
 184
 185             while (n != map.getNode(from)) {
 186                pathToGoal = n.getName() + ", " + pathToGoal;
 187                n = n.getParent();
 188             }
 189             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 190             System.out.println("\n    All expanded nodes:\n    " + expandedNodes + "\n\n");
 191             return pathToGoal;
 192          }
 193
 194          // 5. Otherwise add the children of n to N,
 195          GraphNode neighbour;
 196          for (Enumeration<GraphNode> e = n.getNeighbours();
 197               e.hasMoreElements();) {
 198             neighbour = e.nextElement();
 199
 200             if (!neighbour.isVisited()) {
 201                Double evalFunctionValue;
 202                // Fastest path
 203                if (fastest) {
 204                   evalFunctionValue = n.getDistanceTraveled()
 205                      + ((Road) n.getEdge(neighbour)).getTravelTime()
 206                      + neighbour.getDistanceToNode(map.getNode(to)) / topSpeed;
 207                }
 208                // Shortest path
 209                else {
 210                   evalFunctionValue = n.getDistanceTraveled()
 211                      + ((Road) n.getEdge(neighbour)).getDistance()
 212                      + neighbour.getDistanceToNode(map.getNode(to));
 213                }
 214
 215                if (queue.contains(neighbour)
 216                    && evalFunctionValue >= neighbour.getEvalFuncVal()) {
 217                   // Queue already contains a better way to this
 218                   // node, break the for-loop here and continue.
 219                   continue;
 220                }
 221
 222                if (fastest) {
 223                   neighbour.setDistanceTraveled(n.getDistanceTraveled()
 224                                                 + ((Road) n.getEdge(neighbour)).getTravelTime());
 225                }
 226                else { // shortest
 227                   neighbour.setDistanceTraveled(n.getDistanceTraveled()
 228                                                 + ((Road) n.getEdge(neighbour)).getDistance());
 229                }
 230
 231                neighbour.setEvalFuncVal(evalFunctionValue);
 232                neighbour.setParent(n);
 233
 234                if (!queue.contains(neighbour)) {
 235                   queue.add(neighbour);
 236                }
 237             }
 238          }
 239       }
 240       System.out.println();
 241       // 2. ... exit and signal failure
 242       return "Goal not found!\n";
 243    }
 244
 245    /**
 246     * Utför bredden-förstsökning.
 247     *
 248     * @param from Den plats sökningen börjar från.
 249     * @param to Den plats sökningen avslutas på.
 250     * @return En text-representation som innhåller sökvägen till
 251     * målet. Ex: nod1, nod2, nod3, mål
 252     */
 253    public String breadthFirst (String from, String to) {
 254       /*
 255        * Comments fetched from
 256        * http://en.wikipedia.org/wiki/Breadth-first_search
 257        * at Tue Oct 14 12:57:18 2008
 258        */
 259       LinkedList<GraphNode> queue = new LinkedList<GraphNode>();
 260       String expandedNodes = "";
 261       String pathToGoal = "";
 262       // 1. Put the root node on the queue.
 263       queue.add(map.getNode(from));
 264       while (!queue.isEmpty()) {
 265          // 2. Pull a node from the beginning of the queue and examine it.
 266          GraphNode n = queue.removeFirst();
 267          n.visit();
 268          expandedNodes += n.getName() + (n == map.getNode(to) ? "" : ", ");
 269
 270          //   * If the searched element is found in this node, quit
 271          //   * the search and return a result.
 272          if (n.getName().equals(to)) {
 273             pathToGoal = n.getName(); // Goal
 274             n = n.getParent();
 275
 276             while (n != map.getNode(from)) {
 277                pathToGoal = n.getName() + ", " + pathToGoal;
 278                n = n.getParent();
 279             }
 280             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 281             System.out.println("\nAll expanded nodes:\n" + expandedNodes + "\n\n");
 282             return pathToGoal;
 283          }
 284          //   * Otherwise push all the (so-far-unexamined) successors
 285          //   * (the direct child nodes) of this node into the end of
 286          //   * the queue, if there are any.
 287          else {
 288             for (Enumeration<GraphNode> e = n.getNeighbours(); e.hasMoreElements();) {
 289                GraphNode neighbour = e.nextElement();
 290                if (!neighbour.isVisited() && !queue.contains(neighbour)) {
 291                   neighbour.setParent(n);
 292                   queue.add(neighbour);
 293                }
 294             }
 295          }
 296       }
 297       return "Goal not found!\n";
 298    }
 299
 300    /**
 301     * Utför djupet-förstsökning.
 302     *
 303     * @param from Den plats sökningen börjar från.
 304     * @param to Den plats sökningen avslutas på.
 305     * @return En text-representation som innhåller sökvägen till
 306     * målet. Ex: nod1, nod2, nod3, mål
 307     */
 308    public String depthFirst (String from, String to) {
 309       LinkedList<GraphNode> stack = new LinkedList<GraphNode>();
 310       String expandedNodes = "";
 311       String pathToGoal = "";
 312       // 1. Push the root node onto the stack.
 313       stack.add(map.getNode(from));
 314       while (!stack.isEmpty()) {
 315          // 2. Pop a node from the stack
 316          GraphNode n = stack.removeLast();
 317          //   * Mark this node as visited
 318          n.visit();
 319          //   * If the searched element is found in this node, quit
 320          //   * the search and return a result.
 321          if (n.getName().equals(to)) {
 322             expandedNodes += n.getName();
 323             pathToGoal = n.getName(); // Goal
 324             n = n.getParent();
 325
 326             while (n != map.getNode(from)) {
 327                pathToGoal = n.getName() + ", " + pathToGoal;
 328                n = n.getParent();
 329             }
 330             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 331             System.out.println("\nAll expanded nodes:\n" + expandedNodes + "\n\n");
 332             return pathToGoal;
 333          }
 334          //   * Otherwise push all the unvisited connecting nodes of n
 335          else {
 336             for (Enumeration<GraphNode> e = n.getNeighbours();
 337                  e.hasMoreElements();) {
 338                GraphNode neighbour = e.nextElement();
 339                if (!neighbour.isVisited() && !stack.contains(neighbour)) {
 340                   neighbour.setParent(n);
 341                   stack.add(neighbour);
 342                }
 343             }
 344          }
 345          expandedNodes += n.getName() + ", ";
 346       }
 347       return "Goal not found!\n";
 348    }
 349
 350    /**
 351     * Returnerar en text-representation av kartan satt i metoden
 352     * setMap().
 353     *
 354     * @return En text-representation av kartan satt i metoden
 355     * setMap().
 356     */
 357    public String toString() {
 358       return map.toString();
 359    }
 360 }