如何在图中找到以某些初始部分路径开头的所有路径？

Question

有以下部分代码：

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");

依赖关系：

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

我也只有一部分路径（“abc”）。我需要在这部分获得包含这部分的所有可能路径，即在这种情况下：“abc1”。

我该怎么做？ AsSubgraph、AllDirectedPaths、GraphWalk、BFSShortestPath - 这些都没有给出预期的结果，它只是输出我知道的部分。

提前致谢。

Answer 1

据我了解，您要查找图中以某个初始部分路径 p1=[v_1,v_2,...,v_n] 开头的所有路径。为此，我们必须找到从顶点 v_n（p1 的最后一个顶点）开始并在 p1 尚未访问的某个其他顶点结束的每条路径 p2。有两种替代方法可以实现此目的：

运行从图中的顶点 v_n 开始的最短路径算法，该算法不包含 p1 中除 v_n.
运行来自图中顶点 v_n 的 BFS，不包含 p1 中除 v_n.

代码中的两种解决方案：

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;
}

结果：

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

注意：出于性能原因，最好始终选择最适合您的应用程序的图形类型。如果不需要自环和多边，与其选择DirectedPseudograph，不如使用SimpleDirectedGraph.

如何在图中找到以某些初始部分路径开头的所有路径？

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

java

jgrapht