Changes between Initial Version and Version 1 of Ticket #15507


Ignore:
Timestamp:
12/10/13 13:42:20 (7 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`