Edge view for graphs

[dcoudert]

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.

CC: @nthiery @sagetrac-tmonteil

Component: graph theory

Author: David Coudert

Branch/Commit: 3af5bba

Reviewer: Jeroen Demeyer, Vincent Delecroix, Frédéric Chapoton

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

[dcoudert]

Branch: public/27408_edgeview

[dcoudert]

comment:1

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:

fc42aa0	trac #27408: first trial of edge view
79b426b	trac #27408: fix doctests in views.py
0e4961b	trac #27408: fix issues in graph module
0157987	trac #27408: fix issues in other modules

[dcoudert]

Commit: 0157987

[videlec]

comment:2

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

[dcoudert]

comment:3

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.

[videlec]

comment:4

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.

[videlec]

comment:5

Replying to @videlec:

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

[dcoudert]

comment:6

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.

[sagetrac-git]

Changed commit from 0157987 to 5cf8344

[sagetrac-git]

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

5cf8344

trac #27408: various corrections

[videlec]

comment:8

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.

[jdemeyer]

comment:9

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

[jdemeyer]

comment:10

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

[sagetrac-git]

Changed commit from 5cf8344 to b3f6f4b

[sagetrac-git]

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

b3f6f4b

trac #27408: start internal variables with _

[jdemeyer]

comment:12

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

[jdemeyer]

comment:13

Replying to @videlec:

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.

[jdemeyer]

comment:14

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.

2. If sort=True is given, always sort (raising an exception if the sorting failed)

3. If sort=False is given, never sort.

[jdemeyer]

comment:15

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

[jdemeyer]

comment:16

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.

[jdemeyer]

comment:17

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.

[jdemeyer]

comment:18

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?

[jdemeyer]

comment:19

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.

[fchapoton]

comment:89

• in src/sage/graphs/connectivity.pyx, do we need to wrap with list?

[dcoudert]

comment:90

The graph is modified inside the loop, so yes we need to wrap with list.

[fchapoton]

comment:91

do you want to wait for another round of review by Jeroen ?

if not, you can set to positive on my behalf

[sagetrac-git]

Changed commit from 575420c to 4937d0b

[sagetrac-git]

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

5cd8c5e	trac #27408: Merged with 8.9.beta3
4937d0b	trac #27408: fix small issue with graph_coloring.pyx

[dcoudert]

comment:93

I had to fix a small issue induced by recent change in graph_coloring.pyx.

[dcoudert]

comment:94

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

[dcoudert]

Reviewer: Jeroen Demeyer, Vincent Delecroix, Frédéric Chapoton

[dcoudert]

comment:95

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)

[sagetrac-git]

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

3af5bba

trac #27408: fix merge conflicts with 8.9.beta7

[sagetrac-git]

Changed commit from 4937d0b to 3af5bba

[sagetrac-tmonteil]

comment:97

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.

[dcoudert]

comment:98

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.

[dcoudert]

comment:99

It would be good to have this feature inside 9.0.

[fchapoton]

comment:100

ok, let it be.

Vincent, si tu veux faire une objection, c'est le moment.

[vbraun]

Changed branch from public/27408_edgeview to 3af5bba

[tornaria]

How long it should take until the deprecation warning is removed?