Opened 6 years ago

Closed 6 years ago

Graphs: docstring of _add_ conflicts with function

Reported by: Owned by: jmantysalo major sage-7.2 graph theory dcoudert, mcognetta Jori Mäntysalo David Coudert N/A 2efa40a 2efa40a0db33ddc50ab076a86a22ead8680eec09

Description

`(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.

comment:1 Changed 6 years ago by jmantysalo

• Status changed from new to needs_info

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).

comment:2 follow-up: ↓ 7 Changed 6 years ago by 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.

comment:3 Changed 6 years ago by jmantysalo

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.

comment:4 Changed 6 years ago by dcoudert

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.

comment:7 in reply to: ↑ 2 ; follow-up: ↓ 9 Changed 6 years ago by mcognetta

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.

comment:9 in reply to: ↑ 7 Changed 6 years ago by jmantysalo

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.

comment:11 Changed 6 years ago by jmantysalo

• Commit set to f05cd3f63f07dc35f913444d0e60cd3546321191
• Status changed from needs_info to needs_review

New commits:

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

comment:12 Changed 6 years ago by jmantysalo

• Authors set to Jori Mäntysalo

comment:13 follow-up: ↓ 15 Changed 6 years ago by dcoudert

• Reviewers set to David Coudert
• Status changed from needs_review to needs_work
• "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))`.

comment:14 Changed 6 years ago by git

• Commit changed from f05cd3f63f07dc35f913444d0e60cd3546321191 to 44e539e9c85793a3cfefaa8929a370ef28da5789

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

 ​44e539e `Added tests etc.`

comment:15 in reply to: ↑ 13 Changed 6 years ago by jmantysalo

• Status changed from needs_work to needs_review

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.

comment:16 Changed 6 years ago by dcoudert

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.

comment:17 Changed 6 years ago by git

• Commit changed from 44e539e9c85793a3cfefaa8929a370ef28da5789 to 2efa40a0db33ddc50ab076a86a22ead8680eec09

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

 ​2efa40a `Python3 compliance.`

comment:18 Changed 6 years ago by jmantysalo

OK, done that.

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

comment:19 Changed 6 years ago by dcoudert

• Status changed from needs_review to positive_review

The patch is good to go. Thanks, David.