Namespace AS2.Algos.SingleSourceSP
Classes
SingleSourceSPInitializer
SingleSourceSPParticle
Implements the (1, l)-SPF algorithm. See https://doi.org/10.1145/3662158.3662776.
In the first phase, we run the Euler Tour Technique (ETT) on the
implicit portal graphs for the 3 axes, using the source amoebot as
root and the destination amoebots to define the weight function.
After each iteration, each amoebot knows which of its adjacent portals
is a parent portal. For each neighbor, we count in how many portal graphs
this neighbor is on a parent portal.
At the end of the first phase, each amoebot elects one neighbor that
occurred as parent portal twice to be its parent in the shortest path tree.
In the second phase, we run ETT again on the resulting forest to prune all subtrees without destinations and to identify and remove components that are not connected to the root.