id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
28895 Meta ticket: Simplify and speed up graph backends gh-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
- #6604: Polish the use of iterators in C graphs
- #7720: Digraph.reverse() should be rewritten more efficiently ( not hard )
- #12387: Everything is not well with dense graph backends
- #12540: Graph library passes almost surelly erroneous calls without an exception
- #13730: Speed up some graph iterations
- #22349: Deprecate sorting of Graph vertices and edges by default
- #28259: graph add_edges/delete_edges are dramatically slow
- #28896: Graphs: Move common methods of backends to CGraph
- #28897: BipartiteGraph blindly trusts generic graphs
- #28904: Move reversed graph from backend to CGraph for sparse graphs
- #30641: equality of graphs is 60 times slower than equality of their list of edges
- #30665: Optimize edge iterator for graphs
- #30769: Unify graph backends
- #30753: Further improvements in method subgraph
- #30777: Improve deleting of edges of graphs
- use iterators for outgoing and ingoing arcs
- #31197: Use bitsets/binary matrix for edges of dense graphs
Possibly related tickets:
- #6604: Polish the use of iterators in C graphs
- #9143: Speed up graph generation using Cython
- #9301: Modified check_edge_label in the sparse graph backend to consider equals the same objects rather than objects with the same contents
- #22374: {c,sparse}_graph: systematically turn integer-like vertices into ints
- #24989: G.edges_incident returns edges with vertices swapped
- #25465, #28865: Memory error with graphs generators: JankoKharaghaniGraph and SquaredSkewHadamardMatrixGraph
- #28309: improvement of method allow_multiple_edges
- #31117: Improve Breadth 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
}}}" task new major sage-9.5 graph theory graphs, backends dcoudert gh-kliem N/A