Opened 6 years ago

Last modified 15 months 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 gh-darijgr)

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 6 years ago by darij

  • Cc sage-combinat added; sagecombinat removed
  • Description modified (diff)
  • Keywords bitset added

comment:2 Changed 6 years ago by ncohen

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 ?

comment:3 follow-up: Changed 6 years ago by darij

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: Changed 6 years ago by ncohen

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: Changed 6 years ago by darij

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 6 years ago by ncohen

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 6 years ago by darij

*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 6 years ago by ncohen

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: Changed 6 years ago by kcrisman

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: Changed 6 years ago by ncohen

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: Changed 6 years ago by kcrisman

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: Changed 6 years ago by ncohen

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 6 years ago by kcrisman

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:15 Changed 6 years ago by jdemeyer

  • Dependencies set to #10093
  • Description modified (diff)

comment:16 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:18 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:19 Changed 3 years ago by jakobkroeker

  • Stopgaps set to inconsistencyIssue

comment:20 Changed 3 years ago by jakobkroeker

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 17 months ago by pelegm

  • Cc pelegm added

comment:22 Changed 17 months ago by gh-darijgr

  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-8.3

comment:23 Changed 15 months ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

Note: See TracTickets for help on using tickets.