Is the glass half-full or half-empty ? Pick a standard.

[Nathann Cohen]

Helloooooooo everybody !!

There is a discussion on theology going on at #15060, about whether we
should consider whether the empty graph is connected or not. We
already had one about deciding whether the empty graph is a tree or
not, and Karl-Dieter supposed that other discussions of this kind
already happened in Sage.

Here's the thing : we have two definitions which conflict on a trivial
case only, and we have functions that are expected to answer whether
-- yes or no -- the property holds.

I personally voted for not answering anything, and raising a "We Have
No Idea And We Don't Want To Be Forced To Give An Answer Exception" in
this case, for there is no way to give an answer that would not lead
anybody to very weird bugs.

What do you think ? Darij agreed with this idea, and Karl-Dieter
believes that we should make a decision and answer something :-)

Help us ! :-P

Nathann

[Jernej Azarija]

Hello!

As you can check here http://mathoverflow.net/questions/120536/is-the-empty-graph-a-tree

the big shot guys agree that the empty graph is to be considered disconnected. So YES in general, mathematicians appear to be depressed persons.....

[John Cremona]

This sounds very like the number theory analogue, is 1 prime or
composite -- to which the answer is "neither". That's like counting
te number of connected components: 0 for the empty graph, 1 for a
connected graph (nonempty!) and 2 or more for disconnected graphs.

You really don't want to spoil theorems like uniqueness of
decomposition into connected components. For the empty graph, that's
ok, tere are 0 connected components, just as 1 is the product 0
primes.

In Sage Integers have as is_prime method (and 1.is_prime() is of
course False but no is_composite() method. I suggest that you follow
the lead and have G.is_connected() False for empty G, noting that this
is not backwards compatible, and then you will not have the silly
situation that (in 5.11)

sage: G = Graph([]); G
Graph on 0 vertices
sage: G.is_connected()
True
sage: G.connected_components()
[]
as to me it seems contradictory to have a graph claiming to be
connected but having no connected components.

John

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.

[John Cremona]

PS Note that if you ever did decide to have a method
G.is_disconnected() then I would want that to be False also for the
emtpy graph, just as 1 is not composite.

[Julien Puydt]

Le 19/08/2013 17:51, Nathann Cohen a �crit :

> There is a discussion on theology going on at #15060, about whether we
> should consider whether the empty graph is connected or not. We
> already had one about deciding whether the empty graph is a tree or
> not, and Karl-Dieter supposed that other discussions of this kind
> already happened in Sage.

It's like the question whether the empty set is connected... and the
correct answer is that it depends on the author!

Snark

[Julien Puydt]

Le 19/08/2013 18:09, John Cremona a �crit :

> This sounds very like the number theory analogue, is 1 prime or
> composite -- to which the answer is "neither".

Here you surprise me: I have always seen "prime" exclude invertible
elements!

Snark on #sagemath

[John Cremona]

On 19 August 2013 17:12, Julien Puydt <julien...@laposte.net> wrote:

> Le 19/08/2013 18:09, John Cremona a écrit :
>> This sounds very like the number theory analogue, is 1 prime or
>> composite -- to which the answer is "neither".
>
> Here you surprise me: I have always seen "prime" exclude invertible
> elements!

Read carefully: I said that 1 is not prime and 1 is not composite. I
certainly agree that invertible elements are not prime.

John

>
> Snark on #sagemath

[Julien Puydt]

Le 19/08/2013 18:20, John Cremona a �crit :

> On 19 August 2013 17:12, Julien Puydt <julien...@laposte.net> wrote:

>> Le 19/08/2013 18:09, John Cremona a �crit :

>>> This sounds very like the number theory analogue, is 1 prime or
>>> composite -- to which the answer is "neither".
>>
>> Here you surprise me: I have always seen "prime" exclude invertible
>> elements!
>
> Read carefully: I said that 1 is not prime and 1 is not composite. I
> certainly agree that invertible elements are not prime.

Indeed!

Thanks,

Snark on #sagemath

[Keshav Kini]

John Cremona <john.c...@gmail.com> writes:
> [...] and then you will not have the silly

> situation that (in 5.11)
>
> sage: G = Graph([]); G
> Graph on 0 vertices
> sage: G.is_connected()
> True
> sage: G.connected_components()
> []
> as to me it seems contradictory to have a graph claiming to be
> connected but having no connected components.

Why? A graph is connected iff every pair of vertices is connected, which
is to say that every connected component is the same as every other
connected component (i.e. a uniqueness property). The existence of a
connected component seems to me to be independent from the uniqueness of
a connected component, and so either 0 or 1 connected components should
be admitted.

Anyway, I'm not trying to argue that the empty graph should be
considered connected. Maybe it is more useful to define connectedness by
existence *and uniqueness* of connected components, after all. I like
the nLab wiki link that darij provided in the ticket description [1].
I'm especially tickled by the example, "False is not true" :)

-Keshav

[1] http://ncatlab.org/nlab/show/too+simple+to+be+simple

[John Cremona]

On 19 August 2013 19:26, Keshav Kini <kesha...@gmail.com> wrote:
> John Cremona <john.c...@gmail.com> writes:
>> [...] and then you will not have the silly
>> situation that (in 5.11)
>>
>> sage: G = Graph([]); G
>> Graph on 0 vertices
>> sage: G.is_connected()
>> True
>> sage: G.connected_components()
>> []
>> as to me it seems contradictory to have a graph claiming to be
>> connected but having no connected components.
>
> Why? A graph is connected iff every pair of vertices is connected, which
> is to say that every connected component is the same as every other
> connected component (i.e. a uniqueness property). The existence of a
> connected component seems to me to be independent from the uniqueness of
> a connected component, and so either 0 or 1 connected components should
> be admitted.
>

I was trying to argue against any position based on " my favourite
definition is ... and it satisfies that definition" since the whole
point is that there are many different defintions which agree on
nontrivial cases but give different result for the trivial cases.

If you define a prime number to be an integer with precisely 2 prime
divisors, itself and 1, then you find that the only prime number is
-1.

It seems (to me) much better to decide on an important property which
you want to be true -- such as uniqueness of primes factorizations, or
decompositions into connected components, and use the definition for
trivial objects which is consistent with that.

John

> Anyway, I'm not trying to argue that the empty graph should be
> considered connected. Maybe it is more useful to define connectedness by
> existence *and uniqueness* of connected components, after all. I like
> the nLab wiki link that darij provided in the ticket description [1].
> I'm especially tickled by the example, "False is not true" :)
>
> -Keshav
>
> [1] http://ncatlab.org/nlab/show/too+simple+to+be+simple
>

[Nathann Cohen]

Yooooooooooooo !!

> As you can check here
> http://mathoverflow.net/questions/120536/is-the-empty-graph-a-tree
>
> the big shot guys agree that the empty graph is to be considered
> disconnected. So YES in general, mathematicians appear to be depressed
> persons.....

Come ooooooooooooooooon. It's not funny at all ! Let's just say that
we don't know, and refuse this sterile discussion ! It will be nice to
admit that we don't know what we don't know, for once ! :-P

Nathann

[Andrew Gainer-Dewar]

How about extending the input signature of Graph.is_connected() to
include an option

empty_graph_is_connected = False

? (It could, of course, default to True instead, but I'm an enumeration
guy and think this is nonsense.)

Advantages, as I see them:
* True-ists and False-ists both get their way.
* Novice users of Graph.is_connected() are forced to confront the
problem by the semantics of the method itself.
* Can be configured to not break existing code (although this requires
using the obviously wrong True).
* Reflects the essentially definitional/philosophical nature of the problem.

Disadvantages, as I see them:
* Complicates the semantics of the method.
* Adds a bit of logic.
* Fails to end the philosophical debate—we'd still need to decide what
to set to default!

--Andrew

[Robert Bradshaw]

Is anyone arguing for returning True? If not, let's return False and
put a note about it in the docs.

[Jeroen Demeyer]

On 2013-08-20 23:21, Andrew Gainer-Dewar wrote:
> How about extending the input signature of Graph.is_connected() to
> include an option
>
> empty_graph_is_connected = False

-1 for needless complication.

[Darij Grinberg]

Hi,

On Tuesday, 20 August 2013 23:21:43 UTC+2, Andrew Gainer-Dewar wrote:

How about extending the input signature of Graph.is_connected() to
include an option

    empty_graph_is_connected = False

?

The problem with such a global variable is that is_connected() is used not just by humans, but also by other methods. The authors of those methods don't always know about the global variables affecting the computation; this is what caused the characteristic symmetric function mess in http://trac.sagemath.org/ticket/14885 . And even if they do, it is hard to work around this to obtain reliable behavior; one would have to change the global variable within the computation and then change it back at the end.

  Best regards,
  Darij

[Volker Braun]

+1

[Tom Boothby]

I will argue against False. We've had the convention that
Graph().is_connected() is True for the last n years. This was an
arbitrary (if heedless) choice at the boundary of several definitions.
It doesn't seem to be an undue source of bugs, so the only impact of
changing this arbitrary choice to another arbitrary choice will be to
subtly break backwards-compatibility and add warning noise.

I just consulted NetworkX, and I am convinced that their solution is
the only reasonable change we could make:

if len(G)==0:
raise nx.NetworkXPointlessConcept(
"""Connectivity is undefined for the null graph.""")

[Stefan]

I think backward compatibility is a strong argument to keep returning True.

I also have an answer based on "my favorite definition is ...", namely the analogue with matroid connectivity, where any matroid that is too small to have a k-separation, is automatically k-connected. Extending this to graphs, the empty graph should be infinitely connected.

[Keshav Kini]

I don't think anyone was suggesting a global variable.
empty_graph_is_connected would be a keyword option to is_connected().

-Keshav

[Jakob Kroeker]

I think backward compatibility is a strong argument to keep returning True.

well, there is also the option to deprecate the is_connected() function for the empty graph
and then change the behaviour after a year.

By the way, what about defining that the empty graph is connected AND disconnected.
( I'm joking :-) )

But seriously, 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...

Jakob

[kcrisman]

On Saturday, July 9, 2016 at 12:37:15 PM UTC-4, Jakob Kroeker wrote:

I think backward compatibility is a strong argument to keep returning True.

well, there is also the option to deprecate the is_connected() function for the empty graph
and then change the behaviour after a year.

By the way, what about defining that the empty graph is connected AND disconnected.
( I'm joking :-) )

Why not?  A set can be open and closed :-) which is a perfect occasion to recall the hilarious (if not quite SFW):

https://www.youtube.com/watch?v=SyD4p8_y8Kw