Changes between Initial Version and Version 1 of Ticket #15507
 Timestamp:
 12/10/13 13:42:20 (9 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #15507

Property
Status
changed from
new
toneeds_review

Property
Branch
changed from
to
public/15507

Property
Status
changed from

Ticket #15507 – Description
initial v1 1 1 On Sagedevel [1], Christian reported an humiliating error message : 2 2 3 3 {{{ 4 sage: graphs.PathGraph(70000).diameter() 5 ... 6 ValueError: The graph backend contains more than 65535 nodes 7 }}} 4 8 5 9 This 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. … … 8 12 9 13 I have to mention that this does not make "diameter" answer very fast either on instances with more than 65536 vertices `:/` 14 15 {{{ 16 sage: %time graphs.PathGraph(70000).diameter() 17 CPU times: user 132.41 s, sys: 0.16 s, total: 132.57 s 18 Wall time: 133.42 s 19 69999 20 }}} 10 21 11 22 But at least we can build them `T_T`