I have this maze which represented as undirected graph. Here's how it looks like:
11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
6 11
7 11
In this graph, with the use of depth-first search and it shows me a solution from start node to goal node. My input as a start node is 0 and my goal node is 1. The solution I have got as path to goal is 0-3-11-7-5-4-1 but if you analyze again there is also another solution which is 0-3-11-6-7-5-4-1. My purpose here is not to show the best solution but to show how many solution their are and analyze the best solution later.
The difficulty I am having is that I am not able to print more than one solution. It only prints 0-3-11-7-5-4-1 nothing else and sometimes this 0-3-11-6-7-5-4-1 as I am expecting that there is two of them to be printed. Here is the code that I have done so far:
public class DepthFirstSearch {
private final boolean[] visited;
private final int sourceNode;
private final int[] pathTo;
/**
*
* @param mazeGraph
* @param sourceNode
* @param goal
*/
public DepthFirstSearch(MazeGraph mazeGraph, int sourceNode, int goal) {
this.sourceNode = sourceNode;
visited = new boolean[mazeGraph.node];
pathTo = new int[mazeGraph.node];
performRecursiveDFS(mazeGraph, sourceNode, goal);
}
//Perform recursive depth-first search
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true;
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
}
//Put path to goal in the stack
public Stack<Integer> pathTo(int toGoalNode) {
if (!visited[toGoalNode]) {
return null;
}
Stack<Integer> pathStack = new Stack<Integer>();
for (int pathToGoalNode = toGoalNode; pathToGoalNode != sourceNode; pathToGoalNode = pathTo[pathToGoalNode]) {
pathStack.push(pathToGoalNode);
}
pathStack.push(sourceNode);
reverseStack(pathStack);
return pathStack;
}
//Reverse the stack
public void reverseStack(Stack<Integer> stackToBeReverse) {
if (stackToBeReverse.isEmpty()) {
return;
}
int bottom = popBottomStack(stackToBeReverse);
reverseStack(stackToBeReverse);
stackToBeReverse.push(bottom);
}
//Pop the bottom of the stack
private int popBottomStack(Stack<Integer> stackToBeReverse) {
int popTopStack = stackToBeReverse.pop();
if (stackToBeReverse.isEmpty()) {
return popTopStack;
} else {
int bottomStack = popBottomStack(stackToBeReverse);
stackToBeReverse.push(popTopStack);
return bottomStack;
}
}
//Print the path to goal
public void printPath( int toGoal) {
if (visited[toGoal]) {
out.println("Path to Goal: ");
for (int x : pathTo(toGoal)) {
if (x == toGoal) {
out.print(x);
} else {
out.print(x + " - ");
}
}
out.println();
}
}
/**
*
* @param args
*/
public static void main(String[] args) {
Scanner scanFile = new Scanner(in);
out.print("Enter maze file: ");
String file = scanFile.nextLine();
out.print("Enter start node: ");
int startNode = scanFile.nextInt();
out.print("Enter goal node: ");
int goalNode = scanFile.nextInt();
MazeGraph mazeGraph = new MazeGraph(file);
mazeGraph.print();
out.println("Starting at 0\nGoal at 1");
DepthFirstSearch depthFirstSearch = new DepthFirstSearch(mazeGraph, startNode, goalNode);
depthFirstSearch.printPath( goalNode);
}
}
MazeGraph source code:
public class MazeGraph {
final int node; //Declaring constant value of a node.
int arc;
List<Integer>[] adjacencyList;
final static Set<Integer> setOfNodes = new HashSet<Integer>();
/**
* This constructors takes an integer parameter for reading node indexes in
* a list of adjacent nodes.
*
* @param node - integer parameter for passing the nodes value from the file
* and create a list of adjacent nodes.
*/
MazeGraph(int node) {
this.node = node;
this.arc = 0;
adjacencyList = (List<Integer>[]) new List[node];
for (int index = 0; index < node; index++) {
adjacencyList[index] = new LinkedList<Integer>();
}
}
/**
* The main constructor that takes a String for reading maze file.
*
* @param mazeFile
*/
public MazeGraph(String mazeFile) {
this(getNodeSize(mazeFile));
Scanner scan;
try {
//Scan maze file.
scan = new Scanner(new File(mazeFile));
/*loop when it has next integer then read two nodes from the file and add arc for it.*/
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
addArc(node1, node2);
}
} catch (FileNotFoundException ex) {
out.println("File not found.");
}
}
/**
* This method returns a size of the set of nodes by taking a String
* parameter which the name of the maze file.
*
* @param mazeFile - String parameter for reading maze file for scanning the
* size of the nodes.
* @return - returns an integer value for the size of the set of nodes.
*/
public static int getNodeSize(String mazeFile) {
Scanner scanNodeSize;
try {
scanNodeSize = new Scanner(new File(mazeFile));
while (scanNodeSize.hasNextInt()) {
int node1 = scanNodeSize.nextInt();
int node2 = scanNodeSize.nextInt();
setOfNodes.add(node1);
setOfNodes.add(node2);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return setOfNodes.size();
}
/**
* This method adds an arc by adding two different nodes in array of list
* called adjacency list.
*
* @param node1 - first node.
* @param node2 - next node.
*/
private void addArc(int node1, int node2) {
arc++; //Increase arc by one whenever this addArc method is called.
adjacencyList[node1].add(node2);
adjacencyList[node2].add(node1);
}
/**
* Print the nodes and its arcs by looping through the adjacency list.
*/
public void print() {
out.println(node + " Nodes, " + arc + " Arcs \n");
for (int n = 0; n < node; n++) {
out.print(n + " connected to ");
for (int w : adjacencyList[n]) {
out.print(w + " ");
}
out.println();
}
}
/**
* This method returns a list of nodes to allow objects to be the target for
* "for-each" statement.
*
* @param nodes - an Integer parameter for getting the number of nodes in a
* list.
* @return - returns a list of nodes.
*/
public Iterable<Integer> getAdjacencyList(int nodes) {
return adjacencyList[nodes];
}
/**
* Unit testing To test if it reads the file.
*
* @param args
*/
public static void main(String[] args) {
out.print("Enter maze file: ");
Scanner scanFile = new Scanner(in);
String file = scanFile.nextLine();
MazeGraph G = new MazeGraph(file);
G.print();
}
}
Please explain to me why this is happening in detail and give me suggestions/advise on how can I improve this. Check my quality of code as well if it's ok otherwise it's ok not to check. Thanks in advance anyway.
You are actually lucky that your algorithm finds a path, since it has a major flaw: you do not unset visited if you leave the recursive call. So you have to add this to your performRecursiveDFS:
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true; //set visited
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
visited[node] = false; //unset visited
}
This is necessary because you "backtrack" you are thus looking for another path, and for that path, you haven't visited the node yet.
Furthermore in the recursive call, you can inspect whether you reached the goal, and if that is the case, print the path:
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true; //set visited
if(node == goal) { //found the goal? Good, print it and backtrack.
printPath(goal);
} else {
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
}
visited[node] = false; //unset visited
}
You can of course do something else than printing the path, for instance counting, storing the path in a list, etc.
EDIT: tested it with the maze file you've provided, I get:
$ java DepthFirstSearch
Enter maze file: maze
Enter start node: 0
Enter goal node: 1
12 Nodes, 12 Arcs
0 connected to 3
1 connected to 4
2 connected to 3
3 connected to 11 2 0
4 connected to 1 5
5 connected to 4 7
6 connected to 7 11
7 connected to 5 6 8 11
8 connected to 7 9
9 connected to 8 10
10 connected to 9
11 connected to 3 6 7
Starting at 0
Goal at 1
Path to Goal:
0 - 3 - 11 - 6 - 7 - 5 - 4 - 1
Path to Goal:
0 - 3 - 11 - 7 - 5 - 4 - 1