How to find all paths in a graph that start with some initial partial path?

Question

There is the following part of the code:

SimpleDirectedGraph<String, DefaultEdge> multigraph = new SimpleDirectedGraph<>(DefaultEdge.class);
multigraph.addVertex("a");
multigraph.addVertex("b");
multigraph.addVertex("c");
multigraph.addVertex("1");
multigraph.addEdge("a", "b");
multigraph.addEdge("b", "c");
multigraph.addEdge("c", "1");

Dependencies:

gradle: implementation group: 'org.jgrapht', name: 'jgrapht-core', version: '1.5.1'

I also have only a part of the path ("abc"). And I need to get on this part all possible paths that include this part, that is, in this case: "abc1".

How can i do this? AsSubgraph, AllDirectedPaths, GraphWalk, BFSShortestPath - this all does not give the desired result, it just outputs the part that I know.

Thanks in advance.

Answer 1

From what I understand, you are looking to find all paths in a graph that start with some initial partial path p1=[v_1,v_2,...,v_n]. To do so, we must find every path p2 that starts at vertex v_n (the last vertex of p1) and ends in some other vertex not yet visited by p1. There are two alternative ways to accomplish this:

1. Run a shortest path algorithm from vertex v_n in a graph that does not contain any of the vertices in p1 except v_n.
2. Run a BFS from vertex v_n in a graph that does not contain any of the vertices in p1 except v_n.

Both solutions in code:

public static void shortestPathSolution(){
    Graph<String, DefaultEdge> graph=getGraph();

    List<String> partialPathP1=List.of("a","b","c"); //some partial path
    String source=partialPathP1.get(partialPathP1.size()-1); //the last vertex of P1
    List<List<String>> completePaths = new ArrayList<>();

    //To prevent P2 from revisiting vertices in P1, create a graph which hides all but the last vertex in P1.
    Set<String> vertexSubset=new HashSet<>(graph.vertexSet());
    vertexSubset.removeAll(partialPathP1);
    vertexSubset.add(source);
    Graph<String,DefaultEdge> inducedSubgraph = new AsSubgraph<>(graph, vertexSubset);

    //Find the shortest paths from the end of P1 to all reachable vertices in the graph
    ShortestPathAlgorithm.SingleSourcePaths<String,DefaultEdge> shortestPaths=new DijkstraShortestPath<>(inducedSubgraph).getPaths(source);
    //Iterate over the reachable vertices and construct all extensions
    for(String vertex : inducedSubgraph.vertexSet()){
        if(vertex.equals(source)) continue;
        GraphPath<String, DefaultEdge> gp = shortestPaths.getPath(vertex);
        if(gp == null) continue; //No path exists from the end of P1 to the given vertex

        //Obtain path P2
        List<String> partialPathP2 = gp.getVertexList();
        //Construct path P by concatenating P1 and P2
        List<String> pathP = new ArrayList<>(partialPathP1);
        pathP.addAll(partialPathP2.subList(1, partialPathP2.size()));
        completePaths.add(pathP);
    }

    System.out.println(completePaths);
}

public static void bfsSolution(){
    Graph<String, DefaultEdge> graph = getGraph();

    List<String> partialPathP1 = List.of("a", "b", "c"); //some partial path
    String source = partialPathP1.get(partialPathP1.size() - 1); //the last vertex of P1
    List<List<String>> completePaths = new ArrayList<>();

    //To prevent P2 from revisiting vertices in P1, create a graph which hides all but the last vertex in P1.
    Set<String> vertexSubset = new HashSet<>(graph.vertexSet());
    vertexSubset.removeAll(partialPathP1);
    vertexSubset.add(source);
    Graph<String, DefaultEdge> inducedSubgraph = new AsSubgraph<>(graph, vertexSubset);

    //Run a BFS from the source vertex. Each time a new vertex is encountered, construct a new path.
    BreadthFirstIterator<String, DefaultEdge> bfs = new BreadthFirstIterator<>(inducedSubgraph, source);
    while(bfs.hasNext()){
        String vertex=bfs.next();
        //Create path P2 that ends in the vertex by backtracking from the new vertex we encountered
        Stack<String> partialPathP2 = new Stack<>();
        while(vertex != null) {
            partialPathP2.push(vertex);
            vertex=bfs.getParent(vertex);
        }
        partialPathP2.pop(); //Remove the source vertex
        List<String> pathP = new ArrayList<>(partialPathP1.size()+partialPathP2.size());
        pathP.addAll(partialPathP1);
        while(!partialPathP2.isEmpty())
            pathP.add(partialPathP2.pop());
        completePaths.add(pathP);
    }

    System.out.println(completePaths);
}

public static Graph<String,DefaultEdge> getGraph(){
    Graph<String, DefaultEdge> graph = new SimpleDirectedGraph<>(DefaultEdge.class);
    Graphs.addAllVertices(graph, List.of("a","b","c","1","2","3"));
    graph.addEdge("a", "b");
    graph.addEdge("b", "c");
    graph.addEdge("c", "1");
    graph.addEdge("c", "2");
    graph.addEdge("1", "3");
    graph.addEdge("2", "3");
    return graph;
}

Result:

[[a, b, c], [a, b, c, 1], [a, b, c, 2], [a, b, c, 1, 3]]

Note: For performance reasons, it is always best to choose the graph type that best suits your application. If you don't need self-loops and multiple edges, instead of choosing a DirectedPseudograph, it would be better to use a SimpleDirectedGraph.