Vf2

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

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

VF2 algorithm class.

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.

See also

vf2()

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 >

  • NEQ – A bool-valued binary functor determinining whether a node is mappable to another. By default, it is an always-true operator.

Public Functions

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

Constructor.

Constructor

Parameters:
  • g1 – The graph to be embedded into g2.

  • g2 – The graph g1 will be embedded into.

  • m – read-write NodeMap storing the found mapping.

  • neq – A bool-valued binary functor determining whether a node is mappable to another. By default it is an always true operator.

inline ~Vf2()

Destructor.

inline MappingType mappingType() const

Returns the current mapping type

inline void mappingType( MappingType m_type )

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

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

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