Class PatternMatchHelper

ppq/IR/search.py:288–387

class PatternMatchHelper:
    @ staticmethod
    def match_burte_force(
        graph: BaseGraph, pattern: GraphPattern, 
        exclusive: bool, max_candidates: int = 1000000) -> List[List[Operation]]:
        """暴力子图模式匹配 这是 PPQ 0.6.6 更新的内容
        在 0.6.6 之前，我们使用具有不确定性的贪心匹配算法，但是考虑到实际应用中的问题
        在 0.6.6 版本之后，我们将其修改为枚举匹配。
        
        子图匹配问题是一个 NP-Hard 的问题，不存在多项式时间复杂度的解法。
        你需要给出一个模式子图，match_burte_force 方法将在 graph 中对模式子图进行匹配。
        
        PPQ 使用了非递归的算法完成上述匹配，其最坏时间和空间复杂度大概都是 O(NM^k)
        其中 N 是母图节点个数，M 是子图节点个数，k 是母图的最大出度
        
        对于存在二义性子图模式，匹配复杂度将指数级增长；为了限制算法执行时间，当匹配到多于
        max_candidates 个模式子图时，算法强制停机，并报错返回。
        
        实际使用中的时间复杂度更加接近于 O(NM)
        
        参数 exclusive 指定了是否需要进行精确匹配。在精确匹配模式下：
            1. 不允许模式子图中除根节点外的其他节点有来自模式子图以外节点的输入
            2. 不允许模式子图中除叶节点外的其他节点有朝向模式子图以外节点的输出

        Example:
            pt = PatternTree(
                patterns = [lambda x: x.is_computing_op, 'Softplus', 'Tanh', 'Mul']
                edges = [[0, 1], [1, 2], [2, 3], [0, 3]])

            pt create an abstract tree pattern of:
                                            --- 'Softplus'   ---   'Tanh' --
            lambda x: x.is_computing_op --- +                              + --- 'Mul'
                                            ---     ---     ---    ---    --

        """

        def is_linked(upstream_op: Operation, downstream_op: Operation) -> bool:
            if upstream_op is None or downstream_op is None: return True
            return downstream_op in graph.get_downstream_operations(upstream_op)

        node_order = pattern.order
        matched_patterns = []

        # match root from graph, further pattern matching will start from root.
        for operation in graph.operations.values():
            root_idx = node_order[0]
            if pattern.node_patterns[root_idx](operation):
                matched_patterns.append([operation] + [None for _ in range(len(node_order) - 1)])

        for idx in node_order[1: ]:
            node_candidates, next_generation = [], []
            for operation in graph.operations.values():
                if pattern.node_patterns[idx](operation):
                    node_candidates.append(operation)

            for matched_pattern in matched_patterns:
                for operation in node_candidates:
                    is_pattern_root = len(pattern.input_table[idx]) == 0