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> queue = new LinkedList<GraphNode>();
 200       String expandedNodes = "";
 201       String pathToGoal = "";
 202       // 1. Put the root node on the queue.
 203       queue.add(map.getNode(from));
 204       while (!queue.isEmpty()) {
 205          // 2. Pull a node from the beginning of the queue and examine it.
 206          GraphNode n = queue.removeFirst();
 207          n.visit();
 208          expandedNodes += n.getName() + (n == map.getNode(to) ? "" : ", ");
 209
 210          //   * If the searched element is found in this node, quit
 211          //   * the search and return a result.
 212          if (n.getName().equals(to)) {
 213             pathToGoal = n.getName(); // Goal
 214             n = n.getParent();
 215
 216             while (n != map.getNode(from)) {
 217                pathToGoal = n.getName() + ", " + pathToGoal;
 218                n = n.getParent();
 219             }
 220             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 221             System.out.println("\nAll visited nodes:\n" + expandedNodes + "\n\n");
 222             return "Path to goal:\n" + pathToGoal + "\n";
 223          }
 224          //   * Otherwise push all the (so-far-unexamined) successors
 225          //   * (the direct child nodes) of this node into the end of
 226          //   * the queue, if there are any.
 227          else {
 228             for (Enumeration e = n.getNeighbours(); e.hasMoreElements();) {
 229                GraphNode neighbour = (GraphNode) e.nextElement();
 230                if (!neighbour.isVisited() && !queue.contains(neighbour)) {
 231                   neighbour.setParent(n);
 232                   queue.add(neighbour);
 233                }
 234             }
 235          }
 236       }
 237       return "Goal not found!\n";
 238    }
 239
 240    /**
 241     * Utför djupet-förstsökning.
 242     *
 243     * @param from Den plats sökningen börjar från.
 244     * @param to Den plats sökningen avslutas på.
 245     */
 246    public String depthFirst (String from, String to) {
 247       LinkedList<GraphNode> stack = new LinkedList<GraphNode>();
 248       String expandedNodes = "";
 249       String pathToGoal = "";
 250       // 1. Push the root node onto the stack.
 251       stack.add(map.getNode(from));
 252       while (!stack.isEmpty()) {
 253          // 2. Pop a node from the stack
 254          GraphNode n = stack.removeLast();
 255          //   * Mark this node as visited
 256          n.visit();
 257          //   * If the searched element is found in this node, quit
 258          //   * the search and return a result.
 259          if (n.getName().equals(to)) {
 260             expandedNodes += n.getName();
 261             pathToGoal = n.getName(); // Goal
 262             n = n.getParent();
 263
 264             while (n != map.getNode(from)) {
 265                pathToGoal = n.getName() + ", " + pathToGoal;
 266                n = n.getParent();
 267             }
 268             pathToGoal = n.getName() + ", " + pathToGoal; // Beginning
 269             System.out.println("\nAll visited nodes:\n" + expandedNodes + "\n\n");
 270             return "Path to goal:\n" + pathToGoal + "\n";
 271          }
 272          //   * Otherwise push all the unvisited connecting nodes of n
 273          else {
 274             for (Enumeration e = n.getNeighbours();
 275                  e.hasMoreElements();) {
 276                GraphNode neighbour = (GraphNode) e.nextElement();
 277                if (!neighbour.isVisited() && !stack.contains(neighbour)) {
 278                   neighbour.setParent(n);
 279                   stack.add(neighbour);
 280                }
 281             }
 282          }
 283          expandedNodes += n.getName() + ", ";
 284       }
 285       return "Goal not found!\n";
 286    }
 287
 288    public String toString() {
 289       return map.toString();
 290    }
 291 }