Topoloji çeşidləmə

Kurs planı, layihənin quraşdırılması, paket asılılıqları: bəzi işlər başqalarından sonra gəlməlidir. Belə asılılıqlar yönlü qraf kimi yazılır: u -> v qövsü "u v-dən əvvəl" deməkdir. Topoloji çeşidləmə düyünləri elə sıralayır ki, bütün qövslər soldan sağa getsin.

DAG və sıranın şərti

• Sıra yalnız dövrsüz yönlü qrafda (DAG) mövcuddur.
• Hər u -> v qövsü üçün u sırada v-dən əvvəldir.
• Sıra adətən yeganə deyil: asılı olmayan düyünlər istənilən ardıcıllıqla gələ bilər.
• Dövr varsa sıra yoxdur: a -> b -> a "a b-dən əvvəl və b a-dan əvvəl" tələb edir.

Kahn alqoritmi

Daxil dərəcə düyünə daxil olan qövslərin sayıdır. Dərəcəsi 0 olan düyün heç nədən asılı deyil, ondan başlamaq olar.

deps = {
    "python": ["algorithms", "databases"],
    "math": ["algorithms", "statistics"],
    "algorithms": ["ml"],
    "databases": ["web"],
    "statistics": ["ml"],
    "ml": [],
    "web": [],
}

indegree = {node: 0 for node in deps}
for node in deps:
    for nxt in deps[node]:
        indegree[nxt] += 1
print(indegree)
print("sources:", [n for n in deps if indegree[n] == 0])

{'python': 0, 'math': 0, 'algorithms': 2, 'databases': 1, 'statistics': 1, 'ml': 2, 'web': 1}
sources: ['python', 'math']

1. Dərəcəsi 0 olan bütün düyünləri növbəyə qoyun.
2. Düyünü növbədən götürün, nəticəyə yazın.
3. Onun hər qonşusunun dərəcəsini 1 azaldın; 0 olanları növbəyə qoyun.
4. Növbə boşalana qədər təkrarlayın.