Calculate the subtree formed from a group of nodes to the root node

Question

I have a directed acyclic graph, and I expect to pass in a set of nodes to get a subtree from the root node to them.

For example, in the following figure, if D and E are passed in, a subtree (graph) formed by A, B, D and E should be returned

        A
      /  \
    B     C
   / \
  D   E
 /
G  

Answer 1

https://github.com/jgrapht/jgrapht/issues/1121 I asked the same question here and found a solution.

Answer 2

You need to figure out which vertices to include in the subgraph. You can do this by walking back from the bottom vertices you selected to the root node.

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

If desired, you could include some performance improvements in the above code, since some vertices get added multiple times to the queue. As per example, when you walk back from vertex D to the root node A, you will encounter vertex B. Similarly, when you walk back from E, you encounter B again. There's no need to re-visit B.