Opened 9 years ago

Closed 9 years ago

# Static sparse graphs on > 65536 vertices

Reported by: Owned by: Nathann Cohen major sage-6.1 graph theory Simon King, David Coudert, Christian Stump Nathann Cohen Christian Stump N/A u/ncohen/15507 3b28d9f33d22b458ad21d525dbc55523332145ab

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 n2 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

### comment:1 Changed 9 years ago by Nathann Cohen

Branch: → public/15507 modified (diff) new → needs_review

### comment:2 Changed 9 years ago by Nathann Cohen

Description: modified (diff)

### comment:3 Changed 9 years ago by git

Commit: → fd4b4a5f81e6186b49ec270574393a4784ea45dd

Branch pushed to git repo; I updated commit sha1. New commits:

 ​fd4b4a5 trac #15507: Static sparse graphs on > 65536 vertices

### comment:4 Changed 9 years ago by Christian Stump

Thanks for working on that - how do I find your branch, it doesn't seem to be valid, and I just fetched and do not see any branch containing "15507".

Cheers, C.

### comment:5 Changed 9 years ago by Christian Stump

Ah, there it is...

I still don't feel super comfortable, it more feels like git is using me rather than how it should be. E.g., in #15228 I don't know how to kick the patchbot. I also do not know how to get rid of branches I checked out once. Anyway, I will look at your changes now.

Best, C.

Last edited 9 years ago by Christian Stump (previous) (diff)

### comment:6 Changed 9 years ago by git

Commit: fd4b4a5f81e6186b49ec270574393a4784ea45dd → 16b4b265b784192dab04950e8bd57060917d73a9

Branch pushed to git repo; I updated commit sha1. New commits:

 ​16b4b26 trac #15507: Static sparse graphs on > 65536 vertices

### comment:7 Changed 9 years ago by Nathann Cohen

(sorry, I updated the branch since, as there were two broken doctests left. Some integers were printed as 1L instead of 1 T_T)

Nathann

### comment:8 follow-up:  10 Changed 9 years ago by Christian Stump

Out of curiosity: why do you now use public/ticketnumber after using u/ncohen/ticketnumber before?

I cannot judge if you created any problems anywhere in the code, but I guess you know what you are doing...

I just ran the doctest on all of graphs, and the only error I see is AttributeError in doctesting framework which is also there without having your changes applied.

I didn't see any new doctest for the code testing the diameter for something bigger, line the line graph of 70000 vertices. Don't you think it would be nice to have such an example in the code?

Cheers, Christian

### comment:9 Changed 9 years ago by Vincent Delecroix

Description: modified (diff)

The syntax checker was around... in order to read n2 you should write n caret 2 caret.

### comment:10 in reply to:  8 ; follow-up:  11 Changed 9 years ago by Nathann Cohen

Yooooooooooo !!

Out of curiosity: why do you now use public/ticketnumber after using u/ncohen/ticketnumber before?

Because I don't like it that people have to create their own branch to add a commit. Most of the time it's only typos or non-controversial stuff, so well, let's keep it simple and write on the same branches. I don't link this permission stuff anyway.

I just ran the doctest on all of graphs, and the only error I see is AttributeError in doctesting framework which is also there without having your changes applied.

Hmmmmmm... Perhaps you should report that somewhere, the git version should be the "official" version quite soon.

I didn't see any new doctest for the code testing the diameter for something bigger, line the line graph of 70000 vertices. Don't you think it would be nice to have such an example in the code?

Well... It takes two minutes on its own. I thought that it was a bit too much for a doctest O_o

Nathann

### comment:11 in reply to:  10 ; follow-up:  12 Changed 9 years ago by Christian Stump

Well... It takes two minutes on its own. I thought that it was a bit too much for a doctest O_o

agreed. So, how am I getting the patchbot off the couch to get to work?

### comment:12 in reply to:  11 Changed 9 years ago by Nathann Cohen

agreed. So, how am I getting the patchbot off the couch to get to work?

Noooooooooo Idea ! I ran the tests on my own computer O_o

Nathann

### comment:13 Changed 9 years ago by Christian Stump

What happened to the branch -- is it gone?

### comment:14 Changed 9 years ago by Nathann Cohen

Branch: public/15507 → u/ncohen/15507 16b4b265b784192dab04950e8bd57060917d73a9

Well, no... I can import it from trac, so it exists !

I will reupload it under a different name, in my own folder.

I wouldn' want it to disappear.

Nathann

### comment:15 Changed 9 years ago by git

Commit: → 16b4b265b784192dab04950e8bd57060917d73a9

Branch pushed to git repo; I updated commit sha1. New commits:

 ​16b4b26 trac #15507: Static sparse graphs on > 65536 vertices

### comment:16 Changed 9 years ago by Christian Stump

Status: needs_review → positive_review

The doctests pass, the patch does what it is supposed to, so I am setting this to positive review.

Only trac seems to not to be knowing where the branch is, but I can import it from trac, so there should be a way out...

### comment:17 Changed 9 years ago by Nathann Cohen

HMmmmmmmmmm weird O_o

Thanks for the review, though !!!

Nathann

### comment:18 Changed 9 years ago by Volker Braun

Doesn't merge with sage-6.0, please fix.

Done !

Nathann

### comment:20 Changed 9 years ago by git

Commit: 16b4b265b784192dab04950e8bd57060917d73a9 → 1bbb51b9102baf68c80f8463abb96d879d952d39 positive_review → needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

 ​1bbb51b trac #15507: rebase on 6.1.beta0 ​3735dfd Updated Sage version to 6.1.beta0 ​47c9c75 Trac #15224: Iterate over the points of a toric variety ​f382aec Trac #15403: knapsack's docstring doesn't document an useful feature ​0c95d3d Trac #15228: Default embedding of Ljubljana graph (typo) ​09fd00b Trac #12217: Finite field polynomials allow division by zero ​9acb905 Trac 12217: correctly handle division by zero ​8094791 Trac #14912: UniqueRepresentation tutorial could use more love ​4ce6a49 Trac #15442: MILP solver CBC : undefined symbol: dgetrf_ ​42d6141 #14912: fix leaking print statement when running doctests.

### comment:21 Changed 9 years ago by Volker Braun

Doesn't actually work

### comment:22 Changed 9 years ago by Nathann Cohen

Arggggg... Must be because of Jeroen's patch on the bitset things.. Don't remember which one it was though O_o

### comment:23 Changed 9 years ago by Nathann Cohen

Yoooooooo ! Sorry 'bout that. It was because of #13352. Jeroen replaced these imports almost everywhere, but of course not in the patches needing review :-P

I updated the last commit. This one compiles and passes tests.

Nathann