#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 | da0260dca9b43d96b47bcae2ba79a2b8819896ec
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18864 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by borassi):
Sorry, I forgot a few things:
{{{
sage: eccentricity(digraphs.Path(2), method='standard')
[+Infinity, +Infinity]
}}}
I think that the eccentricity of the first vertex should be 1.
> Do you know similar algorithm for digraphs?
Yep, the papers [1,2] from previous comments generalize this method to
directed graphs (actually, they stop the computation as soon as diameter
and radius are found, but they work also to compute all eccentricities).
Intuitively, if the directed graph is strongly connected, you keep forward
and backward eccentricities for all vertices (backward eccentricity means
eccentricity in the reverse graph). Then, you need four bounds (UF, LF,
UB, LB for forward and backward eccentricity, respectively), and at each
step you perform a forward and backward visit from v. Then, you bound
UF[w] = d(w,v)+eccF(v)
LF[w] = max(d(w,v), eccF(v)-d(v, w))
UB[w] = eccB(v)+d(v,w)
LB[w] = max(d(w,v), eccB(v)-d(w,v)).
The remainder of the algorithm is quite similar to the existing one.
If you want to implement also the directed algorithm, or if this
"intuitive idea" is not clear, please ask and I will provide more details.
--
Ticket URL: <http://trac.sagemath.org/ticket/18864#comment:14>
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.
