Make bridges method for graphs an iterator

[edd8e884-f507-429a-b577-5d554626c0fe]

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

CC: @sagetrac-tpetiteau @sagetrac-cchretien @dcoudert

Component: graph theory

Author: Thierry Monteil

Branch/Commit: 5a42869

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/23002

[edd8e884-f507-429a-b577-5d554626c0fe]

Branch: u/tmonteil/make_bridges_method_for_graphs_an_iterator

[edd8e884-f507-429a-b577-5d554626c0fe]

New commits:

5b9e749

Trac #23002: bridges method for graphs becomes an iterator.

[edd8e884-f507-429a-b577-5d554626c0fe]

Commit: 5b9e749

[dcoudert]

comment:3

What's the motivation for this change ?

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:4

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.

[dcoudert]

comment:5

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.

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:6

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, ...).

[tscrim]

comment:7

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).

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:8

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0bf5687

#23002 : apply suggestions made in comment 7.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5b9e749 to 0bf5687

[dcoudert]

comment:10

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0bf5687 to 416ac32

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

416ac32

Trac #23002: comment 10 (Python 3 compatibility).

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:12

Replying to @dcoudert:

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

Indeed !

[tscrim]

comment:13

Replying to @sagetrac-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

[videlec]

comment:14

Replying to @tscrim:

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

[tscrim]

comment:15

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.

[dcoudert]

comment:16

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.

[tscrim]

comment:17

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.

[heluani]

comment:18

red branch

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 416ac32 to 7dbfb24

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:20

Replying to @heluani:

red branch

green again :)

[dcoudert]

comment:21

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7dbfb24 to 5a42869

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5a42869

#23002 : typo

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:23

Replying to @dcoudert:

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

Oops, thanks for pointing !

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:24

LGTM.

[vbraun]

Changed branch from u/tmonteil/make_bridges_method_for_graphs_an_iterator to 5a42869