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