Isomorphism

Whether two graphs are the same up to relabelling, subgraph isomorphism, automorphisms and canonical labellings, and the isomorphism classes of small graphs.

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

Types

`bliss_sh_t`type#

Unit tests

How the canonical labelling search chooses the cell to split at each search node.

typedef enum og_bliss_sh_t {
    OG_BLISS_F = 0,   /* first non-singleton cell */
    OG_BLISS_FL,      /* first largest non-singleton cell */
    OG_BLISS_FS,      /* first smallest non-singleton cell */
    OG_BLISS_FM,      /* first cell with the most non-trivial connections */
    OG_BLISS_FLM,     /* largest cell among those with the most non-trivial connections */
    OG_BLISS_FSM      /* smallest cell among those with the most non-trivial connections */
} og_bliss_sh_t;

At each search node the engine picks one cell of the partition that still holds several vertices and tries its vertices one by one. The choice affects the running time and which canonical form is found, never the group or the isomorphism answer. F takes the first such cell, FL the first largest, FS the first smallest; FM, FLM and FSM first keep only the cells with the most non-trivial connections to other cells and then take the first, the largest or the smallest of those. The simple interface uses OG_BLISS_FL. The _bliss names are kept so code written for igraph ports by renaming; the engine behind them is not BLISS.

Parameters

OG_BLISS_F 0: first non-singleton cell.
OG_BLISS_FL 1: first largest non-singleton cell.
OG_BLISS_FS 2: first smallest non-singleton cell.
OG_BLISS_FM 3: first cell with the most non-trivial connections.
OG_BLISS_FLM 4: largest cell among those with the most non-trivial connections.
OG_BLISS_FSM 5: smallest cell among those with the most non-trivial connections.

Checked

Same names and values as igraph 1.0; all six heuristics give python-igraph's group orders; an out-of-range value is OG_EINVAL.

C name

og_bliss_sh_t

In notebooks

Og.BlissSh

igraph 1.0

igraph_bliss_sh_t

`bliss_info_t`type#

Unit tests

Statistics of one canonical labelling run, with the exact order of the automorphism group.

typedef struct og_bliss_info_t {
    unsigned long nof_nodes;       /* search tree nodes visited */
    unsigned long nof_leaf_nodes;  /* leaves (discrete or fully symmetric partitions) reached */
    unsigned long nof_bad_nodes;   /* nodes cut off by their refinement invariant */
    unsigned long nof_canupdates;  /* times the canonical candidate improved */
    unsigned long nof_generators;  /* automorphism group generators found */
    unsigned long max_level;       /* deepest search level */
    char *group_size;              /* |Aut|, decimal; og_free() it */
} og_bliss_info_t;

Filled by the _bliss functions when an info pointer is given. group_size is the exact number of automorphisms as a decimal string, allocated with malloc: release it with free (a later call does not release it). The counters describe Open Graph's search tree and cannot be compared with BLISS statistics; nof_generators equals the number of generators returned. The fields are zero (group_size NULL) when isomorphic_bliss rejects graphs of different sizes.

Parameters

nof_nodes Search tree nodes visited.
nof_leaf_nodes Leaves reached (discrete partitions, or nodes whose remaining cells are fully symmetric).
nof_bad_nodes Nodes cut off by their refinement invariant.
nof_canupdates Times the canonical candidate improved.
nof_generators Automorphism group generators found.
max_level Deepest search level.
group_size Order of the automorphism group as a decimal string; free with free.

Checked

Same fields as igraph 1.0. group_size is exact; the counters describe our search tree, not BLISS's.

C name

og_bliss_info_t

In notebooks

Og.BlissInfo

igraph 1.0

igraph_bliss_info_t

`isohandler_t`type#

Unit tests

Type of the function called by the VF2 searches for every mapping found.

typedef og_error_t og_isohandler_t(
    const og_vector_int_t *map12,
    const og_vector_int_t *map21,
    void *arg
);

map12 and map21 hold the mapping just found, in the layout of the search's map12 and map21 arguments (for a subgraph search, map12 has -1 for unmatched vertices of graph1). They are valid only during the call. arg is the user pointer given to the search.

Parameters

map12 For every vertex of graph1, its partner in graph2 (or -1).
map21 For every vertex of graph2, its partner in graph1.
arg The search's arg.

Returns

OG_SUCCESS to continue, OG_STOP to end the search normally, any other code to end it with that error.

Checked

Same signature as igraph 1.0; OG_STOP ends the search normally, any other code is returned.

C name

og_isohandler_t

In notebooks

Og.Isohandler

igraph 1.0

igraph_isohandler_t

`isocompat_t`type#

Unit tests

Type of the compatibility tests the VF2 functions accept for vertex and edge pairs.

typedef og_bool_t og_isocompat_t(
    const og_t *graph1,
    const og_t *graph2,
    const og_int_t g1_num,
    const og_int_t g2_num,
    void *arg
);

As node_compat_fn, g1_num and g2_num are vertex ids of graph1 and graph2; as edge_compat_fn, they are edge ids. Return true when the two may be matched. The test is applied on top of the colours, if any. It should depend only on its arguments, since the search may ask about the same pair several times.

Parameters

graph1 The search's graph1.
graph2 The search's graph2.
g1_num Vertex or edge id in graph1.
g2_num Vertex or edge id in graph2.
arg The search's arg.

Returns

true when the pair may be matched.

Checked

Same signature as igraph 1.0; vertex and edge tests checked against runs with equivalent colours.

C name

og_isocompat_t

In notebooks

Og.Isocompat

igraph 1.0

igraph_isocompat_t

Isomorphism and automorphisms

`isomorphic`#

Exact

Decides whether two graphs are isomorphic, choosing the method itself.

og_error_t og_isomorphic(
    const og_t *graph1,
    const og_t *graph2,
    og_bool_t *iso
);

Two graphs are isomorphic when a one-to-one map of the vertices of graph1 onto those of graph2 takes the edges exactly onto the edges, directions and multiplicities included. The method is picked from the graphs: if either has parallel edges, both are reduced with simplify_and_colorize (self-loop counts become vertex colours, multiplicities edge colours) and compared with VF2; otherwise graphs of different vertex or edge counts are rejected at once; graphs without self-loops of 3 or 4 vertices (directed) or 3 to 6 vertices (undirected) are compared by isomorphism class; all others by canonical labelling (isomorphic_bliss with OG_BLISS_FL).

Only the answer is returned; isomorphic_vf2 and isomorphic_bliss also give a mapping. Self-loops and parallel edges are allowed.

Parameters

graph1 First graph.
graph2 Second graph; same directedness as graph1.
iso Receives true when the graphs are isomorphic; may be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|) for graphs of different sizes and for small graphs; otherwise that of canonical labelling or, for multigraphs, of VF2.

Checked

Equal to python-igraph on 600 random pairs (directed, undirected, self-loops, multigraphs, sizes 0-12 that also hit the small-graph path) plus 363 canonical-labelling pairs.

C name

og_isomorphic

In notebooks

Og.Isomorphic

igraph 1.0

igraph_isomorphic

og_t a, b;
og_bool_t iso;
og_ring(&a, 5, false, false, true);                        /* 0-1-2-3-4-0 */
og_small(&b, 5, false, 0, 2, 2, 4, 4, 1, 1, 3, 3, 0, -1);  /* the same cycle, relabelled */
og_isomorphic(&a, &b, &iso);                               /* iso == true */
og_destroy(&b);
og_destroy(&a);

`subisomorphic`#

Exact

Decides whether graph2 occurs as a subgraph of graph1.

og_error_t og_subisomorphic(
    const og_t *graph1,
    const og_t *graph2,
    og_bool_t *iso
);

A yes/no shortcut for subisomorphic_vf2 without colours or callbacks: graph1 is the larger graph, graph2 the pattern. The subgraph search looks for monomorphisms: graph2's vertices map one-to-one into graph1 so that every edge of graph2 lands on an edge of graph1 (same direction when directed); graph1 may have more edges between the matched vertices. Use subisomorphic_lad with induced = true when such extra edges must be excluded.

Parameters

graph1 The larger graph.
graph2 The pattern; same directedness as graph1.
iso Receives true when graph2 occurs in graph1; may be NULL.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case (subgraph isomorphism is NP-complete). Memory O(|V| + |E|).

Checked

Equal to python-igraph on 300 random pairs.

C name

og_subisomorphic

In notebooks

Og.Subisomorphic

igraph 1.0

igraph_subisomorphic

`count_automorphisms`#

Exact

Counts the automorphisms of a graph, optionally keeping vertex colours fixed.

og_error_t og_count_automorphisms(
    const og_t *graph,
    const og_vector_int_t *colors,
    og_real_t *result
);

An automorphism is a permutation of the vertices that maps the graph onto itself and, with colors, maps every vertex to one of the same colour. Their number is the order of the automorphism group. It is computed exactly, as a product of orbit sizes, by Open Graph's own canonical labelling engine (heuristic OG_BLISS_FL), and then converted to a real number, so very large orders are rounded to the nearest double. count_automorphisms_bliss gives the exact value as a decimal string.

Self-loops are allowed. Parallel edges are outside the method's domain: a graph that has them is answered for the graph with each group of parallel edges merged into one edge, as python-igraph does.

Parameters

graph The graph.
colors NULL, or one colour (any integer) per vertex; automorphisms then map every vertex to one of the same colour.
result Receives the number of automorphisms.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL colors does not have |V| entries.
OG_EOVERFLOW the number exceeds the largest double.
OG_ENOMEM Not enough memory.

Complexity

No polynomial bound is known for the worst case. Each search node costs about O((|V| + |E|) log |V|) for the refinement, and most graphs need few nodes; graphs made of many isomorphic parts are split into components first.

Checked

Equal to python-igraph within 1e-12 relative on 426 graphs (the order is computed exactly first); OG_EOVERFLOW tested.

C name

og_count_automorphisms

In notebooks

Og.CountAutomorphisms

igraph 1.0

igraph_count_automorphisms

`automorphism_group`#

Exact

Returns permutations that generate the automorphism group of a graph.

og_error_t og_automorphism_group(
    const og_t *graph,
    const og_vector_int_t *colors,
    og_vector_int_list_t *generators
);

generators is cleared and filled with permutations of length |V|, each one an automorphism: entry v is the vertex that v is mapped to. Together they generate the whole group (respecting colors when given); a graph with only the identity gives an empty list. The generating set is the one Open Graph's canonical labelling engine finds (heuristic OG_BLISS_FL). Any generating set describes the same group; this one is generally not the set igraph returns.

Self-loops are allowed. Parallel edges are outside the method's domain: a graph that has them is answered for the graph with each group of parallel edges merged into one edge, as python-igraph does.

Parameters

graph The graph.
colors NULL, or one colour (any integer) per vertex; automorphisms then map every vertex to one of the same colour.
generators Initialised list of integer vectors; receives the generators.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL colors does not have |V| entries.
OG_ENOMEM Not enough memory.

Complexity

Checked

The group is python-igraph's: every generator is checked to be an automorphism, the orbits match on 426 graphs and a Schreier-Sims check confirms the exact order for up to 64 vertices. The generators themselves are our own.

C name

og_automorphism_group

In notebooks

Og.AutomorphismGroup

igraph 1.0

igraph_automorphism_group

`canonical_permutation`#

Unit tests

Computes a canonical relabelling: isomorphic graphs relabelled this way become identical.

og_error_t og_canonical_permutation(
    const og_t *graph,
    const og_vector_int_t *colors,
    og_vector_int_t *labeling
);

labeling receives a permutation of the vertices: labeling[i] is the vertex that becomes vertex i, so permute_vertices(graph, &canon, labeling) gives the canonical form. Two graphs (with colours: two coloured graphs) are isomorphic exactly when their canonical forms have the same edges (compare the sorted edge lists) and, with colours, the same colour at every position. The canonical form is Open Graph's own: it is not the one igraph's BLISS produces, and it depends on the heuristic, so compare only forms made by Open Graph with the same heuristic. This function uses OG_BLISS_FL.

Self-loops are allowed. Parallel edges are outside the method's domain: a graph that has them is answered for the graph with each group of parallel edges merged into one edge, as python-igraph does.

Parameters

graph The graph.
colors NULL, or one colour (any integer) per vertex; automorphisms then map every vertex to one of the same colour.
labeling Initialised vector; receives the permutation (length |V|).

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL colors does not have |V| entries.
OG_ENOMEM Not enough memory.

Complexity

Checked

Our own canonical form, tested by its properties: identical forms for random relabellings of 426 graphs under every heuristic, and isomorphism decisions from canonical forms equal python-igraph's on 363 pairs.

C name

og_canonical_permutation

In notebooks

Og.CanonicalPermutation

igraph 1.0

igraph_canonical_permutation

og_vector_int_t lab;
og_t canon;
og_vector_int_init(&lab, 0);
og_canonical_permutation(&g, NULL, &lab);
og_permute_vertices(&g, &canon, &lab);   /* canon: g in canonical form */
og_destroy(&canon);
og_vector_int_destroy(&lab);

Canonical labelling

`isomorphic_bliss`#

Exact

Decides isomorphism by canonical labelling and returns a mapping when the graphs are isomorphic.

og_error_t og_isomorphic_bliss(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *colors1,
    const og_vector_int_t *colors2,
    og_bool_t *iso,
    og_vector_int_t *map12,
    og_vector_int_t *map21,
    og_bliss_sh_t sh,
    og_bliss_info_t *info1,
    og_bliss_info_t *info2
);

Both graphs are canonically labelled with heuristic sh. The map that pairs the two canonical orders position by position is then checked edge by edge (with colours, the colours at each position must also agree), which settles the question in linear time once both labellings are known. map12[i] is the vertex of graph2 matched with vertex i of graph1 and map21 is its inverse; both are emptied when the graphs are not isomorphic. Graphs of different vertex or edge counts are rejected at once.

Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are allowed. With parallel edges the answer is exact (multiplicities count), while the reference may answer false for some isomorphic multigraphs; info1 and info2 then describe the graphs with parallel edges merged, as the counting functions do.

Parameters

graph1 First graph.
graph2 Second graph; same directedness as graph1.
colors1 NULL, or one colour per vertex of graph1.
colors2 NULL, or one colour per vertex of graph2.
iso Receives true when the graphs are isomorphic; may be NULL.
map12 NULL, or an initialised vector: map12[i] is the vertex of graph2 matched with vertex i of graph1. Emptied when there is no match.
map21 NULL, or an initialised vector: map21[j] is the vertex of graph1 matched with vertex j of graph2. Emptied when there is no match.
sh Cell-selection heuristic of the search (bliss_sh_t).
info1 NULL, or a struct for the statistics of graph1; free its group_size with free.
info2 NULL, or a struct for the statistics of graph2; free its group_size with free.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; sh is out of range; a colour vector does not have its graph's vertex count.
OG_ENOMEM Not enough memory.

Complexity

Checked

Decision equal to python-igraph on 363 pairs (colours, self-loops, directed) for every heuristic, the maps checked to be isomorphisms; verifiers added hard families (CFI pairs, Paley, Chang graphs, Latin squares, generalised quadrangles, projective planes, Steiner triple systems) and about 7000 fuzzed graphs.

C name

og_isomorphic_bliss

In notebooks

Og.IsomorphicBliss

igraph 1.0

igraph_isomorphic_bliss

`count_automorphisms_bliss`#

Exact

Counts automorphisms exactly, with a chosen heuristic; the group order comes back as a decimal string.

og_error_t og_count_automorphisms_bliss(
    const og_t *graph,
    const og_vector_int_t *colors,
    og_bliss_sh_t sh,
    og_bliss_info_t *info
);

As count_automorphisms, with the heuristic sh, and the result is info->group_size: the exact order of the group as a decimal string with no size limit (1000 disjoint 5-cycles, for example, have 10^1000 x 1000! automorphisms). The other fields of info hold the search statistics. Free info->group_size with free.

Self-loops are allowed. Parallel edges are outside the method's domain: a graph that has them is answered for the graph with each group of parallel edges merged into one edge, as python-igraph does.

Parameters

graph The graph.
colors NULL, or one colour (any integer) per vertex; automorphisms then map every vertex to one of the same colour.
sh Cell-selection heuristic of the search (bliss_sh_t).
info Receives the group order and the statistics; free info->group_size with free. NULL computes and discards the result.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL sh is out of range; colors does not have |V| entries.
OG_ENOMEM Not enough memory.

Complexity

Checked

Exact order string equal to python-igraph's on 426 graphs for every heuristic, plus 1000 disjoint 5-cycles, hard graph families and about 7000 fuzzed graphs.

C name

og_count_automorphisms_bliss

In notebooks

Og.CountAutomorphismsBliss

igraph 1.0

igraph_count_automorphisms_bliss

`automorphism_group_bliss`#

Exact

Returns generators of the automorphism group, with a chosen heuristic and run statistics.

og_error_t og_automorphism_group_bliss(
    const og_t *graph,
    const og_vector_int_t *colors,
    og_vector_int_list_t *generators,
    og_bliss_sh_t sh,
    og_bliss_info_t *info
);

As automorphism_group, with the heuristic sh: generators receives permutations of length |V| (entry v is the image of v) that generate the group. The generating set depends on the heuristic and is Open Graph's own; the group it generates does not. info, when given, receives the statistics and the exact group order.

Self-loops are allowed. Parallel edges are outside the method's domain: a graph that has them is answered for the graph with each group of parallel edges merged into one edge, as python-igraph does.

Parameters

graph The graph.
colors NULL, or one colour (any integer) per vertex; automorphisms then map every vertex to one of the same colour.
generators Initialised list of integer vectors; receives the generators.
sh Cell-selection heuristic of the search (bliss_sh_t).
info NULL, or a struct that receives the search statistics and the exact group order; free info->group_size with free.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL sh is out of range; colors does not have |V| entries.
OG_ENOMEM Not enough memory.

Complexity

Checked

The generated group equals python-igraph's (orbits, Schreier-Sims order); the generator lists are our own.

C name

og_automorphism_group_bliss

In notebooks

Og.AutomorphismGroupBliss

igraph 1.0

igraph_automorphism_group_bliss

`canonical_permutation_bliss`#

Unit tests

Computes a canonical relabelling with a chosen heuristic and run statistics.

og_error_t og_canonical_permutation_bliss(
    const og_t *graph,
    const og_vector_int_t *colors,
    og_vector_int_t *labeling,
    og_bliss_sh_t sh,
    og_bliss_info_t *info
);

Self-loops are allowed. Parallel edges are outside the method's domain: a graph that has them is answered for the graph with each group of parallel edges merged into one edge, as python-igraph does.

Parameters

graph The graph.
colors NULL, or one colour (any integer) per vertex; automorphisms then map every vertex to one of the same colour.
labeling Initialised vector; receives the permutation (length |V|).
sh Cell-selection heuristic of the search (bliss_sh_t).
info NULL, or a struct that receives the search statistics and the exact group order; free info->group_size with free.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL sh is out of range; colors does not have |V| entries.
OG_ENOMEM Not enough memory.

Complexity

Checked

Our own canonical form, tested by its properties as canonical_permutation, for every heuristic and on the hard families.

C name

og_canonical_permutation_bliss

In notebooks

Og.CanonicalPermutationBliss

igraph 1.0

igraph_canonical_permutation_bliss

VF2

`isomorphic_vf2`#

Exact

Decides isomorphism with VF2, with optional vertex and edge colours and custom compatibility tests, and returns the first mapping.

og_error_t og_isomorphic_vf2(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_bool_t *iso,
    og_vector_int_t *map12,
    og_vector_int_t *map21,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

The first mapping found is returned in map12 and map21. Graphs of different vertex or edge counts are rejected at once. Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have equal degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 First graph.
graph2 Second graph; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
iso Receives true when a mapping exists; may be NULL.
map12 NULL, or an initialised vector: map12[i] is the vertex of graph2 matched with vertex i of graph1. Emptied when there is no match.
map21 NULL, or an initialised vector: map21[j] is the vertex of graph1 matched with vertex j of graph2. Emptied when there is no match.
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the callbacks.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case; fast on graphs without much symmetry. Memory O(|V| + |E|).

Checked

Decision and the first map12 / map21 equal python-igraph's on 274 cases (vertex and edge colours, directed and undirected), 180 multigraph pairs and 1800 more random pairs; compatibility callbacks tested.

C name

og_isomorphic_vf2

In notebooks

Og.IsomorphicVf2

igraph 1.0

igraph_isomorphic_vf2

`count_isomorphisms_vf2`#

Exact

Counts all isomorphisms between two graphs with VF2.

og_error_t og_count_isomorphisms_vf2(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_int_t *count,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

Runs the VF2 search of isomorphic_vf2 to the end and counts the mappings, with the same colours and compatibility callbacks. Passing the same graph twice counts its automorphisms (respecting the colours). Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have equal degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 First graph.
graph2 Second graph; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
count Receives the number of isomorphisms.
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the callbacks.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case, and at least proportional to the number of mappings found. Memory O(|V| + |E|) besides the output.

Checked

Counts equal python-igraph's on the cases the oracle could count.

C name

og_count_isomorphisms_vf2

In notebooks

Og.CountIsomorphismsVf2

igraph 1.0

igraph_count_isomorphisms_vf2

`get_isomorphisms_vf2`#

Exact

Lists every isomorphism between two graphs with VF2.

og_error_t og_get_isomorphisms_vf2(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_vector_int_list_t *maps,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

maps is cleared and receives one vector per isomorphism, in VF2's search order (python-igraph's order). Each vector is a map21: entry j is the vertex of graph1 matched with vertex j of graph2. Colours and callbacks work as in isomorphic_vf2. Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have equal degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 First graph.
graph2 Second graph; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
maps Initialised list of integer vectors; receives the mappings.
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the callbacks.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case, and at least proportional to the number of mappings found. Memory O(|V| + |E|) besides the output.

Checked

Every mapping, in python-igraph's order, on the test cases and 1800 more random pairs.

C name

og_get_isomorphisms_vf2

In notebooks

Og.GetIsomorphismsVf2

igraph 1.0

igraph_get_isomorphisms_vf2

`get_isomorphisms_vf2_callback`#

Exact

Runs the VF2 isomorphism search and calls a function for every mapping found.

og_error_t og_get_isomorphisms_vf2_callback(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_vector_int_t *map12,
    og_vector_int_t *map21,
    og_isohandler_t *isohandler_fn,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

isohandler_fn is called once per mapping found, in search order, with the current map12, map21 and arg. It returns OG_SUCCESS to go on, OG_STOP to end the search normally (the function then returns OG_SUCCESS), or any other code to end it with that error, which the function reports and returns. The vectors passed to the handler belong to the search: copy them to keep a mapping. The other isomorphism functions are built on this search. Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have equal degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 First graph.
graph2 Second graph; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
map12 NULL, or an initialised vector: map12[i] is the vertex of graph2 matched with vertex i of graph1. Emptied when there is no match.
map21 NULL, or an initialised vector: map21[j] is the vertex of graph1 matched with vertex j of graph2. Emptied when there is no match.
isohandler_fn Called for every mapping (isohandler_t).
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the handler and the callbacks.

Returns

OG_SUCCESS (also after OG_STOP from the handler), or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.
handler's code: the handler returned a code other than OG_SUCCESS or OG_STOP.

Complexity

Exponential in the worst case, and at least proportional to the number of mappings found. Memory O(|V| + |E|) besides the output.

Checked

The search behind the other isomorphism functions; stopping with OG_STOP and error propagation tested.

C name

og_get_isomorphisms_vf2_callback

In notebooks

Og.GetIsomorphismsVf2Callback

igraph 1.0

igraph_get_isomorphisms_vf2_callback

`subisomorphic_vf2`#

Exact

Decides with VF2 whether graph2 occurs as a subgraph of graph1, and returns the first match.

og_error_t og_subisomorphic_vf2(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_bool_t *iso,
    og_vector_int_t *map12,
    og_vector_int_t *map21,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

The subgraph search looks for monomorphisms: graph2's vertices map one-to-one into graph1 so that every edge of graph2 lands on an edge of graph1 (same direction when directed); graph1 may have more edges between the matched vertices. Use subisomorphic_lad with induced = true when such extra edges must be excluded.

VF2 (Cordella, Foggia, Sansone and Vento) grows a partial mapping one vertex pair at a time and backtracks, pruning candidates with look-ahead counts of the vertices next to the mapped part. A vertex pair is allowed only when the vertex colours agree and node_compat_fn (if given) accepts it; an edge pair only when the edge colours agree and edge_compat_fn (if given) accepts it. The search order is python-igraph's: the next graph2 vertex is the smallest unmatched one next to the mapped part (out-neighbours first, then in-neighbours), else the smallest unmatched one, and graph1 candidates are tried in increasing id. The first match found is returned in map12 and map21. When graph2 has more vertices or more edges than graph1 the answer is false at once. Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have at least the degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 The larger graph, searched for copies of graph2.
graph2 The pattern; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
iso Receives true when graph2 occurs in graph1; may be NULL.
map12 NULL, or an initialised vector of length |V(graph1)|: the vertex of graph2 matched with each vertex of graph1, -1 where none. Emptied when there is no match.
map21 NULL, or an initialised vector of length |V(graph2)|: the vertex of graph1 matched with each vertex of graph2. Emptied when there is no match.
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the callbacks.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case; fast on graphs without much symmetry. Memory O(|V| + |E|).

Checked

Decision and first maps equal python-igraph's on 273 subgraph cases, 200 multigraph pairs and 1800 more random pairs.

C name

og_subisomorphic_vf2

In notebooks

Og.SubisomorphicVf2

igraph 1.0

igraph_subisomorphic_vf2

`count_subisomorphisms_vf2`#

Exact

Counts the occurrences of graph2 as a subgraph of graph1 with VF2.

og_error_t og_count_subisomorphisms_vf2(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_int_t *count,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

Runs the subgraph search of subisomorphic_vf2 to the end and counts the matches. Every distinct mapping counts, so a pattern with automorphisms is counted once per automorphism at each place it occurs (a triangle in a triangle counts 6 times). The subgraph search looks for monomorphisms: graph2's vertices map one-to-one into graph1 so that every edge of graph2 lands on an edge of graph1 (same direction when directed); graph1 may have more edges between the matched vertices. Use subisomorphic_lad with induced = true when such extra edges must be excluded. Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have at least the degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 The larger graph, searched for copies of graph2.
graph2 The pattern; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
count Receives the number of matches.
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the callbacks.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case, and at least proportional to the number of mappings found. Memory O(|V| + |E|) besides the output.

Checked

Counts equal python-igraph's.

C name

og_count_subisomorphisms_vf2

In notebooks

Og.CountSubisomorphismsVf2

igraph 1.0

igraph_count_subisomorphisms_vf2

`get_subisomorphisms_vf2`#

Exact

Lists every occurrence of graph2 as a subgraph of graph1 with VF2.

og_error_t og_get_subisomorphisms_vf2(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_vector_int_list_t *maps,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

maps is cleared and receives one vector per match, in VF2's search order (python-igraph's order). Each vector is a map21: entry j is the vertex of graph1 matched with vertex j of graph2. The subgraph search looks for monomorphisms: graph2's vertices map one-to-one into graph1 so that every edge of graph2 lands on an edge of graph1 (same direction when directed); graph1 may have more edges between the matched vertices. Use subisomorphic_lad with induced = true when such extra edges must be excluded. Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have at least the degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 The larger graph, searched for copies of graph2.
graph2 The pattern; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
maps Initialised list of integer vectors; receives the matches.
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the callbacks.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case, and at least proportional to the number of mappings found. Memory O(|V| + |E|) besides the output.

Checked

Every match, in python-igraph's order, on the test cases and 1800 more random pairs.

C name

og_get_subisomorphisms_vf2

In notebooks

Og.GetSubisomorphismsVf2

igraph 1.0

igraph_get_subisomorphisms_vf2

og_t big, tri;
og_vector_int_list_t maps;
og_full(&big, 4, false, false);      /* K4 */
og_ring(&tri, 3, false, false, true); /* triangle */
og_vector_int_list_init(&maps, 0);
og_get_subisomorphisms_vf2(&big, &tri, NULL, NULL, NULL, NULL, &maps,
                           NULL, NULL, NULL);
/* 24 maps: 4 triangles x 6 automorphisms; each lists the K4 vertices
   matched with triangle vertices 0, 1, 2 */
og_vector_int_list_destroy(&maps);
og_destroy(&tri);
og_destroy(&big);

`get_subisomorphisms_vf2_callback`#

Exact

Runs the VF2 subgraph search and calls a function for every match found.

og_error_t og_get_subisomorphisms_vf2_callback(
    const og_t *graph1,
    const og_t *graph2,
    const og_vector_int_t *vertex_color1,
    const og_vector_int_t *vertex_color2,
    const og_vector_int_t *edge_color1,
    const og_vector_int_t *edge_color2,
    og_vector_int_t *map12,
    og_vector_int_t *map21,
    og_isohandler_t *isohandler_fn,
    og_isocompat_t *node_compat_fn,
    og_isocompat_t *edge_compat_fn,
    void *arg
);

isohandler_fn is called once per mapping found, in search order, with the current map12, map21 and arg. It returns OG_SUCCESS to go on, OG_STOP to end the search normally (the function then returns OG_SUCCESS), or any other code to end it with that error, which the function reports and returns. The vectors passed to the handler belong to the search: copy them to keep a mapping. The other subgraph functions are built on this search. Colours must be given for both graphs or for neither; colours for one graph only are ignored with a warning. Self-loops are refused. Parallel edges are outside VF2's domain: there the search runs on the graphs with parallel edges merged and also requires matched vertices to have at least the degrees counted with multiplicity, as the reference does (a merged edge carries the colour of its highest-numbered edge).

Parameters

graph1 The larger graph, searched for copies of graph2.
graph2 The pattern; same directedness as graph1.
vertex_color1 NULL, or one colour per vertex of graph1.
vertex_color2 NULL, or one colour per vertex of graph2. Only vertices of equal colour are matched.
edge_color1 NULL, or one colour per edge of graph1.
edge_color2 NULL, or one colour per edge of graph2. Only edges of equal colour are matched.
map12 NULL, or an initialised vector of length |V(graph1)|: the vertex of graph2 matched with each vertex of graph1, -1 where none. Emptied when there is no match.
map21 NULL, or an initialised vector of length |V(graph2)|: the vertex of graph1 matched with each vertex of graph2. Emptied when there is no match.
isohandler_fn Called for every match (isohandler_t).
node_compat_fn NULL, or a callback (isocompat_t) that says whether vertex g1_num of graph1 may be matched with vertex g2_num of graph2.
edge_compat_fn NULL, or the same test for edge g1_num of graph1 and edge g2_num of graph2.
arg Passed unchanged to the handler and the callbacks.

Returns

OG_SUCCESS (also after OG_STOP from the handler), or an error code.

Errors

OG_EINVAL graph1 is directed and graph2 is not, or the other way round; either graph has a self-loop; a colour vector does not match its graph's vertex or edge count.
OG_ENOMEM Not enough memory.
handler's code: the handler returned a code other than OG_SUCCESS or OG_STOP.

Complexity

Exponential in the worst case, and at least proportional to the number of mappings found. Memory O(|V| + |E|) besides the output.

Checked

Stopping with OG_STOP and error propagation tested.

C name

og_get_subisomorphisms_vf2_callback

In notebooks

Og.GetSubisomorphismsVf2Callback

igraph 1.0

igraph_get_subisomorphisms_vf2_callback

LAD subgraph isomorphism

`subisomorphic_lad`#

Exact

Finds copies of a pattern graph in a target graph with Solnon's LAD algorithm, optionally induced and with candidate lists per vertex.

og_error_t og_subisomorphic_lad(
    const og_t *pattern,
    const og_t *target,
    const og_vector_int_list_t *domains,
    og_bool_t *iso,
    og_vector_int_t *map,
    og_vector_int_list_t *maps,
    og_bool_t induced
);

Every pattern vertex has a domain of target vertices it may map to: all of them, or those listed in domains, keeping only those with enough neighbours. The search assigns the vertex with the smallest domain first, trying its values in increasing order, and filters the domains after each step: forward checking along edges (and along non-edges when induced), the LAD test that a vertex's neighbours can be matched into a candidate's neighbours, and a global all-different matching. Every pattern edge must map onto a target edge (same direction in directed graphs); with induced = true, non-adjacent pattern vertices must also map to non-adjacent target vertices.

map receives the first mapping found: map[u] is the target vertex of pattern vertex u. maps, when given, receives every mapping; without maps the search stops at the first. An empty pattern matches once, with an empty map. A pattern self-loop needs a self-loop on its image; the induced test compares distinct vertices only. Parallel edges are refused.

Note the argument order: here the pattern comes first, while the VF2 subgraph functions take the larger graph first. The time limit argument some igraph documentation lists is not part of this signature.

Parameters

pattern The graph to look for.
target The graph to search in; same directedness as pattern.
domains NULL, or a list with an entry for every pattern vertex: the target vertices it may map to (ids outside the target are ignored; an empty entry allows none).
iso Receives true when a mapping exists; may be NULL.
map NULL, or an initialised vector; receives the first mapping, empty when there is none.
maps NULL, or an initialised list; receives every mapping.
induced true: look for induced subgraphs only.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL pattern and target differ in directedness; either has parallel edges; domains has fewer entries than the pattern has vertices.
OG_EOVERFLOW |V(pattern)| x |V(target)| does not fit in og_int_t.
OG_ENOMEM Not enough memory.

Complexity

Exponential in the worst case. Memory O(|V(pattern)| |V(target)|) for the domains.

Checked

Decision, number of mappings and the set of all mappings equal python-igraph's in 322 cases plus 2400 random ones (induced, directed, domains, self-loops). The order of the mappings, and so the single map, follows LAD's internal bookkeeping: it equals python-igraph's first map in about 60% of cases and is always a valid mapping.

C name

og_subisomorphic_lad

In notebooks

Og.SubisomorphicLad

igraph 1.0

igraph_subisomorphic_lad

Isomorphism classes of small graphs

`isoclass`#

Exact

Returns the isomorphism class of a graph with 3 to 6 vertices (undirected) or 3 to 4 vertices (directed).

og_error_t og_isoclass(const og_t *graph, og_int_t *isoclass);

Graphs of a supported size fall into a fixed list of classes: 4, 11, 34 and 156 classes for undirected graphs of 3, 4, 5 and 6 vertices; 16 and 218 for directed graphs of 3 and 4 vertices. The class numbers are igraph's, so they can be exchanged with igraph and python-igraph (for example in motif counts); the lookup tables behind them are Open Graph's own enumeration. Self-loops and parallel edges are ignored. isoclass_create builds a graph of a given class.

Parameters

graph The graph.
isoclass Receives the class number.

Returns

OG_SUCCESS, or an error code.

Errors

OG_UNIMPLEMENTED the graph's vertex count is not supported for its directedness.

Complexity

O(|E|).

Checked

Every labelled graph of every supported size plus 1000 random graphs equal python-igraph; OG_UNIMPLEMENTED as observed.

C name

og_isoclass

In notebooks

Og.Isoclass

igraph 1.0

igraph_isoclass

`isoclass_subgraph`#

Exact

Returns the isomorphism class of the subgraph induced by a few chosen vertices.

og_error_t og_isoclass_subgraph(
    const og_t *graph,
    og_vs_t vids,
    og_int_t *isoclass
);

The subgraph on the vertices of vids, with every edge of graph between them, is classified as by isoclass; the order of vids does not change the class. vids must hold 3 to 6 vertices (undirected) or 3 to 4 (directed); self-loops and parallel edges are ignored. A vertex listed twice gives the class python-igraph reports for that input.

Parameters

graph The graph.
vids Vertex selection of the subgraph.
isoclass Receives the class number.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVVID vids names a vertex that is not in the graph.
OG_EINVAL vids is a malformed selector (for example a range that ends before it starts).
OG_UNIMPLEMENTED vids holds an unsupported number of vertices.

Complexity

O(k (d + k)) for k listed vertices with d edges at them in all.

Checked

Random vertex subsets of random graphs equal python-igraph, a repeated vertex included.

C name

og_isoclass_subgraph

In notebooks

Og.IsoclassSubgraph

igraph 1.0

igraph_isoclass_subgraph

See also

isoclass, isoclass_create

`isoclass_create`#

Exact

Builds a graph of a given isomorphism class.

og_error_t og_isoclass_create(
    og_t *graph,
    og_int_t size,
    og_int_t number,
    og_bool_t directed
);

graph is initialised by the call (it must not be initialised before; destroy it with destroy) and receives the representative of class number for graphs of size vertices: the same edges python-igraph's Graph.Isoclass gives. Valid numbers run from 0 to the class count minus 1. Graphs of a supported size fall into a fixed list of classes: 4, 11, 34 and 156 classes for undirected graphs of 3, 4, 5 and 6 vertices; 16 and 218 for directed graphs of 3 and 4 vertices. The class numbers are igraph's, so they can be exchanged with igraph and python-igraph (for example in motif counts); the lookup tables behind them are Open Graph's own enumeration.

Parameters

graph Uninitialised graph; receives the result.
size Number of vertices: 3 to 6 undirected, 3 or 4 directed.
number Class number.
directed Whether the graph is directed.

Returns

OG_SUCCESS, or an error code.

Errors

OG_UNIMPLEMENTED size is not supported for that directedness.
OG_EINVAL number is not a class of that size.
OG_ENOMEM Not enough memory.

Complexity

O(1).

Checked

Every class of every supported size equals python-igraph's Graph.Isoclass edge by edge.

C name

og_isoclass_create

In notebooks

Og.IsoclassCreate

igraph 1.0

igraph_isoclass_create

See also

isoclass, graph_count

`graph_count`#

Exact

Number of unlabelled graphs on n vertices.

og_error_t og_graph_count(og_int_t n, og_bool_t directed, og_int_t *count);

The number of pairwise non-isomorphic simple graphs with n vertices: 1, 1, 2, 4, 11, 34, 156, ... undirected (OEIS A000088) and 1, 1, 3, 16, 218, 9608, ... directed (OEIS A000273). Graphs with self-loops or parallel edges are not counted. The values come from a table computed with the Polya-Burnside count and are given as long as they fit in 64 bits: n up to 14 undirected and up to 9 directed.

Parameters

n Number of vertices, 0 or more.
directed Count directed graphs.
count Receives the number.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL n is negative.
OG_EOVERFLOW the number does not fit in 64 bits.

Complexity

O(1).

Checked

python-igraph does not expose it; values from an independent exact Polya count, cross-checked with the number of classes python-igraph's Graph.Isoclass accepts.

C name

og_graph_count

In notebooks

Og.GraphCount

igraph 1.0

igraph_graph_count

See also

isoclass, isoclass_create

Permutations

`invert_permutation`#

Unit tests

Computes the inverse of a permutation.

og_error_t og_invert_permutation(
    const og_vector_int_t *permutation,
    og_vector_int_t *inverse
);

inverse[permutation[i]] = i for every i. permutation must hold every value from 0 to n - 1 exactly once, n being its length.

Parameters

permutation The permutation.
inverse Initialised vector; receives the inverse.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL an entry is outside 0..n-1, or a value occurs twice.
OG_ENOMEM Not enough memory.

Complexity

O(n).

Checked

python-igraph does not expose it; checked on random permutations and invalid input.

C name

og_invert_permutation

In notebooks

Og.InvertPermutation

igraph 1.0

igraph_invert_permutation

`permute_vertices`#

Exact

Relabels the vertices of a graph.

og_error_t og_permute_vertices(
    const og_t *graph,
    og_t *res,
    const og_vector_int_t *permutation
);

res is initialised by the call and receives a copy of graph in which vertex i is vertex permutation[i] of graph. Edge e of res joins the new ids of the end points of edge e of graph, so edge ids keep their order; directedness, self-loops and parallel edges are kept. Attributes are carried over through the attribute handler, vertex attributes following their vertices. This is the convention the labeling of canonical_permutation is made for.

Parameters

graph The graph.
res Uninitialised graph; receives the relabelled copy.
permutation One entry per vertex; must be a permutation of 0..|V|-1.

Returns

OG_SUCCESS, or an error code.

Errors

OG_EINVAL permutation does not have |V| entries, or is not a permutation.
OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

Edge list equal to python-igraph's on 220 random graphs (self-loops, multi-edges, directed and undirected, 0 to 300 vertices).

C name

og_permute_vertices

In notebooks

Og.PermuteVertices

igraph 1.0

igraph_permute_vertices

`simplify_and_colorize`#

Exact

Turns a multigraph into a simple graph whose colours record the self-loops and edge multiplicities.

og_error_t og_simplify_and_colorize(
    const og_t *graph,
    og_t *res,
    og_vector_int_t *vertex_color,
    og_vector_int_t *edge_color
);

res is initialised by the call and receives the graph without self-loops and with each group of parallel edges merged into one edge. vertex_color[v] is the number of self-loops at v; edge_color[e] is how many edges were merged into edge e of res. The edges of res are sorted by (from, to). In a directed graph a->b and b->a stay separate edges. Two multigraphs are isomorphic exactly when their simplified graphs are isomorphic with these colours respected; isomorphic uses this for multigraphs.

Parameters

graph The graph.
res Uninitialised graph; receives the simple graph.
vertex_color NULL, or an initialised vector; receives the self-loop count of each vertex.
edge_color NULL, or an initialised vector; receives the multiplicity of each edge of res.

Returns

OG_SUCCESS, or an error code.

Errors

OG_ENOMEM Not enough memory.

Complexity

O(|V| + |E|).

Checked

python-igraph does not expose it; expected edges and colours derived from Graph.simplify with summed multiplicities on 220 random graphs.

C name

og_simplify_and_colorize

In notebooks

Og.SimplifyAndColorize

igraph 1.0

igraph_simplify_and_colorize

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

Isomorphism

Types

bliss_sh_ttype#

bliss_info_ttype#

isohandler_ttype#

isocompat_ttype#

Isomorphism and automorphisms

isomorphic#

subisomorphic#

count_automorphisms#

automorphism_group#

canonical_permutation#

Canonical labelling

isomorphic_bliss#

count_automorphisms_bliss#

automorphism_group_bliss#

canonical_permutation_bliss#

VF2

isomorphic_vf2#

count_isomorphisms_vf2#

get_isomorphisms_vf2#

get_isomorphisms_vf2_callback#

subisomorphic_vf2#

count_subisomorphisms_vf2#

get_subisomorphisms_vf2#

get_subisomorphisms_vf2_callback#

LAD subgraph isomorphism

subisomorphic_lad#

Isomorphism classes of small graphs

isoclass#

isoclass_subgraph#

isoclass_create#

graph_count#

Permutations

invert_permutation#

permute_vertices#

simplify_and_colorize#

`bliss_sh_t`type#

`bliss_info_t`type#

`isohandler_t`type#

`isocompat_t`type#

`isomorphic`#

`subisomorphic`#

`count_automorphisms`#

`automorphism_group`#

`canonical_permutation`#

`isomorphic_bliss`#

`count_automorphisms_bliss`#

`automorphism_group_bliss`#

`canonical_permutation_bliss`#

`isomorphic_vf2`#

`count_isomorphisms_vf2`#

`get_isomorphisms_vf2`#

`get_isomorphisms_vf2_callback`#

`subisomorphic_vf2`#

`count_subisomorphisms_vf2`#

`get_subisomorphisms_vf2`#

`get_subisomorphisms_vf2_callback`#

`subisomorphic_lad`#

`isoclass`#

`isoclass_subgraph`#

`isoclass_create`#

`graph_count`#

`invert_permutation`#

`permute_vertices`#

`simplify_and_colorize`#