Vf2pp

Declared in lemon/vf2pp.h, in the group Graph Isomorphism; the same class on the Doxygen site.

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

VF2 Plus Plus algorithm class [24].

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.

See also

vf2pp()

Template Parameters:
  • G1 – The type of the graph to be embedded. The default type is ListGraph.

  • G2 – The type of the graph g1 will be embedded into. The default type is ListGraph.

  • M – The type of the NodeMap storing the mapping. By default, it is G1::NodeMap< typename G2::Node >

  • M1 – The 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 >.

  • M2 – The 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 >.

Public Functions

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

Constructor.

Parameters:
  • g1 – The graph to be embedded.

  • g2 – The graph g1 will be embedded into.

  • m – The NodeMap storing the mapping, by default of the type G1::NodeMap< typename G2::Node >.

  • intLabels1 – 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.

  • intLabels2 – 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.

inline ~Vf2pp()

Destructor.

inline MappingType mappingType() const

Returns the current mapping type.

inline void mappingType( MappingType m_type )

Sets the mapping type.

The mapping type is set to SUBGRAPH by default.

See also

See MappingType for the possible values.

inline bool find()

Finds a mapping.

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:
  • true – if a mapping is found.

  • false – if there is no (more) mapping.