Opened 2 years ago

Closed 2 years ago

# Improve deleting of edges of graphs

Reported by: Owned by: gh-kliem critical sage-9.3 graph theory graph, delete edges dcoudert, dimpase Jonathan Kliem David Coudert N/A 176c942 176c942be446b3eb8ccbc56285003f5128a48acd #30769, #30776

### 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("delete edges")
....:         %time G.delete_edges(edges)
```

Before (#30769):

```sage: test_speed(200)

now doing dense
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
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
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
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
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
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
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
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.

### comment:1 Changed 2 years ago by gh-kliem

Status: new → needs_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 dcoudert

Component: geometry → graph theory → David Coudert needs_review → 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 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 dcoudert

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

Last edited 3 weeks ago by chapoton (previous) (diff)

### comment:5 Changed 2 years 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 2 years ago by vbraun

Status: positive_review → needs_work

Mereg conflict

### comment:7 Changed 2 years ago by git

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

 ​fb96022 `fix mistakes` ​776e38f `expose subgraph method to initialization/copying` ​7c6e1d5 `clean up` ​40bacf0 `documentation` ​2611e8a `outsource a function that can work more general` ​54d59ea `working version for subgraph check` ​bd9c48c `restructering` ​0347b17 `documentation` ​925a796 `merge in public/30776` ​176c942 `Merge 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 (to new definitions in `.pxd` at same place).

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

Version 0, edited 2 years ago by gh-kliem (next)

### comment:9 Changed 2 years 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 ?

Sure. Done.

### comment:11 Changed 2 years ago by gh-kliem

Status: needs_work → 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 2 years ago by dcoudert

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

### comment:13 Changed 2 years ago by vbraun

Branch: u/gh-kliem/speed_up_edge_deletion → 176c942be446b3eb8ccbc56285003f5128a48acd → fixed positive_review → closed
Note: See TracTickets for help on using tickets.