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
-
| 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. |
- See also
- vf2()
template< class G1 , class G2 , class M , class NEQ >
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. |