| 125 | self.patterns = patterns |
| 126 | |
| 127 | def match(self, graph, nodes): |
| 128 | if not nodes: |
| 129 | return [], None |
| 130 | nodes = nodes if isinstance(nodes, list) else [nodes] |
| 131 | # If a single node, assume we need to match with its siblings |
| 132 | if len(nodes) == 1: |
| 133 | nodes = graph.siblings(nodes[0]) |
| 134 | else: |
| 135 | # Verify all nodes have the same parent or all have no parent |
| 136 | parents = [graph.incoming(n) for n in nodes] |
| 137 | matches = [set(p) == set(parents[0]) for p in parents[1:]] |
| 138 | if not all(matches): |
| 139 | return [], None |
| 140 | |
| 141 | # TODO: If more nodes than patterns, we should consider |
| 142 | # all permutations of the nodes |
| 143 | if len(self.patterns) != len(nodes): |
| 144 | return [], None |
| 145 | |
| 146 | patterns = self.patterns.copy() |
| 147 | nodes = nodes.copy() |
| 148 | all_matches = [] |
| 149 | end_node = None |
| 150 | for p in patterns: |
| 151 | found = False |
| 152 | for n in nodes: |
| 153 | matches, following = p.match(graph, n) |
| 154 | if matches: |
| 155 | found = True |
| 156 | nodes.remove(n) |
| 157 | all_matches.extend(matches) |
| 158 | # Verify all branches end in the same node |
| 159 | if end_node: |
| 160 | if end_node != following: |
| 161 | return [], None |
| 162 | else: |
| 163 | end_node = following |
| 164 | break |
| 165 | if not found: |
| 166 | return [], None |
| 167 | return all_matches, end_node |
| 168 | |
| 169 | |