From ae4077dc1fc110045b8d3e9cc6a05b304e938aea Mon Sep 17 00:00:00 2001 From: Anton Johansson Date: Mon, 20 Oct 2008 15:09:37 +0200 Subject: [PATCH] Added road implementation, it works kind of like before --- rapport/rapport.tex | 89 ++++++++++++++++++++++++++++++++++--------- src/Graph.java | 8 ++-- src/GraphNode.java | 10 ++--- src/MySearcher.java | 30 ++++++++++----- test/GraphTest.java | 18 ++++----- test/MySearcherLatexTest.java | 10 ++++- test/MySearcherTest.java | 58 ---------------------------- 7 files changed, 117 insertions(+), 106 deletions(-) delete mode 100644 test/MySearcherTest.java diff --git a/rapport/rapport.tex b/rapport/rapport.tex index 0ed1090..fbdf248 100644 --- a/rapport/rapport.tex +++ b/rapport/rapport.tex @@ -145,8 +145,12 @@ sätta in noder och kanter mellan noderna. \subsection{GraphNode.java} Klassen GraphNode används för att spara undan städerna ur kartan. GraphNode har en Hashtabell som sparar länkar till sina -grannar som nycklar och vikten som värde. +grannar som nycklar och vikten som värde. Detta innebär att klassen +kan fråga efter en granne och returnera vikten till denna granne. +Dessutom innehåller GraphNode attribut för att spara information om +den är besökt (\textbf{visited}) och information om vilken nod +den har besökts ifrån (\textbf{parent}). \subsection{Oinformerade sökalgoritmer} Följande sökalgoritmer tar emot två parametrar, \textit{from} och @@ -163,8 +167,9 @@ att lagra noder så agerar de enligt följande procedur: \item Om noden som besöks är målnoden avslutas sökningen och resultat returneras. \item Annars läggs alla obesökta grannoder till i - \textit{datastrukturen} och en länk till noden \textbf{n} sparas i - ett attribut \textbf{parent}.\label{Oparent} + \textit{datastrukturen}, om de inte redan finns representerade i + den, och en länk till noden \textbf{n} sparas i ett attribut + \textbf{parent}.\label{Oparent} \end{enumerate} \item Börja om från steg \ref{Otaut}. \end{enumerate} @@ -234,7 +239,7 @@ från startnoden. \subsubsection{From: Tegsbron to Nydala} \textbf{All expanded nodes:} -Tegsbron, Teg, I20, Rondellen, Station, Obs, TreKorvar, Kyrkan, Gamlia, Foa, Begbilar, On, Flygplatsen, NUS, Berghem, Mariehem, Sofiehem, MIT, Nydala +Tegsbron, Teg, I20, Rondellen, Station, Obs, Kyrkan, TreKorvar, Gamlia, Foa, Begbilar, NUS, Flygplatsen, On, Berghem, Mariehem, Sofiehem, MIT, Nydala \textbf{Path to goal:} @@ -243,7 +248,7 @@ Tegsbron, I20, Obs, Foa, Mariehem, Nydala \subsubsection{From: Flygplatsen to Begbilar} \textbf{All expanded nodes:} -Flygplatsen, TreKorvar, On, Rondellen, Teg, Kyrkan, Tegsbron, NUS, Station, I20, Gamlia, Sofiehem, Obs, Berghem, Alidhem, GimonAs, Foa, Begbilar +Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Teg, NUS, Station, Tegsbron, Sofiehem, Gamlia, I20, Obs, Alidhem, GimonAs, Berghem, Foa, Begbilar \textbf{Path to goal:} @@ -252,7 +257,7 @@ Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar \subsubsection{From: MIT to Flygplatsen} \textbf{All expanded nodes:} -MIT, Berghem, Alidhem, Nydala, Gamlia, Mariehem, Sofiehem, Ok, NUS, Station, Foa, GimonAs, Kyrkan, Obs, I20, Begbilar, Rondellen, Tegsbron, TreKorvar, Teg, Flygplatsen +MIT, Berghem, Alidhem, Nydala, Mariehem, Gamlia, Sofiehem, Ok, Foa, NUS, Station, GimonAs, Begbilar, Obs, Kyrkan, I20, Rondellen, Tegsbron, TreKorvar, Teg, Flygplatsen \textbf{Path to goal:} @@ -261,11 +266,11 @@ MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen \subsubsection{From: Nydala to Gamlia} \textbf{All expanded nodes:} -Nydala, Ok, MIT, Mariehem, Alidhem, Berghem, Foa, Sofiehem, Gamlia +Nydala, Ok, Mariehem, MIT, Alidhem, Berghem, Foa, Sofiehem, Gamlia \textbf{Path to goal:} -Nydala, MIT, Berghem, Gamlia +Nydala, Mariehem, Berghem, Gamlia \subsubsection{From: Teg to Foa} @@ -280,25 +285,25 @@ Teg, Tegsbron, I20, Obs, Foa \subsubsection{From: Tegsbron to Nydala} \textbf{All expanded nodes:} -Tegsbron, Teg, Rondellen, Kyrkan, Station, Obs, Begbilar, Foa, Mariehem, Berghem, MIT, Alidhem, Sofiehem, GimonAs, Ok, Nydala +Tegsbron, I20, Obs, Foa, Mariehem, Nydala \textbf{Path to goal:} -Tegsbron, Teg, Rondellen, Kyrkan, Station, Obs, Foa, Mariehem, Nydala +Tegsbron, I20, Obs, Foa, Mariehem, Nydala \subsubsection{From: Flygplatsen to Begbilar} \textbf{All expanded nodes:} -Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar +Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar \textbf{Path to goal:} -Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar +Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar \subsubsection{From: MIT to Flygplatsen} \textbf{All expanded nodes:} -MIT, Alidhem, Sofiehem, GimonAs, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, On, Flygplatsen +MIT, Alidhem, Ok, Sofiehem, GimonAs, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, On, Flygplatsen \textbf{Path to goal:} @@ -307,26 +312,26 @@ MIT, Alidhem, Sofiehem, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, Tre \subsubsection{From: Nydala to Gamlia} \textbf{All expanded nodes:} -Nydala, Ok, Alidhem, Sofiehem, GimonAs, NUS, Gamlia +Nydala, Mariehem, Berghem, Gamlia \textbf{Path to goal:} -Nydala, Ok, Alidhem, Sofiehem, NUS, Gamlia +Nydala, Mariehem, Berghem, Gamlia \subsubsection{From: Teg to Foa} \textbf{All expanded nodes:} -Teg, Rondellen, TreKorvar, Flygplatsen, On, Kyrkan, Station, Obs, Begbilar, Foa +Teg, Tegsbron, I20, Obs, Foa \textbf{Path to goal:} -Teg, Rondellen, Kyrkan, Station, Obs, Foa +Teg, Tegsbron, I20, Obs, Foa -\subsection{Test $A^*$} +\subsection{Test A* snabbast} \subsubsection{From: Tegsbron to Nydala} \textbf{All expanded nodes:} -Tegsbron, I20, Teg, Station, Obs, Rondellen, Gamlia, Berghem, NUS, Kyrkan, TreKorvar, MIT, Nydala +Tegsbron, I20, Teg, Station, Gamlia, Rondellen, Obs, Berghem, NUS, Kyrkan, TreKorvar, MIT, Nydala \textbf{Path to goal:} @@ -368,6 +373,52 @@ Teg, Tegsbron, Rondellen, I20, Kyrkan, TreKorvar, Obs, Foa \textbf{Path to goal:} Teg, Tegsbron, I20, Obs, Foa +\subsection{Test A* kortast} +\subsubsection{From: Tegsbron to Nydala} + +\textbf{All expanded nodes:} +Tegsbron, I20, Teg, Station, Rondellen, Gamlia, Berghem, NUS, Kyrkan, TreKorvar, Obs, MIT, Sofiehem, Nydala + + +\textbf{Path to goal:} +Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala + +\subsubsection{From: Flygplatsen to Begbilar} + +\textbf{All expanded nodes:} +Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Teg, Station, NUS, Tegsbron, Gamlia, Obs, Sofiehem, Begbilar + + +\textbf{Path to goal:} +Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar + +\subsubsection{From: MIT to Flygplatsen} + +\textbf{All expanded nodes:} +MIT, Alidhem, Berghem, Nydala, Sofiehem, Gamlia, GimonAs, Ok, NUS, Station, Mariehem, Kyrkan, I20, Rondellen, TreKorvar, Flygplatsen + + +\textbf{Path to goal:} +MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen + +\subsubsection{From: Nydala to Gamlia} + +\textbf{All expanded nodes:} +Nydala, MIT, Ok, Berghem, Gamlia + + +\textbf{Path to goal:} +Nydala, MIT, Berghem, Gamlia + +\subsubsection{From: Teg to Foa} + +\textbf{All expanded nodes:} +Teg, Rondellen, Tegsbron, Kyrkan, I20, TreKorvar, NUS, Station, Obs, On, Flygplatsen, Gamlia, Sofiehem, Foa + + +\textbf{Path to goal:} +Teg, Tegsbron, I20, Obs, Foa + \subsection{Test Girig sökning} \subsubsection{From: Tegsbron to Nydala} diff --git a/src/Graph.java b/src/Graph.java index 18bdfe1..7b66d51 100644 --- a/src/Graph.java +++ b/src/Graph.java @@ -50,13 +50,13 @@ public class Graph { * @param weight The weight (length) of the edge between the nodes. * @return true if an edge is inserted. */ - public Boolean insertEdge(String srcName, String destName, Double weight) { + public Boolean insertEdge(String srcName, String destName, Object edge) { //Om det inte redan finns en kant GraphNode srcNode = nodes.get(srcName); GraphNode destNode = nodes.get(destName); if (srcNode != null && destNode != null) { - srcNode.addNeighbour(destNode, weight); + srcNode.addNeighbour(destNode, edge); //destNode.addNeighbour(srcNode, weight); numberOfEdges++; return true; @@ -119,10 +119,10 @@ public class Graph { * @param destName The name address of the destination node. * @return The weight of the edge. */ - public Double getWeight(String srcName, String destName) { + public Object getEdge(String srcName, String destName) { GraphNode srcNode = nodes.get(srcName); GraphNode destNode = nodes.get(destName); - return srcNode.getWeight(destNode); + return srcNode.getEdge(destNode); } // Modifikatorer diff --git a/src/GraphNode.java b/src/GraphNode.java index c58d2ce..b77e6c2 100644 --- a/src/GraphNode.java +++ b/src/GraphNode.java @@ -43,8 +43,8 @@ public class GraphNode implements Comparable { * @param weight The weight of the potential edge between * this node and the new neighbour. */ - public void addNeighbour(GraphNode node, Double weight) { - neighbours.put(node, /*(Integer)*/ weight); + public void addNeighbour(GraphNode node, Object edge) { + neighbours.put(node, edge); } public void deleteNeighbour(GraphNode node) { @@ -58,8 +58,8 @@ public class GraphNode implements Comparable { * @param node The neighbour of this node. * @return The weight of the potential edge. */ - public Double getWeight(GraphNode node) { - return (Double) neighbours.get(node); + public Object getEdge(GraphNode node) { + return neighbours.get(node); } /** @@ -189,7 +189,7 @@ public class GraphNode implements Comparable { for (Enumeration e = getNeighbours(); e.hasMoreElements();) { GraphNode neighbour = (GraphNode) e.nextElement(); returnString += " " + neighbour.getName() - + ", traveltime: " + this.getWeight(neighbour) +"\n"; + + ", traveltime: " + this.getEdge(neighbour) +"\n"; } return returnString; } diff --git a/src/MySearcher.java b/src/MySearcher.java index 077afe7..4b2a417 100644 --- a/src/MySearcher.java +++ b/src/MySearcher.java @@ -50,11 +50,13 @@ public class MySearcher extends MapSearcher { GraphNode nodeAtEndOfRoad = map.getNode(roadElement.getAttributeValue("to")); Double distance = Math.hypot((cityNode.getX() - nodeAtEndOfRoad.getX()), (cityNode.getY() - nodeAtEndOfRoad.getY())); - Double time = distance / - (Double.parseDouble(roadElement.getAttributeValue("speed")) / 3.6); + + Road road = + new Road(Integer.parseInt(roadElement.getAttributeValue("speed")), + distance); map.insertEdge(cityNode.getName(), nodeAtEndOfRoad.getName(), - time); + road); } } } @@ -167,23 +169,31 @@ public class MySearcher extends MapSearcher { for (Enumeration e = n.getNeighbours(); e.hasMoreElements();) { neighbour = e.nextElement(); - neighbour.setDistance(n.getDistance() - + n.getWeight(neighbour) - + neighbour.setDistanceToGoal(map.getNode(to))); + if (fastest) { + neighbour.setDistance(n.getDistance() + + ((Road) n.getEdge(neighbour)).getTravelTime() + + (neighbour.setDistanceToGoal(map.getNode(to)) / (110/3.6) )); + } + else { + neighbour.setDistance(n.getDistance() + + ((Road) n.getEdge(neighbour)).getDistance() + + neighbour.setDistanceToGoal(map.getNode(to))); + } + // sort the nodes in N according to the value on their // evaluation function - if (!neighbour.isVisited() && !queue.contains(neighbour)) { + if (!queue.contains(neighbour) && !neighbour.isVisited()) { neighbour.setParent(n); queue.add(neighbour); + // and return to step 2. (end of loop) } - // and return to step 2. (end of loop) } } System.out.println(); // 2. ... exit and signal failure return "Goal not found!\n"; } - + /** * Utför bredden-förstsökning. * @@ -288,4 +298,4 @@ public class MySearcher extends MapSearcher { public String toString() { return map.toString(); } -} +} \ No newline at end of file diff --git a/test/GraphTest.java b/test/GraphTest.java index 6833af3..1454b97 100644 --- a/test/GraphTest.java +++ b/test/GraphTest.java @@ -30,18 +30,18 @@ public class GraphTest extends TestCase { g.insertNode("eslöv", 1, 2); g.insertNode("umeå", 1, 2); g.insertNode("stockholm", 2, 4); - g.insertEdge("lund", "malmö", 100.0); - g.insertEdge("lund", "eslöv", 200.0); - g.insertEdge("eslöv", "umeå", 300.0); - g.insertEdge("lund", "stockholm", 400.0); + g.insertEdge("lund", "malmö", new Double(100)); + g.insertEdge("lund", "eslöv", new Double(200)); + g.insertEdge("eslöv", "umeå", new Double(300)); + g.insertEdge("lund", "stockholm", new Double(400)); assertEquals("malmö", g.getNode("malmö").getName()); assertEquals("umeå", g.getNode("umeå").getName()); assertFalse("malmö" != g.getNode("malmö").getName()); - assertEquals(100.0, g.getWeight("lund", "malmö")); - assertEquals(200.0, g.getWeight("lund", "eslöv")); - assertEquals(300.0, g.getWeight("eslöv", "umeå")); - //assertEquals(300.0, g.getWeight("umeå", "eslöv")); - assertEquals(400.0, g.getWeight("lund", "stockholm")); + assertEquals(new Double(100.0), g.getEdge("lund", "malmö")); + assertEquals(new Double(200.0), g.getEdge("lund", "eslöv")); + assertEquals(new Double(300.0), g.getEdge("eslöv", "umeå")); + //assertEquals(300.0, g.getEdge("umeå", "eslöv")); + assertEquals(new Double(400.0), g.getEdge("lund", "stockholm")); } public void testSetGetDistance() { diff --git a/test/MySearcherLatexTest.java b/test/MySearcherLatexTest.java index 5522677..784ac26 100644 --- a/test/MySearcherLatexTest.java +++ b/test/MySearcherLatexTest.java @@ -30,13 +30,21 @@ public class MySearcherLatexTest extends TestCase { } public void testAStar() { - System.out.println("\\subsection{Test A*}"); + System.out.println("\\subsection{Test A* snabbast}"); for (int i = 0; i < from.length; i++) { MySearcher my = new MySearcher(); my.setMap(new File("maps/umea_map.xml")); System.out.println("\\subsubsection{From: " + from[i] + " to " + to[i] + "}"); System.out.println(my.aStar(from[i], to[i], true)); } + + System.out.println("\\subsection{Test A* kortast}"); + for (int i = 0; i < from.length; i++) { + MySearcher my = new MySearcher(); + my.setMap(new File("maps/umea_map.xml")); + System.out.println("\\subsubsection{From: " + from[i] + " to " + to[i] + "}"); + System.out.println(my.aStar(from[i], to[i], false)); + } } public void testGreedy() { diff --git a/test/MySearcherTest.java b/test/MySearcherTest.java deleted file mode 100644 index a0c75f8..0000000 --- a/test/MySearcherTest.java +++ /dev/null @@ -1,58 +0,0 @@ -import java.io.File; -import junit.framework.*; - -public class MySearcherTest extends TestCase -{ - String from1 = "Nydala"; - String to1 = "Kyrkan"; - String from2 = "Berghem"; - String to2 = "Nydala"; - - MySearcher my; - public MySearcherTest(String name) { - super (name); - my = new MySearcher(); - my.setMap(new File("maps/umea_map.xml")); - } - - public void testMap() { - System.out.println("----------Test Map-------------"); - System.out.println(my.toString()); - } - - public void testBreadthFirst() { - System.out.println("----------Test Breadthfirst-------------"); - System.out.println("From: " + from1 + " to " + to1); - System.out.println(my.breadthFirst(from1, to1)); - my.setMap(new File("maps/umea_map.xml")); - System.out.println("From: " + from2 + " to " + to2); - System.out.println(my.breadthFirst(from2, to2)); - } - - public void testDepthFirst() { - System.out.println("----------Test Depthfirst-------------"); - System.out.println("From: " + from1 + " to " + to1); - System.out.println(my.depthFirst(from1, to1)); - my.setMap(new File("maps/umea_map.xml")); - System.out.println("From: " + from2 + " to " + to2); - System.out.println(my.depthFirst(from2, to2)); - } - - public void testAStar() { - System.out.println("----------Test A*-------------"); - System.out.println("From: " + from1 + " to " + to1); - System.out.println(my.aStar(from1, to1, true)); - my.setMap(new File("maps/umea_map.xml")); - System.out.println("From: " + from2 + " to " + to2); - System.out.println(my.aStar(from2, to2, true)); - } - - public void testGreedy() { - System.out.println("----------Test GreedySearch-------------"); - System.out.println("From: " + from1 + " to " + to1); - System.out.println(my.greedySearch(from1, to1)); - my.setMap(new File("maps/umea_map.xml")); - System.out.println("From: " + from2 + " to " + to2); - System.out.println(my.greedySearch(from2, to2)); - } -} \ No newline at end of file -- 2.11.4.GIT