Check if one SCC is a (transitive) dependency of another.
(self, from_scc_id: int, to_scc_id: int)
| 1527 | ) |
| 1528 | |
| 1529 | def is_transitive_scc_dep(self, from_scc_id: int, to_scc_id: int) -> bool: |
| 1530 | """Check if one SCC is a (transitive) dependency of another.""" |
| 1531 | edge = (from_scc_id, to_scc_id) |
| 1532 | if (cached := self.transitive_deps_cache.get(edge)) is not None: |
| 1533 | return cached |
| 1534 | todo = self.scc_by_id[from_scc_id].deps |
| 1535 | seen = set() |
| 1536 | while todo: |
| 1537 | more = set() |
| 1538 | # Breadth-first search seems to be better here, because all |
| 1539 | # "lower-level" SCCs are processed and some may be cached. |
| 1540 | for dep in todo: |
| 1541 | seen.add(dep) |
| 1542 | if dep == to_scc_id: |
| 1543 | self.transitive_deps_cache[edge] = True |
| 1544 | return True |
| 1545 | if cached := self.transitive_deps_cache.get((dep, to_scc_id)): |
| 1546 | self.transitive_deps_cache[edge] = True |
| 1547 | return True |
| 1548 | elif cached is None: |
| 1549 | more |= self.scc_by_id[dep].deps |
| 1550 | todo = more |
| 1551 | self.transitive_deps_cache[edge] = False |
| 1552 | for dep in seen: |
| 1553 | # We negative-cache all intermediate lookups, thus |
| 1554 | # trading time for space. |
| 1555 | self.transitive_deps_cache[(dep, to_scc_id)] = False |
| 1556 | return False |
| 1557 | |
| 1558 | def error( |
| 1559 | self, |
no test coverage detected