Opened 9 years ago
Closed 9 years ago
#15507 closed enhancement (fixed)
Static sparse graphs on > 65536 vertices
Reported by:  Nathann Cohen  Owned by:  

Priority:  major  Milestone:  sage6.1 
Component:  graph theory  Keywords:  
Cc:  Simon King, David Coudert, Christian Stump  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Christian Stump 
Report Upstream:  N/A  Work issues:  
Branch:  u/ncohen/15507 (Commits, GitHub, GitLab)  Commit:  3b28d9f33d22b458ad21d525dbc55523332145ab 
Dependencies:  Stopgaps: 
Description (last modified by )
On Sagedevel [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 32bits 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 aint *
array of lengthn
. The values are then copied into then^2
matrix ofushort
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/sagedevel/2AI1CNdDm6w/jHKh26pMzqcJ
Change History (26)
comment:1 Changed 9 years ago by
Branch:  → public/15507 

Description:  modified (diff) 
Status:  new → needs_review 
comment:2 Changed 9 years ago by
Description:  modified (diff) 

comment:3 Changed 9 years ago by
Commit:  → fd4b4a5f81e6186b49ec270574393a4784ea45dd 

comment:4 Changed 9 years ago by
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
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.
comment:6 Changed 9 years ago by
Commit:  fd4b4a5f81e6186b49ec270574393a4784ea45dd → 16b4b265b784192dab04950e8bd57060917d73a9 

comment:7 Changed 9 years ago by
(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 followup: 10 Changed 9 years ago by
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
Description:  modified (diff) 

The syntax checker was around... in order to read n^{2} you should write n caret 2 caret.
comment:10 followup: 11 Changed 9 years ago by
Yooooooooooo !!
Out of curiosity: why do you now use
public/ticketnumber
after usingu/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 noncontroversial 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 followup: 12 Changed 9 years ago by
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 Changed 9 years ago by
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:14 Changed 9 years ago by
Branch:  public/15507 → u/ncohen/15507 

Commit:  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
Commit:  → 16b4b265b784192dab04950e8bd57060917d73a9 

comment:16 Changed 9 years ago by
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:20 Changed 9 years ago by
Commit:  16b4b265b784192dab04950e8bd57060917d73a9 → 1bbb51b9102baf68c80f8463abb96d879d952d39 

Status:  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
Doesn't actually work
Cython.Compiler.Errors.InternalError: Internal compiler error: 'sage/misc/bitset_pxd.pxi' not found
comment:22 Changed 9 years ago by
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
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
comment:24 Changed 9 years ago by
Commit:  1bbb51b9102baf68c80f8463abb96d879d952d39 → 3b28d9f33d22b458ad21d525dbc55523332145ab 

comment:25 Changed 9 years ago by
Reviewers:  → Christian Stump 

Status:  needs_review → positive_review 
comment:26 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits: