Changes between Initial Version and Version 1 of Ticket #15507


Ignore:
Timestamp:
12/10/13 13:42:20 (9 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #15507

    • Property Status changed from new to needs_review
    • Property Branch changed from to public/15507

  • Ticket #15507 – Description

    initial v1  
    11On Sage-devel [1], Christian reported an humiliating error message :
    22
    3 
     3{{{
     4sage: graphs.PathGraph(70000).diameter()       
     5...
     6ValueError: The graph backend contains more than 65535 nodes
     7}}}
    48
    59This is because Sage's "static_sparse_graphs" are stored on `unsigned short` fields (and thus to 65536 vertices), and though this is a meaningful limitation for Sage's code to compute the "all pairs shortest path" (the distance between all pairs of vertices, i.e. a n^2 matrix of integers), it does not make any sense to refuse to compute the diameter of such graphs.
    … …  
    812
    913I have to mention that this does not make "diameter" answer very fast either on instances with more than 65536 vertices `:-/`
     14
     15{{{
     16sage: %time graphs.PathGraph(70000).diameter()
     17CPU times: user 132.41 s, sys: 0.16 s, total: 132.57 s
     18Wall time: 133.42 s
     1969999
     20}}}
    1021
    1122But at least we can build them `T_T`