Graph Isomorphism

The same group on the Doxygen site.

group Graph Isomorphism

Algorithms for testing (sub)graph isomorphism.

This group contains algorithms for finding isomorph copies of a given graph in another one, or simply check whether two graphs are isomorphic.

The formal definition of subgraph isomorphism is as follows.

We are given two graphs, \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\). A function \(f:V_1\longrightarrow V_2\) is called mapping or embedding if \(f(u)\neq f(v)\) whenever \(u\neq v\).

The standard Subgraph Isomorphism Problem (SIP) looks for a mapping with the property that whenever \((u,v)\in E_1\), then \((f(u),f(v))\in E_2\).

In case of Induced Subgraph Isomorphism Problem (ISIP) one also requires that if \((u,v)\not\in E_1\), then \((f(u),f(v))\not\in E_2\)

In addition, the graph nodes may be labeled, i.e. we are given two node labelings \(l_1:V_1\longrightarrow L\) and \(l_2:V_2\longrightarrow L\) and we require that \(l_1(u)=l_2(f(u))\) holds for all nodes \(u \in G_1\).

Classes

Class

Description

Vf2

VF2 algorithm class.

Vf2pp

VF2 Plus Plus algorithm class [24].

Functions and other members

enum MappingType

The VF2 algorithm is capable of finding different kind of graph embeddings, this enum specifies their types.

See Graph Isomorphism for a more detailed description.

Values:

enumerator SUBGRAPH

Subgraph isomorphism.

enumerator INDUCED

Induced subgraph isomorphism.

enumerator ISOMORPH

Graph isomorphism

If the two graphs have the same number of nodes, than it is equivalent to INDUCED, and if they also have the same number of edges, then it is also equivalent to SUBGRAPH.

However, using this setting is faster than the other two options.

template< class G1 , class G2 >
Vf2Wizard< Vf2WizardBase< G1 , G2 > > vf2(
const G1 & g1,
const G2 & g2
)

Function-type interface for VF2 algorithm.

Function-type interface for VF2 algorithm [6].

This function has several named parameters declared as the members of class Vf2Wizard. The following examples show how to use these parameters.

// Find an embedding of graph g1 into graph g2
ListGraph::NodeMap< ListGraph::Node > m( g1 );
vf2( g1 , g2 ).mapping( m ).run();

// Check whether graphs g1 and g2 are isomorphic
bool is_iso = vf2( g1 , g2 ).iso().run();

// Count the number of isomorphisms
int num_isos = vf2( g1 , g2 ).iso().count();

// Iterate through all the induced subgraph mappings of graph g1 into g2
auto * myVf2 = vf2( g1 , g2 )
                 .mapping( m )
                 .nodeLabels( c1 , c2 )
                 .induced()
                 .getPtrToVf2Object();
while( myVf2->find() ) {
 //process the current mapping m
 }
delete myVf2;

See also

Vf2Wizard

See also

Vf2

Warning

Don’t forget to put the run(), count() or the getPtrToVf2Object() to the end of the expression.

template< class G1 , class G2 >
Vf2ppWizard< Vf2ppWizardBase< G1 , G2 > > vf2pp(
const G1 & g1,
const G2 & g2
)

Function-type interface for VF2 Plus Plus algorithm.

This function has several named parameters declared as the members of class Vf2ppWizard. The following examples show how to use these parameters.

ListGraph::NodeMap< ListGraph::Node > m( g1 );
// Find an embedding of graph g1 into graph g2
vf2pp( g1 , g2 ).mapping( m ).run();

// Check whether graphs g1 and g2 are isomorphic
bool is_iso = vf2pp( g1 , g2 ).iso().run();

// Count the number of isomorphisms
int num_isos = vf2pp( g1 , g2 ).iso().count();

// Iterate through all the induced subgraph mappings
// of graph g1 into g2 using the labels c1 and c2
auto * myVf2pp = vf2pp( g1 , g2 )
                   .mapping( m )
                   .nodeLabels( c1 , c2 )
                   .induced()
                   .getPtrToVf2ppObject();
while( myVf2pp->find() ) {
 //process the current mapping m
 }
delete myVf2pp;

See also

Vf2ppWizard

See also

Vf2pp

Warning

Don’t forget to put the run(), count() or the getPtrToVf2ppObject() to the end of the expression.