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

VF2 algorithm class. More...

#include <lemon/vf2.h>

Public Member Functions

 Vf2 (const G1 &g1, const G2 &g2, M &m, const NEQ &neq=NEQ())
 Constructor.
 ~Vf2 ()
 Destructor.
MappingType mappingType () const
 Returns the current mapping type.
void mappingType (MappingType m_type)
 Sets mapping type.
bool find ()
 Finds a mapping.

Detailed Description

template< class G1 , class G2 , class M , class NEQ >
class lemon::Vf2< G1 , G2 , M , NEQ >

This class provides an efficient implementation of the VF2 algorithm [6] 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 vf2() for the VF2 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 >
NEQA bool-valued binary functor determinining whether a node is mappable to another. By default, it is an always-true operator.
See also
vf2()

Constructor & Destructor Documentation

◆ Vf2()

template< class G1 , class G2 , class M , class NEQ >
Vf2 ( const G1 & g1,
const G2 & g2,
M & m,
const NEQ & neq = NEQ() )
inline

Constructor

Parameters
g1The graph to be embedded into g2.
g2The graph g1 will be embedded into.
mread-write NodeMap storing the found mapping.
neqA bool-valued binary functor determining whether a node is mappable to another. By default it is an always true operator.

◆ ~Vf2()

template< class G1 , class G2 , class M , class NEQ >
~Vf2 ( )
inline

Destructor.

Member Function Documentation

◆ mappingType() [1/2]

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

Returns the current mapping type

◆ mappingType() [2/2]

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

Sets 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 NEQ >
bool find ( )
inline

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