Rollup

What rollup does when the links it follows loop back.

typedef enum og_rollup_loops_t {
    OG_ROLLUP_REFUSE = 0,
    OG_ROLLUP_SOLVE = 1
} og_rollup_loops_t;

OG_ROLLUP_REFUSE (0, the default): a loop among the vertices the starts reach is an error, OG_EINVAL, and rollup names one cycle of it - right for a bill of materials, where a loop is a data error. OG_ROLLUP_SOLVE (1): loops are solved exactly, x_K = (I - C_K^T)^-1 b_K, as cross-holdings, reciprocal cost allocations and input-output tables need; a loop whose coefficients, taken without their signs, have a spectral radius of 1 or more does not converge and is OG_DIVERGED. Any other value is OG_EINVAL.

Checked

Open Graph extension, no igraph counterpart: Norway Analytics' own design for OpenBI's NETWORK.ROLLUP and the notebooks' Graph.Rollup, checked against its specification and its tests.

C name

og_rollup_loops_t

In notebooks

Og.RollupLoops

igraph 1.0

None: Open Graph's own.

See also

rollup, rollup_options_t

The level rollup gives a vertex inside a solved loop.

#define OG_ROLLUP_IN_LOOP (-1)

A level counts the most links from a start, a loop being one stop; inside a loop the paths go round without end, so a vertex there has no level of its own and gets -1 (OpenBI shows BLANK). The vertices after the loop count on from the loop's place.

Checked

Open Graph extension, no igraph counterpart: Norway Analytics' own design for OpenBI's NETWORK.ROLLUP and the notebooks' Graph.Rollup, checked against its specification and its tests.

C name

OG_ROLLUP_IN_LOOP

In notebooks

Og.OG_ROLLUP_IN_LOOP

igraph 1.0

None: Open Graph's own.

See also

rollup

The choices rollup takes.

typedef struct og_rollup_options_t {
    og_neimode_t mode;
    og_rollup_loops_t loops;
    og_bool_t by_start;
    og_int_t max_rows;
    og_real_t max_work;
} og_rollup_options_t;

mode: OG_OUT (the default) follows each edge from its tail to its head - a bill of materials exploded, an owner's effective shares; OG_IN goes against the edges - costs rolled up from parts, a company's ultimate owners (ignored on an undirected graph, whose edges work both ways). loops: OG_ROLLUP_REFUSE (the default) or OG_ROLLUP_SOLVE. by_start: false (the default) gives one total per vertex over all starts; true gives each start's own totals, a row per start and vertex it reaches (which product drives the need for a part). max_rows and max_work: 0 (the default) for no limit; otherwise a call whose answer has more rows, or would take more elementary steps (vertices and arcs visited, entries of factors and sweeps used), stops with OG_ERANGE before the totals are made. A host derives max_work from the steps per second it measured, so its time guard refuses the same calls on every computer and never depends on a clock. Fill it with rollup_options_init.

Checked

Open Graph extension, no igraph counterpart: Norway Analytics' own design for OpenBI's NETWORK.ROLLUP and the notebooks' Graph.Rollup, checked against its specification and its tests.

C name

og_rollup_options_t

In notebooks

Og.RollupOptions

igraph 1.0

None: Open Graph's own.

See also

rollup_options_init, rollup

What rollup found on its way, also when it stops with an error.

typedef struct og_rollup_info_t {
    og_int_t reached;
    og_int_t arcs;
    og_int_t loops;
    og_int_t largest;
    og_int_t rows;
    og_real_t work;
} og_rollup_info_t;

reached: the vertices the starts reach together, the starts included. arcs: the merged links leaving them. loops: the loops among them (strongly connected parts with a cycle) and largest: the vertices of the largest (0 without loops). rows: the rows of the answer (max_rows + 1 when it stopped for having more). work: the elementary steps the answer takes or would take (at least max_work when it stopped for that). Filled as far as the call got.

Checked

Open Graph extension, no igraph counterpart: Norway Analytics' own design for OpenBI's NETWORK.ROLLUP and the notebooks' Graph.Rollup, checked against its specification and its tests.

C name

og_rollup_info_t

In notebooks

Og.RollupInfo

igraph 1.0

None: Open Graph's own.

See also

rollup

Fills the rollup's options with their defaults.

og_error_t og_rollup_options_init(og_rollup_options_t *opts);

Mode OG_OUT, loops OG_ROLLUP_REFUSE, not by start, no limit on rows or work. rollup takes NULL options to mean the same.

Parameters

• opts The options to fill.

Returns

OG_SUCCESS.

Errors

• OG_EINVAL opts is NULL.

Complexity

O(1).

Checked

Open Graph extension, no igraph counterpart: Norway Analytics' own design for OpenBI's NETWORK.ROLLUP and the notebooks' Graph.Rollup, checked against its specification and its tests.

C name

og_rollup_options_init

In notebooks

Og.RollupOptionsInit

igraph 1.0

None: Open Graph's own.

See also

rollup_options_t, rollup

Multiplies along every path from the starts and adds the paths up: bills of materials, ownership through chains, reciprocal allocation, Leontief input-output.

og_error_t og_rollup(
    const og_t *graph,
    const og_vector_t *weights,
    const og_vector_int_t *starts,
    const og_vector_t *amounts,
    const og_rollup_options_t *opts,
    og_vector_int_t *res_start,
    og_vector_int_t *res_vertex,
    og_vector_t *res_total,
    og_vector_int_t *res_level,
    og_vector_int_t *loop,
    og_rollup_info_t *info
);

Each edge carries a coefficient (its weight: a quantity per unit, a share, a cost rate) and each start an amount. A vertex's total is the sum, over every start and every path from it to the vertex, of the start's amount times the product of the coefficients along the path; a start's own amount counts (the path of no edges). With the 500 bikes of a bill of materials as the start, two wheels a bike and 36 spokes a wheel, the spokes' total is 36,000. Where edges loop back there are infinitely many paths, and their sum is the solution of x = d + C^T x, which rollup solves exactly (OG_ROLLUP_SOLVE) or refuses (OG_ROLLUP_REFUSE, the default).

Coefficients: several edges between one pair (one direction) add up, exactly and rounded once, so their order never changes a total and +0.3, -0.3, 0.1 give 0.1 itself; a pair adding up to exactly 0 is no link at all. Weights may be negative (a by-product), never NaN or infinite. Starts may repeat (their amounts add up the same way); a start nothing links from gives just its own row.

Loops (strongly connected parts with a cycle, or a vertex linked to itself) among the vertices reached are solved one by one in the order the links run: up to 32 vertices by a dense LU, larger ones by Gauss-Seidel sweeps when the convergence certificate's own sweeps settle quickly, else by the sparse LU. A loop converges when the spectral radius of its coefficients, taken without their signs, is below 1 (then the paths add up to the same total in any order); rollup certifies it by solving (I - |C_K|^T) y = 1, whose solution must be positive and at most 1e12. A loop that fails is OG_DIVERGED, and loop holds a cycle through its smallest vertex.

Rows come by start (ascending, only with by_start), then level, then vertex id. The level is the most links from a start, a loop counted as one stop (ROLLUP_IN_LOOP inside a loop). The same graph numbered the same gives the same bits whatever the order of its edges, the number of threads or the platform.

Parameters

• graph The graph; directed for the usual cases (an undirected edge works both ways, so every edge is a loop of two).
• weights Each edge's coefficient, finite and of any sign; NULL for all 1 (the totals then count paths).
• starts The start vertices, repeats allowed; empty gives no rows.
• amounts Each start's amount, finite; NULL for all 1.
• opts The options (rollup_options_t), or NULL for the defaults.
• res_start Output, may be NULL: each row's start (-1 without by_start).
• res_vertex Output: each row's vertex.
• res_total Output: each row's total.
• res_level Output, may be NULL: each row's level, ROLLUP_IN_LOOP inside a loop.
• loop Output, may be NULL: on a loop refused (OG_EINVAL) or not converging (OG_DIVERGED), a shortest cycle through the loop's smallest vertex, from it; otherwise empty.
• info Output, may be NULL: what the call found (rollup_info_t).

Returns

OG_SUCCESS.

Errors

• OG_EINVAL A weight or amount that is NaN or infinite; weights or amounts of the wrong length; an unknown loops value; a negative cap; a pair's weights or a start's amounts adding up beyond the largest double; a loop under OG_ROLLUP_REFUSE (named in loop).
• OG_EINVVID A start that is no vertex.
• OG_EINVMODE A directed graph's mode other than OG_OUT or OG_IN.
• OG_DIVERGED A loop whose coefficients without their signs have a spectral radius of 1 or more (named in loop).
• OG_ERANGE More rows than max_rows, or more work than max_work (info says how much).
• OG_ENOMEM Not enough memory.

Complexity

O(|R| + arcs of R) to merge the reached vertices' edges and find their loops; each loop prepared once (dense k^3/3 up to 32 vertices; larger, a few Gauss-Seidel sweeps over its arcs, or the sparse LU's factors); then each piece (all starts, or each start) visits its vertices and arcs, sorts them (O(r log r)) and solves its loops.

Checked

Open Graph extension, no igraph counterpart: Norway Analytics' own design for OpenBI's NETWORK.ROLLUP and the notebooks' Graph.Rollup, checked against its specification and its tests. Checked against an independent Python reference (exact fractions, brute-force paths, numpy/scipy dense solves; 2,943 cases, 28,666 rows): largest relative difference 2.2e-13, every vertex, start, level, loop and error the same; against Statistics Norway's (2000, 23 industries) and Statistics Finland's (2021 and 2022, 63 industries) published Leontief inverses within their 3 decimals and 1.9e-15 relative of the exact inverses.

Threads

With by_start, each start is a piece run as a task (a first pass counts each start's rows, a second writes them at their offsets); loops are prepared on the calling thread. Bit-identical for any number of threads and any executor.

C name

og_rollup

In notebooks

Og.Rollup

igraph 1.0

None: Open Graph's own.

See also

rollup_options_t, rollup_info_t, rollup_loops_t, ROLLUP_IN_LOOP

#include "og.h"
#include <stdio.h>

int main(void) {
    /* 0 bike, 1 wheel, 2 spoke: 2 wheels a bike, 36 spokes a wheel */
    og_t g;
    og_vector_int_t e, starts, vertex;
    og_vector_t w, amounts, total;
    og_int_t i;
    og_vector_int_init_int(&e, 4, 0, 1, 1, 2);
    og_create(&g, &e, 3, OG_DIRECTED);
    og_vector_init_real(&w, 2, 2.0, 36.0);
    og_vector_int_init_int(&starts, 1, 0);
    og_vector_init_real(&amounts, 1, 500.0);
    og_vector_int_init(&vertex, 0);
    og_vector_init(&total, 0);
    og_rollup(&g, &w, &starts, &amounts, NULL, NULL, &vertex, &total, NULL, NULL, NULL);
    for (i = 0; i < og_vector_int_size(&vertex); i++) {
        printf("%d: %g\n", (int) VECTOR(vertex)[i], VECTOR(total)[i]);   /* 0: 500, 1: 1000, 2: 36000 */
    }
    og_vector_destroy(&total);
    og_vector_int_destroy(&vertex);
    og_vector_destroy(&amounts);
    og_vector_int_destroy(&starts);
    og_vector_destroy(&w);
    og_destroy(&g);
    og_vector_int_destroy(&e);
    return 0;
}