Unify graph backends

[kliem]

This is a follow up to #28896.

We further unify the behavior of dense and sparse (dynamic) graph backends.

Adding and deleting edges now share common methods.

In particular, DenseCGraph and SparseCGraph also behave the same in the following way now:

• adding an arc will add both directions, if the graph is undirected
• deleting an arc will delete both directions, ...

Note that this ticket is also a step towards #28259:

Comparison:

sage: set_random_seed(0)
sage: edges = [(randint(0,1000), randint(0,1000)) for _ in range(100000)]
sage: import igraph
sage: g = igraph.Graph()
sage: g.add_vertices(1001)
sage: sleep(1)
sage: %time g.add_edges(edges)
CPU times: user 10.5 ms, sys: 0 ns, total: 10.5 ms
Wall time: 10.6 ms

Before:

sage: set_random_seed(0)
sage: edges = [(randint(0,1000), randint(0,1000)) for _ in range(100000)]
sage: D = DiGraph(multiedges=True, loops=True); D.add_vertices(range(1001))
sage: sleep(1)
sage: %time D.add_edges(edges)
CPU times: user 69 ms, sys: 38 µs, total: 69 ms
Wall time: 68.7 ms
sage: D = DiGraph(multiedges=False, loops=True, sparse=False); D.add_vertices(range(1001))
sage: sleep(1)
sage: %time D.add_edges(edges)
CPU times: user 32.3 ms, sys: 0 ns, total: 32.3 ms
Wall time: 32 ms

After:

sage: set_random_seed(0)
sage: edges = [(randint(0,1000), randint(0,1000)) for _ in range(100000)]
sage: D = DiGraph(multiedges=True, loops=True); D.add_vertices(range(1001))
sage: sleep(1)
sage: %time D.add_edges(edges)
CPU times: user 32.8 ms, sys: 38 µs, total: 32.8 ms
Wall time: 32.8 ms
sage: D = DiGraph(multiedges=False, loops=True, sparse=False); D.add_vertices(range(1001))
sage: sleep(1)
sage: %time D.add_edges(edges)
CPU times: user 14.6 ms, sys: 0 ns, total: 14.6 ms
Wall time: 14.6 ms

Depends on #30665

CC: @videlec @dimpase @dcoudert @slel

Component: graph theory

Keywords: graph backend

Author: Jonathan Kliem

Branch/Commit: 66b3dde

Reviewer: David Coudert

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

[kliem]

comment:1

Note that I waited about a second between creating the graphs and timing each time. If you hit the next time too fast, I got a slowdown in each case.

[slel]

comment:3

Replying to @kliem:

Note that I waited about a second between creating the graphs
and timing each time. If you hit the next %time too fast,
I got a slowdown in each case.

I added corresponding sleep(1) lines to the code blocks
in the ticket description. : )

[sagetrac-git]

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

c71a05e

fix doctests

[sagetrac-git]

Changed commit from 1fdeca2 to c71a05e

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8beb573	bitset capacity is +1 to last index
63a2f42	reorganization
60623c6	unify arc functions
a4f51c9	change some ordering
2d9154a	unify adding of edges
8eba711	unify delete edges
aabe5a4	typo
3489fa7	some small optimziations
66b3dde	fix doctests

[sagetrac-git]

Changed commit from c71a05e to 66b3dde

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:7

For me this patch is good to go. Thank you.

[kliem]

comment:8

Thank you for reviewing.

[vbraun]

Changed branch from u/gh-kliem/unify_graph_backends to 66b3dde