Opened 14 months ago
Closed 13 months ago
#30769 closed enhancement (fixed)
Unify graph backends
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.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: 
Description (last modified by )
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 followup: ↓ 3 Changed 14 months ago by
comment:2 Changed 14 months ago by
 Status changed from new to needs_review
comment:3 in reply to: ↑ 1 Changed 14 months ago by
 Cc slelievre added
 Description modified (diff)
Replying to ghkliem:
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
 Milestone changed from sage9.2 to sage9.3
comment:5 Changed 14 months ago by
 Commit changed from 1fdeca29d73a475f1f8a28986c8e391abe4e48cc to c71a05eb8c373750f9a4f9a6e38078a42ab3f9e0
Branch pushed to git repo; I updated commit sha1. New commits:
c71a05e  fix doctests

comment:6 Changed 14 months ago by
 Commit changed from c71a05eb8c373750f9a4f9a6e38078a42ab3f9e0 to 66b3dde8bdfe64172a63586ae9112562e82f7e4e
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

comment:7 Changed 14 months ago by
 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
Thank you for reviewing.
comment:9 Changed 13 months ago by
 Branch changed from u/ghkliem/unify_graph_backends to 66b3dde8bdfe64172a63586ae9112562e82f7e4e
 Resolution set to fixed
 Status changed from positive_review to closed
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.