Opened 3 years ago

Closed 3 years ago

#20499 closed defect (fixed)

Graphs: docstring of _add_ conflicts with function

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.2
Component: graph theory Keywords:
Cc: dcoudert, mcognetta Merged in:
Authors: Jori Mäntysalo Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 2efa40a (Commits) Commit: 2efa40a0db33ddc50ab076a86a22ead8680eec09
Dependencies: Stopgaps:

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.

Change History (20)

comment:1 Changed 3 years ago by jmantysalo

  • Cc dcoudert added
  • 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: Changed 3 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 3 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 3 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:5 Changed 3 years ago by jmantysalo

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

comment:6 Changed 3 years ago by dcoudert

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

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

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.

comment:8 Changed 3 years ago by mcognetta

  • Cc mcognetta added

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

Replying to 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.

comment:10 Changed 3 years ago by jmantysalo

  • Branch set to u/jmantysalo/graphs__docstring_of__add__conflicts_with_function

comment:11 Changed 3 years ago by jmantysalo

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

New commits:

7387997graph __add__ error checking etc.
f05cd3fRemove a space

comment:12 Changed 3 years ago by jmantysalo

  • Authors set to Jori Mäntysalo

comment:13 follow-up: Changed 3 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 3 years ago by git

  • Commit changed from f05cd3f63f07dc35f913444d0e60cd3546321191 to 44e539e9c85793a3cfefaa8929a370ef28da5789

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

44e539eAdded tests etc.

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

  • Status changed from needs_work to needs_review

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.

comment:16 Changed 3 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 3 years ago by git

  • Commit changed from 44e539e9c85793a3cfefaa8929a370ef28da5789 to 2efa40a0db33ddc50ab076a86a22ead8680eec09

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

2efa40aPython3 compliance.

comment:18 Changed 3 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 3 years ago by dcoudert

  • Status changed from needs_review to positive_review

The patch is good to go. Thanks, David.

comment:20 Changed 3 years ago by vbraun

  • Branch changed from u/jmantysalo/graphs__docstring_of__add__conflicts_with_function to 2efa40a0db33ddc50ab076a86a22ead8680eec09
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.