id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
17163 Speed improvement for DiGraph.in_degree ncohen "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" defect closed major sage-6.4 graph theory fixed jmantysalo Nathann Cohen David Coudert N/A 0bcb1b78e32614db88ea00658caf986eff07a3f1 0bcb1b78e32614db88ea00658caf986eff07a3f1