12.11 위상 정렬과 방향 비순환 그래프

12.11 위상 정렬과 방향 비순환 그래프

1. 개요

방향 비순환 그래프(Directed Acyclic Graph, DAG)는 사이클이 없는 방향 그래프이며, 객체들 사이의 비대칭적 의존 관계를 표현하는 데 광범위하게 사용된다. 위상 정렬(topological sort)은 DAG의 노드들을 의존 관계를 만족하는 순서로 나열하는 알고리즘이다. 본 절에서는 DAG의 정의와 성질, 위상 정렬의 알고리즘, 그리고 로봇공학에서의 응용을 다룬다. 위상 정렬은 작업 스케줄링, 컴파일러, 의존성 해결 등 다양한 영역에서 핵심 도구이다.

2. 방향 비순환 그래프

2.1 정의

방향 비순환 그래프는 다음을 만족하는 방향 그래프이다.

  • 모든 엣지가 방향성을 가진다.
  • 사이클이 존재하지 않는다.

DAG는 다양한 의존 관계와 부분 순서를 표현하는 데 자연스럽다.

2.2 DAG의 예시

  • 작업 의존성: 작업 A가 작업 B 이전에 수행되어야 함
  • 컴파일러 의존성: 모듈 A가 모듈 B에 의존
  • 부분 순서: 수학적 부분 순서
  • 인과 관계: 사건 A가 사건 B의 원인
  • 상속 관계: 클래스의 상속 그래프

2.3 DAG의 성질

DAG는 다음의 성질을 가진다.

  • 적어도 하나의 시작 노드(입력 차수가 0인 노드)가 존재한다.
  • 적어도 하나의 끝 노드(출력 차수가 0인 노드)가 존재한다.
  • 도달 가능성이 부분 순서를 정의한다.
  • 위상 정렬이 가능하다.

3. 위상 정렬

3.1 정의

DAG의 위상 정렬은 노드들의 선형 순서이며, 모든 방향 엣지 (u, v)에 대해 u가 v보다 앞에 있다.

3.2 위상 순서의 의미

위상 순서는 의존 관계를 만족하는 작업의 실행 순서를 나타낸다. 예를 들어 작업 A가 작업 B 이전에 수행되어야 한다면, 위상 순서에서 A가 B보다 먼저 나타난다.

3.3 위상 정렬의 존재

위상 정렬이 존재하기 위한 필요충분조건은 그래프가 DAG라는 것이다. 사이클이 있으면 위상 정렬이 불가능하다.

3.4 위상 정렬의 유일성

DAG는 일반적으로 여러 개의 위상 정렬을 가진다. 유일한 위상 정렬은 노드들 사이의 모든 비교가 정의된 경우(전순서)에만 존재한다.

4. 위상 정렬 알고리즘

4.1 Kahn 알고리즘

Kahn 알고리즘은 입력 차수를 기반으로 한 위상 정렬 알고리즘이다.

4.1.1 의사 코드

Kahn(G):
    in_degree = compute in-degrees of all nodes
    queue = nodes with in_degree 0
    order = empty list
    
    while queue is not empty:
        u = queue.dequeue()
        order.append(u)
        
        for each neighbor v of u:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.enqueue(v)
    
    if length(order) < |V|:
        return "Cycle exists"
    return order

4.1.2 단계별 동작

  1. 초기화: 모든 노드의 입력 차수를 계산한다. 입력 차수가 0인 노드를 큐에 추가한다.
  2. 반복: 큐가 빌 때까지 다음을 반복한다.
  • 큐에서 노드 u를 꺼내 결과에 추가한다.
  • u의 모든 이웃 v에 대해 입력 차수를 1 감소시킨다.
  • v의 입력 차수가 0이 되면 큐에 추가한다.
  1. 종료: 결과의 길이가 노드 수보다 작으면 사이클이 존재한다.

4.1.3 시간 복잡도

Kahn 알고리즘의 시간 복잡도는 O(|V| + |E|)이다. 각 노드와 엣지가 한 번씩 처리된다.

4.2 DFS 기반 위상 정렬

DFS의 종료 시간을 사용한 위상 정렬도 가능하다.

4.2.1 의사 코드

TopologicalSort_DFS(G):
    visited = empty set
    stack = empty stack
    
    for each node v in V:
        if v not in visited:
            DFS_TS(v, visited, stack)
    
    return reverse(stack)

DFS_TS(v, visited, stack):
    visited.add(v)
    for each neighbor u of v:
        if u not in visited:
            DFS_TS(u, visited, stack)
    stack.push(v)

4.2.2 정확성

DFS의 종료 시간의 역순이 위상 정렬임을 보일 수 있다. u에서 v로의 엣지가 있으면 u의 종료 시간이 v의 종료 시간보다 늦다.

4.2.3 시간 복잡도

DFS 기반 위상 정렬의 시간 복잡도도 O(|V| + |E|)이다.

5. 두 알고리즘의 비교

5.1 차이

측면KahnDFS 기반
자료 구조큐스택 (재귀)
사이클 검출자연스러움추가 작업 필요
메모리O(\vert V\vert)O(\vert V\vert)
병렬화적합어려움

5.2 적합한 응용

  • 사이클 검출이 중요한 경우: Kahn
  • 다른 DFS 기반 분석과 결합: DFS 기반
  • 점진적 처리가 필요한 경우: Kahn

6. Python 구현

6.1 Kahn 알고리즘

from collections import deque

def topological_sort_kahn(graph):
    in_degree = {v: 0 for v in graph}
    for v in graph:
        for u in graph[v]:
            in_degree[u] += 1
    
    queue = deque([v for v in in_degree if in_degree[v] == 0])
    order = []
    
    while queue:
        v = queue.popleft()
        order.append(v)
        for u in graph[v]:
            in_degree[u] -= 1
            if in_degree[u] == 0:
                queue.append(u)
    
    if len(order) < len(graph):
        return None  # 사이클 존재
    return order

6.2 DFS 기반

def topological_sort_dfs(graph):
    visited = set()
    order = []
    
    def dfs(v):
        visited.add(v)
        for u in graph[v]:
            if u not in visited:
                dfs(u)
        order.append(v)
    
    for v in graph:
        if v not in visited:
            dfs(v)
    
    return order[::-1]

7. 위상 정렬의 응용

7.1 작업 스케줄링

여러 작업이 의존 관계를 가질 때, 위상 정렬로 실행 순서를 결정한다.

7.2 컴파일러

소스 코드의 컴파일 순서를 결정하는 데 위상 정렬이 사용된다. 모듈의 의존 관계가 DAG이며, 위상 정렬이 컴파일 순서이다.

7.3 Make 시스템

Make 도구는 파일의 의존 관계를 DAG로 표현하고, 위상 정렬로 빌드 순서를 결정한다.

7.4 패키지 관리자

소프트웨어 패키지의 의존성 해결에 위상 정렬이 사용된다.

7.5 강좌 수강 순서

대학의 강좌가 선수 강좌를 가질 때, 위상 정렬로 수강 순서를 결정할 수 있다.

8. DAG에서의 최단 경로

8.1 효율적 알고리즘

DAG에서는 다익스트라보다 효율적인 최단 경로 알고리즘이 가능하다. 위상 순서에 따라 노드를 처리하면 된다.

8.1.1 알고리즘

DAG_shortest_paths(G, s):
    topological order = topological_sort(G)
    
    for each node v:
        v.distance = ∞
    s.distance = 0
    
    for each node u in topological order:
        for each neighbor v of u:
            if v.distance > u.distance + w(u, v):
                v.distance = u.distance + w(u, v)
    
    return distances

8.2 시간 복잡도

DAG의 최단 경로 알고리즘의 시간 복잡도는 O(|V| + |E|)이다. 다익스트라보다 빠르다.

8.3 음수 가중치

이 알고리즘은 음수 가중치도 처리할 수 있다. DAG에는 음수 사이클이 없기 때문이다.

9. DAG의 최장 경로

9.1 문제

DAG의 최장 경로(longest path)는 다익스트라의 최단 경로 알고리즘과 비슷하게 풀린다. 가중치를 음수로 변환하고 최단 경로를 찾는다.

9.2 응용

PERT(Program Evaluation and Review Technique) 차트에서 프로젝트의 임계 경로(critical path)를 찾는 데 사용된다. 임계 경로는 프로젝트 완료에 가장 긴 시간이 걸리는 경로이다.

10. 위상 정렬의 변형

10.1 사전순 위상 정렬

여러 위상 정렬이 가능할 때, 사전순으로 가장 작은 것을 찾을 수 있다. 우선순위 큐를 사용한 Kahn 알고리즘으로 가능하다.

10.2 부분 위상 정렬

특정 부분 그래프에 대해서만 위상 정렬을 수행하는 변형이다.

10.3 점진적 위상 정렬

DAG에 노드와 엣지가 동적으로 추가될 때, 위상 정렬을 점진적으로 갱신하는 알고리즘이 있다.

11. DAG의 응용

11.1 데이터 파이프라인

데이터 처리 파이프라인은 일반적으로 DAG로 표현된다. Apache Airflow, Luigi 등의 도구는 DAG를 통해 작업을 관리한다.

11.2 신경망

신경망의 계산 그래프는 DAG이다. 순방향 전파와 역전파가 위상 순서로 수행된다.

11.3 빌드 시스템

소프트웨어 빌드 시스템은 파일의 의존 관계를 DAG로 표현한다.

11.4 부분 순서 집합

수학에서 부분 순서 집합(poset)은 DAG로 표현될 수 있다.

11.5 인과 추론

인과 관계의 그래프는 DAG로 표현된다. 베이즈 네트워크가 대표적이다.

12. 로봇공학에서의 응용

12.1 작업 시퀀스 계획

로봇이 여러 작업을 수행할 때, 작업 사이의 의존 관계를 DAG로 표현하고 위상 정렬로 실행 순서를 결정한다.

12.2 매니퓰레이션 작업

매니퓰레이션 작업의 단계가 의존 관계를 가진다. 예를 들어 부품을 집기 전에 부품의 위치를 알아야 한다. 위상 정렬이 이러한 관계를 처리한다.

12.3 매니퓰레이터의 운동학적 트리

매니퓰레이터의 운동학적 구조는 트리이며, 트리는 DAG의 특수한 경우이다. 순기구학과 자코비안 계산이 위상 순서로 수행된다.

12.4 다중 로봇 작업 할당

다중 로봇이 협력하여 작업을 수행할 때, 작업 의존성과 로봇 능력을 결합한 DAG가 사용될 수 있다.

12.5 행동 트리

로봇의 행동 트리는 DAG의 특수한 형태이다. 행동의 실행 순서가 트리 구조로 결정된다.

13. 응용 예시: 빌드 시스템

C 프로그램을 컴파일할 때 소스 파일과 헤더 파일의 의존 관계가 DAG이다. Make 도구는 위상 정렬로 컴파일 순서를 결정한다.

main.c -> main.o
utils.c -> utils.o
main.o, utils.o -> program

위상 정렬: main.c, utils.c, main.o, utils.o, program

14. 응용 예시: 패키지 의존성 해결

Linux의 apt나 yum과 같은 패키지 관리자는 패키지의 의존성을 DAG로 표현하고, 위상 정렬로 설치 순서를 결정한다.

15. 응용 예시: 신경망 학습

신경망의 계산 그래프는 DAG이다. 순방향 전파는 위상 순서로, 역전파는 역위상 순서로 수행된다.

16. 응용 예시: 매니퓰레이션 시퀀스

매니퓰레이터가 부품을 조립할 때 작업의 순서가 정해져 있다.

1. 부품 인식 -> 2. 부품 위치 계산 -> 3. 그리퍼 이동 -> 4. 부품 잡기 -> 5. 목표 위치 이동 -> 6. 부품 놓기

이러한 의존 관계를 DAG로 표현하고 위상 정렬로 실행한다.

17. 응용 예시: 다중 로봇 협력

10대의 로봇이 협력하여 큰 객체를 운반할 때, 각 로봇의 행동에 의존성이 있다. 위상 정렬로 협력 시퀀스를 결정한다.

18. 응용 예시: SLAM의 최적화

그래프 SLAM에서 키프레임의 처리 순서나 마진화 순서에 위상 정렬이 사용될 수 있다.

19. 사이클 검출

19.1 Kahn 알고리즘으로 검출

Kahn 알고리즘이 모든 노드를 처리하지 못하면 사이클이 존재한다. 이는 검출의 자연스러운 방법이다.

19.2 DFS로 검출

DFS에서 백 엣지가 발견되면 사이클이 존재한다. 노드의 색을 사용하여 검출한다.

def has_cycle(graph):
    color = {v: 'white' for v in graph}
    
    def dfs(v):
        color[v] = 'gray'
        for u in graph[v]:
            if color[u] == 'gray':
                return True
            if color[u] == 'white' and dfs(u):
                return True
        color[v] = 'black'
        return False
    
    for v in graph:
        if color[v] == 'white':
            if dfs(v):
                return True
    return False

20. 위상 정렬의 라이브러리 지원

20.1 NetworkX

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4)])

# 위상 정렬
order = list(nx.topological_sort(G))
print(order)  # 가능한 결과: [1, 2, 3, 4]

# DAG 검사
print(nx.is_directed_acyclic_graph(G))  # True

# 모든 위상 정렬
all_orders = list(nx.all_topological_sorts(G))

20.2 다른 라이브러리

  • Boost Graph Library
  • igraph
  • graph-tool

21. 학습의 가치

위상 정렬과 DAG를 이해하는 것은 다음과 같은 이점을 제공한다.

  • 의존 관계를 다루는 기본 도구를 익힌다.
  • 작업 스케줄링과 의존성 해결의 알고리즘을 학습한다.
  • DAG의 다양한 응용을 이해한다.
  • 로봇 작업 계획의 기초를 형성한다.

22. 학습 권장사항

22.1 직접 구현

Kahn 알고리즘과 DFS 기반 위상 정렬을 모두 구현해 본다. 두 방법의 차이를 비교한다.

22.2 응용 학습

빌드 시스템, 패키지 관리, 신경망 등의 실제 응용에서 위상 정렬이 어떻게 사용되는지 학습한다.

22.3 시각화

DAG와 위상 정렬을 시각화하면 이해가 깊어진다.

23. 본 절의 의의

본 절은 위상 정렬과 DAG를 자세히 다루었다. DAG는 다양한 의존 관계를 표현하는 자연스러운 도구이며, 위상 정렬은 그러한 의존성을 만족하는 순서를 결정하는 핵심 알고리즘이다. 로봇공학에서는 작업 계획, 매니퓰레이션 시퀀스, 다중 로봇 협력 등에서 활용된다.

24. 참고 문헌

  • Kahn, A. B. (1962). “Topological sorting of large networks.” Communications of the ACM, 5(11), 558–562.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
  • Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
  • Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.

version: 1.0