Opened 7 years ago
Closed 7 years ago
#18864 closed enhancement (fixed)
New method for the eccentricity of undirected graphs
Reported by:  David Coudert  Owned by:  

Priority:  minor  Milestone:  sage6.8 
Component:  graph theory  Keywords:  
Cc:  Nathann Cohen, Michele Borassi  Merged in:  
Authors:  David Coudert  Reviewers:  Michele Borassi 
Report Upstream:  N/A  Work issues:  
Branch:  ce9d265 (Commits, GitHub, GitLab)  Commit:  ce9d26556e5b1a69002e1a5165933e51ddfc7c05 
Dependencies:  Stopgaps: 
Description (last modified by )
This patch implements the algorithm proposed in [1] for computing the eccentricity of all vertices of a connected undirected unweighted graph. It can be faster than the standard algorithm.
sage: from sage.graphs.distances_all_pairs import eccentricity sage: G = graphs.PetersenGraph() sage: %time _= eccentricity(G, method='standard') CPU times: user 299 µs, sys: 75 µs, total: 374 µs Wall time: 361 µs sage: %time _= eccentricity(G, method='bounds') CPU times: user 218 µs, sys: 29 µs, total: 247 µs Wall time: 235 µs sage: G = graphs.RandomBarabasiAlbert(10000,2) sage: %time _= eccentricity(G, method='standard') CPU times: user 2.78 s, sys: 7.8 ms, total: 2.78 s Wall time: 2.79 s sage: %time _= eccentricity(G, method='bounds') CPU times: user 1.66 s, sys: 8.06 ms, total: 1.67 s Wall time: 1.67 s
Similar method for directed graphs and weighted (di)graphs can be the object of future tickets.
[1] F. W. Takes and W. A. Kosters. Computing the eccentricity distribution of large graphs. *Algorithms* 6:100118 (2013) http://dx.doi.org/10.3390/a6010100
Change History (32)
comment:1 Changed 7 years ago by
Branch:  → public/18864 

comment:2 Changed 7 years ago by
Commit:  → bb2dd5c3860d47e59bb1258df91465f9c22d1281 

comment:3 Changed 7 years ago by
Cc:  Nathann Cohen Michele Borassi added 

Status:  new → needs_review 
Type:  PLEASE CHANGE → enhancement 
Let me know if you like it. David.
comment:4 followup: 6 Changed 7 years ago by
Hello!
Cool! Takes and Kosters algorithm! I really like the way it works (since it is also the base of one of my algorithms [1,2]) :)
I have a few doubts about the code:
 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 tiebreak).
 do you really need to store vector ecc? Can't it be replaced by LB or UB?
 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_MAXdistances[w]
, and the upper bound will beINT32_MAX
, so you will need a lot of BFSes, probably, instead of simply returning an array ofINT32_MAX
after the first BFS. ecc[v] = INT32_MAX if tmp>n else tmp
: I think it is better to use an integer variable namedeccv
, since you use it O(n) times later. you return a vector
ecc
of length3n
: why don't you use two different vectors forLB
andUB
, so that they are freed when the function returns?  for i in range(n): UB[i] = INT32_MAX: can't you use memset?
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).
[1] http://www.sciencedirect.com/science/article/pii/S0304397515001644
[2] http://link.springer.com/chapter/10.1007%2F9783319078908_5
comment:5 Changed 7 years ago by
Commit:  bb2dd5c3860d47e59bb1258df91465f9c22d1281 → 003b73ee0cb4493614412de568aa9f2fb0e58ac8 

comment:6 followup: 7 Changed 7 years ago by
 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 tiebreak).
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_MAXdistances[w]
, and the upper bound will beINT32_MAX
, so you will need a lot of BFSes, probably, instead of simply returning an array ofINT32_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 namedeccv
, since you use it O(n) times later.
Somehow done
 you return a vector
ecc
of length3n
: why don't you use two different vectors forLB
andUB
, 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.
comment:7 Changed 7 years ago by
 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 tiebreak).
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
![2] http://link.springer.com/chapter/10.1007%2F9783319078908_5
comment:8 Changed 7 years ago by
I have implemented a new version of the next node selection.
Concerning the possible use for diameter and centers computation, since I don't know yet how to do it, I prefer to let it for another patch. Also, so far the eccentricity of all the vertices of non (strongly) connected (di)graphs is set to infinity.
comment:9 Changed 7 years ago by
Commit:  003b73ee0cb4493614412de568aa9f2fb0e58ac8 → 873f62d1113634784413c7995e6f78cc7221d702 

Branch pushed to git repo; I updated commit sha1. New commits:
873f62d  trac #18864: new next vertex selection process

comment:10 Changed 7 years ago by
Hellooooo!
Great, now the algorithm should be much faster!
I think there is still a problem with directed graphs: the TakesKosters algorithm works only on undirected graphs, so I think you should add a ValueError
if the user asks the TakesKosters algorithm on directed graphs. I would add at the top of c_eccentricity_bounding
if G.is_directed(): raise ValueError("The bounds method only works on undirected graphs.")
After you correct this, I will try to perform a more extensive testing, and I will provide a positive review!
comment:11 Changed 7 years ago by
Commit:  873f62d1113634784413c7995e6f78cc7221d702 → da0260dca9b43d96b47bcae2ba79a2b8819896ec 

comment:12 followup: 14 Changed 7 years ago by
Should be OK now. Do you know similar algorithm for digraphs?
comment:13 Changed 7 years ago by
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 nonexisting 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) <ipythoninput398d52329e964> 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) <ipythoninput5f1441926fc79> 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
comment:14 Changed 7 years ago by
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.
comment:15 Changed 7 years ago by
Commit:  da0260dca9b43d96b47bcae2ba79a2b8819896ec → 554c5099f8b47cef74a13cd968223c9288264424 

Branch pushed to git repo; I updated commit sha1. New commits:
554c509  trac #18864: implement reviewer's comments

comment:16 Changed 7 years ago by
Commit:  554c5099f8b47cef74a13cd968223c9288264424 → f48a33e012a0187ceea3b3011909342dc5cb1375 

Branch pushed to git repo; I updated commit sha1. New commits:
f48a33e  trac #18864: minor corrections

comment:17 Changed 7 years ago by
Commit:  f48a33e012a0187ceea3b3011909342dc5cb1375 → a3717b73c811ff702345a186b679df4b99e725fa 

Branch pushed to git repo; I updated commit sha1. New commits:
a3717b7  trac #18864: improve behavior with directed graphs

comment:18 Changed 7 years ago by
Description:  modified (diff) 

Summary:  New method for the eccentricity → New method for the eccentricity of undirected graphs 
I have implemented requested changes. However, I propose to restrict this patch to undirected graph and to consider directed graphs in another ticket. Best, David.
comment:19 Changed 7 years ago by
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 20150712175708078c3900. 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/sitepackages/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/sitepackages/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/sitepackages/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.
comment:20 Changed 7 years ago by
Commit:  a3717b73c811ff702345a186b679df4b99e725fa → f621777db49299ce66bf8663795ad79453d4e43e 

Branch pushed to git repo; I updated commit sha1. New commits:
f621777  trac #18864: corrections and improved doc

comment:21 Changed 7 years ago by
Hello Michele,
I have implemented your suggestions. In particular I'm no longer using list W but a bitset instead.
Best.
comment:22 Changed 7 years ago by
Hello!
I am a bit puzzled by the use of bitset (probably because I know very little about it). You use the same bitset both for the BFS and to keep track of vertices in W. Hence, if the graph is connected, when you perform while w!=1:
the bitset contains everything and you iterate over all vertices. Why don't you simply use for w in range(n):
? You can then replace the outer while loop with while next_v!=UINT32_MAX:
, I think.
Otherwise, maybe you should use two different bitsets.
Am I missing something?
Michele
comment:23 Changed 7 years ago by
Commit:  f621777db49299ce66bf8663795ad79453d4e43e → 80cb89935d8eb8288d6659d7c73d8c05ee1c9411 

Branch pushed to git repo; I updated commit sha1. New commits:
80cb899  trac #18864: correct version

comment:25 Changed 7 years ago by
Status:  needs_review → positive_review 

Ok, for me now the patch is good to go.
I have run the doctest for the whole Sage, and I got an error, but it is probably not related to this ticket.
sage t long src/sage/interfaces/expect.py ********************************************************************** File "src/sage/interfaces/expect.py", line 825, in sage.interfaces.expect.Expect._eval_line Failed example: singular.interrupt(timeout=3) # sometimes very slow (up to 60s on sage.math, 2012) Expected: False Got: True **********************************************************************
Indeed, I run again the same doctest and it worked.
Last thing: if you have time, you just wrote
if LB[w]==UB[w]: continue elif ... do something
Maybe it is better to write
if LB[w]==UB[w] and (...): do something
Anyway, I think you can also leave it as it is.
Thank you very much, David!
comment:26 Changed 7 years ago by
Reviewers:  → Michele Borassi 

Thanks for the review. I have added your name as a reviewer (mandatory).
When LB[w]==UB[w]
, we don't want to change next_v
. So the continue
statement seems appropriate. The alternative is to have if LB[w]!=UB[w] and (next_v==UINT32_MAX or (cpt%2==0 and LB[w]<LB[next_v]) or (cpt%2==1 and UB[w]>UB[next_v])):
which is harder to read.
comment:27 Changed 7 years ago by
Status:  positive_review → needs_work 

Can you guys settle on a pattern where you return Sage integers everywhere? Not only would that then work on 32bit as well, it would also give Sage a consistent user interface. graph.radius().factor()
should just work.
sage t long src/sage/graphs/distances_all_pairs.pyx ********************************************************************** File "src/sage/graphs/distances_all_pairs.pyx", line 835, in sage.graphs.distances_all_pairs.eccentricity Failed example: eccentricity(g) Expected: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] Got: [2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L] ********************************************************************** File "src/sage/graphs/distances_all_pairs.pyx", line 854, in sage.graphs.distances_all_pairs.eccentricity Failed example: eccentricity(g, method='standard') Expected: [2, +Infinity, +Infinity] Got: [2L, +Infinity, +Infinity] ********************************************************************** 1 item had failures: 2 of 18 in sage.graphs.distances_all_pairs.eccentricity [82 tests, 2 failures, 0.20 s] sage t long src/sage/graphs/dot2tex_utils.py [4 tests, 0.06 s] sage t long src/sage/graphs/generators/__init__.py [0 tests, 0.00 s] sage t long src/sage/graphs/generators/basic.py ********************************************************************** File "src/sage/graphs/generators/basic.py", line 60, in sage.graphs.generators.basic.BullGraph Failed example: g.radius(); g.diameter(); g.girth() Expected: 2 3 3 Got: 2L 3 3 ********************************************************************** File "src/sage/graphs/generators/basic.py", line 130, in sage.graphs.generators.basic.ButterflyGraph Failed example: G.radius() Expected: 1 Got: 1L ********************************************************************** 2 items had failures: 1 of 14 in sage.graphs.generators.basic.BullGraph 1 of 11 in sage.graphs.generators.basic.ButterflyGraph [191 tests, 2 failures, 16.25 s] sage t long src/sage/graphs/digraph_generators.py [81 tests, 5.09 s] sage t long src/sage/graphs/generators/chessboard.py [44 tests, 1.04 s] sage t long src/sage/graphs/generators/degree_sequence.py [23 tests, 1.11 s] sage t long src/sage/geometry/triangulation/point_configuration.py [202 tests, 23.07 s] sage t long src/sage/graphs/generators/intersection.py [71 tests, 0.35 s] sage t long src/sage/graphs/generators/platonic_solids.py [44 tests, 4.55 s] sage t long src/sage/graphs/generators/families.py ********************************************************************** File "src/sage/graphs/generators/families.py", line 815, in sage.graphs.generators.families.FriendshipGraph Failed example: G.radius() Expected: 1 Got: 1L ********************************************************************** 1 item had failures: 1 of 22 in sage.graphs.generators.families.FriendshipGraph [250 tests, 1 failure, 22.30 s] sage t long src/sage/geometry/triangulation/base.pyx [171 tests, 35.66 s] sage t long src/sage/graphs/generators/world_map.py [4 tests, 0.01 s] sage t long src/sage/graphs/generators/random.py [71 tests, 5.22 s] sage t long src/sage/graphs/generic_graph_pyx.pxd [0 tests, 0.00 s] sage t long src/sage/graphs/generic_graph_pyx.pyx [79 tests, 2.49 s] sage t long src/sage/graphs/generators/smallgraphs.py ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 1302, in sage.graphs.generators.smallgraphs.BrinkmannGraph Failed example: G.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 1650, in sage.graphs.generators.smallgraphs.MeredithGraph Failed example: g.radius() Expected: 7 Got: 7L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 1701, in sage.graphs.generators.smallgraphs.KittellGraph Failed example: g.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 1808, in sage.graphs.generators.smallgraphs.ChvatalGraph Failed example: G.radius(); G.diameter(); G.girth() Expected: 2 2 4 Got: 2L 2 4 ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 2058, in sage.graphs.generators.smallgraphs.DyckGraph Failed example: G.radius() Expected: 5 Got: 5L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 2129, in sage.graphs.generators.smallgraphs.HortonGraph Failed example: g.radius() Expected: 10 Got: 10L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 2372, in sage.graphs.generators.smallgraphs.ErreraGraph Failed example: G.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 2581, in sage.graphs.generators.smallgraphs.FranklinGraph Failed example: G.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 2697, in sage.graphs.generators.smallgraphs.GoldnerHararyGraph Failed example: G.radius() Expected: 2 Got: 2L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 2821, in sage.graphs.generators.smallgraphs.GrotzschGraph Failed example: G.radius() Expected: 2 Got: 2L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 2943, in sage.graphs.generators.smallgraphs.HerschelGraph Failed example: G.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 3257, in sage.graphs.generators.smallgraphs.HoffmanGraph Failed example: g.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 3306, in sage.graphs.generators.smallgraphs.HoltGraph Failed example: g.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 3835, in sage.graphs.generators.smallgraphs.MoserSpindle Failed example: G.radius() Expected: 2 Got: 2L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 4150, in sage.graphs.generators.smallgraphs.ShrikhandeGraph Failed example: G.radius() Expected: 2 Got: 2L ********************************************************************** File "src/sage/graphs/generators/smallgraphs.py", line 4294, in sage.graphs.generators.smallgraphs.SousselierGraph Failed example: g.radius() Expected: 2 Got: 2L ********************************************************************** 16 items had failures: 1 of 14 in sage.graphs.generators.smallgraphs.BrinkmannGraph 1 of 9 in sage.graphs.generators.smallgraphs.ChvatalGraph 1 of 15 in sage.graphs.generators.smallgraphs.DyckGraph 1 of 14 in sage.graphs.generators.smallgraphs.ErreraGraph 1 of 13 in sage.graphs.generators.smallgraphs.FranklinGraph 1 of 12 in sage.graphs.generators.smallgraphs.GoldnerHararyGraph 1 of 12 in sage.graphs.generators.smallgraphs.GrotzschGraph 1 of 13 in sage.graphs.generators.smallgraphs.HerschelGraph 1 of 7 in sage.graphs.generators.smallgraphs.HoffmanGraph 1 of 10 in sage.graphs.generators.smallgraphs.HoltGraph 1 of 9 in sage.graphs.generators.smallgraphs.HortonGraph 1 of 8 in sage.graphs.generators.smallgraphs.KittellGraph 1 of 10 in sage.graphs.generators.smallgraphs.MeredithGraph 1 of 12 in sage.graphs.generators.smallgraphs.MoserSpindle 1 of 15 in sage.graphs.generators.smallgraphs.ShrikhandeGraph 1 of 10 in sage.graphs.generators.smallgraphs.SousselierGraph [541 tests, 16 failures, 25.01 s] sage t long src/sage/graphs/genus.pyx [52 tests, 13.20 s] sage t long src/sage/graphs/graph_coloring.py [75 tests, 3.86 s] sage t long src/sage/graphs/graph_database.py [56 tests, 0.16 s] sage t long src/sage/graphs/graph_decompositions/__init__.py [0 tests, 0.00 s] sage t long src/sage/graphs/graph_decompositions/bandwidth.pyx [14 tests, 0.07 s] sage t long src/sage/graphs/graph.py [669 tests, 13.92 s] sage t long src/sage/graphs/graph_decompositions/fast_digraph.pxd [0 tests, 0.00 s] sage t long src/sage/graphs/graph_decompositions/fast_digraph.pyx [1 test, 0.00 s] sage t long src/sage/graphs/graph_decompositions/graph_products.pyx [15 tests, 0.07 s] sage t long src/sage/graphs/graph_decompositions/rankwidth.pxd [0 tests, 0.00 s] sage t long src/sage/graphs/graph_decompositions/rankwidth.pyx [23 tests, 0.03 s] sage t long src/sage/graphs/graph_decompositions/vertex_separation.pxd [0 tests, 0.00 s] sage t long src/sage/graphs/generic_graph.py ********************************************************************** File "src/sage/graphs/generic_graph.py", line 12686, in sage.graphs.generic_graph.GenericGraph.eccentricity Failed example: G.eccentricity() Expected: [4, 4, 4, 4, 4, 3, 3, 2, 3, 4] Got: [4L, 4L, 4L, 4L, 4L, 3L, 3L, 2L, 3L, 4L] ********************************************************************** File "src/sage/graphs/generic_graph.py", line 12700, in sage.graphs.generic_graph.GenericGraph.eccentricity Failed example: G.eccentricity(with_labels=True) Expected: {0: 0} Got: {0: 0L} ********************************************************************** File "src/sage/graphs/generic_graph.py", line 12753, in sage.graphs.generic_graph.GenericGraph.radius Failed example: G.radius() Expected: 3 Got: 3L ********************************************************************** File "src/sage/graphs/generic_graph.py", line 12761, in sage.graphs.generic_graph.GenericGraph.radius Failed example: G.radius() Expected: 2 Got: 2L ********************************************************************** 2 items had failures: 2 of 13 in sage.graphs.generic_graph.GenericGraph.eccentricity 2 of 9 in sage.graphs.generic_graph.GenericGraph.radius [2707 tests, 4 failures, 52.37 s]
comment:28 Changed 7 years ago by
Commit:  80cb89935d8eb8288d6659d7c73d8c05ee1c9411 → ce9d26556e5b1a69002e1a5165933e51ddfc7c05 

Branch pushed to git repo; I updated commit sha1. New commits:
ce9d265  trac #18864: return Sage integers

comment:30 Changed 7 years ago by
Status:  needs_review → positive_review 

No idea how to test it, but I am quite sure this should work!
comment:31 Changed 7 years ago by
I have tested it using an old computer with 32bits system and it solves the issue. Thanks.
comment:32 Changed 7 years ago by
Branch:  public/18864 → ce9d26556e5b1a69002e1a5165933e51ddfc7c05 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
trac #18864: new method for the eccenticity