igraph Reference Manual

For using the igraph C library

Chapter 16. Graph Isomorphism

1. The simple interface

igraph provides four set of functions to deal with graph isomorphism problems.

The `igraph_isomorphic()` and `igraph_subisomorphic()` functions make up the first set (in addition with the `igraph_permute_vertices()` function). These functions choose the algorithm which is best for the supplied input graph. (The choice is not very sophisticated though, see their documentation for details.)

The VF2 graph (and subgraph) isomorphism algorithm is implemented in igraph, these functions are the second set. See `igraph_isomorphic_vf2()` and `igraph_subisomorphic_vf2()` for starters.

Functions for the BLISS algorithm constitute the third set, see `igraph_isomorphic_bliss()`. This implementation only works for undirected graphs.

Finally, the isomorphism classes of all graphs with three and four vertices are precomputed and stored in igraph, so for these small graphs there is a very simple fast way to decide isomorphism. See `igraph_isomorphic_34()`.

1.1. `igraph_permute_vertices` — Permute the vertices

```int igraph_permute_vertices(const igraph_t *graph, igraph_t *res,
const igraph_vector_t *permutation);
```

This function creates a new graph from the input graph by permuting its vertices according to the specified mapping. Call this function with the output of `igraph_canonical_permutation()` to create the canonical form of a graph.

Arguments:

 `graph`: The input graph. `res`: Pointer to an uninitialized graph object. The new graph is created here. `permutation`: The permutation to apply. Vertex 0 is mapped to the first element of the vector, vertex 1 to the second, etc. Note that it is not checked that the vector contains every element only once, and no range checking is performed either.

Returns:

 Error code.

Time complexity: O(|V|+|E|), linear in terms of the number of vertices and edges.

1.2. `igraph_isomorphic` — Decides whether two graphs are isomorphic

```int igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso);
```

From Wikipedia: The graph isomorphism problem or GI problem is the graph theory problem of determining whether, given two graphs G1 and G2, it is possible to permute (or relabel) the vertices of one graph so that it is equal to the other. Such a permutation is called a graph isomorphism.

This function decides which graph isomorphism algorithm to be used based on the input graphs. Right now it does the following:

1. If one graph is directed and the other undirected then an error is triggered.

2. If the two graphs does not have the same number of vertices and edges it returns with `FALSE`.

3. Otherwise, if the graphs have three or four vertices then an O(1) algorithm is used with precomputed data.

4. Otherwise, if the graphs are directed then VF2 is used, see `igraph_isomorphic_vf2()`.

5. Otherwise BLISS is used, see `igraph_isomorphic_bliss()`.

Please call the VF2 and BLISS functions directly if you need something more sophisticated, e.g. you need the isomorphic mapping.

Arguments:

 `graph1`: The first graph. `graph2`: The second graph. `iso`: Pointer to a logical variable, will be set to TRUE (1) if the two graphs are isomorphic, and FALSE (0) otherwise.

Returns:

 Error code.

Time complexity: exponential.

1.3. `igraph_subisomorphic` — Decide subgraph isomorphism

```int igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso);
```

Check whether `graph2` is isomorphic to a subgraph of `graph1`. Currently this function just calls `igraph_subisomorphic_vf2()` for all graphs.

Arguments:

 `graph1`: The first input graph, may be directed or undirected. This is supposed to be the bigger graph. `graph2`: The second input graph, it must have the same directedness as `graph2`, or an error is triggered. This is supposed to be the smaller graph. `iso`: Pointer to a boolean, the result is stored here.

Returns:

 Error code.

Time complexity: exponential.

2. The BLISS algorithm

BLISS is a successor of the famous NAUTY algorithm and implementation. While using the same ideas in general, with better heuristics and data structure BLISS outperforms NAUTY on most graphs.

BLISS was developed and implemented by Tommi Junttila and Petteri Kaski at Helsinki University of Technology, Finland. See Tommi Juntilla's homepage at http://www.tcs.hut.fi/~tjunttil/ and the publication at http://www.siam.org/proceedings/alenex/2007/alx07_013junttilat.pdf for more information.

BLISS version 0.35 is included in igraph.

2.1. `igraph_bliss_sh_t` — Splitting heuristics for BLISS

```typedef enum { IGRAPH_BLISS_F=0, IGRAPH_BLISS_FL,
IGRAPH_BLISS_FS, IGRAPH_BLISS_FM,
IGRAPH_BLISS_FLM, IGRAPH_BLISS_FSM } igraph_bliss_sh_t;
```

Values:

 `IGRAPH_BLISS_F`: First non-singleton cell. `IGRAPH_BLISS_FL`: First largest non-singleton cell. `IGRAPH_BLISS_FS`: First smallest non-singleton cell. `IGRAPH_BLISS_FM`: First maximally non-trivially connected non-singleton cell. `IGRAPH_BLISS_FLM`: Largest maximally non-trivially connected non-singleton cell. `IGRAPH_BLISS_FSM`: Smallest maximally non-trivially connected non-singletion cell.

2.2. `igraph_bliss_info_t` — Information about a BLISS run

```typedef struct igraph_bliss_info_t {
unsigned long nof_nodes;
unsigned long nof_leaf_nodes;
unsigned long max_level;
char *group_size;
} igraph_bliss_info_t;
```

Some secondary information found by the BLISS algorithm is stored here. It is useful if you wany to study the internal working of the algorithm.

Values:

 `nof_nodes`: The number of nodes in the search tree. `nof_leaf_nodes`: The number of leaf nodes in the search tree. `nof_bad_nodes`: Number of bad nodes. `nof_canupdates`: Number of canrep updates. `max_level`: Maximum level. `group_size`: The size of the automorphism group of the graph, given as a string. It should be deallocated via `free()` if not needed any more.

See http://www.tcs.hut.fi/Software/bliss/index.html for details about the algorithm and these parameters.

2.3. `igraph_canonical_permutation` — Canonical permutation using BLISS

```int igraph_canonical_permutation(const igraph_t *graph, igraph_vector_t *labeling,
igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
```

This function computes the canonical permutation which transforms the graph into a canonical form by using the BLISS algorithm.

Arguments:

 `graph`: The input graph, it is treated as undirected and the multiple edges are ignored. `labeling`: Pointer to a vector, the result is stored here. The permutation takes vertex 0 to the first element of the vector, vertex 1 to the second, etc. The vector will be resized as needed. `sh`: The split heuristics to be used in BLISS. See `igraph_bliss_sh_t`. `info`: If not `NULL` then information on BLISS internals is stored here. See `igraph_bliss_info_t`.

Returns:

 Error code.

Time complexity: exponential, in practice it is fast for many graphs.

2.4. `igraph_isomorphic_bliss` — Graph isomorphism via BLISS

```int igraph_isomorphic_bliss(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso, igraph_vector_t *map12,
igraph_vector_t *map21,
igraph_bliss_sh_t sh1, igraph_bliss_sh_t sh2,
igraph_bliss_info_t *info1, igraph_bliss_info_t *info2);
```

This function uses the BLISS graph isomorphism algorithm, a successor of the famous NAUTY algorithm and implementation. BLISS is open source and licensed according to the GNU GPL. See http://www.tcs.hut.fi/Software/bliss/index.html for details. Currently the 0.35 version of BLISS is included in igraph.

Arguments:

 `graph1`: The first input graph, it is assumed to be undirected, directed graphs are treated as undirected too. The algorithm eliminates multiple edges from the graph first. `graph2`: The second input graph, it is assumed to be undirected, directed graphs are treated as undirected too. The algorithm eliminates multiple edges from the graph first. `iso`: Pointer to a boolean, the result is stored here. `map12`: A vector or `NULL` pointer. If not `NULL` then an isomorphic mapping from `graph1` to `graph2` is stored here. If the input graphs are not isomorphic then this vector is cleared, i.e. it will have length zero. `map21`: Similar to `map12`, but for the mapping from `graph2` to `graph1`. `sh1`: Splitting heuristics to be used for the first graph. See `igraph_bliss_sh_t`. `sh2`: Splitting heuristics to be used for the second graph. See `igraph_bliss_sh_t`. `info1`: If not `NULL`, information about the canonization of the first input graph is stored here. See `igraph_bliss_info_t` for details. Note that if the two graphs have different number of vertices or edges, then this is not filled. `info2`: Same as `info1`, but for the second graph.

Returns:

 Error code.

Time complexity: exponential, but in practice it is quite fast.

2.5. `igraph_automorphisms` — Number of automorphisms using BLISS

```int igraph_automorphisms(const igraph_t *graph,
igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
```

The number of automorphisms of a graph is computed using BLISS. The result is returned as part of the `info` structure, in tag `group_size`. It is returned as a string, as it can be very high even for relatively small graphs. If the GNU MP library is used then this number is exact, otherwise a long double is used and it is only approximate. See also `igraph_bliss_info_t`.

Arguments:

 `graph`: The input graph, it is treated as undirected and the multiple edges are ignored. `sh`: The split heuristics to be used in BLISS. See `igraph_bliss_sh_t`. `info`: The result is stored here, in particular in the `group_size` tag of `info`.

Returns:

 Error code.

Time complexity: exponential, in practice it is fast for many graphs.

3. The VF2 algorithm

3.1. `igraph_isomorphic_vf2` — Isomorphism via VF2

```int igraph_isomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_bool_t *iso, igraph_vector_t *map12,
igraph_vector_t *map21,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

This function performs the VF2 algorithm via calling `igraph_isomorphic_function_vf2()`.

Note that this function cannot be used for deciding subgraph isomorphism, use `igraph_subisomorphic_vf2()` for that.

Arguments:

 `graph1`: The first graph, may be directed or undirected. `graph2`: The second graph. It must have the same directedness as `graph1`, otherwise an error is reported. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `iso`: Pointer to a logical constant, the result of the algorithm will be placed here. `map12`: Pointer to an initialized vector or a NULL pointer. If not a NULL pointer then the mapping from `graph1` to `graph2` is stored here. If the graphs are not isomorphic then the vector is cleared (ie. has zero elements). `map21`: Pointer to an initialized vector or a NULL pointer. If not a NULL pointer then the mapping from `graph2` to `graph1` is stored here. If the graphs are not isomorphic then the vector is cleared (ie. has zero elements). `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential, what did you expect?

Example 16.1.  File `examples/simple/igraph_isomorphic_vf2.c`

```/* -*- mode: C -*-  */
/*
IGraph library.
Copyright (C) 2009-2012  Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard st, Cambridge MA, 02139 USA

This program is free software; you can redistribute it and/or modify
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA

*/

#include <igraph.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int random_permutation(igraph_vector_t *vec) {
/* We just do size(vec) * 2 swaps */
long int one, two, tmp, i, n=igraph_vector_size(vec);
for (i=0; i<2*n; i++) {
one= (double)rand() / RAND_MAX * n;
two= (double)rand() / RAND_MAX * n;
tmp=one; one=two; two=tmp;
}
return 0;
}

int main() {

igraph_t ring1, ring2;
igraph_vector_int_t color1, color2;
igraph_vector_t perm;
igraph_bool_t iso;
igraph_integer_t count;
long int i;

srand(time(0));

igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/1);
igraph_vector_init_seq(&perm, 0, igraph_vcount(&ring1)-1);
random_permutation(&perm);
igraph_permute_vertices(&ring1, &ring2, &perm);

/* Without colors */
igraph_isomorphic(&ring1, &ring2, &iso);
if (!iso) {
fprintf(stderr, "Without color failed.\n");
return 1;
}

/* Without colors, number of isomorphisms */
igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, 0, 0, &count, 0, 0, 0);
if (count != 200) {
fprintf(stderr, "Count without colors failed, expected %li, got %li.\n",
(long int) 200, (long int) count);
return 2;
}

/* Everything has the same colors */
igraph_vector_int_init(&color1, igraph_vcount(&ring1));
igraph_vector_int_init(&color2, igraph_vcount(&ring2));
igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
if (!iso) {
fprintf(stderr, "Single color failed.\n");
return 3;
}

/* Two colors, just counting */
for (i=0; i<igraph_vector_int_size(&color1); i+=2) {
VECTOR(color1)[i]   = VECTOR(color2)[i] = 0;
VECTOR(color1)[i+1] = VECTOR(color2)[i] = 1;
}
igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count, 0, 0, 0);
if (count != 100) {
fprintf(stderr, "Count with two colors failed, expected %li, got %li.\n",
(long int) 100, (long int) count);
return 4;
}

/* Separate colors for each vertex */
for (i=0; i<igraph_vector_int_size(&color1); i++) {
VECTOR(color1)[i]   = VECTOR(color2)[i] = i;
}
igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count, 0, 0, 0);
if (count != 1) {
fprintf(stderr, "Count with separate colors failed, expected %li, got %li.\n",
(long int) 1, (long int) count);
return 5;
}

/* Try a negative result */
igraph_vector_int_fill(&color1, 0);
igraph_vector_int_fill(&color2, 0);
VECTOR(color1)=1;
igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
if (iso) {
fprintf(stderr, "Negative test failed.\n");
return 6;
}

/* Another negative, same color distribution, different topology */
igraph_vector_int_fill(&color1, 0);
igraph_vector_int_fill(&color2, 0);
VECTOR(color1)=1;  VECTOR(color1)=1;
VECTOR(color2)=1;  VECTOR(color2)=1;
igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
if (iso) {
fprintf(stderr, "Second negative test failed.\n");
return 7;
}

igraph_vector_int_destroy(&color1);
igraph_vector_int_destroy(&color2);

igraph_vector_destroy(&perm);
igraph_destroy(&ring2);
igraph_destroy(&ring1);

/* ---------------------------------------------------------------- */
/* SUBGRAPH ISOMORPHISM                                             */
/* ---------------------------------------------------------------- */

igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);
igraph_ring(&ring2, 80 , /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);

/* One color */
igraph_vector_int_init(&color1, igraph_vcount(&ring1));
igraph_vector_int_init(&color2, igraph_vcount(&ring2));
igraph_count_subisomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0,
&count, 0, 0, 0);
if (count != 42) {
fprintf(stderr, "Count with one color failed, expected %li, got %li.\n",
(long int) 42, (long int) count);
return 31;
}

/* Two colors */
for (i=0; i<igraph_vector_int_size(&color1); i+=2) {
VECTOR(color1)[i]   = 0;
VECTOR(color1)[i+1] = 1;
}
for (i=0; i<igraph_vector_int_size(&color2); i+=2) {
VECTOR(color2)[i]   = 0;
VECTOR(color2)[i+1] = 1;
}
igraph_count_subisomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0,
&count, 0, 0, 0);
if (count != 21) {
fprintf(stderr, "Count with two colors failed, expected %li, got %li.\n",
(long int) 21, (long int) count);
return 32;
}

igraph_vector_int_destroy(&color1);
igraph_vector_int_destroy(&color2);

igraph_destroy(&ring1);
igraph_destroy(&ring2);

/* ---------------------------------------------------------------- */
/* EDGE COLORING, GRAPH ISOMORPHISM                                 */
/* ---------------------------------------------------------------- */

igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
igraph_vector_init_seq(&perm, 0, igraph_ecount(&ring1)-1);
random_permutation(&perm);
igraph_permute_vertices(&ring1, &ring2, &perm);
igraph_vector_destroy(&perm);

/* Everything has the same color */
igraph_vector_int_init(&color1, igraph_ecount(&ring1));
igraph_vector_int_init(&color2, igraph_ecount(&ring2));
igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
if (!iso) {
fprintf(stderr, "Single edge-color failed.\n");
return 41;
}

/* Two colors, just counting */
for (i=0; i<igraph_vector_int_size(&color1); i+=2) {
VECTOR(color1)[i]   = VECTOR(color2)[i] = 0;
VECTOR(color1)[i+1] = VECTOR(color2)[i] = 1;
}
igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count, 0, 0, 0);
if (count != 100) {
fprintf(stderr, "Count with two edge colors failed, expected %li, got %li.\n",
(long int) 100, (long int) count);
return 42;
}

/* Separate colors for each edge */
for (i=0; i<igraph_vector_int_size(&color1); i++) {
VECTOR(color1)[i]   = VECTOR(color2)[i] = i;
}
igraph_count_isomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &count, 0, 0, 0);
if (count != 1) {
fprintf(stderr, "Count with separate edge colors failed, expected %li, got %li.\n",
(long int) 1, (long int) count);
return 43;
}

/* Try a negative result */
igraph_vector_int_fill(&color1, 0);
igraph_vector_int_fill(&color2, 0);
VECTOR(color1)=1;
igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
if (iso) {
fprintf(stderr, "Negative edge test failed.\n");
return 44;
}

/* Another negative, same color distribution, different topology */
igraph_vector_int_fill(&color1, 0);
igraph_vector_int_fill(&color2, 0);
VECTOR(color1)=1;  VECTOR(color1)=1;
VECTOR(color2)=1;  VECTOR(color2)=1;
igraph_isomorphic_vf2(&ring1, &ring2, 0, 0, &color1, &color2, &iso, 0, 0, 0, 0, 0);
if (iso) {
fprintf(stderr, "Second negative edge test failed.\n");
return 45;
}

igraph_vector_int_destroy(&color1);
igraph_vector_int_destroy(&color2);

igraph_destroy(&ring1);
igraph_destroy(&ring2);

/* ---------------------------------------------------------------- */
/* EDGE COLORED SUBGRAPH ISOMORPHISM                                */
/* ---------------------------------------------------------------- */

igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);
igraph_ring(&ring2, 80 , /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);

/* One color */
igraph_vector_int_init(&color1, igraph_ecount(&ring1));
igraph_vector_int_init(&color2, igraph_ecount(&ring2));
igraph_count_subisomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2,
&count, 0, 0, 0);
if (count != 42) {
fprintf(stderr, "Count with one edge color failed, expected %li, got %li.\n",
(long int) 42, (long int) count);
return 51;
}

/* Two colors */
for (i=0; i<igraph_vector_int_size(&color1)-1; i+=2) {
VECTOR(color1)[i]   = 0;
VECTOR(color1)[i+1] = 1;
}
for (i=0; i<igraph_vector_int_size(&color2)-1; i+=2) {
VECTOR(color2)[i]   = 0;
VECTOR(color2)[i+1] = 1;
}
igraph_count_subisomorphisms_vf2(&ring1, &ring2, 0, 0, &color1, &color2,
&count, 0, 0, 0);
if (count != 22) {
fprintf(stderr, "Count with two edge colors failed, expected %li, got %li.\n",
(long int) 22, (long int) count);
return 52;
}

igraph_vector_int_destroy(&color1);
igraph_vector_int_destroy(&color2);

igraph_destroy(&ring1);
igraph_destroy(&ring2);

return 0;
}
```

3.2. `igraph_count_isomorphisms_vf2` — Number of isomorphisms via VF2

```int igraph_count_isomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_integer_t *count,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

This function counts the number of isomorphic mappings between two graphs. It uses the generic `igraph_isomorphic_function_vf2()` function.

Arguments:

 `graph1`: The first input graph, may be directed or undirected. `graph2`: The second input graph, it must have the same directedness as `graph1`, or an error will be reported. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `count`: Point to an integer, the result will be stored here. `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential.

3.3. `igraph_get_isomorphisms_vf2` — Collect the isomorphic mappings

```int igraph_get_isomorphisms_vf2(const igraph_t *graph1,
const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_vector_ptr_t *maps,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

This function finds all the isomorphic mappings between two graphs. It uses the `igraph_isomorphic_function_vf2()` function. Call the function with the same graph as `graph1` and `graph2` to get automorphisms.

Arguments:

 `graph1`: The first input graph, may be directed or undirected. `graph2`: The second input graph, it must have the same directedness as `graph1`, or an error will be reported. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `maps`: Pointer vector. On return it is empty if the input graphs are no isomorphic. Otherwise it contains pointers to igraph_vector_t objects, each vector is an isomorphic mapping of `graph2` to `graph1`. Please note that you need to 1) Destroy the vectors via `igraph_vector_destroy()`, 2) free them via `free()` and then 3) call `igraph_vector_ptr_destroy()` on the pointer vector to deallocate all memory when `maps` is no longer needed. `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential.

3.4. `igraph_isohandler_t` — Callback type, called when an isomorphism was found

```typedef igraph_bool_t igraph_isohandler_t(const igraph_vector_t *map12,
const igraph_vector_t *map21, void *arg);
```

See the details at the documentation of `igraph_isomorphic_function_vf2()`.

Arguments:

 `map12`: The mapping from the first graph to the second. `map21`: The mapping from the second graph to the first, the inverse of `map12` basically. `arg`: This extra argument was passed to `igraph_isomorphic_function_vf2()` when it was called.

Returns:

 Boolean, whether to continue with the isomorphism search.

3.5. `igraph_isocompat_t` — Callback type, called to check whether two vertices or edges are compatible

```typedef igraph_bool_t igraph_isocompat_t(const igraph_t *graph1,
const igraph_t *graph2,
const igraph_integer_t g1_num,
const igraph_integer_t g2_num,
void *arg);
```

VF2 (subgraph) isomorphism functions can be restricted by defining relations on the vertices and/or edges of the graphs, and then checking whether the vertices (edges) match according to these relations.

This feature is implemented by two callbacks, one for vertices, one for edges. Every time igraph tries to match a vertex (edge) of the first (sub)graph to a vertex of the second graph, the vertex (edge) compatibility callback is called. The callback returns a logical value, giving whether the two vertices match.

Both callback functions are of type `igraph_isocompat_t`.

Arguments:

 `graph1`: The first graph. `graph2`: The second graph. `g1_num`: The id of a vertex or edge in the first graph. `g2_num`: The id of a vertex or edge in the second graph. `arg`: Extra argument to pass to the callback functions.

Returns:

 Logical scalar, whether vertex (or edge) `g1_num` in `graph1` is compatible with vertex (or edge) `g2_num` in `graph2`.

3.6. `igraph_isomorphic_function_vf2` — The generic VF2 interface

```int igraph_isomorphic_function_vf2(const igraph_t *graph1, const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_vector_t *map12,
igraph_vector_t *map21,
igraph_isohandler_t *isohandler_fn,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

This function is an implementation of the VF2 isomorphism algorithm, see P. Foggia, C. Sansone, M. Vento, An Improved algorithm for matching large graphs, Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations, Italy, 2001.

For using it you need to define a callback function of type `igraph_isohandler_t`. This function will be called whenever VF2 finds an isomorphism between the two graphs. The mapping between the two graphs will be also provided to this function. If the callback returns a nonzero value then the search is continued, otherwise it stops.

Arguments:

 `graph1`: The first input graph. `graph2`: The second input graph. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `map12`: Pointer to an initialized vector or `NULL`. If not `NULL` and the supplied graphs are isomorphic then the permutation taking `graph1` to `graph` is stored here. If not `NULL` and the graphs are not isomorphic then a zero-length vector is returned. `map21`: This is the same as `map12`, but for the permutation taking `graph2` to `graph1`. `isohandler_fn`: The callback function to be called if an isomorphism is found. See also `igraph_isohandler_t`. `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `isohandler_fn`, `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential.

3.7. `igraph_subisomorphic_vf2` — Decide subgraph isomorphism using VF2

```int igraph_subisomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_bool_t *iso, igraph_vector_t *map12,
igraph_vector_t *map21,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

Decides whether a subgraph of `graph1` is isomorphic to `graph2`. It uses `igraph_subisomorphic_function_vf2()`.

Arguments:

 `graph1`: The first input graph, may be directed or undirected. This is supposed to be the larger graph. `graph2`: The second input graph, it must have the same directedness as `graph1`. This is supposed to be the smaller graph. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the subgraph isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `iso`: Pointer to a boolean. The result of the decision problem is stored here. `map12`: Pointer to a vector or `NULL`. If not `NULL`, then an isomorphic mapping from `graph1` to `graph2` is stored here. `map21`: Pointer to a vector ot `NULL`. If not `NULL`, then an isomorphic mapping from `graph2` to `graph1` is stored here. `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential.

3.8. `igraph_count_subisomorphisms_vf2` — Number of subgraph isomorphisms using VF2

```int igraph_count_subisomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_integer_t *count,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

Count the number of isomorphisms between subgraphs of `graph1` and `graph2`. This function uses `igraph_subisomorphic_function_vf2()`.

Arguments:

 `graph1`: The first input graph, may be directed or undirected. This is supposed to be the larger graph. `graph2`: The second input graph, it must have the same directedness as `graph1`. This is supposed to be the smaller graph. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the subgraph isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `count`: Pointer to an integer. The number of subgraph isomorphisms is stored here. `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential.

3.9. `igraph_get_subisomorphisms_vf2` — Return all subgraph isomorphic mappings

```int igraph_get_subisomorphisms_vf2(const igraph_t *graph1,
const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_vector_ptr_t *maps,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

This function collects all isomorphic mappings of `graph2` to a subgraph of `graph1`. It uses the `igraph_subisomorphic_function_vf2()` function.

Arguments:

 `graph1`: The first input graph, may be directed or undirected. This is supposed to be the larger graph. `graph2`: The second input graph, it must have the same directedness as `graph1`. This is supposed to be the smaller graph. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the subgraph isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `maps`: Pointer vector. On return it contains pointers to igraph_vector_t objects, each vector is an isomorphic mapping of `graph2` to a subgraph of `graph1`. Please note that you need to 1) Destroy the vectors via `igraph_vector_destroy()`, 2) free them via `free()` and then 3) call `igraph_vector_ptr_destroy()` on the pointer vector to deallocate all memory when `maps` is no longer needed. `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential.

3.10. `igraph_subisomorphic_function_vf2` — Generic VF2 function for subgraph isomorphism problems

```int igraph_subisomorphic_function_vf2(const igraph_t *graph1,
const igraph_t *graph2,
const igraph_vector_int_t *vertex_color1,
const igraph_vector_int_t *vertex_color2,
const igraph_vector_int_t *edge_color1,
const igraph_vector_int_t *edge_color2,
igraph_vector_t *map12,
igraph_vector_t *map21,
igraph_isohandler_t *isohandler_fn,
igraph_isocompat_t *node_compat_fn,
igraph_isocompat_t *edge_compat_fn,
void *arg);
```

This function is the pair of `igraph_isomorphic_function_vf2()`, for subgraph isomorphism problems. It searches for subgraphs of `graph1` which are isomorphic to `graph2`. When it founds an isomorphic mapping it calls the supplied callback `isohandler_fn`. The mapping (and its inverse) and the additional `arg` argument are supplied to the callback.

Arguments:

 `graph1`: The first input graph, may be directed or undirected. This is supposed to be the larger graph. `graph2`: The second input graph, it must have the same directedness as `graph1`. This is supposed to be the smaller graph. `vertex_color1`: An optional color vector for the first graph. If color vectors are given for both graphs, then the subgraph isomorphism is calculated on the colored graphs; i.e. two vertices can match only if their color also matches. Supply a null pointer here if your graphs are not colored. `vertex_color2`: An optional color vector for the second graph. See the previous argument for explanation. `edge_color1`: An optional edge color vector for the first graph. The matching edges in the two graphs must have matching colors as well. Supply a null pointer here if your graphs are not edge-colored. `edge_color2`: The edge color vector for the second graph. `map12`: Pointer to a vector or `NULL`. If not `NULL`, then an isomorphic mapping from `graph1` to `graph2` is stored here. `map21`: Pointer to a vector ot `NULL`. If not `NULL`, then an isomorphic mapping from `graph2` to `graph1` is stored here. `isohandler_fn`: A pointer to a function of type `igraph_isohandler_t`. This will be called whenever a subgraph isomorphism is found. If the function returns with a non-zero value then the search is continued, otherwise it stops and the function returns. `node_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two nodes are compatible. `edge_compat_fn`: A pointer to a function of type `igraph_isocompat_t`. This function will be called by the algorithm to determine whether two edges are compatible. `arg`: Extra argument to supply to functions `isohandler_fn`, `node_compat_fn` and `edge_compat_fn`.

Returns:

 Error code.

Time complexity: exponential.

4.1. `igraph_subisomorphic_lad` — Check subgraph isomorphism with the LAD algorithm

```int igraph_subisomorphic_lad(const igraph_t *pattern, const igraph_t *target,
igraph_vector_ptr_t *domains,
igraph_bool_t *iso, igraph_vector_t *map,
igraph_vector_ptr_t *maps,
igraph_bool_t induced, int time_limit);
```

Check whether `pattern` is isomorphic to a subgraph os `target`. The original LAD implementation by Christine Solnon was used as the basis of this code.

See more about at http://liris.cnrs.fr/csolnon/LAD.html and in Christine Solnon: AllDifferent-based Filtering for Subgraph Isomorphism. Artificial Intelligence, 174(12-13):850-864, August 2010, Elsevier

Arguments:

 `pattern`: The smaller graph, it can be directed or undirected. `target`: The bigger graph, it can be directed or undirected. `domains`: A pointer vector, or a null pointer. If a pointer vector, then it must contain pointers to `igraph_vector_t` objects and the length of the vector must match the number of vertices in the `pattern` graph. For each vertex, the ids of the compatible vertices in the target graph are listed. `iso`: Pointer to a boolean, or a null pointer. If not a null pointer, then the boolean is set to TRUE (1) if a subgraph isomorphism is found, and to FALSE (0) otherwise. `map`: Pointer to a vector or a null pointer. If not a null pointer and a subgraph isomorphism is found, the matching vertices from the target graph are listed here, for each vertex (in vertex id order) from the pattern graph. `maps`: Pointer vector or a null pointer. If not a null pointer, then all subgraph isomorphisms are stored in the pointer vector, in `igraph_vector_t` objects. `induced`: Boolean, whether to search for induced matching subgraphs. `time_limit`: Processor time limit in seconds. Supply zero here for no limit. If the time limit is over, then the function signals an error.

Returns:

 Error code

 `igraph_subisomorphic_vf2()` for the VF2 algorithm.

Time complexity: exponential.

Example 16.2.  File `examples/simple/igraph_subisomorphic_lad.c`

```/* -*- mode: C -*-  */
/*
IGraph library.
Copyright (C) 2012  Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA

This program is free software; you can redistribute it and/or modify
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA

*/

#include <igraph.h>

int main() {
igraph_t target, pattern;
igraph_bool_t iso;
igraph_vector_t map;
igraph_vector_ptr_t maps;
int i, n;
int domainsvec[] = { 0, 2, 8, -1,
4, 5, 6, 7, -1,
1, 3, 5, 6, 7, 8, -1,
0, 2, 8, -1,
1, 3, 7, 8, -1, -2 };
igraph_vector_ptr_t domains;
igraph_vector_t *v=0;

igraph_small(&target, 9, IGRAPH_UNDIRECTED,
0,1,0,4,0,6,
1,0,1,4,1,2,
2,1,2,3,
3,2,3,4,3,5,3,7,3,8,
4,0,4,1,4,3,4,5,4,6,
5,6,5,4,5,3,5,8,
6,0,6,4,6,5,
7,3,7,8,
8,5,8,3,8,7,
-1);
igraph_simplify(&target, /*multiple=*/ 1, /*loops=*/ 0, /*edge_comb=*/ 0);

igraph_small(&pattern, 5, IGRAPH_UNDIRECTED,
0,1,0,4,
1,0,1,4,1,2,
2,1,2,3,
3,2,3,4,
4,3,4,1,4,0,
-1);
igraph_simplify(&pattern, /*multiple=*/ 1, /*loops=*/ 0, /*edge_comb=*/ 0);

igraph_vector_init(&map, 0);
igraph_vector_ptr_init(&maps, 0);

igraph_subisomorphic_lad(&pattern, &target, /*domains=*/ 0, &iso, &map,
&maps, /*induced=*/ 0, /*time_limit=*/ 0);

if (!iso) { return 1; }
igraph_vector_print(&map);
n=igraph_vector_ptr_size(&maps);
for (i=0; i<n; i++) {
igraph_vector_t *v=VECTOR(maps)[i];
igraph_vector_print(v);
igraph_vector_destroy(v);
igraph_free(v);
}

printf("---------\n");

igraph_subisomorphic_lad(&pattern, &target, /*domains=*/ 0, &iso, &map,
&maps, /*induced=*/ 1, /*time_limit=*/ 0);

if (!iso) { return 2; }
igraph_vector_print(&map);
n=igraph_vector_ptr_size(&maps);
for (i=0; i<n; i++) {
igraph_vector_t *v=VECTOR(maps)[i];
igraph_vector_print(v);
igraph_vector_destroy(v);
igraph_free(v);
}

printf("---------\n");

igraph_vector_ptr_init(&domains, 0);
i=0; while (1) {
if (domainsvec[i] == -2) {
break;
} else if (domainsvec[i] == -1) {
igraph_vector_ptr_push_back(&domains, v);
v=0;
} else {
if (!v) {
v=(igraph_vector_t *) malloc(sizeof(igraph_vector_t));
igraph_vector_init(v, 0);
}
igraph_vector_push_back(v, domainsvec[i]);
}
i++;
}

igraph_subisomorphic_lad(&pattern, &target, &domains, &iso, &map, &maps,
/*induced=*/ 0, /*time_limit=*/ 0);

if (!iso) { return 3; }
igraph_vector_print(&map);
n=igraph_vector_ptr_size(&maps);
for (i=0; i<n; i++) {
igraph_vector_t *v=VECTOR(maps)[i];
igraph_vector_print(v);
igraph_vector_destroy(v);
igraph_free(v);
}

n=igraph_vector_ptr_size(&domains);
for (i=0; i<n; i++) {
igraph_vector_t *v=VECTOR(domains)[i];
igraph_vector_destroy(v);
free(v);
}

igraph_vector_ptr_destroy(&domains);
igraph_vector_destroy(&map);
igraph_vector_ptr_destroy(&maps);

igraph_destroy(&pattern);
igraph_destroy(&target);

return 0;
}
```

5. Functions for graphs with 3 or 4 vertices

5.1. `igraph_isomorphic_34` — Graph isomorphism for 3-4 vertices

```int igraph_isomorphic_34(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso);
```

This function uses precomputed indices to decide isomorphism problems for graphs with only 3 or 4 vertices.

Arguments:

 `graph1`: The first input graph. `graph2`: The second input graph. Must have the same directedness as `graph1`. `iso`: Pointer to a boolean, the result is stored here.

Returns:

 Error code.

Time complexity: O(1).

5.2. `igraph_isoclass` — Determine the isomorphism class of a graph with 3 or 4 vertices

```int igraph_isoclass(const igraph_t *graph, igraph_integer_t *isoclass);
```

All graphs with a given number of vertices belong to a number of isomorphism classes, with every graph in a given class being isomorphic to each other.

This function gives the isomorphism class (a number) of a graph. Two graphs have the same isomorphism class if and only if they are isomorphic.

The first isomorphism class is numbered zero and it is the empty graph, the last isomorphism class is the full graph. The number of isomorphism class for directed graphs with three vertices is 16 (between 0 and 15), for undirected graph it is only 4. For graphs with four vertices it is 218 (directed) and 11 (undirected).

Arguments:

 `graph`: The graph object. `isoclass`: Pointer to an integer, the isomorphism class will be stored here.

Returns:

 Error code.

Because of some limitations this function works only for graphs with three of four vertices.

Time complexity: O(|E|), the number of edges in the graph.

5.3. `igraph_isoclass_subgraph` — The isomorphism class of a subgraph of a graph.

```int igraph_isoclass_subgraph(const igraph_t *graph, igraph_vector_t *vids,
igraph_integer_t *isoclass);
```

This function is only implemented for subgraphs with three or four vertices.

Arguments:

 `graph`: The graph object. `vids`: A vector containing the vertex ids to be considered as a subgraph. Each vertex id should be included at most once. `isoclass`: Pointer to an integer, this will be set to the isomorphism class.

Returns:

 Error code.

Time complexity: O((d+n)*n), d is the average degree in the network, and n is the number of vertices in `vids`.

5.4. `igraph_isoclass_create` — Creates a graph from the given isomorphism class.

```int igraph_isoclass_create(igraph_t *graph, igraph_integer_t size,
igraph_integer_t number, igraph_bool_t directed);
```

This function is implemented only for graphs with three or four vertices.

Arguments:

 `graph`: Pointer to an uninitialized graph object. `size`: The number of vertices to add to the graph. `number`: The isomorphism class. `directed`: Logical constant, whether to create a directed graph.

Returns:

 Error code.