Operators and bipartite graphs

How induced_subgraph builds its result.

typedef enum og_subgraph_implementation_t {
    OG_SUBGRAPH_AUTO = 0,              /* choose by the share of vertices kept */
    OG_SUBGRAPH_COPY_AND_DELETE = 1,   /* copy the graph, delete the other vertices */
    OG_SUBGRAPH_CREATE_FROM_SCRATCH = 2 /* build a new graph from the kept vertices */
} og_subgraph_implementation_t;

Both methods give the same graph; they differ in speed and in edge order. Other values give OG_EINVAL.

Parameters

• OG_SUBGRAPH_AUTO 0: COPY_AND_DELETE when more than half of the vertices are selected, else CREATE_FROM_SCRATCH.
• OG_SUBGRAPH_COPY_AND_DELETE 1: copy the graph and delete the other vertices.
• OG_SUBGRAPH_CREATE_FROM_SCRATCH 2: build a new graph from the kept vertices.

Checked

Enum; every value is tested through induced_subgraph against python-igraph.

C name

og_subgraph_implementation_t

In notebooks

Og.SubgraphImplementation

igraph 1.0

igraph_subgraph_implementation_t

See also

induced_subgraph, induced_subgraph_map

The graph products of product.

typedef enum og_product_t {
    OG_PRODUCT_CARTESIAN = 0,
    OG_PRODUCT_LEXICOGRAPHIC = 1,
    OG_PRODUCT_STRONG = 2,
    OG_PRODUCT_TENSOR = 3,
    OG_PRODUCT_MODULAR = 4
} og_product_t;

Definitions under product. Other values give OG_EINVAL.

Parameters

• OG_PRODUCT_CARTESIAN 0: Cartesian product.
• OG_PRODUCT_LEXICOGRAPHIC 1: lexicographic product.
• OG_PRODUCT_STRONG 2: strong product.
• OG_PRODUCT_TENSOR 3: tensor (direct) product.
• OG_PRODUCT_MODULAR 4: modular product (simple graphs only).

Checked

Enum; every value is tested through product against networkx.

C name

og_product_t

In notebooks

Og.ProductType

igraph 1.0

igraph_product_t

See also

product

Builds a graph from vertex kinds and an edge list, checking that every edge joins the two kinds.

og_error_t og_create_bipartite(
    og_t *graph,
    const og_vector_bool_t *types,
    const og_vector_int_t *edges,
    og_bool_t directed
);

types has one entry per vertex (false and true are the two kinds); its length sets the vertex count. edges lists the two endpoints of every edge in turn, and the edge order is kept. Every edge must join a false vertex and a true one.

Parameters

• graph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• types The kind of every vertex.
• edges Endpoints of the edges, two entries per edge.
• directed true for a directed graph.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL edges has an odd number of entries, or an edge joins two vertices of the same kind.
• OG_EINVVID edges names a vertex id outside 0 .. size of types - 1.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

220 random bipartite graphs rebuilt from python-igraph's types and edges; the error codes as python-igraph reports them.

C name

og_create_bipartite

In notebooks

Og.CreateBipartite

igraph 1.0

igraph_create_bipartite

See also

full_bipartite, is_bipartite, biadjacency

Complete bipartite graph K(n1, n2).

og_error_t og_full_bipartite(
    og_t *graph,
    og_vector_bool_t *types,
    og_int_t n1,
    og_int_t n2,
    og_bool_t directed,
    og_neimode_t mode
);

Vertices 0 .. n1-1 are the first kind (type false), n1 .. n1+n2-1 the second (type true), and every vertex of the first kind is joined to every vertex of the second. A directed graph takes its directions from mode; with OG_ALL each pair gets two edges, first to second kind first. Edges are listed by first-kind vertex, then by second-kind vertex.

Parameters

• graph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• types Output (may be NULL): the kind of every vertex, false for the first n1, true for the rest.
• n1 Number of first-kind vertices.
• n2 Number of second-kind vertices.
• directed true for a directed graph; mode then sets the edge directions.
• mode Directed graphs only: OG_OUT for edges from the first kind to the second, OG_IN the other way, OG_ALL for both.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL n1 or n2 is negative.
• OG_EINVMODE The graph is directed and mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(n1 n2).

Checked

python-igraph's Full_Bipartite on 420 cases (sizes up to 40x40, every directedness and mode); edge order and types identical.

C name

og_full_bipartite

In notebooks

Og.FullBipartite

igraph 1.0

igraph_full_bipartite

See also

create_bipartite, bipartite_game_gnm

Random bipartite graph with exactly m edges, G(n1, n2, m).

og_error_t og_bipartite_game_gnm(
    og_t *graph,
    og_vector_bool_t *types,
    og_int_t n1,
    og_int_t n2,
    og_int_t m,
    og_bool_t directed,
    og_neimode_t mode,
    og_edge_type_sw_t allowed_edge_types,
    og_bool_t edge_labeled
);

Vertices as in full_bipartite, edge directions as there. The m edges are drawn uniformly among the possible first-kind/second-kind pairs. allowed_edge_types decides whether parallel edges are allowed (OG_MULTI_SW); self-loops cannot occur in a bipartite graph. With edge_labeled = true the order of the edges is part of the random outcome; with false the edge list is a set (or a multiset).

Without parallel edges a uniform m-subset of the possible edges is drawn (Vitter's sampling methods) and listed in a fixed order (unlabeled) or a uniformly random order (labeled). With parallel edges, unlabeled draws a uniform multiset and lists it in random order, and labeled draws m independent uniform edges. Asking for every possible edge without parallel edges gives full_bipartite's graph. Random numbers come from rng_default().

Parameters

• graph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• types Output (may be NULL): the kind of every vertex, false for the first n1, true for the rest.
• n1 Number of first-kind vertices.
• n2 Number of second-kind vertices.
• m Number of edges.
• directed true for a directed graph; mode then sets the edge directions.
• mode Directed graphs only: OG_OUT for edges from the first kind to the second, OG_IN the other way, OG_ALL for both.
• allowed_edge_types OG_MULTI_SW allows parallel edges; OG_SIMPLE_SW does not.
• edge_labeled true: edge order is part of the outcome; false: the edges form a set.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL n1, n2 or m is negative; m exceeds the number of possible edges without parallel edges; or m > 0 with no possible edge.
• OG_EINVMODE The graph is directed and mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(n1 + n2 + m).

Checked

Open Graph's own random stream, so one seed gives another graph than igraph. Outcome distributions match python-igraph's Random_Bipartite(m=...) by chi-square (20,000 draws per configuration) and the exact uniform law; unlabeled samples list their edges in python-igraph's order.

C name

og_bipartite_game_gnm

In notebooks

Og.BipartiteGameGnm

igraph 1.0

igraph_bipartite_game_gnm

See also

bipartite_game_gnp, bipartite_iea_game, full_bipartite

Random bipartite graph in which each possible edge appears with probability p, G(n1, n2, p).

og_error_t og_bipartite_game_gnp(
    og_t *graph,
    og_vector_bool_t *types,
    og_int_t n1,
    og_int_t n2,
    og_real_t p,
    og_bool_t directed,
    og_neimode_t mode,
    og_edge_type_sw_t allowed_edge_types,
    og_bool_t edge_labeled
);

Vertices and directions as bipartite_game_gnm. Without parallel edges each possible first-kind/second-kind edge is present independently with probability p (0 <= p <= 1), found by geometric skipping (Batagelj and Brandes 2005); p = 1 gives full_bipartite's graph.

With parallel edges (OG_MULTI_SW) p is the expected number of edges per possible pair and may exceed 1. Unlabeled: every pair gets a geometric number of edges with mean p. Labeled: a geometric total with mean p times the number of pairs, placed uniformly. The labeled model without parallel edges is not available (OG_UNIMPLEMENTED), as in igraph. Random numbers come from rng_default().

Parameters

• graph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• types Output (may be NULL): the kind of every vertex, false for the first n1, true for the rest.
• n1 Number of first-kind vertices.
• n2 Number of second-kind vertices.
• p Edge probability, or the expected multiplicity with parallel edges.
• directed true for a directed graph; mode then sets the edge directions.
• mode Directed graphs only: OG_OUT for edges from the first kind to the second, OG_IN the other way, OG_ALL for both.
• allowed_edge_types OG_MULTI_SW allows parallel edges; OG_SIMPLE_SW does not.
• edge_labeled true: edge order is part of the outcome (parallel edges only).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL n1 or n2 is negative, or p is NaN, negative, infinite, or above 1 without parallel edges.
• OG_UNIMPLEMENTED edge_labeled is true without parallel edges.
• OG_EINVMODE The graph is directed and mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(n1 + n2 + number of edges drawn).

Checked

Open Graph's own random stream. Outcome and edge-count histograms match python-igraph's Random_Bipartite(p=...), plus the exact law on 2x2 and the mean p N for multigraphs; edge order as python-igraph's.

C name

og_bipartite_game_gnp

In notebooks

Og.BipartiteGameGnp

igraph 1.0

igraph_bipartite_game_gnp

See also

bipartite_game_gnm, bipartite_iea_game

Random bipartite multigraph from m independently placed edges.

og_error_t og_bipartite_iea_game(
    og_t *graph,
    og_vector_bool_t *types,
    og_int_t n1,
    og_int_t n2,
    og_int_t m,
    og_bool_t directed,
    og_neimode_t mode
);

Each of the m edges joins a uniformly chosen first-kind/second-kind pair, independently of the others (independent edge assignment), so parallel edges can occur. Vertices and directions as bipartite_game_gnm. Random numbers come from rng_default().

Parameters

• graph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• types Output (may be NULL): the kind of every vertex, false for the first n1, true for the rest.
• n1 Number of first-kind vertices.
• n2 Number of second-kind vertices.
• m Number of edges.
• directed true for a directed graph; mode then sets the edge directions.
• mode Directed graphs only: OG_OUT for edges from the first kind to the second, OG_IN the other way, OG_ALL for both.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL n1, n2 or m is negative, or m > 0 with no possible edge.
• OG_EINVMODE The graph is directed and mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(n1 + n2 + m).

Checked

python-igraph has no bipartite IEA model: uniformity over ordered edge lists by goodness of fit. It is the same model as the edge-labeled multigraph G(n1, n2, m), which is compared with python-igraph.

C name

og_bipartite_iea_game

In notebooks

Og.BipartiteIeaGame

igraph 1.0

igraph_bipartite_iea_game

See also

bipartite_game_gnm, bipartite_game_gnp

Builds a bipartite graph from its biadjacency matrix.

og_error_t og_biadjacency(
    og_t *graph,
    og_vector_bool_t *types,
    const og_matrix_t *biadjmatrix,
    og_bool_t directed,
    og_neimode_t mode,
    og_bool_t multiple
);

Row i of the matrix is first-kind vertex i (type false), column j is second-kind vertex rows + j (type true). With multiple = false every nonzero entry (NaN included) gives one edge; with multiple = true an entry is a count, its integer part giving that many parallel edges, and must be finite and not negative. Entries are read column by column, which sets the edge order. directed and mode as in full_bipartite.

Parameters

• graph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• types Output (may be NULL): the kind of every vertex.
• biadjmatrix The biadjacency matrix: rows are first-kind vertices, columns second-kind ones.
• directed true for a directed graph; mode then sets the edge directions.
• mode Directed graphs only: OG_OUT for edges from the first kind to the second, OG_IN the other way, OG_ALL for both.
• multiple true: entries are edge counts; false: any nonzero entry is one edge.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL multiple is true and an entry is negative, NaN or infinite.
• OG_ERANGE An entry asks for more edges than Open Graph supports.
• OG_EINVMODE The graph is directed and mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Memory runs out.

Complexity

O(rows x cols + |E|).

Checked

220 random matrices for every directedness, mode and multiple, edge order identical to python-igraph's Biadjacency. Deliberate difference: with multiple, NaN and +inf entries are refused (python-igraph makes no edge for them).

C name

og_biadjacency

In notebooks

Og.Biadjacency

igraph 1.0

igraph_biadjacency

See also

weighted_biadjacency, get_biadjacency, create_bipartite

Builds a weighted bipartite graph from a biadjacency matrix.

og_error_t og_weighted_biadjacency(
    og_t *graph,
    og_vector_bool_t *types,
    og_vector_t *weights,
    const og_matrix_t *biadjmatrix,
    og_bool_t directed,
    og_neimode_t mode
);

As biadjacency without counts: every nonzero entry gives one edge, and weights receives the entry as that edge's weight (in a directed graph with OG_ALL both edges get it).

Parameters

• graph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• types Output (may be NULL): the kind of every vertex.
• weights Output (may be NULL): the weight of every edge, in edge order.
• biadjmatrix The biadjacency matrix: rows are first-kind vertices, columns second-kind ones.
• directed true for a directed graph; mode then sets the edge directions.
• mode Directed graphs only: OG_OUT for edges from the first kind to the second, OG_IN the other way, OG_ALL for both.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVMODE The graph is directed and mode is not OG_OUT, OG_IN or OG_ALL.
• OG_ENOMEM Memory runs out.

Complexity

O(rows x cols + |E|).

Checked

The same 220 matrices against python-igraph's Biadjacency(weighted=True): edges and weights identical for every directedness and mode.

C name

og_weighted_biadjacency

In notebooks

Og.WeightedBiadjacency

igraph 1.0

igraph_weighted_biadjacency

See also

biadjacency, get_biadjacency

Biadjacency matrix of a bipartite graph.

og_error_t og_get_biadjacency(
    const og_t *graph,
    const og_vector_bool_t *types,
    const og_vector_t *weights,
    og_matrix_t *res,
    og_vector_int_t *row_ids,
    og_vector_int_t *col_ids
);

Rows are the vertices of type false and columns those of type true, each in increasing id; row_ids and col_ids give the vertex behind every row and column. Entry (i, j) counts the edges between the two vertices, or sums their weights when weights is given. Edge directions are ignored. Edges joining two vertices of the same kind are left out, with a warning.

Parameters

• graph The input graph.
• types The kind of every vertex.
• weights Edge weights to sum (may be NULL: count the edges).
• res Output: the matrix, resized to (number of false vertices) x (number of true vertices).
• row_ids Output (may be NULL): vertex id of every row.
• col_ids Output (may be NULL): vertex id of every column.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL types does not have one entry per vertex, or weights one entry per edge.
• OG_ENOMEM Memory runs out.

Complexity

O(n1 n2 + |V| + |E|), n1 and n2 the sizes of the two kinds.

Checked

220 random bipartite graphs (parallel edges, both orientations) against python-igraph's get_biadjacency: matrix, row and column ids identical.

C name

og_get_biadjacency

In notebooks

Og.GetBiadjacency

igraph 1.0

igraph_get_biadjacency

See also

biadjacency, weighted_biadjacency

Vertex and edge counts of the two one-mode projections, without building them.

og_error_t og_bipartite_projection_size(
    const og_t *graph,
    const og_vector_bool_t *types,
    og_int_t *vcount1,
    og_int_t *ecount1,
    og_int_t *vcount2,
    og_int_t *ecount2
);

The projection onto one kind joins two vertices of that kind when they share a neighbour (Borgatti and Everett 1997); each joined pair counts once. vcount1 and ecount1 describe the projection onto the type-false vertices, vcount2 and ecount2 the one onto the type-true vertices; each output may be NULL.

Parameters

• graph The input graph.
• types The kind of every vertex.
• vcount1 Output (may be NULL): vertices of the first projection.
• ecount1 Output (may be NULL): edges of the first projection.
• vcount2 Output (may be NULL): vertices of the second projection.
• ecount2 Output (may be NULL): edges of the second projection.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL types does not have one entry per vertex, or an edge joins two vertices of the same kind.
• OG_ENOMEM Memory runs out.

Complexity

O(sum over the vertices of degree squared).

Checked

220 random bipartite graphs against python-igraph's bipartite_projection_size; error codes as python-igraph's.

C name

og_bipartite_projection_size

In notebooks

Og.BipartiteProjectionSize

igraph 1.0

igraph_bipartite_projection_size

See also

bipartite_projection

The two one-mode projections of a bipartite graph.

og_error_t og_bipartite_projection(
    const og_t *graph,
    const og_vector_bool_t *types,
    og_t *proj1,
    og_t *proj2,
    og_vector_int_t *multiplicity1,
    og_vector_int_t *multiplicity2,
    og_int_t probe1
);

Each projection is an undirected simple graph with one vertex per vertex of its kind, in increasing original id, and an edge between two vertices that share at least one neighbour. Edges are listed by their smaller vertex, partners in the order first met. multiplicity1 and multiplicity2 give, per projected edge, the number of shared neighbours.

proj1 is the projection onto the type-false vertices, proj2 onto the type-true ones. With probe1 >= 0, proj1 is instead the projection onto the kind of vertex probe1; a negative probe1 keeps the default. Each projection keeps the graph attributes and those of its own vertices.

Parameters

• graph The input graph.
• types The kind of every vertex.
• proj1 Output (may be NULL): an uninitialised og_t. The function creates the result graph; free it with destroy.
• proj2 Output (may be NULL): an uninitialised og_t. The function creates the result graph; free it with destroy.
• multiplicity1 Output (may be NULL): shared-neighbour count of every edge of proj1.
• multiplicity2 Output (may be NULL): shared-neighbour count of every edge of proj2.
• probe1 A vertex whose kind proj1 should hold, or a negative number for the default.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL types does not have one entry per vertex, or an edge joins two vertices of the same kind.
• OG_EINVAL probe1 is not a vertex of the graph, or probe1 is given while proj1 is NULL.
• OG_ENOMEM Memory runs out.

Complexity

O(sum over the vertices of degree squared).

Checked

220 random bipartite graphs against python-igraph's bipartite_projection: both projections' edges in order and their multiplicities identical; attributes as python-igraph keeps them (120 cases).

C name

og_bipartite_projection

In notebooks

Og.BipartiteProjection

igraph 1.0

igraph_bipartite_projection

See also

bipartite_projection_size, is_bipartite

Tests whether the vertices split into two kinds with every edge between the kinds, and returns such a split.

og_error_t og_is_bipartite(
    const og_t *graph,
    og_bool_t *res,
    og_vector_bool_t *types
);

Each connected component is two-coloured by breadth-first search, edge directions ignored. An odd cycle or a self-loop makes the graph non-bipartite. When it is bipartite, types receives the colouring, with the lowest vertex of each component on the false side. The null graph is bipartite.

Parameters

• graph The input graph.
• res Output (may be NULL): true when the graph is bipartite.
• types Output (may be NULL): the kind of every vertex; only written when the graph is bipartite.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

Result and colouring identical to python-igraph's is_bipartite(return_types=True) on 440 graphs (220 random, and the same with one extra edge).

C name

og_is_bipartite

In notebooks

Og.IsBipartite

igraph 1.0

igraph_is_bipartite

See also

is_bipartite_coloring, bipartite_projection, create_bipartite

og_t g;
og_bool_t bip;
og_vector_bool_t types;

og_ring(&g, 6, OG_UNDIRECTED, false, true);   /* an even cycle */
og_vector_bool_init(&types, 0);
og_is_bipartite(&g, &bip, &types);
/* bip is true; types false true false true false true */
og_vector_bool_destroy(&types);
og_destroy(&g);

Puts two graphs side by side in one graph.

og_error_t og_disjoint_union(
    og_t *res,
    const og_t *left,
    const og_t *right
);

The result has the vertices of left with their ids, then those of right with ids shifted by left's vertex count; the edges of left come first, then those of right, each in their original order. Both graphs must be directed or both undirected. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• left The first graph.
• right The second graph.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|) of both graphs together.

Checked

240 random cases against python-igraph's disjoint_union (null graph, single vertex, isolated vertices, loops, multi-edges, both directednesses).

C name

og_disjoint_union

In notebooks

Og.DisjointUnion

igraph 1.0

igraph_disjoint_union

See also

disjoint_union_many, join, union

Puts any number of graphs side by side in one graph.

og_error_t og_disjoint_union_many(og_t *res, const og_vector_ptr_t *graphs);

As disjoint_union for a vector of graph pointers: each graph's vertex ids are shifted by the vertex counts of the graphs before it, and the edges follow graph by graph. An empty vector gives the directed null graph. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• graphs Vector of pointers to the graphs (const og_t *).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|) of all graphs together.

Checked

The same 240 cases with 2-4 operands against python-igraph's disjoint_union.

C name

og_disjoint_union_many

In notebooks

Og.DisjointUnionMany

igraph 1.0

igraph_disjoint_union_many

See also

disjoint_union, union_many

Disjoint union of two graphs plus every edge between them.

og_error_t og_join(og_t *res, const og_t *left, const og_t *right);

The join (Harary 1969) is the disjoint union with every vertex of left joined to every vertex of right; in a directed graph both directions are added. The new edges come after the original ones, grouped by left vertex, right vertices in increasing order (directed: u -> v, then v -> u). Both graphs must be directed or both undirected. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• left The first graph.
• right The second graph.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(|V1| + |V2| + |E1| + |E2| + |V1| |V2|).

Checked

python-igraph has no join: checked against the definition (numbering, edge counts, directions, empty operands). The order of the added edges is Open Graph's reading of the definition and was not compared with igraph.

C name

og_join

In notebooks

Og.Join

igraph 1.0

igraph_join

See also

disjoint_union, full_bipartite

Union of two graphs on shared vertex ids.

og_error_t og_union(
    og_t *res,
    const og_t *left,
    const og_t *right,
    og_vector_int_t *edge_map1,
    og_vector_int_t *edge_map2
);

Vertices with the same id are the same vertex, so the result has as many vertices as the larger graph. An edge (u, v) appears as often as in the operand that has it most often; in undirected graphs (u, v) and (v, u) are the same edge. Result edges are listed in decreasing (from, to) order. edge_map1 and edge_map2 give, for every edge of left and of right, the id of the result edge it became; among parallel edges the pairing is the one igraph reports. Both graphs must be directed or both undirected. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• left The first graph.
• right The second graph.
• edge_map1 Output (may be NULL): result edge id of every edge of left.
• edge_map2 Output (may be NULL): result edge id of every edge of right.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|) when no operand has parallel edges; O(|E| log |E|) for an operand that has them (it is sorted by comparisons).

Checked

240 random cases with shared edges, multi-edges and loops against python-igraph's union: edge order and both edge maps identical. 7.2 ms against python-igraph's 8.2 ms on 2 x 50k directed edges.

C name

og_union

In notebooks

Og.Union

igraph 1.0

igraph_union

See also

union_many, intersection, disjoint_union, difference

og_t a, b, u;
og_vector_int_t map1, map2;

og_small(&a, 3, OG_UNDIRECTED, 0,1, 1,2, -1);
og_small(&b, 4, OG_UNDIRECTED, 1,2, 2,3, -1);
og_vector_int_init(&map1, 0);
og_vector_int_init(&map2, 0);
og_union(&u, &a, &b, &map1, &map2);
/* u: 4 vertices, edges 2-3, 1-2, 0-1 (in that order); map1 2 1; map2 1 0 */
og_vector_int_destroy(&map2);
og_vector_int_destroy(&map1);
og_destroy(&u);
og_destroy(&b);
og_destroy(&a);

Union of any number of graphs on shared vertex ids.

og_error_t og_union_many(
    og_t *res,
    const og_vector_ptr_t *graphs,
    og_vector_int_list_t *edgemaps
);

As union for a vector of graph pointers: the result has as many vertices as the largest graph, and every edge its largest multiplicity over the graphs. edgemaps receives one vector per graph, mapping its edges to result edge ids. With more than two graphs the merge uses a heap, O(|E| log k) for k graphs. An empty vector gives the directed null graph. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• graphs Vector of pointers to the graphs (const og_t *).
• edgemaps Output (may be NULL): one edge map per graph; resized to the number of graphs.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E| log k) for k graphs without parallel edges; graphs with parallel edges are sorted first.

Checked

As union with 2-4 operands, and 3 to 150 operands with edge maps in the independent check.

C name

og_union_many

In notebooks

Og.UnionMany

igraph 1.0

igraph_union_many

See also

union, intersection_many

Intersection of two graphs on shared vertex ids.

og_error_t og_intersection(
    og_t *res,
    const og_t *left,
    const og_t *right,
    og_vector_int_t *edge_map1,
    og_vector_int_t *edge_map2
);

An edge (u, v) is kept as often as the operand that has it least often; the result has as many vertices as the larger graph. Edges are listed in decreasing (from, to) order. edge_map1 and edge_map2 give, for every edge of left and of right, the result edge it became, or -1 when it is not in the intersection. Both graphs must be directed or both undirected. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• left The first graph.
• right The second graph.
• edge_map1 Output (may be NULL): result edge id of every edge of left, -1 if dropped.
• edge_map2 Output (may be NULL): result edge id of every edge of right, -1 if dropped.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ENOMEM Memory runs out.

Complexity

As union.

Checked

240 random cases against python-igraph's intersection: edges in order and edge maps identical.

C name

og_intersection

In notebooks

Og.Intersection

igraph 1.0

igraph_intersection

See also

intersection_many, union, difference

Intersection of any number of graphs on shared vertex ids.

og_error_t og_intersection_many(
    og_t *res,
    const og_vector_ptr_t *graphs,
    og_vector_int_list_t *edgemaps
);

As intersection for a vector of graph pointers: every edge is kept with its smallest multiplicity over the graphs, and edgemaps gives one map per graph (-1 for edges not kept). With more than two graphs the merge uses a heap. An empty vector gives the directed null graph. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• graphs Vector of pointers to the graphs (const og_t *).
• edgemaps Output (may be NULL): one edge map per graph; resized to the number of graphs.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ENOMEM Memory runs out.

Complexity

As union_many.

Checked

As intersection with 2-4 operands, and 3 to 150 operands with edge maps in the independent check.

C name

og_intersection_many

In notebooks

Og.IntersectionMany

igraph 1.0

igraph_intersection_many

See also

intersection, union_many

Edges of one graph that are not in another, on shared vertex ids.

og_error_t og_difference(og_t *res, const og_t *orig, const og_t *sub);

The result has the vertices of orig. Each edge of sub removes one matching copy from orig, so parallel edges subtract by count; vertices of sub beyond orig's count play no role. The treatment of undirected self-loops and the order of the kept edges reproduce igraph's. The result keeps the graph and vertex attributes of orig, and every kept edge the attributes of the orig edge it comes from. Both graphs must be directed or both undirected.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• orig The graph to subtract from.
• sub The graph whose edges are removed.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|) of both graphs together.

Checked

240 random cases against python-igraph's difference (edge order, multi-edges, loops) and 220 attribute cases through a recording handler.

C name

og_difference

In notebooks

Og.Difference

igraph 1.0

igraph_difference

See also

complementer, intersection

Complement graph: the vertex pairs that are not joined.

og_error_t og_complementer(og_t *res, const og_t *graph, og_bool_t loops);

The result has the same vertices and an edge for every pair (ordered pair in a directed graph) that is not an edge of graph. With loops = true a vertex without a self-loop gets one. For every vertex the new edges are listed from the largest partner down. On a multigraph each extra copy of an edge also hides the next smaller partner, which is what igraph does. The graph and vertex attributes are kept.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• graph The input graph.
• loops true: add self-loops where the graph has none.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ERANGE The complement would have more edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(|V|^2).

Checked

240 graphs up to 60 vertices, with and without loops, against python-igraph's complementer: edge order identical, multi-edge behaviour included; attributes as python-igraph keeps them.

C name

og_complementer

In notebooks

Og.Complementer

igraph 1.0

igraph_complementer

See also

difference

Subgraph made of the selected vertices and every edge between them.

og_error_t og_induced_subgraph(
    const og_t *graph,
    og_t *res,
    const og_vs_t vids,
    og_subgraph_implementation_t impl
);

The kept vertices are renumbered 0, 1, ... in increasing original id; repeated ids count once. Attributes of the graph, of the kept vertices and of the kept edges are carried over.

impl chooses the method. OG_SUBGRAPH_COPY_AND_DELETE copies the graph and deletes the other vertices, keeping the surviving edges in their original order. OG_SUBGRAPH_CREATE_FROM_SCRATCH builds a new graph, listing for every kept vertex its kept edges in adjacency order. OG_SUBGRAPH_AUTO takes COPY_AND_DELETE when the selector names more than half as many vertices as the graph has, otherwise CREATE_FROM_SCRATCH. Both orders equal igraph's.

Parameters

• graph The input graph.
• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• vids Vertex selector with the vertices to keep.
• impl OG_SUBGRAPH_AUTO, OG_SUBGRAPH_COPY_AND_DELETE or OG_SUBGRAPH_CREATE_FROM_SCRATCH.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID vids names a vertex that is not in the graph.
• OG_EINVAL impl is not a known value.
• OG_ENOMEM Memory runs out.

Complexity

COPY_AND_DELETE: O(|V| + |E|). CREATE_FROM_SCRATCH: O(|V| + the degrees of the kept vertices).

Checked

240 random graphs against python-igraph's induced_subgraph for all three methods: edge order and the source of every result edge identical. One deliberate difference: with an even number of self-loops at a vertex, CREATE_FROM_SCRATCH maps each loop's attributes once where igraph maps one twice and another not at all.

C name

og_induced_subgraph

In notebooks

Og.InducedSubgraph

igraph 1.0

igraph_induced_subgraph

See also

induced_subgraph_map, induced_subgraph_edges, subgraph_from_edges, subgraph_implementation_t

og_t g, sub;
og_vector_int_t keep;

og_ring(&g, 6, OG_UNDIRECTED, false, true);   /* the cycle 0-1-2-3-4-5-0 */
og_vector_int_init_int(&keep, 3, 0, 1, 2);
og_induced_subgraph(&g, &sub, og_vss_vector(&keep), OG_SUBGRAPH_AUTO);
/* sub: 3 vertices, edges 0-1 and 1-2 */
og_vector_int_destroy(&keep);
og_destroy(&sub);
og_destroy(&g);

Induced subgraph, also returning how vertex ids map between the graph and the result.

og_error_t og_induced_subgraph_map(
    const og_t *graph,
    og_t *res,
    const og_vs_t vids,
    og_subgraph_implementation_t impl,
    og_vector_int_t *map,
    og_vector_int_t *invmap
);

Builds the same subgraph as induced_subgraph. map has one entry per vertex of graph: its id in the result, or -1 when it was not kept. invmap has one entry per vertex of the result: its original id. Either may be NULL.

Parameters

• graph The input graph.
• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• vids Vertex selector with the vertices to keep.
• impl OG_SUBGRAPH_AUTO, OG_SUBGRAPH_COPY_AND_DELETE or OG_SUBGRAPH_CREATE_FROM_SCRATCH.
• map Output (may be NULL): result id of every original vertex, -1 if dropped.
• invmap Output (may be NULL): original id of every result vertex.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID vids names a vertex that is not in the graph.
• OG_EINVAL impl is not a known value.
• OG_ENOMEM Memory runs out.

Complexity

As induced_subgraph.

Checked

The same 240 cases as induced_subgraph, with map and invmap checked for every method.

C name

og_induced_subgraph_map

In notebooks

Og.InducedSubgraphMap

igraph 1.0

igraph_induced_subgraph_map

See also

induced_subgraph

Ids of the edges whose two endpoints are both selected.

og_error_t og_induced_subgraph_edges(
    const og_t *graph,
    og_vs_t vids,
    og_vector_int_t *edges
);

Lists, in increasing order, every edge with both ends among the selected vertices; self-loops at a selected vertex count. Repeated ids in the selector count once. No graph is built.

Parameters

• graph The input graph.
• vids Vertex selector.
• edges Output: the edge ids, increasing; cleared first.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVVID vids names a vertex that is not in the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(k log k + d log k), k the number of selected vertices and d the sum of their degrees.

Checked

240 random selections: the edge ids python-igraph's induced subgraph keeps, increasing.

C name

og_induced_subgraph_edges

In notebooks

Og.InducedSubgraphEdges

igraph 1.0

igraph_induced_subgraph_edges

See also

induced_subgraph, subgraph_from_edges

Subgraph made of the selected edges.

og_error_t og_subgraph_from_edges(
    const og_t *graph,
    og_t *res,
    const og_es_t eids,
    og_bool_t delete_vertices
);

Keeps the selected edges in their original order. With delete_vertices = true, vertices not touched by any selected edge are removed and the rest renumbered in increasing order; with false all vertices stay. Attributes of the graph and of the kept vertices and edges are carried over. Repeated edge ids count once.

Parameters

• graph The input graph.
• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• eids Edge selector with the edges to keep.
• delete_vertices Remove the vertices no kept edge touches.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVEID eids names an edge that is not in the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|).

Checked

240 random edge selections (with repeats) for both values of delete_vertices against python-igraph's subgraph_edges, edge order identical.

C name

og_subgraph_from_edges

In notebooks

Og.SubgraphFromEdges

igraph 1.0

igraph_subgraph_from_edges

See also

induced_subgraph, induced_subgraph_edges

Relational composition of two graphs.

og_error_t og_compose(
    og_t *res,
    const og_t *g1,
    const og_t *g2,
    og_vector_int_t *edge_map1,
    og_vector_int_t *edge_map2
);

For every edge i -> k of g1 and every edge k -> j of g2 the result gets one edge i -> j, so parallel edges and loops multiply. In undirected graphs each edge can be walked either way. The result has the larger vertex count of the two. edge_map1 and edge_map2 give, for every result edge, the g1 edge and the g2 edge it came from. Both graphs must be directed or both undirected. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• g1 The first graph (edges i -> k).
• g2 The second graph (edges k -> j).
• edge_map1 Output (may be NULL): the g1 edge of every result edge.
• edge_map2 Output (may be NULL): the g2 edge of every result edge.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_ENOMEM Memory runs out.

Complexity

O(|V1| + |V2| + |E1| + size of the result).

Checked

240 random cases against python-igraph's compose, edge order identical; the edge maps are checked by hand (python-igraph does not return them).

C name

og_compose

In notebooks

Og.Compose

igraph 1.0

igraph_compose

See also

graph_power, product

Joins every vertex to all vertices within a given distance, in place.

og_error_t og_connect_neighborhood(
    og_t *graph,
    og_int_t order,
    og_neimode_t mode
);

For each vertex i in increasing order a breadth-first search (neighbours in increasing id) finds the vertices within order steps; i gets a new edge to each one at distance 2 or more, in the order found. Undirected graphs, and OG_ALL, add each pair once, from the smaller id. OG_OUT follows edges forward and adds i -> j; OG_IN follows them backward and also adds i -> j. An order below 2 changes nothing (with a warning). Existing edges stay as they are.

Parameters

• graph The graph to change in place.
• order Largest distance to connect.
• mode OG_OUT, OG_IN or OG_ALL; undirected graphs always use OG_ALL.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL.
• OG_EINVAL order is negative.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| (|V| + |E|)) in the worst case: one breadth-first search of depth order per vertex.

Checked

Edge order identical to python-igraph's Lattice(nei=2,3) on 48 lattices, which add their edges through this function; 220 random graphs for orders 0-3 and every mode as edge sets. The direction of the edges added with OG_IN has no oracle and is not tested against igraph.

C name

og_connect_neighborhood

In notebooks

Og.ConnectNeighborhood

igraph 1.0

igraph_connect_neighborhood

See also

graph_power

Merges vertices according to a mapping, in place.

og_error_t og_contract_vertices(
    og_t *graph,
    const og_vector_int_t *mapping,
    const og_attribute_combination_t *vertex_comb
);

mapping[v] is the new id of vertex v; vertices with the same new id become one. The graph ends with (largest new id + 1) vertices, and every edge keeps its id with its endpoints renamed, so loops and parallel edges can appear. Graph and edge attributes are kept. With vertex_comb the vertex attributes of each merged group are combined (original ids in increasing order); with NULL they are dropped. The new structure is built aside and swapped in only when complete, so a failure leaves the graph unchanged.

Parameters

• graph The graph to change in place.
• mapping New id of every vertex.
• vertex_comb How to combine vertex attributes (may be NULL: drop them).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL mapping does not have one entry per vertex.
• OG_EINVVID mapping holds a negative id or one that is too large.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|), plus the attribute combination.

Checked

Structure identical to python-igraph's contract_vertices on 240 cases; attribute combination checked against python-igraph on 210 cases with the attributes area's handler.

C name

og_contract_vertices

In notebooks

Og.ContractVertices

igraph 1.0

igraph_contract_vertices

See also

simplify, induced_subgraph

Graph power: joins every pair of vertices at most k steps apart.

og_error_t og_graph_power(
    const og_t *graph,
    og_t *res,
    og_int_t order,
    og_bool_t directed
);

The result has the same vertices. Its edges are first one edge per adjacent pair, without loops or duplicates, in increasing (from, to) order, then the pairs at distance 2 to order, found as in connect_neighborhood. With directed = true on a directed graph distances follow the edge directions and the result is directed; otherwise it is undirected. order 0 gives no edges. The graph and vertex attributes are kept, the edge attributes are not.

Parameters

• graph The input graph.
• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• order The power k (not negative).
• directed Directed graphs: keep directions (true) or ignore them (false).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL order is negative.
• OG_ENOMEM Memory runs out.

Complexity

O(|V| (|V| + |E|)) in the worst case: one bounded breadth-first search per vertex.

Checked

220 random graphs for orders 0-3, both values of directed, as edge sets against python-igraph's neighborhood() (python-igraph has no graph power); the edge order is Open Graph's own.

C name

og_graph_power

In notebooks

Og.GraphPower

igraph 1.0

igraph_graph_power

See also

connect_neighborhood, compose

Cartesian, lexicographic, strong, tensor or modular product of two graphs.

og_error_t og_product(
    og_t *res,
    const og_t *g1,
    const og_t *g2,
    og_product_t type
);

Vertex (u, v) of the product, u from g1 and v from g2, gets id u |V2| + v. Two product vertices are joined following the definitions in Hammack, Imrich and Klavžar (2011):
Cartesian: u = u' and v ~ v', or u ~ u' and v = v'. Lexicographic: u ~ u', or u = u' and v ~ v'. Strong: the Cartesian edges plus the tensor edges. Tensor: u ~ u' and v ~ v'. Modular: the tensor edges plus the pairs non-adjacent in both graphs (u != u', v != v').

The definitions are applied edge by edge, so parallel edges and loops of the operands carry over. The modular product needs simple graphs. Both graphs must be directed or both undirected. The edge order is Open Graph's own and was not compared with igraph. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• g1 The first graph.
• g2 The second graph.
• type The product (product_t).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_EINVAL type is unknown, or the modular product gets a graph with loops or parallel edges.
• OG_ERANGE The product would have more vertices than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(|V1| |V2| + size of the result); the modular product O(|V1|^2 |V2|^2) for the complement part.

Checked

python-igraph has no product: 220 pairs of simple graphs as edge sets against networkx (BSD, used as a black box) for all five types; directed modular products and multigraph operands checked against the edge-count formulas. Edge order not compared.

C name

og_product

In notebooks

Og.Product

igraph 1.0

igraph_product

See also

product_t, rooted_product

Rooted product: a copy of g2 hung on every vertex of g1 by its root.

og_error_t og_rooted_product(
    og_t *res,
    const og_t *g1,
    const og_t *g2,
    og_int_t root
);

Vertex (u, v), u from g1 and v from g2, gets id u |V2| + v. For every vertex u of g1 the result holds a copy of g2 on the vertices (u, *); then every edge (a, b) of g1 joins the root copies (a, root) and (b, root) (Godsil and McKay 1978). Both graphs must be directed or both undirected. The edge order is Open Graph's own: the copies of g2 first, then g1's edges. Attributes are not carried over.

Parameters

• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• g1 The graph whose vertices carry the copies.
• g2 The graph that is copied.
• root The vertex of g2 used to attach each copy.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL The operands are not all directed or all undirected.
• OG_EINVVID root is not a vertex of g2.
• OG_ERANGE The product would have more vertices than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(|V1| |V2| + |V1| |E2| + |E1|).

Checked

Undirected cases as edge sets against networkx's rooted_product (220 pairs, random roots); directed and multigraph operands by the edge count |V1| |E2| + |E1|. Edge order not compared.

C name

og_rooted_product

In notebooks

Og.RootedProduct

igraph 1.0

igraph_rooted_product

See also

product

Line graph: one vertex per edge, joined when the edges meet.

og_error_t og_linegraph(const og_t *graph, og_t *linegraph);

Vertex i of the result is edge i of the graph. Directed graphs (Harary and Norman 1960): an edge j -> i for every edge j that ends where edge i starts; a self-loop thus gets one loop. Undirected graphs: two edges are joined once for every endpoint they share (a self-loop has two), so edges sharing both ends are joined twice, and every self-loop also gets one loop of its own. Edge order equals igraph's. Attributes are not carried over.

Parameters

• graph The input graph.
• linegraph Output: an uninitialised og_t. The function creates the result graph; free it with destroy.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E| + size of the result); the result has about the sum of the squared degrees in edges.

Checked

240 random graphs (loops, multi-edges, both directednesses) against python-igraph's linegraph, edge order identical.

C name

og_linegraph

In notebooks

Og.Linegraph

igraph 1.0

igraph_linegraph

See also

induced_subgraph_edges

Applies the Mycielski construction k times.

og_error_t og_mycielskian(const og_t *graph, og_t *res, og_int_t k);

One step on a graph with n vertices v_0 .. v_(n-1) adds a shadow u_i = n + i for every vertex and a hub w = 2n. Edges: the original ones, then for every edge (v_a, v_b) the edges (v_a, u_b) and (u_a, v_b), then (u_i, w) for every i. Each step raises the chromatic number by one and keeps a triangle-free graph triangle-free (Mycielski 1955). Special cases: the null graph becomes one vertex, a single vertex becomes one edge. The size is checked before anything is built. Directed graphs follow the same rules. Attributes are not carried over.

Parameters

• graph The input graph.
• res Output: an uninitialised og_t. The function creates the result graph; free it with destroy.
• k Number of steps (not negative); 0 copies the graph.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVAL k is negative.
• OG_ERANGE The result would have more vertices or edges than Open Graph supports.
• OG_ENOMEM Memory runs out.

Complexity

O(size of the result): each step maps n vertices and m edges to 2n + 1 vertices and 3m + n edges.

Checked

python-igraph has no Mycielskian: 220 simple undirected graphs for 0-2 steps as edge sets against networkx's mycielskian, and the Mycielski graphs from the null graph against networkx's mycielski_graph(1..5); edge order as igraph lists its Mycielski graphs (up to order 6).

C name

og_mycielskian

In notebooks

Og.Mycielskian

igraph 1.0

igraph_mycielskian

See also

vertex_coloring_greedy, clique_number

Removes parallel edges, self-loops or both, in place.

og_error_t og_simplify(
    og_t *graph,
    og_bool_t remove_multiple,
    og_bool_t remove_loops,
    const og_attribute_combination_t *edge_comb
);

With remove_multiple the graph keeps one edge per (from, to) pair, listed in increasing (from, to) order (undirected: smaller end first). With remove_loops self-loops go. When only loops are removed the other edges keep their order and ids shift down. If the graph is already known to have no parallel edges (or no loops) it is not touched for them.

Graph and vertex attributes are kept. With edge_comb the attributes of merged edges are combined (the merged edges in increasing id); with NULL edge attributes are dropped when parallel edges are merged, and kept when only loops go. The new structure is built aside and swapped in only when complete, so a failure leaves the graph unchanged.

Parameters

• graph The graph to change in place.
• remove_multiple Merge parallel edges into one.
• remove_loops Delete self-loops.
• edge_comb How to combine the attributes of merged edges (may be NULL).

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_ENOMEM Memory runs out.

Complexity

O(|V| + |E|), plus the attribute combination.

Checked

240 random graphs for every flag combination plus heavy multigraphs against python-igraph's simplify: edge order and the ids merged into each edge identical; attribute combination checked against python-igraph on 210 cases.

C name

og_simplify

In notebooks

Og.Simplify

igraph 1.0

igraph_simplify

See also

contract_vertices

og_t g;

og_small(&g, 3, OG_UNDIRECTED, 0,1, 1,0, 1,1, 1,2, -1);
og_simplify(&g, true, true, NULL);   /* merge parallel edges, drop loops */
/* g now has the edges 0-1 and 1-2 */
og_destroy(&g);

Reverses the direction of the selected edges, in place.

og_error_t og_reverse_edges(og_t *graph, const og_es_t eids);

Each occurrence of an edge in the selector reverses it once, so an edge listed twice ends as it was. Edge ids and all attributes stay. Undirected graphs are left unchanged. Selecting all edges takes a constant-time path: the stored tail and head columns and the in- and out-adjacency tables trade places. Otherwise the new structure is built aside and swapped in only when complete, so a failure leaves the graph unchanged.

Parameters

• graph The graph to change in place.
• eids Edge selector with the edges to reverse.

Returns

OG_SUCCESS, or the error code of the failure (see errors).

Errors

• OG_EINVEID eids names an edge that is not in the graph.
• OG_ENOMEM Memory runs out.

Complexity

O(1) for all edges; O(|V| + |E|) otherwise.

Checked

240 random graphs with random edge lists against python-igraph's reverse_edges; the all-edges path checked equal to reversing the explicit list of every edge.

C name

og_reverse_edges

In notebooks

Og.ReverseEdges

igraph 1.0

igraph_reverse_edges

See also

simplify