Digraph.reverse() should be rewritten more efficiently ( not hard )

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

This function should be rewritten much more efficiently :

First, there should be a way to reverse the arcs "in place" ( without building a copy, by modifying the current graph -- I do not know if the expression used in frech translates in this case ). Such a function, for c_graphs, should be written in Cython and consist in the case of sparse graph in reverting the two copies kept of the graph. In the end, this function should consist in an (optional) copy of the graph (=fast) and a call to the functionr reverting the arcs ( O(1) )

If possible and if deemed useful, the same should be made for NetworkX graphs.

CC: @rlmill

Component: graph theory

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

[89c6e537-b2e3-45e6-882d-d4957b74ffe5]

comment:1

In case of a SparseGraph, the SparseGraphBackend has self._cg and self._cg_rev. They can merely be swapped. In the case of a NetworkX graph, I believe their digraphs have succ and pred dictionaries storing the adjacency information. These could also be swapped. For DenseGraphs, this is equivalent to switching between row ordering and column ordering in bitsets, which is inevitably costly.