Graphs: docstring of _add_ conflicts with function

[jm58660]

(Graph({'a': []})+Graph({'b': []})).vertices() gives [0, 1], but docstring of __add__ says "If there are common vertices to both, they will be renamed." I do not know which way it should be.

Also there is no error checking, so Graph({0:[]})+'junk' does and returns nothing.

CC: @dcoudert @sagetrac-mcognetta

Component: graph theory

Author: Jori Mäntysalo

Branch/Commit: 2efa40a

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/20499

[jm58660]

comment:1

David, a question. How should this function work?

• Not at all, remove this.
• As now, i.e. always relabel to integers.
• Keep vertices, raise exception if there is a common vertex.
• Keep vertices, do like union() does.
• Keep vertices, but relabel common ones (like the docstring now says).

[dcoudert]

comment:2

The current implementation of the add method is

        if isinstance(other_graph, GenericGraph):
            return self.disjoint_union(other_graph, labels='integers')

So it forces to relabel vertices as integer in [0..n-1].

At the least, we should raise an error for cases such as Graph({0:[]})+'junk'. Indeed, the other ordering raises an error

sage: 'junk'+Graph({0:[]})
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-99-2e66a308aaff> in <module>()
----> 1 'junk'+Graph({Integer(0):[]})

TypeError: cannot concatenate 'str' and 'Graph' objects

Now, the semantic of + is the disjoint union, and I believe this is the right choice.
We should however ensure that the doc of __add__, disjoint_union, union, __mul__ and may be join, are clear enough and without ambiguity for users.

Concerning the relabel to integers part, I agree that this is often painful. We could propose and intermediate behavior like: relabel only if some vertices have same label. But again some people will complain.

David.

[jm58660]

comment:3

It seems that example given uses consecutive integeres. But yes, your suggestions sounds reasonable. But now I see this:

sage: G = Graph({'a': ['b']})
sage: G
Graph on 2 vertices
sage: G+G
 disjoint_union : Graph on 4 vertices
sage: H = graphs.CycleGraph(3)
sage: H
Cycle graph: Graph on 3 vertices
sage: H+H
Cycle graph disjoint_union Cycle graph: Graph on 6 vertices

Maybe the __str__ needs modification also.

[dcoudert]

comment:4

Right, we could improve the naming part of disjoint_union. Currently it is:

        G._name = '%s disjoint_union %s'%(self.name(), other.name())

I just saw that there is a deprecation warning in disjoint_union. See #17053.
So some decisions have already been taken on how to relabel vertices.

[jm58660]

comment:5

Should I open a discussion about this in sage-devel?

[dcoudert]

comment:6

That's a good idea.
At least, interested people could add comments here.

[sagetrac-mcognetta]

comment:7

Replying to @dcoudert:

The current implementation of the add method is

        if isinstance(other_graph, GenericGraph):
            return self.disjoint_union(other_graph, labels='integers')

So it forces to relabel vertices as integer in [0..n-1].

At the least, we should raise an error for cases such as Graph({0:[]})+'junk'. Indeed, the other ordering raises an error

sage: 'junk'+Graph({0:[]})
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-99-2e66a308aaff> in <module>()
----> 1 'junk'+Graph({Integer(0):[]})

TypeError: cannot concatenate 'str' and 'Graph' objects

Now, the semantic of + is the disjoint union, and I believe this is the right choice.
We should however ensure that the doc of __add__, disjoint_union, union, __mul__ and may be join, are clear enough and without ambiguity for users.

Concerning the relabel to integers part, I agree that this is often painful. We could propose and intermediate behavior like: relabel only if some vertices have same label. But again some people will complain.

David.

I like the idea of only relabeling (the entire graph) if there are common vertices. NetworkX automatically relabels everything to integers when adding graphs and they get along fine without people complaining. We could possibly think about doing something with recording the previously named values when relabeling them. That way people could choose to invert the labeling if it was really necessary. Our add function could pass in a dictionary of the previous labels as an attribute in the newly created graph.
In the end, I think that relabeling to integers is best. If people know they need to preserve vertex names, they can take precautions beforehand.

[jm58660]

comment:9

Replying to @sagetrac-mcognetta:

In the end, I think that relabeling to integers is best. If people know they need to preserve vertex names, they can take precautions beforehand.

OK for me. Then it would be like .disjoint_union(other, labels=’integers’). Current behaviour would be maintained, so there is no need for a deprecation. Should disjoint_union have an option to get really direct union (and raise an exception it graphs have common vertices)? If not, I will add an example like we now have for disjoint union of posets.

And then there is the naming thing.

But first I will wait for three days to see if there will be opinions against this.

[jm58660]

Branch: u/jmantysalo/graphs__docstring_of__add__conflicts_with_function

[jm58660]

New commits:

7387997	graph `__add__` error checking etc.
f05cd3f	Remove a space

[jm58660]

Commit: f05cd3f

[jm58660]

Author: Jori Mäntysalo

[dcoudert]

comment:13

• "Labels of the resultin" -> "Labels of the resulting"
• a doctest is needed for the TypeError case of the __add__ method.
• the error message could be improved, for instance to something similar to

sage: 1+'a'
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: unsupported operand parent(s) for '+': 'Integer Ring' and '<type 'str'>'

We could using something like that, which is valid for both Graph and DiGraph.

raise TypeError("adding a '{}' and a '{}' is not defined".format(typeof(self),typeof(other))

• I'm not fully aware of python3 syntax, but I suggest to avoid using G._name = '%s disjoint_union %s'%(a, b) and to prefer G._name = '{} disjoint_union {}'.format(a, b). Well actually this is certainly more robust: G.name('{} disjoint_union {}'.format(a, b)).

[dcoudert]

Reviewer: David Coudert

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

44e539e

Added tests etc.

[sagetrac-git]

Changed commit from f05cd3f to 44e539e

[jm58660]

comment:15

Replying to @dcoudert:

I didi three changes as you suggested.

• I'm not fully aware of python3 syntax, but I suggest to avoid using G._name = '%s disjoint_union %s'%(a, b) and to prefer G._name = '{} disjoint_union {}'.format(a, b). Well actually this is certainly more robust: G.name('{} disjoint_union {}'.format(a, b)).

This will give an error: immutable graph can not change name. I suggest we keep this as it is now and think about this later.

[dcoudert]

comment:16

The error message is confusing since the order of types is the reverse of the one used in the operation.

+            sage: G+42
+            Traceback (most recent call last):
+            ...
+            TypeError: adding a <type 'sage.rings.integer.Integer'> to a <class 'sage.graphs.graph.Graph'> is not defined

I was not aware of the problem with immutable graphs. So ok to assign directly to G._name.
However, you should replace G._name = '%s disjoint_union %s'%(a, b) with G._name = '{} disjoint_union {}'.format(a, b).
Some people are actively working on making sage python3 compliant. No need to add extra work.

[sagetrac-git]

Changed commit from 44e539e to 2efa40a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2efa40a

Python3 compliance.

[jm58660]

comment:18

OK, done that.

(But I think that naming question should be considered later. Maybe the design can be made better.)

[dcoudert]

comment:19

The patch is good to go.
Thanks,
David.

[vbraun]

Changed branch from u/jmantysalo/graphs__docstring_of__add__conflicts_with_function to 2efa40a