![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
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. | |
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\).
| 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.
| 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. |
| 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.
| 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.