Module isomorphism 

Graph isomorphism, motifs and graphlets (igraph_isomorphism.h, igraph_motifs.h, igraph_graphlets.h).

Two graphs are isomorphic when they become indistinguishable once their vertex labels are removed, i.e. when a bijection between their vertex sets maps the edges of one onto the edges of the other. This module wraps the four families of isomorphism tools of igraph:

• the generic entry points Graph::isomorphic and Graph::subisomorphic, which pick a suitable algorithm by themselves;
• VF2 (Foggia, Sansone and Vento, 2001), which supports vertex and edge colors, arbitrary compatibility predicates written as Rust closures, counting and listing of all (sub)isomorphisms, and streaming them to a closure that can stop the search early; configure it with Vf2Options;
• Bliss (Junttila and Kaski), a successor of NAUTY, which computes canonical labelings and automorphism groups, and reports the size of the automorphism group exactly, as a decimal string (see BlissInfo and the splitting heuristics BlissSh);
• LAD (Solnon, 2010) for (induced) subgraph isomorphism with per-vertex domains.

In addition, all directed graphs on 3–4 vertices and all undirected graphs on 3–6 vertices are numbered by isomorphism classes (Graph::isoclass, Graph::isoclass_create, graph_count), which are used by the motif finder (Graph::motifs_randesu, FANMOD’s RAND-ESU algorithm), and the module also provides the dyad and triad censuses, triangle listing and counting, and the graphlet decomposition of weighted graphs (Azari Soufiani and Airoldi).

VF2 and Bliss only support simple graphs (Bliss tolerates self-loops); use Graph::simplify_and_colorize to encode multi-edges and self-loops as edge and vertex colors first, as Graph::isomorphic does automatically.

Example

use igraph::prelude::*;
use igraph::isomorphism::{BlissSh, Vf2Options};

// A 4-cycle, and the same cycle with scrambled labels.
let c4 = Graph::ring(4, false, false, true).unwrap();
let scrambled = c4.permute_vertices(&[2, 0, 3, 1]).unwrap();
assert!(c4.isomorphic(&scrambled).unwrap());

// VF2 also returns a witness mapping ...
let m = c4.isomorphic_vf2(&scrambled, &mut Vf2Options::new()).unwrap().unwrap();
for (u, v) in c4.edge_list() {
    let (a, b) = (m.map12[u as usize], m.map12[v as usize]);
    assert!(scrambled.get_eid(a, b, false).unwrap().is_some());
}
// ... and counts them: the dihedral group of the square has 8 elements.
assert_eq!(c4.count_isomorphisms_vf2(&scrambled, &mut Vf2Options::new()).unwrap(), 8);
assert_eq!(c4.count_automorphisms(None).unwrap(), 8.0);

// A path on 3 vertices occurs 4 times in C4 as an induced subgraph (motif).
let hist = c4.motifs_randesu(3, None).unwrap();
assert!(hist[0].is_nan() && hist[1].is_nan()); // disconnected classes
assert_eq!(&hist[2..], &[4.0, 0.0]);

// The Petersen graph has 120 symmetries, and Bliss reports them exactly.
let petersen = Graph::famous("Petersen").unwrap();
let info = petersen.count_automorphisms_bliss(None, BlissSh::Fl).unwrap();
assert_eq!(info.group_size, "120");

Provided functionality

Rust	C function	What
Graph::isomorphic	igraph_isomorphic	automatic isomorphism test
Graph::subisomorphic	igraph_subisomorphic	automatic subgraph isomorphism test
Graph::isomorphic_vf2	igraph_isomorphic_vf2	VF2 test with mapping
Graph::count_isomorphisms_vf2	igraph_count_isomorphisms_vf2	count isomorphisms
Graph::get_isomorphisms_vf2	igraph_get_isomorphisms_vf2	list isomorphisms
Graph::get_isomorphisms_vf2_callback	igraph_get_isomorphisms_vf2_callback	stream isomorphisms to a closure
Graph::subisomorphic_vf2	igraph_subisomorphic_vf2	VF2 subgraph test with mapping
Graph::count_subisomorphisms_vf2	igraph_count_subisomorphisms_vf2	count subgraph isomorphisms
Graph::get_subisomorphisms_vf2	igraph_get_subisomorphisms_vf2	list subgraph isomorphisms
Graph::get_subisomorphisms_vf2_callback	igraph_get_subisomorphisms_vf2_callback	stream subgraph isomorphisms
Graph::subisomorphic_lad, Graph::get_subisomorphisms_lad	igraph_subisomorphic_lad	LAD, with domains and induced mode
Graph::isomorphic_bliss	igraph_isomorphic_bliss	Bliss test with mapping and statistics
Graph::canonical_permutation, Graph::canonical_permutation_bliss	igraph_canonical_permutation(_bliss)	canonical labeling
Graph::canonical_form	(canonical labeling + igraph_permute_vertices)	canonical representative
Graph::count_automorphisms, Graph::count_automorphisms_bliss	igraph_count_automorphisms(_bliss)	automorphism group size
Graph::automorphism_group, Graph::automorphism_group_bliss	igraph_automorphism_group(_bliss)	automorphism group generators
Graph::simplify_and_colorize	igraph_simplify_and_colorize	multigraph → colored simple graph
invert_permutation	igraph_invert_permutation	inverse of a permutation
Graph::isoclass, Graph::isoclass_subgraph	igraph_isoclass(_subgraph)	isomorphism class of small graphs
Graph::isoclass_create	igraph_isoclass_create	representative of an isomorphism class
graph_count	igraph_graph_count	number of unlabeled graphs
Graph::motifs_randesu	igraph_motifs_randesu	motif histogram
Graph::motifs_randesu_callback	igraph_motifs_randesu_callback	stream motifs to a closure
Graph::motifs_randesu_no	igraph_motifs_randesu_no	number of connected subgraphs
Graph::motifs_randesu_estimate	igraph_motifs_randesu_estimate	estimate of the above
Graph::dyad_census	igraph_dyad_census	mutual / asymmetric / null dyads
Graph::triad_census	igraph_triad_census	the 16 MAN triad types
Graph::count_triangles, Graph::count_adjacent_triangles, Graph::list_triangles	igraph_count_triangles, …	triangles
Graph::graphlets, Graph::graphlets_candidate_basis, Graph::graphlets_project	igraph_graphlets*	graphlet decomposition

See also

• Graph::is_same_graph tests labeled equality (same vertex ids and edges), while this module tests equality up to relabeling; Graph::permute_vertices relabels a graph.
• Graph::famous, Graph::full, Graph::ring and Graph::lcf build the classic symmetric graphs used as test cases here; rng::seed makes random relabelings and motif sampling reproducible (per thread).
• The cliques module (complete subgraphs, used by the graphlet decomposition), and the transitivity measures of mixing, e.g. Graph::transitivity_undirected, which are ratios of triangle counts.
• Graph::reciprocity summarizes the dyad census in one number.
• Graph::simplify and Graph::count_multiple for dealing with multigraphs without encoding them as colors.

Structs

BlissInfo

Statistics of a Bliss run (igraph_bliss_info_t).

BlissIsomorphism

Result of Graph::isomorphic_bliss.

ColorizedGraph

Result of Graph::simplify_and_colorize: a colored simple graph that encodes a multigraph.

DyadCensus

The dyad census of a graph, see Graph::dyad_census.

GraphletBasis

A graphlet basis with thresholds, see Graph::graphlets_candidate_basis.

Graphlets

A graphlet decomposition, see Graph::graphlets.

IsoMapping

An isomorphism (or subgraph isomorphism) between two graphs, as a pair of mutually inverse vertex maps.

TriadCensus

The triad census of a graph, see Graph::triad_census.

Vf2Options

Options of the VF2 functions: vertex and edge colors, and custom compatibility predicates.

Enums

BlissSh

Splitting heuristics of Bliss (igraph_bliss_sh_t).

MotifSample

How Graph::motifs_randesu_estimate chooses the sample of vertices.

Functions

graph_count

The number of unlabeled simple graphs on n vertices (igraph_graph_count).

invert_permutation

Inverts a permutation of 0..n (igraph_invert_permutation).

Type Aliases

CompatFn

A vertex or edge compatibility predicate for VF2: it receives the id of a vertex (edge) of the first graph and one of the second graph, and tells whether they may be matched.