Skip to content

RFC: Use a dense representation for the unfolded graph to avoid unbounded memory consumption.

Adam Reichold requested to merge dense-graph into cmp-and-doc

@buergerm Using a dense representation avoids the unbound increase in memory consumption as the path graph becomes more and more meshed even though it does imply a slow down in the beginning when that graph is still sparse. But at least this would allow us to process the large graphs on notebook class hardware:

$ /usr/bin/time ./target/release/unfold 86400 <~/sick-bees/graph_lt060_dc03.bin
nodes = 93697
time,paths
0,333344
1,3402916
...
118,4824669195
119,4905467827
8549.55user 2.10system 17:59.91elapsed 791%CPU (0avgtext+0avgdata 13944812maxresident)k
0inputs+0outputs (0major+379933minor)pagefaults 0swaps
Edited by Adam Reichold

Merge request reports