Opened 7 years ago
Last modified 7 years ago
#15507 closed enhancement
Static sparse graphs on > 65536 vertices — at Version 9
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.1 |
Component: | graph theory | Keywords: | |
Cc: | SimonKing, dcoudert, stumpc5 | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | public/15507 (Commits, GitHub, GitLab) | Commit: | 16b4b265b784192dab04950e8bd57060917d73a9 |
Dependencies: | Stopgaps: |
Description (last modified by )
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 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/sage-devel/2AI1CNdDm6w/jHKh26pMzqcJ
Change History (9)
comment:1 Changed 7 years ago by
- Branch set to public/15507
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Description modified (diff)
comment:3 Changed 7 years ago by
- Commit set to fd4b4a5f81e6186b49ec270574393a4784ea45dd
comment:4 Changed 7 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 7 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 7 years ago by
- Commit changed from fd4b4a5f81e6186b49ec270574393a4784ea45dd to 16b4b265b784192dab04950e8bd57060917d73a9
comment:7 Changed 7 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 Changed 7 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 7 years ago by
- Description modified (diff)
The syntax checker was around... in order to read n^{2} you should write n caret 2 caret.
Branch pushed to git repo; I updated commit sha1. New commits: