Class 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.
Inheritance
SingleSourceSPParticle
Assembly: .dll
Syntax
public class SingleSourceSPParticle : ParticleAlgorithm
Constructors
SingleSourceSPParticle(Particle)
Declaration
public SingleSourceSPParticle(Particle p)
Parameters
Fields
destColor
Declaration
private static readonly Color destColor
Field Value
destPortalColor
Declaration
private static readonly Color destPortalColor
Field Value
ett
Declaration
Field Value
isDest
Declaration
private ParticleAttribute<bool> isDest
Field Value
isDestRepr
Declaration
private ParticleAttribute<bool> isDestRepr
Field Value
isRootRepr
Declaration
private ParticleAttribute<bool> isRootRepr
Field Value
isSource
Declaration
private ParticleAttribute<bool> isSource
Field Value
mixedPortalColor
Declaration
private static readonly Color mixedPortalColor
Field Value
nbrPortalDir1
Declaration
private ParticleAttribute<Direction> nbrPortalDir1
Field Value
nbrPortalDir2
Declaration
private ParticleAttribute<Direction> nbrPortalDir2
Field Value
onDestPortal
Declaration
private ParticleAttribute<bool> onDestPortal
Field Value
onRootPortal
Declaration
private ParticleAttribute<bool> onRootPortal
Field Value
parent
Declaration
private ParticleAttribute<Direction> parent
Field Value
parentCounters
Declaration
private ParticleAttribute<int>[] parentCounters
Field Value
phase
Declaration
private ParticleAttribute<SingleSourceSPParticle.Phase> phase
Field Value
portalAxisDir
Declaration
private ParticleAttribute<Direction> portalAxisDir
Field Value
pruned
Declaration
private ParticleAttribute<bool> pruned
Field Value
round
Declaration
private ParticleAttribute<int> round
Field Value
sourceColor
Declaration
private static readonly Color sourceColor
Field Value
sourcePortalColor
Declaration
private static readonly Color sourcePortalColor
Field Value
Properties
GenerationMethod
Declaration
public static string GenerationMethod { get; }
Property Value
Name
Declaration
public static string Name { get; }
Property Value
PinsPerEdge
The number of pins on each edge.
This number must be the same constant for all
particles.
Declaration
public override int PinsPerEdge { get; }
Property Value
Overrides
Methods
ActivateBeep()
This is the second part of the main activation logic of the
particle. It is called exactly once in each round, after the
movements scheduled in ActivateMove() have been
executed, and should contain the algorithm code that
implements the look-compute-beep cycle.
Inside of this method, particles are allowed to change their
pin configuration and send beeps and messages on the updated
configuration.
Note that beeps and messages sent in the current round will
be readable in both the ActivateMove() and
ActivateBeep() calls in the next round.
Declaration
public override void ActivateBeep()
Overrides
ActivateFinalPrunePhase()
Declaration
private void ActivateFinalPrunePhase()
ActivateMove()
This is one part of the main activation logic of the particle.
It is called exactly once in each round and should contain the
algorithm code that implements the look-compute-move cycle.
After the movements are executed, ActivateBeep()
is called within the same round.
Inside of this method, particles are allowed to release bonds,
define which bonds should be marked, and schedule movements.
Only the last movement operation scheduled in this method will
be applied.
Declaration
public override void ActivateMove()
Overrides
ActivatePortalPhase()
Declaration
private void ActivatePortalPhase()
DeterminePortalNeighbors(Direction)
Sets the neighbor portal flags of this amoebot. Direction 1
indicates the "top" neighbor edge, direction 2 the "bottom"
neighbor edge. The direction will be unequal to
NONE if and only if this amoebot
is the unique amoebot with the edge to that neighboring portal.
Declaration
private void DeterminePortalNeighbors(Direction portalDir)
Parameters
Type |
Name |
Description |
Direction |
portalDir |
The direction of the portal axis.
|
Init(bool, bool)
Declaration
public void Init(bool isSource = false, bool isDest = false)
Parameters
Type |
Name |
Description |
bool |
isSource |
|
bool |
isDest |
|
IsChild(Direction)
Checks whether there is an amoebot in direction d
which has its parent direction pointing at this amoebot.
Declaration
private bool IsChild(Direction d)
Parameters
Type |
Name |
Description |
Direction |
d |
The direction to check.
|
Returns
Type |
Description |
bool |
true if and only if we have a shortest path tree
child in direction d .
|
IsFinished()
Checks whether this particle has finished its algorithm.
Override this method to return true
when a particle
is done executing the algorithm. Once all particles in the
system are finished, the simulation will stop automatically.
When a particle's state results in this method returning
true
, its activation methods should not change its
state any more.
Declaration
public override bool IsFinished()
Returns
Type |
Description |
bool |
true if and only if this particle has
finished its algorithm.
|
Overrides
Prune()
Sets this amoebot's internal state to pruned. Hereafter,
the amoebot will not participate in the rest of the
algorithm. Also sets the correct color.
Declaration
SetColor()
Sets the color of this amoebot according to its
current phase and state.
Declaration
SetupPortalNeighborCircuits(Direction)
Sets up one circuit for each neighbor of a portal along
the given axis. The "top" partition set will have ID 0
and the "bottom" partition set will have ID 1. If there
is no neighbor in one of the directions, no partition set
will be created for that direction.
Declaration
private void SetupPortalNeighborCircuits(Direction portalDir)
Parameters
Type |
Name |
Description |
Direction |
portalDir |
The direction of the portal axis.
|
SetupSimplePortalCircuit(Direction)
Sets up a simple circuit connecting all pins along the given axis
into partition set 0.
Declaration
private void SetupSimplePortalCircuit(Direction portalDir)
Parameters
Type |
Name |
Description |
Direction |
portalDir |
The direction of the portal axis.
|
ShowPortalGraph(ParticleSystem, Particle)
Declaration
[StatusInfo("Show Portal Graph", "Draws the (implicit) portal graph during the first phase of the algorithm. The root portal is marked red, the destination portals are marked blue. If the root portal contains a destination, it is marked magenta.", false)]
public static void ShowPortalGraph(ParticleSystem system, Particle selectedParticle)
Parameters
ShowTree(ParticleSystem, Particle)
Declaration
[StatusInfo("Show SP Tree", "Draws the parent edges of all amoebots as soon as they are available. This will only work during the second phase of the algorithm.", false)]
public static void ShowTree(ParticleSystem system, Particle selectedParticle)
Parameters
UpdateParentCounter(Direction, int)
Increments the parent counter of the parent in
direction d
in case a beep
was received on the partition set with ID
pSet
and there is a neighbor
in that direction.
Declaration
private void UpdateParentCounter(Direction d, int pSet)
Parameters
Type |
Name |
Description |
Direction |
d |
The direction of the neighbor to update.
|
int |
pSet |
The partition set to check.
|