This PR contain memory improvements to the following functions:

• Acyclic
• BFS
• Bipartition
• Components
• Connected
• EulerDirected
• EulerUndirected
• MST
• ShortestPath
• ShortestPaths
• Sort
• TopSort
• Transpose

The technique to use less memory is equal in all the functions. I declared the closures (from g.Visit(v, closure)) outside the loop (related: #8), the result is the closure is allocated only one time and not allocated in each loop iteration.

I changed ShortestPath to stop when finding the target vertex.

I added the benchmark results in the testdata directory (it can be removed). The benchmarks were done in my machine with background processes running so the speed results aren't very reliable, but the memory results should be.

Obs: I didn't change the StrongComponents because it uses a recursive function, so the technique didn't fit well, and I didn't change MaxFlow because the improvement in memory was tiny.

Benchmark Results:

name       old time/op    new time/op    delta
Acyclic-8     128µs ± 0%      66µs ± 0%  -47.95%

name       old alloc/op   new alloc/op   delta
Acyclic-8    52.0kB ± 0%    12.4kB ± 0%  -76.18%

name       old allocs/op  new allocs/op  delta
Acyclic-8     1.17k ± 0%     0.01k ± 0%  -98.89%

name   old time/op    new time/op    delta
BFS-8     269µs ± 0%     206µs ± 0%  -23.36%

name   old alloc/op   new alloc/op   delta
BFS-8    86.8kB ± 0%    23.2kB ± 0%  -73.27%

name   old allocs/op  new allocs/op  delta
BFS-8     1.01k ± 0%     0.02k ± 0%  -98.33%

name           old time/op    new time/op    delta
Bipartition-8    1.88µs ± 0%    1.40µs ± 0%  -25.44%

name           old alloc/op   new alloc/op   delta
Bipartition-8    3.62kB ± 0%    2.79kB ± 0%  -22.79%

name           old allocs/op  new allocs/op  delta
Bipartition-8      26.0 ± 0%      14.0 ± 0%  -46.15%

name          old time/op    new time/op    delta
Components-8     196µs ± 0%     149µs ± 0%  -24.01%

name          old alloc/op   new alloc/op   delta
Components-8    86.8kB ± 0%    54.8kB ± 0%  -36.83%

name          old allocs/op  new allocs/op  delta
Components-8     1.23k ± 0%     0.23k ± 0%  -80.96%

name         old time/op    new time/op    delta
Connected-8     151µs ± 0%     104µs ± 0%  -31.26%

name         old alloc/op   new alloc/op   delta
Connected-8    40.2kB ± 0%     8.3kB ± 0%  -79.45%

name         old allocs/op  new allocs/op  delta
Connected-8     1.00k ± 0%     0.01k ± 0%  -99.50%

name             old time/op    new time/op    delta
EulerDirected-8    7.28µs ± 0%    2.00µs ± 0%  -72.44%

name             old alloc/op   new alloc/op   delta
EulerDirected-8    5.71kB ± 0%    0.96kB ± 0%  -83.19%

name             old allocs/op  new allocs/op  delta
EulerDirected-8       103 ± 0%         4 ± 0%  -96.12%

name               old time/op    new time/op    delta
EulerUndirected-8    7.07µs ± 0%    2.39µs ± 0%  -66.21%

name               old alloc/op   new alloc/op   delta
EulerUndirected-8    5.72kB ± 0%    0.97kB ± 0%  -83.08%

name               old allocs/op  new allocs/op  delta
EulerUndirected-8       104 ± 0%         5 ± 0%  -95.19%

name   old time/op    new time/op    delta
MST-8     249µs ± 0%     190µs ± 0%  -23.85%

name   old alloc/op   new alloc/op   delta
MST-8    96.9kB ± 0%    33.0kB ± 0%  -65.99%

name   old allocs/op  new allocs/op  delta
MST-8     1.01k ± 0%     0.01k ± 0%  -99.20%

name            old time/op    new time/op    delta
ShortestPath-8     141µs ± 0%      60µs ± 0%  -57.23%

name            old alloc/op   new alloc/op   delta
ShortestPath-8    79.9kB ± 0%    39.8kB ± 0%  -50.23%

name            old allocs/op  new allocs/op  delta
ShortestPath-8       856 ± 0%        21 ± 0%  -97.55%

name             old time/op    new time/op    delta
ShortestPaths-8     121µs ± 0%      80µs ± 0%  -34.06%

name             old alloc/op   new alloc/op   delta
ShortestPaths-8    79.2kB ± 0%    39.7kB ± 0%  -49.85%

name             old allocs/op  new allocs/op  delta
ShortestPaths-8       841 ± 0%        19 ± 0%  -97.74%

name    old time/op    new time/op    delta
Sort-8     608µs ± 0%     500µs ± 0%  -17.79%

name    old alloc/op   new alloc/op   delta
Sort-8     249kB ± 0%     201kB ± 0%  -19.25%

name    old allocs/op  new allocs/op  delta
Sort-8     6.03k ± 0%     5.03k ± 0%  -16.57%

name       old time/op    new time/op    delta
TopSort-8     135µs ± 0%      69µs ± 0%  -48.49%

name       old alloc/op   new alloc/op   delta
TopSort-8    56.1kB ± 0%    16.5kB ± 0%  -70.62%

name       old allocs/op  new allocs/op  delta
TopSort-8     1.18k ± 0%     0.02k ± 0%  -98.14%

name         old time/op    new time/op    delta
Transpose-8     404µs ± 0%     401µs ± 0%   -0.72%

name         old alloc/op   new alloc/op   delta
Transpose-8     218kB ± 0%     170kB ± 0%  -22.04%

name         old allocs/op  new allocs/op  delta
Transpose-8     5.00k ± 0%     4.00k ± 0%  -19.98%

I apologies if your pkg can already do this, but I was perusing your docs and didn't see an easy way to. I'd like to tell which vertices contain cycles or paths back to themselves.

I do know that you can tell me quickly if it is Acyclic, but I'd like to know which nodes have cycles.

Is that possible and if not how would on add that?

Thank you!

Hi Korthaj, when i was using the ShortestPath function i noticed that it was using a significant amount of memory (I was processing a large graph). It seems that the closure is allocated (or a pointer to it) at each iteration of the loop which makes the function use more memory.

name             old time/op    new time/op    delta
ShortestPaths-8     154µs ± 0%      85µs ± 0%  -45.02%

name             old alloc/op   new alloc/op   delta
ShortestPaths-8    81.0kB ± 0%    41.1kB ± 0%  -49.26%

name             old allocs/op  new allocs/op  delta
ShortestPaths-8       849 ± 0%        17 ± 0%  -98.00%

This package and your blog are awsome.

-Rodrigo

I noticed that the performance of ShortestPath can be substantially improved. Instead of finding all the shortest paths from the initial vertex, we could terminate the search as soon as we found the path to the destination vertex.

I've opened a pull request because I already have a patch.

1. No API changes whatsoever;
2. This performance enhancement is based on the original E. W. Dijkstra's paper (it's what should be found in a CS textbook).

old/new comparison:

benchmark                       old ns/op     new ns/op     delta
BenchmarkShortestPath250-4      55089         31078         -43.59%
BenchmarkShortestPath500-4      121956        51563         -57.72%
BenchmarkShortestPath1000-4     206507        79512         -61.50%