Opened 5 years ago
Closed 5 years ago
#17163 closed defect (fixed)
Speed improvement for DiGraph.in_degree
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | graph theory | Keywords: | |
Cc: | jmantysalo | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 0bcb1b7 (Commits) | Commit: | 0bcb1b78e32614db88ea00658caf986eff07a3f1 |
Dependencies: | Stopgaps: |
Description
As reported by Jori, the following is... unexpected:
sage: g = digraphs.RandomDirectedGNP(300,.2) sage: %timeit g.sinks() # vertices of outdegree 0 1000 loops, best of 3: 376 µs per loop sage: %timeit g.sources() # vertices of indegree 0 100 loops, best of 3: 7.78 ms per loop
With this patch:
sage: g = digraphs.RandomDirectedGNP(300,.2) sage: %timeit g.sinks() # vertices of outdegree 0 1000 loops, best of 3: 370 µs per loop sage: %timeit g.sources() # vertices of indegree 0 1000 loops, best of 3: 361 µs per loop
Cause:
This is because the function in_degree
was not implemented at the data structure level, but "abstractly" by iterating over all incoming edges of a vertices and counting them. This is bad, especially since any sensible backends already stores that information.
What the branch does:
1) Add a in_degree
function in the CGraph backend.
2) Add a in_degree
and out_degree
(empty) function in the GenericGraph
backend (the only point is to write somewhere that the in_degree/out_degree
functions should be implemented by all graph backends
3) Add a in_degree/out_degree
function to the NetworkX backend. This backend is only used in one doctest, and this is the only backend that did not have this function.
4) Because all backends now have the in_degree/out_degree
functions, it is now useless to 'check if the backend has the function' before calling it. As a result the code of DiGraph.in_degree/out_degree
is simplified.
Nathann
Change History (9)
comment:1 Changed 5 years ago by
- Branch set to u/ncohen/17163
- Status changed from new to needs_review
comment:2 Changed 5 years ago by
- Commit set to 303ad6cc6643b491f160b539c0750153a8158486
comment:3 Changed 5 years ago by
Seems to work; now top()
and bottom()
on posets take same time. This also explains why timings with #13223 where little strange.
Unfortunately I don't know enought Sage to be able to really review this.
comment:4 follow-up: ↓ 6 Changed 5 years ago by
- Reviewers set to David Coudert
The patch is working well. However, there are several places in src/sage/graphs/base/c_graph.pyx
where you have such instruction (this one from your patch):
cdef v_int = get_vertex(v, self.vertex_ints, self.vertex_labels, self._cg)
Shouldn't you specify the int type ?
comment:5 Changed 5 years ago by
- Commit changed from 303ad6cc6643b491f160b539c0750153a8158486 to 0bcb1b78e32614db88ea00658caf986eff07a3f1
comment:6 in reply to: ↑ 4 Changed 5 years ago by
Shouldn't you specify the int type ?
Indeed. I just did, thanks.
Nathann
comment:7 Changed 5 years ago by
- Status changed from needs_review to positive_review
All tests pass on src/sage/graphs/
, so I give positive review.
comment:8 Changed 5 years ago by
Thanks !
Nathann
comment:9 Changed 5 years ago by
- Branch changed from u/ncohen/17163 to 0bcb1b78e32614db88ea00658caf986eff07a3f1
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17163: Speed improvement for DiGraph.in_degree