#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: | eaa6a3eccacf8f90064cde79febef149c7b8e5e8
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18137 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Hello,
> this is my first comment: please, forgive me if I make mistakes due to
my lack of experience, and I am willing to receive suggestions.
Your comments are rather good, actually.
> 1. bitset_union(seen,seen,next_layer): this operation takes time O(n),
and it is performed at each layer. This means that, if there are many
layers, then the running time might be O(n^2^) to perform a BFS, and
O(mn^2^) overall (for instance, if the input is a path). I would change
the code by memorizing the distances from the source, and making tests
with distances. Example: it takes more time to analyze a path of length
10,000 than a G(N,p) random graph with N=10,000 and p=0.001 (with about
100,000 edges).
HMmm.. Well, indeed when thinking of a long path this may actually make a
big difference. Do you feel like giving it a try and telling us about the
difference?
I believe that it may make performances worse in some case, though I do
not know by how much. Storing everything as a bitset (instead of storing
distances) also makes things more compact in memory, and the cpu cache
works better. Though again, I have no idea how much time that represents.
> 1. Only to improve readability of the code: why do you use
layer_current_beginning, layer_current_end, and layer_next_end? I would
rather use a variable for the start of the queue and another for the end
of the queue, as in a standard BFS. Is there any particular reason why
you do not do it?
I do not understand your question. What do you mean by "a variable for the
start of the que and another for the end of the queue"? This is precisely
what `layer_current_beginning` and `layer_current_end` do, in my
understanding.
> 1. In the comment part, Section "ALGORITHM", I would add something to
explain what happens if k=0.
In this case the sum is empty, and thus equal to 0. Do you think that it
should be emphasized?
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18137#comment:30>
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.
