Class SubgraphIsomorphism¶

Inheritance Relationships¶

Class Documentation¶

class SubgraphIsomorphism : public NetworKit::Algorithm¶

Abstract base class for subgraph isomorphism algorithms.

The algorithms find every match of a small pattern graph in a large target graph. A match maps the pattern nodes injectively to target nodes and every pattern edge to a target edge. Under Semantics::INDUCED, the default, it also maps every pattern non-edge to a target non-edge. The search finds an occurrence once per automorphism of the pattern, so a triangle occurs six times.

Pattern and target must both be directed or both be undirected, and the pattern must not contain self-loops. The search ignores edge weights and target self-loops, and it collapses parallel edges. The algorithm holds both graphs by reference, so they must outlive it. Since the graphs may change after construction, run() validates them and the labels each time.

Subclassed by NetworKit::VF2

Public Types

enum class Semantics¶

Values:

enumerator INDUCED¶

Pattern edges map to target edges and pattern non-edges map to target non-edges.

enumerator MONOMORPHISM¶

Pattern edges map to target edges. Additional target edges are allowed.

using Match = std::vector<node>¶

One match: match[u] is the image of pattern node u, or none if u is not a node.

using MatchCallback = std::function<void(std::span<const node>)>¶

Receives one match at a time, never concurrently. The match is indexed like a Match. It refers to an internal buffer and is valid only during the call.

Public Functions

~SubgraphIsomorphism() override = default¶

virtual void run() override = 0¶

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.

void setNodeLabels(std::span<const index> patternNodeLabels, std::span<const index> targetNodeLabels)¶

Restricts matches to map every pattern node to a target node with the same label. The label none matches any label, and two empty spans remove the labels. The labels are copied. Call this before run(), which throws if a span is shorter than the node id bound of its graph.

Parameters:

• patternNodeLabels – Labels of the pattern nodes, indexed by node id.

• targetNodeLabels – Labels of the target nodes, indexed by node id.

void setEdgeLabels(std::span<const index> patternEdgeLabels, std::span<const index> targetEdgeLabels)¶

Restricts matches to map every pattern edge to a target edge with the same label. The label none matches any label, and two empty spans remove the labels. The labels are copied. Call this before run(), which throws if a graph has no edge ids (see Graph::indexEdges()), if a span is shorter than the edge id bound of its graph, or for parallel edges with different labels.

Parameters:

• patternEdgeLabels – Labels of the pattern edges, indexed by edge id.

• targetEdgeLabels – Labels of the target edges, indexed by edge id.

void setCallback(MatchCallback callback)¶

Passes every match to callback instead of storing it, so getMatches() throws. Replaces an earlier callback. Call this before run().

void setStoreMatches(bool storeMatches)¶

Sets whether matches are stored. Pass false to only count them, so getMatches() throws. Call this before run().

const std::vector<Match> &getMatches() const¶

Returns the matches of the last run(). Throws if run() has not finished, or if that run did not store the matches because a callback was set or matches were only counted.

count numberOfMatches() const¶

Returns the number of matches found, stored or not.

bool hasMatch() const¶

Returns whether a match was found. Pass maxMatches = 1 to stop at the first one.

Protected Functions

SubgraphIsomorphism(const Graph &pattern, const Graph &target, Semantics semantics, count maxMatches)¶

Throws:

std::invalid_argument – If semantics is not a known value.

inline bool hasCallback() const noexcept¶

void prepareRun()¶

Resets the results and validates the input. Call this at the start of run().

bool reportMatch(std::span<const node> match)¶

Records one match. Returns false once the cap is reached.

void finishRun()¶

Marks the run as finished.

Protected Attributes

const Graph *pattern¶

const Graph *target¶

std::vector<index> patternNodeLabels¶

std::vector<index> targetNodeLabels¶

std::vector<index> patternEdgeLabels¶

std::vector<index> targetEdgeLabels¶

Semantics semantics¶

count maxMatches¶

0 means no limit.