abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Vf2pp< G1 , G2 , M , M1 , M2 > Class Template Reference

VF2 Plus Plus algorithm class [24]. More...

#include <lemon/vf2pp.h>

Public Member Functions

 Vf2pp (const G1 &g1, const G2 &g2, M &m, M1 &intLabels1, M2 &intLabels2)
 Constructor.
 ~Vf2pp ()
 Destructor.
MappingType mappingType () const
 Returns the current mapping type.
void mappingType (MappingType m_type)
 Sets the mapping type.
bool find ()
 Finds a mapping.

Detailed Description

template< class G1 , class G2 , class M , class M1 , class M2 >
class lemon::Vf2pp< G1 , G2 , M , M1 , M2 >

This class provides an efficient implementation of the VF2 Plus Plus algorithm [24] for variants of the (Sub)graph Isomorphism problem.

Both graphs must be simple, i.e., without loops and parallel edges: the algorithm takes the neighbours of a node from its incident edges, and on a graph with parallel edges it may report a mapping more than once.

There is also a function-type interface called vf2pp() for the VF2 Plus Plus algorithm, which is probably more convenient in most use cases.

Template Parameters
G1The type of the graph to be embedded. The default type is ListGraph.
G2The type of the graph g1 will be embedded into. The default type is ListGraph.
MThe type of the NodeMap storing the mapping. By default, it is G1::NodeMap< typename G2::Node >
M1The type of the NodeMap storing the integer node labels of G1. The labels must be the numbers {0,1,2,..,K-1}, where K is the number of different labels. By default, it is G1::NodeMap< int >.
M2The type of the NodeMap storing the integer node labels of G2. The labels must be the numbers {0,1,2,..,K-1}, where K is the number of different labels. By default, it is G2::NodeMap< int >.
See also
vf2pp()

Constructor & Destructor Documentation

◆ Vf2pp()

template< class G1 , class G2 , class M , class M1 , class M2 >
Vf2pp ( const G1 & g1,
const G2 & g2,
M & m,
M1 & intLabels1,
M2 & intLabels2 )
inline

Constructor.

Parameters
g1The graph to be embedded.
g2The graph g1 will be embedded into.
mThe NodeMap storing the mapping, by default of the type G1::NodeMap< typename G2::Node >.
intLabels1The NodeMap storing the integer node labels of G1. The labels must be the numbers {0,1,2,..,K-1}, where K is the number of different labels.
intLabels2The NodeMap storing the integer node labels of G2. The labels must be the numbers {0,1,2,..,K-1}, where K is the number of different labels.

◆ ~Vf2pp()

template< class G1 , class G2 , class M , class M1 , class M2 >
~Vf2pp ( )
inline

Destructor.

Member Function Documentation

◆ mappingType() [1/2]

template< class G1 , class G2 , class M , class M1 , class M2 >
MappingType mappingType ( ) const
inline

Returns the current mapping type.

◆ mappingType() [2/2]

template< class G1 , class G2 , class M , class M1 , class M2 >
void mappingType ( MappingType m_type)
inline

Sets the mapping type.

The mapping type is set to SUBGRAPH by default.

See also
See MappingType for the possible values.

◆ find()

template< class G1 , class G2 , class M , class M1 , class M2 >
bool find ( )
inline

This method finds a mapping from g1 into g2 according to the mapping type set by mappingType().

By subsequent calls, it returns all possible mappings one-by-one.

Return values
trueif a mapping is found.
falseif there is no (more) mapping.