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