# 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.is_strongly_connected()
True


I dislike that this is not returning False:

sage: G = DiGraph()
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.strongly_connected_components()
[[6, 7, 8, 9], , , , , , ]
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]


?

edit retag close merge delete

Sort by » oldest newest most voted

Note 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.

more