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 David Coudert, Dima Pasechnik 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 David Coudert

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 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_review → needs_work

Mereg conflict

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

Commit: 7addd5c7e4f8f1f79cc67d1ba41393a4e4a8c178 → 176c942be446b3eb8ccbc56285003f5128a48acd

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 (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 ?

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 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_deletion → 176c942be446b3eb8ccbc56285003f5128a48acd → fixed positive_review → closed
Note: See TracTickets for help on using tickets.