Follow list path with recursion. [Java]

Question

Hello i have a list with different connections. I want a function that allows me to give a start and end value. The function needs to figure out if there is a path. And if there's a path, it needs to be returned. I already created a working program. But the only thing is that i only get if there is a path yes or no. But i want to get the path.

    private static String[] connections = {
            "Strawberry -> Apple",
            "Apple -> Strawberry",
            "Strawberry -> Melon",
            "Melon -> Strawberry"
    };

    public static void main(String[] args)  {
        System.out.println(testConnection("Apple", "Melon", new ArrayList<>()));
    }

    public static boolean testConnection(String from, String to, List<String> checked) {
        if(from.equals(to)) return true;

        for(String con : connections) {
            String[] conSplit = con.split(" -> ");

            String first = conSplit[0];
            String second = conSplit[1];

            if(first.equals(from)) {
                if(second.equals(to)) return true;

                if(checked.contains(second)) continue;
                checked.add(first);

                if(testConnection(second, to, checked)) return true;
            }
        }
        return false;
    }

As you see Apple goes to Strawberry, Strawberry goes to Melon. And in my testConnection I said that i need to get the path from Apple to Melon.

Answer 1

Looking at the checked list is not sufficient to construct the path, since it will only be the same as the path if no backtracking is used. For example, with the connections:

private static String[] connections = {
        "Strawberry -> Apple",
        "Apple -> Pineapple",
        "Apple -> Strawberry",
        "Strawberry -> Cherry",
        "Cherry -> Apple",
        "Strawberry -> Melon",
        "Melon -> Strawberry",
};

You would end up checking Apple, Pineapple, Strawberry, Cherry then Melon, even though the path is Apple, Strawberry, Melon. A separate list is needed to find the path, e.g.:

public static boolean testConnection(String from, String to, List<String> checked, Stack<String> path) {
    checked.add(from);
    path.add(from);
    if (from.equals(to)) return true;

    for (String con : connections) {
        String[] conSplit = con.split(" -> ");

        String first = conSplit[0];
        String second = conSplit[1];

        if (first.equals(from)) {
            if (second.equals(to)) {
                path.add(second);
                return true;
            }

            if (checked.contains(second)) continue;


            if (testConnection(second, to, checked, path)) return true;
        }
    }
    path.pop();
    return false;
}

The key is that if all the connections are checked and no path is found, then the item is removed from the end of the path (path.pop()). This means that if a path is explored and then it is found that it doesn't lead to the destination, it won't affect the final path.

This algorithm is quite inefficient however, since every iteration it loops over every single connection. This can be fixed by building a graph data structure:

class Node {
    String name;
    List<Node> nextNodes;

    public Node(String name) {
        this.name = name;
        this.nextNodes = new ArrayList<>();
    }

    public static Map<String, Node> fromConnections(String[] connections) {
        Map<String, Node> nodes = new HashMap<>();
        for (String con :
                connections) {
            String[] conSplit = con.split(" -> ");

            String first = conSplit[0];
            String second = conSplit[1];

            Node node = nodes.computeIfAbsent(first, Node::new);
            node.nextNodes.add(nodes.computeIfAbsent(second, Node::new));
        }
        return nodes;
    }
}

This only loops over the entire list once. Now finding the connections that lead from a node only involves looping over those connections, not the entire list. It also separates the parsing stage from the search stage. Lastly, when you are going to do many checked.contains(second) checks, it is more efficient to use a HashSet rather than a list. Checking if a list contains an element involves looping over the entire list, whereas checking if a hashset contains something takes the same amount of time regardless of the size of the hashset.

Here is a running example of both versions of the algorithm:

import java.util.*;

public class Main {
    static class Node {
        String name;
        List<Node> nextNodes;

        public Node(String name) {
            this.name = name;
            this.nextNodes = new ArrayList<>();
        }

        public static Map<String, Node> fromConnections(String[] connections) {
            Map<String, Node> nodes = new HashMap<>();
            for (String con :
                    connections) {
                String[] conSplit = con.split(" -> ");

                String first = conSplit[0];
                String second = conSplit[1];

                Node node = nodes.computeIfAbsent(first, Node::new);
                node.nextNodes.add(nodes.computeIfAbsent(second, Node::new));
            }
            return nodes;
        }
    }

    private static String[] connections = {
            "Strawberry -> Apple",
            "Apple -> Pineapple",
            "Apple -> Strawberry",
            "Strawberry -> Cherry",
            "Cherry -> Apple",
            "Strawberry -> Melon",
            "Melon -> Strawberry",
    };

    public static void main(String[] args) {
        Stack<String> path = new Stack<>();
        ArrayList<String> checked = new ArrayList<>();
        System.out.println(testConnection("Apple", "Melon", checked, path));
        System.out.println(path);
        System.out.printf("checked: %s\n", checked);

        Map<String, Node> graph = Node.fromConnections(connections);
        path = new Stack<>();
        System.out.println(testConnection(graph.get("Apple"), graph.get("Melon"), new HashSet<>(), path));
        System.out.println(path);
    }


    public static boolean testConnection(String from, String to, List<String> checked, Stack<String> path) {
        checked.add(from);
        path.add(from);
        if (from.equals(to)) return true;

        for (String con : connections) {
            String[] conSplit = con.split(" -> ");

            String first = conSplit[0];
            String second = conSplit[1];

            if (first.equals(from)) {
                if (second.equals(to)) {
                    path.add(second);
                    return true;
                }

                if (checked.contains(second)) continue;


                if (testConnection(second, to, checked, path)) return true;
            }
        }
        path.pop();
        return false;
    }

    public static boolean testConnection(Node from, Node to, Set<Node> checked, Stack<String> path) {
        checked.add(from);
        path.add(from.name);
        if (from == to) return true;

        for (Node next : from.nextNodes) {

            if (checked.contains(next)) continue;


            if (testConnection(next, to, checked, path)) return true;
        }
        path.pop();
        return false;
    }
}

Answer 2

You can use many ways to do that. In these cases I don't like to use recursion, but it's up to you. For example you can just use the print statement in your loop to print first and second strings when the statement if(first.equals(from)) returns true.

Here is my version of the testConnection method using iteration:

public static boolean testConnection(String from, String to, List<String> checked) {
    boolean flag = false;

    for (String con : connections) {
        String[] conSplit = con.split(" -> ");

        String first = conSplit[0];
        String second = conSplit[1];

        if (first.equals(from)) {
            checked.add(first);
            checked.add(second);
            from = second;

            if (second.equals(to)) {
                flag = true;
                break;
            }
        }
    }
    if (flag) 
        System.out.println(checked);
    return flag;
}