Spatial graphs and numbers

The result of power_law_fit: the fitted power law and how well it fits.

typedef struct og_plfit_result_t {
    og_bool_t continuous;   /* continuous (true) or discrete (false) model */
    og_real_t alpha;        /* fitted exponent */
    og_real_t xmin;         /* the power law is fitted to the samples >= xmin */
    og_real_t L;            /* log-likelihood of the fitted model */
    og_real_t D;            /* Kolmogorov-Smirnov statistic of the fit */
    const og_vector_t *data; /* the input samples (borrowed, not copied) */
} og_plfit_result_t;

The fields describe a power law p(x) proportional to x^-alpha for x >= xmin. data points to the caller's sample vector, which is not copied; plfit_result_calculate_p_value reads it, so the vector must stay alive while the result is used for a p-value. The struct has no p-value field.

Parameters

• continuous true for the continuous model, false for the discrete one.
• alpha The fitted exponent.
• xmin The lower cutoff: the law is fitted to the samples >= xmin.
• L Log-likelihood of the fitted model on those samples.
• D Kolmogorov-Smirnov distance between those samples and the fitted law.
• data The input samples (borrowed, not copied).

Checked

Fields as declared in the reference manual: continuous, alpha, xmin, L, D, data.

C name

og_plfit_result_t

In notebooks

Og.PlfitResult

igraph 1.0

igraph_plfit_result_t

See also

power_law_fit, plfit_result_calculate_p_value

Selects the distance used by the spatial functions: Euclidean or Manhattan.

typedef enum og_metric_t {
    OG_METRIC_EUCLIDEAN = 0,
    OG_METRIC_L2 = OG_METRIC_EUCLIDEAN,
    OG_METRIC_MANHATTAN = 1,
    OG_METRIC_L1 = OG_METRIC_MANHATTAN
} og_metric_t;

OG_METRIC_EUCLIDEAN (alias OG_METRIC_L2, value 0) is the straight-line distance sqrt(sum (x_i - y_i)^2); OG_METRIC_MANHATTAN (alias OG_METRIC_L1, value 1) is sum |x_i - y_i|. Functions given any other value fail with OG_EINVAL.

Parameters

• OG_METRIC_EUCLIDEAN Euclidean distance (0).
• OG_METRIC_L2 Same as OG_METRIC_EUCLIDEAN.
• OG_METRIC_MANHATTAN Manhattan distance (1).
• OG_METRIC_L1 Same as OG_METRIC_MANHATTAN.

Checked

Same names and values as the reference; other values are refused with OG_EINVAL.

C name

og_metric_t

In notebooks

Og.Metric

igraph 1.0

igraph_metric_t

See also

nearest_neighbor_graph, spatial_edge_lengths

Builds the Delaunay graph of a point set, in any dimension.

og_error_t og_delaunay_graph(og_t *graph, const og_matrix_t *points);

Two points are adjacent when they are corners of a common simplex of the Delaunay triangulation, whose simplices have no other point inside their circumscribed spheres. The triangulation is built by incremental insertion (Bowyer and Watson 1981) in the order of a space-filling curve, with exact geometric predicates (a floating-point filter backed by exact expansion arithmetic), so rounding never produces a wrong edge. Points that lie in a lower-dimensional affine subspace are triangulated within it, so collinear points give a path.

When several points lie on a common sphere (a circle in the plane), the triangulation is not unique; Open Graph then uses the one fixed by a symbolic perturbation (Edelsbrunner and Muecke 1990), which does not depend on the order of the rows. The graph is undirected, has one vertex per row and lists its edges sorted by (smaller id, larger id).

Parameters

• graph An uninitialised graph. On success it holds the result; destroy it with destroy.
• points One point per row; the number of columns is the dimension. Coordinates must be finite and no two rows equal.

Returns

OG_SUCCESS, or one of the error codes below. On error no graph is left initialised.

Errors

• OG_EINVAL A coordinate is NaN or infinite, the matrix has rows but no columns, two points are equal, or there are more than 23 dimensions.
• OG_ENOMEM Not enough memory.

Complexity

Expected about O(n log n) for evenly spread points in 2 and 3 dimensions; in d dimensions the triangulation itself can have O(n^ceil(d/2)) simplices.

Checked

python-igraph does not expose it. Equal to scipy's Delaunay (Qhull, the library igraph's manual names) on 240 point sets in general position, 2 to 6 dimensions, 0 to 300 points. For co-spherical input (grids) the result is a valid Delaunay triangulation (empty-sphere property and Euler's formula checked), but which diagonal igraph's Qhull call would choose is not tested.

C name

og_delaunay_graph

In notebooks

Og.DelaunayGraph

igraph 1.0

igraph_delaunay_graph

See also

gabriel_graph, relative_neighborhood_graph, nearest_neighbor_graph

Joins every point to its k nearest neighbours, optionally only those closer than a cutoff.

og_error_t og_nearest_neighbor_graph(
    og_t *graph,
    const og_matrix_t *points,
    og_metric_t metric,
    og_int_t k,
    og_real_t cutoff,
    og_bool_t directed
);

For each point the other points are ranked by distance in the chosen metric, ties going to the smaller vertex id; the first k of them (k negative: all) that are strictly closer than cutoff become its neighbours (cutoff negative, NaN or infinite: no limit). A k-d tree finds them. With directed true each point gets edges to its neighbours, listed vertex by vertex from the nearest; undirected, a pair found from either side becomes one edge, listed by (larger, smaller) end. k = 0 gives no edges; k negative without a cutoff joins every pair.

Parameters

• graph An uninitialised graph. On success it holds the result; destroy it with destroy.
• points One point per row; the number of columns is the dimension. Coordinates must be finite; repeated points are allowed.
• metric OG_METRIC_EUCLIDEAN or OG_METRIC_MANHATTAN.
• k Neighbours per point; negative for no limit.
• cutoff Only neighbours strictly closer than this; negative, NaN or infinite for no limit.
• directed Whether to make a directed graph (edges from each point to its neighbours).

Returns

OG_SUCCESS, or one of the error codes below. On error no graph is left initialised.

Errors

• OG_EINVAL metric is unknown, a coordinate is NaN or infinite, or the matrix has rows but no columns.
• OG_ENOMEM Not enough memory, or n x k edges are more than can be stored.

Complexity

O(n log n) to build the tree; a query costs about O(k log n) for well-spread points, so roughly O(n k log n) in all. 100,000 random planar points with k = 5 take about 0.1 s (python-igraph 1.0: 0.16 s).

Checked

Edges and their order identical to python-igraph 1.0 on 260 cases (0 to 300 points, 1 to 4 dimensions, both metrics, cutoffs, both directions) and 6 graphs of 5,000 to 20,000 points. On integer grids, where many distances are equal, python-igraph's choice among equally distant neighbours follows its internal search order, so there the distances are compared instead of the ids.

C name

og_nearest_neighbor_graph

In notebooks

Og.NearestNeighborGraph

igraph 1.0

igraph_nearest_neighbor_graph

See also

delaunay_graph, spatial_edge_lengths, metric_t

og_matrix_t pts;
og_t g;
og_matrix_init(&pts, 4, 2);            /* four planar points, one per row */
MATRIX(pts, 0, 0) = 0.0; MATRIX(pts, 0, 1) = 0.0;
MATRIX(pts, 1, 0) = 1.0; MATRIX(pts, 1, 1) = 0.0;
MATRIX(pts, 2, 0) = 0.0; MATRIX(pts, 2, 1) = 2.0;
MATRIX(pts, 3, 0) = 5.0; MATRIX(pts, 3, 1) = 5.0;
/* each point to its two nearest neighbours, no distance limit */
if (og_nearest_neighbor_graph(&g, &pts, OG_METRIC_EUCLIDEAN, 2, -1.0, OG_UNDIRECTED) == OG_SUCCESS) {
    og_destroy(&g);
}
og_matrix_destroy(&pts);

Builds the Gabriel graph: two points are joined when no other point lies in the ball that has them as a diameter.

og_error_t og_gabriel_graph(og_t *graph, const og_matrix_t *points);

A and B are adjacent unless some third point C lies in the closed ball with diameter AB, that is unless (C - A) . (C - B) <= 0 (Gabriel and Sokal 1969). Every Gabriel edge is a Delaunay edge, so the Delaunay edges are the candidates (every pair from 5 dimensions on, where the triangulation would outgrow the n^2 pairs), each tested by a k-d tree search. Any dimension. The graph is undirected, has one vertex per row and lists its edges sorted by (smaller id, larger id).

The Gabriel graph contains the relative neighbourhood graph and is contained in the Delaunay graph; it equals the lune-based beta-skeleton with beta = 1.

Parameters

• graph An uninitialised graph. On success it holds the result; destroy it with destroy.
• points One point per row; the number of columns is the dimension. Coordinates must be finite and no two rows equal.

Returns

OG_SUCCESS, or one of the error codes below. On error no graph is left initialised.

Errors

• OG_EINVAL A coordinate is NaN or infinite, the matrix has rows but no columns, or two points are equal.
• OG_ENOMEM Not enough memory.

Complexity

The Delaunay graph plus one bounded k-d tree search per candidate edge; from 5 dimensions on, O(n^2) candidate pairs. 100,000 random planar points take about 0.5 s.

Checked

No python-igraph counterpart. Compared with a brute-force evaluation of the definition on 222 point sets (random reals and integer grids with points on the boundaries, 1 to 8 dimensions) and with an independent brute force in exact rational arithmetic on 835 more point sets (integer and real, collinear, co-circular, 1 to 4 dimensions); igraph's edge order is not tested.

C name

og_gabriel_graph

In notebooks

Og.GabrielGraph

igraph 1.0

igraph_gabriel_graph

See also

relative_neighborhood_graph, lune_beta_skeleton, beta_weighted_gabriel_graph, delaunay_graph

Builds the relative neighbourhood graph: two points are joined unless a third point is closer to both of them than they are to each other.

og_error_t og_relative_neighborhood_graph(
    og_t *graph,
    const og_matrix_t *points
);

A and B are adjacent unless some point C has |AC| < |AB| and |BC| < |AB|. The inequalities are strict, so for example the three corners of an equilateral triangle stay connected (Toussaint 1980). Candidates are the Delaunay edges (every pair from 5 dimensions on), each tested by a k-d tree search. Any dimension. The graph is undirected, has one vertex per row and lists its edges sorted by (smaller id, larger id).

The graph is a subgraph of the Gabriel graph and contains a Euclidean minimum spanning tree, so it is connected.

Parameters

• graph An uninitialised graph. On success it holds the result; destroy it with destroy.
• points One point per row; the number of columns is the dimension. Coordinates must be finite and no two rows equal.

Returns

OG_SUCCESS, or one of the error codes below. On error no graph is left initialised.

Errors

• OG_EINVAL A coordinate is NaN or infinite, the matrix has rows but no columns, or two points are equal.
• OG_ENOMEM Not enough memory.

Complexity

As gabriel_graph; 100,000 random planar points take about 0.6 s.

Checked

No python-igraph counterpart. Compared with a brute-force evaluation of the definition on 222 point sets in 1 to 8 dimensions and with an independent brute force in exact rational arithmetic on 835 more point sets (integer and real, collinear, co-circular, 1 to 4 dimensions); igraph's edge order is not tested.

C name

og_relative_neighborhood_graph

In notebooks

Og.RelativeNeighborhoodGraph

igraph 1.0

igraph_relative_neighborhood_graph

See also

gabriel_graph, lune_beta_skeleton, delaunay_graph

Builds the lune-based beta-skeleton of a point set: A and B are joined when a lune-shaped region built on AB holds no other point.

og_error_t og_lune_beta_skeleton(
    og_t *graph,
    const og_matrix_t *points,
    og_real_t beta
);

For beta >= 1 the region is the intersection of two closed balls of radius beta|AB|/2, centred on the line AB, one passing through A and the other through B. beta = 1 gives the Gabriel graph, beta = 2 the relative neighbourhood graph with closed lunes, and beta = infinity the open slab between the hyperplanes through A and B perpendicular to AB; these work in any dimension. For beta < 1, planar points only, the region is the set of points that see AB under an angle of at least pi - asin(beta), and the skeleton has more edges than the Delaunay graph (Kirkpatrick and Radke 1985).

A larger beta means larger regions and fewer edges. The regions are closed, so a point on the boundary blocks the edge (for beta = 2 this makes the result triangle-free). The graph is undirected, has one vertex per row and lists its edges sorted by (smaller id, larger id).

Parameters

• graph An uninitialised graph. On success it holds the result; destroy it with destroy.
• points One point per row; the number of columns is the dimension. Coordinates must be finite and no two rows equal.
• beta Positive; infinity is allowed. Values below 1 need planar points.

Returns

OG_SUCCESS, or one of the error codes below. On error no graph is left initialised.

Errors

• OG_EINVAL beta is not positive (or NaN), or beta < 1 and the points do not have two columns.
• OG_EINVAL A coordinate is NaN or infinite, the matrix has rows but no columns, or two points are equal.
• OG_ENOMEM Not enough memory.

Complexity

beta >= 1: the Delaunay graph plus one k-d tree search per candidate edge. beta < 1: every pair is a candidate and the search is output-sensitive; the result can have O(n^2) edges (points in convex position). 50,000 random planar points with beta 0.05 give 4.5 million edges in about 38 s.

Checked

No python-igraph counterpart. Compared with a brute-force evaluation of the definition on 954 cases (beta 0.05 to infinity, 1 to 8 dimensions) and over 300 planar point sets with beta < 1 and with an independent brute force in exact rational arithmetic on 835 more point sets (integer and real, collinear, co-circular, 1 to 4 dimensions); igraph's edge order is not tested.

C name

og_lune_beta_skeleton

In notebooks

Og.LuneBetaSkeleton

igraph 1.0

igraph_lune_beta_skeleton

See also

circle_beta_skeleton, beta_weighted_gabriel_graph, gabriel_graph, relative_neighborhood_graph

Builds the circle-based beta-skeleton of a planar point set.

og_error_t og_circle_beta_skeleton(
    og_t *graph,
    const og_matrix_t *points,
    og_real_t beta
);

For beta >= 1 the region built on AB is the union of the two closed discs of diameter beta|AB| whose circles pass through A and B: the points that see AB under an angle of at least asin(1/beta). For beta < 1 it is the intersection of the two closed discs of radius |AB|/(2 beta) through A and B: the points that see AB under an angle of at least pi - asin(beta). A and B are joined when the region holds no other point. beta = 1 gives the Gabriel graph. The points must have two columns. The graph is undirected, has one vertex per row and lists its edges sorted by (smaller id, larger id).

Parameters

• graph An uninitialised graph. On success it holds the result; destroy it with destroy.
• points One planar point per row (two columns); finite coordinates, no repeated points.
• beta Positive; infinity is allowed.

Returns

OG_SUCCESS, or one of the error codes below. On error no graph is left initialised.

Errors

• OG_EINVAL beta is not positive (or NaN), or there are points and the matrix does not have two columns.
• OG_EINVAL A coordinate is NaN or infinite, the matrix has rows but no columns, or two points are equal.
• OG_ENOMEM Not enough memory.

Complexity

beta >= 1: the Delaunay graph plus a k-d tree search per candidate edge. beta < 1: every pair is a candidate (output-sensitive search).

Checked

No python-igraph counterpart. Compared with a brute-force evaluation of the definition on 512 planar cases and over 300 point sets with beta < 1 and with an independent brute force in exact rational arithmetic on 835 more point sets (integer and real, collinear, co-circular, 1 to 4 dimensions); igraph's edge order is not tested.

C name

og_circle_beta_skeleton

In notebooks

Og.CircleBetaSkeleton

igraph 1.0

igraph_circle_beta_skeleton

See also

lune_beta_skeleton, gabriel_graph

Builds the Gabriel graph and gives each edge the beta at which it leaves the lune-based beta-skeleton.

og_error_t og_beta_weighted_gabriel_graph(
    og_t *graph,
    og_vector_t *weights,
    const og_matrix_t *points,
    og_real_t max_beta
);

The edges are those of gabriel_graph, in the same order. weights[e] is the threshold of edge e: the edge belongs to lune_beta_skeleton for every beta below it and to none at or above it, so the skeleton for any beta >= 1 is the set of edges whose weight is greater than beta. The weight is infinity when the edge never leaves the skeleton, or would only leave above max_beta. One call thus gives every lune-based skeleton with beta >= 1.

Parameters

• graph An uninitialised graph. On success it holds the result; destroy it with destroy.
• weights Initialised vector; receives one threshold per edge.
• points One point per row; the number of columns is the dimension. Coordinates must be finite and no two rows equal.
• max_beta Thresholds above this are reported as infinity; infinity for no limit.

Returns

OG_SUCCESS, or one of the error codes below. On error no graph is left initialised.

Errors

• OG_EINVAL max_beta is NaN.
• OG_EINVAL A coordinate is NaN or infinite, the matrix has rows but no columns, or two points are equal.
• OG_ENOMEM Not enough memory.

Complexity

As gabriel_graph, plus one best-first k-d tree search per edge, bounded by the lune of max_beta.

Checked

No python-igraph counterpart. Edges and thresholds against a brute force on 513 cases (weights to 1e-12), consistent with the lune skeletons for beta 1.5 and 3, plus the exact-rational brute force on 835 more point sets; igraph's convention at exact ties is not tested.

C name

og_beta_weighted_gabriel_graph

In notebooks

Og.BetaWeightedGabrielGraph

igraph 1.0

igraph_beta_weighted_gabriel_graph

See also

lune_beta_skeleton, gabriel_graph

Computes the length of every edge from the coordinates of its end points.

og_error_t og_spatial_edge_lengths(
    const og_t *graph,
    og_vector_t *lengths,
    const og_matrix_t *points,
    og_metric_t metric
);

lengths[e] is the distance, in the chosen metric, between the points of the two ends of edge e; row i of points holds the coordinates of vertex i. Any graph and any dimension; direction is ignored and a self-loop has length 0.

Parameters

• graph The graph.
• lengths Initialised vector; receives one length per edge, in edge order.
• points One row per vertex; finite coordinates.
• metric OG_METRIC_EUCLIDEAN or OG_METRIC_MANHATTAN.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL metric is unknown, points does not have one row per vertex, a coordinate is NaN or infinite, or the matrix has rows but no columns.
• OG_ENOMEM Not enough memory.

Complexity

O(|E| x d).

Checked

The definition checked on 200 random graphs (self-loops, multi-edges, both directions, 1 to 5 dimensions, both metrics).

C name

og_spatial_edge_lengths

In notebooks

Og.SpatialEdgeLengths

igraph 1.0

igraph_spatial_edge_lengths

See also

nearest_neighbor_graph, metric_t

Finds the corners of the convex hull of a planar point set, in clockwise order.

og_error_t og_convex_hull_2d(
    const og_matrix_t *data,
    og_vector_int_t *resverts,
    og_matrix_t *rescoords
);

Graham's scan: the start is the lowest point (the leftmost of the lowest, the first of identical copies), the other points are sorted by angle around it, and the scan keeps only strict turns. resverts receives the row indices of the corners, from that point clockwise; points on the hull's edges that are not corners are left out. rescoords receives the corners' coordinates as a k x 2 matrix in the same order. Either output may be NULL. Infinite coordinates are accepted; the angles come from the C library's atan2.

Parameters

• data One planar point per row (two columns).
• resverts Receives the row indices of the corners; may be NULL.
• rescoords Receives the corners' coordinates (k x 2); may be NULL.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL There are points and the matrix does not have two columns, or a coordinate is NaN.
• OG_ENOMEM Not enough memory.

Complexity

O(n log n).

Checked

Corners and their order identical to python-igraph 1.0 on 240 cases (random reals, integer grids, repeated and collinear points, circles, lines, 0 to 300 points). Among exact copies of a corner python-igraph's choice of index follows its unstable sort (72 corners report another copy with the same coordinates); nearly collinear sets follow atan2 to the last bit (no differences on Windows, 2 of 240 on macOS).

C name

og_convex_hull_2d

In notebooks

Og.ConvexHull2d

igraph 1.0

igraph_convex_hull_2d

See also

delaunay_graph

Draws length distinct integers from the range [l, h], uniformly at random, in increasing order.

og_error_t og_random_sample(
    og_vector_int_t *res,
    og_int_t l,
    og_int_t h,
    og_int_t length
);

Uses Vitter's sequential sampling (1987): method D, which skips ahead through the range with a rejection step, and method A when the sample is dense (13 x length >= h - l + 1). Every subset of the given size is equally likely, the result comes out sorted, and the range is never stored, so any part of the og_int_t range can be sampled. The random numbers come from the default generator (rng_default); rng_seed makes a run repeatable.

Parameters

• res Initialised vector; receives the sample in increasing order.
• l Smallest allowed value.
• h Largest allowed value.
• length Number of values to draw, 0 to h - l + 1.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL l > h, length is negative, or length is larger than the range.
• OG_ENOMEM Not enough memory.

Complexity

Expected O(length).

Checked

Different random draws than igraph; checked statistically: inclusion frequencies (chi-square), pair inclusion, uniformity of sparse samples and the distribution of the first value.

C name

og_random_sample

In notebooks

Og.RandomSample

igraph 1.0

igraph_random_sample

See also

rng_seed

Draws points uniformly on the surface of a sphere centred at the origin, in any dimension.

og_error_t og_rng_sample_sphere_surface(
    og_rng_t *rng,
    og_int_t dim,
    og_int_t n,
    og_real_t radius,
    og_bool_t positive,
    og_matrix_t *res
);

Each point is a vector of dim independent standard normal values scaled to length radius (Muller 1959), which is uniform on the sphere. With positive true every coordinate is replaced by its absolute value, which gives points uniform on the part of the sphere in the positive orthant. Note that the points are the columns of res, unlike the spatial graph functions, which take points as rows.

Parameters

• rng The random number generator to draw from, for example rng_default().
• dim Dimension, at least 2.
• n Number of points, at least 0.
• radius Radius; positive and finite.
• positive Whether to restrict the points to the positive orthant.
• res Initialised matrix; receives dim x n values, one point per column.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL dim is below 2, n is negative, or radius is not positive and finite.
• OG_ENOMEM Not enough memory.

Complexity

O(dim x n).

Checked

Point norms exact to 1e-12; coordinate means and E[x^2] = r^2/dim checked over 20000 samples in 2 to 5 dimensions, with and without positive. Argument rules as R igraph's sample_sphere_surface, except that a NaN or infinite radius is an error here.

C name

og_rng_sample_sphere_surface

In notebooks

Og.Native.og_rng_sample_sphere_surface

igraph 1.0

igraph_rng_sample_sphere_surface

See also

rng_sample_sphere_volume, rng_sample_dirichlet

Draws points uniformly inside a ball centred at the origin, in any dimension.

og_error_t og_rng_sample_sphere_volume(
    og_rng_t *rng,
    og_int_t dim,
    og_int_t n,
    og_real_t radius,
    og_bool_t positive,
    og_matrix_t *res
);

Each point is a uniform direction (drawn as in rng_sample_sphere_surface) times radius x U^(1/dim), with U uniform on [0, 1], which makes the points uniform in the ball. positive restricts them to the positive orthant. The points are the columns of res.

Parameters

• rng The random number generator to draw from, for example rng_default().
• dim Dimension, at least 2.
• n Number of points, at least 0.
• radius Radius; positive and finite.
• positive Whether to restrict the points to the positive orthant.
• res Initialised matrix; receives dim x n values, one point per column.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL dim is below 2, n is negative, or radius is not positive and finite.
• OG_ENOMEM Not enough memory.

Complexity

O(dim x n).

Checked

(|x|/r)^dim checked to be uniform on [0, 1] over 20000 samples in 2 to 5 dimensions, with and without positive; argument rules as R igraph's sample_sphere_volume.

C name

og_rng_sample_sphere_volume

In notebooks

Og.Native.og_rng_sample_sphere_volume

igraph 1.0

igraph_rng_sample_sphere_volume

See also

rng_sample_sphere_surface

Draws n samples from the Dirichlet distribution with parameter vector alpha.

og_error_t og_rng_sample_dirichlet(
    og_rng_t *rng,
    og_int_t n,
    const og_vector_t *alpha,
    og_matrix_t *res
);

Each sample is a vector of independent gamma variates with shapes alpha[i] and scale 1, divided by its sum, so its entries are positive and add up to 1. The work is done in logarithms, with gamma(a) = gamma(a + 1) x U^(1/a) for a < 1, so even tiny parameters (1e-3) do not underflow to 0/0. The samples are the columns of res, which becomes length(alpha) x n.

Parameters

• rng The random number generator to draw from, for example rng_default().
• n Number of samples, at least 0.
• alpha The parameters: at least two, each positive and finite.
• res Initialised matrix; receives one sample per column.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL n is negative, alpha has fewer than two values, or a parameter is not positive and finite.
• OG_ENOMEM Not enough memory.

Complexity

O(length(alpha) x n).

Checked

Means and variances against the Dirichlet moments over 20000 samples, columns summing to 1, no NaN for parameters of 1e-3. Argument rules as R igraph's sample_dirichlet, except that NaN or infinite parameters are errors here.

C name

og_rng_sample_dirichlet

In notebooks

Og.Native.og_rng_sample_dirichlet

igraph 1.0

igraph_rng_sample_dirichlet

See also

rng_sample_sphere_surface

Fits a power-law distribution to samples by maximum likelihood, choosing the lower cutoff xmin by the Kolmogorov-Smirnov distance.

og_error_t og_power_law_fit(
    const og_vector_t *data,
    og_plfit_result_t *result,
    og_real_t xmin,
    og_bool_t force_continuous
);

Follows Clauset, Shalizi and Newman (2009). The data are treated as discrete when every value is a whole number, unless force_continuous. For a given xmin only the samples at or above it count: the continuous exponent is 1 + n / sum ln(x / xmin), the discrete one the exact root of the likelihood equation, which involves the Hurwitz zeta function. With fewer than 50 samples in the tail the exponent gets the finite-size correction 1 + (alpha - 1)(n - 1)/n. L is the log-likelihood and D the KS distance between the tail and the fitted law.

With xmin negative or NaN, xmin is chosen among the distinct sample values (all but the largest) as the one with the smallest D. For continuous data with 50 or more distinct values the search is a coarse pass over every tenth value followed by the neighbourhood of the best, which is what python-igraph 1.0 does; discrete data are scanned in full. Discrete samples that are all below 1 give xmin 1, alpha infinity, L NaN and D = DBL_MAX. A sample of minus infinity is simply below every xmin.

Parameters

• data The samples.
• result Receives the fit; may be NULL. Its data member points to data.
• xmin The lower cutoff, or a negative value or NaN to search for it. A given xmin must be positive (continuous) or at least 1 (discrete).
• force_continuous Whether to use the continuous model even when all values are whole numbers.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL data is empty or holds NaN, a given xmin is out of range or has no sample at or above it, no value can serve as xmin, the fitted exponent is not above 1 (too few tail samples), or continuous data hold +infinity.
• OG_FAILURE Discrete data hold +infinity.
• OG_ENOMEM Not enough memory.

Complexity

O(n log n) for a given xmin (sorting). With the search, O(n) per candidate: O(n x k) for discrete data with k distinct values, about O(n x (k/10 + 18)) for continuous data. 100,000 continuous samples with the search take about 0.5 s.

Checked

Continuous fits identical to python-igraph 1.0 to 1e-10 (alpha, xmin, L, D) on 363 fixture cases and 430 more on a fresh seed. Discrete exponents are the exact root (checked against 50-digit arithmetic) where python-igraph's optimiser stops about 1e-6 short, so alpha and D agree to 5e-5. python-igraph's discrete xmin search passes over some winning candidates: the chosen xmin differed on 99 of 1495 random samples, mostly below 10 values, where Open Graph keeps the exact KS minimum. NaN samples are an error here and give NaN results there.

C name

og_power_law_fit

In notebooks

Og.PowerLawFit

igraph 1.0

igraph_power_law_fit

See also

plfit_result_t, plfit_result_calculate_p_value

og_plfit_result_t fit;
og_real_t p;
/* degrees: an og_vector_t of samples; search for xmin */
if (og_power_law_fit(&degrees, &fit, -1, false) == OG_SUCCESS) {
    printf("alpha %g, xmin %g, KS %g\n", fit.alpha, fit.xmin, fit.D);
    /* precision 0.01: 2500 bootstrap samples */
    og_plfit_result_calculate_p_value(&fit, &p, 0.01);
}

Estimates the p-value of a power-law fit by a semi-parametric bootstrap.

og_error_t og_plfit_result_calculate_p_value(
    const og_plfit_result_t *model,
    og_real_t *result,
    og_real_t precision
);

Draws floor(0.25 / precision^2) synthetic data sets of the original size: each value comes from the fitted power law with probability n_tail / n and is otherwise drawn from the observed values below xmin. Every set is refitted with its own xmin search, and the p-value is the fraction of sets whose KS distance exceeds the model's D (Clauset, Shalizi and Newman 2009, section 4.1). A small p-value is evidence against the power law. precision 0.01 means 2500 data sets. Random numbers come from the default generator.

Parameters

• model A result of power_law_fit whose data vector is still alive.
• result Receives the p-value; may be NULL.
• precision The wanted accuracy of the p-value; its sign is ignored, and 0.25 / precision^2 must lie between 1 and 2^31 - 1.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL model or its data is NULL, precision is out of range, or the model's alpha is not above 1 or its xmin is NaN.
• OG_ENOMEM Not enough memory.

Complexity

floor(0.25 / precision^2) refits, each costing as much as power_law_fit with the xmin search.

Checked

p-values of 10 data sets (5 with a searched xmin, 5 with a given one) within 4 standard errors + 0.02 of python-igraph 1.0's; the same precisions are accepted.

C name

og_plfit_result_calculate_p_value

In notebooks

Og.PlfitResultCalculatePValue

igraph 1.0

igraph_plfit_result_calculate_p_value

See also

power_law_fit, plfit_result_t

Reports the version of the Open Graph library.

void og_version(
    const char **version_string,
    int *major,
    int *minor,
    int *patch
);

Gives the version string (OG_VERSION_STRING) and its major, minor and patch numbers (OG_VERSION_MAJOR, OG_VERSION_MINOR, OG_VERSION_PATCH). This is Open Graph's own version, not igraph's. Any argument may be NULL; the string is static and must not be freed.

Parameters

• version_string Receives the version string; may be NULL.
• major Receives the major number; may be NULL.
• minor Receives the minor number; may be NULL.
• patch Receives the patch number; may be NULL.

Returns

Nothing.

Complexity

O(1).

Checked

Reports Open Graph's own version; every argument may be NULL.

C name

og_version

In notebooks

Og.Native.og_version

igraph 1.0

igraph_version

Computes the mean of every window of binwidth consecutive values.

og_error_t og_running_mean(
    const og_vector_t *data,
    og_vector_t *res,
    og_int_t binwidth
);

res[i] is the mean of data[i], ..., data[i + binwidth - 1], so res gets n - binwidth + 1 values for n data values. The windows share one running sum: the first window is added up in order, then each step subtracts the value that leaves and adds the one that enters. This is fast, but rounding from earlier windows carries over, and once an infinity or NaN has entered, every later mean is infinite or NaN.

Parameters

• data The values.
• res Initialised vector; receives the means.
• binwidth Window length, 1 to the number of values.

Returns

OG_SUCCESS, or one of the error codes below.

Errors

• OG_EINVAL binwidth is below 1 or larger than the number of values.
• OG_ENOMEM Not enough memory.

Complexity

O(n).

Checked

Bit for bit equal to R igraph 2.3.3's running_mean (igraph C 0.10) on 220 vectors with mixed magnitudes, infinities and NaN; python-igraph does not expose it.

C name

og_running_mean

In notebooks

Og.RunningMean

igraph 1.0

igraph_running_mean

Compares two doubles with a relative tolerance and returns -1, 0 or 1.

int og_cmp_epsilon(double a, double b, double eps);

Returns 0 when a == b (equal infinities included) or when |a - b| / (|a| + |b|) < eps; otherwise -1 if a < b and 1 if a > b. With eps 0 or negative only exact equality gives 0. NaN never compares equal (which sign is returned then is unspecified), and an infinity equals only the same infinity. The test runs on copies scaled by a power of two, so it neither overflows near DBL_MAX nor loses accuracy for subnormal numbers.

Parameters

• a First value.
• b Second value.
• eps Relative tolerance.

Returns

0 when a and b are equal within eps, else -1 (a < b) or 1 (a > b).

Complexity

O(1).

Checked

Not exposed by python-igraph. Unit tests of the rule: eps = 0, NaN, infinities, values near DBL_MAX and subnormals.

C name

og_cmp_epsilon

In notebooks

Og.CmpEpsilon

igraph 1.0

igraph_cmp_epsilon

See also

almost_equals, complex_almost_equals

Tells whether two doubles are equal within a relative tolerance.

og_bool_t og_almost_equals(double a, double b, double eps);

True exactly when cmp_epsilon(a, b, eps) is 0: a == b, or |a - b| / (|a| + |b|) < eps. NaN is never almost equal to anything, itself included.

Parameters

• a First value.
• b Second value.
• eps Relative tolerance.

Returns

true or false.

Complexity

O(1).

Checked

Defined as cmp_epsilon(a, b, eps) == 0; unit-tested.

C name

og_almost_equals

In notebooks

Og.AlmostEquals

igraph 1.0

igraph_almost_equals

See also

cmp_epsilon, complex_almost_equals

Tells whether two complex numbers are equal within a relative tolerance.

og_bool_t og_complex_almost_equals(
    og_complex_t a,
    og_complex_t b,
    og_real_t eps
);

True when a and b are identical, or when |a - b| < eps x (|a| + |b|) with |.| the complex modulus. A NaN or infinite part makes the answer false unless the two numbers are identical; eps 0 or negative means exact equality. The moduli are computed on parts scaled by a power of two, so nothing overflows or underflows.

Parameters

• a First value.
• b Second value.
• eps Relative tolerance.

Returns

true or false.

Complexity

O(1).

Checked

Unit tests: NaN never equal, equal infinities equal, no overflow near DBL_MAX.

C name

og_complex_almost_equals

In notebooks

Og.Native.og_complex_almost_equals

igraph 1.0

igraph_complex_almost_equals

See also

almost_equals, cmp_epsilon