Opened 2 years ago

Closed 2 years ago

#30777 closed enhancement (fixed)

Improve deleting of edges of graphs

Reported by: gh-kliem Owned by:
Priority: critical Milestone: sage-9.3
Component: graph theory Keywords: graph, delete edges
Cc: David Coudert, Dima Pasechnik Merged in:
Authors: Jonathan Kliem Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 176c942 (Commits, GitHub, GitLab) Commit: 176c942be446b3eb8ccbc56285003f5128a48acd
Dependencies: #30769, #30776 Stopgaps:

Status badges

Description

As a follow up to #30769, we improve deleting edges.

Comparison:

sage: import itertools 
....: def test_speed(n): 
....:     for struct in ('dense', 'sparse', 'sparse labeled', 'sparse labeled multiedge'): 
....:         print("\nnow doing {}".format(struct)) 
....:         if struct == "sparse labeled": 
....:             struct = "sparse" 
....:             multiedge=False 
....:             labeled = True 
....:         elif struct == "sparse labeled multiedge": 
....:             struct = 'sparse' 
....:             multiedge=True 
....:             labeled = True 
....:         else: 
....:             multiedge=False 
....:             labeled = False 
....:         G = Graph(n, data_structure=struct, multiedges=multiedge) 
....:         edges = list(itertools.combinations(range(n), 2)) 
....:         if labeled: 
....:             if multiedge: 
....:                 m = 10 
....:             else: 
....:                 m = 1 
....:             edges = [(a,b,"{}.{}.{}".format(a,b,i)) for a,b in edges for i in range(m)] 
....:         print("adding edges") 
....:         %time G.add_edges(edges) 
....:         print("delete edges") 
....:         %time G.delete_edges(edges) 

Before (#30769):

sage: test_speed(200)                                                                                                                                                                                                                                                                                                                                                      

now doing dense
adding edges
CPU times: user 2.17 ms, sys: 220 µs, total: 2.39 ms
Wall time: 2.39 ms
delete edges
CPU times: user 24.2 ms, sys: 32 µs, total: 24.2 ms
Wall time: 24 ms

now doing sparse
adding edges
CPU times: user 5.76 ms, sys: 0 ns, total: 5.76 ms
Wall time: 5.71 ms
delete edges
CPU times: user 25.6 ms, sys: 0 ns, total: 25.6 ms
Wall time: 25.6 ms

now doing sparse labeled
adding edges
CPU times: user 3.94 ms, sys: 3.98 ms, total: 7.92 ms
Wall time: 7.92 ms
delete edges
CPU times: user 118 ms, sys: 0 ns, total: 118 ms
Wall time: 118 ms

now doing sparse labeled multiedge
adding edges
CPU times: user 47.9 ms, sys: 12 ms, total: 59.9 ms
Wall time: 59.9 ms
delete edges
CPU times: user 9.76 s, sys: 639 µs, total: 9.76 s
Wall time: 9.76 s

After:

sage: test_speed(200)                                                                                                                                                                                                                                                                                                                                                      

now doing dense
adding edges
CPU times: user 2.54 ms, sys: 0 ns, total: 2.54 ms
Wall time: 2.54 ms
delete edges
CPU times: user 2.47 ms, sys: 0 ns, total: 2.47 ms
Wall time: 2.47 ms

now doing sparse
adding edges
CPU times: user 5.73 ms, sys: 67 µs, total: 5.8 ms
Wall time: 5.83 ms
delete edges
CPU times: user 428 µs, sys: 3.67 ms, total: 4.1 ms
Wall time: 4.1 ms

now doing sparse labeled
adding edges
CPU times: user 8.14 ms, sys: 8 µs, total: 8.15 ms
Wall time: 8.02 ms
delete edges
CPU times: user 8.16 ms, sys: 0 ns, total: 8.16 ms
Wall time: 8.11 ms

now doing sparse labeled multiedge
adding edges
CPU times: user 58.3 ms, sys: 0 ns, total: 58.3 ms
Wall time: 58.3 ms
delete edges
CPU times: user 150 ms, sys: 0 ns, total: 150 ms
Wall time: 150 ms

Note that in particular deletion of edges in a multiedge graph was truly not working before: There was a loop through all edge labels, which slowed down everything. Not just for a complete graph.

Change History (13)

comment:1 Changed 2 years ago by gh-kliem

Status: newneeds_review

I marked it as critical, because of the huge improvement when deleting labeled edges in a multiedge graph.

comment:2 Changed 2 years ago by David Coudert

Component: geometrygraph theory
Reviewers: David Coudert
Status: needs_reviewpositive_review

This is really impressive. With this ticket, sage -tp src/sage/graphs/ takes 60s less on my (slow) laptop than with 9.2.rc2 only.

As I said for other tickets, it's not easy to check the code due to the chain of tickets. We will certainly have to do some cleaning when all these tickets will be merged.

LGTM.

comment:3 Changed 2 years ago by gh-kliem

There is a merge conflict with #30776 or the previous ticket.

A trivial one, as both are trying to add something in the same line in c_graph.pxd.

Should I take care of it and make it a long chain of dependencies or wait?

comment:4 Changed 2 years ago by David Coudert

Cc: Dima Pasechnik added

I don't know which is best to quickly get all these tickets in 9.3.beta..

@Dima: any advise ?

comment:5 Changed 2 years ago by Dima Pasechnik

well, make 9.2 happen sooner than later. Berliners of course have an advantage here - they can buy Volker a lunch/coffee :-)

comment:6 Changed 2 years ago by Volker Braun

Status: positive_reviewneeds_work

Mereg conflict

comment:7 Changed 2 years ago by git

Commit: 7addd5c7e4f8f1f79cc67d1ba41393a4e4a8c178176c942be446b3eb8ccbc56285003f5128a48acd

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

fb96022fix mistakes
776e38fexpose subgraph method to initialization/copying
7c6e1d5clean up
40bacf0documentation
2611e8aoutsource a function that can work more general
54d59eaworking version for subgraph check
bd9c48crestructering
0347b17documentation
925a796merge in public/30776
176c942Merge branch 'develop' of git://trac.sagemath.org/sage into u/gh-kliem/speed_up_edge_deletion

comment:8 Changed 2 years ago by gh-kliem

Dependencies: #30769#30769, #30776

I pulled in #30776 and fixed the trivial merge conflict (two new definitions in .pxd at same place).

It is not clear to me, why both #30776 and #30777 were marked as merge conflict.

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:9 Changed 2 years ago by David Coudert

It's not clear to me too. I can merge #30776 without conflict. May be we can set back #30776 to positive review, and wait until it is merged before setting this one to positive ?

comment:10 Changed 2 years ago by gh-kliem

Sure. Done.

comment:11 Changed 2 years ago by gh-kliem

Status: needs_workpositive_review

#30776 has been merged. I don't think there is a merge conflict anymore.

I think that #30776 and #30777 were both tried to be merged at once and both of them rejected. With #30777 based on #30776 it should be fine (and it really was only the one desclaration in the header at the same location).

comment:12 Changed 2 years ago by David Coudert

I tried successfully this ticket over 9.3.beta2 which includes #30776

comment:13 Changed 2 years ago by Volker Braun

Branch: u/gh-kliem/speed_up_edge_deletion176c942be446b3eb8ccbc56285003f5128a48acd
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.