Changes between Version 1 and Version 2 of Ticket #15507


Ignore:
Timestamp:
12/10/13 14:12:44 (7 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #15507 – Description

    v1 v2  
    99This 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.
    1010
    11 Soooooooooo this patch changes these "unsigned short" to good old integers (which are not unsigned because it makes the code clearer and does not change much), which is also good to have when Simon is about to use the same data structure for combinatorial graphs, which can be huge.
     11Soooooooooo this patch changes these "unsigned short" to 32-bits unsigned integers (and note more, because that already doubles the memory requires), which is also good to have when Simon is about to use the same data structure for combinatorial graphs, which can be huge.
    1212
    1313I have to mention that this does not make "diameter" answer very fast either on instances with more than 65536 vertices `:-/`
     
    2323
    2424What this patch does:
    25 * change the type of the static_sparse_graph data structure from ushort to int, as well as the functions that use it
     25* change the type of the static_sparse_graph data structure from ushort to uint32_t, as well as the functions that use it
    2626* change the `all_pairs_shortest_path_BFS` function to first compute the distance on a `int *` array of length `n`. The values are then copied into the `n^2` matrix of `ushort` if necessary. That's a loss of time, but it's either this or rewriting two versions of the function `:-/`
    2727* remove a useless `degree` variable in the same function