inducer / inducer/pytools

[Feature-request] Topological sort with keying function that exposes internal state

Open
#143 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
73
Forks
26
Avg merge
7h 3m
Merged PRs (30d)
2

Description

Consider the DAG below:
```python
from pytools.graph import compute_topological_order

dag = {"A": {"C"},
"B": {"E"},
"C": {"D"},
"D": set(),
"E": set(),
}

colors = {"A": "red",
"B": "red",
"C": "blue",
"D": "red",
"E": "blue"
}

sorted_nodes = compute_topological_order(dag, key=lambda x: x)
print(sorted_nodes) # ['A', 'B', 'C', 'D', 'E']
print([colors[node] for node in sorted_nodes]) # ['red', 'red', 'blue', 'red', 'blue']
```

My application needs a valid topological sort that minimizes the jumps from 'red'<->'blue' nodes in the final schedule. And so for this problem, the topological sort order I'm after would be `['A', 'B', 'C', 'E', 'D']`. I don't think that's possible with the current interface of `compute_topological_order`.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.