Algorithm to transform a polytree in a set of trees

95 Views Asked by At

Problem : Given a polytree graph, cut the graph in a set of trees that all depend from a common set.

Context : I have a huge java project that i want to cut in smaller projects. The goal is to have N top-projects which depend from a single common project.

I came up with this algorithm:

  1. Make the graph acyclic by finding strong components (the result is a polytree)
  2. For each vertex with no incoming edges :
    1. Browse the graph (depth first), for each vertex
    2. If the number of incoming edges is greater than N (N is a parameter of the algorithm) OR if common-set has an edge pointing to this vertex
      • Include this vertex in common-set
    3. Else
      • Include this vertex in current tree
    4. End if

This produces a result that seems valid, but the common set is HUGE.

Is my approach valid? Is there a better solution or an existing algorithm that I don't know of?