abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Graph Isomorphism

Algorithms for testing (sub)graph isomorphism. More...

Classes

class  Vf2< G1 , G2 , M , NEQ >
 VF2 algorithm class. More...
class  Vf2pp< G1 , G2 , M , M1 , M2 >
 VF2 Plus Plus algorithm class [24]. More...

Enumerations

enum  MappingType { SUBGRAPH = 0 , INDUCED = 1 , ISOMORPH = 2 }

Functions

template< class G1 , class G2 >
Vf2Wizard< Vf2WizardBase< G1 , G2 > > vf2 (const G1 &g1, const G2 &g2)
 Function-type interface for VF2 algorithm.
template< class G1 , class G2 >
Vf2ppWizard< Vf2ppWizardBase< G1 , G2 > > vf2pp (const G1 &g1, const G2 &g2)
 Function-type interface for VF2 Plus Plus algorithm.

Detailed Description

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\).

Enumeration Type Documentation

◆ 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.

Enumerator
SUBGRAPH 

Subgraph isomorphism.

INDUCED 

Induced subgraph isomorphism.

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.

Function Documentation

◆ vf2()

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

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;
Vf2Wizard< Vf2WizardBase< G1 , G2 > > vf2( const G1 & g1 , const G2 & g2 )
Function-type interface for VF2 algorithm.
Definition vf2.h:681
Warning
Don't forget to put the run(), count() or the getPtrToVf2Object() to the end of the expression.
See also
Vf2Wizard
Vf2

◆ vf2pp()

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;
Vf2ppWizard< Vf2ppWizardBase< G1 , G2 > > vf2pp( const G1 & g1 , const G2 & g2 )
Function-type interface for VF2 Plus Plus algorithm.
Definition vf2pp.h:875
Warning
Don't forget to put the run(), count() or the getPtrToVf2ppObject() to the end of the expression.
See also
Vf2ppWizard
Vf2pp