Python TopologicalSorter에서 순환 의존성을 찾는 방법

위상 순서는 모든 선행 관계를 만족하는 작업 순서입니다. Python TopologicalSorter에 넘기는 매핑은 노드를 키로, 그 노드의 선행 노드들을 값으로 둡니다.

순환이 있으면 완전한 위상 순서는 존재하지 않고 prepare()에서 CycleError가 발생합니다. 그렇더라도 순환에 포함되지 않은 일부 준비 가능 노드는 얻을 수 있으므로, 오류를 전체 그래프가 전혀 처리 불가능하다는 뜻으로 확대하면 안 됩니다.

위상 정렬은 선행 조건을 어기지 않는 순서입니다

작업 A가 끝난 뒤 B를 시작해야 하고, B가 끝난 뒤 C를 처리해야 한다면 가능한 순서는 A, B, C입니다. 위상 순서는 방향 그래프의 간선 제약을 지키는 선형 순서입니다. 그래프에 방향 순환이 있으면 모든 관계를 동시에 만족하는 전체 순서는 만들 수 없습니다. Python 3.12의 graphlib.TopologicalSorter는 이런 그래프 처리를 돕습니다. 생성자에 전달하는 딕셔너리에서 키는 작업 노드이고 값은 그 노드의 모든 선행 작업(iterable)입니다. 간선 화살표 그림과 매핑 방향을 혼동하지 않도록 주의해야 합니다.

값 목록에는 해당 작업이 기다리는 선행 항목을 둡니다

세 작업이 재료 준비 → 조리 → 포장 순으로 이어진다고 하겠습니다. 키가 조리인 항목의 값은 조리보다 먼저 끝나야 할 재료 준비입니다. 포장의 선행 작업은 조리입니다. TopologicalSorter는 선행 목록에 있는 항목들이 완료된 뒤에야 해당 노드를 준비된 것으로 다룹니다. 간선의 화살표를 작업에서 선행 작업 쪽으로 거꾸로 그린다고 생각하기보다, 각 키의 값이 ‘이 키가 기다리는 작업’이라고 읽으면 됩니다.

from graphlib import TopologicalSorter

graph = {
    "재료 준비": set(),
    "조리": {"재료 준비"},
    "포장": {"조리"},
}
print(tuple(TopologicalSorter(graph).static_order()))

이 그래프에는 순환이 없으므로 하나 이상의 유효한 순서가 나옵니다. 서로 독립적인 작업이 있으면 가능한 위상 순서는 여러 개일 수 있습니다. Python 문서의 예제도 독립 노드의 순서가 하나로 고정된다는 규칙을 두지 않습니다. 따라서 테스트에서 유효한 순서를 확인할 때는 결과 문자열 하나와 무조건 같아야 한다고 단정하기보다, 모든 선행 노드가 해당 작업보다 앞에 있는지를 검사하는 것이 안전합니다.

prepare에서 순환 오류를 확인합니다

전체 순서를 한 번에 얻으려면 static_order()를 사용할 수 있습니다. 더 세밀하게 처리하려면 prepare()로 그래프를 검사하고 get_ready()에서 현재 실행할 수 있는 노드를 가져온 뒤, 실제 완료된 노드는 done()으로 표시합니다. prepare()에서 방향 순환을 발견하면 CycleError가 발생합니다. 사이클을 조사하려면 노드 매핑에서 서로를 기다리는 관계를 추적하면 됩니다. 아래 예시는 조리가 포장을 기다리고 포장은 다시 조리를 기다리는 모순을 만듭니다.

from graphlib import CycleError, TopologicalSorter

graph = {
    "재료 준비": set(),
    "조리": {"포장"},
    "포장": {"조리"},
}
sorter = TopologicalSorter(graph)
try:
    sorter.prepare()
except CycleError as exc:
    print(type(exc).__name__)

1. 각 작업을 노드로 정하고, 선행 조건을 방향 간선으로 표현합니다.
2. 생성자 매핑에서 키마다 기다리는 모든 선행 노드를 기록합니다.
3. static_order() 또는 prepare() 기반 흐름으로 그래프를 처리합니다.
4. CycleError가 발생하면 예외에 포함된 노드와 의존 경로를 살펴 순환을 찾습니다.
5. 독립되거나 이미 준비된 노드와 순환에 막힌 노드를 구분해 대응합니다.

CycleError가 발생했다고 해서 그래프의 모든 노드가 영원히 막힌 것은 아닙니다. 공식 문서는 순환을 발견해도 순환과 무관한 일부 노드는 반환될 수 있고, 남은 노드를 진행하는 선택지가 있다고 설명합니다. 이는 전체 그래프의 완전한 위상 순서가 존재한다는 말은 아닙니다. 순환에 속하지 않는 작업을 처리한 뒤에도 서로 기다리는 작업은 완료되지 않습니다. 프로그램은 부분 진행을 허용할지, 오류를 내고 중단할지, 의존 그래프를 수정할지 정책을 정해야 합니다.

매핑 방향과 오류 뒤 부분 진행을 혼동하지 않습니다

첫 번째 실수는 작업: 선행 작업이 아니라 선행 작업: 후속 작업으로 딕셔너리를 만든 뒤, 라이브러리가 이를 후속 목록으로 해석한다고 생각하는 것입니다. 키 값은 해당 키를 준비하기 전에 끝나야 하는 선행 노드들의 iterable입니다. 두 번째 실수는 CycleError를 잡은 뒤 순환 그래프 전체를 정상 정렬했다고 간주하는 것입니다. 예외는 완전한 전체 순서가 불가능하다는 진단입니다. 일부 준비 노드를 처리할 수 있다는 동작은 실패한 순서를 성공으로 바꾸지 않습니다.

예를 들어 문서 검토와 배포 승인이 서로를 선행 작업으로 요구하면 둘은 순환에 묶입니다. 그러나 두 작업과 관계없는 이미지 압축은 별도로 준비될 수 있습니다. 운영 시스템이라면 독립 작업을 계속할지, 실패 시 전부 멈출지 정책을 결정해야 합니다. 학습 문제에서는 먼저 간선 방향을 쓰고, 각 작업의 선행 집합을 표로 만든 다음 순환 경로가 있는지 추적하면 오류 위치를 찾기 쉽습니다.