ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 05 Dec 2017 04:02:19 -0600Why a graph with one vertex and no edge considered strongly connected?http://ask.sagemath.org/question/39945/why-a-graph-with-one-vertex-and-no-edge-considered-strongly-connected/Everytime I need to use the strongly connected components of a graph in Sage, I am looking for a graph where there exists a biinfinite path going trough all the vertices of a components infinitely often. In that sense, I dislike the behavior of
the methods `is_strongly_connected` and `strongly_connected_components`.
More precisely, I agree with this:
sage: G = DiGraph(loops=True)
sage: G.add_edge((0,0))
sage: G.is_strongly_connected()
True
I dislike that this is not returning False:
sage: G = DiGraph()
sage: G.add_vertex(0)
sage: G.is_strongly_connected()
True
and I dislike that `strongly_connected_components` method and its friends always return a lot of garbage components containing one vertex with no loops where no biinfinite path can live in:
sage: G = DiGraph()
sage: G.add_edges([(i,i+1) for i in range(9)])
sage: G.add_edge(9,6)
sage: G.strongly_connected_components()
[[6, 7, 8, 9], [5], [4], [3], [2], [1], [0]]
sage: G.strongly_connected_components_subgraphs()
[Subgraph of (): Digraph on 4 vertices,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex]
Do you think like me that the definition should be changed to :
sage: [sub for sub in G.strongly_connected_components_subgraphs() if sub.num_edges()]
[Subgraph of (): Digraph on 4 vertices]
?Tue, 05 Dec 2017 01:52:49 -0600http://ask.sagemath.org/question/39945/why-a-graph-with-one-vertex-and-no-edge-considered-strongly-connected/Answer by tmonteil for <p>Everytime I need to use the strongly connected components of a graph in Sage, I am looking for a graph where there exists a biinfinite path going trough all the vertices of a components infinitely often. In that sense, I dislike the behavior of
the methods <code>is_strongly_connected</code> and <code>strongly_connected_components</code>.</p>
<p>More precisely, I agree with this:</p>
<pre><code>sage: G = DiGraph(loops=True)
sage: G.add_edge((0,0))
sage: G.is_strongly_connected()
True
</code></pre>
<p>I dislike that this is not returning False:</p>
<pre><code>sage: G = DiGraph()
sage: G.add_vertex(0)
sage: G.is_strongly_connected()
True
</code></pre>
<p>and I dislike that <code>strongly_connected_components</code> method and its friends always return a lot of garbage components containing one vertex with no loops where no biinfinite path can live in:</p>
<pre><code>sage: G = DiGraph()
sage: G.add_edges([(i,i+1) for i in range(9)])
sage: G.add_edge(9,6)
sage: G.strongly_connected_components()
[[6, 7, 8, 9], [5], [4], [3], [2], [1], [0]]
sage: G.strongly_connected_components_subgraphs()
[Subgraph of (): Digraph on 4 vertices,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex,
Subgraph of (): Digraph on 1 vertex]
</code></pre>
<p>Do you think like me that the definition should be changed to :</p>
<pre><code>sage: [sub for sub in G.strongly_connected_components_subgraphs() if sub.num_edges()]
[Subgraph of (): Digraph on 4 vertices]
</code></pre>
<p>?</p>
http://ask.sagemath.org/question/39945/why-a-graph-with-one-vertex-and-no-edge-considered-strongly-connected/?answer=39947#post-id-39947Note that if you remove the "biinfinite", there is no problem, because of the empty path. Usually, when we speak about "components", we expect to get a partition of the ground set, your definition breaks that. I do understand the behaviour you expect, but imho, it should be at most an option, definitely not the default, the default should be what is expected by an average graph theorist.Tue, 05 Dec 2017 04:02:19 -0600http://ask.sagemath.org/question/39945/why-a-graph-with-one-vertex-and-no-edge-considered-strongly-connected/?answer=39947#post-id-39947