#18864: New method for the eccentricity
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.8
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | bb2dd5c3860d47e59bb1258df91465f9c22d1281
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18864 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by borassi):
Hello!
Cool! Takes and Kosters algorithm! I really like the way it works (since
it is also the base of one of my algorithms [1,2]) :)
I have a few doubts about the code:
* if I understood well your code, the starting vertices of the BFSes are
chosen in decreasing order of degree. This way, upper bounds are quite
good, but lower bounds are not very good, and the running time does not
decrease much. Instead, you should alternate between vertices where UB is
high and vertices where LB is low (if you want, you can also use degrees
as tie-break).
* do you really need to store vector ecc? Can't it be replaced by LB or
UB?
* I think you should handle separately the case when the graph is not
connected. Otherwise, the first visits will start from the giant
component, and for each vertex in the giant component the lower bound will
be `ecc[v] - distances[w]=INT32_MAX-distances[w]`, and the upper bound
will be `INT32_MAX`, so you will need a lot of BFSes, probably, instead of
simply returning an array of `INT32_MAX` after the first BFS.
* `ecc[v] = INT32_MAX if tmp>n else tmp`: I think it is better to use an
integer variable named `eccv`, since you use it O(n) times later.
* you return a vector `ecc` of length `3n`: why don't you use two
different vectors for `LB` and `UB`, so that they are freed when the
function returns?
* for i in range(n): UB[i] = INT32_MAX: can't you use memset?
Other, more general, remarks:
* this algorithm can be used to compute the radius (resp. diameter), by
stopping as soon as LB is big enough (resp. UB is small enough). I think
you could add a flag to stop the execution before, in case only the radius
or the diameter is needed.
* maybe you could add this algorithm to the list of diameter algorithms
(see previous remark).
[1] http://www.sciencedirect.com/science/article/pii/S0304397515001644
[2] !http://link.springer.com/chapter/10.1007%2F978-3-319-07890-8_5
--
Ticket URL: <http://trac.sagemath.org/ticket/18864#comment:4>
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.
