graph: should the gonum graph types be able to iterate over more than 1<<31 nodes

24 views
Skip to first unread message

Dan Kortschak

unread,
Jun 20, 2017, 4:09:38 AM6/20/17
to gonu...@googlegroups.com, Vladimír Chalupecký
There is a PR pending to change the ID type from int to int64. This in
principle would allow all architectures to be able to handle more than
1<<31 nodes if there were an iterator type to allow access to a backing
store. The notion of an iterator is discussed in [1].

There are algorithms that we implement that cannot handle graphs of
this order either because of space or time complexity of the algorithm
or the implementation. So my gut feeling is that retaining an
architecture-dependent limit on order is appropriate, even though the
ID space is much larger. The utility of the larger ID space is still in
being able to take subgraphs from much larger on-disk graphs to perform
analyses on those. This is the basis for [2].

Thoughts?

[1]https://github.com/gonum/graph/issues/46
[2]https://github.com/gonum/gonum/issues/72
Reply all
Reply to author
Forward
0 new messages