3
\$\begingroup\$

I noticed there were already countless implementations of graphsearch procedures on here, but there were a couple of features of my approach that I haven't seen in the others, plus I would greatly appreciate some experienced eyes on my code (my university is pretty miserly with constructive criticism).

I wrote this as an assignment (already submitted for marking) so I had a few constraints. The most interesting (?) was that we were told to create a single method which could do DFS, BFS, A/A* and Uniform Cost Search - in other words, they wanted us to see that the difference lay in the ordering of the open set, not in the program logic.

/**
   * Constructor for objects of class Search
   * 
   * @param strat       strategy to use
   * @param iterations  diagnostic iterations
   * @param newGraph    the graph we're going to search.
   */
  public Search(String strat, int iterations, Graph newGraph) {
    // initialise instance variables
    strategy = strat;
    diagIterations = iterations; // how many 'turns' to give full diag for.
    currentIterations = 0;
    graph = newGraph;
    open = new LinkedList<>();
    closed = new LinkedHashSet<>();
    output = new OutputBlock(strategy, diagIterations, graph.getGridSize());
    diagQueue = new LinkedList<>();
    position = graph.findStart().getCoords();
    // path = new StringBuilder("S");

    // We can add the starting node to the open set now.
    open.add(graph.findStart());

  }

  /**
   * When this method is called, we start the search for a path. DiagBlocks are generated and kept
   * in an OutputBlock, which is returned by the method at the end.
   * 
   * @return an outputblock containing the output of the search
   * 
   */
  public OutputBlock run() {
    long startTime = System.currentTimeMillis();
    boolean diag = false; // We'll flip this back if we need to.
    switch (strategy) {
      case "D":
        System.out.println("Initiating Depth-First search...");
        break;
      case "B":
        System.out.println("Initiating Breadth-First search...");
        break;
      case "U":
        System.out.println("Initiating Uniform Cost search...");
        break;
      case "A":
        System.out.println("Initiating A/A* search...");
        break;
      default:
        System.out.println("Search strategy not available, something broke.");
        break;
    }
    boolean finished = false;
    // We want to run until we're done
    while (!finished) {

      // Time to expand the node we've chosen (or started at)
      currentIterations++; // Increment iterations
      // Checking if we need diagnostics
      if (currentIterations <= diagIterations) {
        diag = true;
      } else {
        diag = false;
      }

      Node currentNode = graph.getNode(position);
      // Adding this node to the closed set
      closed.add(currentNode);

      if (Driver.verbose()) {
        System.out.println("# Looking at node (" + currentNode.getCoords() + ") #");
        System.out
            .println("Type: " + currentNode.getNodeType() + " | g: " + currentNode.getCost()
                + " | h: " + currentNode.getHeuristic() + " | f: " + currentNode.getFn()
                + " | Parent: (" + currentNode.getCameFrom() + ")\n" + "Path: "
                + currentNode.getPath());
      }


      // Grabbing neighbours
      LinkedHashMap<String, Edge> neighbours = currentNode.getEdges();

      if (currentNode.getNodeType() == 'G') {
        // If we're on the goal node, we finish and start packing up our
        // output
        // If we were using BFS or DFS we won't get here, because those
        // strategies finish when they
        // see the goal, not when they select it for expansion.
        System.out.println("Found the goal node at position (" + currentNode.getCoords() + ")");

        finished = true;
        path = currentNode.getPath() + "-G " + currentNode.getRealCost();
        if (Driver.verbose()) {
          System.out.println("Final path: " + path);
        }
        output.setPath(path);
        // put the path into the output block
      } else {


        // Now adding children of this node to the open set
        for (Edge neighbour : neighbours.values()) {
          // Checking if this neighbour is already in the closed set.
          if (!(closed.contains(neighbour.getDest()) || open.contains(neighbour.getDest()))) {
            // It's not in the closed set.

            if (Driver.verbose()) {
              System.out.println("--> Looking at neighbour (" + neighbour.getDest().getCoords()
                  + ")");
            }
            neighbour.getDest().cameFrom(position);
            neighbour.getDest().setPath(currentNode.getPath() + "-" + neighbour.getDirection());
            neighbour.getDest().setRealCost(currentNode.getRealCost() + neighbour.getEdgeCost());

            switch (strategy) {
              case "B":
              case "D":
                neighbour.getDest().setCost(currentNode.getCost() + 1);
                break;
              case "U":
              case "A":
                neighbour.getDest().setCost(currentNode.getCost() + neighbour.getEdgeCost());
                break;
              default:
                System.err.println("Something has gone terribly wrong with the strategy again.");
                break;
            }
            // We've given it a cost based on the strategy we're, now we add it to the open set.
            if (strategy != "D") {
              open.addFirst(neighbour.getDest());
            } else {
              open.addLast(neighbour.getDest());
            }

            // Maybe we found the goal, we can do this in BFS and DFS
            if (((strategy == "B") || (strategy == "D"))
                && (neighbour.getDest().getNodeType() == 'G')) {
              // If we see the goal while doing BFS or DFS, we end
              // here
              System.out.println("Found the goal node while looking at neighbour ("
                  + currentNode.getCoords() + ")");

              finished = true;
              path = neighbour.getDest().getPath() + "-G " + currentNode.getRealCost();
              if (Driver.verbose()) {
                System.out.println("Final path: " + path);
              }
              output.setPath(path);
              // Putting the path into the output block
            }
          }

        }
        // Done adding neighbours to the open set
        // If we need diagnostics we can prepare a block now
        if (diag) {
          DiagBlock thisDiag = new DiagBlock();
          thisDiag.addLine(currentNode.getPath() + " " + currentNode.getCost() + " "
              + currentNode.getHeuristic() + " " + currentNode.getFn());
          StringBuilder sb1 = new StringBuilder();
          sb1.append("OPEN");
          for (Node diagOpenNode : open) {
            sb1.append(" " + diagOpenNode.getPath());
          }
          thisDiag.addLine(sb1.toString());
          StringBuilder sb2 = new StringBuilder();
          sb2.append("CLOSED");
          for (Node diagClosedNode : closed) {
            sb2.append(" " + diagClosedNode.getPath());
          }
          thisDiag.addLine(sb2.toString());
          diagQueue.add(thisDiag);
        }
      }
      // Done with this node
      if (!finished) {
        if (!selectNextNode()) {
          System.out.println("Nothing left in the open set.");
          output.setPath("NO-PATH");
          finished = true;

        }

      }

    }
    // And we're done, returning the output block now.
    long endTime = System.currentTimeMillis();
    long processTime = (endTime - startTime);
    System.out.println("Took " + processTime + "ms");
    for (DiagBlock db : diagQueue) {
      output.addDiagBlock(db);
    }
    return output;
  }


  /**
   * Gets the coordinates of the node to be expanded
   * 
   */
  public boolean selectNextNode() {
    // Which node we pick from the queue depends on the strategy we're using
    Node nextNode;
    if (open.peekLast() == null) {
      // System.out.println("Didn't get a node from the open set - it's probably empty.");
      return false;
    }
    switch (strategy) {
      case "B":
        // This case can fall through to the next, because they do the same thing.
      case "D":
        nextNode = open.removeFirst();
        break;
      case "A":
        sortA();
        nextNode = open.removeFirst();
        break;
      case "U":
        sortUcs();
        nextNode = open.removeFirst();
        break;

      default:
        System.out.println("Search strategy not available, something broke.");
        nextNode = null; // this is bad and doesn't really solve any problems, but it won't create
                         // any new ones...
        return false;
    }


    position = nextNode.getCoords();
    // We actually got a node, so we're returning true.
    return true;



    /*
     * When this is called, the pathfinding loop will be about to repeat with a new position.
     */
  }

  /*
   * Sorts the open set by g(n) - for a Uniform Cost Search
   */
  public void sortUcs() {
    Collections.sort(open, Node.GComparator);
  }

  /*
   * Sorts the open set by f(n), used for A/A*
   */
  public void sortA() {
    // put your code here
    Collections.sort(open, Node.FComparator);
  }

At this stage in my learning, I'm not knowledgeable enough to really benefit from any advice relating to how the code compiles, but any advice anyone could offer as to how I can improve this and/or develop as a programmer would be amazing.

A couple of things that stand out to me:

I know LinkedLists are universally despised, but I used one because I couldn't find another collection that intuitively allowed me to treat it as a FIFO queue, a FILO queue, AND could be easily sorted with a Comparator. What collection would a more competent java programmer have chosen? Since the closed set didn't need to be sorted, I was free to just use a LinkedHashSet... but in retrospect I'm not sure I even ended up iterating over the closed set at any point, so I should probably have just used a HashSet.

Speaking of Comparators, I didn't bother to include them, as they're just one line operations comparing the path cost ('g') and path cost + heuristic ('f').

\$\endgroup\$
  • \$\begingroup\$ Actually I remember now, I DID have to iterate over that closed set - the assignment basically required that the program write some diagnostics to file, including the closed set, which also had to be kept in its original order (the order the nodes were visited). That was in another class with the main method/io/validation, and isn't very interesting. \$\endgroup\$ – Toadfish Apr 22 '15 at 8:10
2
\$\begingroup\$

In my option it would be nicer to have an enum for the strategy rather than a String. This would only allow valid input and any developer using your class would know what strategys are supported without digging around in your code since the supported values are not part of the javadocs.

Also it is somewhat useless to use a string for the strategy while it is only one character long. A simple byte/char would minimize memory usage.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.