From c6b861f2d5162e813df307847e7e5094042b3bd1 Mon Sep 17 00:00:00 2001 From: Anton Johansson Date: Tue, 14 Oct 2008 11:48:52 +0200 Subject: [PATCH] Map implementated, looks like it works! --- src/Graph.java | 21 ++++++++++++--------- src/GraphNode.java | 24 ++++++++++++++---------- src/MySearcher.java | 36 +++++++++++++++++++++++++++--------- test/GraphTest.java | 43 +++++++++++++++++++------------------------ test/MySearcherTest.java | 33 ++++++++++++++++++++------------- 5 files changed, 92 insertions(+), 65 deletions(-) rewrite test/MySearcherTest.java (67%) diff --git a/src/Graph.java b/src/Graph.java index 903241b..a90f301 100644 --- a/src/Graph.java +++ b/src/Graph.java @@ -1,8 +1,3 @@ -/* - * @(#)Graph.java - * Time-stamp: "2008-10-13 21:32:47 dit06vzy" - */ - import java.util.Enumeration; import java.util.Hashtable; @@ -54,7 +49,7 @@ 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, int weight) { + public Boolean insertEdge(String srcName, String destName, Double weight) { //Om det inte redan finns en kant GraphNode srcNode = nodes.get(srcName); GraphNode destNode = nodes.get(destName); @@ -104,7 +99,7 @@ public class Graph { * this Graph. */ public int size() { - return nodes.size(); + return nodes.size(); } /** @@ -123,7 +118,7 @@ public class Graph { * @param destName The name address of the destination node. * @return The weight of the edge. */ - public int getWeight(String srcName, String destName) { + public Double getWeight(String srcName, String destName) { GraphNode srcNode = nodes.get(srcName); GraphNode destNode = nodes.get(destName); return srcNode.getWeight(destNode); @@ -163,7 +158,7 @@ public class Graph { * @param destNode The destination node. * @param weight The new weight between the two nodes. */ - public void setWeight(GraphNode srcNode, GraphNode destNode, int weight) { + public void setWeight(GraphNode srcNode, GraphNode destNode, Double weight) { deleteEdge(srcNode, destNode); insertEdge(srcNode.getName(), destNode.getName(), weight); } @@ -182,4 +177,12 @@ public class Graph { public GraphNode getNode(String name) { return nodes.get(name); } + + public String toString() { + String returnString = ""; + for (Enumeration e = nodes.elements(); e.hasMoreElements();) { + returnString += e.nextElement(); + } + return returnString; + } } diff --git a/src/GraphNode.java b/src/GraphNode.java index 8a29025..0903b57 100644 --- a/src/GraphNode.java +++ b/src/GraphNode.java @@ -1,8 +1,3 @@ -/* - * @(#)GraphNode.java - * Time-stamp: "2008-10-13 16:55:16 anton" - */ - import java.util.Vector; import java.util.Hashtable; import java.util.Enumeration; @@ -20,7 +15,7 @@ public class GraphNode implements Comparable { private String name; private int x; private int y; - private double distanceToGoal; + private Double distanceToGoal; private boolean visited; private int distance; private GraphNode parent; @@ -48,7 +43,7 @@ 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, Integer weight) { + public void addNeighbour(GraphNode node, Double weight) { neighbours.put(node, /*(Integer)*/ weight); } @@ -63,8 +58,8 @@ public class GraphNode implements Comparable { * @param node The neighbour of this node. * @return The weight of the potential edge. */ - public int getWeight(GraphNode node) { - return (Integer) neighbours.get(node); + public Double getWeight(GraphNode node) { + return (Double) neighbours.get(node); } /** @@ -171,7 +166,7 @@ public class GraphNode implements Comparable { * * @return the distance to goal. */ - public double getDistanceToGoal() { + public Double getDistanceToGoal() { return this.distanceToGoal; } @@ -187,4 +182,13 @@ public class GraphNode implements Comparable { public int compareTo(Object node) { return name.compareTo(((GraphNode) node).getName()); } + + public String toString() { + String returnString = name + "\n"; + for (Enumeration e = getNeighbours(); e.hasMoreElements();) { + GraphNode neighbour = (GraphNode) e.nextElement(); + returnString += " " + neighbour.getName() + ", traveltime: " + this.getWeight(neighbour) +"\n"; + } + return returnString; + } } diff --git a/src/MySearcher.java b/src/MySearcher.java index bbb8ac3..50303f5 100644 --- a/src/MySearcher.java +++ b/src/MySearcher.java @@ -10,8 +10,7 @@ import org.jdom.*; * Beskrivning av klassen. */ public class MySearcher extends MapSearcher { - - Graph map; + private Graph map; /** * Skapar en ny MySearcher-instans. @@ -27,24 +26,39 @@ public class MySearcher extends MapSearcher { * * @TODO fixa this.map.insertEdge() för alla noder. */ - public void setMap(File map) { + public void setMap(File mapFile) { Document doc; List cityElements; try { - doc = loadXmlMap(map); - System.out.println(doc.getRootElement().toString()); + doc = loadXmlMap(mapFile); + //System.out.println(doc.getRootElement().toString()); cityElements = doc.getRootElement().getChildren(); + map = new Graph(cityElements.size(), 5); // Iterate through cityElements for (Element cityElement: cityElements) { // Prints names of cities - System.out.println(cityElement.getAttributeValue("id")); + String cityName = cityElement.getAttributeValue("id"); + int cityX = Integer.parseInt(cityElement.getAttributeValue("x")); + int cityY = Integer.parseInt(cityElement.getAttributeValue("y")); + GraphNode cityNode = map.insertNode(cityName, cityX, cityY); + //System.out.println(cityName + " at position (" + cityX + ", " + cityY + ")"); List roadElements = cityElement.getChildren(); // Iterate through roadElements - for (Iterator ii = roadElements.iterator(); ii.hasNext();) { - Element roadElement = ii.next(); + for (Element roadElement: roadElements) { + String roadTo = roadElement.getAttributeValue("to"); + Double roadSpeed = Double.parseDouble(roadElement.getAttributeValue("speed")); // Prints all roads connected to the current cityElement - System.out.println(" road to -> " + roadElement.getAttributeValue("to")); + //System.out.println(" road to -> " + roadElement.getAttributeValue("to")); + Double time = 1.0; + if (map.isInGraph(roadTo)) { // @FIX declare var in if condition + GraphNode roadToNode = map.getNode(roadTo); + Double distance = Math.hypot((cityNode.getX() - roadToNode.getX()), + (cityNode.getY() - roadToNode.getY())); + time = distance / (roadSpeed / 3.6); + } + map.insertEdge(cityName, roadTo, time); + // @FIX change roadSpeed to time } } } @@ -130,4 +144,8 @@ public class MySearcher extends MapSearcher { */ return ""; } + + public String toString() { + return map.toString(); + } } diff --git a/test/GraphTest.java b/test/GraphTest.java index 0685229..2132464 100644 --- a/test/GraphTest.java +++ b/test/GraphTest.java @@ -1,8 +1,3 @@ -/* - * @(#)GraphTest.java - * Time-stamp: "2008-10-13 16:51:00 anton" - */ - import junit.framework.*; /** @@ -10,11 +5,11 @@ import junit.framework.*; * * @author "Anton Johansson" */ -public class GraphTest extends TestCase { +public class GraphTest extends TestCase { public GraphTest(String name) { super(name); } - + public void testEmpty() { Graph g = new Graph(11, 24); assertTrue(g.isEmpty()); @@ -26,8 +21,8 @@ public class GraphTest extends TestCase { g.deleteNode(g.getNode("malmö")); assertTrue(g.isEmpty()); } - - + + public void testEdges() { Graph g = new Graph(11, 24); g.insertNode("lund", 1, 2); @@ -35,19 +30,19 @@ 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); - g.insertEdge("lund", "eslöv", 200); - g.insertEdge("eslöv", "umeå", 300); - g.insertEdge("lund", "stockholm", 400); + 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); assertEquals("malmö", g.getNode("malmö").getName()); assertEquals("umeå", g.getNode("umeå").getName()); assertFalse("malmö" != g.getNode("malmö").getName()); - assertEquals(100, g.getWeight("lund", "malmö")); - assertEquals(200, g.getWeight("lund", "eslöv")); - assertEquals(300, g.getWeight("eslöv", "umeå")); - assertEquals(300, g.getWeight("umeå", "eslöv")); - assertEquals(400, g.getWeight("stockholm", "lund")); - assertEquals(400, g.getWeight("lund", "stockholm")); + 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("stockholm", "lund")); + assertEquals(400.0, g.getWeight("lund", "stockholm")); } public void testSetGetDistance() { @@ -60,20 +55,20 @@ public class GraphTest extends TestCase { // g.insertNode("stockholm", 2, 4); assertEquals(0, lund.getX()); assertEquals(0, lund.getY()); - + assertEquals(0, malmo.getX()); assertEquals(2, malmo.getY()); - + lund.setDistanceToGoal(malmo); assertEquals(2.0, lund.getDistanceToGoal()); - + lund.setDistanceToGoal(eslov); assertEquals(5.0, lund.getDistanceToGoal()); - + lund.setDistanceToGoal(umea); // (sqrt (+ (expt 4 2) (expt 7 2))) assertEquals(8.06225774829855, lund.getDistanceToGoal(), 0.0000000001); - + umea.setDistanceToGoal(kiruna); // (sqrt (+ (expt (- 4 9) 2) (expt (- 7 15) 2))) assertEquals(9.433981132056603, umea.getDistanceToGoal(), 0.0000000001); diff --git a/test/MySearcherTest.java b/test/MySearcherTest.java dissimilarity index 67% index b053f11..918463f 100644 --- a/test/MySearcherTest.java +++ b/test/MySearcherTest.java @@ -1,13 +1,20 @@ -import java.io.File; -import junit.framework.*; -public class MySearcherTest extends TestCase -{ - public MySearcherTest (String name) { - super (name); - } - - public void testEmpty () { - MySearcher my = new MySearcher(); - my.setMap(new File("maps/umea_map.xml")); - } -} \ No newline at end of file +import java.io.File; +import junit.framework.*; + +public class MySearcherTest extends TestCase +{ + public MySearcherTest (String name) { + super (name); + } + + public void testEmpty () { + MySearcher my = new MySearcher(); + my.setMap(new File("maps/umea_map.xml")); + } + + public void testMap() { + MySearcher my = new MySearcher(); + my.setMap(new File("maps/umea_map.xml")); + System.out.println(my.toString()); + } +} \ No newline at end of file -- 2.11.4.GIT