#17163: Speed improvement for DiGraph.in_degree
----------------------------+---------------------------------
Reporter: ncohen | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.4
Component: graph theory | Keywords:
Merged in: | Authors: Nathann Cohen
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
----------------------------+---------------------------------
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
--
Ticket URL: <http://trac.sagemath.org/ticket/17163>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
