Implement a breadth first graph traversal upto a given depth

Question

I am trying to implement a breadth first graph traversal that returns the number of paths from one node to another, but only through a given number of nodes.

For example given a list of Nodes A, B, C, D, E, if I want to know the number of different paths I can get from A to D, but only if the path has no more than 2 stops. A-B-D, A-E-D would be considered acceptable, but A-B-E-D would be too many stops, so the answer would be 2 paths.

I am trying to implement this algorithm, but I am not sure how I can keep track of the depth, so that my search only goes n levels deep.

Here is my codeI have written so far. The problem lies in searchNumPaths() method.

public class PathSearch{
private int maxSearches;
private int pathCount;
private int numPaths;
private String node;
private ArrayList<ArrayList<String>> path;
ArrayList<Node> visited;

public PathSearch(int maxSearches, int pathCount) {
    node = "";
    this.maxSearches = maxSearches;
    this.pathCount = pathCount;
    path = new ArrayList<ArrayList<String>>();
    visited = new ArrayList<Node>();
}

public int searchNumPaths(HashMap<String, Node> graph, Node startLocation, String endLocation, Queue<String> queue) {
    //queue.add(startLocation.getLocation());
    while(!queue.isEmpty()) {
        node = queue.remove();
        System.out.println("\n" + node +"\n");
        for (Edge realPath: graph.get(node).getNeighbors()) {
                node = realPath.getEndLocation();
                System.out.println(node);
                queue.add(node);
                if (node.equals(endLocation)) {
                    numPaths++;
                }   
        }
        pathCount++;
        if (pathCount>6){
            break;
        }
        for (int i = 0; i<queue.size(); i++) {
            searchNumPaths(graph, graph.get(queue.peek()), endLocation, queue);
            queue.remove();
        }

    }
    return numPaths;
}

public static void main(String[] args) throws IOException {
    Train train = new Train();
    Graph graph = new Graph(train.readFile("input.txt"));
    LinkedList<String> queue = new LinkedList<String>();
    queue.add("A");
    PathSearch great = new PathSearch(10, 0);
    HashMap<String, Node> map = graph.returnMap();
    Node node = graph.returnMap().get("A");
    String nodeTwo = graph.returnMap().get("C").getLocation();
    //System.out.println(queue.remove());
    System.out.println("Number of paths: " + great.searchNumPaths(map, node, nodeTwo, queue));

}

}

Answer 1

You can create a QueueNode class that contains the current string you put in your queue together with a number that indicates the depth of the node. You could then continue the search until you encounter a node with a depth that is too high. Something like this (T is a String in your case):

public class QueueNode<T> {

    T value;
    int depth;

    public QueueNode(T value, int depth) {
        this.value = value;
        this.depth = depth;
    }

    // And so on.. Getters etc.

}

When you create new QueueNode objects, you can just set the depth to one greater than the depth of the current node.

By doing this, you could add something like this to your searchNumPaths function (after the call to queue.remove()):

if (node.getDepth() > maxDepth) {
    return numPaths;
}

Note that this only works if your queue is guaranteed to return nodes with increasing depth. This is always true for a breadth-first search, but if you're going to change it to an A-star search or something later, this assumption breaks.