perf: use the "railroad" technique

[william-silversmith]

A "rail road" (a term defined by us) is the shortest last-mile path (the "road") from a target point to a "rail network" that includes the source point. A "rail" is a zero weighted path that acts as a strong attractor for the search algorithm. In the context of the skeletonization problem, such networks are assembled as a matter of course. It becomes more and more efficient to search for the rail network than for the target point.

For example, consider a glia. As the number of paths increases, the size of the rail network grows to the point that a source->target algorithm will perform extraneous work searching the network even though it is already a restricted domain compared to a naive search. Instead, it makes more sense to find the first rail, which generates a shorter path and avoids the extraneous work.

The shorter path also reduces redundancy in the invalidation algorithm as otherwise the same voxels need to be invalidated over and over (though there is already a provision for preventing that issue).

[william-silversmith]

Results are a little hard to parse but it seems better overall?

(black) 2.2.0 (blue) 2.2.0 + sorted target + railroad (red) 2.2.0 + sorted target

One detail that stands out (same plot minus red) is that railroad seems to work better on the soma? Since bidirectional isn't used, peak memory usage falls.

The railroad doesn't seem to have much effect beyond that. Starting to wonder if the difference is really just dijkstra vs bidirectional dijkstra.

[william-silversmith]

(black) dijkstra vs (blue) railroad

dijkstra was terminated early, so compare the heights of the peaks at the end to figure out what is what.

[william-silversmith]

Think I figured out why dijkstra is better for somas than bidirectional. The edge effect of the target is an implied constraint on the search space while bidirectional wastes energy spiraling around the source. Additionally, t->s follows the gradient rather than fights it.

We introduced bidirection before we figured out the target->source benefit, so bidirectional was way superior to unidirectional s->t. However, regular t->s dijkstra or railroad is a superior replacement.

[william-silversmith]

Now that I understand that, I think I can interpret yesterday's experiments more clearly. dijkstra/railroad are about the same for soma and everywhere else except on very complex glia, where railroad has a slight advantage that reproduced across 2 trials in line with my hypothesis about tracing the rail network taking up some time at the end.