Class Sub1SPF

Subroutine implementation of the single-source shortest path algorithm (SingleSourceSPParticle).

Usage:

• Initialize by calling Init(bool, bool, bool, List<Direction>, int). There must be exactly one source in each connected set of amoebots running this subroutine.
• Run SetupPC(PinConfiguration), then ActivateSend() to start the procedure.
• In the round immediately following a ActivateSend() call, ActivateReceive() must be called. There can be an arbitrary break until the next pin configuration setup and ActivateSend() call. Continue this until the procedure is finished.
• You can call IsFinished() immediately after ActivateReceive() to check whether the procedure is finished. If it is, you can find each amoebot's parent direction in the resulting shortest path tree using Parent(). Some amoebots may not be part of a shortest path to a destination, so they will have no parent.

Inheritance

object

Subroutine

Sub1SPF

Namespace: AS2.Subroutines.SingleSourceSP

Assembly: .dll

Syntax

public class Sub1SPF : Subroutine

Constructors

Sub1SPF(Particle, SubETT)

Declaration

public Sub1SPF(Particle p, SubETT ett = null)

Parameters

Type	Name	Description
Particle	p
SubETT	ett

Fields

controlColor

Declaration

private BinAttributeBool controlColor

Field Value

Type	Description
BinAttributeBool

destColor

Declaration

private static readonly Color destColor

Field Value

Type	Description
Color

destPortalColor

Declaration

private static readonly Color destPortalColor

Field Value

Type	Description
Color

dirCounter

Declaration

private BinAttributeInt dirCounter

Field Value

Type	Description
BinAttributeInt

ett

Declaration

private SubETT ett

Field Value

Type	Description
SubETT

finished

Declaration

private BinAttributeBool finished

Field Value

Type	Description
BinAttributeBool

ignoreDirs

Declaration

private BinAttributeBitField ignoreDirs

Field Value

Type	Description
BinAttributeBitField

instanceIdx

Declaration

private BinAttributeInt instanceIdx

Field Value

Type	Description
BinAttributeInt

isDest

Declaration

private BinAttributeBool isDest

Field Value

Type	Description
BinAttributeBool

isSource

Declaration

private BinAttributeBool isSource

Field Value

Type	Description
BinAttributeBool

manualCtrUpdate0

Declaration

private BinAttributeBool manualCtrUpdate0

Field Value

Type	Description
BinAttributeBool

manualCtrUpdate1

Declaration

private BinAttributeBool manualCtrUpdate1

Field Value

Type	Description
BinAttributeBool

mixedPortalColor

Declaration

private static readonly Color mixedPortalColor

Field Value

Type	Description
Color

nbrPortal1

Declaration

private BinAttributeDirection nbrPortal1

Field Value

Type	Description
BinAttributeDirection

nbrPortal2

Declaration

private BinAttributeDirection nbrPortal2

Field Value

Type	Description
BinAttributeDirection

onDestPortal

Declaration

private BinAttributeBool onDestPortal

Field Value

Type	Description
BinAttributeBool

onSourcePortal

Declaration

private BinAttributeBool onSourcePortal

Field Value

Type	Description
BinAttributeBool

parentCounters

Declaration

private BinAttributeInt[] parentCounters

Field Value

Type	Description
BinAttributeInt[]

parentDir

Declaration

private BinAttributeDirection parentDir

Field Value

Type	Description
BinAttributeDirection

pruned

Declaration

private BinAttributeBool pruned

Field Value

Type	Description
BinAttributeBool

round

Declaration

private BinAttributeInt round

Field Value

Type	Description
BinAttributeInt

sourceColor

Declaration

private static readonly Color sourceColor

Field Value

Type	Description
Color

sourcePortalColor

Declaration

private static readonly Color sourcePortalColor

Field Value

Type	Description
Color

state1

Declaration

private ParticleAttribute<int> state1

Field Value

Type	Description
ParticleAttribute<int>

state2

Declaration

private ParticleAttribute<int> state2

Field Value

Type	Description
ParticleAttribute<int>

Methods

ActivateReceive()

The first half of the subroutine activation. Must be called in the round immediately after ActivateSend() was called.

Declaration

public void ActivateReceive()

ActivateSend()

The second half of the subroutine activation. Before this can be called, the pin configuration set up by SetupPC(PinConfiguration) must be planned.

Declaration

public void ActivateSend()

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, bool, List<Direction>, int)

Initializes the subroutine.

Declaration

public void Init(bool isSource, bool isDest, bool controlColor = false, List<Direction> ignoreDirections = null, int instanceIndex = 0)

Parameters

Type	Name	Description
bool	isSource	Whether this amoebot is the source. Exactly one amoebot in the component running this subroutine must be the source.
bool	isDest	Whether this amoebot is a destination.
bool	controlColor	Whether the subroutine should control the amoebot's color.
List<Direction>	ignoreDirections	The directions in which neighbors should be ignored.
int	instanceIndex	The index of this instance. Instances that run at the same time on the same amoebot must have different indices.

IsFinished()

Checks whether the SPF procedure has finished.

Declaration

public bool IsFinished()

Returns

Type	Description
bool	true if and only if the shortest paths to the source have been found.

IsPruned()

Declaration

public bool IsPruned()

Returns

Type	Description
bool

PSetPortal1(Direction)

The ID of the first partition set on the given portal axis.

Declaration

private int PSetPortal1(Direction portalDir)

Parameters

Type	Name	Description
Direction	portalDir

Returns

Type	Description
int

PSetPortal2(Direction)

The ID of the second partition set on the given portal axis.

Declaration

private int PSetPortal2(Direction portalDir)

Parameters

Type	Name	Description
Direction	portalDir

Returns

Type	Description
int

Parent()

Gets the parent direction of this amoebot after the procedure is finished.

Declaration

public Direction Parent()

Returns

Type	Description
Direction	The direction of this amoebot in the shortest path forest. NONE if the amoebot has no parent (this is the case if it is the source/root or has been pruned).

SetColor()

Declaration

private void SetColor()

SetupGlobalCircuit(PinConfiguration, int, int)

Sets up a global circuit using the given pin offset.

Declaration

private void SetupGlobalCircuit(PinConfiguration pc, int offset, int pSet)

Parameters

Type	Name	Description
PinConfiguration	pc	The pin configuration to modify.
int	offset	The pin offset.
int	pSet	The partition set ID.

SetupPC(PinConfiguration)

Sets up the pin configuration required for the ActivateSend() call. The pin configuration is not planned by this method.

Declaration

public void SetupPC(PinConfiguration pc)

Parameters

Type	Name	Description
PinConfiguration	pc	The pin configuration to modify.

SetupPortalNeighborCircuits(PinConfiguration, Direction)

Sets up one circuit for each neighbor of a portal along the given axis. The "top" partition set will have the ID PSetPortal1(Direction) and the "bottom" partition set the ID PSetPortal2(Direction). If there is no neighbor in one of the directions, no partition set will be created for that direction. Also, if no partition set can be created, the corresponding manual update flag is set.

Declaration

private void SetupPortalNeighborCircuits(PinConfiguration pc, Direction portalDir)

Parameters

Type	Name	Description
PinConfiguration	pc	The pin configuration to modify.
Direction	portalDir	The direction of the portal axis.

SetupSimplePortalCircuit(PinConfiguration, Direction, int, int)

Sets up a simple circuit connecting all amoebots along the given portal direction, using the given pin offset in that direction. No partition set will be created if there are no neighbors on the portal axis.

Declaration

private void SetupSimplePortalCircuit(PinConfiguration pc, Direction portalDir, int pinOffset, int partitionSet = 0)

Parameters

Type	Name	Description
PinConfiguration	pc	The pin configuration to modify.
Direction	portalDir	The direction of the portal axis.
int	pinOffset	The pin offset in portal direction.
int	partitionSet	The partition set ID to use.

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 dir, int pSet)

Parameters

Type	Name	Description
Direction	dir	The direction of the neighbor to update.
int	pSet	The partition set to check.