Reduce the cyclic graph to a tree (dependency graph & # 8594; tree)

Question

I am analyzing some code for its dependencies. Let's say there are some intertwined dependencies, for example:

F A /| | / | | / | V < V B<--->C--->E \ / | > < | D<------+ 

B depends on A and C C depends on B and F E depends on C and F D depends on B and C and E

We have a problem with B and C, they depend on each other. They should be combined in a super-node. We have a problem with C and E and F, they have a loop. They must be combined in a super-node.

As a result, you get

  A | V super node | | D 

Is there a good library or source of the algorithm (preferred by Java, but open to suggestions) that allows such a reduction?

Any nodes of the cycle are combined into one node. Any node pointing to any node in a new node must point to a new node. Any node that any node in the new node points to should cause the new node to point to node.

Thanks!

Answer 1

I believe that you are asking to combine strongly related components on the chart. Yes?

I do not remember the algorithm, try to find it.

Edit: the one we learned is Tarjan. I don’t remember him well enough to teach, but here is the Wikipedia page .

I will try to give a basic idea. Give each node a C # index. Then give each node a link #. The bottom link is the node index at the root of us: the first node to consider, which can find the way to us. If our lowlink == is our index, then we are the root of a strongly related component. Otherwise, we are in the same component as our lowlink. By doing this on the entire graph, we can determine which nodes are parts of which the components are strongly connected.