# Yet another graph search

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;
output = new OutputBlock(strategy, diagIterations, graph.getGridSize());
position = graph.findStart().getCoords();
// path = new StringBuilder("S");

// We can add the starting node to the open set now.

}

/**
* 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":
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

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

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") {
} else {
}

// 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());
}
StringBuilder sb2 = new StringBuilder();
sb2.append("CLOSED");
for (Node diagClosedNode : closed) {
sb2.append(" " + diagClosedNode.getPath());
}
}
}
// 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) {
}
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() {
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').

• 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. – Toadfish Apr 22 '15 at 8:10