Package org.evoludo.simulator

Class Geometry

Object

Geometry

public class Geometry
extends Object

Instances of Geometry represent the interaction and/or competition structure of the population. For a list of currently implemented geometries, Geometry.Type.

Author:

Christoph Hauert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	Geometry.Type	The types of graph geometries.

Field Summary

Fields

Modifier and Type	Field	Description
double	avgIn	The average number of incoming links.
double	avgOut	The average number of outgoing links.
double	avgTot	The average number of the sum of incoming and outgoing links.
double	connectivity	The degree or connectivity of the graph or (average) number of neighbours.
(package private) EvoLudo	engine	The pacemaker of all models.
private boolean	evaluated	true if geometry has been evaluated.
boolean	fixedBoundary	Flag indicating whether boundaries are fixed or periodic (default).
private Geometry.Type	geometry	The geometry of the graph.
int[]	hierarchy	The number of units in each hierarchical level.
double	hierarchyweight	The strength of interactions between hierarchical levels.
int[][]	in	This is the neighbourhood network structure of incoming links.
boolean	interCompSame	true if the interaction and competition graphs are the same.
boolean	isDynamic	true if the network structure is ephemeral.
boolean	isRegular	true if the network structure is regular (all nodes have the same number of neighbours).
boolean	isRewired	true if the graph includes rewired edges or links.
boolean	isUndirected	true if the graph is undirected.
boolean	isValid	true if the network structure has been successfully initialized.
int[]	kin	The array storing the number of incoming neighbours for each node, i.e.
int[]	kout	The array storing the number of outgoing neighbours for each node, i.e.
int	linearAsymmetry	The difference between the number of neighbours on the left and the right in linear, 1D lattices.
(package private) Logger	logger	Logger for keeping track of and reporting events and issues.
protected static final int	MAX_TRIALS	Maximum number of attempts to generate a graph structure.
int	maxIn	The maximum number of incoming links.
int	maxOut	The maximum number of outgoing links.
int	maxTot	The maximum sum of incoming and outgoing links.
int	minIn	The minimum number of incoming links.
int	minOut	The minimum number of outgoing links.
int	minTot	The minimum sum of incoming and outgoing links.
String	name	The name of this graph.
private Network2D	network2D	Local storage for the 2D representation of this graph.
private Network3D	network3D	Local storage for the 3D representation of this graph.
private static final int[]	nulllink	Convenience field.
IBSPopulation	opponent	The IBS population representing the opponent.
int[][]	out	This is the neighbourhood network structure of outgoing links.
double	pAddwire	Fraction of directed links to add or rewire.
double	pKlemm	The probability for adding links adjust small-world properties of Klemm-Eguiluz scale-free networks.
(package private) IBSPopulation	population	The IBS population that has this geometry.
double	pRewire	Fraction of undirected links to add or rewire.
protected int[]	rawhierarchy	The number of units in each hierarchical level requested.
double	sfExponent	The exponent in scale-free networks.
int	size	The number of nodes in the graph.
Geometry.Type	subgeometry	Only used for hierarchical geometries to specify the geometry of each level.
int	superstar_amplification	The chain length in superstars.
int	superstar_petals	The number of petals or tips in superstars.

Constructor Summary

Constructors

Constructor	Description
Geometry(EvoLudo engine)	Instantiates a new geometry for data visualization with pacemaker engine.
Geometry(EvoLudo engine, Module module)	Instantiates a new geometry for intra-species module module with pacemaker engine.
Geometry(EvoLudo engine, Module popModule, Module oppModule)	Instantiates a new geometry for inter-species module popModule and opponent oppModule with pacemaker engine.

Method Summary

Modifier and Type	Method	Description
boolean	addDirected()	Add directed links to network.
void	addEdgeAt(int from, int to)	Add edge (undirected link) from node from to node to.
void	addLinkAt(int from, int to)	Add link (directed link) from node from to node to.
boolean	addUndirected()	Add undirected links.
void	alloc()	Allocate the memory neccessary to store the network structure.
boolean	check()	Check the feasibility of the network parameters.
boolean	checkConnections()	Check consistency of links.
void	clearLinksFrom(int idx)	Remove all outgoing links from node idx.
void	clearLinksTo(int idx)	Remove all incoming links to node idx.
Geometry	clone()	Clone geometry.
void	decodeGeometry(Plist plist)	Decode the geometry from the plist.
Geometry	deriveCompetitionGeometry()	Derive competition geometry from current (interaction) geometry.
Geometry	deriveInteractionGeometry(IBSPopulation opp)	Derive interaction geometry from current (competition) geometry.
static boolean	displayUniqueGeometry(Geometry inter, Geometry comp)	Checks whether a single graphical representation can be used for the interaction and competition graphs.
static boolean	displayUniqueGeometry(Module module)	Checks whether a single graphical representation can be used for the interaction and competition graphs.
String	encodeGeometry()	Encode geometry as a plist string fragment.
boolean	equals(Geometry geo)	Check if this Geometry and geo refer to the same structures.
void	evaluate()	Evaluate geometry.
String	getName()	Gets the name of this graph.
Network2D	getNetwork2D()	Get the 2D network representation of this graph.
Network3D	getNetwork3D()	Get the 3D network representation of this graph.
IBSPopulation	getOpponent()	Gets the opponent of the population represented by this graph.
Geometry.Type	getType()	Get the type of this geometry.
void	init()	Entry point to initialize the network structure according to the given parameters.
void	initGeometryAmplifier()	Generates a strong undirected amplifier of selection.
void	initGeometryComplete()	Generates a complete graph where every node is connected to every other node.
void	initGeometryCube()	Generates a cubic (3D) regular lattice.
private boolean	initGeometryDegreeDistr(int[] distr)	Utility method to generate network with a given degree distribution.
void	initGeometryDesarguesGraph()	Generates a Desargues graph, named after Girard Desargues (1591–1661).
void	initGeometryDodekahedronGraph()	Generates a dodecahedron graph.
void	initGeometryFranklinGraph()	Generates a Franklin graph.
void	initGeometryFruchtGraph()	Generates a Frucht graph.
void	initGeometryHeawoodGraph()	Generates a Heawood graph.
void	initGeometryHierarchical()	Generates hierarchical graphs.
private void	initGeometryHierarchy(int level, int start)	Utility method to generate hierarchical graphs.
private int	initGeometryHierarchyMeanfield(int start, int end)	Utility method to generate hierarchical well-mixed subpopulations (demes).
private int	initGeometryHierarchySquare(int start, int end)	Utility method to generate hierarchical square lattices with degree degree.
void	initGeometryHoneycomb()	Generates a hexagonal regular lattice (degree \(6\)).
void	initGeometryIcosahedronGraph()	Generates an icosahedron graph.
void	initGeometryLinear()	Generates a linear chain (1D lattice).
void	initGeometryMeanField()	Generates well-mixed graph, also termed mean-field networks or unstructured populations.
void	initGeometryRandomGraph()	Generate a (connected, directed) random graph.
void	initGeometryRandomGraphDirected()	Generate a (connected, directed) random graph.
void	initGeometryRandomRegularGraph()	Generate a (connected, undirected) random regular graph.
void	initGeometryScaleFree()	Generate a (connected, undirected) scale-free network.
void	initGeometryScaleFreeBA()	Generate a (connected, undirected) scale-free network following the procedure by Barabási & Albert (1999).
void	initGeometryScaleFreeKlemm()	Generate a (connected, undirected) scale-free network following the procedure by Klemm & Eguíluz (2001).
void	initGeometrySquare()	Generates a square regular lattice (chessboard).
private void	initGeometrySquare(int side, int fullside, int offset)	Utility method to generate a square lattice with arbitrarily large neighbourhoods.
private void	initGeometrySquareMoore(int side, int fullside, int offset)	Utility method to generate a square lattice with Moore neighbourhood.
private void	initGeometrySquareSelf(int side, int fullside, int offset)	Utility method to generate a square lattice with exclusively 'self'-connections.
private void	initGeometrySquareVonNeumann(int side, int fullside, int offset)	Utility method to generate a square lattice with von Neumann neighbourhood.
private void	initGeometrySquareVonNeumann2nd(int side, int fullside, int offset)	Utility method to generate a square lattice with von Neumann neighbourhood.
void	initGeometryStar()	Generates a star geometry with a hub in the middle that is connected to all other nodes (leaves).
void	initGeometrySuperstar()	Generates a superstar geometry, which represents a strong directed amplifier of selection.
void	initGeometrySuppressor()	Generates a strong undirected suppressor of selection.
void	initGeometryTietzeGraph()	Generates a Tietze graph.
void	initGeometryTriangular()	Generates a triangular regular lattice (degree \(3\)).
void	initGeometryWheel()	Generates a wheel geometry, which corresponds to a ring (periodic 1D lattice) with a hub in the middle that is connected to all nodes in the ring (resembling spokes).
private void	initRRGCore(RNGDistribution rng, int start, int end, int degree)	Utility method to generate an (almost) regular graph as the core of an evolutionary amplifier.
boolean	isGraphConnected()	Check if graph is connected.
boolean	isGraphConnected(int node, boolean[] check)	Check if any other node can be reached from node.
boolean	isInterspecies()	Check if graph refers to inter-species model.
boolean	isLattice()	Utility method to determine whether a given geometry type is a lattice.
boolean	isNeighborOf(int focal, int check)	Check if check is a neighbor of focal (not necessarily the other way round).
boolean	isUniqueGeometry()	Check if current geometry unique.
private boolean	isUniqueGeometry(Geometry.Type geo)	Helper method to check uniqueness of the geometry geo.
boolean	parse(String cli)	Parse string of geometry specifications cli.
void	printParams(PrintStream output)	Report relevant parameters of geometry and print to output.
void	removeEdgeAt(int from, int to)	Remove edge (undirected link) from node from to node to.
private void	removeInLink(int from, int to)	Remove incoming link (directed link) to node to from node from.
void	removeLinkAt(int from, int to)	Remove link (directed link) from node from to node to.
private void	removeOutLink(int from, int to)	Remove outgoing link (directed link) from node from to node to.
void	reset()	Reset the network structure and free the allocated memory.
void	rewire()	Add/rewire directed and undirected random links.
boolean	rewireDirected()	Rewire directed links.
void	rewireEdgeAt(int from, int to, int prev)	Rewire edge (undirected link) from node from to node prev to node to.
void	rewireLinkAt(int from, int to, int prev)	Rewire directed link from node from to node prev to node to.
private boolean	rewireNeighbourEdge(RNGDistribution rng, int nodeA, int nodeB, int[] done, int nDone)	Utility method to rewire an edge between two nodes.
boolean	rewireUndirected(double prob)	Rewire undirected links.
void	setName(String name)	Sets the name of this graph.
void	setNetwork2D(Network2D net)	Set the 2D network representation of this graph.
void	setNetwork3D(Network3D net)	Set the 3D network representation of this graph.
boolean	setSize(int size)	Sets the number of nodes in the graph to size.
void	setType(Geometry.Type type)	Set the type of this geometry.
private static void	swap(int[] x, int a, int b)	Swap elements with indices a and b in array x
private boolean	swapEdges(int a, int an, int b, int bn)	Utility method to swap edges (undirected links) between nodes: change link a-an to a-bn and b-bn to b-an.
String	usage()	Get the usage description for the command line option --geometry.

Methods inherited from class Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

engine

EvoLudo engine

The pacemaker of all models. Interface with the outside world.

population

IBSPopulation population

The IBS population that has this geometry.

opponent

public IBSPopulation opponent

The IBS population representing the opponent. For intra-species interactions population==opponent holds.

logger

Logger logger

Logger for keeping track of and reporting events and issues.

network2D

private Network2D network2D

Local storage for the 2D representation of this graph.

network3D

private Network3D network3D

Local storage for the 3D representation of this graph.

geometry

private Geometry.Type geometry

The geometry of the graph.

subgeometry

public Geometry.Type subgeometry

Only used for hierarchical geometries to specify the geometry of each level.

See Also:

• initGeometryHierarchical()

name

public String name

The name of this graph. Typically this is "interaction" or "competition" for the correpsonding graphs, or "structure" if the two graphs are the same. In multi-species models the name of the species may be prepended.

in

public int[][] in

This is the neighbourhood network structure of incoming links. More specifically, for each node a list of indices of neighbouring nodes with links to this one.

Requirements/notes:

in[i].length does not necessarily reflect the number of neighbours! Use kin[i] instead. To minimize memory allocation requests in[i].length>kin[i] may hold. This is primarily important for dynamical networks.

out

public int[][] out

This is the neighbourhood network structure of outgoing links. More specifically, for each node a list of indices of neighbouring nodes that links point to.

Requirements/notes:

out[i].length does not necessarily reflect the number of neighbours! Use kout[i] instead. To minimize memory allocation requests out[i].length>kout[i] may hold. This is primarily important for dynamical networks.

kin

public int[] kin

The array storing the number of incoming neighbours for each node, i.e. the number of neighbours that have a link pointing to this one.

kout

public int[] kout

The array storing the number of outgoing neighbours for each node, i.e. the number of links pointing from this node to another.

size

public int size

The number of nodes in the graph.

fixedBoundary

public boolean fixedBoundary

Flag indicating whether boundaries are fixed or periodic (default).

rawhierarchy

protected int[] rawhierarchy

The number of units in each hierarchical level requested. Processed for feasibility and then stored in hierarchy.

See Also:

• check()
• initGeometryHierarchical()

hierarchy

public int[] hierarchy

The number of units in each hierarchical level. The lowest level refers to the number of nodes.

See Also:

• initGeometryHierarchical()

hierarchyweight

public double hierarchyweight

The strength of interactions between hierarchical levels. For example, with a strength \(p\) between the first and second level, the strength is \(p^2\) between the first and third. More generally, the interaction strength is \(p^n\), where \(n\) denotes the number of levels between the two interacting individuals.

See Also:

• initGeometryHierarchical()

minIn

public int minIn

The minimum number of incoming links.

See Also:

• evaluate()

maxIn

public int maxIn

The maximum number of incoming links.

See Also:

• evaluate()

avgIn

public double avgIn

The average number of incoming links.

See Also:

• evaluate()

minOut

public int minOut

The minimum number of outgoing links.

See Also:

• evaluate()

maxOut

public int maxOut

The maximum number of outgoing links.

See Also:

• evaluate()

avgOut

public double avgOut

The average number of outgoing links.

See Also:

• evaluate()

minTot

public int minTot

The minimum sum of incoming and outgoing links.

See Also:

• evaluate()

maxTot

public int maxTot

The maximum sum of incoming and outgoing links.

See Also:

• evaluate()

avgTot

public double avgTot

The average number of the sum of incoming and outgoing links.

See Also:

• evaluate()

superstar_petals

public int superstar_petals

The number of petals or tips in superstars.

See Also:

• initGeometrySuperstar()

superstar_amplification

public int superstar_amplification

The chain length in superstars.

See Also:

• initGeometrySuperstar()

sfExponent

public double sfExponent

The exponent in scale-free networks.

See Also:

• initGeometryScaleFree()

pKlemm

public double pKlemm

The probability for adding links adjust small-world properties of Klemm-Eguiluz scale-free networks.

See Also:

• initGeometryScaleFreeKlemm()

linearAsymmetry

public int linearAsymmetry

The difference between the number of neighbours on the left and the right in linear, 1D lattices.

connectivity

public double connectivity

The degree or connectivity of the graph or (average) number of neighbours.

pRewire

public double pRewire

Fraction of undirected links to add or rewire.

See Also:

• rewireUndirected(double)
• addUndirected()

pAddwire

public double pAddwire

Fraction of directed links to add or rewire.

See Also:

• rewireDirected()
• addDirected()

isUndirected

public boolean isUndirected

true if the graph is undirected.

isRewired

public boolean isRewired

true if the graph includes rewired edges or links.

interCompSame

public boolean interCompSame

true if the interaction and competition graphs are the same.

isDynamic

public boolean isDynamic

true if the network structure is ephemeral.

isRegular

public boolean isRegular

true if the network structure is regular (all nodes have the same number of neighbours).

isValid

public boolean isValid

true if the network structure has been successfully initialized.

nulllink

private static final int[] nulllink

Convenience field. Array of zero length for initialization and well-mixed populations.

MAX_TRIALS

protected static final int MAX_TRIALS

Maximum number of attempts to generate a graph structure.

See Also:

• Constant Field Values

evaluated

private boolean evaluated

true if geometry has been evaluated.

See Also:

• evaluate()

Constructor Details

Geometry

public Geometry(EvoLudo engine)

Instantiates a new geometry for data visualization with pacemaker engine.

Parameters:

engine - the pacemaker for running the model

See Also:

• Distribution.createGeometry(int)

Geometry

public Geometry(EvoLudo engine,
 Module module)

Instantiates a new geometry for intra-species module module with pacemaker engine.

Parameters:

engine - the pacemaker for running the model

module - the module with interaction parameters

Geometry

public Geometry(EvoLudo engine,
 Module popModule,
 Module oppModule)

Instantiates a new geometry for inter-species module popModule and opponent oppModule with pacemaker engine. For intra-species interactions population==opponent holds.

Parameters:

engine - the pacemaker for running the model

popModule - the module with interaction parameters

oppModule - the module of the opponent

Method Details

getName

public String getName()

Gets the name of this graph. Typically this is "Interaction" or "Competition" for the correpsonding graphs, or "Structure" if the two graphs are the same. In multi-species models the name of the species may be prepended.

Returns:

the name of the graph

See Also:

• setName(String)

setName

public void setName(String name)

Sets the name of this graph.

Parameters:

name - the name of this graph.

See Also:

• getName()

getType

public Geometry.Type getType()

Get the type of this geometry.

Returns:

the type of this geometry

setType

public void setType(Geometry.Type type)

Set the type of this geometry.

Parameters:

type - the type of this geometry

setNetwork2D

public void setNetwork2D(Network2D net)

Set the 2D network representation of this graph. This is purely for storage. The network is generated in Network2D.

Parameters:

net - the 2D network representation

getNetwork2D

public Network2D getNetwork2D()

Get the 2D network representation of this graph. This is purely for storage. The network is generated in Network2D.

Returns:

the 2D network representation of this graph

setNetwork3D

public void setNetwork3D(Network3D net)

Set the 3D network representation of this graph. This is purely for storage. The network is generated in Network3D.

Parameters:

net - the 3D network representation

getNetwork3D

public Network3D getNetwork3D()

Get the 3D network representation of this graph. This is purely for storage. The network is generated in Network3D.

Returns:

the 3D network representation of this graph.

setSize

public boolean setSize(int size)

Sets the number of nodes in the graph to size. This affects memory allocations in the model and hence a reset is required if the size changes.

Parameters:

size - the new size of the graph

Returns:

true if the graph size changed

getOpponent

public IBSPopulation getOpponent()

Gets the opponent of the population represented by this graph. For intra-species models this.opponent==this.population holds.

Returns:

the opponent population

isInterspecies

public boolean isInterspecies()

Check if graph refers to inter-species model. For intra-species models this.opponent==this.population holds.

Returns:

true for inter-species graphs.

displayUniqueGeometry

public static boolean displayUniqueGeometry(Geometry inter,
 Geometry comp)

Checks whether a single graphical representation can be used for the interaction and competition graphs. Two distinct graphical represntations are generally required if the two graphs differ but not if they both refer to the same lattice structure even if connectivities or boundary conditions are different.

Examples:

A single graphical representation is adequate:

1. if the interaction and competition graphs are identical,
2. if both the interaction and competition graphs are lattices, even if the boundary conditions or the connectivities are different,
3. but not if the interaction and competition graphs are separate instances of the same random structure, e.g. random regular graphs.

Requirements/notes:

1. Tooltips need to be careful to report the different graphs and neighborhoods properly.

Parameters:

inter - the interaction graph

comp - the competition graph

Returns:

true if a single graphical representation suffices, false if two separate graphical representations are required for the interaction and the competition graphs

See Also:

• displayUniqueGeometry(Geometry, Geometry)

displayUniqueGeometry

public static boolean displayUniqueGeometry(Module module)

Checks whether a single graphical representation can be used for the interaction and competition graphs.

Parameters:

module - the population whose interaction and competition structures to check

Returns:

true if a single graphical representation suffices

See Also:

• displayUniqueGeometry(Geometry, Geometry)

reset

public void reset()

Reset the network structure and free the allocated memory.

alloc

public void alloc()

Allocate the memory neccessary to store the network structure.

check

public boolean check()

Check the feasibility of the network parameters. If parameters need to be adjusted a warning is issued through the logger. Some changes require a reset of the model because they affect memory allocations (e.g. adjustments of the population size).

Returns:

true if reset is required

init

public void init()

Entry point to initialize the network structure according to the given parameters.

See Also:

• Geometry.Type
• parse(String)
• check()

printParams

public void printParams(PrintStream output)

Report relevant parameters of geometry and print to output.

Parameters:

output - the print stream to direct the output to

initGeometryMeanField

public void initGeometryMeanField()

Generates well-mixed graph, also termed mean-field networks or unstructured populations.

Requirements/notes:

In the limit of large population sizes the results of individual based simulations (IBS) must converge to those of the corresponding deterministic dynamical equations (ODE's) or, with mutations, the stochastic dynamical equations (SDE's).

initGeometryComplete

public void initGeometryComplete()

Generates a complete graph where every node is connected to every other node. This is very similar to well-mixed (unstructured) populations. The only difference is the potential treatment of the focal node. For example, in the Moran process offspring can replace their parent in the original formulation for well-mixed populations (birth-death updating) but this does not occur in complete networks where offspring replaces one of the parents neighbours.

Requirements/notes:

None.

See Also:

• Wikipedia: Complete graph
• initGeometryMeanField()

initGeometryHierarchical

public void initGeometryHierarchical()

Generates hierarchical graphs.

Requirements/notes:

Only well-mixed (complete) or square lattice graphs are currently supported.

initGeometryHierarchy

private void initGeometryHierarchy(int level,
 int start)

Utility method to generate hierarchical graphs.

Requirements/notes:

None.

Parameters:

level - the hierarchical level

start - the index of the first node to process

initGeometryHierarchyMeanfield

private int initGeometryHierarchyMeanfield(int start,
 int end)

Utility method to generate hierarchical well-mixed subpopulations (demes).

Requirements/notes:

None.

Parameters:

start - the index of the first node to process

end - the index of the last node to process

Returns:

the number of nodes processed

initGeometryHierarchySquare

private int initGeometryHierarchySquare(int start,
 int end)

Utility method to generate hierarchical square lattices with degree degree.

Requirements/notes:

None.

Parameters:

start - the index of the first node to process

end - the index of the last node to process

Returns:

the number of nodes processed

initGeometryLinear

public void initGeometryLinear()

Generates a linear chain (1D lattice). With asymmetric neighbours and fixed boundaries this represents the simplest suppressor of selection.

Requirements/notes:

1. May have different numbers of neighbours to the left and the right.
2. For inter-species interactions connectivities are \(+1\) and a connectivity of \(1\) is admissible.
3. Boundaries fixed or periodic (default).

initGeometryStar

public void initGeometryStar()

Generates a star geometry with a hub in the middle that is connected to all other nodes (leaves). The star structure is the simplest undirected evolutionary amplifier.

Requirements/notes:

Node \(0\) is the hub.

initGeometryWheel

public void initGeometryWheel()

Generates a wheel geometry, which corresponds to a ring (periodic 1D lattice) with a hub in the middle that is connected to all nodes in the ring (resembling spokes). The wheel structure is an undirected evolutionary amplifier but less than the star structure.

Requirements/notes:

Node \(0\) is the hub.

See Also:

• initGeometryStar()

initGeometrySuperstar

public void initGeometrySuperstar()

Generates a superstar geometry, which represents a strong directed amplifier of selection. The superstar consists of a central hub surrounded by \(p\) petals that are each equipped with a reservoir of size \(r\) and a linear chain of length \(k\) connecting the reservoir with the hub (last node of each chain). The hub connects to all reservoir nodes (in all petals) and all reservoir nodes in each petal connect to the first node in the linear chain. The superstar represents the best studied evolutionary amplifier of arbitrary strength (in the limit \(N\to\infty\) as well as \(p, r, k \to\infty\)).

Requirements/notes:

1. Population size: \(N=(r+k-1)p+1\) with \(r,k,p\) integer.
2. Strong amplification requires \(r\gg k,p\).
3. Node \(0\) is the hub.

See Also:

• Lieberman, E., Hauert, Ch. & Nowak, M. A. (2005) Evolutionary dynamics on graphs, Nature 433 312-316.

initGeometryAmplifier

public void initGeometryAmplifier()

Generates a strong undirected amplifier of selection.

Requirements/notes:

Population size: \(N=n^3+(1+a)n^2\) where \(n\) integer and a suitable \(a\geq 5\). Three types of nodes \(U=n^3\), \(V=n^2\) and \(W=N-U-V\) where \(W\) represents a regular graph core with degree \(n^2\), each node in \(U\) is a leaf and connected to a single node in \(V\), while each node in \(V\) is connected to \(n^2\) nodes in \(W\).

See Also:

• Giakkoupis, George (2016) Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs, arXiv 1611.01585

initRRGCore

private void initRRGCore(RNGDistribution rng,
 int start,
 int end,
 int degree)

Utility method to generate an (almost) regular graph as the core of an evolutionary amplifier.

Requirements/notes:

In contrast to initGeometryRandomRegularGraph() no extra effort is made to ensure regularity.

Parameters:

rng - the random number generator

start - the index of the first node in the (almost) regular graph

end - the index of the last node in the (almost) regular graph

degree - the degree/connectivity of the (almost) regular graph

rewireNeighbourEdge

private boolean rewireNeighbourEdge(RNGDistribution rng,
 int nodeA,
 int nodeB,
 int[] done,
 int nDone)

Utility method to rewire an edge between two nodes. This assumes that nodeA and nodeB are neighbours. Pick random node C from set done and node D a random neighbour of C. Now try to rewire the edge A-B to A-C and B-D or B-C and A-D, respectively. Returns false and do nothing if the edge would result in self-loops or double edges.

Parameters:

rng - the random number generator

nodeA - the first node with nodeB as neighbour

nodeB - the second node with nodeA as neighbour

done - the set of nodes to pick node C from

nDone - the number of nodes in done

Returns:

true if the edges are successfully rewired, false otherwise

initGeometrySuppressor

public void initGeometrySuppressor()

Generates a strong undirected suppressor of selection.

Requirements/notes:

Population size: \(N=n^2(1+n(1+n))=n^2+n^3+n^4\) for \(n\) integer. With three types of nodes \(U=n^3\), \(V=n^4\) and \(W=n^2\), each node in \(V\) is connected to one node in \(U\) and to all in \(W\).

See Also:

• Giakkoupis, George (2016) Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs, arXiv 1611.01585

initGeometrySquare

public void initGeometrySquare()

Generates a square regular lattice (chessboard). The most common lattices are the von Neumann lattice with four nearest neighbours (north, south, east and west) as well as the Moore lattice with eight nearest neighbours (chess king's moves).

Requirements/notes:

1. Integer square population size, \(N=n^2\).
2. Admissible connectivities: \(4\) (von Neumann) or \(3\times 3-1=8\) (Moore), \(5\times 5-1=24\), \(7\times 7-1=48\) etc.
3. For inter-species interactions connectivities are \(+1\) and a connectivity of \(1\) is admissible.
4. Boundaries are periodic by default.
5. For SQUARE_MOORE interactions with Group.SAMPLING_ALL and group sizes between 2 and 8 (excluding boundaries) relies on a particular arrangement of the neighbors, see IBSDPopulation.playGroupGameAt(IBSGroup) and IBSCPopulation.playGroupGameAt(IBSGroup).

See Also:

• Wikipedia: von Neumann neighborhood
• Wikipedia: Moore neighborhood

initGeometrySquareSelf

private void initGeometrySquareSelf(int side,
 int fullside,
 int offset)

Utility method to generate a square lattice with exclusively 'self'-connections.

Requirements/notes:

1. Makes only sense in inter-species interactions.
2. Inter-species interactions include 'self'-connections.
3. Hierarchical structures may call this method recursively.
4. Neighbourhood corresponds to a \(3\times 3\), \(5\times 5\), \(7\times 7\), etc. area.
5. Boundaries fixed or periodic (default).

Parameters:

side - the side length of the (sub) lattice

fullside - the full side length of the entire lattice

offset - the offset to the sub-lattice

initGeometrySquareVonNeumann

private void initGeometrySquareVonNeumann(int side,
 int fullside,
 int offset)

Utility method to generate a square lattice with von Neumann neighbourhood.

Requirements/notes:

1. Inter-species interactions include 'self'-connections.
2. Hierarchical structures may call this method recursively.
3. Neighbourhood corresponds to a \(3\times 3\), \(5\times 5\), \(7\times 7\), etc. area.
4. Boundaries fixed or periodic (default).

Parameters:

side - the side length of the (sub) lattice

fullside - the full side length of the entire lattice

offset - the offset to the sub-lattice

initGeometrySquareVonNeumann2nd

private void initGeometrySquareVonNeumann2nd(int side,
 int fullside,
 int offset)

Utility method to generate a square lattice with von Neumann neighbourhood.

Requirements/notes:

1. Inter-species interactions include 'self'-connections.
2. Hierarchical structures may call this method recursively.
3. Neighbourhood corresponds to a \(3\times 3\), \(5\times 5\), \(7\times 7\), etc. area.
4. Boundaries fixed or periodic (default).

Parameters:

side - the side length of the (sub) lattice

fullside - the full side length of the entire lattice

offset - the offset to the sub-lattice

initGeometrySquareMoore

private void initGeometrySquareMoore(int side,
 int fullside,
 int offset)

Utility method to generate a square lattice with Moore neighbourhood.

Requirements/notes:

1. Inter-species interactions include 'self'-connections.
2. Hierarchical structures may call this method recursively.
3. Boundaries fixed or periodic (default).

Parameters:

side - the side length of the (sub) lattice

fullside - the full side length of the entire lattice

offset - the offset to the sub-lattice

initGeometrySquare

private void initGeometrySquare(int side,
 int fullside,
 int offset)

Utility method to generate a square lattice with arbitrarily large neighbourhoods.

Requirements/notes:

1. Inter-species interactions include 'self'-connections.
2. Hierarchical structures may call this method recursively.
3. Neighbourhood corresponds to a \(3\times 3\), \(5\times 5\), \(7\times 7\), etc. area.
4. Boundaries fixed or periodic (default).

Parameters:

side - the side length of the (sub) lattice

fullside - the full side length of the entire lattice

offset - the offset to the sub-lattice

initGeometryCube

public void initGeometryCube()

Generates a cubic (3D) regular lattice.

Requirements/notes:

1. Integer cube population size, \(N=n^3\).
2. Admissible connectivities: \(6\) or \(3\times 3\times 3-1=26\), \(5\times 5\times 5-1\), \(7\times 7\times 7-1\) etc.
3. For inter-species interactions connectivities are \(+1\) and a connectivity of \(1\) is admissible.
4. Boundaries fixed or periodic (default).
5. For \(N=25'000\) a lattice is generated representing the NOVA installation in the Zürich main train station (2006-20012). EvoLudo was launched on the NOVA on September 9, 2009 to commemorate the bicentenary of Darwin and 150 years since the publication of his On the Origin of Species.

See Also:

• Wikipedia: Zürich HB, NOVA
• Wikipedia: Zürich HB, NOVA (more extensive, in German)

initGeometryHoneycomb

public void initGeometryHoneycomb()

Generates a hexagonal regular lattice (degree \(6\)). Also called a triangular lattice depending on whether the focus is on the nodes or on the tiles.

Requirements/notes:

1. Even integer square population size, i.e. \(N=n^2\) where \(n\) is even.
2. Boundaries fixed or periodic (default).

See Also:

• Wikipedia: Triangular tiling
• initGeometryTriangular()

initGeometryTriangular

public void initGeometryTriangular()

Generates a triangular regular lattice (degree \(3\)). Also called a hexagonal lattice depending on whether the focus is on the nodes or on the tiles.

Requirements/notes:

1. Even integer square population size, i.e. \(N=n^2\) where \(n\) is even.
2. Boundaries fixed or periodic (default).

See Also:

• Wikipedia: Hexagonal lattice
• initGeometryHoneycomb()

initGeometryFruchtGraph

public void initGeometryFruchtGraph()

Generates a Frucht graph. The Frucht graph is the smallest regular graph without any further symmetries. A cubic graph with \(12\) nodes and no automorphisms apart from the identity map.

Requirements/notes:

1. No automorphisms, \(k=3, N=12\).
2. The numbering of the nodes follows McAvoy & Hauert (2015).

See Also:

• Wikipedia: Frucht graph
• Wikipedia: Graph automorphism
• "Frucht, R. (1939), Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Mathematica, 6: 239–250"
• McAvoy, A. & Hauert, C. (2015) Structural Symmetry in Evolutionary Games J. R. Soc. Interface 12 20150420.

initGeometryTietzeGraph

public void initGeometryTietzeGraph()

Generates a Tietze graph. Tietze’s graph is a (regular) cubic graph with twelve vertices but with a higher degree of symmetry than the Frucht graph. Tietze’s graph has twelve automorphisms but is not vertex-transitive.

Requirements/notes:

\(12\) automorphisms, \(k=3, N=12\).

See Also:

• Wikipedia: Tietze's graph
• Wikipedia: Graph automorphism
• "Tietze, Heinrich (1910), Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen, DMV Annual Report, 19: 155–159"

initGeometryFranklinGraph

public void initGeometryFranklinGraph()

Generates a Franklin graph. The Franklin graph is another a cubic graph with twelve nodes but is also vertex-transitive. Intuitively speaking, vertex transitivity means that the graph looks the same from the perspective of every node.

Requirements/notes:

Vertex-transitive graph, \(k=3, N=12\).

See Also:

• Wikipedia: Franklin graph
• Wikipedia: Vertex-transitive graph
• Franklin, P. A Six Color Problem. J. Math. Phys. 13, 363-379, 1934.

initGeometryHeawoodGraph

public void initGeometryHeawoodGraph()

Generates a Heawood graph. No cubic symmetric graph with \(12\) vertices exists. The closest comparable graph is the Heawood graph, which cubic and symmetric but with \(14\) nodes.

Symmetric graphs satisfy the stronger structural symmetry requirements of arc-transitivity. intuitively speaking, arc-transitivity means that not only does the graph look the same from the perspective of every node but also that if a pair of neighbouring individuals is randomly relocated to some other neighbouring pair of nodes, the two individuals are not able to tell whether and where they have been moved even when both are aware of the overall graph structure and share their conclusions.

Requirements/notes:

Symmetric graph, \(k=3, N=14\).

See Also:

• Wikipedia: Heawood graph
• Wikipedia: Symmetric graph (arc-transitive)
• "Heawood, P. J. (1890) Map colouring theorems. Quarterly J. Math. Oxford Ser. 24: 322–339."

initGeometryIcosahedronGraph

public void initGeometryIcosahedronGraph()

Generates an icosahedron graph. A symmetric graph with \(12\) nodes and degree \(5\).

Requirements/notes:

Symmetric graph, \(k=5, N=12\).

See Also:

• Wikipedia: Icosahedron

initGeometryDodekahedronGraph

public void initGeometryDodekahedronGraph()

Generates a dodecahedron graph. A cubic, symmetric graph with \(20\) nodes (same as Desargue's graph). The two graphs have the same diameter, mean shortest path length, and clustering coefficient. Nevertheless the highly susceptible fixation times differ for the two graphs.

Requirements/notes:

Symmetric graph, \(k=3, N=20\).

See Also:

• Wikipedia: Regular dodecahedron
• initGeometryDesarguesGraph()

initGeometryDesarguesGraph

public void initGeometryDesarguesGraph()

Generates a Desargues graph, named after Girard Desargues (1591–1661). A cubic, symmetric graph with \(20\) nodes (same as icosahedron graph). The two graphs have the same diameter, mean shortest path length, and clustering coefficient. Nevertheless the highly susceptible fixation times differ for the two graphs.

Requirements/notes:

Symmetric graph, \(k=3, N=20\).

See Also:

• Wikipedia: Desargues graph
• Kagno, I. N. (1947), "Desargues' and Pappus' graphs and their groups", American Journal of Mathematics, 69 (4): 859–863
• initGeometryDodekahedronGraph()

initGeometryRandomGraph

public void initGeometryRandomGraph()

Generate a (connected, directed) random graph.

Requirements/notes:

1. Rounds link count to even number.
2. Ensure minimal assumptions, i.e. fully general graph.

initGeometryRandomGraphDirected

public void initGeometryRandomGraphDirected()

Generate a (connected, directed) random graph.

Requirements/notes:

1. check if truly connected
2. first node may not necessarily get an incoming link
3. ensure minimal assumptions, i.e. fully general graph

initGeometryRandomRegularGraph

public void initGeometryRandomRegularGraph()

Generate a (connected, undirected) random regular graph.

Requirements/notes:

1. Graph generation may fail
2. After MAX_TRIALS failures, resort to well-mixed population
3. Minimize risk of failure?

initGeometryScaleFree

public void initGeometryScaleFree()

Generate a (connected, undirected) scale-free network. Generates power-law degree distribution first and then a random network that satisfies those connectivities.

Requirements/notes:

Makes efforts to match the desired overall connectivity.

swap

private static void swap(int[] x,
 int a,
 int b)

Swap elements with indices a and b in array x

Parameters:

x - [] the data array

a - the index of the first element

b - the index of the second element

initGeometryDegreeDistr

private boolean initGeometryDegreeDistr(int[] distr)

Utility method to generate network with a given degree distribution.

Requirements/notes:

The degree distribution is sorted with descending degrees.

Parameters:

distr - the array to store the degree distribution

Returns:

true if generation succeeded

initGeometryScaleFreeBA

public void initGeometryScaleFreeBA()

Generate a (connected, undirected) scale-free network following the procedure by Barabási & Albert (1999).

Requirements/notes:

None.

See Also:

• Barabási, Albert-László & Albert, Réka (1999) "Emergence of scaling in random networks", Science. 286 (5439): 509–512

initGeometryScaleFreeKlemm

public void initGeometryScaleFreeKlemm()

Generate a (connected, undirected) scale-free network following the procedure by Klemm & Eguíluz (2001).

Requirements/notes:

1. Effective connectivity is \(k (N-1)/N\) where \(k\) is the desired average connectivity and \(N\) is the population size.
2. Add bookkeeping to optimize generation time.

See Also:

• Klemm, Konstantin & Eguíluz, Víctor M. (2001) Growing scale-free networks with small-world behavior, Phys. Rev. E 65, 057102.

rewire

public void rewire()

Add/rewire directed and undirected random links.

Requirements/notes:

None.

See Also:

• rewireUndirected(double)
• rewireDirected()

rewireUndirected

public boolean rewireUndirected(double prob)

Rewire undirected links.

Requirements/notes:

1. Requires an undirected graph.
2. Rewiring preserves connectivity of all nodes.
3. Resulting graph obviously remains undirected.
4. The number of rewired links is \(N_\text{rewired}=\min {N_\text{links}, N_\text{links} \log(1-p_\text{undir})}\), i.e. at most the number undirected links in the graph. Thus, at most an expected fraction of \(1-1/e\) (or \(~63%\)) of original links get rewired.

Parameters:

prob - the probability of rewiring an undirected link

Returns:

true if geometry rewired

addUndirected

public boolean addUndirected()

Add undirected links.

Requirements/notes:

The number of links added is \(N_\text{add}=N_\text{links} p_\text{undir}\).

Returns:

true if adding of undirected links successfult

rewireDirected

public boolean rewireDirected()

Rewire directed links.

Requirements/notes:

1. Only undirected graphs are guaranteed to remain connected.
2. Resulting graph is obviously directed (even if original was undirected).
3. Rewiring preserves connectivity of all nodes (both inlinks and outlinks).
4. The number of rewired links is \(N_\text{rewired}=\min {N_\text{links}, N_\text{links} \log(1-p_\text{dir})}\), i.e. at most the number directed links in the graph. Thus, at most an expected fraction of \(1-1/e\) (or \(~63%\)) of original links get rewired.
5. ToDo: Rewrite similar to rewireUndirected().

Returns:

true if rewiring succeeded

addDirected

public boolean addDirected()

Add directed links to network.

Requirements/notes:

The number of links added is \(N_\text{add}=N_\text{links} p_\text{dir}\).

Returns:

true if adding links succeeded

evaluate

public void evaluate()

Evaluate geometry. Convenience method to set frequently used quantities such as minIn, maxOut, avgTot etc.

Requirements/notes:

1. For Geometry.Type.MEANFIELD geometries all quantities are set to zero.
2. Dynamic graphs are always evaluated because all quantities are ephemeral.

isLattice

public boolean isLattice()

Utility method to determine whether a given geometry type is a lattice.

Returns:

true if geometry is lattice, false otherwise

isGraphConnected

public boolean isGraphConnected()

Check if graph is connected.

Requirements/notes:

Requires undirected graphs.

Returns:

true if graph is connected

isGraphConnected

public boolean isGraphConnected(int node,
 boolean[] check)

Check if any other node can be reached from node.

Requirements/notes:

1. Requires undirected graphs.
2. check is a boolean array indicating which nodes can or cannot be reached from node.

Parameters:

node - the node to check the connections from

check - the array of nodes that can be reached

Returns:

true if graph is connected

swapEdges

private boolean swapEdges(int a,
 int an,
 int b,
 int bn)

Utility method to swap edges (undirected links) between nodes: change link a-an to a-bn and b-bn to b-an.

Requirements/notes:

Does the same as rewireEdgeAt(a, bn, an); rewireEdgeAt(b, an, bn); but without allocating and freeing memory.

Parameters:

a - the first node

an - the neighbour of the first node

b - the second node

bn - the neighbour of the second node

Returns:

true if swap succeeded

checkConnections

public boolean checkConnections()

Check consistency of links.

Requirements/notes:

1. Self connections are unacceptable.
2. Double links between nodes are unacceptable.
3. For undirected networks every outgoing link must correspond to an incoming link.
4. ToDo: "self-connections" are acceptable for inter-species interactions.

Returns:

true if check succeeded

addEdgeAt

public void addEdgeAt(int from,
 int to)

Add edge (undirected link) from node from to node to.

Requirements/notes:

None.

Parameters:

from - the first node

to - the second node

addLinkAt

public void addLinkAt(int from,
 int to)

Add link (directed link) from node from to node to.

Requirements/notes:

1. Allocate new memory if required.
2. Geometry needs to be re-evaluated when finished.

Parameters:

from - the index of the first node

to - the index of the second node

See Also:

• evaluate()

removeEdgeAt

public void removeEdgeAt(int from,
 int to)

Remove edge (undirected link) from node from to node to.

Requirements/notes:

1. Does not update maxIn, maxOut or maxTot.
2. Geometry needs to be re-evaluated when finished.

Parameters:

from - the index of the first node

to - the index of the second node

See Also:

• evaluate()

removeLinkAt

public void removeLinkAt(int from,
 int to)

Remove link (directed link) from node from to node to.

Requirements/notes:

1. Does not update maxIn, maxOut or maxTot.
2. Geometry needs to be re-evaluated when finished.

Parameters:

from - the index of the first node

to - the index of the second node

See Also:

• evaluate()

clearLinksFrom

public void clearLinksFrom(int idx)

Remove all outgoing links from node idx.

Requirements/notes:

Doesn't free memory.

Parameters:

idx - the index of the node to remove all outgoing links

removeInLink

private void removeInLink(int from,
 int to)

Remove incoming link (directed link) to node to from node from.

Requirements/notes:

Geometry needs to be re-evaluated when done with all manipulations.

Parameters:

from - the index of the first node

to - the index of the second node

See Also:

• evaluate()

clearLinksTo

public void clearLinksTo(int idx)

Remove all incoming links to node idx.

Requirements/notes:

Doesn't free memory.

Parameters:

idx - the index of the node to remove all incoming links

removeOutLink

private void removeOutLink(int from,
 int to)

Remove outgoing link (directed link) from node from to node to.

Requirements/notes:

Geometry needs to be re-evaluated when done with all manipulations.

Parameters:

from - the index of the first node

to - the index of the second node

See Also:

• evaluate()

rewireLinkAt

public void rewireLinkAt(int from,
 int to,
 int prev)

Rewire directed link from node from to node prev to node to.

Requirements/notes:

Geometry needs to be re-evaluated when done with all manipulations.

Parameters:

from - the index of the first node

to - the index of the second node

prev - the index of the second node

See Also:

• evaluate()

rewireEdgeAt

public void rewireEdgeAt(int from,
 int to,
 int prev)

Rewire edge (undirected link) from node from to node prev to node to.

Requirements/notes:

Geometry needs to be re-evaluated when done with all manipulations.

Parameters:

from - the index of the first node

to - the index of the second node

prev - the index of the second node

See Also:

• evaluate()

isNeighborOf

public boolean isNeighborOf(int focal,
 int check)

Check if check is a neighbor of focal (not necessarily the other way round). For undirected networks focal and check can be exchanged.

Parameters:

focal - index of focal individual

check - index of individual to be checked

Returns:

true if check is neighbor of focal

deriveInteractionGeometry

public Geometry deriveInteractionGeometry(IBSPopulation opp)

Derive interaction geometry from current (competition) geometry. This is only possible if interCompSame is true. Returns null otherwise.

If opp==population then it is an intra-species interaction, which allows to simply return this, i.e. no cloning etc. required. Otherwise the geometry is cloned, the opponent set and 'self-loops' added for interactions with individuals in the same location.

Parameters:

opp - the population of interaction partners

Returns:

the derived interaction geometry or null if it cannot be derived

deriveCompetitionGeometry

public Geometry deriveCompetitionGeometry()

Derive competition geometry from current (interaction) geometry. This is only possible if interCompSame is true. Returns null otherwise.

If opp==population then it is an intra-species interaction, which allows to simply return this, i.e. no cloning etc. required. Otherwise the geometry is cloned, the opponent, the opponent set and 'self-loops' removed.

Returns:

the derived interaction geometry or null if it cannot be derived

parse

public boolean parse(String cli)

Parse string of geometry specifications cli. Check for consistency of settings (e.g. in terms of population size, connectivity). If adjustments are required and possible inform the user through the logger.

Parameters:

cli - the string with geometry specifications

Returns:

true if reset is required

usage

public String usage()

Get the usage description for the command line option --geometry.

Returns:

the usage description

clone

public Geometry clone()

Clone geometry.

Requirements/notes:

1. Overrides clone() in Object but conflicts with GWT's aversion to clone()ing...
2. Remove @SuppressWarnings("all") to ensure that no other issues crept in when modifying method.

Overrides:

clone in class Object

Returns:

clone of geometry

equals

public boolean equals(Geometry geo)

Check if this Geometry and geo refer to the same structures. Different realizations of random structures, such as random regular graphs, are considered equal as long as their characteristic parameters are the same.

Parameters:

geo - the geometry to compare to.

Returns:

true if the structures are the same

encodeGeometry

public String encodeGeometry()

Encode geometry as a plist string fragment.

Returns:

the geometry encoded as a plist

See Also:

• decodeGeometry(Plist)
• Plist

decodeGeometry

public void decodeGeometry(Plist plist)

Decode the geometry from the plist. The structure is encoded in map which provides array of neighbor indices for each individual index.

Requirements/notes:

The population (including its geometry/geometries) must already have been initialized. This only restores a particular (unique) geometry.

Parameters:

plist - the plist encoding the geometry

See Also:

• encodeGeometry()

isUniqueGeometry

public boolean isUniqueGeometry()

Check if current geometry unique. Only unique geomteries need to be encoded.

Requirements/notes:

1. Lattices etc. are not unique because they can be identically recreated.
2. All geometries involving random elements are unique.

Returns:

true if geometry is unique

isUniqueGeometry

private boolean isUniqueGeometry(Geometry.Type geo)

Helper method to check uniqueness of the geometry geo.

Requirements/notes:

Hierarchical geometries require recursive checks of uniqueness.

Parameters:

geo - the geometry to be checked for uniqueness

Returns:

true if geometry is unique