Wishlist: Condensation of directed graph

[szhorvat]

What is the feature or improvement you would like to see?

A function that returns the condensation of the directed graph.

The condensation of a directed graph is obtained by contracting each strongly connected component to a single vertex.

It would be particularly useful to index the vertices of the condensation in topological order.

Use cases for the feature

• The condensation is a compact representation of the reachability structure of the graph
• Feature parity with other libraries

Alternatives

This is currently doable by using igraph_connected_compoments(), igraph_contract_vertices(), then igraph_simplify(). A more efficient version that produces vertices in topological order would be nice.

References

• Wishlist: How many vertices are reachable from each vertex? #1872