#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 borassi):
> > * 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?
You don't need to. This operation is done at each loop, and each loop
performs a BFS (that needs time O(m)), so you can afford to spend time
O(n) to find the right vertex. You can do it either when you update
bounds, or in a new line, for instance:
{{{
cdef uint_32 next = UINT32_MAX
for w in W:
LB[w] = max(LB[w], max(LB[v] - distances[w], distances[w]))
UB[w] = min(UB[w], LB[v] + distances[w])
if LB[w]==UB[w]:
W.remove(w)
else:
if next == UINT32_MAX or (iter % 2 == 0 and LB[w] < LB[next]) or
(iter % 2 == 1 and UB[w] > UB[next]):
next = w
}}}
Obviously, then you need to replace v = W.pop() with v = next, you need to
set next at the beginning (for instance, as the maximum degree vertex),
and you have to remove the line where you sort W.
> > 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?
No, this algorithm only works for graphs. For digraphs, you need [1] in
the case of strongly connected digraphs, [2] in general (anyway, if you
define the eccentricity of a vertex to be infinite if it cannot reach all
other vertices, the general case is easily solvable from the strongly
connected case).
In any case, before running the algorithm, you need to check that the
graph is undirected.
> Thanks for all the comments.
You are welcome! Thank you for implementing this nice algorithm!
![1] [http://www.sciencedirect.com/science/article/pii/S0304397515001644
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:7>
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.
