Meta ticket: Simplify and speed up graph backends

[kliem]

This ticket collects tickets simplifying and improving the graph backends.

It is motivated by the following post:

https://groups.google.com/d/msg/sage-devel/JhirgrbcFMc/CVfHhPCdAgAJ

• Polish the use of iterators in C graphs #6604: Polish the use of iterators in C graphs
• Digraph.reverse() should be rewritten more efficiently ( not hard ) #7720: Digraph.reverse() should be rewritten more efficiently ( not hard )
• Everything is not well with dense graph backends #12387: Everything is not well with dense graph backends
• Graph library passes almost surelly erroneous calls without an exception #12540: Graph library passes almost surelly erroneous calls without an exception
• Speed up some graph iterations #13730: Speed up some graph iterations
• Deprecate sorting of Graph vertices and edges by default #22349: Deprecate sorting of Graph vertices and edges by default
• graph add_edges/delete_edges are dramatically slow #28259: graph add_edges/delete_edges are dramatically slow
• Graphs: Move common methods of backends to CGraph #28896: Graphs: Move common methods of backends to CGraph
• BipartiteGraph blindly trusts generic graphs #28897: BipartiteGraph blindly trusts generic graphs
• Move reversed graph from backend to CGraph for sparse graphs #28904: Move reversed graph from backend to CGraph for sparse graphs
• equality of graphs is 60 times slower than equality of their list of edges #30641: equality of graphs is 60 times slower than equality of their list of edges
• Optimize edge iterator for graphs #30665: Optimize edge iterator for graphs
• Unify graph backends #30769: Unify graph backends
• Further improvements in method subgraph #30753: Further improvements in method subgraph
• Improve deleting of edges of graphs #30777: Improve deleting of edges of graphs
• use iterators for outgoing and ingoing arcs
• Use bitsets/binary matrix for edges of dense graphs #31197: Use bitsets/binary matrix for edges of dense graphs

Possibly related tickets:

• Polish the use of iterators in C graphs #6604: Polish the use of iterators in C graphs
• Speed up graph generation using Cython #9143: Speed up graph generation using Cython
• Modified check_edge_label in the sparse graph backend to consider equals the same objects rather than objects with the same contents #9301: Modified check_edge_label in the sparse graph backend to consider equals the same objects rather than objects with the same contents
• {c,sparse}_graph: systematically turn integer-like vertices into ints #22374: {c,sparse}_graph: systematically turn integer-like vertices into ints
• G.edges_incident returns edges with vertices swapped #24989: G.edges_incident returns edges with vertices swapped
• Memory error with graphs generators: JankoKharaghaniGraph and SquaredSkewHadamardMatrixGraph #25465, 2 doctests failed in smallgraphs.py #28865: Memory error with graphs generators: JankoKharaghaniGraph and SquaredSkewHadamardMatrixGraph
• improvement of method allow_multiple_edges #28309: improvement of method allow_multiple_edges
• Improve Breadth First Search in c_graph.pyx #31117: Improve Breadth First Search in c_graph.pyx
• Improve Depth First Search in c_graph.pyx #31129: Improve Depth First Search in c_graph.pyx

Here are some timings we try to improve along the way:

sage: import itertools
sage: def test_speed(n):
....:     for struct in ('dense', 'sparse'):
....:         print("\nnow doing {}".format(struct))
....:         G = Graph(n, data_structure=struct)
....:         edges = itertools.combinations(range(n), 2)
....:         print("adding edges")
....:         %time G.add_edges(edges)
....:         print("copy to dense")
....:         %time _ = copy(G)
....:         print("copy to sparse")
....:         %time _ = G.copy(sparse=True)
....:         print("copy to statice sparse")
....:         %time H = G.copy(immutable=True)
....:         edges = itertools.combinations(range(n), 2)
....:         print("delete edges")
....:         %time G.delete_edges(edges)
....:     
....:         print("copying static sparse to {}".format(struct))
....:         %time _ = H.copy(data_structure=struct)
....:   

sage: test_speed(1000)

now doing dense
adding edges
CPU times: user 169 ms, sys: 4 µs, total: 169 ms
Wall time: 169 ms
copy to dense
CPU times: user 2.14 s, sys: 0 ns, total: 2.14 s
Wall time: 2.14 s
copy to sparse
CPU times: user 2.44 s, sys: 0 ns, total: 2.44 s
Wall time: 2.44 s
copy to statice sparse
CPU times: user 2.75 s, sys: 3.61 ms, total: 2.75 s
Wall time: 2.75 s
delete edges
CPU times: user 613 ms, sys: 0 ns, total: 613 ms
Wall time: 613 ms
copying static sparse to dense
CPU times: user 282 ms, sys: 0 ns, total: 282 ms
Wall time: 282 ms

now doing sparse
adding edges
CPU times: user 434 ms, sys: 0 ns, total: 434 ms
Wall time: 435 ms
copy to dense
CPU times: user 619 ms, sys: 0 ns, total: 619 ms
Wall time: 619 ms
copy to sparse
CPU times: user 747 ms, sys: 3.84 ms, total: 750 ms
Wall time: 750 ms
copy to statice sparse
CPU times: user 997 ms, sys: 0 ns, total: 997 ms
Wall time: 997 ms
delete edges
CPU times: user 896 ms, sys: 0 ns, total: 896 ms
Wall time: 896 ms
copying static sparse to sparse
CPU times: user 582 ms, sys: 0 ns, total: 582 ms
Wall time: 582 ms

sage: test_speed(2000)

now doing dense
adding edges
CPU times: user 672 ms, sys: 0 ns, total: 672 ms
Wall time: 671 ms
copy to dense
CPU times: user 16.1 s, sys: 0 ns, total: 16.1 s
Wall time: 16.1 s
copy to sparse
CPU times: user 17.4 s, sys: 34.7 ms, total: 17.5 s
Wall time: 17.5 s
copy to statice sparse
CPU times: user 18.9 s, sys: 51.6 ms, total: 18.9 s
Wall time: 18.9 s
delete edges
CPU times: user 2.49 s, sys: 0 ns, total: 2.49 s
Wall time: 2.49 s
copying static sparse to dense
CPU times: user 1.18 s, sys: 0 ns, total: 1.18 s
Wall time: 1.18 s

now doing sparse
adding edges
CPU times: user 1.87 s, sys: 0 ns, total: 1.87 s
Wall time: 1.87 s
copy to dense
CPU times: user 2.64 s, sys: 0 ns, total: 2.64 s
Wall time: 2.64 s
copy to sparse
CPU times: user 3.21 s, sys: 47.8 ms, total: 3.26 s
Wall time: 3.26 s
copy to statice sparse
CPU times: user 4.25 s, sys: 36 ms, total: 4.28 s
Wall time: 4.28 s
delete edges
CPU times: user 3.86 s, sys: 0 ns, total: 3.86 s
Wall time: 3.86 s
copying static sparse to sparse
CPU times: user 2.55 s, sys: 0 ns, total: 2.55 s
Wall time: 2.55 s

CC: @dcoudert @kliem

Component: graph theory

Keywords: backends

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

[kliem]

comment:2

The idea is that in the end, most top level function should be handled in c_graph.pyx.
If possible, only the low level functions are done separate for each backend.

Once things are unified (as good as different backends allow), one should speed up things. E.g. the following is extremely slow:

sage: import itertools
sage: def test_speed(n):
....:     G = Graph(n, data_structure='dense')
....:     edges = itertools.combinations(range(n), 2)
....:     %time G.add_edges(edges)
....:     edges = itertools.combinations(range(n), 2)
....:     %time G.delete_edges(edges)
sage: test_speed(1000)
CPU times: user 175 ms, sys: 8 µs, total: 175 ms
Wall time: 175 ms
CPU times: user 574 ms, sys: 0 ns, total: 574 ms
Wall time: 574 ms

I got both things down to about 80 ms by calling add_edges on the top level and then actually using the unsafe methods wherever possible (if we already obtained the indices safely, there should be nothing preventing as from using unsafe methods). Similar for delete_edges.

[kliem]

comment:3

Adding this, because I missed it on my first try to optimize add_edges. This would have created a mistake in BipartiteGraph without a doctest catching on.

[dcoudert]

comment:6

just mentioned that #25465, #28865 are for the same issue.

[embray]

comment:8

Ticket retargeted after milestone closed

[mkoeppe]

comment:9

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.

[dcoudert]

comment:10

#22349 could also be part of this task.

[kliem]

comment:19

With #30776 and #30777 things are looking much better:

sage: test_speed(1000)                                                                                                                                                                                                                                                                                                                                                     

now doing dense
adding edges
CPU times: user 81.9 ms, sys: 0 ns, total: 81.9 ms
Wall time: 81.9 ms
copy to dense
CPU times: user 10.2 ms, sys: 0 ns, total: 10.2 ms
Wall time: 10.2 ms
copy to sparse
CPU times: user 89.5 ms, sys: 7.87 ms, total: 97.4 ms
Wall time: 97.1 ms
copy to statice sparse
CPU times: user 423 ms, sys: 11.9 ms, total: 435 ms
Wall time: 435 ms
delete edges
CPU times: user 79.1 ms, sys: 0 ns, total: 79.1 ms
Wall time: 79.1 ms
copying static sparse to dense
CPU times: user 81.3 ms, sys: 51 µs, total: 81.4 ms
Wall time: 81.4 ms

now doing sparse
adding edges
CPU times: user 169 ms, sys: 0 ns, total: 169 ms
Wall time: 169 ms
copy to dense
CPU times: user 158 ms, sys: 0 ns, total: 158 ms
Wall time: 158 ms
copy to sparse
CPU times: user 290 ms, sys: 0 ns, total: 290 ms
Wall time: 290 ms
copy to statice sparse
CPU times: user 544 ms, sys: 0 ns, total: 544 ms
Wall time: 544 ms
delete edges
CPU times: user 166 ms, sys: 0 ns, total: 166 ms
Wall time: 166 ms
copying static sparse to sparse
CPU times: user 187 ms, sys: 0 ns, total: 187 ms
Wall time: 187 ms
sage: test_speed(2000)                                                                                                                                                                                                                                                                                                                                                     

now doing dense
adding edges
CPU times: user 340 ms, sys: 0 ns, total: 340 ms
Wall time: 340 ms
copy to dense
CPU times: user 40.9 ms, sys: 0 ns, total: 40.9 ms
Wall time: 40.8 ms
copy to sparse
CPU times: user 396 ms, sys: 3.93 ms, total: 400 ms
Wall time: 400 ms
copy to statice sparse
CPU times: user 2 s, sys: 68 ms, total: 2.07 s
Wall time: 2.07 s
delete edges
CPU times: user 321 ms, sys: 32 µs, total: 321 ms
Wall time: 321 ms
copying static sparse to dense
CPU times: user 396 ms, sys: 0 ns, total: 396 ms
Wall time: 396 ms

now doing sparse
adding edges
CPU times: user 768 ms, sys: 0 ns, total: 768 ms
Wall time: 768 ms
copy to dense
CPU times: user 791 ms, sys: 0 ns, total: 791 ms
Wall time: 791 ms
copy to sparse
CPU times: user 1.32 s, sys: 48 ms, total: 1.36 s
Wall time: 1.36 s
copy to statice sparse
CPU times: user 2.48 s, sys: 0 ns, total: 2.48 s
Wall time: 2.48 s
delete edges
CPU times: user 825 ms, sys: 0 ns, total: 825 ms
Wall time: 825 ms
copying static sparse to sparse
CPU times: user 876 ms, sys: 0 ns, total: 876 ms
Wall time: 876 ms

[mkoeppe]

comment:23

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.