#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 | 003b73ee0cb4493614412de568aa9f2fb0e58ac8
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18864 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
> * 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).
This is true, but so far I don't know how to do this efficiently. Any
guess?
> * do you really need to store vector ecc? Can't it be replaced by LB or
UB?
Done
> * 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.
This is now handled directly in method `eccentricity`, plus I have some
easy test in method `c_eccentricity_bounds`.
> * `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.
Somehow done
> * 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?
Now returning `LB` of length `n`.
> * for i in range(n): UB[i] = INT32_MAX: can't you use memset?
Now yes since I changed types to uint32_t.
> 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).
Is it correct for both graphs and digraphs?
Thanks for all the comments.
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/18864#comment:6>
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.
