计算从一组节点到根节点形成的子树

Question

我有一个有向无环图，我希望传入一组节点，从根节点获得子树。

例如，在下图中，如果传入D和E，则由a、B、D和E组成的子树(图(应返回

A
/  
B     C
/ 
D   E
/
G  

Answer 1

您需要找出子图中包含的顶点。可以通过从选定的底部顶点返回到根节点来执行此操作。

//Create graph
Graph<String, DefaultEdge> dag = new SimpleDirectedGraph<>(DefaultEdge.class);
Graphs.addAllVertices(dag, Arrays.asList("A","B","C","D","E","G"));
dag.addEdge("A","B");
dag.addEdge("A","C");
dag.addEdge("B","D");
dag.addEdge("B","E");
dag.addEdge("D","G");
NeighborCache<String, DefaultEdge> neighborCache = new NeighborCache<>(dag);
//Define inputs
Set<String> blockers = Set.of("D", "E");
//Figure out which vertices are in the subgraph
Queue<String> queue=new LinkedList<>();
queue.addAll(blockers);
Set<String> subgraphVertices = new HashSet<>();
while(!queue.isEmpty()){
String vertex = queue.poll();
subgraphVertices.add(vertex);
queue.addAll(neighborCache.predecessorsOf(vertex));
}
//Create subgraph
Graph<String,DefaultEdge> subDag = new AsSubgraph<>(dag, subgraphVertices);
System.out.println(subDag);

如果需要，可以在上面的代码中包括一些性能改进，因为有些顶点会多次添加到队列中。例如，当你从顶点D往回走到根节点A时，你会遇到顶点B。同样，当你从不点E往回走时，你又会遇到B。没有必要再次访问B.

Answer 2

https://github.com/jgrapht/jgrapht/issues/1121我在这里问了同样的问题，并找到了解决方案。