Sage: Ticket #15060: The empty graph once again
https://trac.sagemath.org/ticket/15060
<pre class="wiki">sage: Graph({}).is_connected()
True
</pre><p>
If my understanding of good terminology is correct, this should not be the case (see <a class="ext-link" href="http://ncatlab.org/nlab/show/too+simple+to+be+simple"><span class="icon"></span>http://ncatlab.org/nlab/show/too+simple+to+be+simple</a> ). Note that <code>Graph({}).is_tree()</code> correctly returns <code>False</code>.
</p>
<p>
Another issue is that
</p>
<pre class="wiki">Graph({}).is_triangle_free()
</pre><p>
seems to allocate lots of RAM and possibly die with a <a class="missing wiki">MemoryError?</a> (it did so on the Sage cell server; on my machine I had to ctrl-alt-del the VM). The culprit seems to be <code>Bitset(capacity=0)</code>. If I see other issues caused by this, I'll open up a new ticket for this.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15060
Trac 1.1.6darijSun, 18 Aug 2013 16:00:20 GMTcc, keywords, description changed
https://trac.sagemath.org/ticket/15060#comment:1
https://trac.sagemath.org/ticket/15060#comment:1
<ul>
<li><strong>cc</strong>
<em>sage-combinat</em> added; <em>sagecombinat</em> removed
</li>
<li><strong>keywords</strong>
<em>bitset</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/15060?action=diff&version=1">diff</a>)
</li>
</ul>
TicketncohenSun, 18 Aug 2013 18:25:50 GMT
https://trac.sagemath.org/ticket/15060#comment:2
https://trac.sagemath.org/ticket/15060#comment:2
<p>
Ahahah. I mostly agree with the first comment of <a class="ext-link" href="http://math.stackexchange.com/questions/50551/is-the-empty-graph-connected"><span class="icon"></span>http://math.stackexchange.com/questions/50551/is-the-empty-graph-connected</a> : "This is not mathematics, this is theology".
</p>
<p>
Honestly, why do you insist on putting those weird definitions in Sage ? Now you can make a disconnected graph connected by adding an isolated vertex to it ? <code>:-P</code>
What's the point ? It's unnatural. It just confuses people. It will just create bugs. Why can't we just say that a graph is connected if any two vertices are linked by a path and be satisfied with that ?
</p>
TicketdarijSun, 18 Aug 2013 18:38:29 GMT
https://trac.sagemath.org/ticket/15060#comment:3
https://trac.sagemath.org/ticket/15060#comment:3
<p>
I noticed the issue when I tried to compute the chromatic polynomial of an empty graph and got a wrong answer with <a class="needs_info ticket" href="https://trac.sagemath.org/ticket/14529" title="enhancement: Drastic performance improvement of computing the chromatic polynomial (needs_info)">#14529</a> applied (and an error without). It starts by checking whether the graph is connected and if not, multiplying the characteristic polynomials of the connected components. I claim that most of the time, connectedness appears together with connected components, and from the viewpoint of connected components it is much more natural to have empty objects disconnected.
</p>
<p>
If you are saying it's theology, can't we rather output an error instead of claiming it is "True"?
</p>
TicketncohenSun, 18 Aug 2013 18:46:22 GMT
https://trac.sagemath.org/ticket/15060#comment:4
https://trac.sagemath.org/ticket/15060#comment:4
<blockquote class="citation">
<p>
I noticed the issue when I tried to compute the chromatic polynomial of an empty graph and got a wrong answer with <a class="needs_info ticket" href="https://trac.sagemath.org/ticket/14529" title="enhancement: Drastic performance improvement of computing the chromatic polynomial (needs_info)">#14529</a> applied (and an error without). It starts by checking whether the graph is connected and if not, multiplying the characteristic polynomials of the connected components. I claim that most of the time, connectedness appears together with connected components, and from the viewpoint of connected components it is much more natural to have empty objects disconnected.
</p>
</blockquote>
<p>
<code>O_o</code>
</p>
<p>
What is wrong with "a graph is connected if any two vertices are linked by a path" ? An empty graph can be partitionned in connected component, i.e. only one : itself.
</p>
<blockquote class="citation">
<p>
If you are saying it's theology, can't we rather output an error instead of claiming it is "True"?
</p>
</blockquote>
<p>
I would love it to be <code>"ValueError: We don't know whether an empty graph is connected. We discussed it, and just never agreed on anything"</code>
</p>
<p>
It would make it a very practical issue rather than a theoretical one, and emphasize that definitions are mostly what people agree on <code>:-P</code>
</p>
<p>
The same should hold for <code>Graph({}).is_tree()</code> of course <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketdarijSun, 18 Aug 2013 19:00:40 GMT
https://trac.sagemath.org/ticket/15060#comment:5
https://trac.sagemath.org/ticket/15060#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15060#comment:4" title="Comment 4">ncohen</a>:
</p>
<blockquote class="citation">
<p>
What is wrong with "a graph is connected if any two vertices are linked by a path" ? An empty graph can be partitionned in connected component, i.e. only one : itself.
</p>
</blockquote>
<p>
Then the factorization of a graph into disjoint connected components is not unique. You can add as many empty components as you wish then.
</p>
<blockquote class="citation">
<p>
I would love it to be <code>"ValueError: We don't know whether an empty graph is connected. We discussed it, and just never agreed on anything"</code>
</p>
</blockquote>
<p>
Sounds good :)
</p>
TicketncohenSun, 18 Aug 2013 19:03:42 GMT
https://trac.sagemath.org/ticket/15060#comment:6
https://trac.sagemath.org/ticket/15060#comment:6
<blockquote class="citation">
<p>
Then the factorization of a graph into disjoint connected components is not unique. You can add as many empty components as you wish then.
</p>
</blockquote>
<p>
ahahaha. Well, at least I have no reason to ask for a decomposition of a connected graph into connected subgraphs. What would you answer for the empty graph ? <code>:-P</code>
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
I would love it to be <code>"ValueError: We don't know whether an empty graph is connected. We discussed it, and just never agreed on anything"</code>
</p>
</blockquote>
<p>
Sounds good :)
</p>
</blockquote>
<p>
Really ? Great then ! I love when arbitrary decisions are claimed as such ! "We had no idea. So let's not write anything we might regret" <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketdarijSun, 18 Aug 2013 19:47:43 GMT
https://trac.sagemath.org/ticket/15060#comment:7
https://trac.sagemath.org/ticket/15060#comment:7
<p>
*Any* graph will have infinitely many decompositions in connected components once you say that the empty graph is connected. Not what I'd want. But since people disagree more than I expected, I'm completely fine with throwing a valueerror.
</p>
TicketncohenSun, 18 Aug 2013 20:16:39 GMT
https://trac.sagemath.org/ticket/15060#comment:8
https://trac.sagemath.org/ticket/15060#comment:8
<p>
Well, as according to your definition the empty set doesn't have any decomposition into connected components either, let's just agree that a decomposition into connected components if only defined for nonempty connected components.
</p>
<p>
Ahahahah.
</p>
<p>
Yes, it's ugly.
</p>
<p>
Your definition would be better there.
</p>
<p>
But honestly... The empty graph ? Disconnected? <code>:-PPPPP</code>
</p>
<p>
Nathann
</p>
TicketkcrismanMon, 19 Aug 2013 02:42:58 GMT
https://trac.sagemath.org/ticket/15060#comment:9
https://trac.sagemath.org/ticket/15060#comment:9
<p>
As a non graph-theorist... I was wondering whether the empty graph should be a connected graph with zero connected components. Though one of the definitions on that math.SX question suggested one connected component is the definition of connected.
</p>
<p>
So... what do the various standard texts say about this? Maybe they are silent on the question?
</p>
<p>
Note that apparently there is still enough disagreement about the definition that the Wikipedia article on the related set question (connectedness) points it out, though without references.
</p>
<p>
Perhaps it is better to *document* that we follow a certain convention (probably the more obvious one, in this case), and then in documentation for anything about connected components point it out again. If we really have to. I don't quite see why there are infinitely many decompositions, since the empty graph does not have any connected components (which is not quite the same as a connected graph) - or perhaps I err in thinking a component has to be non-empty. Naturally, this is all just deciding on a definition. But it's not quite the same as 1 not being a prime number (and note Conway's argument that 1 and -1 <em>do</em> count, but as prime <em>powers</em>, not "primes", whatever those are - perhaps something analogous could work with sets or graphs, who knows).
</p>
TicketncohenMon, 19 Aug 2013 06:54:33 GMT
https://trac.sagemath.org/ticket/15060#comment:10
https://trac.sagemath.org/ticket/15060#comment:10
<p>
Yooooooooooooo !!
</p>
<blockquote class="citation">
<p>
As a non graph-theorist... I was wondering whether the empty graph should be a connected graph with zero connected components. Though one of the definitions on that math.SX question suggested one connected component is the definition of connected.
</p>
</blockquote>
<p>
You will also see at a lot of places that a graph is connected if and only if any two vertices are linked by a path.
</p>
<blockquote class="citation">
<p>
So... what do the various standard texts say about this? Maybe they are silent on the question?
</p>
</blockquote>
<p>
Because there are moments when you want them to be connected, other when you don't want them to be. I just had a look at Diestel's book (page 2, <a class="ext-link" href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf"><span class="icon"></span>http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf</a>) :
</p>
<p>
"For the empty graph (\emptyset,\emptyset) we simply write \emptyset. A graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an induction, trivial graphs can be useful; at other times they form silly counterexamples and become a nuisance. To avoid cluttering the text with non-triviality conditions, we shall mostly trat the trivial graphs, and particularly the empty graph \emptyset with generous disregard."
</p>
<p>
After which he defines connectedness by : "A non-empty graph G is called connected if <a href="https://trac.sagemath.org/ticket">..</a>".
</p>
<blockquote class="citation">
<p>
Perhaps it is better to *document* that we follow a certain convention (probably the more obvious one, in this case),
</p>
</blockquote>
<p>
We also disagree on the most obvious one I guess <code>:-P</code>
We had another battle like that about whether the complete graph and the empty graph are strongly regular. I was decided that they weren't because there is a theorem saying that strongly regular graphs have exactly 3 eigenvalues <code>:-PPPP</code>
(needless to say I don't agree with that <code>:-P</code>)
</p>
<blockquote class="citation">
<p>
and then in documentation for anything about connected components point it out again. If we really have to.
</p>
</blockquote>
<p>
Come on.. Nobody reads these things before finding a bug in the code, everybody assumes that his own definition of connectivity is right. To me any definition is a mistake.
</p>
<blockquote class="citation">
<p>
I don't quite see why there are infinitely many decompositions,
</p>
</blockquote>
<p>
He claims that you can add as many empty graphs to a "connected subgraphs decomposition" as soon as you assume the empty graph to be connected.
</p>
<blockquote class="citation">
<p>
since the empty graph does not have any connected components (which is not quite the same as a connected graph) - or perhaps I err in thinking a component has to be non-empty.
</p>
</blockquote>
<p>
Well, if you add nonempty to the definition of connected components decomposition then everything is fine.
</p>
<blockquote class="citation">
<p>
Naturally, this is all just deciding on a definition. But it's not quite the same as 1 not being a prime number (and note Conway's argument that 1 and -1 <em>do</em> count, but as prime <em>powers</em>, not "primes", whatever those are - perhaps something analogous could work with sets or graphs, who knows).
</p>
</blockquote>
<p>
It's a word play. It's theology <code>:-P</code>
</p>
<p>
The truth is that we could take any definition and explain at length why it's the best way to see it. And usually it is to make our favorite theorems work for the empty graph too <code>:-P</code>
</p>
<p>
We should just raise an exception when an empty graph is created : <code>ThisThingDoesNotExistException : it's safer to deny the existence of the empty graph. It really creates a lot of problems if you don't</code> <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketkcrismanMon, 19 Aug 2013 13:20:35 GMT
https://trac.sagemath.org/ticket/15060#comment:11
https://trac.sagemath.org/ticket/15060#comment:11
<blockquote class="citation">
<blockquote class="citation">
<p>
As a non graph-theorist... I was wondering whether the empty graph should be a connected graph with zero connected components. Though one of the definitions on that math.SX question suggested one connected component is the definition of connected.
</p>
</blockquote>
<p>
You will also see at a lot of places that a graph is connected if and only if any two vertices are linked by a path.
</p>
</blockquote>
<p>
Well, yes, that was the definition that I (and you) had in mind. Just because I'm not a graph theorist doesn't mean I'm not fairly conversant with graph theory ;-)
</p>
<blockquote class="citation">
<p>
Because there are moments when you want them to be connected, other when you don't want them to be. I just had a look at Diestel's book (page 2, <a class="ext-link" href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf"><span class="icon"></span>http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf</a>) :
</p>
<p>
"For the empty graph (\emptyset,\emptyset) we simply write \emptyset. A graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an induction, trivial graphs can be useful; at other times they form silly counterexamples and become a nuisance. To avoid cluttering the text with non-triviality conditions, we shall mostly trat the trivial graphs, and particularly the empty graph \emptyset with generous disregard."
</p>
</blockquote>
<p>
That sounds like a good approach, but one that doesn't work for computers :(
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
since the empty graph does not have any connected components (which is not quite the same as a connected graph) - or perhaps I err in thinking a component has to be non-empty.
</p>
</blockquote>
<p>
Well, if you add nonempty to the definition of connected components decomposition then everything is fine.
</p>
</blockquote>
<p>
Right, that's what I meant. Otherwise the notion of a connected component seems less useful. But I suppose it's all a matter of one's favorite definition, as we all seem to agree. Is the theorem what defines connectedness, or is the definition what leads to the theorem? That's sort of what's going on here.
</p>
<p>
Well, have fun resolving this! I think that leaving it as it is, with a brief comment we can point to when people complain, is easiest. If it really is a bug at <a class="needs_info ticket" href="https://trac.sagemath.org/ticket/14529" title="enhancement: Drastic performance improvement of computing the chromatic polynomial (needs_info)">#14529</a>, that is different, but it probably just means that patch needs some slight adjustment. After all, changing this could also lead to unintended consequences in other code that assumed implicitly that this worked. I suppose it's also an API change in some ways.
</p>
TicketncohenMon, 19 Aug 2013 15:22:59 GMT
https://trac.sagemath.org/ticket/15060#comment:12
https://trac.sagemath.org/ticket/15060#comment:12
<p>
Yoooooooooooooo !!!
</p>
<blockquote class="citation">
<p>
That sounds like a good approach, but one that doesn't work for computers :(
</p>
</blockquote>
<p>
Does it ? Well, what do you think of this "<a class="missing wiki">WeHaveNoIdeaException?</a>" ? Do you think it's not a good way out ?
</p>
<blockquote class="citation">
<p>
Right, that's what I meant. Otherwise the notion of a connected component seems less useful. But I suppose it's all a matter of one's favorite definition, as we all seem to agree. Is the theorem what defines connectedness, or is the definition what leads to the theorem? That's sort of what's going on here.
</p>
</blockquote>
<p>
I'd say that the theorems make the definitions they need <code>:-P</code>
</p>
<blockquote class="citation">
<p>
Well, have fun resolving this! I think that leaving it as it is, with a brief comment we can point to when people complain, is easiest. If it really is a bug at <a class="needs_info ticket" href="https://trac.sagemath.org/ticket/14529" title="enhancement: Drastic performance improvement of computing the chromatic polynomial (needs_info)">#14529</a>, that is different, but it probably just means that patch needs some slight adjustment.
</p>
</blockquote>
<p>
Yepyep, it can be fixed with a <code>if G.order() == 0</code>.
</p>
<blockquote class="citation">
<p>
After all, changing this could also lead to unintended consequences in other code that assumed implicitly that this worked.
</p>
</blockquote>
<p>
Or that assumed incorrectly that it worked and gave the other answer <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketkcrismanMon, 19 Aug 2013 15:41:55 GMT
https://trac.sagemath.org/ticket/15060#comment:13
https://trac.sagemath.org/ticket/15060#comment:13
<blockquote class="citation">
<p>
Does it ? Well, what do you think of this "<a class="missing wiki">WeHaveNoIdeaException?</a>" ? Do you think it's not a good way out ?
</p>
</blockquote>
<p>
No, that seems silly to me. We should just pick a definition. But you could ask on sage-devel - I'm sure this comes up elsewhere (disagreement about definitions).
</p>
<blockquote class="citation">
<p>
Yepyep, it can be fixed with a <code>if G.order() == 0</code>.
</p>
</blockquote>
<p>
I suspected as much.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
After all, changing this could also lead to unintended consequences in other code that assumed implicitly that this worked.
</p>
</blockquote>
<p>
Or that assumed incorrectly that it worked and gave the other answer <code>:-P</code>
</p>
</blockquote>
<p>
I meant within the Sage library, but yes, that too.
</p>
TicketncohenMon, 19 Aug 2013 15:52:27 GMT
https://trac.sagemath.org/ticket/15060#comment:14
https://trac.sagemath.org/ticket/15060#comment:14
<p>
<a class="ext-link" href="https://groups.google.com/d/topic/sage-devel/WVJ6YIURESs/discussion"><span class="icon"></span>https://groups.google.com/d/topic/sage-devel/WVJ6YIURESs/discussion</a>
</p>
<p>
Done ! <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerTue, 10 Dec 2013 15:57:51 GMTdescription changed; dependencies set
https://trac.sagemath.org/ticket/15060#comment:15
https://trac.sagemath.org/ticket/15060#comment:15
<ul>
<li><strong>dependencies</strong>
set to <em>#10093</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/15060?action=diff&version=15">diff</a>)
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/15060#comment:16
https://trac.sagemath.org/ticket/15060#comment:16
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/15060#comment:17
https://trac.sagemath.org/ticket/15060#comment:17
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/15060#comment:18
https://trac.sagemath.org/ticket/15060#comment:18
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketjakobkroekerSat, 09 Jul 2016 16:54:35 GMTstopgaps set
https://trac.sagemath.org/ticket/15060#comment:19
https://trac.sagemath.org/ticket/15060#comment:19
<ul>
<li><strong>stopgaps</strong>
set to <em>inconsistencyIssue</em>
</li>
</ul>
TicketjakobkroekerSat, 09 Jul 2016 16:56:46 GMT
https://trac.sagemath.org/ticket/15060#comment:20
https://trac.sagemath.org/ticket/15060#comment:20
<p>
I just thought, what about dropping the definition for graph connectedness at all.
and introduce three different cases instead:
</p>
<ul><li>a graph has 0 components
</li><li>a graph has exactly 1 component
</li><li>a graph has 2 or more components
</li></ul><p>
At least we are able to count ;-)
</p>
<p>
I think If we cannot handle special cases consistently even in theory, we will never ever be able to implement it without getting tons of worms...
</p>
<p>
see also the discussion at
<a class="ext-link" href="https://groups.google.com/forum/#!msg/sage-devel/WVJ6YIURESs/cQi1U6M1QRMJ"><span class="icon"></span>https://groups.google.com/forum/#!msg/sage-devel/WVJ6YIURESs/cQi1U6M1QRMJ</a>
</p>
TicketpelegmWed, 23 May 2018 10:18:57 GMTcc changed
https://trac.sagemath.org/ticket/15060#comment:21
https://trac.sagemath.org/ticket/15060#comment:21
<ul>
<li><strong>cc</strong>
<em>pelegm</em> added
</li>
</ul>
Ticketgh-darijgrSat, 26 May 2018 07:28:08 GMTdescription, milestone changed
https://trac.sagemath.org/ticket/15060#comment:22
https://trac.sagemath.org/ticket/15060#comment:22
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15060?action=diff&version=22">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-8.3</em>
</li>
</ul>
TicketvdelecroixFri, 03 Aug 2018 19:20:18 GMTmilestone changed
https://trac.sagemath.org/ticket/15060#comment:23
https://trac.sagemath.org/ticket/15060#comment:23
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.3</em> to <em>sage-8.4</em>
</li>
</ul>
<p>
update milestone 8.3 -> 8.4
</p>
Ticket