ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 10 Jun 2016 17:13:08 +0200Finding number of strongly connected componentshttps://ask.sagemath.org/question/33735/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!Fri, 10 Jun 2016 15:01:31 +0200https://ask.sagemath.org/question/33735/finding-number-of-strongly-connected-components/Answer by tmonteil for <p>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,</p>
<pre><code>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]``
</code></pre>
<p>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.</p>
<p>1) Should I just use len(~DiGraph.strongly_connected_components())?
2) Am I badly misreading the documentation for this method?</p>
<p>I'm in Sage 7.2.</p>
<p>Thanks in advance for help here!</p>
https://ask.sagemath.org/question/33735/finding-number-of-strongly-connected-components/?answer=33737#post-id-33737You are right the doc is not consistent with the actual output, thanks for reporting ! It is now [trac ticket 20800](http://trac.sagemath.org/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())
Fri, 10 Jun 2016 16:45:25 +0200https://ask.sagemath.org/question/33735/finding-number-of-strongly-connected-components/?answer=33737#post-id-33737Comment by JEFLSU for <p>You are right the doc is not consistent with the actual output, thanks for reporting ! It is now <a href="http://trac.sagemath.org/ticket/20800">trac ticket 20800</a></p>
<p>The result is indeed a list of strongly connected components, so to get their number, you just have to do, if <code>G</code> is a digraph:</p>
<pre><code>sage: len(G.strongly_connected_components())
</code></pre>
https://ask.sagemath.org/question/33735/finding-number-of-strongly-connected-components/?comment=33739#post-id-33739Thanks! 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?Fri, 10 Jun 2016 17:13:08 +0200https://ask.sagemath.org/question/33735/finding-number-of-strongly-connected-components/?comment=33739#post-id-33739