Opened 8 years ago
Last modified 3 years ago
#15060 new defect
The empty graph once again
Reported by: | darij | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.4 |
Component: | combinatorics | Keywords: | graphs, border cases, bitset, memleak |
Cc: | sage-combinat, pelegm | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10093 | Stopgaps: | inconsistencyIssue |
Description (last modified by )
sage: Graph({}).is_connected() True
If my understanding of good terminology is correct, this should not be the case (see http://ncatlab.org/nlab/show/too+simple+to+be+simple ). Note that Graph({}).is_tree()
correctly returns False
.
[EDIT: removed "another issue" which has been fixed in the meantime.]
Change History (23)
comment:1 Changed 8 years ago by
- Cc sage-combinat added; sagecombinat removed
- Description modified (diff)
- Keywords bitset added
comment:2 Changed 8 years ago by
comment:3 follow-up: ↓ 4 Changed 8 years ago by
I noticed the issue when I tried to compute the chromatic polynomial of an empty graph and got a wrong answer with #14529 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.
If you are saying it's theology, can't we rather output an error instead of claiming it is "True"?
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 8 years ago by
I noticed the issue when I tried to compute the chromatic polynomial of an empty graph and got a wrong answer with #14529 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.
O_o
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.
If you are saying it's theology, can't we rather output an error instead of claiming it is "True"?
I would love it to be "ValueError: We don't know whether an empty graph is connected. We discussed it, and just never agreed on anything"
It would make it a very practical issue rather than a theoretical one, and emphasize that definitions are mostly what people agree on :-P
The same should hold for Graph({}).is_tree()
of course :-P
Nathann
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 8 years ago by
Replying to ncohen:
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.
Then the factorization of a graph into disjoint connected components is not unique. You can add as many empty components as you wish then.
I would love it to be
"ValueError: We don't know whether an empty graph is connected. We discussed it, and just never agreed on anything"
Sounds good :)
comment:6 in reply to: ↑ 5 Changed 8 years ago by
Then the factorization of a graph into disjoint connected components is not unique. You can add as many empty components as you wish then.
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 ? :-P
I would love it to be
"ValueError: We don't know whether an empty graph is connected. We discussed it, and just never agreed on anything"
Sounds good :)
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" :-D
Nathann
comment:7 Changed 8 years ago by
*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.
comment:8 Changed 8 years ago by
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.
Ahahahah.
Yes, it's ugly.
Your definition would be better there.
But honestly... The empty graph ? Disconnected? :-PPPPP
Nathann
comment:9 follow-up: ↓ 10 Changed 8 years ago by
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.
So... what do the various standard texts say about this? Maybe they are silent on the question?
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.
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 do count, but as prime powers, not "primes", whatever those are - perhaps something analogous could work with sets or graphs, who knows).
comment:10 in reply to: ↑ 9 ; follow-up: ↓ 11 Changed 8 years ago by
Yooooooooooooo !!
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.
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.
So... what do the various standard texts say about this? Maybe they are silent on the question?
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, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf) :
"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."
After which he defines connectedness by : "A non-empty graph G is called connected if ..".
Perhaps it is better to *document* that we follow a certain convention (probably the more obvious one, in this case),
We also disagree on the most obvious one I guess :-P
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 :-PPPP
(needless to say I don't agree with that :-P
)
and then in documentation for anything about connected components point it out again. If we really have to.
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.
I don't quite see why there are infinitely many decompositions,
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.
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.
Well, if you add nonempty to the definition of connected components decomposition then everything is fine.
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 do count, but as prime powers, not "primes", whatever those are - perhaps something analogous could work with sets or graphs, who knows).
It's a word play. It's theology :-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 :-P
We should just raise an exception when an empty graph is created : ThisThingDoesNotExistException : it's safer to deny the existence of the empty graph. It really creates a lot of problems if you don't
:-P
Nathann
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 8 years ago by
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.
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.
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 ;-)
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, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf) :
"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."
That sounds like a good approach, but one that doesn't work for computers :(
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.
Well, if you add nonempty to the definition of connected components decomposition then everything is fine.
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.
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 #14529, 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.
comment:12 in reply to: ↑ 11 ; follow-up: ↓ 13 Changed 8 years ago by
Yoooooooooooooo !!!
That sounds like a good approach, but one that doesn't work for computers :(
Does it ? Well, what do you think of this "WeHaveNoIdeaException?" ? Do you think it's not a good way out ?
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.
I'd say that the theorems make the definitions they need :-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 #14529, that is different, but it probably just means that patch needs some slight adjustment.
Yepyep, it can be fixed with a if G.order() == 0
.
After all, changing this could also lead to unintended consequences in other code that assumed implicitly that this worked.
Or that assumed incorrectly that it worked and gave the other answer :-P
Nathann
comment:13 in reply to: ↑ 12 Changed 8 years ago by
Does it ? Well, what do you think of this "WeHaveNoIdeaException?" ? Do you think it's not a good way out ?
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).
Yepyep, it can be fixed with a
if G.order() == 0
.
I suspected as much.
After all, changing this could also lead to unintended consequences in other code that assumed implicitly that this worked.
Or that assumed incorrectly that it worked and gave the other answer
:-P
I meant within the Sage library, but yes, that too.
comment:14 Changed 8 years ago by
comment:15 Changed 8 years ago by
- Dependencies set to #10093
- Description modified (diff)
comment:16 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:17 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:18 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:19 Changed 5 years ago by
- Stopgaps set to inconsistencyIssue
comment:20 Changed 5 years ago by
I just thought, what about dropping the definition for graph connectedness at all. and introduce three different cases instead:
- a graph has 0 components
- a graph has exactly 1 component
- a graph has 2 or more components
At least we are able to count ;-)
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...
see also the discussion at https://groups.google.com/forum/#!msg/sage-devel/WVJ6YIURESs/cQi1U6M1QRMJ
comment:21 Changed 3 years ago by
- Cc pelegm added
comment:22 Changed 3 years ago by
- Description modified (diff)
- Milestone changed from sage-6.4 to sage-8.3
comment:23 Changed 3 years ago by
- Milestone changed from sage-8.3 to sage-8.4
update milestone 8.3 -> 8.4
Ahahah. I mostly agree with the first comment of http://math.stackexchange.com/questions/50551/is-the-empty-graph-connected : "This is not mathematics, this is theology".
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 ?
:-P
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 ?