#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):
Little bug: you set `next_v = W[0]` before computing bounds, but then
`W[0]` might be eliminated from `W`, and you end up with a non-existing
`next_v`. Example:
{{{
sage: from sage.graphs.distances_all_pairs import eccentricity
sage: tmp = eccentricity(graphs.PathGraph(50), method='bounds')
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
<ipython-input-3-98d52329e964> in <module>()
----> 1 tmp = eccentricity(g, method='bounds')
/home/michele/Programmi/sage/src/sage/graphs/distances_all_pairs.pyx in
sage.graphs.distances_all_pairs.eccentricity
(/home/michele/Programmi/sage/src/build/cythonized/sage/graphs/distances_all_pairs.c:11580)()
891 cdef uint32_t * ecc
892 if method=="bounds":
--> 893 ecc = c_eccentricity_bounding(G)
894 elif method=="standard":
895 ecc = c_eccentricity(G)
/home/michele/Programmi/sage/src/sage/graphs/distances_all_pairs.pyx in
sage.graphs.distances_all_pairs.c_eccentricity_bounding
(/home/michele/Programmi/sage/src/build/cythonized/sage/graphs/distances_all_pairs.c:10862)()
787
788 v = next_v
--> 789 W.remove(v)
790 cpt += 1
791
ValueError: list.remove(x): x not in list
}}}
Moreover, I don't like that if you ask for the eccentricity of a directed
graph, then the default algorithm does not work.
{{{
sage: tmp = eccentricity(digraphs.Path(10))
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
<ipython-input-5-f1441926fc79> in <module>()
----> 1 tmp = eccentricity(digraphs.Path(Integer(10)))
/home/michele/Programmi/sage/src/sage/graphs/distances_all_pairs.pyx in
sage.graphs.distances_all_pairs.eccentricity
(/home/michele/Programmi/sage/src/build/cythonized/sage/graphs/distances_all_pairs.c:11449)()
883 elif G.is_directed():
884 if method=='bounds':
--> 885 raise ValueError("The 'bounds' method only works on
undirected graphs.")
886 elif not G.is_strongly_connected():
887 return [Infinity]*n
ValueError: The 'bounds' method only works on undirected graphs.
}}}
Apart from these, build is OK, documentation is OK, and I still have to
perform all tests (tests from this package are OK).
Have fuuuuuuuuuuuun!
Michele
--
Ticket URL: <http://trac.sagemath.org/ticket/18864#comment:13>
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.
