Opened 7 years ago

Last modified 7 years ago

#15507 closed enhancement

Static sparse graphs on > 65536 vertices — at Version 1

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:
Dependencies: Stopgaps:

Status badges

Description (last modified by ncohen)

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

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 int, 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

Change History (1)

comment:1 Changed 7 years ago by ncohen

  • Branch set to public/15507
  • Description modified (diff)
  • Status changed from new to needs_review
Note: See TracTickets for help on using tickets.