#18137: Centrality betweenness in Sage
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.6
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: | 421dc01c948b631dd227c17aeba0459080293b94
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/18137 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Hello,
> The advantage of using rationals is that it was exact!
And this is the very reason why I wrote both implementations.
I am not so sure that it is a very big problem, however, as the algorithm
will not add noise to noise like it can happen for PDE computations.
The current version of `centrality_betweenness`, from **NetworkX** shipped
with Sage, also computes on floats (in Python):
{{{
sage: import networkx
sage: networkx.algorithms.centrality.betweenness._accumulate_basic??
}}}
I wanted to check how **Boost** does it, but I was not able to locate the
source code (God, how can anyone read those files???).
(15 minutes later)
Here it is! Line 338 of:
http://boost.cvs.sourceforge.net/viewvc/boost/boost/boost/graph/betweenness_centrality.hpp?annotate=1.2.6.1
So the answer is that "it depends of dependency_type", which is.. A
template.
For **igraph** it is apparently a double too:
https://github.com/igraph/igraph/blob/master/src/centrality.c#L1685
https://github.com/igraph/igraph/blob/master/src/centrality.c#L1804
For **graph-tools** (last of the libraries compared on the link in the
ticket's description) it is apparently a double too, though I can't make
sure for I do not find the `get_betweenness` function
https://git.skewed.de/count0/graph-
tool/blob/master/src/graph_tool/centrality/__init__.py#L326
Sooooooo please don't just limit your argumentation to "not exact=BAD". I
care about this, and for this reason I implemented both (which definitely
took more than a couple of minutes as you can imagine), but I do believe
that for this kind of computations working on floats is not that bad, for
I know when the divisions occur and, well, we do not mind much.
I would personally be very happy to have both in Sage, with an easy flag
to switch from one implementation to the other. If you just checkout the
first of my commits you will see that only one variable need to be changed
so that double become rationals. My trouble is that using Cython's
preprocessor instructions requires to run `sage -b`, and we do not want
that.
I would also like to NOT have the same code copy/pasted twice, and to not
pay for the 'if' inside of the loops.
I would be happy to have both if there is a free (in terms of
computations) way to handle both at once, and a cheap (in term of lines of
code) way to have both.
So far I did not find any way out, and I thought that the best was to have
what everybody seemds interested in: computations on double (we can also
turn them into 'long double' if necessary).
Nathann
P.S.: I uploaded a commit with both versions so that it will be available
somewhere (and not on my computer only) if we ever need that
implementation. I did that on purpose, to have it archived somewhere.
--
Ticket URL: <http://trac.sagemath.org/ticket/18137#comment:12>
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.
