Sort the layers in a high level graph topologically Parameters ---------- hlg : HighLevelGraph The high level graph's layers to sort Returns ------- sorted: list List of layer names sorted topologically
(self)
| 696 | return g |
| 697 | |
| 698 | def _toposort_layers(self) -> list[str]: |
| 699 | """Sort the layers in a high level graph topologically |
| 700 | |
| 701 | Parameters |
| 702 | ---------- |
| 703 | hlg : HighLevelGraph |
| 704 | The high level graph's layers to sort |
| 705 | |
| 706 | Returns |
| 707 | ------- |
| 708 | sorted: list |
| 709 | List of layer names sorted topologically |
| 710 | """ |
| 711 | degree = {k: len(v) for k, v in self.dependencies.items()} |
| 712 | reverse_deps: dict[str, list[str]] = {k: [] for k in self.dependencies} |
| 713 | ready = [] |
| 714 | for k, v in self.dependencies.items(): |
| 715 | for dep in v: |
| 716 | reverse_deps[dep].append(k) |
| 717 | if not v: |
| 718 | ready.append(k) |
| 719 | ret = [] |
| 720 | while len(ready) > 0: |
| 721 | layer = ready.pop() |
| 722 | ret.append(layer) |
| 723 | for rdep in reverse_deps[layer]: |
| 724 | degree[rdep] -= 1 |
| 725 | if degree[rdep] == 0: |
| 726 | ready.append(rdep) |
| 727 | return ret |
| 728 | |
| 729 | def cull(self, keys: Iterable[Key]) -> HighLevelGraph: |
| 730 | """Return new HighLevelGraph with only the tasks required to calculate keys. |