# Finding number of strongly connected components

I need to find the number of strongly connected components of a digraph, and I looked at the documentation for the ~DiGraph.strongly_connected_components() method. Tabbing .strongly_connected_components? gives the documentation from sage/graphs/base/static_sparse_graph.pyx for tarjan_strongly_connected_components(G) that says,

This routine returns a pair [nscc, scc], where nscc is the number of
SCCs and scc is a dictionary associating to each vertex v an
integer between 0 and nscc-1, corresponding to the SCC containing
v. SCCs
are numbered in reverse topological order, that is, if (v,w) is an edge
in the graph, scc[v] <= scc[w]


Which would be great, as I just need the result of tarjan_strongly_connected_components_C. However, 1) this is only called during tarjan_strongly_connected_components, which does the (admittedly minor) additional work of topologically sorting SCCs and 2) the examples (and testing) show the output of ~DiGraph.strongly_connected_components() is a list of vertex lists for each connected component. This is perfectly reasonable and clear, but more than I want, particularly as there's some work in the back end that determines what I'm looking for earlier in the process.

1) Should I just use len(~DiGraph.strongly_connected_components())? 2) Am I badly misreading the documentation for this method?

I'm in Sage 7.2.

Thanks in advance for help here!

edit retag close merge delete

Sort by ยป oldest newest most voted

You are right the doc is not consistent with the actual output, thanks for reporting ! It is now trac ticket 20800

The result is indeed a list of strongly connected components, so to get their number, you just have to do, if G is a digraph:

sage: len(G.strongly_connected_components())

more

Thanks! I imagine the documentation was at some point in the past consistent with the method; supposing that is so, perhaps there is some discussion floating around on why the method's output was changed?

( 2016-06-10 17:13:08 +0200 )edit