위상 정렬: 의존성 순서 정하기

모노레포에 패키지 다섯 개가 있다. ui와 api는 utils를 쓰고, web은 ui와 api를 쓰며, docs는 ui를 쓴다. 전체를 빌드하는 스크립트를 짜야 한다. web을 ui보다 먼저 빌드하면 아직 없는 결과물을 찾다가 실패한다. 의존하는 쪽이 의존 대상보다 늘 뒤에 오는 순서가 필요하다.

같은 질문이 곳곳에 있다. CI에서 어떤 작업이 다른 작업이 끝나기를 기다리는 설정, 데이터베이스 마이그레이션 순서, 스프레드시트에서 다른 셀을 참조하는 셀의 계산 순서가 모두 그렇다. 그리고 이런 도구는 "순환 의존이 있다"는 경고도 낸다. 순서를 정하는 방법과 순환을 잡아내는 방법이 하나의 알고리즘에서 같이 나온다. 그래프(graph) 용어는 그래프 노트에 있다.

그래프로 옮기기: 진입 차수

작업을 노드로, "a가 끝나야 b를 시작한다"를 a에서 b로 가는 화살표, 곧 간선(edge)으로 그린다. 화살표는 먼저 끝나야 하는 쪽에서 출발하니, ui가 utils를 쓰면 화살표는 utils→ui다. "누가 누구를 쓰나"를 그리는 의존 그래프와 방향이 반대다. 예의 간선은 utils→ui, utils→api, ui→web, api→web, ui→docs 다섯 개다. 간선에 방향이 있고 돌아오는 길(순환)이 없는 그래프를 DAG(directed acyclic graph)라고 한다(노드·간선·DAG 같은 그래프 용어는 『개발 수학』 Unit 10). 모든 간선이 앞에서 뒤로 가도록 노드를 한 줄로 세운 것이 위상 순서(topological order)이고, 그 순서를 찾는 일이 위상 정렬(topological sort)이다.

노드마다 세어 둘 값이 하나 있다. 자기에게 들어오는 간선 수, 곧 진입 차수(in-degree)다. 이 작업을 시작하기 전에 끝나기를 기다려야 하는 작업의 개수라고 읽으면 된다. 예에서 utils는 0, ui·api·docs는 1, web은 2다.

칸 알고리즘: 기다릴 것이 없는 것부터

진입 차수가 0인 노드는 기다릴 것이 없으니 지금 바로 실행할 수 있다. 칸 알고리즘(Kahn's algorithm)은 이 관찰 하나로 돈다.

1. 진입 차수 0인 노드를 모두 큐(queue)에 넣는다.
2. 큐에서 하나를 꺼내 결과에 붙인다.
3. 그 노드를 기다리던 노드들의 진입 차수를 1씩 줄인다. 0이 된 노드는 큐에 넣는다.
4. 큐가 빌 때까지 2~3을 되풀이한다.

1const nodes = ['utils', 'ui', 'api', 'web', 'docs']2const edges = [['utils', 'ui'], ['utils', 'api'], ['ui', 'web'], ['api', 'web'], ['ui', 'docs']]3const after: Record<string, string[]> = {}4const indeg: Record<string, number> = {}5for (const v of nodes) {6  after[v] = []7  indeg[v] = 08}9for (const [a, b] of edges) {10  after[a].push(b)11  indeg[b] += 112}13const queue = nodes.filter(v => indeg[v] === 0)14const order: string[] = []15let head = 016while (head < queue.length) {17  const v = queue[head]18  head += 119  order.push(v)20  for (const w of after[v]) {21    indeg[w] -= 122    if (indeg[w] === 0) queue.push(w)23  }24}25console.log(order.join(' → '))26if (order.length < nodes.length) console.log(`순환이 있다: ${nodes.length - order.length}개가 남았다`)

utils → ui → api → docs → web

순환: 끝내 0이 되지 않는 노드

Python의 graphlib

Python은 3.9부터 표준 라이브러리 graphlib에 TopologicalSorter가 있다(Python 문서: graphlib). 그래프는 딕셔너리로 넘기는데, 키는 노드이고 값은 그 노드의 선행 노드(predecessor)들(그 노드가 기다리는 노드)이다. 이 장의 코드 추적에 쓴 after(뒤에 올 노드 목록)와 방향이 반대라서 옮겨 적을 때 조심해야 한다.

from graphlib import TopologicalSorter

deps = {"ui": {"utils"}, "api": {"utils"}, "web": {"ui", "api"}, "docs": {"ui"}}
print(list(TopologicalSorter(deps).static_order()))

static_order()는 위상 순서대로 노드를 내놓고, 순환이 있으면 ValueError의 하위 클래스인 CycleError를 던진다. 예외에는 찾아낸 순환 하나가 노드 목록으로 들어 있다. 같은 단계의 노드끼리 순서는 정해져 있지 않고 그래프에 넣은 순서에 따라 달라질 수 있다고 문서가 밝힌다. 작업을 동시에 돌리려면 prepare() 뒤 is_active()가 참인 동안 get_ready()로 지금 실행할 수 있는 노드를 모두 받고, 끝난 노드를 done()으로 알려 준다. 보너스 문제의 단계별 위상 정렬이 이 동작이다.

JavaScript에는 표준 위상 정렬이 없어서 이 장의 코드처럼 직접 짜거나 라이브러리를 쓴다. 직접 짤 때는 다음 절의 함정을 피한다.

코드 리뷰: 빌드 순서 함수

정리하면 문제는 셋이다. 키만 노드로 모아 목록에만 나오는 패키지가 빠지고, 꺼낼 때마다 includes로 훑어 O(V × (V + E))가 되고(기다리는 쪽 목록을 미리 만들면 O(V + E)), 결과 길이를 확인하지 않아 순환이 있으면 일부가 빠진 순서를 조용히 돌려준다.

1단계: install
2단계: …
…