Opened 3 years ago
Closed 2 years ago
#27408 closed enhancement (fixed)
Edge view for graphs
Reported by: | dcoudert | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.0 |
Component: | graph theory | Keywords: | |
Cc: | nthiery, tmonteil | Merged in: | |
Authors: | David Coudert | Reviewers: | Jeroen Demeyer, Vincent Delecroix, Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | 3af5bba (Commits, GitHub, GitLab) | Commit: | 3af5bba498be7277c4c4eb087124c1aee35eb9fd |
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 (101)
comment:1 follow-up: ↓ 16 Changed 3 years ago by
- Branch set to public/27408_edgeview
- Commit set to 01579875c3b76eaf76421decbdc89c4fde53793a
- Status changed from new to needs_review
comment:2 follow-up: ↓ 13 Changed 3 years ago by
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: ↓ 4 Changed 3 years ago by
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: ↓ 5 Changed 3 years ago by
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 theEdgeView
, 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 raisingNotImplementedError
. 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: ↓ 6 Changed 3 years ago by
Replying to vdelecroix:
Replying to dcoudert:
We can certainly also replace
edge_iterator
by theEdgeView
, 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 3 years ago by
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 3 years ago by
- Commit changed from 01579875c3b76eaf76421decbdc89c4fde53793a to 5cf8344cd92ff982bae5644340644556b0788ab5
Branch pushed to git repo; I updated commit sha1. New commits:
5cf8344 | trac #27408: various corrections
|
comment:8 Changed 3 years ago by
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 3 years ago by
You want this to be fast. I would certainly do this in Cython.
comment:10 Changed 3 years ago by
I think it should be called EdgesView
(plural): you're making a view of all edges, not one particular edge.
comment:11 Changed 3 years ago by
- Commit changed from 5cf8344cd92ff982bae5644340644556b0788ab5 to b3f6f4b5dae864c21afd0aadc8c416326a2a1003
Branch pushed to git repo; I updated commit sha1. New commits:
b3f6f4b | trac #27408: start internal variables with _
|
comment:12 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
What do you think of this proposal from #22349?
- 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.
- If
sort=True
is given, always sort (raising an exception if the sorting failed)
- If
sort=False
is given, never sort.
comment:15 Changed 3 years ago by
- 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.
comment:16 in reply to: ↑ 1 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
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 3 years ago by
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 3 years ago by
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: ↓ 22 ↓ 23 Changed 3 years ago by
Some quick answers (cannot work on it now):
- networkx defines
EdgeView
and notEdgesView
(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 writelabels=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 aEdgeView
?- and of course switch to Cython.
comment:22 in reply to: ↑ 21 Changed 3 years ago by
Replying to dcoudert:
labels
. I have this bad habit that I'm trying to correct to writelabels=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 3 years ago by
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 aEdgeView
?
I wouldn't mind to return a list here. It's not very elegant, but it's good for backwards compatibility.
comment:24 Changed 3 years ago by
- Commit changed from b3f6f4b5dae864c21afd0aadc8c416326a2a1003 to 5ba0c3fa4b856e98aad4bbecf74c28db9e795973
comment:25 follow-up: ↓ 26 Changed 3 years ago by
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: ↓ 35 Changed 3 years ago by
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 3 years ago by
- Commit changed from 5ba0c3fa4b856e98aad4bbecf74c28db9e795973 to d9736595c4bac3224a0afb8394d25e1965c82e4a
Branch pushed to git repo; I updated commit sha1. New commits:
d973659 | trac #27408: better getitem and various fix
|
comment:28 Changed 3 years ago by
- Commit changed from d9736595c4bac3224a0afb8394d25e1965c82e4a to 711be0b9788a32164f83dadb287ec5c8333b0f0f
Branch pushed to git repo; I updated commit sha1. New commits:
711be0b | trac #27408: set default sort to None by default and add deprecation warning
|
comment:29 Changed 3 years ago by
- 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
comment:30 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
- Commit changed from 711be0b9788a32164f83dadb287ec5c8333b0f0f to a1701f80d0a80c7a94a7407b6952e23fa1025e76
Branch pushed to git repo; I updated commit sha1. New commits:
a1701f8 | trac #27408: some care for Python 3
|
comment:33 follow-up: ↓ 34 Changed 3 years ago by
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 usingislice
without success. GotAttributeError: 'slice' object has no attribute 'end'
...
- for
.edge_iterator
, we have many calls tonext(...)
. We have to change each of them and may be other stuff.
comment:34 in reply to: ↑ 33 Changed 3 years ago by
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 usingislice
without success. GotAttributeError: '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)
comment:35 in reply to: ↑ 26 Changed 3 years ago by
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 3 years ago by
- Commit changed from a1701f80d0a80c7a94a7407b6952e23fa1025e76 to 890530982e496ddd4b893eb616bfe8c1c8e888ab
Branch pushed to git repo; I updated commit sha1. New commits:
8905309 | trac #27408: improve getitem
|
comment:37 Changed 3 years ago by
According to the documentation of islice, it needs non negative parameters. Thus I tried to combine use of islice and list()[i]
.
comment:38 Changed 3 years ago by
- Commit changed from 890530982e496ddd4b893eb616bfe8c1c8e888ab to e27645bffae04b1b04e39efe41a19e6ac85e5193
Branch pushed to git repo; I updated commit sha1. New commits:
e27645b | trac #27408: it's .step, not .end
|
comment:39 Changed 3 years ago by
- Commit changed from e27645bffae04b1b04e39efe41a19e6ac85e5193 to 8d7bd05b4a60909cc1bf694dc8990fe3d9cae4c2
Branch pushed to git repo; I updated commit sha1. New commits:
8d7bd05 | trac #27408: better like that
|
comment:40 Changed 3 years ago by
- Commit changed from 8d7bd05b4a60909cc1bf694dc8990fe3d9cae4c2 to 132284fc54db27855167d6643fa009340067f218
Branch pushed to git repo; I updated commit sha1. New commits:
132284f | trac #27408: correction of len
|
comment:41 Changed 3 years ago by
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 3 years ago by
- Status changed from needs_work to needs_review
comment:43 Changed 3 years ago by
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 3 years ago by
self.__mul__(n)
-> self * n
comment:45 Changed 3 years ago by
- Commit changed from 132284fc54db27855167d6643fa009340067f218 to bbbb824d1535e76d5ae28ff22f679c8991ddfdf2
comment:46 follow-up: ↓ 47 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
- 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 3 years ago by
- 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 3 years ago by
- Commit changed from bbbb824d1535e76d5ae28ff22f679c8991ddfdf2 to 95322eb2ad828053b869bc077c07c07d0f2da1e8
Branch pushed to git repo; I updated commit sha1. New commits:
95322eb | trac #27408: fix merge conflict
|
comment:51 Changed 3 years ago by
rebase and fix merge conflict with 8.8.beta1
comment:52 Changed 3 years ago by
17 hasn't been addressed. Was that intentional or did you just forget about it?
comment:53 Changed 3 years ago by
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: ↓ 60 Changed 3 years ago by
Various comments about views.pyx
:
- Instead of
class EdgesView():
, I suggest a Cython classcdef 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__
.
<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
byi
.
- 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
.
- The proper way to deal with unknown types in
__eq__
,__add__
and friends is toreturn NotImplemented
.
- In
__mul__
, drop the check forn < 1
, leave that tolist
.
- It would be good to implement
__bool__
too (for checking non-emptyness).
comment:55 Changed 3 years ago by
- Commit changed from 95322eb2ad828053b869bc077c07c07d0f2da1e8 to 7287f14b26832c0958fe1a4d8024909724085d1a
comment:56 follow-ups: ↓ 57 ↓ 58 ↓ 59 Changed 3 years ago by
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 assigningG
_vertex_set
is frozenset_labels
is boolean, but it preventsNone
_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 3 years ago by
With the info that you provided, it should be
_labels
is boolean, but it preventsNone
Why should it be None
? Isn't it just a boolean?
comment:58 in reply to: ↑ 56 Changed 3 years ago by
Replying to dcoudert:
_vertices
can be list, and then we have to handle empty list case instead of assigningG
Or you could use _vertices = None
to represent that case.
comment:59 in reply to: ↑ 56 Changed 3 years ago by
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: ↓ 63 Changed 3 years ago by
Replying to jdemeyer:
Various comments about
views.pyx
:
- Instead of
class EdgesView():
, I suggest a Cython classcdef 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 3 years ago by
- Commit changed from 7287f14b26832c0958fe1a4d8024909724085d1a to 38cdcedfa0401260abb147e02bd95e7b39aa1854
Branch pushed to git repo; I updated commit sha1. New commits:
38cdced | trac #27408: cdef class EdgesView
|
comment:62 Changed 3 years ago by
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 3 years ago by
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 3 years ago by
- Commit changed from 38cdcedfa0401260abb147e02bd95e7b39aa1854 to 2fa2823e1b36e066ebecd6b4265b48a0af2a263c
Branch pushed to git repo; I updated commit sha1. New commits:
2fa2823 | trac #27408: improve __eq__
|
comment:65 Changed 3 years ago by
I didn't know that. It's really tricky.
comment:66 Changed 3 years ago by
Yes, Cython is 95% like Python but that 5% is what makes it tricky.
comment:67 Changed 3 years ago by
Some more comments:
- Moving the handling of
sort=None
toGenericGraph
(in line with 17)
self._sort_edges = False if sort is False else True
should be simplyself._sort_edges = sort
then (since_sort_edges
is declaredbint
, Cython automatically does the conversion tobool
)
self._graph = <GenericGraph_pyx>G
is very dangerous as no type check is done. Replace this byself._graph = <GenericGraph_pyx?>G
which is the same, except that an exception is raised by Cython ifG
is not an instance ofGenericGraph_pyx
.
- Use
def __add__(left, right)
instead ofdef __add__(self, other)
since using the nameself
here is potentially confusing. Same for__mul__
.
- 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 preciseslice
behavior.
comment:68 Changed 3 years ago by
- Commit changed from 2fa2823e1b36e066ebecd6b4265b48a0af2a263c to 74219866a2d11f535d35c611930cb7c5a3f30197
Branch pushed to git repo; I updated commit sha1. New commits:
7421986 | trac #27408: further improvements
|
comment:69 Changed 3 years ago by
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: ↓ 73 Changed 3 years ago by
This should return NotImplemented
:
if not isinstance(right, EdgesView): raise TypeError('right is not a EdgesView')
comment:71 Changed 3 years ago by
- Commit changed from 74219866a2d11f535d35c611930cb7c5a3f30197 to 4e8684663116fc45a1d402a22b1b44977c1a8db6
Branch pushed to git repo; I updated commit sha1. New commits:
4e86846 | trac #27408: return NotImplemented
|
comment:72 Changed 3 years ago by
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:
- Create a new
EdgesView
withsorted=False
and use that to iterate.
- Factor out the iteration-without-sorting to a separate method and call that from
__iter__
.
comment:73 in reply to: ↑ 70 Changed 3 years ago by
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 3 years ago by
- Commit changed from 4e8684663116fc45a1d402a22b1b44977c1a8db6 to 5044e460c8ab0841404a5e097b19d1811cc49593
comment:75 Changed 3 years ago by
- for the iterator, I added a method to iterate unsorted edges. This is cleaner now.
- for
__add__
, I tried to drop tests and gotFile "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 onleft
.
comment:76 Changed 3 years ago by
This is twice the same condition :-)
if not isinstance(right, EdgesView) or not isinstance(right, EdgesView):
comment:77 follow-up: ↓ 79 Changed 3 years ago by
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 3 years ago by
- Commit changed from 5044e460c8ab0841404a5e097b19d1811cc49593 to 96d87bb88cf274a8526e61779b23461027a1b1fa
Branch pushed to git repo; I updated commit sha1. New commits:
96d87bb | trac #27408: fix __add__
|
comment:79 in reply to: ↑ 77 Changed 3 years ago by
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 allowingEdgesView
+list
. Otherwise,EdgesView
+EdgesView
works butEdgesView
+EdgesView
+EdgesView
does not. That would be strange. So, if you want to keep the condition, you should check forisinstance(..., (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 settingsort=True
automatically whenever akey
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 ?
comment:80 Changed 3 years ago by
- Commit changed from 96d87bb88cf274a8526e61779b23461027a1b1fa to 4db22e28da77e5f85898809ae435c734dc215073
comment:81 Changed 3 years ago by
in the doctest in matroids/utilities.py
, I also changed 'a'
to 55
to avoid py2/py3 issues.
comment:82 Changed 3 years ago by
- Commit changed from 4db22e28da77e5f85898809ae435c734dc215073 to 9db083b7318d17379debd265dbb86f8b2699c48b
Branch pushed to git repo; I updated commit sha1. New commits:
9db083b | trac #27408: fix merge conflict with 8.8.rc0
|
comment:83 Changed 3 years ago by
just fixed a merge conflict with 8.8.rc0.
comment:84 Changed 3 years ago by
- Milestone changed from sage-8.8 to sage-8.9
Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).
comment:85 follow-up: ↓ 86 Changed 3 years ago by
- in python2, maybe we need
__nonzero__
as an alias for__bool__
?
- the implementation of
__bool__
does not look optimal.. maybe trying to iter would be better ?
comment:86 in reply to: ↑ 85 Changed 3 years ago by
Replying to chapoton:
- the implementation of
__bool__
does not look optimal.. maybe trying to iter would be better ?
Indeed, if it has to go through return sum(1 for _ in self)
it is rather suboptimal. You can use the funny
for _ in self: return True return False
comment:87 Changed 3 years ago by
- Commit changed from 9db083b7318d17379debd265dbb86f8b2699c48b to 575420c70b6e04e3c6df1505aa0e760b4802066b
comment:88 Changed 3 years ago by
I did something more complex but certainly more efficient than for _ in self:
to avoid the cost of extracting edge labels and to sort edges (when _sort_edges is True
).
Let me know if I should or not add __nonzero__
.
comment:89 Changed 3 years ago by
- in src/sage/graphs/connectivity.pyx, do we need to wrap with list?
comment:90 Changed 3 years ago by
The graph is modified inside the loop, so yes we need to wrap with list.
comment:91 Changed 3 years ago by
do you want to wait for another round of review by Jeroen ?
if not, you can set to positive on my behalf
comment:92 Changed 3 years ago by
- Commit changed from 575420c70b6e04e3c6df1505aa0e760b4802066b to 4937d0b9a9b469576eb36dc7a5ea721a6a169192
comment:93 Changed 3 years ago by
I had to fix a small issue induced by recent change in graph_coloring.pyx
.
comment:94 Changed 3 years ago by
- Reviewers set to Jeroen Demeyer, Vincent Delecroix, Frédéric Chapoton
Let's wait for the patchbot to see if everything is in order, but for me this patch is now good to go (and the html documentation displays well).
comment:95 Changed 3 years ago by
I let you guys decide if another round of review is necessary or not.
As this is a big change, shouldn't we add a specific note in the release changelog or in the documentation of the graph module ? (by the way, sage-8.8.txt is missing in the Changelogs page)
comment:96 Changed 3 years ago by
- Commit changed from 4937d0b9a9b469576eb36dc7a5ea721a6a169192 to 3af5bba498be7277c4c4eb087124c1aee35eb9fd
Branch pushed to git repo; I updated commit sha1. New commits:
3af5bba | trac #27408: fix merge conflicts with 8.9.beta7
|
comment:97 Changed 3 years ago by
- Cc tmonteil added
When reading this thread i was surprised not to be in cc of this ticket as it refers to an email of mine, now i realize that there is a confusion in names between Nicolas Thiéry and Thierry Monteil (it is not the first time). I had some plans to implement that, but i am even happier that someone did the job, i will have a look to the branch.
comment:98 Changed 3 years ago by
Any feedback is more than welcome, and if happy, you can set to positive. We will also have to work on vertices and neighbors views.
comment:99 Changed 3 years ago by
- Milestone changed from sage-8.9 to sage-9.0
It would be good to have this feature inside 9.0.
comment:100 Changed 2 years ago by
- Status changed from needs_review to positive_review
ok, let it be.
Vincent, si tu veux faire une objection, c'est le moment.
comment:101 Changed 2 years ago by
- Branch changed from public/27408_edgeview to 3af5bba498be7277c4c4eb087124c1aee35eb9fd
- Resolution set to fixed
- Status changed from positive_review to closed
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:
next(E)
?E[i]
to get the ith edge, even if it's slow ?New commits:
trac #27408: first trial of edge view
trac #27408: fix doctests in views.py
trac #27408: fix issues in graph module
trac #27408: fix issues in other modules