Reduce cyclic graph to tree (dependency graph-->tree)

Question

I'm analyzing some code for its dependencies. Let's say there are some interwoven dependencies, like so:

                 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 into a super-node. We have a problem with C and E and F, they have a cycle. They should be combined into a super-node.

You would end up with

  A
  |
  V
super
 node
  |
  |
  D

Is there a good library or algorithm source (Java prefered, but open to suggestions) that allows for such reduction?

Any nodes in a cycle are combined into a single node. Any node that pointed to any node in the new node should point to the new node. Any node pointed to by any node in the new node should cause the new node to point to that node.

Thanks!

Answer 1

I believe you are asking to combine the strongly connected components of the graph. Yes?

I don't remember the algorithm, will try to look it up.

Edit: The one we learned is Tarjan's. I don't remember it well enough to teach, but here is the Wikipedia page.

I'll try to give the basic idea. Give each node an index #. Then give each node a lowlink #. The lowlink is the index of the node at the root from us: the first node to be considered that can find a path to us. If our lowlink == our index, then we are the root of a strongly connected component. Otherwise, we are in the same component as our lowlink is. By doing this over the whole graph, we can determine which nodes are parts of which strongly connected components.