For using the igraph C library
igraph provides four set of functions to deal with graphisomorphism problems.
Theigraph_isomorphic() andigraph_subisomorphic()functions make up the first set (in addition with theigraph_permute_vertices() function). These functions choose thealgorithm which is best for the supplied input graph. (The choice isnot very sophisticated though, see their documentation fordetails.)
The VF2 graph (and subgraph) isomorphism algorithm is implemented inigraph, these functions are the second set. Seeigraph_isomorphic_vf2() andigraph_subisomorphic_vf2() forstarters.
Functions for the Bliss algorithm constitute the third set,seeigraph_isomorphic_bliss().
Finally, the isomorphism classes of all directed graphs with three andfour vertices and all undirected graphs with 3-6 vertices are precomputedand stored in igraph, so for these small graphs there is a separate fastpath in the code that does not use more complex, generic isomorphismalgorithms.
igraph_error_t igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2, igraph_bool_t *iso);
In simple terms, two graphs are isomorphic if they become indistinguishablefrom each other once their vertex labels are removed (rendering the verticeswithin each graph indistiguishable). More precisely, two graphs are isomorphicif there is a one-to-one mapping from the vertices of the first oneto the vertices of the second such that it transforms the edge set of thefirst graph into the edge set of the second. This mapping is calledanisomorphism.
This function decides which graph isomorphism algorithm to beused based on the input graphs. Right now it does the following:
If one graph is directed and the other undirected then an error is triggered.
If one of the graphs has multi-edges then both graphs are simplified and colorized usingigraph_simplify_and_colorize() and sent to VF2.
If the two graphs does not have the same number of vertices and edges it returns withfalse.
Otherwise, if theigraph_isoclass() function supports both graphs (which is true for directed graphs with 3 and 4 vertices, and undirected graphs with 3-6 vertices), an O(1) algorithm is used with precomputed data.
Otherwise Bliss is used, seeigraph_isomorphic_bliss().
Please call the VF2 and Bliss functions directly if you needsomething more sophisticated, e.g. you need the isomorphic mapping.
Arguments:
| The first graph. |
| The second graph. |
| Pointer to a Boolean variable, will be set to |
Returns:
Error code. |
See also:
Time complexity: exponential.
igraph_error_t igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2, igraph_bool_t *iso);
Check whethergraph2 is isomorphic to a subgraph ofgraph1.Currently this function just callsigraph_subisomorphic_vf2()for all graphs.
Currently this function does not support non-simple graphs.
Arguments:
| The first input graph, may be directed or undirected. This is supposed to be the bigger graph. |
| The second input graph, it must have the same directedness as |
| Pointer to a boolean, the result is stored here. |
Returns:
Error code. |
Time complexity: exponential.
igraph_bliss_sh_t — Splitting heuristics for Bliss.igraph_bliss_info_t — Information about a Bliss run.igraph_canonical_permutation — Canonical permutation using Bliss.igraph_isomorphic_bliss — Graph isomorphism via Bliss.igraph_count_automorphisms — Number of automorphisms using Bliss.igraph_automorphism_group — Automorphism group generators using Bliss.Bliss is a successor of the famous NAUTY algorithm andimplementation. While using the same ideas in general, with betterheuristics and data structures Bliss outperforms NAUTY on mostgraphs.
Bliss was developed and implemented by Tommi Junttila and Petteri Kaski atHelsinki University of Technology, Finland. For more information,see the Bliss homepage athttps://users.aalto.fi/~tjunttil/bliss/ and the followingpublication:
Tommi Junttila and Petteri Kaski: "Engineering an Efficient Canonical LabelingTool for Large and Sparse Graphs" In ALENEX 2007, pages 135–149, 2007https://doi.org/10.1137/1.9781611972870.13
Tommi Junttila and Petteri Kaski: "Conflict Propagation and Component Recursionfor Canonical Labeling" in TAPAS 2011, pages 151–162, 2011.https://doi.org/10.1007/978-3-642-19754-3_16
Bliss works with both directed graphs and undirected graphs. It supports graphs withself-loops, but not graphs with multi-edges.
Bliss version 0.75 is included in igraph.
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;IGRAPH_BLISS_FL provides good performance for many graphs, and is a reasonabledefault choice.IGRAPH_BLISS_FSM is recommended for graphs that have somecombinatorial structure, and is the default of the Bliss library's commandline tool.
Values:
| First non-singleton cell. |
| First largest non-singleton cell. |
| First smallest non-singleton cell. |
| First maximally non-trivially connected non-singleton cell. |
| Largest maximally non-trivially connected non-singleton cell. |
| Smallest maximally non-trivially connected non-singletion cell. |
typedef struct igraph_bliss_info_t { unsigned long nof_nodes; unsigned long nof_leaf_nodes; unsigned long nof_bad_nodes; unsigned long nof_canupdates; unsigned long nof_generators; unsigned long max_level; char *group_size;} igraph_bliss_info_t;Some secondary information found by the Bliss algorithm is storedhere. It is useful if you wany to study the internal working of thealgorithm.
Values:
| The number of nodes in the search tree. |
| The number of leaf nodes in the search tree. |
| Number of bad nodes. |
| Number of canrep updates. |
| Number of generators of the automorphism group. |
| Maximum level. |
| The size of the automorphism group of the graph, given as a string. It should be deallocated via |
Seehttps://users.aalto.fi/~tjunttil/bliss/for details about the algorithm and these parameters.
igraph_error_t igraph_canonical_permutation(const igraph_t *graph, const igraph_vector_int_t *colors, igraph_vector_int_t *labeling, igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
This function computes the vertex permutation which transformsthe graph into a canonical form, using the Bliss algorithm.Two graphs have the same canonical form if and only if theyare isomorphic. Useigraph_is_same_graph() to comparetwo canonical forms.
Arguments:
| The input graph. Multiple edges between the same nodes are not supported and will cause an incorrect result to be returned. |
| An optional vertex color vector for the graph. Supply a null pointer is the graph is not colored. |
| 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. |
| The splitting heuristics to be used in Bliss. See |
| If not |
Returns:
Error code. |
See also:
Time complexity: exponential, in practice it is fast for many graphs.
igraph_error_t igraph_isomorphic_bliss(const igraph_t *graph1, const igraph_t *graph2, const igraph_vector_int_t *colors1, const igraph_vector_int_t *colors2, igraph_bool_t *iso, igraph_vector_int_t *map12, igraph_vector_int_t *map21, igraph_bliss_sh_t sh, igraph_bliss_info_t *info1, igraph_bliss_info_t *info2);
This function uses the Bliss graph isomorphism algorithm, asuccessor of the famous NAUTY algorithm and implementation. Blissis open source and licensed according to the GNU LGPL. Seehttps://users.aalto.fi/~tjunttil/bliss/ fordetails. Currently the 0.75 version of Bliss is included in igraph.
Isomorphism testing is implemented by producing the canonical formof both graphs usingigraph_canonical_permutation() andcomparing them.
Arguments:
| The first input graph. Multiple edges between the same nodes are not supported and will cause an incorrect result to be returned. |
| The second input graph. Multiple edges between the same nodes are not supported and will cause an incorrect result to be returned. |
| An optional vertex color vector for the first graph. Supply a null pointer if your graph is not colored. |
| An optional vertex color vector for the second graph. Supply a null pointer if your graph is not colored. |
| Pointer to a boolean, the result is stored here. |
| A vector or |
| Similar to |
| Splitting heuristics to be used for the graphs. See |
| If not |
| Same as |
Returns:
Error code. |
Time complexity: exponential, but in practice it is quite fast.
igraph_error_t igraph_count_automorphisms(const igraph_t *graph, const igraph_vector_int_t *colors, igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
The number of automorphisms of a graph is computed using Bliss. Theresult is returned as part of theinfo structure, in taggroup_size. It is returned as a string, as it can be very high evenfor relatively small graphs. See alsoigraph_bliss_info_t.
Arguments:
| The input graph. Multiple edges between the same nodes are not supported and will cause an incorrect result to be returned. |
| An optional vertex color vector for the graph. Supply a null pointer is the graph is not colored. |
| The splitting heuristics to be used in Bliss. See |
| The result is stored here, in particular in the |
Returns:
Error code. |
Time complexity: exponential, in practice it is fast for many graphs.
igraph_error_t igraph_automorphism_group( const igraph_t *graph, const igraph_vector_int_t *colors, igraph_vector_int_list_t *generators, igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
The generators of the automorphism group of a graph are computedusing Bliss. The generator set may not be minimal and may depend onthe splitting heuristics. The generators are permutations representedusing zero-based indexing.
Arguments:
| The input graph. Multiple edges between the same nodes are not supported and will cause an incorrect result to be returned. |
| An optional vertex color vector for the graph. Supply a null pointer is the graph is not colored. |
| Must be an initialized interger vector list. The generators of the automorphism group will be stored here. |
| The splitting heuristics to be used in Bliss. See |
| If not |
Returns:
Error code. |
Time complexity: exponential, in practice it is fast for many graphs.
igraph_error_t igraph_automorphisms(const igraph_t *graph, const igraph_vector_int_t *colors, igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
Deprecated since version 0.10.5. Please do not use this function in newcode; useigraph_count_automorphisms()instead.
igraph_isomorphic_vf2 — Isomorphism via VF2.igraph_count_isomorphisms_vf2 — Number of isomorphisms via VF2.igraph_get_isomorphisms_vf2 — Collect all isomorphic mappings of two graphs.igraph_get_isomorphisms_vf2_callback — The generic VF2 interfaceigraph_isohandler_t — Callback type, called when an isomorphism was foundigraph_isocompat_t — Callback type, called to check whether two vertices or edges are compatibleigraph_subisomorphic_vf2 — Decide subgraph isomorphism using VF2igraph_count_subisomorphisms_vf2 — Number of subgraph isomorphisms using VF2igraph_get_subisomorphisms_vf2 — Return all subgraph isomorphic mappings.igraph_get_subisomorphisms_vf2_callback — Generic VF2 function for subgraph isomorphism problems.The VF2 algorithm can search for a subgraph in a larger graph, or check if twographs are isomorphic. See P. Foggia, C. Sansone, M. Vento, An Improved algorithm formatching large graphs, Proc. of the 3rd IAPR-TC-15 InternationalWorkshop on Graph-based Representations, Italy, 2001.
VF2 supports both vertex and edge-colored graphs, as well as custom vertex or edgecompatibility functions.
VF2 works with both directed and undirected graphs. Only simple graphs are supported.Self-loops or multi-edges must not be present in the graphs. Currently, the VF2functions do not check that the input graph is simple: it is the responsibilityof the user to pass in valid input.
igraph_error_t 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_int_t *map12, igraph_vector_int_t *map21, igraph_isocompat_t *node_compat_fn, igraph_isocompat_t *edge_compat_fn, void *arg);
This function performs the VF2 algorithm via callingigraph_get_isomorphisms_vf2_callback().
Note that this function cannot be used fordeciding subgraph isomorphism, useigraph_subisomorphic_vf2()for that.
Arguments:
| The first graph, may be directed or undirected. |
| The second graph. It must have the same directedness as |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Pointer to a Boolean constant, the result of the algorithm will be placed here. |
| Pointer to an initialized vector or a NULL pointer. If not a NULL pointer then the mapping from |
| Pointer to an initialized vector or a NULL pointer. If not a NULL pointer then the mapping from |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
See also:
Time complexity: exponential, what did you expect?
Example 17.1. Fileexamples/simple/igraph_isomorphic_vf2.c
#include <igraph.h>#include <stdio.h>#include <stdlib.h>intmain(void) { igraph_t ring1, ring2; igraph_vector_int_t color1, color2; igraph_vector_int_t perm; igraph_bool_t iso; igraph_integer_t count; igraph_integer_t i;igraph_rng_seed(igraph_rng_default(), 12345);igraph_ring(&ring1, 100,/*directed=*/ 0,/*mutual=*/ 0,/*circular=*/1);igraph_vector_int_init_range(&perm, 0,igraph_vcount(&ring1));igraph_vector_int_shuffle(&perm);igraph_permute_vertices(&ring1, &ring2, &perm);/* 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 1; }/* Two colors, just counting */for (i = 0; i <igraph_vector_int_size(&color1); i += 2) {VECTOR(color1)[i] =VECTOR(color2)[VECTOR(perm)[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 100, got %" IGRAPH_PRId ".\n", count);return 2; }igraph_destroy(&ring1);igraph_destroy(&ring2);igraph_vector_int_destroy(&color2);igraph_vector_int_destroy(&perm);/* Two colors, count subisomorphisms */igraph_ring(&ring1, 100,/*directed=*/ 0,/*mutual=*/ 0,/*circular=*/0);igraph_ring(&ring2, 80,/*directed=*/ 0,/*mutual=*/ 0,/*circular=*/0);igraph_vector_int_init(&color2,igraph_vcount(&ring2));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 21, got %" IGRAPH_PRId ".\n", count);return 3; }igraph_vector_int_destroy(&color1);igraph_vector_int_destroy(&color2);igraph_destroy(&ring1);igraph_destroy(&ring2);return 0;}
igraph_error_t 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 twographs. It uses the genericigraph_get_isomorphisms_vf2_callback()function.
Arguments:
| The first input graph, may be directed or undirected. |
| The second input graph, it must have the same directedness as |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Point to an integer, the result will be stored here. |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
See also:
igraph_count_automorphisms() |
Time complexity: exponential.
igraph_error_t 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_int_list_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 simplegraphs. It uses theigraph_get_isomorphisms_vf2_callback()function. Call the function with the same graph asgraph1 andgraph2 to get automorphisms.
Arguments:
| The first input graph, may be directed or undirected. |
| The second input graph, it must have the same directedness as |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Pointer to a list of integer vectors. On return it is empty if the input graphs are not isomorphic. Otherwise it contains pointers to |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
Time complexity: exponential.
igraph_error_t igraph_get_isomorphisms_vf2_callback( 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_int_t *map12, igraph_vector_int_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 formatching large graphs, Proc. of the 3rd IAPR-TC-15 InternationalWorkshop on Graph-based Representations, Italy, 2001.
For using it you need to define a callback function of typeigraph_isohandler_t. This function will be called whenever VF2finds an isomorphism between the two graphs. The mapping betweenthe two graphs will be also provided to this function. If thecallback returnsIGRAPH_SUCCESS, then the search is continued,otherwise it stops.IGRAPH_STOP as a return value can be used toindicate normal premature termination; any other return value will betreated as an igraph error code, making the caller function return thesame error code as well. The callback function must not destroy themapping vectors that are passed to it.
Arguments:
| The first input graph. |
| The second input graph. |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Pointer to an initialized vector or |
| This is the same as |
| The callback function to be called if an isomorphism is found. See also |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
Time complexity: exponential.
typedef igraph_error_t igraph_isohandler_t(const igraph_vector_int_t *map12, const igraph_vector_int_t *map21, void *arg);
See the details at the documentation ofigraph_get_isomorphisms_vf2_callback().
Arguments:
| The mapping from the first graph to the second. |
| The mapping from the second graph to the first, the inverse of |
| This extra argument was passed to |
Returns:
|
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 definingrelations on the vertices and/or edges of the graphs, and then checkingwhether the vertices (edges) match according to these relations.
This feature is implemented by two callbacks, one forvertices, 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 alogical value, giving whether the two vertices match.
Both callback functions are of typeigraph_isocompat_t.
Arguments:
| The first graph. |
| The second graph. |
| The id of a vertex or edge in the first graph. |
| The id of a vertex or edge in the second graph. |
| Extra argument to pass to the callback functions. |
Returns:
Logical scalar, whether vertex (or edge) |
igraph_error_t 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_int_t *map12, igraph_vector_int_t *map21, igraph_isocompat_t *node_compat_fn, igraph_isocompat_t *edge_compat_fn, void *arg);
Decides whether a subgraph ofgraph1 is isomorphic tograph2. It usesigraph_get_subisomorphisms_vf2_callback().
Arguments:
| The first input graph, may be directed or undirected. This is supposed to be the larger graph. |
| The second input graph, it must have the same directedness as |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Pointer to a boolean. The result of the decision problem is stored here. |
| Pointer to a vector or |
| Pointer to a vector ot |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
Time complexity: exponential.
igraph_error_t 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 ofgraph1 andgraph2. This function usesigraph_get_subisomorphisms_vf2_callback().
Arguments:
| The first input graph, may be directed or undirected. This is supposed to be the larger graph. |
| The second input graph, it must have the same directedness as |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Pointer to an integer. The number of subgraph isomorphisms is stored here. |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
Time complexity: exponential.
igraph_error_t 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_int_list_t *maps, igraph_isocompat_t *node_compat_fn, igraph_isocompat_t *edge_compat_fn, void *arg);
This function collects all isomorphic mappings ofgraph2 to asubgraph ofgraph1. It uses theigraph_get_subisomorphisms_vf2_callback() function. The graphs should be simple.
Arguments:
| The first input graph, may be directed or undirected. This is supposed to be the larger graph. |
| The second input graph, it must have the same directedness as |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Pointer to a list of integer vectors. On return it contains pointers to |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
Time complexity: exponential.
igraph_error_t igraph_get_subisomorphisms_vf2_callback( 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_int_t *map12, igraph_vector_int_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 ofigraph_get_isomorphisms_vf2_callback(),for subgraph isomorphism problems. It searches for subgraphs ofgraph1 which are isomorphic tograph2. When it founds anisomorphic mapping it calls the supplied callbackisohandler_fn.The mapping (and its inverse) and the additionalarg argumentare supplied to the callback.
Arguments:
| The first input graph, may be directed or undirected. This is supposed to be the larger graph. |
| The second input graph, it must have the same directedness as |
| 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. |
| An optional color vector for the second graph. See the previous argument for explanation. |
| 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. |
| The edge color vector for the second graph. |
| Pointer to a vector or |
| Pointer to a vector ot |
| A pointer to a function of type |
| A pointer to a function of type |
| A pointer to a function of type |
| Extra argument to supply to functions |
Returns:
Error code. |
Time complexity: exponential.
igraph_error_t 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_int_t *map12, igraph_vector_int_t *map21, igraph_isohandler_t *isohandler_fn, igraph_isocompat_t *node_compat_fn, igraph_isocompat_t *edge_compat_fn, void *arg);
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_get_isomorphisms_vf2_callback()instead.
igraph_error_t 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_int_t *map12, igraph_vector_int_t *map21, igraph_isohandler_t *isohandler_fn, igraph_isocompat_t *node_compat_fn, igraph_isocompat_t *edge_compat_fn, void *arg);
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_get_subisomorphisms_vf2_callback()instead.
The LAD algorithm can search for a subgraph in a larger graph, or checkif two graphs are isomorphic.See Christine Solnon: AllDifferent-based Filtering for SubgraphIsomorphism. Artificial Intelligence, 174(12-13):850-864, 2010.https://doi.org/10.1016/j.artint.2010.05.002as well as the homepage of the LAD library athttp://liris.cnrs.fr/csolnon/LAD.htmlThe implementation in igraph is based on LADv1, but it ismodified to use igraph's own memory allocation and error handling.
LAD uses the concept of domains to indicate vertex compatibility when matching thepattern graph. Domains can be used to implement matching of colored vertices.
LAD works with both directed and undirected graphs. Graphs with multi-edges are not supported.
igraph_error_t igraph_subisomorphic_lad(const igraph_t *pattern, const igraph_t *target, const igraph_vector_int_list_t *domains, igraph_bool_t *iso, igraph_vector_int_t *map, igraph_vector_int_list_t *maps, igraph_bool_t induced, igraph_integer_t time_limit);
Check whetherpattern is isomorphic to a subgraph ostarget.The original LAD implementation by Christine Solnon was used as thebasis of this code.
See more about LAD athttp://liris.cnrs.fr/csolnon/LAD.html and inChristine Solnon: AllDifferent-based Filtering for SubgraphIsomorphism. Artificial Intelligence, 174(12-13):850-864, 2010.https://doi.org/10.1016/j.artint.2010.05.002
Arguments:
| The smaller graph, it can be directed or undirected. |
| The bigger graph, it can be directed or undirected. |
| An integer vector list of |
| Pointer to a boolean, or a null pointer. If not a null pointer, then the boolean is set to |
| 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. |
| Pointer to a list of integer vectors or a null pointer. If not a null pointer, then all subgraph isomorphisms are stored in the vector list, in |
| Boolean, whether to search for induced matching subgraphs. |
| 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 |
See also:
|
Time complexity: exponential.
Example 17.2. Fileexamples/simple/igraph_subisomorphic_lad.c
#include <igraph.h>voidprint_maps(igraph_vector_int_t *map, igraph_vector_int_list_t *maps) { igraph_integer_t n, i;igraph_vector_int_print(map); n =igraph_vector_int_list_size(maps);for (i = 0; i < n; i++) { igraph_vector_int_t *v =igraph_vector_int_list_get_ptr(maps, i);igraph_vector_int_print(v); }igraph_vector_int_list_clear(maps);}intmain(void) { igraph_t target, pattern; igraph_bool_t iso; igraph_vector_int_t map; igraph_vector_int_list_t maps; igraph_integer_t i; 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_int_list_t domains; igraph_vector_int_t v;igraph_small(&target, 9, IGRAPH_UNDIRECTED, 0, 1, 0, 4, 0, 6, 1, 4, 1, 2, 2, 3, 3, 4, 3, 5, 3, 7, 3, 8, 4, 5, 4, 6, 5, 6, 5, 8, 7, 8, -1);igraph_small(&pattern, 5, IGRAPH_UNDIRECTED, 0, 1, 0, 4, 1, 4, 1, 2, 2, 3, 3, 4, -1);igraph_vector_int_init(&map, 0);igraph_vector_int_list_init(&maps, 0);igraph_subisomorphic_lad(&pattern, &target,/*domains=*/ NULL, &iso, &map, &maps,/*induced=*/ false,/*time_limit=*/ 0);if (!iso) {return 1; }print_maps(&map, &maps);printf("---------\n");igraph_subisomorphic_lad(&pattern, &target,/*domains=*/ NULL, &iso, &map, &maps,/*induced=*/ true,/*time_limit=*/ 0);if (!iso) {return 2; }print_maps(&map, &maps);printf("---------\n");igraph_vector_int_list_init(&domains, 0); i = 0;igraph_vector_int_init(&v, 0);while (1) {if (domainsvec[i] == -2) {break; }elseif (domainsvec[i] == -1) {igraph_vector_int_list_push_back_copy(&domains, &v);igraph_vector_int_clear(&v); }else {igraph_vector_int_push_back(&v, domainsvec[i]); } i++; }igraph_vector_int_destroy(&v);igraph_subisomorphic_lad(&pattern, &target, &domains, &iso, &map, &maps,/*induced=*/ false,/*time_limit=*/ 0);if (!iso) {return 3; }print_maps(&map, &maps);igraph_vector_int_list_destroy(&domains);igraph_vector_int_destroy(&map);igraph_vector_int_list_destroy(&maps);igraph_destroy(&pattern);igraph_destroy(&target);return 0;}
igraph_isoclass — Determine the isomorphism class of small graphs.igraph_isoclass_subgraph — The isomorphism class of a subgraph of a graph.igraph_isoclass_create — Creates a graph from the given isomorphism class.igraph_graph_count — The number of unlabelled graphs on the given number of vertices.igraph_error_t igraph_isoclass(const igraph_t *graph, igraph_integer_t *isoclass);
All graphs with a given number of vertices belong to a number ofisomorphism classes, with every graph in a given class beingisomorphic to each other.
This function gives the isomorphism class (a number) of agraph. Two graphs have the same isomorphism class if and only ifthey are isomorphic.
The first isomorphism class is numbered zero and it contains the edgelessgraph. The last isomorphism class contains the full graph. The number ofisomorphism classes for directed graphs with three vertices is 16(between 0 and 15), for undirected graph it is only 4. For graphswith four vertices it is 218 (directed) and 11 (undirected).For 5 and 6 vertex undirected graphs, it is 34 and 156, respectively.These values can also be retrieved usingigraph_graph_count().For more information, seehttps://oeis.org/A000273 andhttps://oeis.org/A000088.
At the moment, 3- and 4-vertex directed graphs and 3 to 6 vertexundirected graphs are supported.
Multi-edges and self-loops are ignored by this function.
Arguments:
| The graph object. |
| Pointer to an integer, the isomorphism class will be stored here. |
Returns:
Error code. |
See also:
Because of some limitations this function works only for graphswith three of four vertices.
Time complexity: O(|E|), the number of edges in the graph.
igraph_error_t igraph_isoclass_subgraph(const igraph_t *graph, const igraph_vector_int_t *vids, igraph_integer_t *isoclass);
This function identifies the isomorphism class of the subgraphinduced the vertices specified invids.
At the moment, 3- and 4-vertex directed graphs and 3 to 6 vertexundirected graphs are supported.
Multi-edges and self-loops are ignored by this function.
Arguments:
| The graph object. |
| A vector containing the vertex IDs to be considered as a subgraph. Each vertex ID should be included at most once. |
| Pointer to an integer, this will be set to the isomorphism class. |
Returns:
Error code. |
See also:
Time complexity: O((d+n)*n), d is the average degree in the network,and n is the number of vertices invids.
igraph_error_t igraph_isoclass_create(igraph_t *graph, igraph_integer_t size, igraph_integer_t number, igraph_bool_t directed);
This function creates the canonical representative graph of thegiven isomorphism class.
The isomorphism class is an integer between 0 and the number ofunique unlabeled (i.e. non-isomorphic) graphs on the given numberof vertices and give directedness. Seehttps://oeis.org/A000273andhttps://oeis.org/A000088 for the number of directed andundirected graphs onsize nodes.
At the moment, 3- and 4-vertex directed graphs and 3 to 6 vertexundirected graphs are supported.
Arguments:
| Pointer to an uninitialized graph object. |
| The number of vertices to add to the graph. |
| The isomorphism class. |
| Boolean constant, whether to create a directed graph. |
Returns:
Error code. |
See also:
Time complexity: O(|V|+|E|), the number of vertices plus the numberof edges in the graph to create.
igraph_error_t igraph_graph_count(igraph_integer_t n, igraph_bool_t directed, igraph_integer_t *count);
Gives the number of unlabelledsimple graphs on the specified number of vertices.The "isoclass" of a graph of this size is at most one less than this value.
This function is meant to be used in conjunction with isoclass and motif finderfunctions. It will only work for smalln values for which the result isrepresetable in anigraph_integer_t. For largern values, an overflowerror is raised.
Arguments:
| The number of vertices. |
| Boolean, whether to consider directed graphs. |
| Pointer to an integer, the result will be stored here. |
Returns:
Error code. |
See also:
Time complexity: O(1).
igraph_error_t igraph_invert_permutation(const igraph_vector_int_t *permutation, igraph_vector_int_t *inverse);
Produces the inverse ofpermutation intoinverse and at the same time it checksthat the permutation vector is valid, i.e. all indices are within range and there areno duplicate entries.
Arguments:
| A permutation vector containing 0-based integer indices. |
| An initialized vector. The inverse of |
Returns:
Error code. |
igraph_error_t igraph_permute_vertices(const igraph_t *graph, igraph_t *res, const igraph_vector_int_t *permutation);
This function creates a new graph from the input graph by permutingits vertices according to the specified mapping. Call this functionwith the output ofigraph_canonical_permutation() to createthe canonical form of a graph.
Arguments:
| The input graph. |
| Pointer to an uninitialized graph object. The new graph is created here. |
| The permutation to apply. Vertex 0 is mapped to the first element of the vector, vertex 1 to the second, etc. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in terms of the number ofvertices and edges.
igraph_error_t igraph_simplify_and_colorize( const igraph_t *graph, igraph_t *res, igraph_vector_int_t *vertex_color, igraph_vector_int_t *edge_color);
This function creates a vertex and edge colored simple graph from the inputgraph. The vertex colors are computed as the number of incident self-loopsto each vertex in the input graph. The edge colors are computed as the number ofparallel edges in the input graph that were merged to create each edgein the simple graph.
The resulting colored simple graph is suitable for use by isomorphism checkingalgorithms such as VF2, which only support simple graphs, but can considervertex and edge colors.
Arguments:
| The graph object, typically having self-loops or multi-edges. |
| An uninitialized graph object. The result will be stored here |
| Computed vertex colors corresponding to self-loop multiplicities. |
| Computed edge colors corresponding to edge multiplicities |
Returns:
Error code. |
See also:
igraph_error_t igraph_isomorphic_34( const igraph_t *graph1, const igraph_t *graph2, igraph_bool_t *iso);
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_isomorphic()instead.
If you really care about performance and youknow for sure that yourinput graphs are simple and have either 3 or 4 vertices for directed graphs,or 3-6 vertices for undirected graphs, you can compare their isomorphismclasses obtained fromigraph_isoclass() directly instead of callingigraph_isomorphic(); this saves the cost of checking whether the graphsdo not contain multiple edges or self-loops.
Arguments:
| The first input graph. |
| The second input graph. Must have the same directedness as |
| Pointer to a boolean, the result is stored here. |
Returns:
Error code. |
Time complexity: O(1).
| ← Chapter 16. Cliques and independent vertex sets | Chapter 18. Graph coloring → |