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: sage-9.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:

Status badges

Description

The bridges method for graphs returns a list. Here we return an iterator.

Change History (26)

comment:1 Changed 4 years ago by tmonteil

  • Branch set to u/tmonteil/make_bridges_method_for_graphs_an_iterator

comment:2 Changed 4 years ago by tmonteil

  • Commit set to 5b9e7499e156824cd533e4e39fd5b461e37b4765
  • Status changed from new to needs_review

New commits:

5b9e749Trac #23002: bridges method for graphs becomes an iterator.

comment:3 Changed 4 years ago by dcoudert

What's the motivation for this change ?

comment:4 Changed 4 years ago by tmonteil

Today, i am meeting two students who did some Sage development and show them how to contribute their code (related to spanning-trees 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 follow-up: Changed 4 years ago by 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.

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 tmonteil

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 follow-up: Changed 4 years ago by tscrim

A quick comments: Instead of raise StopIteration, you should simply have a return. Also, while you are at is, change Returns -> Return in the 1-line 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 ; follow-up: Changed 4 years ago by tmonteil

Replying to tscrim:

A quick comments: Instead of raise StopIteration, you should simply have a return. Also, while you are at is, change Returns -> Return in the 1-line 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 ill-defined 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 git

  • 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 follow-up: Changed 4 years ago by dcoudert

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 git

  • Commit changed from 0bf5687308d4ea6faf7db373247ebace226cab0c to 416ac326de1f6c1f0b1710cbff1b8ba904102bce

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

416ac32Trac #23002: comment 10 (Python 3 compatibility).

comment:12 in reply to: ↑ 10 Changed 4 years ago by tmonteil

Replying to dcoudert:

you wrote in the test section: g.bridges().next(). Isn't it better to write next(g.bridges()) in Python3 ?

Indeed !

comment:13 in reply to: ↑ 8 ; follow-up: Changed 4 years ago by 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 a range_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 ill-defined 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.

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 vdelecroix

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 a range_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.

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 tscrim

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 dcoudert

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 tscrim

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 follow-up: Changed 11 months ago by heluani

  • Status changed from needs_review to needs_work

red branch

comment:19 Changed 11 months ago by git

  • 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 tmonteil

  • Status changed from needs_work to needs_review

Replying to heluani:

red branch

green again :)

comment:21 follow-up: Changed 11 months ago by dcoudert

-        sage: list(list(bridges(g)))
+        sage: list(bridges(g))

comment:22 Changed 11 months ago by git

  • 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 tmonteil

Replying to dcoudert:

-        sage: list(list(bridges(g)))
+        sage: list(bridges(g))

Oops, thanks for pointing !

comment:24 Changed 11 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

LGTM.

comment:25 Changed 11 months ago by chapoton

  • Milestone changed from sage-8.0 to sage-9.2

comment:26 Changed 11 months ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.