டோபோலজிக்கல் வரிசைப்படுத்தல் ஒரு DAG-ன் (இயக்கப்பட்ட சுழற்சிஹீன வரைபடம்) முனைகளை நேரியல் முறையில் வரிசைப்படுத்துவதாகும், அதனால் ஒவ்வொரு விளிம்பு u->v இல் u முன் v இருக்கும். "இந்த பணிகளை அவற்றின் சார்புகள் கொடுக்கப்பட்டு என்ன வரிசையில் செய்யலாம்?" என்ற கேள்விக்கு பதிலளிக்கிறது.
இரண்டு பொதுவான நெறிமுறைகள்: (உள்ளீட்டு அளவு 0 உள்ள முனைகளை மீண்டும் அகற்று) அல்லது (தலைகீழ் பிந்திய-வரிசை). செல்லுபடியாகும் வரிசை உள்ளது.
from collections import deque
def topo_sort(graph):
indeg = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
indeg[v] += 1 # count incoming edges
queue = deque([u for u in indeg if indeg[u] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1 # "remove" the edge
if indeg[v] == 0:
queue.append(v)
return order if len(order) == len(graph) else None # None -> cycle
topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
கட்டமைப்பு அமைப்புகள், பணி அட்டவணைப்படுத்தல், பாடநெறி முன்நிபந்தனைகள் மற்றும் சார்பு தீர்வுக்கு பயன்படுத்தவும். முடிவு V-ஐ விட சிறியதாக இருந்தால், வரைபடத்தில் சுழற்சி உள்ளது (செல்லுபடியாகும் வரிசை இல்லை). வரிசை பொதுவாக தனித்துவமாக இல்லை.
சார்பு வரிசைப்படுத்தல் எல்லா இடங்களிலும் உள்ளது — தொகுப்பிகள், தொகுப்பு மேலாளர்கள், விரிதாள் மறுகணக்கீடு, CI பைப்லைன்கள்.
டோபோலজிக்கல் வரிசைப்படுத்தல் இயக்கப்பட்ட வரைபடங்களுக்கான சுழற்சி শনாক்தம் என்றும் செயல்படுகிறது.
ஒரு பிரச்சினையை "கட்டுப்பாடுகளின் கீழ் வரிசை" என்று அங்கீகரித்து டோபோ வரிசைப்படுத்தலுக்கு செல்வது ஒரு மூத்த சமிக்ஞை.