3. Directed Graph(Digraph)

Directed graph는 edge의 방향이 존재하는 그래프이다.

우리 주변에 매우 많은 것들은 서로 연결되어있고, 가리키는 방향이 정해져있다.

프로그래밍으로 따지면, 상속관계, 함수의 호출구조 등이 있고, 응용은 무궁무진하다.

 

사실 이전에 배웠던 Undirected graph는 양방향 directed graph로도 볼 수 있다.

 

1) Digraph API

 

Diagraph는 Undirected graph와 동일하게 Sparse Matrix를 표현할 때 사용하는, Adjacency-list를 주로 사용한다.

Digraph API는 Undirected graph의 API와 완전히 동일하며, 모든 Edge의 방향을 바꾸는 연산이 추가된다.

 

Digraph reverse()

 

구현 또한 완전히 동일한데, addEdge함수만이 양방향이 아닌 한쪽방향으로만 추가가 된다.

즉, Undirected graph를 모든 Edge가 양방향인 Directed graph로 볼 수 있다.

 

//Undirected graph
public void addEdge(int v, int w){
    adj[v].add(w);
    adj[w].add(v);
}

//Directed graph
public void addEdge(int v, int w){
    adj[v].add(w); // v -> w
}

 

2) Digraph search

 

Digraph 또한 DFS, BFS가 가능한데, 구현은 Undirected와 완전히 동일하다. 다만 다른점은, 방향이 반대인 곳은 못간다는 것이다.

 

Digraph의 DFS 응용은 Reachability가 있다.

Reachability problem이란 source vertex로 부터 닿을 수 있는 모든 vertex를 찾는 문제이다.

이 문제는 여러가지에 적용될 수 있고, Digraph의 DFS로 해결할 수 있다.

첫번째 예시로, 모든 프로그램은 digraph로 볼 수 있다.

Vertex = basic block of instructions, Edge = jump

이를 Digraph로 표현한 후 닿을 수 없는 코드는 제거하거나, 코드의 탈출구까지 도달하지 못해 무한루프를 도는 부분을 탐색할 수 있다.

두번째 예시로, Garbage collector를 생각할 수 있다.

객체들의 참조관계를 directed graph로 표현하여, root로부터 닿을 수 없는 부분을 메모리에서 제거한다.

 

Digraph의 BFS 응용은 웹 크롤러가 있다.

우리는 웹페이지를 탐색할 때 보통 너무 깊게 탐색하지 않고, 폭넓게 탐색하는 경향이 있다. 따라서,  BFS를 응용하여 웹 크롤링을 개발 할 수 있다.

 

3) Topological sort

 

Task들이 있고,  Task들간에 선행 제약사항이 있는 경우 이를 Digraph로 표현할 수 있다

또한, 만약 Cycle이 존재하지 않는 DAG(Directed acyclic graph)일 경우, 모든 Edge가 위쪽을 가리키는 동형의 DAG로 표현할 수 있다. 이를 Topological sort라고 한다.

역 또한 성립하는데, topological order으로 표현될 수 있을 경우, Cycle이 존재하지 않는다.

 

직관적으로, Cycle이 존재할 경우 아래를 가리키는 Edge가 반드시 존재하게 되므로 topological order는 불가능하다.

출처 : coursera, Algorithm part2 lecture

 

이렇게 표현할 경우, 우리는 Task에 대해 우선순위 Scheduling을 할 수 있다.

방법은 다음과 같다.

1) DFS를 수행하고 return된 순서에 따라 Stack에 넣는다(post order)

2) Stack에서 차례대로 꺼내 출력한다(topological order)

 

따라서, DAG임을 보장하기 위해 Cycle을 찾는 것이 중요함을 알 수 있다.

DFS를 이용하면, Cycle을 탐색할 수 있다(자세한 설명은 생략)

Cycle탐색을 이용하면 순환 참조와 같은 것들을 찾을 수 있다.

 

4) Strong components

 

vertex v, w에 대해, v -> w인 경로와 w -> v인 경로가 존재한다면 서로 strongly connected라고 한다.

strong connectivity는 equivalence relation을 갖는다.

그것은 다음과 같다.

v is strongly connected to v 

if v is strongly connected to w, then w is strongly connected to v 

if v is strongly connected to w and w to x, then v is strongly connected to x. 

 

Strong component란 strongly-connected vertex들의 최대 집합이다.

(집합 내부 모든 요소들은 상호간에 strongly connected이다)

 

출처 : coursera, Algorithm part2 lecture

 

strongly component는 앞서 undirected graph에서 보았던 connected component에서 처럼 id를 부여함으로서 구분할 수 있다.

프로그래밍에서 strongly component는 집합내부에 상호간에 연결관계가 강하므로, 하나의 패키지로 묶을 요소들을 결정할 때 이를 응용할 수 있다.

 

그렇다면 계산은 어떻게 할까? 이러한 strongly component를 구하는 여러 알고리즘이 개발되었는데,  여기서 소개할 그 중 하나는 1980년대에 개발된Kosaraju-Sharir algorithm이다. Digraph G가 주어졌을 때, 다음과 같은 두 phase를 거친다.

- Phase1 : G를 reverse하고, topological sort로 Stack에 집어넣는다.

이렇게 되면, Stack에 꺼낼 때는 맨 마지막 Task가 먼저 꺼내지게 되며, 원 그래프의 order과 완전히 반대 순서이다.

- Phase2 : Stack에서 꺼낸 순서를 고려하여 원래 그래프 G에 대해 DFS를 수행한다. 

이렇게 맨 마지막 Task부터 검사해야 순차적으로 바로바로 strong component를 구할 수 있어, 성능이 향상되며, 성능은 E + V에 비례한다. 다만 두번 DFS를 수행해야하는 overhead가 있다.