revisiting nodes during DFS and controlling infinite cycles

Question

I am implementing DFS on a weighted directed graph in the following way:

    public class DFSonWeightedDirectedGraph {

    private static final String START = "A";
    private static final String END = "C";
    private int pathLength = 0;
    private int stops = 0;

    public static void main(String[] args) {
        //this is a directed weighted graph
        WeightedDirectedGraph graph = new WeightedDirectedGraph();
        graph.addEdge("A", "B", 5);
        graph.addEdge("A", "D", 5);
        graph.addEdge("A", "E", 7);
        graph.addEdge("B", "C", 4);
        graph.addEdge("C", "D", 8);
        graph.addEdge("C", "E", 2);
        graph.addEdge("D", "C", 8);
        graph.addEdge("D", "E", 6);
        graph.addEdge("E", "B", 3);

        LinkedList<String> visited = new LinkedList<String>();
        visited.add(START);
        new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
    }

    private void depthFirst(WeightedDirectedGraph graph, LinkedList<String> visited) {
        Collection<Map.Entry<String, Integer>> nodes = graph.adjacentNodes(visited.getLast());      
        // examine adjacent nodes
        for (Map.Entry<String, Integer> node : nodes) {
            if (visited.contains(node.getKey())) {
                continue;
            }
            if (node.getKey().equals(END)) {
                visited.addLast(node.getKey());  
                pathLength += node.getValue();
                stops += 1;
                printPath(visited);
                visited.removeLast();
                pathLength -= node.getValue();
                stops -= 1;
                break;
            }
        }
        // recursion
        for (Map.Entry<String, Integer> node : nodes) {
            if (visited.contains(node.getKey()) || node.getKey().equals(END)) {
                continue;
            }
            visited.addLast(node.getKey());
            pathLength += node.getValue();
            stops += 1;
            depthFirst(graph, visited);
            visited.removeLast();
            pathLength -= node.getValue();
            stops -= 1;
        }
    }

    private void printPath(LinkedList<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println("[path length: "+pathLength +
                " stops made: "+ stops+"]");
    }
}

I need to modify the above to allow cycles during the search for all paths between a source node and a destination node. To avoid infinite cycles, conditions can be set to terminate the search based on the number of "stops" made, or a maximum allowed distance traveled from the source.

This way I can find, for example, the number of trips starting at A and ending at D with exactly 5 stops: One solution can be ABCDCD. Or, I can find, say, the number of different routes from D to D with a distance of less than 40: a few solutions would be DECD, DEBCD, DCDCD.

My problem is that I am not sure how to create the logic of keeping the main algorithm searching, while escaping an infinite search cycle that is guaranteed not to reach the destination node.

Let's say I want to travel from A to D. A possible dead-end cycle can be ABCEBCEBCEB....(to infinity). My conditions based on number of stops, or total distance traveled, can terminate this loop, but will also end the entire search, which could otherwise find the right path of say ABCDCDCDCD, which will correctly terminate when either pre-set condition is met.

Thanks for any ideas.

Answer 1

I think you need to set your cutoff stops/distance dynamically. For example, for a problem "A to D in exactly 5 stops", setting a cutoff value of 5 stops will terminate all cycles when they reach 6 stops. The same holds for the problem "D to D with a distance of less than 40", if you set a cutoff distance of 40.

Some cycles can be cut off earlier, using an "accessibility matrix", i.e. a matrix such that a(i, j) = 1 if there is a path from i to j or a(i, j) = 0 otherwise. You can construct such a matrix by first finding the strongly connected components of your graph (using an algorithm like this).
Then you can reject a search cycle, if the target node is not accessible from the current node, i.e. a(current, target) = 0.