Deeploy.CommonExtensions.OptimizationPasses.Matchers.SubgraphMatcher

class Deeploy.CommonExtensions.OptimizationPasses.Matchers.SubgraphMatcher(regex_op: bool = False)

Bases: object

Base class for pattern matching in computational graphs.

This class provides the foundation for matching pattern graphs against larger computational graphs. It supports both exact string matching and regular expression matching for operation types, enabling flexible pattern recognition for graph optimization and transformation.

The matcher identifies non-overlapping instances of a pattern within a target graph, returning Match objects that can be used for subsequent transformations or analysis.

Notes

This is an abstract base class that defines the interface for pattern matching. Concrete implementations must override the abstract methods _valid_pattern and _nodes_map_from_anchor to define specific matching algorithms.

The matching process ensures non-overlapping matches, meaning each node in the target graph can only participate in at most one match.

Methods

__init__(regex_op: bool = False)

Initialize the SubgraphMatcher.

Parameters:

regex_op (bool, optional) – Whether to use regular expression matching for operation types. Default is False for exact string matching.

__init__([regex_op])	Initialize the SubgraphMatcher.
is_op_match(patternNode, graphNode)	Check if a pattern node operation matches a graph node operation.
match(graph, pattern)	Find all non-overlapping matches of a pattern in a target graph.

is_op_match(patternNode: Node, graphNode: Node)

Check if a pattern node operation matches a graph node operation.

Compares the operation types of two nodes according to the configured matching policy (regex or exact match).

Parameters:

• patternNode (gs.Node) – The pattern node whose operation type serves as the match criterion.

• graphNode (gs.Node) – The target graph node to check for a match.

Returns:

True if the operations match according to the configured policy, False otherwise.

Return type:

bool

Notes

When regex_op is True, the pattern node’s operation is treated as a regular expression pattern and matched against the graph node’s operation using re.fullmatch. When False, exact string equality is used.

match(graph: Graph, pattern: Graph)

Find all non-overlapping matches of a pattern in a target graph.

Systematically searches the target graph for instances of the pattern, ensuring that each node participates in at most one match to avoid conflicts during transformations.

Parameters:

• graph (gs.Graph) – The target graph to search for pattern matches.

• pattern (gs.Graph) – The pattern graph to find instances of.

Returns:

A list of Match objects representing all non-overlapping instances of the pattern found in the target graph.

Return type:

List[Match]

Notes

The algorithm: 1. Validates the pattern using the subclass-specific validation 2. Iterates through all nodes in the target graph as potential anchors 3. Attempts to match the pattern from each anchor 4. Collects only non-overlapping matches to avoid conflicts

Non-overlapping means that if a node is part of one match, it cannot be part of any other match in the returned list.