How to remove cycles from a directed graph by edge contraction?

Question

We have cyclic directed graph (possibly disconnected). For cycles consisting of two vertices A->B and B->A, we replace them by a single vertex. In case of A->B, B->C, C->A we also replace them by one vertex. We replace N vertices when all reachable from each other. Edges leaving a vertex stay as edges leaving the group containing the vertex. For example,

digraph cyclic {
        rankdir=BT;
01
2->3
3->2
5->2
6->4
8->3
9->4
a->4
a->9
9->a
b->8
b->c
c->b
6->7
7->8
8->6
}

We must obtain

digraph acyclic {
        rankdir=BT;
01
5->23
678->23
678->4
a9->4
bc->678
}

How is algorithm? Practical application of problem: we have class where method depends from fields and other methods. How decomposite to max number smallest classes? we allow multiple inheritance, inheritance diamond, but not allow cycles.

Answer 1

Since the only way to get rid of a cycle by edge contractions is to contract all the edges of the cycle to result in a single vertex, the vertices of the new graph are the strongly connected components of the original graph. Two vertices have an edge between them if the original components corresponding to these two vertices had such an edge in the same direction.

Strongly connected components can ve found in linear time.