Ask Your Question
1

Why a graph with one vertex and no edge considered strongly connected?

asked 2017-12-05 01:52:49 -0600

Sébastien gravatar image

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]

?

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
1

answered 2017-12-05 04:02:19 -0600

tmonteil gravatar image

updated 2017-12-06 07:59:57 -0600

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.

edit flag offensive delete link more

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

Stats

Asked: 2017-12-05 01:52:49 -0600

Seen: 32 times

Last updated: Dec 06