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 algorithm class. |
|
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 SUBGRAPH
-
template< class G1 , class G2 >
Vf2Wizard< Vf2WizardBase< G1 , G2 > > vf2(
) 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
See also
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(
) 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
See also
Warning
Don’t forget to put the run(), count() or the getPtrToVf2ppObject() to the end of the expression.