Opened 7 weeks ago

Last modified 12 days ago

#27408 needs_review enhancement

Edge view for graphs

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.8
Component: graph theory Keywords:
Cc: nthiery Merged in:
Authors: David Coudert Reviewers:
Report Upstream: N/A Work issues:
Branch: public/27408_edgeview (Commits) Commit: 96d87bb88cf274a8526e61779b23461027a1b1fa
Dependencies: Stopgaps:

Description

This ticket implements an edge view for graphs, as discussed in #22349 and in this message.

An edge view is a read-only iterable container of edges enabling operations like for e in E and e in E. In can be iterated multiple times. Checking membership is done in constant time. It avoids the construction of edge lists and so consumes little memory.

Change History (79)

comment:1 follow-up: Changed 7 weeks ago by dcoudert

  • Branch set to public/27408_edgeview
  • Commit set to 01579875c3b76eaf76421decbdc89c4fde53793a
  • Status changed from new to needs_review

This is a first draft of an EdgeView. I tried to combined the flexibility offered by the parameters of .edges() and .edge_iterator(). I have not tested it with Python3 yet, only with Python2 to understand the impact and what should be fixed.

Feedback is more than welcome, for instance concerning:

  • Is the location OK or should we move it another file ?
  • Should it be in Cython ?
  • how to make next(E) ?
  • should we add the option to call E[i] to get the ith edge, even if it's slow ?

New commits:

fc42aa0trac #27408: first trial of edge view
79b426btrac #27408: fix doctests in views.py
0e4961btrac #27408: fix issues in graph module
0157987trac #27408: fix issues in other modules

comment:2 follow-up: Changed 7 weeks ago by vdelecroix

I think having this separate views.py file is perfect. Also, prototyping is much easier in Python and the Cython phase should be kept for a later ticket.

In Python there is a difference between an iterator (what you obtain with iter(X) and on which you can apply next) and an iterable (something on which iter(X) make sense). It is dangerous to have an object that is doing both (e.g. when X is an iterator iter(X) returns X itself). EdgeView is definitely an iterable. I would simply disallow next(E) similarly to

sage: next([0,1,2])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-1-21b4c4a0c628> in <module>()
----> 1 next([Integer(0),Integer(1),Integer(2)])

TypeError: list object is not an iterator

comment:3 follow-up: Changed 7 weeks ago by dcoudert

OK. We can still do next(iter(E)) to get first edge if needed.

We can certainly also replace edge_iterator by the EdgeView, but this can induce a small slow down.

I have also create a class VertexView currently raising NotImplementedError. I'm not sure if it's needed.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 7 weeks ago by vdelecroix

Replying to dcoudert:

OK. We can still do next(iter(E)) to get first edge if needed.

The various combinatorial sets in sage implements .first() and .last().

sage: Partitions(5).first()
[5]
sage: Partitions(5).last()
[1, 1, 1, 1, 1]

We can certainly also replace edge_iterator by the EdgeView, but this can induce a small slow down.

To avoid slowdown there are several possibilities:

  • cache the edge view of the whole graph
  • have a pool of edge views to avoid creating the objects

I have also create a class VertexView currently raising NotImplementedError. I'm not sure if it's needed.

Then remove it for now. I think that there are enough troubles introducing this EdgeView.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 7 weeks ago by vdelecroix

Replying to vdelecroix:

Replying to dcoudert:

We can certainly also replace edge_iterator by the EdgeView, but this can induce a small slow down.

To avoid slowdown there are several possibilities:

  • cache the edge view of the whole graph

Actually, the above makes sense if you want the following to be fast

sage: (0,3) in G.edges()

(Am I right that G.edges() would return the view?)

comment:6 in reply to: ↑ 5 Changed 7 weeks ago by dcoudert

The various combinatorial sets in sage implements .first() and .last().

.first() is easy, but .last() requires to iterate over all edges.

Actually, in the current implementation, when sort=True, we store a sorted list of edges. So getting the last one becomes easy. But when sort=False, we have to iterate. Furthermore, as the view is updated as the graph, we cannot store first/last edge.

  • cache the edge view of the whole graph

I don't know how to do that...

(Am I right that G.edges() would return the view?)

Yes.

comment:7 Changed 7 weeks ago by git

  • Commit changed from 01579875c3b76eaf76421decbdc89c4fde53793a to 5cf8344cd92ff982bae5644340644556b0788ab5

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

5cf8344trac #27408: various corrections

comment:8 Changed 7 weeks ago by vdelecroix

Why the attributes graph, directed, etc of EdgeView do not start with underscore? With this version they would appear in the tab-completion which is not desirable.

The sorted function does not need a list as input. Replace sorted(list(edges), ...) with sorted(edges, ...).

Why do you store the directed attribute in EdgeView?

What I mean by cache is that the graph class could have a _edge_view attribute which is initialized with EdgeView(self) in Graph.__init__. Even if edges are added to the graph the edge view is magically updated (though you need to remove the directed attribute). It might even make sense to have two versions: _edge_view and _edge_view_unlabelled.

comment:9 Changed 7 weeks ago by jdemeyer

You want this to be fast. I would certainly do this in Cython.

comment:10 Changed 7 weeks ago by jdemeyer

I think it should be called EdgesView (plural): you're making a view of all edges, not one particular edge.

comment:11 Changed 7 weeks ago by git

  • Commit changed from 5cf8344cd92ff982bae5644340644556b0788ab5 to b3f6f4b5dae864c21afd0aadc8c416326a2a1003

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

b3f6f4btrac #27408: start internal variables with _

comment:12 Changed 7 weeks ago by jdemeyer

Again for performance, this should be as low-level as possible so I would drop the inheritance from SageObject.

comment:13 in reply to: ↑ 2 Changed 7 weeks ago by jdemeyer

Replying to vdelecroix:

the Cython phase should be kept for a later ticket.

I disagree here. I would agree with you if we would be adding a completely new feature. But here, we are changing an existing feature (namely edges()). So we don't want this to become slower than before.

comment:14 Changed 7 weeks ago by jdemeyer

What do you think of this proposal from #22349?

  1. Make the default sort=None. In this case, give a deprecation warning and try to sort but fail gracefully if the input is not sortable.
  1. If sort=True is given, always sort (raising an exception if the sorting failed)
  1. If sort=False is given, never sort.

comment:15 Changed 7 weeks ago by jdemeyer

  • Status changed from needs_review to needs_work

I'm not going to insist on the cythonization, but I'd like to hear the opinion from others on this ticket.

Last edited 7 weeks ago by jdemeyer (previous) (diff)

comment:16 in reply to: ↑ 1 Changed 7 weeks ago by jdemeyer

Replying to dcoudert:

  • should we add the option to call E[i] to get the ith edge, even if it's slow ?

I would say yes, since the old edges() had that functionality.

comment:17 Changed 7 weeks ago by jdemeyer

I also suggest to keep the interface as simple as possible. For example, for the vertices argument, I would support only None and a list (and not: a single vertex).

I also wouldn't do True if labels else False. Just write labels and assume that people don't give funny arguments for labels.

To check for a key function, use key is not None instead of key.

comment:18 Changed 7 weeks ago by jdemeyer

In various places, you are replacing calls to edges() by edge_iterator().

That looks like a backwards change: isn't the eventual goal to deprecate edge_iterator() and replace it by edges(), similarly to how itervalues() was deprecated in favor of values() in Python?

comment:19 Changed 7 weeks ago by jdemeyer

Cython allows you to use yield from, so you could implement __iter__ as

        if self._sort_edges:
            yield from sorted(self, key=self._sort_edges_key)
        elif self._graph._directed:
            yield from self._graph._backend.iterator_out_edges(self._vertices, self._labels)
            if self._ignore_direction:
                yield from self._graph._backend.iterator_in_edges(self._vertices, self._labels)
        else:
            yield from self._graph._backend.iterator_edges(self._vertices, self._labels)

which I find easier to read and it's probably more efficient too.

comment:20 Changed 7 weeks ago by jdemeyer

Overall, I think that this is a good change. I would like to see some more compatibility added with the old list return type for edges(), in particular implementing __getitem__. You could also consider __add__ and __mul__.

comment:21 follow-ups: Changed 7 weeks ago by dcoudert

Some quick answers (cannot work on it now):

  • networkx defines EdgeView and not EdgesView (see here), but we can decide to use plural
  • change of .edges() to .edge_iterator(). I agree that it's not necessary. We can revert these changes. Also, I combined parameters of existing .edges and .edge_iterator methods to be able to get a unique method with more options. We could certainly extend the tool to also do .edges_incident() and .edge_boundary(), but in another ticket.
  • I agree with the proposal for sort #comment:14, but we will have to check in many places if sorted is required or not.
  • labels. I have this bad habit that I'm trying to correct to write labels=0... that's why I offered some flexibility to users. But of course we can be strict.
  • __add__ and __mul__. What could be a smart way to do that ? It's easy to return a list of edges, but a EdgeView ?
  • and of course switch to Cython.

comment:22 in reply to: ↑ 21 Changed 7 weeks ago by jdemeyer

Replying to dcoudert:

  • labels. I have this bad habit that I'm trying to correct to write labels=0... that's why I offered some flexibility to users.

But do you expect users to call EdgeView directly? I consider the edges() method the high-level interface, where you can be flexible. On the other hand, EdgeView should be as fast and simple as possible.

comment:23 in reply to: ↑ 21 Changed 7 weeks ago by jdemeyer

Replying to dcoudert:

  • __add__ and __mul__. What could be a smart way to do that ? It's easy to return a list of edges, but a EdgeView ?

I wouldn't mind to return a list here. It's not very elegant, but it's good for backwards compatibility.

comment:24 Changed 7 weeks ago by git

  • Commit changed from b3f6f4b5dae864c21afd0aadc8c416326a2a1003 to 5ba0c3fa4b856e98aad4bbecf74c28db9e795973

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

367534ftrac #27408: move to Cython file
c68e5d1trac #27408: rename EdgesView and revert some edges/edge_iterator
5f9cae8trac #27408: use yield from in __iter__
5ba0c3ftrac #27408: add __mul__, __rmul__, __getitem__, __add__

comment:25 follow-up: Changed 7 weeks ago by dcoudert

I have implemented some of our wishlist. It remains to deal with

  • labels
  • sort
  • sublist query like G.edges()[:-2]. What's the name ?
  • try to replace .edge_iterator()
  • make sure it works with Python 3

comment:26 in reply to: ↑ 25 ; follow-up: Changed 7 weeks ago by vdelecroix

Replying to dcoudert:

I have implemented some of our wishlist. It remains to deal with

  • labels
  • sort
  • sublist query like G.edges()[:-2]. What's the name ?

This is also __getitem__. The call X.[a:b:c] is transformed into X.__getitem__(slice(a,b,c)). You can do something as simple as

def __getitem__(self, i):
    if isinstance(i, slice):
        return list(self).__getitem__(i)

(or possibly be a little bit smarter using islice from itertools).

  • try to replace .edge_iterator()
  • make sure it works with Python 3

comment:27 Changed 7 weeks ago by git

  • Commit changed from 5ba0c3fa4b856e98aad4bbecf74c28db9e795973 to d9736595c4bac3224a0afb8394d25e1965c82e4a

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

d973659trac #27408: better getitem and various fix

comment:28 Changed 7 weeks ago by git

  • Commit changed from d9736595c4bac3224a0afb8394d25e1965c82e4a to 711be0b9788a32164f83dadb287ec5c8333b0f0f

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

711be0btrac #27408: set default sort to None by default and add deprecation warning

comment:29 Changed 7 weeks ago by dcoudert

  • for slice queries, I have not use islice as it returns an iterator. The compatibility with current behavior is list. We can change that in the future
  • I implemented the proposal of Jeroen for sorting. Well, the "fail gracefully" is not clear to me.

it remains to

  • try to replace .edge_iterator() -- I tried and it breaks too many things. Could be done in another ticket, replacing calls be .edges and adding a deprecation warning to .vertex_iterator
  • make sure it works with Python 3
  • certainly try to speed up the beast
Last edited 7 weeks ago by dcoudert (previous) (diff)

comment:30 Changed 7 weeks ago by vdelecroix

Since you know how many edges there are it is easy to implement E[-3] without creating the list (though I have no idea whether it has any proper use case).

Concerning slices, I never suggested to return islice but to use it. More explicitely

if isinstance(i, slice):
    return list(islice(self, i.start, i.stop, i.end)))

The above avoids creating the list of all edges (at least when b is positive which can always be done since you know the length). You will notice the difference if you do E[:10] on a huge graph.

comment:31 Changed 7 weeks ago by vdelecroix

I think that it would be good to replace some occurrences of .edge_iterator and identify what is the source of breakage.

comment:32 Changed 7 weeks ago by git

  • Commit changed from 711be0b9788a32164f83dadb287ec5c8333b0f0f to a1701f80d0a80c7a94a7407b6952e23fa1025e76

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

a1701f8trac #27408: some care for Python 3

comment:33 follow-up: Changed 7 weeks ago by dcoudert

I fixed various issues for Python3 to avoid introducing new issues.

  • We know the length if and only if vertices = None. Otherwise we have to count edges. I tried using islice without success. Got AttributeError: 'slice' object has no attribute 'end'...
  • for .edge_iterator, we have many calls to next(...). We have to change each of them and may be other stuff.

comment:34 in reply to: ↑ 33 Changed 7 weeks ago by vdelecroix

Replying to dcoudert:

I fixed various issues for Python3 to avoid introducing new issues.

  • We know the length if and only if vertices = None. Otherwise we have to count edges. I tried using islice without success. Got AttributeError: 'slice' object has no attribute 'end'...

Sorry, the attributes are start, stop, step. When you know the length you can use the method indices of the slice to find out the (correctly bounded) start, stop, step as in

sage: slice(1, -1, 2).indices(23)
(1, 22, 2)

See https://docs.python.org/2/library/functions.html#slice

comment:35 in reply to: ↑ 26 Changed 7 weeks ago by jdemeyer

Replying to vdelecroix:

You can do something as simple as

def __getitem__(self, i):
    if isinstance(i, slice):
        return list(self).__getitem__(i)

...except that the line should be written as return list(self)[i]. There is almost never a need to call special methods like __getitem__ directly (although one exception is super() calls).

comment:36 Changed 7 weeks ago by git

  • Commit changed from a1701f80d0a80c7a94a7407b6952e23fa1025e76 to 890530982e496ddd4b893eb616bfe8c1c8e888ab

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

8905309trac #27408: improve getitem

comment:37 Changed 7 weeks ago by dcoudert

According to the documentation of islice, it needs non negative parameters. Thus I tried to combine use of islice and list()[i].

Last edited 7 weeks ago by dcoudert (previous) (diff)

comment:38 Changed 7 weeks ago by git

  • Commit changed from 890530982e496ddd4b893eb616bfe8c1c8e888ab to e27645bffae04b1b04e39efe41a19e6ac85e5193

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

e27645btrac #27408: it's .step, not .end

comment:39 Changed 7 weeks ago by git

  • Commit changed from e27645bffae04b1b04e39efe41a19e6ac85e5193 to 8d7bd05b4a60909cc1bf694dc8990fe3d9cae4c2

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

8d7bd05trac #27408: better like that

comment:40 Changed 7 weeks ago by git

  • Commit changed from 8d7bd05b4a60909cc1bf694dc8990fe3d9cae4c2 to 132284fc54db27855167d6643fa009340067f218

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

132284ftrac #27408: correction of len

comment:41 Changed 7 weeks ago by dcoudert

To replace .edge_iterator, we must be able to call next(...) on EdgesView. Some algorithms use this functionality. The trivial solution is to use it = iter(E), but there is certainly a smarter solution.

comment:42 Changed 7 weeks ago by dcoudert

  • Status changed from needs_work to needs_review

comment:43 Changed 6 weeks ago by vdelecroix

I read the sentence the graph should not be updated while iterating through a view. Note that the following behavior for sets

sage: s = set([1,2])
sage: for i in s:
....:     print(i)
....:     s.add(3*i)
Traceback (most recent call last):
...
RuntimeError: Set changed size during iteration

comment:44 Changed 6 weeks ago by vdelecroix

self.__mul__(n) -> self * n

comment:45 Changed 6 weeks ago by git

  • Commit changed from 132284fc54db27855167d6643fa009340067f218 to bbbb824d1535e76d5ae28ff22f679c8991ddfdf2

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

529419btrac #27408: Merged with 8.7.beta7
bbbb824trac #27408: fix __mul__

comment:46 follow-up: Changed 6 weeks ago by dcoudert

I fixed __mul__.

For sets, we also have this.

sage: s = set([1,2])
sage: for i in s:
....:     print(i)
....:     s.add(i*3)
....:     s.discard(i)
....:     
1
2
3
6

comment:47 in reply to: ↑ 46 Changed 6 weeks ago by vdelecroix

Replying to dcoudert:

I fixed __mul__.

For sets, we also have this.

sage: s = set([1,2])
sage: for i in s:
....:     print(i)
....:     s.add(i*3)
....:     s.discard(i)
....:     
1
2
3
6

Ouch.

comment:48 Changed 6 weeks ago by dcoudert

  • Cc nthiery added

@Nicolas: this ticket implements your proposal of an view for edges. Any comment / suggestion for improvements is more than welcome ;)

comment:49 Changed 4 weeks ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:50 Changed 2 weeks ago by git

  • Commit changed from bbbb824d1535e76d5ae28ff22f679c8991ddfdf2 to 95322eb2ad828053b869bc077c07c07d0f2da1e8

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

95322ebtrac #27408: fix merge conflict

comment:51 Changed 2 weeks ago by dcoudert

rebase and fix merge conflict with 8.8.beta1

comment:52 Changed 2 weeks ago by jdemeyer

17 hasn't been addressed. Was that intentional or did you just forget about it?

comment:53 Changed 2 weeks ago by jdemeyer

To better explain what I meant with 17: I would try to keep the logic in EdgesView.__init__ as simple as possible and move some of the argument handling (like replacing a single vertex by a 1-element list) to GenericGraph.edges().

comment:54 follow-up: Changed 2 weeks ago by jdemeyer

Various comments about views.pyx:

  1. Instead of class EdgesView():, I suggest a Cython class cdef class EdgesView: (dropping the empty tuple since that looks strange to me). This requires explicitly declaring attributes but it will be faster. It also requires merging __mul__ and __rmul__.
  1. <int>i is not correct (the correct cast is <Py_ssize_t>) and not needed (Cython should do the type conversion automatically): just replace <int>i by i.
  1. I personally dislike code of the form
                try:
                    yield from sorted(self, key=self._sort_edges_key)
                except Exception as msg:
                    raise TypeError("the edges cannot be sorted due to " + msg)
    

just keep the original exception, drop the try/except.

  1. The proper way to deal with unknown types in __eq__, __add__ and friends is to return NotImplemented.
  1. In __mul__, drop the check for n < 1, leave that to list.
  1. It would be good to implement __bool__ too (for checking non-emptyness).

comment:55 Changed 2 weeks ago by git

  • Commit changed from 95322eb2ad828053b869bc077c07c07d0f2da1e8 to 7287f14b26832c0958fe1a4d8024909724085d1a

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

0aa8c01trac #27408: avoid vertices=single vertex
7287f14trac #27408: most reviewers comment #54

comment:56 follow-ups: Changed 2 weeks ago by dcoudert

I have not (yet) done the change cdef class EdgesView: as I don't know how to properly define the types of the variables.

  • _vertices can be list, and then we have to handle empty list case instead of assigning G
  • _vertex_set is frozenset
  • _labels is boolean, but it prevents None
  • _sort_edges is a boolean
  • _sort_edges_key is a function. What's the appropriate type ?

Also, I did not get how to merge __mul__ and __rmul__. Any pointer is welcome.

comment:57 in reply to: ↑ 56 Changed 2 weeks ago by jdemeyer

With the info that you provided, it should be

  • _labels is boolean, but it prevents None

Why should it be None? Isn't it just a boolean?

comment:58 in reply to: ↑ 56 Changed 2 weeks ago by jdemeyer

Replying to dcoudert:

  • _vertices can be list, and then we have to handle empty list case instead of assigning G

Or you could use _vertices = None to represent that case.

comment:59 in reply to: ↑ 56 Changed 2 weeks ago by jdemeyer

Replying to dcoudert:

Also, I did not get how to merge __mul__ and __rmul__. Any pointer is welcome.

https://cython.readthedocs.io/en/latest/src/userguide/special_methods.html#arithmetic-methods

comment:60 in reply to: ↑ 54 ; follow-up: Changed 2 weeks ago by dcoudert

Replying to jdemeyer:

Various comments about views.pyx:

  1. Instead of class EdgesView():, I suggest a Cython class cdef class EdgesView: (dropping the empty tuple since that looks strange to me). This requires explicitly declaring attributes but it will be faster.

With the current implementation of __eq__, we must access the variables of other. The only solution I see is to declare the class in views.pxd and to explicitly declare the members, i.e., make all members public. Is that the only solution or there is a smarter solution ?

comment:61 Changed 2 weeks ago by git

  • Commit changed from 7287f14b26832c0958fe1a4d8024909724085d1a to 38cdcedfa0401260abb147e02bd95e7b39aa1854

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

38cdcedtrac #27408: cdef class EdgesView

comment:62 Changed 2 weeks ago by dcoudert

Using readonly on some class members allow to fix __eq__. This way, the required members are available in Python-space, but only for reading. documentation

I think I have now implemented all comments/suggestions. I don't know what else we can do to speed up the code. Anyway, thank you for your help.

comment:63 in reply to: ↑ 60 Changed 2 weeks ago by jdemeyer

First of all, making the attributes readonly is a good idea anyway. There is no reason why they should only be accessible from Cython.

Second, the correct way to deal with __eq__ (or really any other place where you do a type check for EdgesView) is to write code as follows:

def __eq__(self, right):
    if not isinstance(right, EdgesView):
        return NotImplemented
    other = <EdgesView>right

This way, Cython knows that other is an instance of EdgesView and it will use optimized access to the cdef attributes. Otherwise, Cython accesses those attributes as Python attributes, which is must slower (and requires readonly or public).

comment:64 Changed 2 weeks ago by git

  • Commit changed from 38cdcedfa0401260abb147e02bd95e7b39aa1854 to 2fa2823e1b36e066ebecd6b4265b48a0af2a263c

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

2fa2823trac #27408: improve __eq__

comment:65 Changed 2 weeks ago by dcoudert

I didn't know that. It's really tricky.

comment:66 Changed 2 weeks ago by jdemeyer

Yes, Cython is 95% like Python but that 5% is what makes it tricky.

comment:67 Changed 2 weeks ago by jdemeyer

Some more comments:

  1. Moving the handling of sort=None to GenericGraph (in line with 17)
  1. self._sort_edges = False if sort is False else True should be simply self._sort_edges = sort then (since _sort_edges is declared bint, Cython automatically does the conversion to bool)
  1. self._graph = <GenericGraph_pyx>G is very dangerous as no type check is done. Replace this by self._graph = <GenericGraph_pyx?>G which is the same, except that an exception is raised by Cython if G is not an instance of GenericGraph_pyx.
  1. Use def __add__(left, right) instead of def __add__(self, other) since using the name self here is potentially confusing. Same for __mul__.
  1. I have some doubts about start, stop, step = i.start or 0, i.stop or sys_maxsize, i.step or 1 but I'll need to check precise slice behavior.

comment:68 Changed 2 weeks ago by git

  • Commit changed from 2fa2823e1b36e066ebecd6b4265b48a0af2a263c to 74219866a2d11f535d35c611930cb7c5a3f30197

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

7421986trac #27408: further improvements

comment:69 Changed 2 weeks ago by dcoudert

I treated 1-4.

for slice, I followed the suggestion at https://docs.python.org/3/library/itertools.html#itertools.islice, but I agree it's not so clear.

comment:70 follow-up: Changed 2 weeks ago by jdemeyer

This should return NotImplemented:

        if not isinstance(right, EdgesView):
            raise TypeError('right is not a EdgesView')

comment:71 Changed 2 weeks ago by git

  • Commit changed from 74219866a2d11f535d35c611930cb7c5a3f30197 to 4e8684663116fc45a1d402a22b1b44977c1a8db6

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

4e86846trac #27408: return NotImplemented

comment:72 Changed 2 weeks ago by jdemeyer

I don't quite like this code:

        if self._sort_edges is True:
            self._sort_edges = False
            yield from sorted(self, key=self._sort_edges_key)
            self._sort_edges = True
        elif self._sort_edges is None:
            self._sort_edges = False
            yield from sorted(self)
            self._sort_edges = True

First of all, the condition should be if self._sort_edges:, dropping the None case. Second, mutating _sort_edges like this looks dangerous: what if the iteration is interrupted for example? Two alternatives:

  1. Create a new EdgesView with sorted=False and use that to iterate.
  1. Factor out the iteration-without-sorting to a separate method and call that from __iter__.

comment:73 in reply to: ↑ 70 Changed 2 weeks ago by jdemeyer

Replying to jdemeyer:

This should return NotImplemented:

        if not isinstance(right, EdgesView):
            raise TypeError('right is not a EdgesView')

Actually, looking better at __add__, you're not really assuming anything about the types of left and right, only that they are iterable. So why not just drop the condition completely and allow any iterable for left and right? That would also solve the case list + EdgesView for example.

comment:74 Changed 2 weeks ago by git

  • Commit changed from 4e8684663116fc45a1d402a22b1b44977c1a8db6 to 5044e460c8ab0841404a5e097b19d1811cc49593

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

578315etrac #27408: better iterator over edges
5044e46trac #27408: more tests in __add__

comment:75 Changed 2 weeks ago by dcoudert

  • for the iterator, I added a method to iterate unsorted edges. This is cleaner now.
  • for __add__, I tried to drop tests and got
    File "src/sage/graphs/views.pyx", line 628, in sage.graphs.views.EdgesView.__add__
    Failed example:
        E + 'foo'
    Expected:
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand type(s) for +: 'sage.graphs.views.EdgesView' and 'str'
    Got:
        [(0, 1, None),
         (0, 2, None),
         (1, 3, None),
         (2, 3, None),
         (2, 4, None),
         (3, 4, None),
         'f',
         'o',
         'o']
    
    So I added a test on left.

comment:76 Changed 12 days ago by jdemeyer

This is twice the same condition :-)

if not isinstance(right, EdgesView) or not isinstance(right, EdgesView):

comment:77 follow-up: Changed 12 days ago by jdemeyer

For __add__, I really meant allowing EdgesView + list. Otherwise, EdgesView + EdgesView works but EdgesView + EdgesView + EdgesView does not. That would be strange. So, if you want to keep the condition, you should check for isinstance(..., (list, EdgesView)).

For the deprecation warning for the sort keyword to be meaningful, sort=None should be the default. You could also consider setting sort=True automatically whenever a key is given.

comment:78 Changed 12 days ago by git

  • Commit changed from 5044e460c8ab0841404a5e097b19d1811cc49593 to 96d87bb88cf274a8526e61779b23461027a1b1fa

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

96d87bbtrac #27408: fix __add__

comment:79 in reply to: ↑ 77 Changed 12 days ago by dcoudert

Replying to jdemeyer:

This is twice the same condition :-)

if not isinstance(right, EdgesView) or not isinstance(right, EdgesView):

not always easy to focus on something... Replying to jdemeyer:

For __add__, I really meant allowing EdgesView + list. Otherwise, EdgesView + EdgesView works but EdgesView + EdgesView + EdgesView does not. That would be strange. So, if you want to keep the condition, you should check for isinstance(..., (list, EdgesView)).

I changed to use isinstance(..., (list, EdgesView)), and added a doctest with the some a 3 EdgesView

For the deprecation warning for the sort keyword to be meaningful, sort=None should be the default. You could also consider setting sort=True automatically whenever a key is given.

Actually, I'm not so sure of what we should do. The current default is True and None has never been used here. So introducing None might not be a good idea. Consequently, adding a deprecation warning is this ticket might be confusing. It is certainly better to make a specific / clearly identified ticket for that. Do you agree ?

Note: See TracTickets for help on using tickets.