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

object

ParticleAlgorithm

SingleSourceSPParticle

Namespace: AS2.Algos.SingleSourceSP

Assembly: .dll

Syntax

public class SingleSourceSPParticle : ParticleAlgorithm

Constructors

SingleSourceSPParticle(Particle)

Declaration

public SingleSourceSPParticle(Particle p)

Parameters

Type	Name	Description
Particle	p

Fields

destColor

Declaration

private static readonly Color destColor

Field Value

Type	Description
Color

destPortalColor

Declaration

private static readonly Color destPortalColor

Field Value

Type	Description
Color

ett

Declaration

private SubETT ett

Field Value

Type	Description
SubETT

isDest

Declaration

private ParticleAttribute<bool> isDest

Field Value

Type	Description
ParticleAttribute<bool>

isDestRepr

Declaration

private ParticleAttribute<bool> isDestRepr

Field Value

Type	Description
ParticleAttribute<bool>

isRootRepr

Declaration

private ParticleAttribute<bool> isRootRepr

Field Value

Type	Description
ParticleAttribute<bool>

isSource

Declaration

private ParticleAttribute<bool> isSource

Field Value

Type	Description
ParticleAttribute<bool>

mixedPortalColor

Declaration

private static readonly Color mixedPortalColor

Field Value

Type	Description
Color

nbrPortalDir1

Declaration

private ParticleAttribute<Direction> nbrPortalDir1

Field Value

Type	Description
ParticleAttribute<Direction>

nbrPortalDir2

Declaration

private ParticleAttribute<Direction> nbrPortalDir2

Field Value

Type	Description
ParticleAttribute<Direction>

onDestPortal

Declaration

private ParticleAttribute<bool> onDestPortal

Field Value

Type	Description
ParticleAttribute<bool>

onRootPortal

Declaration

private ParticleAttribute<bool> onRootPortal

Field Value

Type	Description
ParticleAttribute<bool>

parent

Declaration

private ParticleAttribute<Direction> parent

Field Value

Type	Description
ParticleAttribute<Direction>

parentCounters

Declaration

private ParticleAttribute<int>[] parentCounters

Field Value

Type	Description
ParticleAttribute<int>[]

phase

Declaration

private ParticleAttribute<SingleSourceSPParticle.Phase> phase

Field Value

Type	Description
ParticleAttribute<SingleSourceSPParticle.Phase>

portalAxisDir

Declaration

private ParticleAttribute<Direction> portalAxisDir

Field Value

Type	Description
ParticleAttribute<Direction>

pruned

Declaration

private ParticleAttribute<bool> pruned

Field Value

Type	Description
ParticleAttribute<bool>

round

Declaration

private ParticleAttribute<int> round

Field Value

Type	Description
ParticleAttribute<int>

sourceColor

Declaration

private static readonly Color sourceColor

Field Value

Type	Description
Color

sourcePortalColor

Declaration

private static readonly Color sourcePortalColor

Field Value

Type	Description
Color

Properties

GenerationMethod

Declaration

public static string GenerationMethod { get; }

Property Value

Type	Description
string

Name

Declaration

public static string Name { get; }

Property Value

Type	Description
string

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

Type	Description
int

Overrides

ParticleAlgorithm.PinsPerEdge

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

ParticleAlgorithm.ActivateBeep()

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

ParticleAlgorithm.ActivateMove()

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

ParticleAlgorithm.IsFinished()

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

private void Prune()

SetColor()

Sets the color of this amoebot according to its current phase and state.

Declaration

private void SetColor()

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

Type	Name	Description
ParticleSystem	system
Particle	selectedParticle

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

Type	Name	Description
ParticleSystem	system
Particle	selectedParticle

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.