search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.35k stars 461 forks source link

New method for the eccentricity of undirected graphs #18864

Closed dcoudert closed 9 years ago

dcoudert commented 9 years ago

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

CC: @nathanncohen @sagetrac-borassi

Component: graph theory

Author: David Coudert

Branch/Commit: ce9d265

Reviewer: Michele Borassi

Issue created by migration from https://trac.sagemath.org/ticket/18864

dcoudert commented 9 years ago

Branch: public/18864

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

bb2dd5ctrac #18864: new method for the eccenticity
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Commit: bb2dd5c

dcoudert commented 9 years ago
comment:3

Let me know if you like it. David.

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:4

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:

Other, more general, remarks:

[1] http://www.sciencedirect.com/science/article/pii/S0304397515001644

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

41a2c87trac #18864: implement some reviewers suggestions
003b73etrac #18864: unify types for eccentricity
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from bb2dd5c to 003b73e

dcoudert commented 9 years ago
comment:6
  • 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.

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:7
  • 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

dcoudert commented 9 years ago
comment:8

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 003b73e to 873f62d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

873f62dtrac #18864: new next vertex selection process
a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:10

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!

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 873f62d to da0260d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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
dcoudert commented 9 years ago
comment:12

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

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:13

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

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:14

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from da0260d to 554c509

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

554c509trac #18864: implement reviewer's comments
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 554c509 to f48a33e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

f48a33etrac #18864: minor corrections
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from f48a33e to a3717b7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

a3717b7trac #18864: improve behavior with directed graphs
dcoudert commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-This patch implements the algorithm proposed in [1] for computing the eccentricity of all vertices. It can be faster than the standard algorithm.
+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 @@ -18,5 +18,7 @@ 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
dcoudert commented 9 years ago
comment:18

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.

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:19

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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

f621777trac #18864: corrections and improved doc
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from a3717b7 to f621777

dcoudert commented 9 years ago
comment:21

Hello Michele,

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

Best.

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:22

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from f621777 to 80cb899

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

80cb899trac #18864: correct version
dcoudert commented 9 years ago
comment:24

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

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:25

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!

dcoudert commented 9 years ago

Reviewer: Michele Borassi

dcoudert commented 9 years ago
comment:26

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.

vbraun commented 9 years ago
comment:27

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]
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

ce9d265trac #18864: return Sage integers
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 80cb899 to ce9d265

dcoudert commented 9 years ago
comment:29

This should work.

a8f3419b-6383-42be-b93c-ecaa87929754 commented 9 years ago
comment:30

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

dcoudert commented 9 years ago
comment:31

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

vbraun commented 9 years ago

Changed branch from public/18864 to ce9d265