Deeploy.CommonExtensions.OptimizationPasses.Matchers.BranchingMatcher

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

Bases: SubgraphMatcher

Pattern matcher for computational graphs with branching and merging.

This matcher handles complex patterns that contain splits, merges, and other non-sequential structures. It uses a more sophisticated algorithm that can traverse graphs in both forward and reverse directions to handle branching patterns.

The matching algorithm explores multiple paths through the graph and can handle patterns with: - Multiple inputs/outputs per node - Fan-out (one node feeding multiple nodes) - Fan-in (multiple nodes feeding one node) - Complex DAG structures

Parameters:

regex_op (bool, optional) – If True, enables regex-based operation type matching instead of exact string matching. Default is False.

Notes

This matcher is suitable for complex patterns such as: - ResNet skip connections - Attention mechanisms with multiple branches - Feature pyramid networks - Any pattern with non-linear control flow

The algorithm is more computationally intensive than NonBranchingMatcher but provides full generality for arbitrary DAG patterns.

Methods

__init__(regex_op: bool = False)

Initialize the branching pattern matcher.

Parameters:

regex_op (bool, optional) – Enable regex-based operation type matching. Default is False.

__init__([regex_op])

Initialize the branching pattern matcher.

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.