Number of total data elements on which this key depends For each key we return the number of tasks that must be run for us to run this task. Examples -------- >>> inc = lambda x: x + 1 >>> dsk = {'a': 1, 'b': (inc, 'a'), 'c': (inc, 'b')} >>> dependencies, dependents = g
(
dependencies: Mapping[Key, set[Key]], dependents: Mapping[Key, set[Key]]
)
| 704 | |
| 705 | |
| 706 | def ndependencies( |
| 707 | dependencies: Mapping[Key, set[Key]], dependents: Mapping[Key, set[Key]] |
| 708 | ) -> tuple[dict[Key, int], dict[Key, int]]: |
| 709 | """Number of total data elements on which this key depends |
| 710 | |
| 711 | For each key we return the number of tasks that must be run for us to run |
| 712 | this task. |
| 713 | |
| 714 | Examples |
| 715 | -------- |
| 716 | >>> inc = lambda x: x + 1 |
| 717 | >>> dsk = {'a': 1, 'b': (inc, 'a'), 'c': (inc, 'b')} |
| 718 | >>> dependencies, dependents = get_deps(dsk) |
| 719 | >>> num_dependencies, total_dependencies = ndependencies(dependencies, dependents) |
| 720 | >>> sorted(total_dependencies.items()) |
| 721 | [('a', 1), ('b', 2), ('c', 3)] |
| 722 | |
| 723 | Returns |
| 724 | ------- |
| 725 | num_dependencies: Dict[key, int] |
| 726 | total_dependencies: Dict[key, int] |
| 727 | """ |
| 728 | num_needed = {} |
| 729 | result = {} |
| 730 | for k, v in dependencies.items(): |
| 731 | num_needed[k] = len(v) |
| 732 | if not v: |
| 733 | result[k] = 1 |
| 734 | |
| 735 | num_dependencies = num_needed.copy() |
| 736 | current: list[Key] = [] |
| 737 | current_pop = current.pop |
| 738 | current_append = current.append |
| 739 | |
| 740 | for key in result: |
| 741 | for parent in dependents[key]: |
| 742 | num_needed[parent] -= 1 |
| 743 | if not num_needed[parent]: |
| 744 | current_append(parent) |
| 745 | while current: |
| 746 | key = current_pop() |
| 747 | result[key] = 1 + sum(result[child] for child in dependencies[key]) |
| 748 | for parent in dependents[key]: |
| 749 | num_needed[parent] -= 1 |
| 750 | if not num_needed[parent]: |
| 751 | current_append(parent) |
| 752 | return num_dependencies, result |
| 753 | |
| 754 | |
| 755 | OrderInfo = namedtuple( |