How to increment a number for 3 different paths while using recursion?

Question

I have a program that prints all the reachable paths of a graph. It contains 2 classes GraphPath1 and Search . The program is given below:

Class GraphPath1:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;


public class GraphPath1 {
    List<String> src=new ArrayList<String>();  // source node
    List<String> dest=new ArrayList<String>(); // destination node 

private Map<String, LinkedHashSet<String>> map = new HashMap();

public void addEdge(String node1, String node2){
    LinkedHashSet<String> adjacent = map.get(node1);
    if(adjacent==null) {
        adjacent = new LinkedHashSet();
        map.put(node1, adjacent);
        src.add(node1);
    }
    adjacent.add(node2);
    dest.add(node2);
}



public LinkedList<String> adjacentNodes(String last) {
    LinkedHashSet<String> adjacent = map.get(last);
    if(adjacent==null) {
        return new LinkedList();
    }
    return new LinkedList<String>(adjacent);
}

}

Class Search:

import java.util.ArrayList;
import dfs.GraphPath1;
import java.util.LinkedList;
import java.util.List;

import dfs.LoanSystem;


public class Search {
private static final String START = "1";
private static final String END = "7";
public static void main(String[] args) {


    // this graph is directional
    GraphPath1 graph = new GraphPath1();

    graph.addEdge("1", "2");
    graph.addEdge("1", "3");
    graph.addEdge("2", "5");
    graph.addEdge("3", "4");
    graph.addEdge("4", "5");
    graph.addEdge("4", "6");
    graph.addEdge("5", "7");
    graph.addEdge("6", "7");
    //graph.addEdge("7", "1");

    /*
    List<String> s = graph.src;
    List<String> d = graph.dest;
    System.out.print(s);
    System.out.print(d);*/

    LinkedList<String> visited = new LinkedList();
    visited.add(START);
    new Search().DFS(graph, visited);

}


private void DFS(GraphPath1 graph, LinkedList<String> visited) {
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (String node : nodes) {
    if (visited.contains(node)) {
        continue;
    }
    if (node.equals(END)) {
        visited.add(node);
        printPath(visited);
        visited.removeLast();
        break;
    }
}



// in DFS, recursion needs to come after visiting adjacent nodes
for (String node : nodes) {
    if (visited.contains(node) || node.equals(END)) {
        continue;
    }

    visited.addLast(node);
    DFS(graph, visited);
    visited.removeLast();
}

}
/*
public List<Edge> getEdgeList (LinkedList<String> visited){
    List<Edge> edges = new ArrayList<Edge>();
    for(int i=0;i<=visited.size();i++)
        edges.add(new Edge(visited.get(i), visited.get(i+1)));

    return edges;
}
*/

private void printPath(LinkedList<String> visited) {

    ArrayList<String> sequence = new ArrayList<String>();
    {
    for (String node : visited) {
        sequence.add(node);

    }

}
    ArrayList<String> sequences = new ArrayList<String>();
    sequences.addAll(sequence);
    System.out.println(sequences);

}
}

The output of this program is :

1,2,5,7
1,3,4,5,7
1,3,4,6,7

Now I need to print 3 different messages for these 3 paths. For Example:

This is Path 1:
1,2,5,7
This is Path 2:
1,3,4,5,7
This is Path 3:
1,3,4,6,7 

But I don't know how to do this. Can anyone give me any idea how can I increment the number I used in the message (i.e. This is Path 1:) for the 3 different paths?

Answer 1

First, you have raw types. DON'T!!!!
E.g. change adjacent = new LinkedHashSet(); to adjacent = new LinkedHashSet<>();
If you use a good IDE, it should have already told you this.

---

Normally, you'd want the search to return the result, not print it, otherwise you cannot write any code that needs/uses the result.

This means that you need a result collector, and pass that in as a parameter to the recursive method. You then print result when search is complete.

Also:

• DFS can be made static.

• Handling of END and recursive calls can be unified.

• ArrayDeque would be a better type for visited.

• When doing recursive methods, it's often a good idea to isolate it behind an entry method, so caller doesn't have to know about extra parameters needed by the recursion (e.g. visited).

• START and END should be made parameters of DFS, so you can perform multiple searches on the same graph, if needed.

• Your printPath method seems a bit excessive.

public final class Search {
    public static void main(String[] args) {
        GraphPath1 graph = new GraphPath1();
        graph.addEdge("1", "2");
        graph.addEdge("1", "3");
        graph.addEdge("2", "5");
        graph.addEdge("3", "4");
        graph.addEdge("4", "5");
        graph.addEdge("4", "6");
        graph.addEdge("5", "7");
        graph.addEdge("6", "7");
        graph.addEdge("7", "1");

        searchAndPrint(graph, "1", "1");
        searchAndPrint(graph, "3", "2");
        searchAndPrint(graph, "1", "7");
    }

    private static void searchAndPrint(GraphPath1 graph, String start, String end) {
        List<List<String>> result = DFS(graph, start, end);
        for (int i = 0; i < result.size(); i++)
            System.out.printf("This is Path %d: %s%n", i + 1, result.get(i));
    }

    private static List<List<String>> DFS(GraphPath1 graph, String start, String end) {
        if (start.equals(end))
            return Collections.singletonList(Collections.singletonList(start));
        List<List<String>> result = new ArrayList<>();
        Deque<String> visited = new ArrayDeque<>();
        visited.add(start);
        DFS(graph, end, visited, result);
        return result;
    }

    private static void DFS(GraphPath1 graph, String end, Deque<String> visited, List<List<String>> result) {
        for (String node : graph.adjacentNodes(visited.getLast()))
            if (! visited.contains(node)) {
                visited.addLast(node);
                if (node.equals(end))
                    result.add(new ArrayList<>(visited)); // add copy to result
                else
                    DFS(graph, end, visited, result);
                visited.removeLast();
            }
    }
}

OUTPUT

This is Path 1: [1]

This is Path 1: [3, 4, 5, 7, 1, 2]
This is Path 2: [3, 4, 6, 7, 1, 2]

This is Path 1: [1, 2, 5, 7]
This is Path 2: [1, 3, 4, 5, 7]
This is Path 3: [1, 3, 4, 6, 7]

Answer 2

This is not hard to do. All you need is a counter variable to keep track of which path you are currently printing. In your case you can set a counter to 0 before you call the DFS() function. Then before each print you increment it and then print your line saying which path it is. After that you call printPath(). This could look something like that:

private int pathCount = 0;

// more of you code ...

private void DFS(GraphPath1 graph, LinkedList<String> visited) {
    LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
    // examine adjacent nodes
    for (String node : nodes) {
        if (visited.contains(node)) {
            continue;
        }
        if (node.equals(END)) {
            visited.add(node);
            pathNumber++;
            System.out.println("This is path " + pathNumber + ":");
            printPath(visited);
            visited.removeLast();
            break;
        }
    }

    // the rest of the algorithm ...
}

One more thing: If you make DFS a static function (private static void DFS(...)), you can call it directly from the main function without having to create an instance of the Search class and new Search().DFS(graph, visited); can be turned into DFS(graph, visited);. As we now use a instance variable to keep track of the path count, one instance of the Search class per search is what we want.

Edit: Reworked code snippet to use a instance variable instead of a local one in the function, which does not work as the function is recursive. Thanks to Andreas for pointing that out.