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().
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().
int igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2,
igraph_bool_t *iso);
In simple terms, two graphs are isomorphic if they become indistinguishable from each other once their vertex labels are removed (rendering the vertices within each graph indistiguishable). More precisely, two graphs are isomorphic if there is a one-to-one mapping from the vertices of the first one to the vertices of the second such that it transforms the edge set of the first graph into the edge set of the second. This mapping is called an isomorphism.
Currently, this function supports simple graphs and graphs with self-loops, but does not support multigraphs.
This function decides which graph isomorphism algorithm to be used 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 an error is triggered.
If the two graphs does not have the same number of vertices
and edges it returns with FALSE.
Otherwise, if the graphs have three or four vertices then an O(1) algorithm is used with precomputed data.
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:
|
The first graph. |
|
The second graph. |
|
Pointer to a logical variable, will be set to TRUE (1) if the two graphs are isomorphic, and FALSE (0) otherwise. |
Returns:
Error code. |
See also:
Time complexity: exponential.
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.
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 runigraph_canonical_permutation — Canonical permutation using Bliss.igraph_isomorphic_bliss — Graph isomorphism via Bliss.igraph_automorphisms — Number of automorphisms using Bliss.igraph_automorphism_group — Automorphism group generators using Bliss.Bliss is a successor of the famous NAUTY algorithm and implementation. While using the same ideas in general, with better heuristics and data structures Bliss outperforms NAUTY on most graphs.
Bliss was developed and implemented by Tommi Junttila and Petteri Kaski at Helsinki University of Technology, Finland. For more information, see the Bliss homepage at https://users.aalto.fi/~tjunttil/bliss/ and the following publication:
Tommi Junttila and Petteri Kaski: "Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs" In ALENEX 2007, pages 135–149, 2007 https://doi.org/10.1137/1.9781611972870.13
Tommi Junttila and Petteri Kaski: "Conflict Propagation and Component Recursion for 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 with self-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 reasonable
default choice. IGRAPH_BLISS_FSM is recommended for graphs that have some
combinatorial structure, and is the default of the Bliss library's command
line 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 stored here. It is useful if you wany to study the internal working of the algorithm.
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
|
See http://www.tcs.hut.fi/Software/bliss/index.html for details about the algorithm and these parameters.
int igraph_canonical_permutation(const igraph_t *graph, const igraph_vector_int_t *colors,
igraph_vector_t *labeling, igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
This function computes the vertex permutation which transforms
the graph into a canonical form, using the Bliss algorithm.
Two graphs have the same canonical form if and only if they
are isomorphic. Use igraph_is_same_graph() to compare
two 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:
igraph_is_same_graph() |
Time complexity: exponential, in practice it is fast for many graphs.
int 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_t *map12,
igraph_vector_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, a successor of the famous NAUTY algorithm and implementation. Bliss is open source and licensed according to the GNU LGPL. See https://users.aalto.fi/~tjunttil/bliss/ for details. Currently the 0.75 version of Bliss is included in igraph.
Isomorphism testing is implemented by producing the canonical form
of both graphs using igraph_canonical_permutation() and
comparing 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.
int igraph_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. 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:
|
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.
int igraph_automorphism_group(
const igraph_t *graph, const igraph_vector_int_t *colors, igraph_vector_ptr_t *generators,
igraph_bliss_sh_t sh, igraph_bliss_info_t *info);
The generators of the automorphism group of a graph are computed using Bliss. The generator set may not be minimal and may depend on the splitting heuristics. The generators are permutations represented using 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 pointer vector. It will
contain pointers to |
|
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_isomorphic_vf2 — Isomorphism via VF2igraph_count_isomorphisms_vf2 — Number of isomorphisms via VF2igraph_get_isomorphisms_vf2 — Collect all isomorphic mappings of two graphs.igraph_isohandler_t — Callback type, called when an isomorphism was foundigraph_isocompat_t — Callback type, called to check whether two vertices or edges are compatibleigraph_isomorphic_function_vf2 — The generic VF2 interfaceigraph_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_subisomorphic_function_vf2 — Generic VF2 function for subgraph isomorphism problemsThe VF2 algorithm can search for a subgraph in a larger graph, or check if two graphs are isomorphic. 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.
VF2 supports both vertex and edge-colored graphs, as well as custom vertex or edge compatibility 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 VF2 functions do not check that the input graph is simple: it is the responsibility of the user to pass in valid input.
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:
|
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 logical 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. 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 it under the terms of the GNU General Public License as published by 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> 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; igraph_rng_seed(igraph_rng_default(), 12345); igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/1); igraph_vector_init_seq(&perm, 0, igraph_vcount(&ring1) - 1); igraph_vector_shuffle(&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)[(long int)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 %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)[(long int)VECTOR(perm)[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)[0] = 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)[0] = 1; VECTOR(color1)[1] = 1; VECTOR(color2)[0] = 1; VECTOR(color2)[((long int)VECTOR(perm)[1] + 1) % igraph_vcount(&ring2)] = 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); igraph_vector_shuffle(&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)[0] = 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)[0] = 1; VECTOR(color1)[1] = 1; VECTOR(color2)[0] = 1; VECTOR(color2)[2] = 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; }
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:
|
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. |
Time complexity: exponential.
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 simple
graphs. It uses the igraph_isomorphic_function_vf2()
function. Call the function with the same graph as graph1 and graph2 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 vector. 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.
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:
|
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:
Boolean, whether to continue with the isomorphism search. |
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:
|
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) |
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. The callback function must not destroy the
mapping 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.
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:
|
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.
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:
|
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.
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. 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 vector. 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.
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:
|
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.
The LAD algorithm can search for a subgraph in a larger graph, or check if two graphs are isomorphic. See Christine Solnon: AllDifferent-based Filtering for Subgraph Isomorphism. Artificial Intelligence, 174(12-13):850-864, 2010. https://doi.org/10.1016/j.artint.2010.05.002 as well as the homepage of the LAD library at http://liris.cnrs.fr/csolnon/LAD.html The implementation in igraph is based on LADv1, but it is modified to use igraph's own memory allocation and error handling.
LAD uses the concept of domains to indicate vertex compatibility when matching the pattern 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.
int igraph_subisomorphic_lad(const igraph_t *pattern, const igraph_t *target,
const 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 LAD 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, 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. |
|
A pointer vector, or a null pointer. If a pointer
vector, then it must contain pointers to |
|
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. |
|
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 vector or a null pointer. If not a null
pointer, then all subgraph isomorphisms are stored in the
pointer vector, 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. 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 it under the terms of the GNU General Public License as published by 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> /* This test counts motifs using LAD and compares the results with * the RANDESU motif finder */ void test_k_motifs(const igraph_t *graph, const int k, const int class_count, igraph_bool_t directed) { igraph_vector_t randesu_counts, lad_counts; igraph_vector_t cut_prob; igraph_bool_t equal; int i, n; igraph_integer_t vcount; igraph_real_t expected_count; vcount = igraph_vcount(graph); n = class_count; igraph_vector_init(&lad_counts, n); for (i = 0; i < n; i++) { igraph_t pattern; igraph_vector_ptr_t maps; igraph_integer_t nAutomorphisms; igraph_isoclass_create(&pattern, k, i, directed); igraph_vector_ptr_init(&maps, 0); igraph_subisomorphic_lad(&pattern, graph, NULL, NULL, NULL, &maps, /* induced = */ 1, 0); igraph_count_subisomorphisms_vf2(&pattern, &pattern, NULL, NULL, NULL, NULL, &nAutomorphisms, NULL, NULL, NULL); VECTOR(lad_counts)[i] = igraph_vector_ptr_size(&maps) / nAutomorphisms; IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(&maps, igraph_vector_destroy); igraph_vector_ptr_destroy_all(&maps); igraph_destroy(&pattern); } igraph_vector_init(&cut_prob, k); igraph_vector_init(&randesu_counts, 0); igraph_motifs_randesu(graph, &randesu_counts, k, &cut_prob); equal = 1 /* true */; for (i = 0; i < n; i++) { if (igraph_is_nan(VECTOR(randesu_counts)[i])) { continue; } if (VECTOR(randesu_counts)[i] != VECTOR(lad_counts)[i]) { equal = 0; break; } } if (! equal) { printf("LAD %s %d-motif count does not agree with RANDESU.\n", directed ? "directed" : "undirected", k); } expected_count = 1; for (i = 0; i < k; i++) { expected_count *= (vcount - i); } for (i = 0; i < k; i++) { expected_count /= (i + 1); } if (igraph_vector_sum(&lad_counts) != expected_count) { printf("Total %d-vertex %s subgraph count is incorrect.\n", k, directed ? "directed" : "undirected"); } igraph_vector_destroy(&randesu_counts); igraph_vector_destroy(&lad_counts); igraph_vector_destroy(&cut_prob); } void test_motifs() { igraph_t graph; igraph_rng_seed(igraph_rng_default(), 42); igraph_erdos_renyi_game_gnm(&graph, 30, 400, /* directed = */ 1, /* loops = */ 0); test_k_motifs(&graph, 3, 16, /* directed= */ 1); /* there are 16 size-3 directed graphs */ test_k_motifs(&graph, 4, 218, /* directed= */ 1); /* there are 218 size-4 directed graphs */ igraph_destroy(&graph); } void test_motifs_undirected() { igraph_t graph; igraph_rng_seed(igraph_rng_default(), 137); igraph_erdos_renyi_game_gnm(&graph, 18, 100, /* directed = */ 0, /* loops = */ 0); test_k_motifs(&graph, 3, 4, /* directed= */ 0); /* there are 4 size-3 undirected graphs */ test_k_motifs(&graph, 4, 11, /* directed= */ 0); /* there are 11 size-4 undirected graphs */ igraph_destroy(&graph); /* Use a smaller graph so that the test would not take too long. */ igraph_erdos_renyi_game_gnm(&graph, 9, 36, /* directed = */ 0, /* loops = */ 0); test_k_motifs(&graph, 5, 34, /* directed= */ 0); /* there are 34 size-5 undirected graphs */ test_k_motifs(&graph, 6, 156, /* directed= */ 0); /* there are 156 size-6 undirected graphs */ igraph_destroy(&graph); } int main() { igraph_t target, pattern; igraph_bool_t iso; igraph_vector_t map; igraph_vector_ptr_t maps; int i, n, result; 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); printf("---------\n"); igraph_vector_init(&map, 0); igraph_vector_ptr_init(&maps, 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, 0, IGRAPH_DIRECTED, -1); igraph_set_error_handler(igraph_error_handler_ignore); result = igraph_subisomorphic_lad(&pattern, &target, /*domains=*/ 0, &iso, &map, &maps, /*induced=*/ 0, /*time_limit=*/ 0); igraph_set_error_handler(igraph_error_handler_abort); if (result != IGRAPH_EINVAL) { return 4; } igraph_destroy(&pattern); igraph_small(&pattern, 0, IGRAPH_UNDIRECTED, -1); igraph_subisomorphic_lad(&pattern, &target, /*domains=*/ 0, &iso, &map, &maps, /*induced=*/ 0, /*time_limit=*/ 0); if (!iso) { return 5; } if (igraph_vector_size(&map) != 0) { return 6; } if (igraph_vector_ptr_size(&maps) != 0) { return 7; } igraph_destroy(&pattern); igraph_destroy(&target); igraph_vector_destroy(&map); igraph_vector_ptr_destroy(&maps); test_motifs(); test_motifs_undirected(); return 0; }
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. Multi-edges and self-loops are ignored by this function.
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).
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 contains the edgeless graph. The last isomorphism class contains the full graph. The number of isomorphism classes 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). For 5 and 6 vertex undirected graphs, it is 34 and 156, respectively. For more information, see https://oeis.org/A000273 and https://oeis.org/A000088.
At the moment, 3- and 4-vertex directed graphs and 3 to 6 vertex undirected 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 graphs with three of four vertices.
Time complexity: O(|E|), the number of edges in the graph.
int igraph_isoclass_subgraph(const igraph_t *graph, const igraph_vector_t *vids,
igraph_integer_t *isoclass);
This function identifies the isomorphism class of the subgraph
induced the vertices specified in vids.
At the moment, 3- and 4-vertex directed graphs and 3 to 6 vertex undirected 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 in vids.
int 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 the given isomorphism class.
The isomorphism class is an integer between 0 and the number of
unique unlabeled (i.e. non-isomorphic) graphs on the given number
of vertices and give directedness. See https://oeis.org/A000273
and https://oeis.org/A000088 for the number of directed and
undirected graphs on size nodes.
At the moment, 3- and 4-vertex directed graphs and 3 to 6 vertex undirected graphs are supported.
Arguments:
|
Pointer to an uninitialized graph object. |
|
The number of vertices to add to the graph. |
|
The isomorphism class. |
|
Logical constant, whether to create a directed graph. |
Returns:
Error code. |
See also:
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph to create.
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:
|
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. 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.
int 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 input graph. The vertex colors are computed as the number of incident self-loops to each vertex in the input graph. The edge colors are computed as the number of parallel edges in the input graph that were merged to create each edge in the simple graph.
The resulting colored simple graph is suitable for use by isomorphism checking algorithms such as VF2, which only support simple graphs, but can consider vertex 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:
| ← Chapter 16. Cliques and independent vertex sets | Chapter 18. Graph coloring → |