trac #15507: Static sparse graphs on > 65536 vertices
trac #15507: rebase on 6.1.beta0
Trac #15507: Static sparse graphs on > 65536 vertices

On Sage-devel [1], Christian reported an humiliating error message :

{{{
sage: graphs.PathGraph(70000).diameter()
...
ValueError: The graph backend contains more than 65535 nodes
}}}

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.

Soooooooooo 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.

I have to mention that this does not make "diameter" answer very fast
either on instances with more than 65536 vertices `:-/`

{{{
sage: %time graphs.PathGraph(70000).diameter()
CPU times: user 132.41 s, sys: 0.16 s, total: 132.57 s
Wall time: 133.42 s
69999
}}}

But at least we can build them `T_T`

What this patch does:
* change the type of the static_sparse_graph data structure from ushort
to uint32_t, as well as the functions that use it
* 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 `:-/`
* remove a useless `degree` variable in the same function
* Some simplifications from place to place in the code

Nathann

[1] https://groups.google.com/d/msg/sage-devel/2AI1CNdDm6w/jHKh26pMzqcJ

URL: http://trac.sagemath.org/15507
Reported by: ncohen
Ticket author(s): Nathann Cohen
Reviewer(s):