Topology library. More...

#include <assert.h>
#include <stdlib.h>
#include <core/core.h>
#include <datatypes/list.h>
#include <ROOT-Sim.h>

Include dependency graph for topology.c:

Classes
struct	graph_node
	A node in the topology adjacency matrix. More...

struct	topology
	The structure describing a topology. More...

Functions
static lp_id_t	get_random_neighbor (lp_id_t from, struct topology *topology, size_t n_directions, enum topology_direction directions[n_directions])
	Return a random neighbor. More...

static lp_id_t	get_neighbor_hexagon (lp_id_t from, struct topology *topology, enum topology_direction direction)
	Given a linear id in a TOPOLOGY_HEXAGON map, get the linear id of a neighbor in a given direction (if any). More...

static lp_id_t	get_neighbor_square (lp_id_t from, struct topology *topology, enum topology_direction direction)
	Given a linear id in a TOPOLOGY_SQUARE map, get the linear id of a neighbor in a given direction (if any). More...

static lp_id_t	get_neighbor_torus (lp_id_t from, struct topology *topology, enum topology_direction direction)
	Given a linear id in a TOPOLOGY_TORUS map, get the linear id of a neighbor in a given direction (if any). More...

static lp_id_t	get_neighbor_mesh (lp_id_t from, struct topology *topology, enum topology_direction direction)
	Given an id in a TOPOLOGY_FCMESH map, get the id of a neighbor. More...

static lp_id_t	get_neighbor_bidring (lp_id_t from, struct topology *topology, enum topology_direction direction)

static lp_id_t	get_neighbor_ring (lp_id_t from, struct topology *topology, enum topology_direction direction)

static lp_id_t	get_neighbor_star (lp_id_t from, struct topology *topology, enum topology_direction direction)

static lp_id_t	get_neighbor_graph (lp_id_t from, struct topology *topology, enum topology_direction direction)

lp_id_t	CountRegions (struct topology *topology)

lp_id_t	CountDirections (lp_id_t from, struct topology *topology)

bool	IsNeighbor (lp_id_t from, lp_id_t to, struct topology *topology)

lp_id_t	GetReceiver (lp_id_t from, struct topology *topology, enum topology_direction direction)

struct topology *	vInitializeTopology (enum topology_geometry geometry, int argc,...)
	Initialize a topology region. More...

void	ReleaseTopology (struct topology *topology)

bool	AddTopologyLink (struct topology *topology, lp_id_t from, lp_id_t to, double probability)

Variables
static enum topology_direction	directions_hexagon []
	Allowed directions to reach a neighbor in a TOPOLOGY_HEXAGON. More...

static enum topology_direction	directions_square_torus [] = {DIRECTION_E, DIRECTION_W, DIRECTION_N, DIRECTION_S}
	Allowed directions to reach a neighbor in either a TOPOLOGY_SQUARE or a TOPOLOGY_TORUS.

Detailed Description

Topology library.

A library implementing commonly-required topologies in simulation models.

Copyright: Copyright (C) 2008-2022 HPDCS Group https://hpdcs.github.io

Function Documentation

◆ get_neighbor_hexagon()

static lp_id_t get_neighbor_hexagon	(	lp_id_t	from,
		struct topology *	topology,
		enum topology_direction	direction
	)

static

Given a linear id in a TOPOLOGY_HEXAGON map, get the linear id of a neighbor in a given direction (if any).

We use only one possible representation of a hexagonal map, namely a "pointy" "odd-r" horizontal layout, with an arbitrary width and height. In this representation, odd rows are showed right:

/ \ / \ / \ / \ |0,0|1,0|2,0|3,0| \ / \ / \ / \ / \ |0,1|1,1|2,1|3,1| / \ / \ / \ / \ / |0,2|1,2|2,2|3,2| \ / \ / \ / \ /

This is a map of size 3x4, in which 12 different cells are represented. In each hexagon, the (x,y) coordinates are represented. Nevertheless, to support simulation, we typically linearize the cells of the map. Indeed, the cells are linearly mapped as: 0 → (0,0); 1 → (1,0); 2 → (2,0); 3 → (3,0); 4 → (0,1); 5 → (1,1); 6 → (2,1); 7 → (3,1); etc.

The general mapping from linear (L) to hex (x,y) is therefore implemented as (in integer arithmetic): y = L / width x = L % width

while the mapping from (x,y) to L is implemented as:

L = y * width + x

When checking for a neighbor, we have to consider the row in which we are starting from. Indeed, considering that it's an "odd-r" map, if we are in an odd row and we move "up left" or "down left", we retain the same x value. Conversely, if we move from an odd row "up right" or "down right", we have to increment x. Moving from an even row is the other way round (retain x if you move up/down right, decrement if you move up/down left). In this implementation, we use bitwise and with 1 to check if we are in an odd row. Moving up/down always decrements/increments y. Moving right/left only increments/decrements x.

At the end, to check if a move is valid, we compare new coordinates (x,y) with the size of the grid.

Parameters

from	The linear representation of the source element
topology	The structure keeping the information about the topology
direction	The direction to move towards, to find a linear id

Returns: The linear id of the neighbor, INVALID_DIRECTION if such neighbor does not exist in the topology.

◆ get_neighbor_mesh()

static lp_id_t get_neighbor_mesh	(	lp_id_t	from,
		struct topology *	topology,
		enum topology_direction	direction
	)

static

Given an id in a TOPOLOGY_FCMESH map, get the id of a neighbor.

The algorithm is simple: return a random element in the topology, different from from. The only corner case is if we have only one element, in which case we return INVALID_DIRECTION.

Parameters

from	The linear representation of the source element
topology	The structure keeping the information about the topology
direction	Can be only set to DIRECTION_RANDOM

Returns: The linear id of the neighbor, INVALID_DIRECTION if such neighbor does not exist in the topology.

◆ get_neighbor_square()

static lp_id_t get_neighbor_square	(	lp_id_t	from,
		struct topology *	topology,
		enum topology_direction	direction
	)

static

Given a linear id in a TOPOLOGY_SQUARE map, get the linear id of a neighbor in a given direction (if any).

The general mapping from linear (L) to hex (x,y) is therefore implemented as (in integer arithmetic): y = L / width x = L % width

while the mapping from (x,y) to L is implemented as: L = y * width + x

Getting a neighbor simply entails incrementing/decrementing x or y, depending on the direction, and then checking if such an element exists in the current map.

Parameters

from	The linear representation of the source element
topology	The structure keeping the information about the topology
direction	The direction to move towards, to find a linear id

Returns: The linear id of the neighbor, INVALID_DIRECTION if such neighbor does not exist in the topology.

◆ get_neighbor_torus()

static lp_id_t get_neighbor_torus	(	lp_id_t	from,
		struct topology *	topology,
		enum topology_direction	direction
	)

static

Given a linear id in a TOPOLOGY_TORUS map, get the linear id of a neighbor in a given direction (if any).

The general mapping from linear (L) to hex (x,y) is therefore implemented as (in integer arithmetic): y = L / width x = L % width

while the mapping from (x,y) to L is implemented as: L = y * width + x

Getting a neighbor simply entails incrementing/decrementing x or y, depending on the direction, and computing the modulus on the map size.

Parameters

from	The linear representation of the source element
topology	The structure keeping the information about the topology
direction	The direction to move towards, to find a linear id

Returns: The linear id of the neighbor, which always exists.

◆ get_random_neighbor()

static lp_id_t get_random_neighbor	(	lp_id_t	from,
		struct topology *	topology,
		size_t	n_directions,
		enum topology_direction	directions[n_directions]
	)

static

Return a random neighbor.

This function computes a random receiver, only for TOPOLOGY_HEXAGON, TOPOLOGY_SQUARE, and TOPOLOGY_TORUS. The algorithm simply generates a random permutation over the list of valid directions passed by the caller, and then attempts to get a receiver in every direction. The first direction that is not INVALID_DIRECTION dictates the picked random neighbor.

Parameters

from	source element of the random receiver computation
topology	the topology currently being considered
n_directions	the number of valid directions for the given topology
directions	the number of directions (a variable array)

Returns: A random neighbor according to the specified topology

◆ vInitializeTopology()

struct topology* vInitializeTopology	(	enum topology_geometry	geometry,
		int	argc,
			...
	)

Initialize a topology region.

This is a variadic function, that initializes a topology depending on its actual shape. In case the topology is a grid, two unsigned parameters should be passed, to specify the width and height of the grid. For all other topologies (included generic graphs) only a single unsigned parameter is needed, which is the number of elements composing the topology.

Parameters

geometry	The geometry to be used in the topology, a value from enum topology_geometry
argc	This is the number of variadic arguments passed to the function, computed thanks to some preprocessor black magic. This allows to make some early sanity check and prevent users to mess with the stack or initialize wrong topologies.
...	If geometry is TOPOLOGY_HEXAGON, TOPOLOGY_SQUARE, or TOPOLOGY_TORUS, two unsigned should be passed, to specify the width and height of the topology's grid. For all the other topologies, a single unsigned, determining the number of elements that compose the topology should be passed.

Returns: A pointer to as newly-allocated opaque topology struct. Releasing the topology (and all the memory internally used to represent it) can be done by passing it to ReleaseTopology().