From 096a4dbd5fd14f74a90bbbc18a6e935c475777f9 Mon Sep 17 00:00:00 2001
From: Anton Johansson <anton.johansson@gmail.com>
Date: Sun, 19 Oct 2008 19:06:13 +0200
Subject: [PATCH] Fixed greedy and depth to not add the same node twice in
 queue/stack, MySearcherLatexTest changed to print sections in the right place

---
 src/MySearcher.java           | 28 +++++++++++++---------------
 test/MySearcherLatexTest.java |  8 ++++----
 2 files changed, 17 insertions(+), 19 deletions(-)

diff --git a/src/MySearcher.java b/src/MySearcher.java
index d5fab80..8d4e5a9 100644
--- a/src/MySearcher.java
+++ b/src/MySearcher.java
@@ -196,21 +196,20 @@ public class MySearcher extends MapSearcher {
        * http://en.wikipedia.org/wiki/Breadth-first_search
        * at Tue Oct 14 12:57:18 2008
        */
-      LinkedList<GraphNode> q = new LinkedList<GraphNode>();
+      LinkedList<GraphNode> queue = new LinkedList<GraphNode>();
       String expandedNodes = "";
       String pathToGoal = "";
       // 1. Put the root node on the queue.
-      q.add(map.getNode(from));
-      while (!q.isEmpty()) {
+      queue.add(map.getNode(from));
+      while (!queue.isEmpty()) {
          // 2. Pull a node from the beginning of the queue and examine it.
-         GraphNode n = q.removeFirst();
+         GraphNode n = queue.removeFirst();
          n.visit();
+         expandedNodes += n.getName() + (n == map.getNode(to) ? "" : ", ");
 
          //   * If the searched element is found in this node, quit
          //   * the search and return a result.
          if (n.getName().equals(to)) {
-            expandedNodes += to;
-
             pathToGoal = n.getName(); // Goal
             n = n.getParent();
 
@@ -228,13 +227,12 @@ public class MySearcher extends MapSearcher {
          else {
             for (Enumeration e = n.getNeighbours(); e.hasMoreElements();) {
                GraphNode neighbour = (GraphNode) e.nextElement();
-               if (!neighbour.isVisited()) {
+               if (!neighbour.isVisited() && !queue.contains(neighbour)) {
                   neighbour.setParent(n);
-                  q.add(neighbour);
+                  queue.add(neighbour);
                }
             }
          }
-         expandedNodes += n.getName() + ", ";
       }
       return "Goal not found!\n";
    }
@@ -246,14 +244,14 @@ public class MySearcher extends MapSearcher {
     * @param to Den plats sökningen avslutas på.
     */
    public String depthFirst (String from, String to) {
-      LinkedList<GraphNode> s = new LinkedList<GraphNode>();
+      LinkedList<GraphNode> stack = new LinkedList<GraphNode>();
       String expandedNodes = "";
       String pathToGoal = "";
       // 1. Push the root node onto the stack.
-      s.add(map.getNode(from));
-      while (!s.isEmpty()) {
+      stack.add(map.getNode(from));
+      while (!stack.isEmpty()) {
          // 2. Pop a node from the stack
-         GraphNode n = s.removeLast();
+         GraphNode n = stack.removeLast();
          //   * Mark this node as visited
          n.visit();
          //   * If the searched element is found in this node, quit
@@ -276,9 +274,9 @@ public class MySearcher extends MapSearcher {
             for (Enumeration e = n.getNeighbours();
                  e.hasMoreElements();) {
                GraphNode neighbour = (GraphNode) e.nextElement();
-               if (!neighbour.isVisited()) {
+               if (!neighbour.isVisited() && !stack.contains(neighbour)) {
                   neighbour.setParent(n);
-                  s.add(neighbour);
+                  stack.add(neighbour);
                }
             }
          }
diff --git a/test/MySearcherLatexTest.java b/test/MySearcherLatexTest.java
index 4c3cdc6..5522677 100644
--- a/test/MySearcherLatexTest.java
+++ b/test/MySearcherLatexTest.java
@@ -10,40 +10,40 @@ public class MySearcherLatexTest extends TestCase {
    }
 
    public void testBreadthFirst() {
+      System.out.println("\\subsection{Test Bredden-först}");
       for (int i = 0; i < from.length; i++) {
          MySearcher my = new MySearcher();
          my.setMap(new File("maps/umea_map.xml"));
-         System.out.println("\\subsection{Test Bredden-först}");
          System.out.println("\\subsubsection{From: " + from[i] + " to " + to[i] + "}");
          System.out.println(my.breadthFirst(from[i], to[i]));
       }
    }
 
    public void testDepthFirst() {
+      System.out.println("\\subsection{Test Djupet-först}");
       for (int i = 0; i < from.length; i++) {
          MySearcher my = new MySearcher();
          my.setMap(new File("maps/umea_map.xml"));
-         System.out.println("\\subsection{Test Djupet-först}");
          System.out.println("\\subsubsection{From: " + from[i] + " to " + to[i] + "}");
          System.out.println(my.depthFirst(from[i], to[i]));
       }
    }
 
    public void testAStar() {
+      System.out.println("\\subsection{Test A*}");
       for (int i = 0; i < from.length; i++) {
          MySearcher my = new MySearcher();
          my.setMap(new File("maps/umea_map.xml"));
-         System.out.println("\\subsection{Test A*}");
          System.out.println("\\subsubsection{From: " + from[i] + " to " + to[i] + "}");
          System.out.println(my.aStar(from[i], to[i], true));
       }
    }
 
    public void testGreedy() {
+      System.out.println("\\subsection{Test Girig sökning}");
       for (int i = 0; i < from.length; i++) {
          MySearcher my = new MySearcher();
          my.setMap(new File("maps/umea_map.xml"));
-         System.out.println("\\subsection{Test Girig sökning}");
          System.out.println("\\subsubsection{From: " + from[i] + " to " + to[i] + "}");
          System.out.println(my.greedySearch(from[i], to[i]));
       }
-- 
2.11.4.GIT