1
\$\begingroup\$

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();
    }

}
\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

Let's start by getting your Maze data structure right.

First, you have a compiler warning about generics.

$ javac Maze.java 
Note: Maze.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
$ javac -Xlint:unchecked Maze.java 
Maze.java:21: warning: [unchecked] unchecked cast
    adjList = (List<Integer>[]) new List[node];
                                ^
  required: List<Integer>[]
  found:    List[]
1 warning

You could @SuppressWarnings("unchecked"), but rather, I would recommend that you not use arrays at all, because:

  • Using generics with arrays is a pain.
  • You need to parse the file in two passes, with the purpose of the first pass being just to determine the size of the array.
  • The array size is correct only if you assume that the nodes are numbered consecutively from 0.

Most of the variables in the Maze class are inappropriate:

  • What is int node for? The comment (//declaring value for my nodes) is cryptic. It seems to be referenced only from the Maze(int node) constructor, and its JavaDoc makes no sense (@param node - integer parameter for passing the nodes value…). Both the Maze(int node) constructor and the node member have default access, which is also a bad idea.
  • What is int con for? It appears to be a write-only variable; you never use it anywhere. It has default access, which is a bad idea: you almost certainly want either public or private.
  • If there are multiple Maze objects, each maze should be independent, right? Therefore, Nodes should not be static. It should also be named with a lowercase.
  • You shouldn't even need the Set<Integer> Nodes, if you use the right data structure for the adjacency list. I recommend

    private final Map<Integer, Set<Integer>> adjList = new HashMap<>();
    

    That is, it's a map where each key is a node number, and the value is an unordered set of node numbers.


The public Maze(String mazeFile) constructor should accept a File instead of a String, to make it clear that expects a file path rather than the file contents. You shouldn't catch and discard the FileNotFoundException, because that would just give you an unconstucted object and some junk printed on System.out. Rather, if you don't know what to do with the exception, just let it propagate.

Rather than a print() method, I recommend overriding toString(). It's both more standard and more performant, since you would be making fewer print() calls.

getadjList() should return an immutable view, so that it cannot be tampered with.

The main() function is not really a unit test: there is pass/fail test. It's just a demonstration, so be honest about it in the JavaDoc.


import java.io.*;
import java.util.*;

public class Maze {

    private final Map<Integer, Set<Integer>> adjList = new HashMap<>();

    /**
     * The main constructor that takes a String for reading maze file.
     *
     * @param mazeFile
     */
    public Maze(File mazeFile) throws FileNotFoundException {
        try (Scanner scan = new Scanner(mazeFile)) {
            while (scan.hasNextInt()) {
                int node1 = scan.nextInt();
                int node2 = scan.nextInt();
                this.connect(node1, node2);
                this.connect(node2, node1);
            }
        }
    }

    /**
     * Makes a unidirectional connection from node1 to node2.
     */
    private void connect(int node1, int node2) {
        if (!this.adjList.containsKey(node1)) {
            this.adjList.put(node1, new HashSet<Integer>());
        }
        this.adjList.get(node1).add(node2);
    }

    /**
     * Returns a human-readable description of the adjacency lists.
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Map.Entry<Integer, Set<Integer>> adj : this.adjList.entrySet()) {
            int from = adj.getKey();
            Set<Integer> to = adj.getValue();
            s.append(from).append(" connected to ").append(to).append('\n');
        }
        return s.toString();
    }

    /**
     * Returns the set of nodes connected to a particular node.
     *
     * @param node - the node whose neighbors should be fetched
     */
    public Iterable<Integer> getadjList(int node) {
        return Collections.unmodifiableSet(adjList.get(node));
    }

    /**
     * Demonstration of file reading.
     */
    public static void main(String[] args) throws FileNotFoundException {
        System.err.print("Enter File: ");
        Scanner scanFile = new Scanner(System.in);
        String file = scanFile.nextLine();
        Maze m = new Maze(new File(file));
        System.out.println(m);
    }

}
\$\endgroup\$
2
  • \$\begingroup\$ This is fantastic, I had initially though about using that data structure but shy'd away from it but you have laid it out much easier than I first though negating a lot of my unnecessary rambling. After implementing your updates to my maze I am being thrown two errors within my DFS class stopping it from running on line 118, 122. I have altered the print function but it doesn't seem to be allowing me to pass the maze through to be traversed. \$\endgroup\$
    – Ben411916
    Jan 11, 2016 at 19:17
  • \$\begingroup\$ can you advise any material for using adjList with Map's as i have little to no experience using them \$\endgroup\$
    – Ben411916
    Jan 12, 2016 at 15:37
1
\$\begingroup\$

Nice job keeping your methods small and readable. It's always a good idea to split big monolithic methods into smaller ones so that your code is easier to test and reason about.

You've done a decent job of documenting what each of these does. One thing to note is that you should really only be using single line // comments within methods. When annotating a method with a description of its functionality, arguments, and return type, you're going to want to use a docblock (it seems like you've done this in Maze, but not in DFS).

Some general notes as I read:

  • Arguments like inputInt aren't really helpful (you can tell it's an int from the type). Instead, strive for names that describe what they contain (ie. desiredSolutions)
  • Your inputInt should probably be bool (since it can only have 2 values). I'd name it allSolutions and pass true if the user inputs 2
  • There seem to be a few indentation problems (although those may be a result of copy and pasting here). Having properly indented code makes debugging easier on the eyes and improves readability for others
  • In general you should not have System.out.println() deep in your code. What if you wanted to use this code for a non-CLI application? Instead of printing errors, throw exceptions. Then in your CLI code (maybe the main method if it's not too bulky), add a catch and print the error string there
  • I don't understand the point of startNode and goal in the DFS constructor. Primitives are passed by value in java, so you could simply call startDFS with the values. However, since these functions are recursive, it seems that you're trying to use the DFS constructor as the starting point for calling into the recursion. I would instead use overloading so that you could just call startDFSall(maze) or startDFSone(maze) from the constructor like so:

DFS.java:

public DFS(Maze maze, bool allSolutions) {
    if(allSolutions) {
        startDFSall(maze);
    } else {
        startDFSone(maze);
    }
}

private void startDFSall(maze) {
    startDFSall(maze, 0, 1);
}

private void startDFSall(maze, int startNode, int goal) {
    // your code
}
  • In general, it is a bad idea to do heavy lifting in a constructor (calling the startDFS methods, for example). The general pattern you should probably use is create a DFS with a maze, and then on that object call performSearch() to actually start the DFS
  • The logic for DFSone and DFSall is so similar that you could probably refactor them into a single method with a boolean flag for one/all. Since DFS all may return multiple paths, the best solution here is to have an internal DFSall that returns a List of solutions and takes a boolean flag allSolutions/oneSolution. Then the public DFSall (which I would rename to findAll()) call this private DFSall with allSolutions = true. DFSone (which I would rename to findOne()) calls the inner DFSall with allSolutions = false and returns the first and only item in the returned List
  • Watch your naming conventions. DFSone and DFSall isn't really great camel case. I'd prefer something like: findAll()/findOne() since the class name already identifies that it performs a DFS
  • The popBottomStack/reverseStack methods unnecessarily use recursion. Be careful with this. In this instance, the recursive call isn't the last statement in the function so it can't be tail-call optimized. This means for long enough stacks, you run the risk of a stack overflow. You're almost certainly better off using a while loop here.
  • Also on the topic of reverseStack, it seems very inefficient to use this Θ(n) operation. Consider using a Deque (double ended stack) if you need insert/iteration from the head and/or tail
  • I see a few instances of new Scanner(new File(mazeFile)). You should strive to not repeat yourself (especially when these two are close enough in your codebase that they can be shared)
  • Again on the topic of constructors, you're probably better off creating a separate class to handle reading in the maze from the file. This better adheres to the Single Responsibility Principle. This reader class should take a BufferedInputStream and upon calling a read() method on it should return an instance of Maze (this also allows you to handle exception logic for File I/O outside of the Maze class)
  • Given that DFS is responsible for the search, it probably makes sense to refactor out things related to the actual Path produced into its own class. This way, you can have the DFS class return a Path (and not have to have path printing logic inside DFS).
  • (Although this is more a matter of taste), I would have this program accept arguments from the command line instead of reading interactively from stdin. This way, you can use this program from other scripts easily. See https://stackoverflow.com/questions/367706/how-to-parse-command-line-arguments-in-java

With these suggestions your main method should probably look like this:

BufferedInputStream mazeFile = // get mazeFile from args
boolean allSolutions = // get allSolutions/oneSolution binary switch from args

MazeReader reader = new MazeReader(mazeFile);

try {
    Maze maze = reader.read();
} except(IOException e) {
    System.error.println("User-friendly error message");
}

DepthFirstSearcher dfs = new DepthFirstSearcher(maze);

if(allSolutions) {
    List<Path> solutions = dfs.findAll();
    for(Path p : solutions) {
        System.out.println(p.toString());
    }
} else {
    Path solution = dfs.findOne();
    System.out.println(solution.toString());
}

When designing an application like this, I find it helpful to lay out the main() method first so you can get a feel for the APIs you need to design and what patterns you should employ. This also allows you to consider things like error cases (and the appropriate exceptions you'll need), which classes have which responsibilities, etc.

\$\endgroup\$
1
  • \$\begingroup\$ Sorry I have got a bit confused when going over and trying to create and implement the functions like findAll() is it possible to get see your test code to play around with. \$\endgroup\$
    – Ben411916
    Jan 11, 2016 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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