#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: dcoudert, dimpase 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 14 months ago by gh-kliem

  • Status changed from new to needs_review

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

comment:2 Changed 14 months ago by dcoudert

  • Component changed from geometry to graph theory
  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_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 14 months 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 14 months ago by dcoudert

  • Cc dimpase added

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

@Dima: any advise ?

comment:5 Changed 14 months ago by dimpase

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 13 months ago by vbraun

  • Status changed from positive_review to needs_work

Mereg conflict

comment:7 Changed 13 months ago by git

  • Commit changed from 7addd5c7e4f8f1f79cc67d1ba41393a4e4a8c178 to 176c942be446b3eb8ccbc56285003f5128a48acd

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 13 months ago by gh-kliem

  • Dependencies changed from #30769 to #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 13 months ago by gh-kliem (previous) (diff)

comment:9 Changed 13 months ago by dcoudert

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 13 months ago by gh-kliem

Sure. Done.

comment:11 Changed 13 months ago by gh-kliem

  • Status changed from needs_work to positive_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 12 months ago by dcoudert

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

comment:13 Changed 12 months ago by vbraun

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