2 import java
.io
.IOException
;
4 import java
.util
.LinkedList
;
5 import java
.util
.PriorityQueue
;
6 import java
.util
.Hashtable
;
7 import java
.util
.Enumeration
;
11 * Beskrivning av klassen.
13 public class MySearcher
extends MapSearcher
{
17 * Skapar en ny MySearcher-instans.
19 public MySearcher () {
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
) {
32 List
<Element
> cityElements
;
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"));
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.");
68 } catch (JDOMException e
) {
69 System
.err
.println ("File is not in valid XML format?");
71 } catch (NumberFormatException e
) {
72 System
.err
.println ("Coordinates cannot be parsed.");
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
));
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;
96 System
.out
.print(" " + n
.getName() + ", ");
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,
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() + ": " +
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
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;
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.
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
)) {
179 while (n
!= map
.getNode(from
)) {
180 pathToGoal
= n
.getName() + ", " + pathToGoal
;
183 pathToGoal
= n
.getName() + ", " + pathToGoal
;
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.
190 expandedNodes
+= n
.getName() + ", ";
191 for (Enumeration e
= n
.getNeighbours(); e
.hasMoreElements();) {
192 GraphNode neighbour
= (GraphNode
) e
.nextElement();
193 neighbour
.setParent(n
);
197 // If the queue is empty, every node on the graph has been
198 // examined -- quit the search and return "not found".
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.
220 public String
toString() {
221 return map
.toString();