#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 borassi):
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.
First of all, congrats for the excellent running time! Some comments
follow (I think the first is important, while the others are only "style"
comments):
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).
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?
1. In the comment part, Section "ALGORITHM", I would add something to
explain what happens if k=0.
Hope it is useful!
Michele
--
Ticket URL: <http://trac.sagemath.org/ticket/18137#comment:29>
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.
