Opened 4 years ago
Closed 11 months ago
#23002 closed enhancement (fixed)
Make bridges method for graphs an iterator
Reported by:  tmonteil  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  graph theory  Keywords:  
Cc:  tpetiteau, cchretien, dcoudert  Merged in:  
Authors:  Thierry Monteil  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  5a42869 (Commits, GitHub, GitLab)  Commit:  5a4286984f499cd442d3e2018644d593b7924634 
Dependencies:  Stopgaps: 
Description
The bridges method for graphs returns a list. Here we return an iterator.
Change History (26)
comment:1 Changed 4 years ago by
 Branch set to u/tmonteil/make_bridges_method_for_graphs_an_iterator
comment:2 Changed 4 years ago by
 Commit set to 5b9e7499e156824cd533e4e39fd5b461e37b4765
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
What's the motivation for this change ?
comment:4 Changed 4 years ago by
Today, i am meeting two students who did some Sage development and show them how to contribute their code (related to spanningtrees for digraphs and sandpiles), so we took an existing method and i explained the whole git/trac process, and since we were discussing the difference list/iterator, we chosed that one. So, indeed, this is not an important change regarding Sage, but it has some pedagogical interest.
Wile being a minor improvement, this commit adds some tests to that method ; also, when possible, iterators are prefered over lists, as they save a lot of memory while being as fast, which can be critical for some backtracking or search algorithms, where such constructions can be stacked.
This is becoming the default case with Python3, where even range
becomes an iterator. Ideally, most method should behave that way (when there is no cost). In particular, in the longer term, i am in favor to replace things like neighbor_iterator
by neighbors
and neighbors
by nothing, while the user can write list(G.neighbors())
if she explicitely wants to store the whole stuff for reuse.
comment:5 followup: ↓ 6 Changed 4 years ago by
ok, I understand the motivation. It will certainly be a very hard task to change all the graph module. It is not always easy/possible to do. See for instance #22613.
Q: do you also plan to ask your students to review this ticket? the code looks good to me.
comment:6 in reply to: ↑ 5 Changed 4 years ago by
Replying to dcoudert:
ok, I understand the motivation. It will certainly be a very hard task to change all the graph module. It is not always easy/possible to do. See for instance #22613.
Agree, it is especially unfeasible for things that require recurrent access to data (e.g. dynamic programming).
Q: do you also plan to ask your students to review this ticket? the code looks good to me.
If it is OK for you, go ahead, i guess it is better for them to first create tickets and recieve lots of comments from experienced devs about their code (doctests, naming conventions, ...).
comment:7 followup: ↓ 8 Changed 4 years ago by
A quick comments: Instead of raise StopIteration
, you should simply have a return
. Also, while you are at is, change Returns
> Return
in the 1line docstring.
A more serious comment: This is a backwards incompatible change. So I would instead introduce a new method bridges_iterator
similar to other methods in graphs (e.g., degree
, subgraph_search
, edge_iterator
/edges
).
comment:8 in reply to: ↑ 7 ; followup: ↓ 13 Changed 4 years ago by
Replying to tscrim:
A quick comments: Instead of
raise StopIteration
, you should simply have areturn
. Also, while you are at is, changeReturns
>Return
in the 1line docstring.
Thanks, this indeed cleaner, i will do it.
A more serious comment: This is a backwards incompatible change. So I would instead introduce a new method
bridges_iterator
similar to other methods in graphs (e.g.,degree
,subgraph_search
,edge_iterator
/edges
).
Well, i am more in favor to remove the _iterator
in other methods as explained in comment:4 or we are going to get entangled. When we will move to Python 3, should we define a range_iterator
wrapper ?
Regarding the edges
method, returning a list has a very bad side effect: a list is an iterable but also a container, but the containment is illdefined for graphs:
sage: G = graphs.PetersenGraph() sage: (0, 1) in G.edges(labels=False) True sage: (1,0) in G.edges(labels=False) False sage: G.has_edge((1,0)) True
This causes a lot of troubles as it does not even raise a warning.
My longer term plans would be to define an edge()
view (à la numpy
), with __contains__
pointing to has_edge
, and __iter__
pointing to edge_iterator
, so that every feature works correctly with a pleasant syntax.
comment:9 Changed 4 years ago by
 Commit changed from 5b9e7499e156824cd533e4e39fd5b461e37b4765 to 0bf5687308d4ea6faf7db373247ebace226cab0c
Branch pushed to git repo; I updated commit sha1. New commits:
0bf5687  #23002 : apply suggestions made in comment 7.

comment:10 followup: ↓ 12 Changed 4 years ago by
you wrote in the test section: g.bridges().next()
. Isn't it better to write next(g.bridges())
in Python3 ?
comment:11 Changed 4 years ago by
 Commit changed from 0bf5687308d4ea6faf7db373247ebace226cab0c to 416ac326de1f6c1f0b1710cbff1b8ba904102bce
Branch pushed to git repo; I updated commit sha1. New commits:
416ac32  Trac #23002: comment 10 (Python 3 compatibility).

comment:12 in reply to: ↑ 10 Changed 4 years ago by
Replying to dcoudert:
you wrote in the test section:
g.bridges().next()
. Isn't it better to writenext(g.bridges())
in Python3 ?
Indeed !
comment:13 in reply to: ↑ 8 ; followup: ↓ 14 Changed 4 years ago by
Replying to tmonteil:
Replying to tscrim:
A more serious comment: This is a backwards incompatible change. So I would instead introduce a new method
bridges_iterator
similar to other methods in graphs (e.g.,degree
,subgraph_search
,edge_iterator
/edges
).Well, i am more in favor to remove the
_iterator
in other methods as explained in comment:4 or we are going to get entangled. When we will move to Python 3, should we define arange_iterator
wrapper ?
I do not disagree with this, but at this point we should try to be as consistent as possible. If we are going to change the behavior, we should do it for all or most such methods at once to reduce the backwards breaking shock. Although we could put a deprecation warning in bridges
to say it will return an iterator and while we add the bridges_iterator
, we add it with a deprecation as well saying we will just have an iterator version of bridges
in a year.
Regarding the
edges
method, returning a list has a very bad side effect: a list is an iterable but also a container, but the containment is illdefined for graphs:sage: G = graphs.PetersenGraph() sage: (0, 1) in G.edges(labels=False) True sage: (1,0) in G.edges(labels=False) False sage: G.has_edge((1,0)) TrueThis causes a lot of troubles as it does not even raise a warning.
My longer term plans would be to define an
edge()
view (à lanumpy
), with__contains__
pointing tohas_edge
, and__iter__
pointing toedge_iterator
, so that every feature works correctly with a pleasant syntax.
That one is a much harder and more subtle issue (which deserves a separate ticket). My first thought was basically what you are suggesting too. +1
comment:14 in reply to: ↑ 13 Changed 4 years ago by
Replying to tscrim:
Replying to tmonteil:
Replying to tscrim:
A more serious comment: This is a backwards incompatible change. So I would instead introduce a new method
bridges_iterator
similar to other methods in graphs (e.g.,degree
,subgraph_search
,edge_iterator
/edges
).Well, i am more in favor to remove the
_iterator
in other methods as explained in comment:4 or we are going to get entangled. When we will move to Python 3, should we define arange_iterator
wrapper ?I do not disagree with this, but at this point we should try to be as consistent as possible. If we are going to change the behavior, we should do it for all or most such methods at once to reduce the backwards breaking shock. Although we could put a deprecation warning in
bridges
to say it will return an iterator and while we add thebridges_iterator
, we add it with a deprecation as well saying we will just have an iterator version ofbridges
in a year.
There will be no deprecation warning to say that we switch to Python3 (which is the next stable release). Hence I don't feel like we need something to advertise the switch. However, I agree that doing it all at once in sage 8.0 for all methods that we want to be converted would be much better.
comment:15 Changed 4 years ago by
I am pretty sure we are not switching to Python3 in 8.0. The big changes are the default notebook and support for Cygwin. We still have a bit of work before we are ready to be Python3 compatible, but that isn't way off in the future now.
However, I think there are still differences between Python's view objects and true iterators being returned. Plus, list
will still be perfectly valid in Python3, so changing to an iterator is still a separate can of worms in my mind.
comment:16 Changed 4 years ago by
comment:8 makes me realize that the bridges
method makes the strong assumption that not only edges are ordered (we use (0, 1)
and not (1,0)
) but also blocks (we have block [0, 1]
and not block [1, 0]
). If we want to strengthen the method to avoid future problems, we could make ME
a graph and then use ME.has_edge(tuple(b))
, or use a faster method if any.
Then we should conclude on this ticket. Either we decide that we continue the current practice and create method bridge_iterator
, or we consider that as a first step toward turning all methods to iterators we start with bridges
.
comment:17 Changed 4 years ago by
A view/container object is not the same as an iterator; in particular, you (can) have a __contains__
method. So changing the output to be an iterator would still be a backwards incompatible change. Yet, a view/container object would only be if there was no __contains__
, but not having that would defeat its purpose.
I'm still 1 on making this into an iterator and say we should keep the current practice of having an iterator method.
comment:18 followup: ↓ 20 Changed 11 months ago by
 Status changed from needs_review to needs_work
red branch
comment:19 Changed 11 months ago by
 Commit changed from 416ac326de1f6c1f0b1710cbff1b8ba904102bce to 7dbfb245bca94607f90e79975238ef3de81fe21a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7dbfb24  #23002 : make bridges method for graphs an iterator

comment:20 in reply to: ↑ 18 Changed 11 months ago by
 Status changed from needs_work to needs_review
comment:21 followup: ↓ 23 Changed 11 months ago by
 sage: list(list(bridges(g))) + sage: list(bridges(g))
comment:22 Changed 11 months ago by
 Commit changed from 7dbfb245bca94607f90e79975238ef3de81fe21a to 5a4286984f499cd442d3e2018644d593b7924634
Branch pushed to git repo; I updated commit sha1. New commits:
5a42869  #23002 : typo

comment:23 in reply to: ↑ 21 Changed 11 months ago by
Replying to dcoudert:
 sage: list(list(bridges(g))) + sage: list(bridges(g))
Oops, thanks for pointing !
comment:24 Changed 11 months ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
LGTM.
comment:25 Changed 11 months ago by
 Milestone changed from sage8.0 to sage9.2
comment:26 Changed 11 months ago by
 Branch changed from u/tmonteil/make_bridges_method_for_graphs_an_iterator to 5a4286984f499cd442d3e2018644d593b7924634
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac #23002: bridges method for graphs becomes an iterator.