Search code examples
javatreejgrapht

Split a tree in a forset using jgrapht

I have a tree represented with the library jgrapht, there are variuous type of nodes I need to cut any subtree starting from a particulare node type.

graph example

As you can see in this example, this tree represent a source code of a Java class. I need to create multiple jgrapht objects by splitting the main tree starting for each "Entry" node type. In total I should get 7 tree from this big one. The structure I use is a DirectedPseudograph.

Solution

  • Although I'm not 100% clear about what you want, it seems there are various solution approaches.

    1. Starting from every outgoing neighbor of the root node, you could run a depth first search and record the nodes returned. The nodes reachable by the DFS algorithm belong to the same subtree. For this you can use the DepthFirstIterator
    2. You could create a subgraph without the root node, for instance by using the AsSubgraph class. You can then invoke the ConnectivityInspector on the resulting induced subgraph. Since every subtree is a disconnected graph component, the connectivity inspector will be able to find each of these components.

    Btw, unless you need the capabilities of a Pseudograph, for performance it would be better to use the SimpleDirectedGraph. Obviously, the latter does not allow parallel edges or self-loops.