[Algorithm Part 2] 2. Directed Graph

이번 글에서는, 여러 가지 digraph-processing algorithm에 대해 살펴볼 것이다.

---

Digraph

Definition

Digraph(=Directed Graph): set of vertices connected pairwise by directed edges (connection & direction)

Terminology

In-degree: number of edges leaving the vertex

Out-degree: number of edges coming into the vertex

Path: sequence of vertices connected by directed edges

Cycle: path whose first and last vertrices are the same

 

두 vertex사이에 경로가 있으면, 두 vertex는 "연결되어 있음"을 의미한다.

Graph VS Digraph

graph와 digraph는 edge(s) 방향을 제외한 모든 것이 같다.

때문에, graph design pattern과 동일하게 digraph-processing algorithm을 설계하면 된다.

Digraph representation

graph와 동일하다. 다만, edge에 방향성이 존재하기에, 그에 맞게 edge를 적절히 표현해야 한다.

• Graph: if v-w exists, then adj[v][w] = adj[w][v] = true (or adj[v].append(w), adj[w].append(v))
• Digraph: if v→w exists, then adj[v][w] = true (or adj[v].append(w))

---

1. Digraph search

방향 그래프 탐색은 source vertex(=s)와 연결된 모든 vertices(=v)를 찾는 문제다.

방향 그래프 탐색 알고리즘에는 graph search와 동일하게 1). dfs 2). bfs가 있다.

엄밀히 말하자면, dfs와 dfs는 방향 그래프 탐색 알고리즘에 가깝다.

무방향 그래프(무방향 edge(s))를 쌍방향 그래프(쌍방향 edge(s))로 취급하여 문제를 풀었기 때문이다.

 

Diagraph의 dfs, bfs는 graph의 dfs, bfs와 99% 동일하기에 생략하겠다.

---

2. Topological sort

Topological sort는 partical order를 호환 가능한 linear order로 변경하는 문제다.

• partial order(=부분 순서): 모든 원소의 대소 관계가 정해지지 않은 집합 (e.g., 대학교 전공 커리큘럼, 제조 공정)
• linear(or total) order(=완전 순서): 모든 원소의 대소 관계가 정해진 집합 (e.g., 실수)

 

partial order는 가위바위보 같은 순환 구조가 존재하지 않는다.

때문에, 그래프가 DAG(Directed Acyclic Graph)일 때만, 위상 정렬을 할 수 있다.

 

자식 노드가 부모 노드보다 크다고 가정하기 때문에, 모든 자식 노드는 부모 노드 뒤에 배치되어야 한다. 

즉, 배치 순서가 reverse postorder로 되어야 한다.

재귀 DFS을 활용하면 쉽게 reverse postorder로 정렬할 수 있다.

Algorithm

• 모든 vertex(=s)를 순회하면서, 방문 여부를 확인한다. s를 방문하지 않았으면,
  정점 s를 시작으로 재귀 DFS 그래프 탐색을 한다.
• 이때, 재귀 성질을 이용해 v의 인접 정점(=w)을 먼저 배치한 뒤 v를 맨 앞에 배치한다.
  자세히 말하자면, dfs(v)는 3단계로 구성된다. 1). v를 방문한다. 2). dfs(w)로 w를 방문 및 배치한다. 3). v를 배치한다.

---

Correctness of algorithm

DAG의 reverse postorder가 linear order임을 증명해보겠다.

 

edge v→w가 있다고 가정하자.

이때, dfs(v) 호출 당시 3가지 경우의 수만 존재한다.

1. dfs(w)가 아직 호출되지 않은 경우:
   dfs(v)가 dfs(w)를 호출하기에, w가 배치된 뒤 v가 배치된다. 때문에, v가 w앞에 배치된다.
2. dfs(w)가 먼저 호출되고 반환된 경우:
   w가 먼저 배치 되었기에, v가 w앞에 배치된다.
3. dfs(w)가 먼저 호출되고 반환되지 않은 경우:
   DAG에서는 불가능하다.

DAG는 위 3가지 경우 중 2가지 경우만 일어나고,

2가지 경우는 linear order 성질에 위배되지 않기에, correctness하다.

---

3. Directed cycle detection

Directed cycle detection은 뱡향 그래프의 순환 여부 확인 문제다.

(e.g., 순환 참조 및 순환 상속)

 

위 문제는 DFS로 쉽게 풀 수 있기에, 알고리즘 설명은 생략하겠다.

---

4. Strong components

Definition

vertices v and w are strongly connected if there is a directed path from v to w and a directed path from w to v.

A strong connected component(SCC) is a maximal subset of stronly-connected vertices.

 

strong connectivity query는 서로 다른 vertices의 강결합 여부를 물어보는 문제다.

(e.g., SW module 의존성 그래프에서 SCC 찾아 package 만들기)

 

위 문제는 2번의 DFS(Kosaraju-Sharir algorithm)을 통해 문제를 풀 수 있다.

정점 간의 연결성 정보를 저장한 배열(id[])을 구축해 문제를 푼다.
(id[v] == id[w]인 경우, 두 vertices가 같은 SCC에 속함을 의미한다.)

Kosaraju-Sharir algorithm

1. DFS을 통해, $G^R$의 reverse postorder를 구한다. ($\approx$ $G^R$의 topological sort)
2. $G^R$의 reverse postorder대로, vertex(=v)를 순회하면서, 방문 여부를 확인한다.
   1. 만약 v를 방문하지 않았으면, 정점 v를 시작으로 DFS 그래프 탐색한다.
      탐색 도중 장점(w=방문하지 않은 v의 인접 정점)을 방문하면,
      고유 "SCC 식별자"를 할당한다. (e.g., id[w] = count)
   2. 탐색 종료 시, 다음 SCC와 식별하기 위해 식별자를 수정한다. (e.g., count++)

---

Algorithm 설명

위 algorithm은 직관적으로 이해하기 힘들다. 

예시를 통해 이해해보도록 하자!!

 

그래프의 SCC를 찾기 위해선, 탐색 순서를 잘(?) 정해야 한다. 

예를 들어, DFS 탐색 순서를 C→D→B→A 순서로 DFS를 탐색할 경우, SCC를 찾을 수 있다.

하지만, 그 외의 탐색 순서(e.g., A→D→B→C) DFS를 탐색할 경우, SCC를 찾을 수 없다. 

왜냐하면, 탐색 경로가 탐색 범위(=현재 탐색하는 SCC 범위)를 벗어날 수 있기 때문이다.

예를 들어, A를 탐색할 때, 탐색 경로가 A를 벗어날 수 있다. 

그럼 적절한 탐색 순서를 구하는 방법에 대해 알아보자!!

high-level SCC부터 탐색을 진행해야 한다.

high-level SCC부터 DFS 탐색할 경우, 현재 탐색 범위(current SCC)와 이전 탐색 범위(previous SCC)만 탐색하기 때문이다.

(high-level node $\approx$ leaf node, low-level node $\approx$ root node)

 

$G^R$의 reverse postorder($G^R$의 topological sort)는

"high-level SCC의 임의의 정점이 먼저 나오고 low-level SCC의 임의의 정점이 나중에 나오는 배치 순서"를 가지고 있다.

위 순서대로 DFS 탐색을 진행하면, high-level SCC부터 찾은 후, low-level SCC를 찾는다.

 

그럼 다음과 같은 질문을 할 수 있다.

"$G$의 postorder의 reverse로 적절한 탐색 순서를 구할 수 있는 것이 아닌가?" 결과부터 말하자면 아니다.

$G$의 postorder는 "low-level SCC의 임의의 정점이 먼저 나오고 high-level SCC의 임의의 정점이 나중에 나오는 배치 순서"를 가지고 있다. 이 말은 "high-level SCC의 임의의 정점이 나온 뒤, low-level SCC의 정점이 나올 수 있음"을 의미한다. 그렇기에, "$G$의 postorder의 reverse는 절적한 탐색 순서를 제공하지 않는다.

---

Peformance

Topological sort와 SCC의 algorithm은 DFS를 기반으로 설계되기 때문에, time-complexity도 DFS와 같다.