#18864: New method for the eccentricity of undirected graphs
-------------------------+-------------------------------------------------
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 | a3717b73c811ff702345a186b679df4b99e725fa
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18864 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by borassi):
I absolutely agree to put the directed case in another ticket, because it
is much more complicated.
Unfortunately, there is still a bug... When you iterate over W (line 807),
inside the loop you modify W, and the loop does not work, anymore. For
instance:
{{{
17:57:03 michele@Lena:~/Programmi/sage$ ./sage -t
src/sage/graphs/generic_graph.py
too many failed tests, not using stored timings
Running doctests with ID 2015-07-12-17-57-08-078c3900.
Git branch: t/18864/public/18864
Using --optional=mpir,python2,sage,scons
Doctesting 1 file.
sage -t src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 12685, in
sage.graphs.generic_graph.GenericGraph.eccentricity
Failed example:
G.eccentricity()
Exception raised:
Traceback (most recent call last):
File "/home/michele/Programmi/sage/local/lib/python2.7/site-
packages/sage/doctest/forker.py", line 496, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/home/michele/Programmi/sage/local/lib/python2.7/site-
packages/sage/doctest/forker.py", line 858, in compile_and_execute
exec(compiled, globs)
File "<doctest
sage.graphs.generic_graph.GenericGraph.eccentricity[1]>", line 1, in
<module>
G.eccentricity()
File "/home/michele/Programmi/sage/local/lib/python2.7/site-
packages/sage/graphs/generic_graph.py", line 12712, in eccentricity
return eccentricity(self, method='standard' if self.is_directed()
else 'bounds')
File "sage/graphs/distances_all_pairs.pyx", line 899, in
sage.graphs.distances_all_pairs.eccentricity
(/home/michele/Programmi/sage/src/build/cythonized/sage/graphs/distances_all_pairs.c:11517)
ecc = c_eccentricity_bounding(G)
File "sage/graphs/distances_all_pairs.pyx", line 789, in
sage.graphs.distances_all_pairs.c_eccentricity_bounding
(/home/michele/Programmi/sage/src/build/cythonized/sage/graphs/distances_all_pairs.c:10860)
W.remove(v)
ValueError: list.remove(x): x not in list
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 12704, in
sage.graphs.generic_graph.GenericGraph.eccentricity
Failed example:
sig_on_count() # check sig_on/off pairings (virtual doctest)
Expected:
0
Got:
1
**********************************************************************
1 item had failures:
2 of 13 in sage.graphs.generic_graph.GenericGraph.eccentricity
[2666 tests, 2 failures, 18.28 s]
----------------------------------------------------------------------
sage -t src/sage/graphs/generic_graph.py # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 18.9 seconds
cpu time: 16.9 seconds
cumulative wall time: 18.3 seconds
}}}
Another correction in the documentation:
{{{
INPUT:
- ``G`` -- a Graph or a DiGraph.
- ``method`` -- (default: 'standard') name of the method used to
compute the
eccentricity of the vertices. Available methods are `'standard'`
which
performs a BFS from each vertex and `'bounds'` which uses the fast
algorithm proposed in [TK13]_ for undirected graphs.
EXAMPLE:
sage: from sage.graphs.distances_all_pairs import eccentricity
sage: g = graphs.PetersenGraph()
sage: eccentricity(g)
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
}}}
I think you should write `EXAMPLE::` instead of `EXAMPLE:`. Since we are
already here, I would also add {{{``}}} instead of {{{`}}} in the name of
the possible methods (standard, bounds). The modification should be as
follows.
{{{
``method`` -- (default: ``'standard'``) name of the method used to compute
the
eccentricity of the vertices. Available methods are ``'standard'``
which
performs a BFS from each vertex and ``'bounds'`` which uses the fast
algorithm proposed in [TK13]_ for undirected graphs.
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18864#comment:19>
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.
