I am trying to get this code running as fast as possible when traversing through my stack of my DFS currently the input files are like so:
0 2 2 1 1 4 4 5 5 6 10 8 8 9 9 6 7 6 3 4 0 1 3 9 0 4
Where my Maze
class will tie the numbers together and create a graph for me. After the graph is created my DFS
class runs through traversing giving one or all solutions to the .txt file submitted.
My DFS
class looks like so:
import java.util.Scanner;
import java.util.Stack;
public class DFS {
//starting node, the route to the next node, has node been visited
private int startNode;
private int[] route2;
private boolean[] visited;
// 2 main arguments - Maze File & user input
public DFS(Maze maze, int inputInt) {
int startNode = 0;
int goal = 1;
route2 = new int[maze.node];
visited = new boolean[maze.node];
if(inputInt == 1){
startDFSone(maze, startNode, goal);
}
else if (inputInt == 2){
startDFSall(maze, startNode, goal);
}
else {
System.out.println("input invalid. No Solution Returned");
}
}
//Put path to goal in the stack
public Stack<Integer> route2(int toGoalNode) {
if (!visited[toGoalNode]) {
return null;
}
Stack<Integer> pathStack = new Stack<Integer>();
for (int route2GoalNode = toGoalNode; route2GoalNode != startNode; route2GoalNode = route2[route2GoalNode]) {
pathStack.push(route2GoalNode);
}
pathStack.push(startNode);
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;
}
}
//performs DFS and unsets visited to give the result of all paths
private void startDFSall(Maze maze, int node, int goal) {
visited[node] = true;
if(node == goal) {
printPath(goal);
} else {
for (int con : maze.getadjList(node)) {
if (!visited[con]) {
route2[con] = node;
startDFSall(maze, con, goal);
}
}
}
visited[node] = false;
}
//performs DFS and maintains visited marker giving only one path
private void startDFSone(Maze maze, int node, int goal) {
visited[node] = true;
for (int con : maze.getadjList(node)) {
if (!visited[con]) {
route2[con] = node;
startDFSone(maze, con, goal);
}
}
}
//Traverse the connections to the goal and print the path taken
public void printPath( int toGoal) {
int goalNode = 1;
if (visited[toGoal]) {
System.out.println("Completed Path: ");
for (int t : route2(toGoal)) {
if (t == toGoal) {
System.out.print(t);
} else {
System.out.print(t + " -> ");
}
}
System.out.println();
}
}
/**
*
* @param args
*/
public static void main(String[] args) {
Scanner scanFile = new Scanner(System.in);
int goalNode = 1;
System.out.print("Enter maze file: ");
String file = scanFile.nextLine();
Maze maze = new Maze(file);
Scanner scanInt = new Scanner(System.in);
System.out.print("Enter desired feedback (1 = one soultion, 2 = all): ");
int inputInt = scanInt.nextInt();
maze.print();
System.out.println();
DFS dfs = new DFS(maze, inputInt);
dfs.printPath(goalNode);
}
}
I am asking for some example or pointers to get my code (specifically the traversal of the stack) more concise so that when I implement my testing for completion time of the code I can minimize it as much as humanly possible.
I'll link my Maze
class below if it might help.
import java.io.*;
import java.util.*;
public class Maze {
final static Set<Integer> Nodes = new HashSet<Integer>();
List<Integer>[] adjList;
int node; //declaring value for my nodes.
int con; // declaring a connection
/**
* 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.
*/
Maze(int node) {
this.node = node;
this.con = 0;
adjList = (List<Integer>[]) new List[node];
for (int index = 0; index < node; index++) {
adjList[index] = new LinkedList<Integer>();
}
}
/**
* The main constructor that takes a String for reading maze file.
*
* @param mazeFile
*/
public Maze(String mazeFile) {
this(getNodeSize(mazeFile));
Scanner scan;
try {
//Creates a scanner for reading the file and loops through linking the nodes to their connections.
scan = new Scanner(new File(mazeFile));
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
addCon(node1, node2);
}
} catch (FileNotFoundException ex) {
System.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();
Nodes.add(node1);
Nodes.add(node2);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return Nodes.size();
}
/**
* This method adds an con by adding two different nodes in array of list
* called adjacency list.
*
* @param node1 - first node.
* @param node2 - next node.
*/
private void addCon(int node1, int node2) {
con++; //Increase con by one whenever this addcon method is called.
adjList[node1].add(node2);
adjList[node2].add(node1);
}
/**
* Print the nodes and its cons by looping through the adjacency list.
*/
public void print() {
for (int n = 0; n < node; n++) {
System.out.print(n + " connected to ");
for (int w : adjList[n]) {
System.out.print(w + " ");
}
System.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> getadjList(int nodes) {
return adjList[nodes];
}
/**
* Unit testing To test if it reads the file.
*
* @param args
*/
public static void main(String[] args) {
System.out.print("Enter File: ");
Scanner scanFile = new Scanner(System.in);
String file = scanFile.nextLine();
Maze M = new Maze(file);
M.print();
}
}