Layouts

Coordinates for drawing a graph in 2D and 3D: simple shapes, force-directed layouts, trees and layered drawings, distance-based layouts, and merging and aligning layouts.

31 entries: 29 functions and 2 types. Part of the Open Graph reference; All functions lists every entry on one page, with a filter. The badges say how each entry is checked.

Types

`layout_drl_options_t`type#

Unit tests

Parameters of the DrL layout: the edge-cut level and six annealing stages.

typedef struct og_layout_drl_options_t {
    og_real_t edge_cut;
    og_int_t init_iterations;
    og_real_t init_temperature;
    og_real_t init_attraction;
    og_real_t init_damping_mult;
    og_int_t liquid_iterations;
    og_real_t liquid_temperature;
    og_real_t liquid_attraction;
    og_real_t liquid_damping_mult;
    og_int_t expansion_iterations;
    og_real_t expansion_temperature;
    og_real_t expansion_attraction;
    og_real_t expansion_damping_mult;
    og_int_t cooldown_iterations;
    og_real_t cooldown_temperature;
    og_real_t cooldown_attraction;
    og_real_t cooldown_damping_mult;
    og_int_t crunch_iterations;
    og_real_t crunch_temperature;
    og_real_t crunch_attraction;
    og_real_t crunch_damping_mult;
    og_int_t simmer_iterations;
    og_real_t simmer_temperature;
    og_real_t simmer_attraction;
    og_real_t simmer_damping_mult;
} og_layout_drl_options_t;

DrL runs six stages in this order: init, liquid, expansion, cooldown, crunch and simmer. Each stage has a number of passes over all vertices, a temperature (how far a random jump may go), an attraction (the weight of the edge-length energy) and a damping multiplier (how far the analytic move goes toward the neighbours). edge_cut sets how many long edges are cut from the cooldown stage on.

Fill the struct with layout_drl_options_init and change single fields as needed. layout_drl requires every real field to be finite and every iteration count to be 0 or more.

Parameters

edge_cut How much edge cutting to do, from 0 (none) to 1 (the most; larger values act as 1). Cutting starts with the cooldown stage. 0.8 in every template.
init_iterations Passes over all vertices in the init stage, 0 or more.
init_temperature Size of the random jumps in the init stage.
init_attraction Weight of the edge-length energy against the density energy in the init stage.
init_damping_mult Fraction of the way to the weighted centre of the neighbours that the analytic move takes in the init stage (0 to 1).
liquid_iterations Passes over all vertices in the liquid stage, 0 or more.
liquid_temperature Size of the random jumps in the liquid stage.
liquid_attraction Weight of the edge-length energy against the density energy in the liquid stage.
liquid_damping_mult Fraction of the way to the weighted centre of the neighbours that the analytic move takes in the liquid stage (0 to 1).
expansion_iterations Passes over all vertices in the expansion stage, 0 or more.
expansion_temperature Size of the random jumps in the expansion stage.
expansion_attraction Weight of the edge-length energy against the density energy in the expansion stage.
expansion_damping_mult Fraction of the way to the weighted centre of the neighbours that the analytic move takes in the expansion stage (0 to 1).
cooldown_iterations Passes over all vertices in the cooldown stage, 0 or more.
cooldown_temperature Size of the random jumps in the cooldown stage.
cooldown_attraction Weight of the edge-length energy against the density energy in the cooldown stage.
cooldown_damping_mult Fraction of the way to the weighted centre of the neighbours that the analytic move takes in the cooldown stage (0 to 1).
crunch_iterations Passes over all vertices in the crunch stage, 0 or more.
crunch_temperature Size of the random jumps in the crunch stage.
crunch_attraction Weight of the edge-length energy against the density energy in the crunch stage.
crunch_damping_mult Fraction of the way to the weighted centre of the neighbours that the analytic move takes in the crunch stage (0 to 1).
simmer_iterations Passes over all vertices in the simmer stage, 0 or more.
simmer_temperature Size of the random jumps in the simmer stage.
simmer_attraction Weight of the edge-length energy against the density energy in the simmer stage.
simmer_damping_mult Fraction of the way to the weighted centre of the neighbours that the analytic move takes in the simmer stage (0 to 1).

Checked

Same fields and meaning as igraph 1.0's structure.

C name

og_layout_drl_options_t

In notebooks

Og.LayoutDrlOptions

igraph 1.0

igraph_layout_drl_options_t

`layout_drl_default_t`type#

Unit tests

Names of the ready-made DrL parameter sets.

typedef enum og_layout_drl_default_t {
    OG_LAYOUT_DRL_DEFAULT = 0,
    OG_LAYOUT_DRL_COARSEN,
    OG_LAYOUT_DRL_COARSEST,
    OG_LAYOUT_DRL_REFINE,
    OG_LAYOUT_DRL_FINAL
} og_layout_drl_default_t;

Pass one to layout_drl_options_init. DEFAULT is the general set. COARSEN and COARSEST pull groups of vertices together harder (a stronger attraction in the expansion and a longer crunch), COARSEST more so. REFINE and FINAL are meant for improving a layout given as a seed: they skip the liquid stage and use short, cool stages; FINAL is the shortest and coolest.

The numbers behind each name are Open Graph's own (see layout_drl_options_init).

Parameters

OG_LAYOUT_DRL_DEFAULT 0: the general set.
OG_LAYOUT_DRL_COARSEN 1: tighter groups.
OG_LAYOUT_DRL_COARSEST 2: the tightest groups.
OG_LAYOUT_DRL_REFINE 3: improve a seed layout.
OG_LAYOUT_DRL_FINAL 4: polish a refined layout.

Checked

Same names and values as igraph 1.0.

C name

og_layout_drl_default_t

In notebooks

Og.LayoutDrlDefault

igraph 1.0

igraph_layout_drl_default_t

Simple shapes

`layout_random`#

Same quality

Places every vertex at a uniformly random point of the square [-1, 1] x [-1, 1].

og_error_t og_layout_random(const og_t *graph, og_matrix_t *res);

Each coordinate is drawn on its own from the uniform distribution on [-1, 1] with Open Graph's default random number generator, so the result depends on the seed set with rng_seed. Edges are not looked at.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.

Returns

OG_SUCCESS, or an error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V|).

Checked

Same distribution as python-igraph 1.0 (uniform in [-1, 1]^2); our random stream, so the points differ. Checked by range, mean and variance.

C name

og_layout_random

In notebooks

Og.LayoutRandom

igraph 1.0

igraph_layout_random

`layout_circle`#

Exact

Puts the vertices of a selection on the unit circle at equal angles, in the selection's order.

og_error_t og_layout_circle(
    const og_t *graph,
    og_matrix_t *res,
    og_vs_t order
);

The k-th vertex of order (counting from 0) gets the angle 2 pi k / c, where c is the number of vertices in order: the first one sits at (1, 0) and the others follow counter-clockwise. Vertices that are not in order are left at the origin. Pass vss_all() to place every vertex in id order.

Edges and edge directions are not used.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
order Vertex selection: which vertices go on the circle, and in which order.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVVID order names a vertex that is not in the graph.
OG_ENOMEM Not enough memory.

Complexity

O(|V|).

Checked

Equal to python-igraph 1.0 on 200 seeded random graphs of 0 to 300 vertices, with and without a vertex order.

C name

og_layout_circle

In notebooks

Og.LayoutCircle

igraph 1.0

igraph_layout_circle

`layout_star`#

Exact

Puts one vertex at the origin and the others evenly on the unit circle around it.

og_error_t og_layout_star(
    const og_t *graph,
    og_matrix_t *res,
    og_int_t center,
    const og_vector_int_t *order
);

center goes to (0, 0). The other vertices are placed on the unit circle at angle steps of 2 pi / (|V| - 1), starting at angle 0 (the point (1, 0)) and going counter-clockwise, in the order given by order with center skipped; without order the vertex ids are taken in increasing order.

The edges are not used, so any graph can be drawn this way; it suits star-shaped graphs. A graph without vertices gives a 0 x 2 matrix.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
center The vertex placed at the origin. Not checked when the graph has no vertices.
order NULL, or a vector of |V| vertex ids giving the order around the circle (every vertex once; center may appear anywhere in it).

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL center is not a vertex id; order does not have |V| entries; order holds an id outside 0..|V|-1.
OG_ENOMEM Not enough memory.

Complexity

O(|V|).

Checked

Equal to python-igraph 1.0 on 200 seeded random graphs with given centre and order; invalid centre and order give the same error codes.

C name

og_layout_star

In notebooks

Og.LayoutStar

igraph 1.0

igraph_layout_star

See also

layout_circle

`layout_grid`#

Exact

Places the vertices on a square grid, row after row.

og_error_t og_layout_grid(
    const og_t *graph,
    og_matrix_t *res,
    og_int_t width
);

Vertex i gets x = i mod width and y = floor(i / width), with spacing 1. When width is 0 or negative it is set to ceil(sqrt(|V|)), which gives a grid that is as square as possible. Edges are not used.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
width Vertices per row; 0 or negative picks ceil(sqrt(|V|)).

Returns

OG_SUCCESS, or an error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V|).

Checked

Equal to python-igraph 1.0 on 200 seeded random graphs, automatic and given widths.

C name

og_layout_grid

In notebooks

Og.LayoutGrid

igraph 1.0

igraph_layout_grid

See also

layout_grid_3d

`layout_random_3d`#

Same quality

Places every vertex at a uniformly random point of the cube [-1, 1]^3.

og_error_t og_layout_random_3d(const og_t *graph, og_matrix_t *res);

Each coordinate is drawn on its own from the uniform distribution on [-1, 1] with the default random number generator, so the result depends on the seed. Edges are not looked at.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 3 columns, row i holding the coordinates of vertex i.

Returns

OG_SUCCESS, or an error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V|).

Checked

Same distribution as python-igraph 1.0 (uniform in [-1, 1]^3); checked by range and statistics.

C name

og_layout_random_3d

In notebooks

Og.LayoutRandom3d

igraph 1.0

igraph_layout_random_3d

See also

layout_random, layout_sphere

`layout_sphere`#

Exact

Places the vertices on the unit sphere along a spiral from the south pole to the north pole.

og_error_t og_layout_sphere(const og_t *graph, og_matrix_t *res);

Vertex i of n gets the height z = -1 + 2 i / (n - 1) and lies on the circle of latitude of radius r = sqrt(1 - z^2). The azimuth starts at 0 and grows by 3.6 / (sqrt(n) r) from one vertex to the next (the generalised spiral of Saff and Kuijlaars), which spreads the points almost evenly. Vertex 0 is at the south pole (0, 0, -1) and vertex n - 1 at the north pole; a single vertex goes to (0, 0, -1). Edges are not used.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 3 columns, row i holding the coordinates of vertex i.

Returns

OG_SUCCESS, or an error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V|).

Checked

Equal to python-igraph 1.0 on 200 seeded random graphs.

C name

og_layout_sphere

In notebooks

Og.LayoutSphere

igraph 1.0

igraph_layout_sphere

See also

layout_circle, layout_random_3d

`layout_grid_3d`#

Exact

Places the vertices on a 3D grid, filling layer after layer.

og_error_t og_layout_grid_3d(
    const og_t *graph,
    og_matrix_t *res,
    og_int_t width,
    og_int_t height
);

Vertex i gets x = i mod width, y = floor(i / width) mod height and z = floor(i / (width height)), with spacing 1. When width and height are both 0 or negative, both become the smallest w with w^3 >= |V|; when only one of them is, it becomes the smallest w with w^2 times the other >= |V|. Edges are not used.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 3 columns, row i holding the coordinates of vertex i.
width Vertices along x; 0 or negative: automatic.
height Vertices along y; 0 or negative: automatic.

Returns

OG_SUCCESS, or an error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V|).

Checked

Equal to python-igraph 1.0 on 200 seeded random graphs, automatic and given width and height.

C name

og_layout_grid_3d

In notebooks

Og.LayoutGrid3d

igraph 1.0

igraph_layout_grid_3d

See also

layout_grid

Force-directed layouts

`layout_graphopt`#

Within tolerance

Force-directed layout after Michael Schmuhl's graphopt: charged vertices repel each other and edges act as springs.

og_error_t og_layout_graphopt(
    const og_t *graph,
    og_matrix_t *res,
    og_int_t niter,
    og_real_t node_charge,
    og_real_t node_mass,
    og_real_t spring_length,
    og_real_t spring_constant,
    og_real_t max_sa_movement,
    og_bool_t use_seed
);

Each iteration computes all forces from the current positions and then moves every vertex at once. Two vertices repel by Coulomb's law, k q^2 / d^2 with k = 8.9875e9 and q = node_charge, but only when they are closer than 500 units. Each edge is a spring of rest length spring_length and constant spring_constant, half of its force acting on each end. A vertex moves by force / node_mass along each axis, capped at max_sa_movement per axis and iteration. There is no cooling: the cap stays the same in every iteration.

Edge directions are ignored; a self-loop has no length and no effect; parallel edges add their springs. With node_charge = 0 the repulsion is skipped. At the end the layout is centred and turned onto its principal axes with layout_align. A random start uses the random number generator.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 2). On return: the layout, row i holding vertex i.
niter Number of iterations, 0 or more.
node_charge Charge of every vertex; 0 turns the repulsion off.
node_mass Mass of every vertex; the move is the force divided by it.
spring_length Rest length of the edge springs.
spring_constant Spring constant of the edges.
max_sa_movement Largest move of a vertex along one axis in one iteration.
use_seed true: start from res. false: start from uniform random positions in [-1, 1]^2. A seed of the wrong size is replaced by a random start, with a warning.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL niter is negative.
OG_ENOMEM Not enough memory.

Complexity

O(niter (|V|^2 + |E|)); O(niter (|V| + |E|)) when node_charge is 0.

Checked

142 cases of 1 to 30 iterations from given seeds agree with python-igraph 1.0 as shapes (pairwise distances), within a tolerance taken from the oracle's own change when its seed is scaled by 1 +- 1e-15.

C name

og_layout_graphopt

In notebooks

Og.LayoutGraphopt

igraph 1.0

igraph_layout_graphopt

`layout_drl_options_init`#

Unit tests

Fills a DrL parameter struct from one of the ready-made sets.

og_error_t og_layout_drl_options_init(
    og_layout_drl_options_t *options,
    og_layout_drl_default_t templ
);

Sets edge_cut to 0.8 (32/40) and the six stages from the chosen template. DEFAULT spends 1000 passes in the split of the published OpenOrd schedule: liquid 250, expansion 250, cooldown 250, crunch 100, simmer 150, and no init passes. The temperatures, attractions and damping values, and the other four templates, were chosen by Norway Analytics and tuned on layout stress against python-igraph's DrL. python-igraph does not show its own values, so these are not igraph's numbers.

Parameters

options The struct to fill.
templ Which ready-made set to use.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL templ is not one of the five layout_drl_default_t values.

Complexity

O(1).

Checked

edge_cut as documented; the stage values are Open Graph's own. Each template is held to python-igraph's template of the same name (stress; for refine and final also how far vertices travel). An unknown template is OG_EINVAL.

C name

og_layout_drl_options_init

In notebooks

Og.LayoutDrlOptionsInit

igraph 1.0

igraph_layout_drl_options_init

`layout_drl`#

Same quality SIMD

DrL force-directed layout for large graphs: a density grid and staged annealing.

og_error_t og_layout_drl(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    const og_layout_drl_options_t *options,
    const og_vector_t *weights
);

This is Open Graph's implementation of the VxOrd scheme behind DrL and OpenOrd (Martin, Brown, Klavans and Boyack). The energy of a vertex is its attraction times the weighted squared lengths of its edges, plus the value of a density grid to which every vertex adds a small tent-shaped kernel. In every pass each vertex moves to the better of two points: the damped move toward the weighted centre of its neighbours, and a random jump around that point whose size follows the stage temperature. The stages in options run in order. From the cooldown stage on, edges longer than a cut length are cut for the rest of the run when edge_cut is above 0 (a vertex keeps its last edge), which lets clusters separate.

Edge directions are ignored; a weight scales the pull of its edge. The output is in units of about one edge length and is neither centred nor rotated. The function draws random numbers, so the result depends on the seed.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 2). On return: the layout, row i holding vertex i.
use_seed true: start from res (centred on its mean and shrunk if it does not fit the grid; both undone in the output). false: random start near the centre.
options Stage parameters, for example from layout_drl_options_init; must not be NULL.
weights NULL, or one finite, strictly positive weight per edge.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL weights does not have |E| entries or holds a value that is not finite and > 0; a stage has a negative iteration count or a real parameter that is not finite; use_seed with res not of size |V| x 2.
OG_ENOMEM Not enough memory.

Complexity

O(P (21^2 |V| + |E|)) for P passes in all (1000 with the default template); each move removes and adds back a kernel of 21 x 21 grid cells. The grid takes about 8 MB up to some 4,400 vertices and grows with the graph to at most 4096 x 4096 cells (128 MiB, from about 75,000 vertices).

Checked

Random, our generator. Mean normalised stress over 14 connected graphs x 4 seeds 0.110 against python-igraph's 0.142, better also on large trees, block models and BA graphs, and 2-3x faster on 5000 vertices. Worse on ring-like graphs (ring of 30: 0.141 against 0.024): quality parity is NOT reached on cycles.

SIMD

Adding and removing the density kernels runs on the SIMD axpy kernel; the grid gets the same values on every CPU path.

C name

og_layout_drl

In notebooks

Og.LayoutDrl

igraph 1.0

igraph_layout_drl

og_layout_drl_options_t opt;
og_matrix_t pos;
og_layout_drl_options_init(&opt, OG_LAYOUT_DRL_DEFAULT);
opt.edge_cut = 0;                       /* no edge cutting */
og_matrix_init(&pos, 0, 0);
og_rng_seed(og_rng_default(), 7);
og_layout_drl(&g, &pos, false, &opt, NULL);
og_matrix_destroy(&pos);

`layout_drl_3d`#

Same quality SIMD

DrL force-directed layout in three dimensions.

og_error_t og_layout_drl_3d(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    const og_layout_drl_options_t *options,
    const og_vector_t *weights
);

This is Open Graph's implementation of the VxOrd scheme behind DrL and OpenOrd (Martin, Brown, Klavans and Boyack). The energy of a vertex is its attraction times the weighted squared lengths of its edges, plus the value of a density grid to which every vertex adds a small tent-shaped kernel (in a 3D grid). In every pass each vertex moves to the better of two points: the damped move toward the weighted centre of its neighbours, and a random jump around that point whose size follows the stage temperature. The stages in options run in order. From the cooldown stage on, edges longer than a cut length are cut for the rest of the run when edge_cut is above 0 (a vertex keeps its last edge), which lets clusters separate.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 3). On return: the layout, row i holding vertex i.
use_seed true: start from res (centred on its mean and shrunk if it does not fit the grid; both undone in the output). false: random start near the centre.
options Stage parameters, for example from layout_drl_options_init; must not be NULL.
weights NULL, or one finite, strictly positive weight per edge.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL weights does not have |E| entries or holds a value that is not finite and > 0; a stage has a negative iteration count or a real parameter that is not finite; use_seed with res not of size |V| x 3.
OG_ENOMEM Not enough memory.

Complexity

O(P (9^3 |V| + |E|)) for P passes in all; each move removes and adds back a kernel of 9 x 9 x 9 cells. The grid takes about 8 MB (100^3 cells) for small graphs and at most 256^3 cells (128 MiB, from about 45,000 vertices).

Checked

Random, our generator. Mean normalised stress over 14 graphs x 4 seeds 0.088 against python-igraph's 0.095.

SIMD

Adding and removing the density kernels runs on the SIMD axpy kernel; the grid gets the same values on every CPU path.

C name

og_layout_drl_3d

In notebooks

Og.LayoutDrl3d

igraph 1.0

igraph_layout_drl_3d

`layout_fruchterman_reingold`#

Within tolerance SIMD

Fruchterman-Reingold force-directed layout in 2D: edges attract, all vertex pairs repel, under a falling temperature.

og_error_t og_layout_fruchterman_reingold(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    og_int_t niter,
    og_real_t start_temp,
    og_layout_grid_t grid,
    const og_vector_t *weights,
    const og_vector_t *minx,
    const og_vector_t *maxx,
    const og_vector_t *miny,
    const og_vector_t *maxy
);

Each iteration computes a displacement for every vertex and then moves all vertices at once. Every pair of vertices repels with force 1/d; every edge pulls its ends together with force w d^2 (w its weight, 1 without weights). When the graph has more than one component and no grid is used, every pair also attracts weakly with force |V|^(-3/2) d, so components stay near each other. A tiny random jitter (at most 1e-9 per coordinate) is added to each displacement so that symmetric starts do not get stuck, and vertices on the same spot are pushed apart in a random direction. The length of a displacement is capped by the temperature, which starts at start_temp and falls linearly to 0 over niter iterations; vertices are then clamped to their bounds, if any.

With the grid, repulsion is computed only between vertices closer than 2 that sit in the same or a neighbouring cell of a grid of 2 x 2 cells, which makes an iteration close to linear on large graphs; there is no weak attraction in that mode. OG_LAYOUT_AUTOGRID uses the grid above 1000 vertices.

Edge directions are ignored and self-loops have no effect. Without bounds the result is centred and turned with layout_align. The function draws random numbers (the start and the jitter): set the seed with rng_seed for a repeatable layout.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 2). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: random start, uniform in a square of side sqrt(|V|) centred on the origin (inside the bounds where given).
niter Number of iterations, 0 or more.
start_temp Largest displacement in the first iteration; it falls linearly to 0.
grid OG_LAYOUT_GRID, OG_LAYOUT_NOGRID, or OG_LAYOUT_AUTOGRID (grid for more than 1000 vertices).
weights NULL, or one strictly positive weight per edge; a larger weight pulls the ends closer.
minx NULL, or a lower bound on the x coordinate of every vertex (length |V|); -infinity leaves that side open.
maxx NULL, or an upper bound on the x coordinate of every vertex (length |V|); +infinity leaves that side open.
miny NULL, or a lower bound on the y coordinate of every vertex (length |V|); -infinity leaves that side open.
maxy NULL, or an upper bound on the y coordinate of every vertex (length |V|); +infinity leaves that side open.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL niter is negative; grid is not one of the three values; use_seed with res not of size |V| x 2; weights does not have |E| entries or holds a value that is not > 0 (NaN included); a bound vector does not have |V| entries, or a vertex's lower bound is above its upper bound.
OG_ENOMEM Not enough memory.

Complexity

O(niter (|V|^2 + |E|)) without the grid; with the grid about O(niter (|V| + |E|)) when the vertices are spread evenly.

Checked

From given seeds, 200 cases without and 120 with the grid (0 to 300 vertices, weights, bounds) agree with python-igraph 1.0 within each case's tolerance (both sides add a 1e-9 jitter); a verifier repeated it on 238 more cases. Release timing: 0.57-0.65x python-igraph's time for 2000 vertices / 10,000 edges (500 iterations), 0.61-0.93x for 20,000 / 100,000 with the grid.

SIMD

In 2D without the grid, each vertex's row of the all-pairs repulsion runs on the SIMD kernel with a fixed summation order, so every CPU path (AVX-512, AVX2, NEON, scalar) gives the same bits.

C name

og_layout_fruchterman_reingold

In notebooks

Og.LayoutFruchtermanReingold

igraph 1.0

igraph_layout_fruchterman_reingold

og_t g;
og_matrix_t pos;
og_ring(&g, 12, false, false, true);     /* undirected cycle of 12 vertices */
og_matrix_init(&pos, 0, 0);
og_rng_seed(og_rng_default(), 42);       /* repeatable result */
og_layout_fruchterman_reingold(&g, &pos, false, 500, 1.0, OG_LAYOUT_AUTOGRID,
                               NULL, NULL, NULL, NULL, NULL);
/* OG_MATRIX(pos, i, 0), OG_MATRIX(pos, i, 1): x and y of vertex i */
og_matrix_destroy(&pos);
og_destroy(&g);

`layout_kamada_kawai`#

Within tolerance Threads SIMD

Kamada-Kawai spring layout: the drawn distance between two vertices follows their graph distance.

og_error_t og_layout_kamada_kawai(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    og_int_t maxiter,
    og_real_t epsilon,
    og_real_t kkconst,
    const og_vector_t *weights,
    const og_vector_t *minx,
    const og_vector_t *maxx,
    const og_vector_t *miny,
    const og_vector_t *maxy
);

Every pair of vertices is joined by a spring whose rest length is L times their shortest-path distance, with L = sqrt(|V|) divided by the largest finite distance, and whose stiffness is kkconst divided by the squared distance. Pairs in different components use the largest finite distance. Each iteration picks the vertex with the largest energy gradient and moves it by one Newton-Raphson step; the run ends after maxiter iterations or when the squared length of the largest gradient is below epsilon.

Distances are taken on the undirected graph: hop counts without weights, weighted shortest paths with weights (a weight is an edge length). Without a seed and without bounds the start is a circle of radius 0.36 sqrt(|V|), and no random numbers are drawn; with bounds and no seed the start is random inside the bounds. Without bounds the result is centred and turned with layout_align.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 2). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: start from the circle described above.
maxiter Largest number of single-vertex moves, 0 or more.
epsilon Stop when the squared gradient of every vertex is below this; 0 runs all maxiter iterations.
kkconst Spring constant, > 0.
weights NULL, or one strictly positive length per edge.
minx NULL, or a lower bound on the x coordinate of every vertex (length |V|); -infinity leaves that side open.
maxx NULL, or an upper bound on the x coordinate of every vertex (length |V|); +infinity leaves that side open.
miny NULL, or a lower bound on the y coordinate of every vertex (length |V|); -infinity leaves that side open.
maxy NULL, or an upper bound on the y coordinate of every vertex (length |V|); +infinity leaves that side open.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL maxiter is negative; kkconst is not > 0; use_seed with res not of size |V| x 2; weights does not have |E| entries or holds a value that is not > 0; a bound vector does not have |V| entries, or a vertex's lower bound is above its upper bound.
OG_ENOMEM Not enough memory.

Complexity

All-pairs shortest paths first (O(|V| (|V| + |E|)) without weights, O(|V| (|V| + |E|) log |V|) with them), O(|V|^2) to set up the gradients, then O(|V|) per iteration; O(|V|^2) memory.

Checked

200 seeded cases within a tolerance taken from the oracle's own change when its seed is scaled by 1 +- 1e-15. From the default circle start compared by stress, because rounding decides which of several equal vertices moves first.

Threads

The all-pairs distances at the start run on the paths area's parallel kernel (distances, distances_dijkstra) when set_num_threads allows more than one thread; the result is the same for every thread count. The iterations themselves are serial.

SIMD

In 2D the three loops of an iteration (the largest gradient, the Hessian sums, the gradient updates) run on SIMD kernels with a fixed order; the same bits on every CPU path.

C name

og_layout_kamada_kawai

In notebooks

Og.LayoutKamadaKawai

igraph 1.0

igraph_layout_kamada_kawai

og_matrix_t pos;
og_matrix_init(&pos, 0, 0);
/* 50 moves per vertex, run to the end, spring constant |V| */
og_layout_kamada_kawai(&g, &pos, false, 50 * og_vcount(&g), 0.0,
                       (og_real_t) og_vcount(&g), NULL, NULL, NULL, NULL, NULL);
og_matrix_destroy(&pos);

`layout_gem`#

Same quality

GEM layout (Frick, Ludwig and Mehldau): vertices move one at a time, each with its own temperature.

og_error_t og_layout_gem(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    og_int_t maxiter,
    og_real_t temp_max,
    og_real_t temp_min,
    og_real_t temp_init
);

In each round the vertices are visited in a fresh random order. A visited vertex gets an impulse made of a pull toward the barycentre of all vertices (scaled by its mass 1 + degree/2), a small random disturbance, a repulsion L^2/d from every other vertex and an attraction d^2/(L^2 mass) along its edges, with desired edge length L = 1. The impulse is scaled to the vertex's local temperature. A vertex that swings back and forth cools down, one that keeps going the same way heats up, and one that turns in circles is damped by a skew gauge; no temperature exceeds temp_max. The run stops after maxiter single-vertex updates or when the mean temperature falls below temp_min.

Edge directions are ignored and the result is not aligned. The function draws random numbers. python-igraph 1.0 has no GEM, so the constants (gravity 1/16, disturbance up to 1/4, the oscillation and rotation sensitivities) are Open Graph's own.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 2). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: random start in a square of side sqrt(|V|) centred on the origin.
maxiter Largest number of single-vertex updates, 0 or more.
temp_max Upper bound of any vertex temperature, > 0.
temp_min Stop when the mean temperature is below this, 0 or more.
temp_init Starting temperature of every vertex, in (0, temp_max].

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL maxiter is negative; temp_max is not > 0; temp_min is negative or NaN; temp_init is outside (0, temp_max]; use_seed with res not of size |V| x 2.
OG_ENOMEM Not enough memory.

Complexity

O(maxiter |V|): each update looks at every other vertex.

Checked

python-igraph 1.0 has no GEM; held to its Fruchterman-Reingold instead: mean normalised stress 0.083 against 0.085 over 14 graphs x 4 seeds. The argument errors are Open Graph's choice.

C name

og_layout_gem

In notebooks

Og.LayoutGem

igraph 1.0

igraph_layout_gem

`layout_davidson_harel`#

Same quality

Davidson-Harel layout: simulated annealing on an energy that rewards spread, short edges and few crossings.

og_error_t og_layout_davidson_harel(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    og_int_t maxiter,
    og_int_t fineiter,
    og_real_t cool_fact,
    og_real_t weight_node_dist,
    og_real_t weight_border,
    og_real_t weight_edge_lengths,
    og_real_t weight_edge_crossings,
    og_real_t weight_node_edge_dist
);

The energy of a layout is the sum of five weighted terms: 1/d^2 over all vertex pairs (weight_node_dist), 1/r^2 to each of the four borders of the drawing square (weight_border), the squared edge lengths (weight_edge_lengths), the number of edge crossings (weight_edge_crossings) and, in fine tuning only, 1/g^2 between every vertex and every edge not touching it (weight_node_edge_dist). The square has side 10 sqrt(|V|) and is centred on the origin.

In each of the maxiter annealing rounds every vertex tries 30 moves to a random point on a circle around it; a move that lowers the energy is kept, a worse one with the Metropolis probability. The temperature and the circle radius shrink by cool_fact after each round. Then fineiter fine-tuning rounds try 10 moves per vertex and keep only improvements. A term with weight 0 is skipped, which saves time (the crossing and node-edge terms cost the most). Edge directions are ignored and the function draws random numbers; without a seed, a single vertex goes to the origin.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 2). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: random start inside the drawing square.
maxiter Annealing rounds, 0 or more.
fineiter Fine-tuning rounds, 0 or more.
cool_fact Factor applied to the temperature and move radius after each round, strictly between 0 and 1.
weight_node_dist Weight of the vertex-vertex repulsion term.
weight_border Weight of the border term.
weight_edge_lengths Weight of the edge-length term.
weight_edge_crossings Weight of the edge-crossing term.
weight_node_edge_dist Weight of the vertex-edge distance term (fine tuning only).

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL maxiter or fineiter is negative; cool_fact is not strictly between 0 and 1; use_seed with res not of size |V| x 2.
OG_ENOMEM Not enough memory.

Complexity

Each annealing round costs O(|V|^2 + |E|^2) with the crossing term and O(|V|^2 + |E|) without it; each fine-tuning round adds O(|V| |E|) for the vertex-edge term.

Checked

Mean normalised stress 0.112 against python-igraph's 0.123, and 24.1 against 33.1 edge crossings, over 10 graphs of up to 60 vertices x 4 seeds; argument errors as observed.

C name

og_layout_davidson_harel

In notebooks

Og.LayoutDavidsonHarel

igraph 1.0

igraph_layout_davidson_harel

`layout_lgl`#

Same quality

Large Graph Layout: grows the drawing outward from a root, one breadth-first level at a time.

og_error_t og_layout_lgl(
    const og_t *graph,
    og_matrix_t *res,
    og_int_t maxit,
    og_real_t maxdelta,
    og_real_t area,
    og_real_t coolexp,
    og_real_t repulserad,
    og_real_t cellsize,
    og_int_t proot
);

The vertices are sorted into breadth-first levels from the root, ignoring edge directions. Levels are added one at a time: a new vertex starts one natural length k = sqrt(area / |V|) from its parent, pointing away from the centre of the vertices placed so far (within 60 degrees either side). After each level, maxit iterations in the style of Fruchterman-Reingold move the placed vertices: attraction d^2/k along edges, repulsion k^2/d between vertices in the same or neighbouring grid cells, and a weak global pull -k^2 d^2 / repulserad (our reading of that argument), which cancels the repulsion at distance repulserad^(1/3). The largest move in iteration i of a level is maxdelta ((maxit - i) / maxit)^coolexp. Vertices stay inside the square of the given area, centred on the origin.

A disconnected graph gives a warning: the components the search misses are added after it, each started from its lowest vertex id, as further levels. A single vertex sits at the origin. The function draws random numbers (the angles of new vertices, and the root when proot is negative).

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
maxit Iterations after each level, 0 or more.
maxdelta Largest move in the first iteration of a level, > 0.
area Area of the drawing square; 0 or negative uses |V|^2.
coolexp Cooling exponent, > 0.
repulserad Scale of the weak global pull; 0 or negative uses area x |V|.
cellsize Side of the grid cells used for the repulsion; 0 or negative uses area^(1/4).
proot The root vertex; negative picks one at random.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL maxit is negative; maxdelta or coolexp is not > 0.
OG_EINVVID proot is |V| or more.
OG_ENOMEM Not enough memory.

Complexity

About O(levels x maxit x (|V| + |E|)) when the vertices are spread evenly over the cells (at most 4096 x 4096 cells).

Checked

Mean normalised stress 0.096 against python-igraph's 0.106 over 14 graphs x 4 seeds; equal on trees and BA graphs, but worse on graphs of large diameter (60 x 60 lattice 0.37 against 0.24, ring of 60 0.30 against 0.21): quality parity is NOT reached there.

C name

og_layout_lgl

In notebooks

Og.LayoutLgl

igraph 1.0

igraph_layout_lgl

`layout_fruchterman_reingold_3d`#

Within tolerance

Fruchterman-Reingold force-directed layout in 3D.

og_error_t og_layout_fruchterman_reingold_3d(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    og_int_t niter,
    og_real_t start_temp,
    const og_vector_t *weights,
    const og_vector_t *minx,
    const og_vector_t *maxx,
    const og_vector_t *miny,
    const og_vector_t *maxy,
    const og_vector_t *minz,
    const og_vector_t *maxz
);

There is no grid variant in 3D. For parity a quirk of the reference is kept: in a disconnected graph, the z part of the pairwise force on the lower-numbered vertex of a pair is added to its y coordinate.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 3). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: random start, uniform in a cube of side sqrt(|V|) centred on the origin (inside the bounds where given).
niter Number of iterations, 0 or more.
start_temp Largest displacement in the first iteration; it falls linearly to 0.
weights NULL, or one strictly positive weight per edge.
minx NULL, or a lower bound on the x coordinate of every vertex (length |V|); -infinity leaves that side open.
maxx NULL, or an upper bound on the x coordinate of every vertex (length |V|); +infinity leaves that side open.
miny NULL, or a lower bound on the y coordinate of every vertex (length |V|); -infinity leaves that side open.
maxy NULL, or an upper bound on the y coordinate of every vertex (length |V|); +infinity leaves that side open.
minz NULL, or a lower bound on the z coordinate of every vertex (length |V|); -infinity leaves that side open.
maxz NULL, or an upper bound on the z coordinate of every vertex (length |V|); +infinity leaves that side open.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL niter is negative; use_seed with res not of size |V| x 3; weights does not have |E| entries or holds a value that is not > 0; a bound vector does not have |V| entries, or a vertex's lower bound is above its upper bound.
OG_ENOMEM Not enough memory.

Complexity

O(niter (|V|^2 + |E|)).

Checked

120 seeded cases within the per-case jitter tolerance, as in 2D. 3000 vertices / 15,000 edges, 200 iterations: 2.65 s against python-igraph's 2.78 s.

C name

og_layout_fruchterman_reingold_3d

In notebooks

Og.LayoutFruchtermanReingold3d

igraph 1.0

igraph_layout_fruchterman_reingold_3d

`layout_kamada_kawai_3d`#

Within tolerance Threads

Kamada-Kawai spring layout in 3D.

og_error_t og_layout_kamada_kawai_3d(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    og_int_t maxiter,
    og_real_t epsilon,
    og_real_t kkconst,
    const og_vector_t *weights,
    const og_vector_t *minx,
    const og_vector_t *maxx,
    const og_vector_t *miny,
    const og_vector_t *maxy,
    const og_vector_t *minz,
    const og_vector_t *maxz
);

Distances are taken on the undirected graph: hop counts without weights, weighted shortest paths with weights (a weight is an edge length). Without a seed and without bounds the start is a sphere (layout_sphere) of radius 0.36 sqrt(|V|), and no random numbers are drawn; with bounds and no seed the start is random inside the bounds. Without bounds the result is centred and turned with layout_align.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 3). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: start from the sphere described above.
maxiter Largest number of single-vertex moves, 0 or more.
epsilon Stop when the squared gradient of every vertex is below this; 0 runs all maxiter iterations.
kkconst Spring constant, > 0.
weights NULL, or one strictly positive length per edge.
minx NULL, or a lower bound on the x coordinate of every vertex (length |V|); -infinity leaves that side open.
maxx NULL, or an upper bound on the x coordinate of every vertex (length |V|); +infinity leaves that side open.
miny NULL, or a lower bound on the y coordinate of every vertex (length |V|); -infinity leaves that side open.
maxy NULL, or an upper bound on the y coordinate of every vertex (length |V|); +infinity leaves that side open.
minz NULL, or a lower bound on the z coordinate of every vertex (length |V|); -infinity leaves that side open.
maxz NULL, or an upper bound on the z coordinate of every vertex (length |V|); +infinity leaves that side open.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL maxiter is negative; kkconst is not > 0; use_seed with res not of size |V| x 3; weights does not have |E| entries or holds a value that is not > 0; a bound vector does not have |V| entries, or a vertex's lower bound is above its upper bound.
OG_ENOMEM Not enough memory.

Complexity

All-pairs shortest paths first (O(|V| (|V| + |E|)) without weights, O(|V| (|V| + |E|) log |V|) with them), O(|V|^2) to set up the gradients, then O(|V|) per iteration; O(|V|^2) memory.

Checked

120 seeded cases within the per-case rounding tolerance, as in 2D.

Threads

C name

og_layout_kamada_kawai_3d

In notebooks

Og.LayoutKamadaKawai3d

igraph 1.0

igraph_layout_kamada_kawai_3d

Trees, layers and bipartite graphs

`layout_bipartite`#

Same quality

Draws a two-mode graph as two horizontal rows and orders each row to reduce edge crossings.

og_error_t og_layout_bipartite(
    const og_t *graph,
    const og_vector_bool_t *types,
    og_matrix_t *res,
    og_real_t hgap,
    og_real_t vgap,
    og_int_t maxiter
);

Vertices whose type is true go to the row y = 0, the others to the row y = vgap. The order inside each row comes from Open Graph's Sugiyama machinery (layout_sugiyama with these two layers): barycenter sweeps cut the number of crossings, then Brandes-Koepf coordinate assignment gives x in units of hgap, the leftmost vertex at x = 0. Edges between vertices of the same row are allowed; they take no part in the crossing reduction.

The y coordinates follow from types; the x coordinates are Open Graph's own result, not python-igraph's.

Parameters

graph The graph to lay out.
types Boolean vector of length |V|: true puts the vertex in the row y = 0.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
hgap Smallest horizontal distance between vertices of one row, 0 or more (0 puts every x at 0).
vgap Distance between the two rows.
maxiter Largest number of crossing-reduction sweeps, 0 or more.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL types does not have |V| entries; hgap is negative; maxiter is negative.
OG_ENOMEM Not enough memory.

Complexity

As layout_sugiyama with two layers: about O(maxiter (|V| + |E|) log |V|).

Checked

y equal to python-igraph 1.0. x from our own crossing reduction: 3685 crossings in total on the bipartite test cases against python-igraph's 4095; the x values differ.

C name

og_layout_bipartite

In notebooks

Og.LayoutBipartite

igraph 1.0

igraph_layout_bipartite

See also

layout_sugiyama

`layout_reingold_tilford`#

Exact Threads

Tidy tree drawing (Reingold-Tilford): one row per level, subtrees packed side by side as tightly as their outlines allow.

og_error_t og_layout_reingold_tilford(
    const og_t *graph,
    og_matrix_t *res,
    og_neimode_t mode,
    const og_vector_int_t *roots,
    const og_vector_int_t *rootlevel
);

A breadth-first search from the root(s) gives every vertex a parent and a depth; children are taken in increasing vertex id. Each subtree is drawn on its own and then pushed against its left neighbour along their outlines until vertices on every level are at least 1 apart; a parent sits at the mean x of its children. The y coordinate is the depth: the root at 0, its children at 1, and so on. If the graph is not a tree, the search tree is drawn and the other edges are ignored.

With several roots, the roots hang one level below an invisible common root, so their depth is 1; rootlevel[i] adds that many extra levels above root i, which lets the trees of a forest start at different heights. Vertices the search cannot reach are attached to the root and the search is run again, so every vertex gets a position. Without roots, they are chosen with roots_for_tree_layout: the degree heuristic below 500 vertices, the eccentricity heuristic from 500 on; rootlevel is then ignored, with a warning.

mode says which edges a search follows in a directed graph: OG_OUT from parent to child along the edge direction, OG_IN against it, OG_ALL either way. Undirected graphs always use OG_ALL.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
mode OG_OUT, OG_IN or OG_ALL (see above); ignored for undirected graphs.
roots NULL or empty: choose the roots automatically. Otherwise the root vertices.
rootlevel NULL, or one value >= 0 per root: extra levels above that root. Used only with two or more given roots.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVVID a root is not a vertex.
OG_EINVAL rootlevel does not have one entry per root; a root level is negative or too large.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) for the placement after sorting the neighbour lists; automatic roots add the cost of roots_for_tree_layout (O(|V| (|V| + |E|)) for the eccentricity heuristic used from 500 vertices on).

Checked

343 cases within 1e-9 of python-igraph 1.0: random graphs of 0 to 300 vertices with loops and multi-edges, trees, forests, given and automatic roots, root levels, all three modes; same errors.

Threads

Only when the roots are chosen automatically for 500 or more vertices: the eccentricities come from eccentricity, which runs on the thread layer when more than one thread is allowed (same result for any thread count).

C name

og_layout_reingold_tilford

In notebooks

Og.LayoutReingoldTilford

igraph 1.0

igraph_layout_reingold_tilford

og_t tree;
og_matrix_t pos;
og_vector_int_t roots;
og_kary_tree(&tree, 15, 2, OG_TREE_OUT);  /* binary tree, root 0 */
og_matrix_init(&pos, 0, 0);
og_vector_int_init_int(&roots, 1, 0);
og_layout_reingold_tilford(&tree, &pos, OG_OUT, &roots, NULL);
/* y of vertex i = its depth; x spaced at least 1 apart per level */
og_vector_int_destroy(&roots);
og_matrix_destroy(&pos);
og_destroy(&tree);

`layout_reingold_tilford_circular`#

Exact Threads

The Reingold-Tilford tree drawing bent into a circle: the root in the centre, each level on a ring.

og_error_t og_layout_reingold_tilford_circular(
    const og_t *graph,
    og_matrix_t *res,
    og_neimode_t mode,
    const og_vector_int_t *roots,
    const og_vector_int_t *rootlevel
);

The tree is first laid out exactly as by layout_reingold_tilford. Then x is mapped linearly onto an angle from 0 to 2 pi (|V| - 1) / |V| (the smallest x to 0) and the depth becomes the radius, giving (depth cos angle, depth sin angle). The root sits at the origin when there is one root; several roots lie on the ring of radius 1 (plus their root level).

mode says which edges a search follows in a directed graph: OG_OUT from parent to child along the edge direction, OG_IN against it, OG_ALL either way. Undirected graphs always use OG_ALL.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
mode OG_OUT, OG_IN or OG_ALL (see above); ignored for undirected graphs.
roots NULL or empty: choose the roots automatically. Otherwise the root vertices.
rootlevel NULL, or one value >= 0 per root: extra levels above that root. Used only with two or more given roots.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVVID a root is not a vertex.
OG_EINVAL rootlevel does not have one entry per root; a root level is negative or too large.
OG_ENOMEM Not enough memory.

Complexity

Checked

The same 343 cases within 1e-9 of python-igraph 1.0.

Threads

C name

og_layout_reingold_tilford_circular

In notebooks

Og.LayoutReingoldTilfordCircular

igraph 1.0

igraph_layout_reingold_tilford_circular

`roots_for_tree_layout`#

Exact Threads

Chooses one root per component for a tree layout.

og_error_t og_roots_for_tree_layout(
    const og_t *graph,
    og_neimode_t mode,
    og_vector_int_t *roots,
    og_root_choice_t heuristic
);

In an undirected graph, or with OG_ALL, every connected component gets one root. In a directed graph with OG_OUT the candidates are the strongly connected components that no edge enters from another component, each getting one root; with OG_IN, those that no edge leaves. Inside a candidate component the best-ranked vertex wins: with OG_ROOT_CHOICE_DEGREE the one with the most edges in the direction of mode (self-loops not counted), with OG_ROOT_CHOICE_ECCENTRICITY the one with the smallest eccentricity (the largest distance to a vertex it reaches, following mode). Ties are broken by the order of a Bentley-McIlroy sort, which gives python-igraph's choice.

roots is cleared and then filled, best-ranked first. layout_reingold_tilford calls this when no roots are given.

Parameters

graph The graph to lay out.
mode OG_OUT, OG_IN or OG_ALL; ignored for undirected graphs.
roots Initialised vector; receives the roots.
heuristic OG_ROOT_CHOICE_DEGREE (0) or OG_ROOT_CHOICE_ECCENTRICITY (1), an og_root_choice_t.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
OG_EINVAL heuristic is not one of the two values.
OG_ENOMEM Not enough memory.

Complexity

Degree heuristic: O(|V| log |V| + |E|). Eccentricity heuristic: O(|V| (|V| + |E|)).

Checked

190 cases with both heuristics: the roots equal python-igraph's as a set (python-igraph shows them only through the layout, not their order).

Threads

With OG_ROOT_CHOICE_ECCENTRICITY the eccentricities come from eccentricity, which runs on the thread layer when more than one thread is allowed (same result for any thread count).

C name

og_roots_for_tree_layout

In notebooks

Og.RootsForTreeLayout

igraph 1.0

igraph_roots_for_tree_layout

`layout_sugiyama`#

Same quality

Layered drawing of a hierarchy (Sugiyama): vertices on horizontal layers, long edges bent through extra points, few crossings.

og_error_t og_layout_sugiyama(
    const og_t *graph,
    og_matrix_t *res,
    og_matrix_list_t *routing,
    const og_vector_int_t *layers,
    og_real_t hgap,
    og_real_t vgap,
    og_int_t maxiter,
    const og_vector_t *weights
);

Layers. With layers given, vertex v goes to layer layers[v] (any integers) and y = layer x vgap. Otherwise a directed graph has the edges of an Eades-Lin-Smyth feedback arc set reversed (self-loops are never reversed) and is layered by longest path from its sources; an undirected graph is layered by breadth-first distance from the best-ranked vertex of each component (highest degree, or highest strength with weights). 2. Every edge that spans more than one layer gets a dummy vertex on each layer in between. 3. Barycenter sweeps down and up reorder each layer to cut crossings, which are counted exactly between neighbouring layers; the sweeps run once from the id order and once from a breadth-first order, and the better result is kept. 4. Brandes-Koepf assigns x in units of hgap, the smallest x at 0.

routing, when not NULL, receives one matrix per edge with one row (x, y) per dummy vertex, listed from the edge's source end; an edge between neighbouring layers gets an empty matrix. Edges inside one layer are drawn straight and take no part in the crossing reduction.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and 2 columns, row i holding the coordinates of vertex i.
routing NULL, or an initialised matrix list; receives |E| matrices of bend points.
layers NULL, or the layer of every vertex (length |V|).
hgap Horizontal spacing; 0 or negative puts every x at 0.
vgap Distance between layers.
maxiter Largest number of crossing-reduction sweeps, 0 or more.
weights NULL, or one weight per edge, used for the layering (the feedback arc set and the undirected ranking); NaN is refused.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL maxiter is negative; layers does not have |V| entries; weights does not have |E| entries or holds NaN; the layer indices span too wide a range or need too many dummy vertices.
OG_EINTERNAL breaking the cycles left a cycle (an internal fault; not expected).
OG_ENOMEM Not enough memory.

Complexity

Near-linear layering, then O(maxiter (N + E') log N) for the crossing reduction and O(N + E') for the coordinates, where N and E' count the vertices and edge segments including the dummy vertices.

Checked

With given layers (120 of 120) and for undirected graphs, y and the routing equal python-igraph 1.0. Directed graphs without layers get python-igraph's layering in 243 of 300 cases (it sometimes moves a vertex lower). x is our own: 2667 crossings against python-igraph's 5711 on 211 comparable cases.

C name

og_layout_sugiyama

In notebooks

Og.LayoutSugiyama

igraph 1.0

igraph_layout_sugiyama

Distance-based layouts

`layout_mds`#

Within tolerance SIMD

Classical multidimensional scaling: drawn distances approximate given or shortest-path distances.

og_error_t og_layout_mds(
    const og_t *graph,
    og_matrix_t *res,
    const og_matrix_t *dist,
    og_int_t dim
);

For each connected component, the squared distances are double-centred (B = -1/2 J D^2 J) and the coordinates are the eigenvectors of the dim largest eigenvalues of B, each scaled by the square root of the eigenvalue's absolute value (Torgerson's method). Without dist the distances are hop counts on the undirected graph; with dist the entries of that matrix are used (it should be symmetric), while the components are still those of the graph.

A single vertex goes to the origin and a component of two vertices to (-1/sqrt 2, 0) and (1/sqrt 2, 0). A disconnected graph can only be scaled into 2 dimensions: each component is scaled on its own, the pieces are joined with layout_merge_dla (which is random) and the result is centred on the mean. For a connected graph the result is deterministic up to the sign of each axis (an eigenvector has no fixed sign). Components of up to 200 vertices use a dense symmetric eigensolver, larger ones a block Krylov method that computes only the leading eigenpairs.

Parameters

graph The graph to lay out.
res Initialised matrix; resized to |V| rows and dim columns, row i holding the coordinates of vertex i.
dist NULL, or a |V| x |V| matrix of distances.
dim Number of dimensions, from 2 to |V|.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL dim is below 2; dist is not |V| x |V|; the graph has vertices but fewer than dim; the graph is disconnected and dim is not 2.
OG_ENOMEM Not enough memory.

Complexity

O(|V| (|V| + |E|)) for the hop distances; O(k^3) for a component of k <= 200 vertices and about O(k^2) per Krylov step above that; O(k^2) memory for the largest component.

Checked

242 cases vs python-igraph 1.0: connected graphs agree in the leading eigenvalues and, where the leading eigenspace is unique, in shape (pairwise distances); disconnected graphs go through the random merge and are checked by its properties.

SIMD

Components of up to 200 vertices are solved with linalg's lapack_dsyevr, whose inner loops run on the SIMD kernels with a fixed order.

C name

og_layout_mds

In notebooks

Og.LayoutMds

igraph 1.0

igraph_layout_mds

`layout_umap`#

Same quality

UMAP layout of a neighbour graph: graph neighbours stay close, random pairs are pushed apart.

og_error_t og_layout_umap(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    const og_vector_t *distances,
    og_real_t min_dist,
    og_int_t epochs,
    og_bool_t distances_are_weights
);

The graph is read as a nearest-neighbour graph whose edges carry distances. Unless distances_are_weights is true, each edge first gets a membership weight as in layout_umap_compute_weights. The layout then lowers UMAP's cross-entropy by stochastic gradient descent over the epochs: an edge of weight w is sampled about once every w_max / w epochs, pulls its two ends together, and pushes its first end away from about 5 vertices drawn at random per sample; the learning rate falls linearly from 1 to 0 and each gradient component is clipped at 4. The curve 1 / (1 + a d^(2b)) for the low-dimensional similarity is fitted to min_dist with Levenberg-Marquardt.

The start is res (use_seed) or uniform in [-10, 10] on each axis; the result is centred on the mean. Edges of weight 0 take no part. The graph must have no self-loops and no parallel edges (a directed graph may have both directions of a pair). The function draws random numbers.

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 2). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: random start.
distances NULL (all neighbours equally close), or one value per edge: a distance >= 0, or a weight when distances_are_weights.
min_dist Smallest distance between points in the layout, >= 0; small values give tight clusters.
epochs Number of epochs, 0 or more.
distances_are_weights true: distances already holds the weights (for example from layout_umap_compute_weights); false: compute them from the distances.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL min_dist is negative or NaN; epochs is negative; use_seed with res not of size |V| x 2; distances does not have |E| entries; a distance is negative or NaN; a weight is NaN; the graph has a self-loop or parallel edges.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) for the weights, then O(epochs x |E|) for the descent.

Checked

Random (stochastic gradient descent). Neighbourhood preservation and cluster separation compared with python-igraph 1.0 over several seeds (3 clusters, 8 neighbours: 0.615 against 0.643 +- 0.010; ring of 60: 0.926 against 0.911); a and b checked against scipy.

C name

og_layout_umap

In notebooks

Og.LayoutUmap

igraph 1.0

igraph_layout_umap

`layout_umap_compute_weights`#

Exact

Turns the edge distances of a neighbour graph into UMAP membership weights.

og_error_t og_layout_umap_compute_weights(
    const og_t *graph,
    const og_vector_t *distances,
    og_vector_t *weights
);

For every vertex, rho is the smallest distance among its edges and sigma is found by bisection so that the sum of exp(-(d - rho) / sigma) over its k edges equals log2(k), within 0.01. Each edge then gets exp(-(d - rho) / sigma) from that vertex (1 for its closest neighbours), and the values a and b from the two ends are combined as the fuzzy union a + b - a b.

In an undirected graph both ends contribute to an edge. In a directed graph only the source does (out-neighbours); when both directions of a pair exist, the union is stored on the edge with the lower id and the other edge gets 0. Vertices without edges are skipped.

Parameters

graph The graph to lay out.
distances NULL (all distances 0, so every neighbour weighs 1), or one distance >= 0 per edge.
weights Initialised vector; receives one weight in [0, 1] per edge.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL distances does not have |E| entries, or holds a negative value or NaN; the graph has a self-loop or parallel edges.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) times the bisection steps (at most 100 per vertex).

Checked

302 graphs equal to python-igraph 1.0 within 1e-10.

C name

og_layout_umap_compute_weights

In notebooks

Og.LayoutUmapComputeWeights

igraph 1.0

igraph_layout_umap_compute_weights

See also

layout_umap, layout_umap_3d

`layout_umap_3d`#

Same quality

UMAP layout of a neighbour graph in 3D.

og_error_t og_layout_umap_3d(
    const og_t *graph,
    og_matrix_t *res,
    og_bool_t use_seed,
    const og_vector_t *distances,
    og_real_t min_dist,
    og_int_t epochs,
    og_bool_t distances_are_weights
);

Parameters

graph The graph to lay out.
res With use_seed: the start positions (|V| x 3). On return: the layout, row i holding vertex i.
use_seed true: start from res. false: random start.
distances NULL (all neighbours equally close), or one value per edge: a distance >= 0, or a weight when distances_are_weights.
min_dist Smallest distance between points in the layout, >= 0; small values give tight clusters.
epochs Number of epochs, 0 or more.
distances_are_weights true: distances already holds the weights (for example from layout_umap_compute_weights); false: compute them from the distances.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL min_dist is negative or NaN; epochs is negative; use_seed with res not of size |V| x 3; distances does not have |E| entries; a distance is negative or NaN; a weight is NaN; the graph has a self-loop or parallel edges.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) for the weights, then O(epochs x |E|) for the descent.

Checked

3 clusters, 8 neighbours in 3D: neighbourhood preservation 0.673 against python-igraph's 0.687 +- 0.008, separation 0.118 against 0.125.

C name

og_layout_umap_3d

In notebooks

Og.LayoutUmap3d

igraph 1.0

igraph_layout_umap_3d

Merging and aligning

`layout_merge_dla`#

Same quality

Joins several 2D layouts into one, packing them around each other by diffusion-limited aggregation.

og_error_t og_layout_merge_dla(
    const og_vector_ptr_t *thegraphs,
    const og_matrix_list_t *coords,
    og_matrix_t *res
);

Each layout of k vertices is scaled about the centre of its bounding box so that half the box diagonal becomes k^(3/4); that disc stands for the layout, and a single vertex is a disc of radius 1. The discs are placed from the largest to the smallest by vertex count (equal counts keep their list order): the first at the origin, each other one released at a random point on a circle around the cluster and moved by random jumps (walk on spheres) until it touches a placed disc; a walker that strays four times as far as its start circle is released again.

res holds the vertices of coords[0] first, then those of coords[1], and so on. thegraphs is not read (NULL is accepted): the vertex count of each graph is the row count of its matrix in coords. The function draws random numbers. layout_mds uses it for disconnected graphs.

Parameters

thegraphs The graphs the layouts belong to; not read.
coords One layout per graph, each a matrix with 2 columns (an empty matrix is allowed).
res Initialised matrix; receives all the vertices, 2 columns.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL a non-empty layout does not have exactly 2 columns.
OG_ENOMEM Not enough memory.

Complexity

O(total vertices) for scaling and copying, plus the random walks: each jump checks every disc placed so far, and the number of jumps is random.

Checked

Random. The exact properties (each layout scaled to half-diagonal n^(3/4), no overlaps, centred) were observed through python-igraph's MDS of disconnected graphs; compactness is compared statistically.

C name

og_layout_merge_dla

In notebooks

Og.LayoutMergeDla

igraph 1.0

igraph_layout_merge_dla

See also

layout_mds

`layout_align`#

Exact

Centres a layout on the origin and turns it so that its main directions lie along the axes.

og_error_t og_layout_align(const og_t *graph, og_matrix_t *layout);

First every axis is shifted so that its mean is 0. Then the principal directions are found from the scatter of the edge vectors (the differences between the end points of the non-loop edges), or of the vertex positions when no edge has a length, and the layout is turned by plane rotations so that each principal direction lies along an axis; directions the data leaves open are not turned. Finally the axes are ordered by the extent of the drawing, widest first. In 2D a nearly round scatter (eigenvalues within 0.2% of each other) has no clear main direction; there the first vector (vertex 0, or the first edge of non-zero length) decides the turn, as in python-igraph.

Works in any number of dimensions; a one-column layout is only centred. The force-directed layouts call it at the end when no bounds are given.

Parameters

graph The graph to lay out.
layout The layout to change in place: |V| rows, any number of columns.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL layout does not have |V| rows; a coordinate is not finite.
OG_ENOMEM Not enough memory.

Complexity

O(|V| d + |E| d^2 + d^3) for d columns.

Checked

200 random layouts of 1 to 4 dimensions equal python-igraph 1.0 within 1e-9 up to the sign of each axis (as shapes in 4D), plus 405 more in a verifier. Not matched: 3D and 4D scatters with repeated eigenvalues, where python-igraph's choice depends on its eigensolver.

C name

og_layout_align

In notebooks

Og.LayoutAlign

igraph 1.0

igraph_layout_align

Last updated 6 November 2026 · Open Graph 0.1.0 · OpenBI Studio 0.3.78

Layouts

Types

layout_drl_options_ttype#

layout_drl_default_ttype#

Simple shapes

layout_random#

layout_circle#

layout_star#

layout_grid#

layout_random_3d#

layout_sphere#

layout_grid_3d#

Force-directed layouts

layout_graphopt#

layout_drl_options_init#

layout_drl#

layout_drl_3d#

layout_fruchterman_reingold#

layout_kamada_kawai#

layout_gem#

layout_davidson_harel#

layout_lgl#

layout_fruchterman_reingold_3d#

layout_kamada_kawai_3d#

Trees, layers and bipartite graphs

layout_bipartite#

layout_reingold_tilford#

layout_reingold_tilford_circular#

roots_for_tree_layout#

layout_sugiyama#

Distance-based layouts

layout_mds#

layout_umap#

layout_umap_compute_weights#

layout_umap_3d#

Merging and aligning

layout_merge_dla#

layout_align#

`layout_drl_options_t`type#

`layout_drl_default_t`type#

`layout_random`#

`layout_circle`#

`layout_star`#

`layout_grid`#

`layout_random_3d`#

`layout_sphere`#

`layout_grid_3d`#

`layout_graphopt`#

`layout_drl_options_init`#

`layout_drl`#

`layout_drl_3d`#

`layout_fruchterman_reingold`#

`layout_kamada_kawai`#

`layout_gem`#

`layout_davidson_harel`#

`layout_lgl`#

`layout_fruchterman_reingold_3d`#

`layout_kamada_kawai_3d`#

`layout_bipartite`#

`layout_reingold_tilford`#

`layout_reingold_tilford_circular`#

`roots_for_tree_layout`#

`layout_sugiyama`#

`layout_mds`#

`layout_umap`#

`layout_umap_compute_weights`#

`layout_umap_3d`#

`layout_merge_dla`#

`layout_align`#