Ask Your Question

Finding number of strongly connected components

asked 2016-06-10 08:01:31 -0500

JEFLSU gravatar image

updated 2016-06-10 09:59:59 -0500

tmonteil gravatar image

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 flag offensive close merge delete

1 answer

Sort by » oldest newest most voted

answered 2016-06-10 09:45:25 -0500

tmonteil gravatar image

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())
edit flag offensive delete link 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?

JEFLSU gravatar imageJEFLSU ( 2016-06-10 10:13:08 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2016-06-10 08:01:31 -0500

Seen: 211 times

Last updated: Jun 10 '16