Class VF2¶

Inheritance Relationships¶

Class Documentation¶

class VF2 : public NetworKit::SubgraphIsomorphism¶

Finds every occurrence of a pattern graph inside a target graph using the VF2 algorithm.

VF2 extends a partial mapping one node pair at a time, depth first, and draws the candidate pairs from the terminal sets of unmapped nodes adjacent to mapped ones. It supports both semantics, directed and undirected graphs, node labels and edge labels.

The implementation is based on

Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2004). A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10), 1367-1372.

Public Functions

VF2(const Graph &pattern, const Graph &target, Semantics semantics = Semantics::INDUCED, count maxMatches = 0)¶

Parameters:

• pattern – The graph to look for. Must not contain self-loops.

• target – The graph to look in. Must agree with pattern on directedness.

• semantics – Whether matches must be induced. See SubgraphIsomorphism::Semantics.

• maxMatches – Stop after this many matches; 0 means no limit.

Throws:

std::invalid_argument – If semantics is not a known value. run() checks the graphs, since they may change after construction.

virtual void run() override¶

Runs the search. If a callback throws or CTRL+C interrupts the search, run() stops and rethrows, and the results stay unavailable.

Throws:

std::runtime_error – If the graphs break the requirements above, or if the labels do not fit the graphs.