Skip to main content

isomorphic_bliss

Function isomorphic_bliss 

Source
pub fn isomorphic_bliss(
    graph1: &Graph,
    graph2: &Graph,
    vertex_color1: Option<&[u32]>,
    vertex_color2: Option<&[u32]>,
) -> IgraphResult<Vf2Isomorphism>
Expand description

Test whether two graphs are isomorphic via canonical labeling (BLISS).

Both graphs are reduced to their canonical form by the shared individualization-refinement engine (ALGO-ISO-003); they are isomorphic iff the canonical certificates (and, when colours are supplied, the colour sequence in canonical order) coincide. When they match, a concrete vertex mapping is recovered by composing the two canonical labelings.

Optional vertex_color1 / vertex_color2 slices restrict the matching: two vertices may correspond only if their colours are equal. Pass None for uncoloured graphs; supplying a colour for only one side makes that colour be ignored (matching upstream). Unlike VF2, self-loops are supported (BLISS folds a loop into the vertex invariant); multi-edges are rejected.

On success Vf2Isomorphism::iso tells whether a mapping exists; when it does, map12 / map21 hold the permutation taking graph1 to graph2 and its inverse, otherwise they are empty.

§Errors

Returns IgraphError::InvalidArgument if the two graphs differ in directedness or if a supplied colour vector has the wrong length, and IgraphError::Unsupported if either graph has multiple edges.

§Examples

use rust_igraph::{Graph, isomorphic_bliss};

// Two triangles with relabelled vertices are isomorphic.
let mut a = Graph::new(3, false).unwrap();
a.add_edge(0, 1).unwrap();
a.add_edge(1, 2).unwrap();
a.add_edge(2, 0).unwrap();
let mut b = Graph::new(3, false).unwrap();
b.add_edge(0, 2).unwrap();
b.add_edge(2, 1).unwrap();
b.add_edge(1, 0).unwrap();
let r = isomorphic_bliss(&a, &b, None, None).unwrap();
assert!(r.iso);
assert_eq!(r.map12.len(), 3);