#30769 closed enhancement (fixed)

Unify graph backends

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.3
Component: graph theory Keywords: graph backend
Cc: vdelecroix, dimpase, dcoudert, slelievre Merged in:
Authors: Jonathan Kliem Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 66b3dde (Commits, GitHub, GitLab) Commit: 66b3dde8bdfe64172a63586ae9112562e82f7e4e
Dependencies: #30665 Stopgaps:

Status badges

Description (last modified by slelievre)

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

Change History (9)

comment:1 follow-up: Changed 14 months ago by gh-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.

comment:2 Changed 14 months ago by gh-kliem

  • Status changed from new to needs_review

comment:3 in reply to: ↑ 1 Changed 14 months ago by slelievre

  • Cc slelievre added
  • Description modified (diff)

Replying to gh-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. : )

comment:4 Changed 14 months ago by gh-kliem

  • Milestone changed from sage-9.2 to sage-9.3

comment:5 Changed 14 months ago by git

  • Commit changed from 1fdeca29d73a475f1f8a28986c8e391abe4e48cc to c71a05eb8c373750f9a4f9a6e38078a42ab3f9e0

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

c71a05efix doctests

comment:6 Changed 14 months ago by git

  • Commit changed from c71a05eb8c373750f9a4f9a6e38078a42ab3f9e0 to 66b3dde8bdfe64172a63586ae9112562e82f7e4e

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

8beb573bitset capacity is +1 to last index
63a2f42reorganization
60623c6unify arc functions
a4f51c9change some ordering
2d9154aunify adding of edges
8eba711unify delete edges
aabe5a4typo
3489fa7some small optimziations
66b3ddefix doctests

comment:7 Changed 14 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

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

comment:8 Changed 14 months ago by gh-kliem

Thank you for reviewing.

comment:9 Changed 13 months ago by vbraun

  • Branch changed from u/gh-kliem/unify_graph_backends to 66b3dde8bdfe64172a63586ae9112562e82f7e4e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.