Opened 4 years ago

Closed 4 years ago

#18864 closed enhancement (fixed)

New method for the eccentricity of undirected graphs

Reported by: dcoudert Owned by:
Priority: minor Milestone: sage-6.8
Component: graph theory Keywords:
Cc: ncohen, borassi Merged in:
Authors: David Coudert Reviewers: Michele Borassi
Report Upstream: N/A Work issues:
Branch: ce9d265 (Commits) Commit: ce9d26556e5b1a69002e1a5165933e51ddfc7c05
Dependencies: Stopgaps:

Description (last modified by dcoudert)

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:100-118 (2013) http://dx.doi.org/10.3390/a6010100

Change History (32)

comment:1 Changed 4 years ago by dcoudert

  • Branch set to public/18864

comment:2 Changed 4 years ago by git

  • Commit set to bb2dd5c3860d47e59bb1258df91465f9c22d1281

Branch pushed to git repo; I updated commit sha1. New commits:

bb2dd5ctrac #18864: new method for the eccenticity

comment:3 Changed 4 years ago by dcoudert

  • Cc ncohen borassi added
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

Let me know if you like it. David.

comment:4 follow-up: Changed 4 years ago by borassi

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 tie-break).
  • 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_MAX-distances[w], and the upper bound will be INT32_MAX, so you will need a lot of BFSes, probably, instead of simply returning an array of INT32_MAX after the first BFS.
  • ecc[v] = INT32_MAX if tmp>n else tmp: I think it is better to use an integer variable named eccv, since you use it O(n) times later.
  • you return a vector ecc of length 3n: why don't you use two different vectors for LB and UB, 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%2F978-3-319-07890-8_5

comment:5 Changed 4 years ago by git

  • Commit changed from bb2dd5c3860d47e59bb1258df91465f9c22d1281 to 003b73ee0cb4493614412de568aa9f2fb0e58ac8

Branch pushed to git repo; I updated commit sha1. New commits:

41a2c87trac #18864: implement some reviewers suggestions
003b73etrac #18864: unify types for eccentricity

comment:6 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by dcoudert

  • 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?

  • 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_MAX-distances[w], and the upper bound will be INT32_MAX, so you will need a lot of BFSes, probably, instead of simply returning an array of INT32_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 named eccv, since you use it O(n) times later.

Somehow done

  • you return a vector ecc of length 3n: why don't you use two different vectors for LB and UB, 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 in reply to: ↑ 6 Changed 4 years ago 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

![2] http://link.springer.com/chapter/10.1007%2F978-3-319-07890-8_5

comment:8 Changed 4 years ago by dcoudert

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 4 years ago by git

  • Commit changed from 003b73ee0cb4493614412de568aa9f2fb0e58ac8 to 873f62d1113634784413c7995e6f78cc7221d702

Branch pushed to git repo; I updated commit sha1. New commits:

873f62dtrac #18864: new next vertex selection process

comment:10 Changed 4 years ago by borassi

Hellooooo!

Great, now the algorithm should be much faster!

I think there is still a problem with directed graphs: the Takes-Kosters algorithm works only on undirected graphs, so I think you should add a ValueError if the user asks the Takes-Kosters 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 4 years ago by git

  • Commit changed from 873f62d1113634784413c7995e6f78cc7221d702 to da0260dca9b43d96b47bcae2ba79a2b8819896ec

Branch pushed to git repo; I updated commit sha1. New commits:

da7bad7trac #18864: Merged with 6.8.beta8
da0260dtrac #18864: prevent using the Takes-Kosters algorithm on digraphs

comment:12 follow-up: Changed 4 years ago by dcoudert

Should be OK now. Do you know similar algorithm for digraphs?

comment:13 Changed 4 years ago 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

comment:14 in reply to: ↑ 12 Changed 4 years ago 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.

comment:15 Changed 4 years ago by git

  • Commit changed from da0260dca9b43d96b47bcae2ba79a2b8819896ec to 554c5099f8b47cef74a13cd968223c9288264424

Branch pushed to git repo; I updated commit sha1. New commits:

554c509trac #18864: implement reviewer's comments

comment:16 Changed 4 years ago by git

  • Commit changed from 554c5099f8b47cef74a13cd968223c9288264424 to f48a33e012a0187ceea3b3011909342dc5cb1375

Branch pushed to git repo; I updated commit sha1. New commits:

f48a33etrac #18864: minor corrections

comment:17 Changed 4 years ago by git

  • Commit changed from f48a33e012a0187ceea3b3011909342dc5cb1375 to a3717b73c811ff702345a186b679df4b99e725fa

Branch pushed to git repo; I updated commit sha1. New commits:

a3717b7trac #18864: improve behavior with directed graphs

comment:18 Changed 4 years ago by dcoudert

  • Description modified (diff)
  • Summary changed from New method for the eccentricity to 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 4 years ago 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.

comment:20 Changed 4 years ago by git

  • Commit changed from a3717b73c811ff702345a186b679df4b99e725fa to f621777db49299ce66bf8663795ad79453d4e43e

Branch pushed to git repo; I updated commit sha1. New commits:

f621777trac #18864: corrections and improved doc

comment:21 Changed 4 years ago by dcoudert

Hello Michele,

I have implemented your suggestions. In particular I'm no longer using list W but a bitset instead.

Best.

comment:22 Changed 4 years ago by borassi

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 4 years ago by git

  • Commit changed from f621777db49299ce66bf8663795ad79453d4e43e to 80cb89935d8eb8288d6659d7c73d8c05ee1c9411

Branch pushed to git repo; I updated commit sha1. New commits:

80cb899trac #18864: correct version

comment:24 Changed 4 years ago by dcoudert

You are perfectly right. Not well awaken today...

comment:25 Changed 4 years ago by borassi

  • Status changed from needs_review to 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 4 years ago by dcoudert

  • Reviewers set to 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 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Can you guys settle on a pattern where you return Sage integers everywhere? Not only would that then work on 32-bit 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 4 years ago by git

  • Commit changed from 80cb89935d8eb8288d6659d7c73d8c05ee1c9411 to ce9d26556e5b1a69002e1a5165933e51ddfc7c05

Branch pushed to git repo; I updated commit sha1. New commits:

ce9d265trac #18864: return Sage integers

comment:29 Changed 4 years ago by dcoudert

  • Status changed from needs_work to needs_review

This should work.

comment:30 Changed 4 years ago by borassi

  • Status changed from needs_review to positive_review

No idea how to test it, but I am quite sure this should work!

comment:31 Changed 4 years ago by dcoudert

I have tested it using an old computer with 32bits system and it solves the issue. Thanks.

comment:32 Changed 4 years ago by vbraun

  • Branch changed from public/18864 to ce9d26556e5b1a69002e1a5165933e51ddfc7c05
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.