Removing reverse graph from CGraph

[Jonathan Kliem]

Dear all,

currently the sparse graph backend keeps a reversed copy of the graph.

However, the SparseGraph itself does not have access to it and thus the reversed structure should be moved there for obvious optimizations. See #28904.

As the sparse graph backend is the only backend actually using the reversed structure, it would make sense to remove this.

However, it is very well possible that people use the unsafe methods of SparseGraph directly and code will break.

E.g. in graphs/trees.py the undirected trees are generated by manually adding an arc in each direction.

I think, if we remove the reversed graph attribute in CGraph altogether, people are more likely to catch on that something changed.

But in an undirected graph it can very well happen that they add two edges instead of one (as they used to add one arc for each direction).

Any thoughts?

Jonathan

[David Coudert]

I'm in favor of this change. The code is faster and slightly easier to understand.

Extra opinions are more than welcome.

David.

[Vincent Delecroix]

Dear Jonathan,

The implementation of SparseGraph has many problems. One definitely
has to go through backward incompatible changes in the data structure.
The alternative would be to make a copy of the files with a class
SparseGraphNew. But this sounds completely silly.

People who do not want code to break should not rely on (semi-)private
methods or attributes. In that sense, it is safe to make the thing you
suggest. The behavior of no public method of graphs will change, right?

Thanks for working on this!

Best
Vincent

Le 07/01/2020 à 22:42, 'Jonathan Kliem' via sage-devel a écrit :
> Dear all,
>
> currently the sparse graph backend keeps a reversed copy of the graph.
>
> However, the SparseGraph itself does not have access to it and thus the
> reversed structure should be moved there for obvious optimizations. See

> #28904 <https://trac.sagemath.org/ticket/28904>.

[Jonathan Kliem]

Dear Vincent,

thanks for the reply.

So I guess, it makes sense to remove _cg_rev from CGraphBackend then. This also a step towards unifying the different backends and putting common methods in CGraph instead for a copy in each backend.

Jonathan