Changed compareTo in GraphNode to work with the queue used in greedySearch.
[ailab2.git] / src / MySearcher.java
blobebc8118452ded83189222482baeac1ce085b8a64
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.*;
10 /**
11 * Beskrivning av klassen.
13 public class MySearcher extends MapSearcher {
14 private Graph map;
16 /**
17 * Skapar en ny MySearcher-instans.
19 public MySearcher () {
20 super ();
23 /**
24 * Specificerar kartan.
26 * @param map Den XML-fil som representerar kartan.
28 * @TODO fixa this.map.insertEdge() för alla noder.
30 public void setMap(File mapFile) {
31 Document doc;
32 List<Element> cityElements;
33 try {
34 doc = loadXmlMap(mapFile);
35 //System.out.println(doc.getRootElement().toString());
36 cityElements = doc.getRootElement().getChildren();
37 map = new Graph(cityElements.size(), 5);
38 // Iterate through cityElements
39 for (Element cityElement: cityElements) {
40 // Prints names of cities
41 String cityName = cityElement.getAttributeValue("id");
42 int cityX = Integer.parseInt(cityElement.getAttributeValue("x"));
43 int cityY = Integer.parseInt(cityElement.getAttributeValue("y"));
44 GraphNode cityNode = map.insertNode(cityName, cityX, cityY);
45 //System.out.println(cityName + " at position (" + cityX + ", " + cityY + ")");
47 List<Element> roadElements = cityElement.getChildren();
48 // Iterate through roadElements
49 for (Element roadElement: roadElements) {
50 String roadTo = roadElement.getAttributeValue("to");
51 Double roadSpeed = Double.parseDouble(roadElement.getAttributeValue("speed"));
52 // Prints all roads connected to the current cityElement
53 //System.out.println(" road to -> " + roadElement.getAttributeValue("to"));
54 Double time = 1.0;
55 if (map.isInGraph(roadTo)) { // @FIX declare var in if condition
56 GraphNode roadToNode = map.getNode(roadTo);
57 Double distance = Math.hypot((cityNode.getX() - roadToNode.getX()),
58 (cityNode.getY() - roadToNode.getY()));
59 time = distance / (roadSpeed / 3.6);
61 map.insertEdge(cityName, roadTo, time);
65 catch (IOException e) {
66 System.err.println ("Could not read/find file.");
67 System.exit(1);
68 } catch (JDOMException e) {
69 System.err.println ("File is not in valid XML format?");
70 System.exit(1);
71 } catch (NumberFormatException e) {
72 System.err.println ("Coordinates cannot be parsed.");
76 /**
77 * Utför sökning med Greedy Search.
79 * @param from Den plats sökningen börjar från.
80 * @param to Den plats sökningen avslutas på.
82 public String greedySearch (String from, String to) {
83 String pathToGoal = null;
84 // 1. Set N to be a sorted list of initial nodes;
85 System.err.println("STARTING GREEDY SEARCH!");
86 PriorityQueue<GraphNode> queue =
87 new PriorityQueue<GraphNode>(this.map.size());
88 System.err.println("Adding " + to + " to queue.");
89 queue.add(map.getNode(from));
90 GraphNode n;
91 System.out.print("Expanding:");
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 // print expander
96 System.out.print(" " + n.getName() + ", ");
97 n.visit();
98 // 4. If n is the goal node, exit and signal success;
99 if (n == this.map.getNode(to))
100 return pathToGoal + n.getName();
101 pathToGoal += n.getName() + ", ";
102 // 5. Otherwise add the children of n to N,
103 GraphNode neighbour;
104 for (Enumeration<GraphNode> e = n.getNeighbours();
105 e.hasMoreElements();) {
106 neighbour = e.nextElement();
107 neighbour.setDistance(n.getWeight(neighbour));
108 System.err.println("Distance between " +
109 n.getName() + " and " +
110 neighbour.getName() + ": " +
111 n.getDistance());
112 // sort the nodes in N according to the value on their
113 // evaluation function
114 if (!neighbour.isVisited())
115 queue.add(neighbour);
116 // and return to step 2. (end of loop)
119 System.out.println();
120 // 2. ... exit and signal failure
121 return null;
125 * Utför sökning med A*.
127 * @param from Den plats sökningen börjar från.
128 * @param to Den plats sökningen avslutas på.
129 * @param fastest Om <code>true</code>, hitta snabbaste vägen,
130 * annars den kortaste.
132 public String aStar (String from, String to, boolean fastest) {
133 // skapa en tabell över hur långt det är från alla platser på
134 // kartan till målet för sökningen
135 // Hashtable<String, Double> targetDistTable =
136 // new Hashtable<String, Double>(map.size());
137 // // spara ned målnoden
138 // GraphNode targetLocation = map.getNode(to);
139 // GraphNode tempNode;
140 // Enumeration e;
141 // // för alla noder
142 // for (e = map.getNodes(),
143 // tempNode = (GraphNode) e.nextElement();
144 // e.hasMoreElements(); // medan e har element
145 // tempNode = (GraphNode) e.nextElement()) {
146 // // spara avståndet till målnoden för varje nod
147 // targetDistTable.put(tempNode.getName(),
148 // Math.hypot(targetLocation.getX()-tempNode.getX(),
149 // targetLocation.getY()-tempNode.getY()));
152 * implementation av aStar.
154 return "";
158 * Utför bredden-förstsökning.
160 * @param from Den plats sökningen börjar från.
161 * @param to Den plats sökningen avslutas på.
163 public String breadthFirst (String from, String to) {
164 // Comments fetched from
165 // http://en.wikipedia.org/wiki/Breadth-first_search
166 // at Tue Oct 14 12:57:18 2008
167 LinkedList<GraphNode> q = new LinkedList<GraphNode>();
168 String expandedNodes = "";
169 String pathToGoal = "";
170 // 1. Put the root node on the queue.
171 q.add(map.getNode(from));
172 while (!q.isEmpty()) {
173 // 2. Pull a node from the beginning of the queue and examine it.
174 GraphNode n = q.removeFirst();
175 // * If the searched element is found in this node, quit
176 // * the search and return a result.
177 if (n.getName().equals(to)) {
178 expandedNodes += to;
179 while (n != map.getNode(from)) {
180 pathToGoal = n.getName() + ", " + pathToGoal;
181 n = n.getParent();
183 pathToGoal = n.getName() + ", " + pathToGoal;
184 break;
186 // * Otherwise push all the (so-far-unexamined) successors
187 // * (the direct child nodes) of this node into the end of
188 // * the queue, if there are any.
189 else {
190 expandedNodes += n.getName() + ", ";
191 for (Enumeration e = n.getNeighbours(); e.hasMoreElements();) {
192 GraphNode neighbour = (GraphNode) e.nextElement();
193 neighbour.setParent(n);
194 q.add(neighbour);
197 // If the queue is empty, every node on the graph has been
198 // examined -- quit the search and return "not found".
199 if (q.isEmpty()) {
200 return "\nGoal not found!";
203 return "\nAll visited nodes:\n" + expandedNodes + "\n"
204 + "Path to goal:\n" + pathToGoal;
208 * Utför djupet-förstsökning.
210 * @param from Den plats sökningen börjar från.
211 * @param to Den plats sökningen avslutas på.
213 public String depthFirst (String from, String to) {
215 * implementation av depthFirst.
217 return "";
220 public String toString() {
221 return map.toString();