Is there any algorithm which can transform any graph to tree, with providing mapping from one to another? Suppose we have directed graph:
E->A A->C C->C C->B B->A B->D
I want to convert it to tree in such way, that all biggest cycles is converted to node, and all dependencies out of this cycle is binded to this node. So, in other words, all cycles represented as nodes.
For example, the biggest cycle here:
A B C
Biggest cycle is a cycle which do not contained in other cycles. So, in example [C] is one-node-cycle but it contained in bigger cycle [A,B,C], so it is not biggest. On the other hand [A,B,C] is not contained in any other cycle, so it is biggest. Graph can contain multiple biggest cycles.
Output will be:
E->F F->D where F is alias for A,B,C
Is there some algorithm for this?
Other interesting example with 2 biggest cycles:
A->B B->A A->C C->D D->C
Will be converted to:
E->F where E is alias for A,B where F is alias for C,D