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:
- Make the graph acyclic by finding strong components (the result is a polytree)
- For each vertex with no incoming edges :
- Browse the graph (depth first), for each vertex
- 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
- Else
- Include this vertex in current tree
- 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?