How to show every path possible to take, when you have small segments?

Question

I'm trying to make a program that shows all the different paths one could take when you have segments. The segments and the beginning and destiny are inputs, and it would work like this:

Segments:

• A->B
• A->C
• A->D
• B->D
• B->A
• C->E
• C->F
• C->D
• D->G
• D->F
• D->E
• F->E
• F->A
• F->B
• G->A
• G->B
• G->E

Now, what I want is to know all the available paths that one can take for example from A to E.

In the end, it should show something like:

• A->C->E
• A->C->F->E
• A->D->G->E
• A->D->E

It shouldn't show paths that would repeat locations (make loops) like:

A->C->F->A->D->E

I'm using arrayLists, and I have a class named segment that has as attributes the Start and End of a segment.

import java.util.ArrayList;

public class mane {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        listatrips a = new listatrips("A", "B");
        listatrips b = new listatrips("A", "C");
        listatrips c = new listatrips("A", "D");
        listatrips d = new listatrips("B", "D");
        listatrips e = new listatrips("B", "A");
        listatrips f = new listatrips("C", "E");
        listatrips h = new listatrips("C", "F");
        listatrips i = new listatrips("C", "D");
        listatrips j = new listatrips("D", "E");
        listatrips l = new listatrips("D", "F");
        listatrips m = new listatrips("D", "G");
        listatrips n = new listatrips("F", "E");
        listatrips o = new listatrips("F", "A");
        listatrips p = new listatrips("F", "B");
        listatrips q = new listatrips("G", "B");
        listatrips r = new listatrips("G", "A");
        listatrips s = new listatrips("G", "E");

        // A->E

        ArrayList<listatrips> ola = new ArrayList<listatrips>();
        ArrayList<String> ahah = new ArrayList<String>();
        ArrayList<String> bl = new ArrayList<String>();
        ArrayList<listatrips> ola2 = new ArrayList<listatrips>();
        ArrayList<String> eheh = new ArrayList<String>();
        ola2 = ola;

        ola.add(a);
        ola.add(b);
        ola.add(c);
        ola.add(d);
        ola.add(e);
        ola.add(f);
        ola.add(h);
        ola.add(i);
        ola.add(j);
        ola.add(l);
        ola.add(m);
        ola.add(n);
        ola.add(o);
        ola.add(p);
        ola.add(q);
        ola.add(r);
        ola.add(s);
        ola.size();

        int count = 0;

        eheh.add("A");
        boolean g = false;
        while (!g) {
            count = count + 1;
            for (int t = 0; t < ahah.size(); t++) {
                bl.add(ahah.get(t));
            }
            ahah.clear();
            for (int t1 = 0; t1 < eheh.size(); t1++) {
                ahah.add(eheh.get(t1));
            }
            eheh.clear();
            for (int z = 0; z < ola2.size(); z++) {

                for (int v = 0; v < ahah.size(); v++) {

                    if (ola2.get(z).inicio == ahah.get(v)) {

                        if (!bl.contains(ola2.get(z).fim) & !ahah.contains(ola2.get(z).fim)) {

                            eheh.add(ola2.get(z).fim);
                        }
                        if (ola.get(z).fim == "E") {
                            

                            
                        }
                    }

                }
            }

        }

    }

}

I want to know A-E:

I begin by checking every segment that starts at A and I add the ending of those segments to the list "eheh". When the code in the "while" begins for the second time the A that was in "ahah" goes into the "bl" (blacklist), so it won't get checked again. And the B, C, D go from the "eheh" to the "ahah" list, and are the ones getting checked next. It will search for segments that start at those 3 points and so on. Im not getting any output, I can get to the E but I don't know how to keep track of all the paths I took.

How do I solve this problem?

Answer 1

Assuming you don't want to include paths that have cycle, the following algorithm should solve your problem.

1. Construct an input graph When dealing with graph problems, it is a good practice to use graph adjacency-list representation. In this case, adjacency-set is sufficient.

2. Preprocess the graph to remove all self circle path(path that points to itself)

3. Perform depth first search on each node that has at least 1 neighbor Each search adds all possible paths starting from one particular node, giving all possible paths after doing this dfs on all node. The dfs itself uses backtracking. And the terminating condition is either you hit a node that does not have neighbors(such as E in your example) or you hit a cycle.

import java.util.*;

class Segment {
    String from, to;
    Segment(String from, String to) {
        this.from = from;
        this.to = to;
    }
}

public class PossiblePaths {
    public static List<List<String>> getAllPossiblePaths(Segment[] segments) {
        List<List<String>> paths = new ArrayList<>();

        //construct graph
        Map<String, Set<String>> graph = new HashMap<>();
        for(Segment segment : segments) {
            if(!graph.containsKey(segment.from)) {
                graph.put(segment.from, new HashSet<>());
            }
            Set<String> tos = graph.get(segment.from);
            tos.add(segment.to);
        }

        //preprocess to remove self circle
        for(String node : graph.keySet()) {
            Set<String> neighbors = graph.get(node);
            if(neighbors.contains(node)) {
                neighbors.remove(node);
            }
        }
        //dfs on each node in this graph to find all paths that do not have cycle in it
        for(String node : graph.keySet()) {
            if(graph.get(node).size() > 0) {
                List<String> path = new ArrayList<>(); path.add(node);
                Set<String> visited = new HashSet<>(); visited.add(node);
                dfs(graph, paths, path, node, visited);
            }
        }
        return paths;
    }
    private static void dfs(Map<String, Set<String>> graph, List<List<String>> paths, List<String> path, String node, Set<String> visited) {
        if(path.size() > 1) {
            paths.add(new ArrayList<>(path));
        }
        Set<String> neighbors = graph.get(node);
        if(neighbors != null) {
            for(String neighbor : neighbors) {
                if(!visited.contains(neighbor)) {
                    path.add(neighbor);
                    visited.add(neighbor);
                    dfs(graph, paths, path, neighbor, visited);
                    path.remove(path.size() - 1);
                    visited.remove(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Segment segment1 = new Segment("A", "B");
        Segment segment2 = new Segment("A", "C");
        Segment segment3 = new Segment("A", "D");
        Segment segment4 = new Segment("B", "D");
        Segment segment5 = new Segment("B", "A");
        Segment segment6 = new Segment("C", "E");
        Segment segment7 = new Segment("C", "F");
        Segment segment8 = new Segment("C", "D");
        Segment segment9 = new Segment("D", "G");
        Segment segment10 = new Segment("D", "F");
        Segment segment11 = new Segment("D", "E");
        Segment segment12 = new Segment("F", "E");
        Segment segment13 = new Segment("F", "A");
        Segment segment14 = new Segment("F", "B");
        Segment segment15 = new Segment("G", "A");
        Segment segment16 = new Segment("G", "B");
        Segment segment17 = new Segment("G", "E");

        Segment[] segments = {segment1, segment2, segment3, segment4, segment5, segment6, segment7, segment8, segment9,
                                segment10, segment11, segment12, segment13, segment14, segment15, segment16, segment17};

        List<List<String>> paths = getAllPossiblePaths(segments);
        for(int i = 0; i < paths.size(); i++) {
            System.out.println(paths.get(i));
        }
    }
}