Move reversed graph from backend to CGraph for sparse graphs #28904

kliem · 2019-12-21T00:44:43Z

Currently, for sparse graphs the backend keeps a copy of the reversed graph. This makes iterating over ingoing neighbors much faster.

However, SparseGraph itself does not have access to this. So e.g. when deleting vertices, this results in a massive slow down as it needs to delete incoming edges.

We initialize the sparse backend with the reversed structure and instead add the reversed structure directly to SparseGraph.

Before this ticket:

sage: edges = [(randint(0,1000), randint(0,1000)) for _ in range(100000)]
sage: save(edges, '/tmp/edges')
sage: D = DiGraph(multiedges=True, loops=True)
sage: %time D.add_edges(edges)
CPU times: user 80.1 ms, sys: 0 ns, total: 80.1 ms
Wall time: 79.6 ms
sage: %time for i in range(100): D.delete_vertex(i)
CPU times: user 11.7 ms, sys: 0 ns, total: 11.7 ms
Wall time: 11.5 ms

With this ticket:

sage: edges = load('/tmp/edges')
sage: D = DiGraph(multiedges=True, loops=True)
sage: %time D.add_edges(edges)
CPU times: user 69 ms, sys: 0 ns, total: 69 ms
Wall time: 68.6 ms
sage: %time for i in range(100): D.delete_vertex(i)
CPU times: user 4.42 ms, sys: 16 µs, total: 4.43 ms
Wall time: 4.44 ms

We fix an issue in subdivide_edges that would have caused a doctest to fail with the new setup:

There is a doctest calling the method subdivide_edges with self.edges(). As one can see from the documenation from EdgesView, one should not modify the graph while iterating through EdgesView, because it updates itself. So the following test in generic_graph.py is wrong usage of subdivide_edges or edges:

sage: g.subdivide_edges(g.edges(), 1)

However, as it seems very natural to do this, we pass a tuple instead of EdgesView to the backend.

CC: @videlec @dcoudert

Component: graph theory

Keywords: sparse graphs, backend

Author: Jonathan Kliem

Branch/Commit: a46e717

Reviewer: David Coudert

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

The text was updated successfully, but these errors were encountered:

kliem · 2019-12-21T00:46:29Z

comment:1

TBtw, there is a bug that leads to a crash with:

sage: G = DiGraph(2, data_structure='dense')
sage: G.add_edge(0,1)
sage: G.is_eulerian()

This ticket also fixes this (the method in_degree in the CGraph backend assumes _cg_rev to be initialized).

kliem · 2019-12-21T00:50:15Z

Commit: 47a3897

kliem · 2019-12-21T00:50:15Z

Author: Jonathan Kliem

kliem · 2019-12-21T00:50:15Z

Branch: public/28904

kliem · 2019-12-21T00:50:15Z

comment:2

This probably needs to be cleaned up a lot.
Is it going in a good direction?
On my side, all tests in graphs seem to succeed.

New commits:

`47a3897`	`moved duplicate of sparse graph into the cgraph structure`

kliem · 2019-12-21T10:31:36Z

comment:4

One needs to be careful, about taking the same set of edges I guess.

sagetrac-git · 2019-12-21T10:32:22Z

Changed commit from 47a3897 to 7d70aaf

sagetrac-git · 2019-12-21T10:32:22Z

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

`7d70aaf`	`make class final`

dcoudert · 2019-12-21T10:46:56Z

comment:6

Thank you for doing this, it's really needed.

With these changes, _cg_rev is no longer initialized, right ? If it's no longer needed, may be we can remove it, but we have to ensure that no-one is using it. Actually I fear that some users are using it for personal code. I see 2 solutions for that:

send a pool to sage-dev for complete removal
maintain an object build from _cg with appropriate pointers, and add a warning in the documentation.

in `sparse_graph.pyx`:

-            for i from 0 <= i < self.active_vertices.size * self.hash_length:
+            for i in range(self.active_vertices.size * self.hash_length):

I think you can simplify tests to NULL

-                while temp[0] != NULL:
+                while temp[0]:

-        Lists the in-neighbors of a vertex as BTNodes
+        List the in-neighbors of a vertex as BTNodes

-        Builds the list of arcs into a vertex.
+        Build the list of arcs into a vertex.

-        Adds arc (u, v) to the graph with label l.
+        Add arc (u, v) to the graph with label l.

Better to use True and False instead of 0 and 1.

-        cdef int u_int = self.check_labelled_vertex(u, 0)
-        cdef int v_int = self.check_labelled_vertex(v, 0)
+        cdef int u_int = self.check_labelled_vertex(u, False)
+        cdef int v_int = self.check_labelled_vertex(v, False)

in `c_graph.pyx` we can do some extra optimisations, like

in verts

-        cdef int i
-        return [i for i in range(<int>self.active_vertices.size)
-                if bitset_in(self.active_vertices, i)]
+       return bitset_list(self.active_vertices)

in iterator_verts

-            for i in range(self._cg.active_vertices.size):
-                if (bitset_in(self._cg.active_vertices, i)
-                    and i not in self.vertex_labels
-                    and i not in self.vertex_ints):
-                        yield i
+            i = bitset_first(self._cg.active_vertices)
+            while i >= 0:
+                if (i not in self.vertex_labels
+                    and i not in self.vertex_ints):
+                        yield i
+                i = bitset_next(self._cg.active_vertices, i + 1)

embray · 2020-01-06T14:10:03Z

comment:7

Ticket retargeted after milestone closed

kliem · 2020-01-07T19:30:44Z

Changed commit from 7d70aaf to 64c9493

kliem · 2020-01-07T19:30:44Z

New commits:

`d72d0ab`	`moved duplicate of sparse graph into the cgraph structure`
`64c9493`	`make class final`

kliem · 2020-01-07T19:30:44Z

Changed branch from public/28904 to public/28904-reb

sagetrac-git · 2020-01-07T21:03:34Z

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

`81e99e6`	`lots of small improvements`

sagetrac-git · 2020-01-07T21:03:34Z

Changed commit from 64c9493 to 81e99e6

kliem · 2020-01-07T21:25:41Z

comment:10

Thanks for the comments.

Replying to @dcoudert:

in iterator_verts

-            for i in range(self._cg.active_vertices.size):
-                if (bitset_in(self._cg.active_vertices, i)
-                    and i not in self.vertex_labels
-                    and i not in self.vertex_ints):
-                        yield i
+            i = bitset_first(self._cg.active_vertices)
+            while i >= 0:
+                if (i not in self.vertex_labels
+                    and i not in self.vertex_ints):
+                        yield i
+                i = bitset_next(self._cg.active_vertices, i + 1)

Fixing this makes a mistake apparent: There is a doctest in generic_graph.py that subdivides all edges of a graph by using self.edges(). However, one should not iterate over an EdgesView object while modifying the graph. I have modified the method subdivide_edges to generate a tuple from EdgesView.

sagetrac-git · 2020-01-07T21:26:47Z

Changed commit from 81e99e6 to f4423f0

sagetrac-git · 2020-01-07T21:26:47Z

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

`f4423f0`	`small optimizations`

dcoudert · 2020-01-08T12:07:09Z

comment:12

I have some compilation warnings. It's better to check if it's possible to avoid.

[2/4] gcc -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -I./sage/cpython -I./sage/libs/ntl -I/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/cysignals -Isage/cpython -I./sage/rings -I/Users/dcoudert/sage3/sage/local/include -I/Users/dcoudert/sage3/sage/src -I/Users/dcoudert/sage3/sage/src/sage/ext -I/Users/dcoudert/sage3/sage/local/include/python3.7m -I/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/numpy/core/include -Ibuild/cythonized -I/Users/dcoudert/sage3/sage/local/include/python3.7m -c build/cythonized/sage/graphs/base/c_graph.cpp -o build/temp.macosx-10.9-x86_64-3.7/build/cythonized/sage/graphs/base/c_graph.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -std=c++11
build/cythonized/sage/graphs/base/c_graph.cpp:16256:48: warning: comparison of integers of different signs: 'size_t' (aka 'unsigned long') and 'long' [-Wsign-compare]
      __pyx_t_2 = ((__pyx_cur_scope->__pyx_v_i != -1L) != 0);
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~ ^  ~~~
1 warning generated.
g++ -bundle -undefined dynamic_lookup -L/Users/dcoudert/sage3/sage/local/lib -Wl,-rpath,/Users/dcoudert/sage3/sage/local/lib -L/usr/local/opt/openssl/lib -L. -L/Users/dcoudert/sage3/sage/local/lib -Wl,-rpath,/Users/dcoudert/sage3/sage/local/lib -L/usr/local/opt/openssl/lib -L/Users/dcoudert/sage3/sage/local/lib -Wl,-rpath,/Users/dcoudert/sage3/sage/local/lib build/temp.macosx-10.9-x86_64-3.7/build/cythonized/sage/graphs/base/c_graph.o -L/Users/dcoudert/sage3/sage/local/lib -L/Users/dcoudert/sage3/sage/local/lib -lgmp -lstdc++ -o build/lib.macosx-10.9-x86_64-3.7/sage/graphs/base/c_graph.cpython-37m-darwin.so -lpari
[3/4] gcc -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -I./sage/cpython -Isage/cpython -I/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/cysignals -I/Users/dcoudert/sage3/sage/local/include -I/Users/dcoudert/sage3/sage/src -I/Users/dcoudert/sage3/sage/src/sage/ext -I/Users/dcoudert/sage3/sage/local/include/python3.7m -I/Users/dcoudert/sage3/sage/local/lib/python3.7/site-packages/numpy/core/include -Ibuild/cythonized -I/Users/dcoudert/sage3/sage/local/include/python3.7m -c build/cythonized/sage/graphs/base/sparse_graph.c -o build/temp.macosx-10.9-x86_64-3.7/build/cythonized/sage/graphs/base/sparse_graph.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -std=c99
build/cythonized/sage/graphs/base/sparse_graph.c:11350:35: warning: comparison of integers of different signs: 'size_t' (aka 'unsigned long') and 'int' [-Wsign-compare]
    for (__pyx_t_5 = 0; __pyx_t_5 < __pyx_t_4; __pyx_t_5+=1) {
                        ~~~~~~~~~ ^ ~~~~~~~~~
build/cythonized/sage/graphs/base/sparse_graph.c:11384:35: warning: comparison of integers of different signs: 'size_t' (aka 'unsigned long') and 'int' [-Wsign-compare]
    for (__pyx_t_5 = 0; __pyx_t_5 < __pyx_t_4; __pyx_t_5+=1) {
                        ~~~~~~~~~ ^ ~~~~~~~~~
build/cythonized/sage/graphs/base/sparse_graph.c:19114:87: warning: incompatible pointer types passing 'struct __pyx_obj_4sage_6graphs_4base_7c_graph_CGraph *' to parameter of
      type 'struct __pyx_obj_4sage_6graphs_4base_12sparse_graph_SparseGraph *' [-Wincompatible-pointer-types]
  ...((struct __pyx_obj_4sage_6graphs_4base_7c_graph_CGraph *)((struct __pyx_obj_4sage_6graphs_4base_12sparse_graph_SparseGraph *)__pyx_v_self->__pyx_base._cg)), __pyx_v_u_int...
     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
build/cythonized/sage/graphs/base/sparse_graph.c:9396:149: note: passing argument to parameter '__pyx_v_self' here
static int __pyx_f_4sage_6graphs_4base_12sparse_graph_11SparseGraph_has_arc_unsafe(struct __pyx_obj_4sage_6graphs_4base_12sparse_graph_SparseGraph *__pyx_v_self, int __pyx...
                                                                                                                                                    ^
build/cythonized/sage/graphs/base/sparse_graph.c:25037:87: warning: incompatible pointer types passing 'struct __pyx_obj_4sage_6graphs_4base_7c_graph_CGraph *' to parameter of
      type 'struct __pyx_obj_4sage_6graphs_4base_12sparse_graph_SparseGraph *' [-Wincompatible-pointer-types]
  ...((struct __pyx_obj_4sage_6graphs_4base_7c_graph_CGraph *)((struct __pyx_obj_4sage_6graphs_4base_12sparse_graph_SparseGraph *)__pyx_v_self->__pyx_base._cg)), __pyx_v_u_int...
     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
build/cythonized/sage/graphs/base/sparse_graph.c:9396:149: note: passing argument to parameter '__pyx_v_self' here
static int __pyx_f_4sage_6graphs_4base_12sparse_graph_11SparseGraph_has_arc_unsafe(struct __pyx_obj_4sage_6graphs_4base_12sparse_graph_SparseGraph *__pyx_v_self, int __pyx...
                                                                                                                                                    ^
4 warnings generated.

method del_arc_unsafe returns nothing
in method del_arc_label_unsafe, can't we do this (not sure if it's better or not):

-        cdef int error = self._del_arc_label_unsafe(u, v, l, self.vertices)
-        if error:
-            return 1 # indicate an error
+        if self._del_arc_label_unsafe(u, v, l, self.vertices):
+            return 1 # indicate an error

Thanks for correcting subdivise_edges.

I confirm that vertex deletion is much faster now.

kliem · 2020-01-08T16:02:45Z

comment:13

There are tons of compilation warnings, as we include all of bitset.pxi, which is annoying, but of course not serious.

The compilation warning about wrong casting of self._cg is a bit tricky. I think I took care of it now. The problem is that SparseGraphBackend casts the SparseGraph to a CGraph in order to assign it to self._cg, which is declared to be a CGraph. This is later on casted back into a SpareGraph, which of course produces a warning.

My approach now: Remove the attribute _cg from CGraphBackend and add it to the inherited backends with the proper declaration. Add an inline method cg, which returns _cg casted to a CGraph. This is cleaner, I think.

sagetrac-git · 2020-01-08T16:03:25Z

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

`545eeaf`	`replaced self._cg by the correct object to avoid type casting warnings`
`4af81b4`	small improvements in `del_arc_...`

sagetrac-git · 2020-01-08T16:03:25Z

Changed commit from f4423f0 to 4af81b4

dcoudert · 2020-01-09T17:13:45Z

comment:15

I'm happy with the current code, but it would be better to get extra opinion (e.g., from the thread https://groups.google.com/forum/#!topic/sage-devel/2eIaD3r8Vl8).

kliem · 2020-01-09T19:37:56Z

comment:16

There remains the question, whether we should remove cg_rev altogether and whether we should do it now.

The advantage of removing it, is that code referring to it won't compile anymore and/or give a proper warning. Currently, if one assumes this to be initialized and uses it in cython, sage might crash hard (segmentation fault I believe).

sagetrac-git · 2020-01-14T08:21:56Z

Changed commit from 4af81b4 to bfd25a9

sagetrac-git · 2020-01-14T08:21:56Z

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

`bfd25a9`	`removed attribute _cg_rev from CGraphBackend`

kliem · 2020-01-14T08:25:35Z

comment:18

I removed the attribute _cg_rev now.

The method check_labelled_vertex just ignores the input reverse now.

The method c_graph return (self._cg, None) instead of (self._cg, self._cg_rev).

videlec · 2020-02-15T15:33:33Z

comment:19

Why

diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
index 139c8df..4fa7f75 100644
--- a/src/sage/graphs/generic_graph.py
+++ b/src/sage/graphs/generic_graph.py
@@ -11001,6 +11001,8 @@ class GenericGraph(GenericGraph_pyx):
 
             - :meth:`subdivide_edge` -- subdivides one edge
         """
+        if isinstance(edges, EdgesView):
+            edges = tuple(edges)

dcoudert · 2020-02-15T16:19:00Z

comment:20

This is independent from the purpose of this ticket, but this is effectively an issue to be fixed.

kliem · 2020-02-15T16:24:01Z

comment:21

I updated the description of the ticket to account for the change.

mkoeppe · 2020-04-14T19:41:51Z

comment:22

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

mkoeppe · 2020-08-11T17:31:11Z

comment:23

What's the status of this ticket?

kliem · 2020-08-11T20:24:38Z

comment:24

Needs review.

It's annoying to check, I guess. But it would be a nice improvements with many applications. Maybe I should request a review on sage-devel.

dcoudert · 2020-08-12T08:41:16Z

comment:25

overall, it's a very nice improvement. I have only a few suggestions.

sparse_graph.pyx

instead of checking self.vertices != self.vertices_rev, we could store a boolean value self._directed and have a method self.is_directed()).
instead of <size_t>-1, don't we have a constant equal to the max value ? This is something we should do in several places in the code. Could be done in dedicated tickets
in out_neighbors_unsafe and in_neighbors_unsafe, remove cdef list l = [], not used
I know that the documentation of cdef methods is not displayed, but it would be cleaner to follow the same standard than in the other parts of the code. For instance

        INPUT:
-            u, v -- non-negative integers
+
+            - ``u, v`` -- non-negative integers

Of course, we can do that in a future ticket. Not a priority here

methods out_arcs_unsafe and in_arcs_unsafe return lists. Why not changing to an iterator ? If I'm not mistaken, these methods are only used in for loops.
same for method all_arcs which is used in a for loop and in some doctests where we could use list(...).

confetti:sage dcoudert$ git grep -i "\.all_arcs" src/sage/
src/sage/graphs/base/c_graph.pyx:            - :meth:`all_arcs <sage.graphs.base.sparse_graph.SparseGraph.all_arcs>`
src/sage/graphs/base/c_graph.pyx:            sage: G.all_arcs(0, 1)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(1,2)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(7,3)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(1,2)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(5,4)
src/sage/graphs/base/sparse_graph.pyx:            sage: G.all_arcs(1,2)
src/sage/graphs/base/sparse_graph.pyx:        num_arcs = self.all_arcs_unsafe(u, v, arc_labels, size)
src/sage/graphs/base/sparse_graph.pyx:            sage: G.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:            sage: G.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:                     for l_int in self._cg.all_arcs(u_int, v_int)]
src/sage/graphs/base/sparse_graph.pyx:        for l_int in self._cg.all_arcs(u_int, v_int):

kliem · 2020-08-12T10:19:24Z

Changed commit from bfd25a9 to a46e717

kliem · 2020-08-12T10:19:24Z

New commits:

`fd1d8de`	`Merge branch 'public/28904-reb' of git://trac.sagemath.org/sage into public/28904-reb2`
`bb68006`	`more consistent INPUT blocks`
`a46e717`	method `is_directed` and remove unused list l

kliem · 2020-08-12T10:19:24Z

Changed branch from public/28904-reb to public/28904-reb2

kliem · 2020-08-12T10:27:04Z

comment:27

Replying to @dcoudert:

overall, it's a very nice improvement. I have only a few suggestions.

sparse_graph.pyx

instead of checking self.vertices != self.vertices_rev, we could store a boolean value self._directed and have a method self.is_directed()).

Done.

instead of <size_t>-1, don't we have a constant equal to the max value ? This is something we should do in several places in the code. Could be done in dedicated tickets

This is being cythonized into ((size_t)-1L) and I hope the compiler takes care of it from there. It's maybe not so nice codewise, but I don't think it is any loss.

in out_neighbors_unsafe and in_neighbors_unsafe, remove cdef list l = [], not used

Done.

I know that the documentation of cdef methods is not displayed, but it would be cleaner to follow the same standard than in the other parts of the code. For instance
        INPUT:
-            u, v -- non-negative integers
+
+            - ``u, v`` -- non-negative integers
Of course, we can do that in a future ticket. Not a priority here

Done. It's a rather large commit though as I went over all the places that "caught my eye".

methods out_arcs_unsafe and in_arcs_unsafe return lists. Why not changing to an iterator ? If I'm not mistaken, these methods are only used in for loops.
same for method all_arcs which is used in a for loop and in some doctests where we could use list(...).

confetti:sage dcoudert$ git grep -i "\.all_arcs" src/sage/
src/sage/graphs/base/c_graph.pyx:            - :meth:`all_arcs <sage.graphs.base.sparse_graph.SparseGraph.all_arcs>`
src/sage/graphs/base/c_graph.pyx:            sage: G.all_arcs(0, 1)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(1,2)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(7,3)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(1,2)
src/sage/graphs/base/sparse_graph.pyx:    sage: S.all_arcs(5,4)
src/sage/graphs/base/sparse_graph.pyx:            sage: G.all_arcs(1,2)
src/sage/graphs/base/sparse_graph.pyx:        num_arcs = self.all_arcs_unsafe(u, v, arc_labels, size)
src/sage/graphs/base/sparse_graph.pyx:            sage: G.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:            sage: G.all_arcs(0,1)
src/sage/graphs/base/sparse_graph.pyx:                     for l_int in self._cg.all_arcs(u_int, v_int)]
src/sage/graphs/base/sparse_graph.pyx:        for l_int in self._cg.all_arcs(u_int, v_int):

The last two I would leave for future tickets. But you are right. We really iterate over a structure that is already there (either over a bitset or a tree). So there is no use in wasting resources for creating this list.

dcoudert · 2020-08-12T13:48:24Z

comment:28

OK to let the change from list to iterator for another ticket.

LGTM.

Thank you.

dcoudert · 2020-08-12T13:48:24Z

Reviewer: David Coudert

kliem · 2020-08-12T15:07:46Z

comment:29

Thanks.

vbraun · 2020-08-14T22:23:47Z

Changed branch from public/28904-reb2 to a46e717

kliem added this to the sage-9.0 milestone Dec 21, 2019

kliem added c: graph theory labels Dec 21, 2019

kliem added the s: needs review label Dec 21, 2019

This comment has been minimized.

Sign in to view

embray modified the milestones: sage-9.0, sage-9.1 Jan 6, 2020

This comment has been minimized.

Sign in to view

mkoeppe modified the milestones: sage-9.1, sage-9.2 Apr 14, 2020

dcoudert added s: positive review and removed s: needs review labels Aug 12, 2020

vbraun removed the s: positive review label Aug 14, 2020

vbraun closed this as completed in c0b61fd Aug 14, 2020

kliem mentioned this issue Jan 29, 2023

Meta ticket: Simplify and speed up graph backends #28895

Open

Move reversed graph from backend to CGraph for sparse graphs #28904

Move reversed graph from backend to CGraph for sparse graphs #28904

Comments

kliem commented Dec 21, 2019

kliem commented Dec 21, 2019

kliem commented Dec 21, 2019

kliem commented Dec 21, 2019

kliem commented Dec 21, 2019

kliem commented Dec 21, 2019

This comment has been minimized.

kliem commented Dec 21, 2019

sagetrac-git mannequin commented Dec 21, 2019

sagetrac-git mannequin commented Dec 21, 2019

dcoudert commented Dec 21, 2019

in sparse_graph.pyx:

in c_graph.pyx we can do some extra optimisations, like

embray commented Jan 6, 2020

kliem commented Jan 7, 2020

kliem commented Jan 7, 2020

kliem commented Jan 7, 2020

sagetrac-git mannequin commented Jan 7, 2020

sagetrac-git mannequin commented Jan 7, 2020

kliem commented Jan 7, 2020

sagetrac-git mannequin commented Jan 7, 2020

sagetrac-git mannequin commented Jan 7, 2020

dcoudert commented Jan 8, 2020

kliem commented Jan 8, 2020

sagetrac-git mannequin commented Jan 8, 2020

sagetrac-git mannequin commented Jan 8, 2020

dcoudert commented Jan 9, 2020

kliem commented Jan 9, 2020

sagetrac-git mannequin commented Jan 14, 2020

sagetrac-git mannequin commented Jan 14, 2020

kliem commented Jan 14, 2020

videlec commented Feb 15, 2020

dcoudert commented Feb 15, 2020

kliem commented Feb 15, 2020

This comment has been minimized.

mkoeppe commented Apr 14, 2020

mkoeppe commented Aug 11, 2020

kliem commented Aug 11, 2020

dcoudert commented Aug 12, 2020

kliem commented Aug 12, 2020

kliem commented Aug 12, 2020

kliem commented Aug 12, 2020

kliem commented Aug 12, 2020

dcoudert commented Aug 12, 2020

dcoudert commented Aug 12, 2020

kliem commented Aug 12, 2020

vbraun commented Aug 14, 2020

in `sparse_graph.pyx`:

in `c_graph.pyx` we can do some extra optimisations, like