From 99c65e53a08e05dd65200a9cca49a7346d89e054 Mon Sep 17 00:00:00 2001
From: Anton Johansson <anton.johansson@gmail.com>
Date: Tue, 14 Oct 2008 13:17:15 +0200
Subject: [PATCH] started breadth first algorithm

---
 src/MySearcher.java | 77 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 54 insertions(+), 23 deletions(-)

diff --git a/src/MySearcher.java b/src/MySearcher.java
index 50303f5..19ecb46 100644
--- a/src/MySearcher.java
+++ b/src/MySearcher.java
@@ -2,6 +2,8 @@ import java.io.File;
 import java.io.IOException;
 import java.util.Iterator;
 import java.util.List;
+import java.util.LinkedList;
+import java.util.PriorityQueue;
 import java.util.Hashtable;
 import java.util.Enumeration;
 import org.jdom.*;
@@ -80,10 +82,19 @@ public class MySearcher extends MapSearcher {
     * @param to Den plats sökningen avslutas på.
     */
    public String greedySearch (String from, String to) {
-      /*
-       * implementation av greedySearch.
-       */
-      return "";
+       // 1. Set N to be a sorted list of initial nodes;
+       PriorityQueue<GraphNode> bigN =
+           new PriorityQueue<GraphNode>(this.map.getNode());
+       GraphNode n;
+       while (!bigN.isEmpty()) { // 2. If N is empty, 
+           // 3. set n to be the first node in N, and remove n from N;
+           // 4. If n is a goal node, exit and signal success;
+           // 5. Otherwise add the children of n to N, sort the nodes in N
+           // according to the value on their evaluation function and return to
+           // step 2.
+       }
+       // 2. ... exit and signal failure
+       return null;
    }
 
    /**
@@ -97,22 +108,22 @@ public class MySearcher extends MapSearcher {
    public String aStar (String from, String to, boolean fastest) {
        // skapa en tabell över hur långt det är från alla platser på
        // kartan till målet för sökningen
-       Hashtable<String, Double> targetDistTable =
-           new Hashtable<String, Double>(map.size());
-       // spara ned målnoden
-       GraphNode targetLocation = map.getNode(to);
-       GraphNode tempNode;
-       Enumeration e;
-       // för alla noder
-       for (e = map.getNodes(),
-                tempNode = (GraphNode) e.nextElement();
-            e.hasMoreElements(); // medan e har element
-            tempNode = (GraphNode) e.nextElement()) {
-           // spara avståndet till målnoden för varje nod
-           targetDistTable.put(tempNode.getName(),
-                            Math.hypot(targetLocation.getX()-tempNode.getX(),
-                                       targetLocation.getY()-tempNode.getY()));
-       }
+       // Hashtable<String, Double> targetDistTable =
+      //            new Hashtable<String, Double>(map.size());
+      //        // spara ned målnoden
+      //        GraphNode targetLocation = map.getNode(to);
+      //        GraphNode tempNode;
+      //        Enumeration e;
+      //        // för alla noder
+      //        for (e = map.getNodes(),
+      //                 tempNode = (GraphNode) e.nextElement();
+      //             e.hasMoreElements(); // medan e har element
+      //             tempNode = (GraphNode) e.nextElement()) {
+      //            // spara avståndet till målnoden för varje nod
+      //            targetDistTable.put(tempNode.getName(),
+      //                             Math.hypot(targetLocation.getX()-tempNode.getX(),
+      //                                        targetLocation.getY()-tempNode.getY()));
+      //}
        /*
         * implementation av aStar.
         */
@@ -126,9 +137,29 @@ public class MySearcher extends MapSearcher {
     * @param to Den plats sökningen avslutas på.
     */
    public String breadthFirst (String from, String to) {
-      /*
-       * implementation av breadthFirst.
-       */
+      // Comments fetched from
+      // http://en.wikipedia.org/wiki/Breadth-first_search
+      // at Tue Oct 14 12:57:18 2008
+      String pathToGoal = "";
+      LinkedList<GraphNode> queue = new LinkedList();
+      
+      
+      // 1. Put the root node on the queue.
+      queue.add(map.getNode(from));
+      while (!queue.isEmpty()) {
+         // 2. Pull a node from the beginning of the queue and examine it.
+         GraphNode tmpNode = queue.removeFirst();
+         //   * If the searched element is found in this node, quit the search and return a result.
+         if (tmpNode.getName().equals(to)) {
+            // Found goal
+            return
+         }
+         
+         //   * Otherwise push all the (so-far-unexamined) successors (the direct child nodes) of this node into the end of the queue, if there are any.
+         
+         // 3. If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
+         
+      }
       return "";
    }
 
-- 
2.11.4.GIT