Tarjan 알고리즘으로 순환 의존성 찾기
개별 사이클이 아니라 SCC 단위로 시각화하는 이유
SCC(Strongly Connected Component, 강한 연결 요소)란 방향 그래프에서 서로 오갈 수 있는 노드들의 최대 집합을 말한다.
같은 SCC에 속하는 임의의 두 노드 u, v에 대해 다음 조건이 모두 성립한다.
u에서 v로 가는 경로가 존재한다.
v에서 u로 가는 경로가 존재한다.
아래 그림을 보면 이해하기 쉬울 것이다.
예를 들어 1에서 3으로 갈 수 있고 3에서도 다시 1로 갈 수 있다면 두 노드는 같은 SCC에 속할 수 있다. 반면 2에서 4로 갈 수 있지만 4에서 2로 돌아가는 경로가 없다면 두 노드는 같은 SCC에 속하지 않는다.
여기서 중요한 점은 하나의 SCC 안에 여러 개의 개별 사이클이 존재할 수 있다는 것이다.
1 → 2 → 1
1 → 2 → 3 → 1
2 → 3 → 2
플러그인이 이 사이클들을 하나씩 모두 시각화한다면 같은 노드와 간선이 여러 결과에 반복해서 등장한다. 그래프가 복잡해질수록 개별 사이클의 수는 크게 늘어날 수 있고, 사용자는 여러 그림 중 어느 것을 기준으로 순환을 해소해야 하는지 판단하기 어려워진다.
하지만 위의 노드들이 모두 서로 도달할 수 있다면 하나의 SCC로 묶을 수 있다.
SCC 1 = {1, 2, 3}
이렇게 표현하면 가능한 모든 순환 경로를 나열하는 대신, 서로 얽혀 있는 문제 영역 전체를 한 번에 보여줄 수 있다.
이 플러그인의 목적은 사이클의 정확한 개수를 세는 것이 아니다. 어떤 클래스와 패키지들이 서로 얽혀 있으며, 순환을 해소하려면 어느 범위를 함께 살펴봐야 하는지 보여주는 것이다.
따라서 개별 사이클을 모두 열거하기보다 서로 순환 가능한 노드들을 SCC 단위로 묶어 시각화하는 편이 목적에 더 적합했다.
내 플러그인의 경우 클래스 그래프, 패키지 그래프 이렇게 2가지 경우를 각각 타잔 알고리즘으로 순환을 분석하여 각각의 .mmd 파일에서 보여준다.
타잔 알고리즘 소개 (시간복잡도, 코드 원리 설명)
package com.minsun.analyzer;
/**
* Tarjan 알고리즘으로 {@link DependencyGraph} 의 강결합요소(SCC)를 찾는다.
*
* <p>SCC 하나 = "서로 도달 가능한(=순환으로 얽힌) 노드 덩어리". 크기 ≥ 2 인 SCC 는
* 그 안에서 반드시 순환이 존재한다. 이 방식은 개별 순환(elementary cycle)을 모두
* 나열하지 않고 덩어리로 묶어 보여주므로 조합 폭발을 피한다.
*
* <p>참고: 재귀 DFS 구현이라 매우 깊은 그래프(수천 depth)에서는 스택 한계에 닿을 수
* 있다. 실제 대형 프로젝트에서 문제가 되면 명시적 스택 기반으로 전환한다.
*/
public final class TarjanScc {
private final DependencyGraph graph;
private int index = 0;
private final Map<String, Integer> indices = new HashMap<>();
private final Map<String, Integer> lowlink = new HashMap<>();
private final Deque<String> stack = new ArrayDeque<>();
private final Set<String> onStack = new HashSet<>();
private final List<List<String>> components = new ArrayList<>();
private TarjanScc(DependencyGraph graph) {
this.graph = graph;
}
/**
* 그래프의 모든 SCC 를 반환한다. 각 SCC 는 노드 이름 정렬,
* SCC 목록은 대표(첫) 노드 기준 정렬 → 결정적 출력.
*/
public static List<List<String>> stronglyConnectedComponents(DependencyGraph graph) {
TarjanScc tarjan = new TarjanScc(graph);
for (String node : graph.nodes()) {
if (!tarjan.indices.containsKey(node)) {
tarjan.strongConnect(node);
}
}
tarjan.components.forEach(Collections::sort);
tarjan.components.sort(Comparator.comparing(component -> component.get(0)));
return tarjan.components;
}
/**
* 순환을 이루는 SCC 만 반환한다.
* 크기 ≥ 2 이거나, 크기 1 이어도 자기 자신으로의 간선(self-loop)이 있으면 순환이다.
*/
public static List<List<String>> cycles(DependencyGraph graph) {
List<List<String>> result = new ArrayList<>();
for (List<String> component : stronglyConnectedComponents(graph)) {
if (component.size() >= 2) {
result.add(component);
} else {
String only = component.get(0);
if (graph.successors(only).contains(only)) { // self-loop
result.add(component);
}
}
}
return result;
}
private void strongConnect(String v) {
indices.put(v, index);
lowlink.put(v, index);
index++;
stack.push(v);
onStack.add(v);
for (String w : graph.successors(v)) {
if (!indices.containsKey(w)) {
strongConnect(w);
lowlink.put(v, Math.min(lowlink.get(v), lowlink.get(w)));
} else if (onStack.contains(w)) {
lowlink.put(v, Math.min(lowlink.get(v), indices.get(w)));
}
}
// v 가 SCC 의 뿌리면, 스택에서 v 까지 팝해 한 덩어리로 묶는다.
if (lowlink.get(v).equals(indices.get(v))) {
List<String> component = new ArrayList<>();
String w;
do {
w = stack.pop();
onStack.remove(w);
component.add(w);
} while (!w.equals(v));
components.add(component);
}
}
}큰 그림 그려보기
TarjanScc 클래스에 3가지 메서드가 있다.
stronglyConnectedComponents
cycles
strongConnect
외부에서 TarjanScc.cycles를 호출하면서 시작된다.
cycles 메서드가 시작되면 곧바로 List<List<String» 타입으로 SCC 목록을 반환하는 stronglyConnectedComponents 메서드를 호출하여 결과값으로 for문을 돌린다. 해당 반환 결과는 전체 SCC 목록을 담고 있다.
SCC의 크기가 2 이상이면 그래프에서 순환이 발생하고 있다는 의미이므로 최종 순환 결과 집합에 추가한다.
SCC의 크기가 1일 경우 self 순환이 발생할 경우에만 최종 순환 결과 집합에 추가한다. (self 순환은 의도적인 순환일 경우가 많을 것 같아서 시각화하는 게 맞을지 아직도 잘 모르겠다. 추후 self 순환이 문제가 되지 않는다고 판단하면 최종 순환 결과 집합에서 제거하는 방향으로 변경할 수도 있다.)
stronglyConnectedComponents 메서드에서는 그래프의 모든 노드를 순회하면서 strongConnect 메서드를 호출한다.
서로 연결되어 있지 않은 SCC가 있을 수 있기 때문에 모든 노드를 순회하는 코드가 있어야 하기 때문이다.
가장 핵심적이 되는 부분은 strongConnect 메서드이다.
0 → 1 → 2 → 0이라는 SCC가 존재한다고 가정하고 흐름을 따라가보자.
노드 v가 0이라고 가정하고 출발해보자.
indices와 lowlink의 key가 0일 때 value를 0으로 갱신해주고 index++하여 index는 1이 된다. 그리고 0을 스택에 push한다.
아직 indices에는 0의 자식 노드인 1이 없으므로 if문을 통과하여 재귀로 노드 1을 전달한다.
indices와 lowlink의 key가 1일 때 value를 1로 갱신해주고 index++하여 index는 2이 된다. 그리고 1을 스택에 push한다.
아직 indices에는 1의 자식 노드인 2가 없으므로 if문을 통과하여 재귀로 노드 2를 전달한다.
indices와 lowlink의 key가 2일 때 value를 2로 갱신해주고 index++하여 index는 3이 된다. 그리고 2를 스택에 push한다.
이번에는 indices에 0이 있으므로 else if문을 확인한다. stack에 0을 넣은 적이 있으므로 통과한다.
Math.min(lowlink.get(v), indices.get(w)) == Math.min(lowlink.get(2), indices.get(0)) == 0이므로 2의 lowlink를 0으로 갱신해준다.
2의 재귀 호출이 끝나고 다시 노드 1의 호출 지점으로 돌아온다.
Math.min(lowlink.get(v), indices.get(w)) == Math.min(lowlink.get(1), indices.get(2)) == 0이므로 1의 lowlink를 0으로 갱신해준다.
1의 재귀 호출이 끝나고 다시 노드 0의 호출 지점으로 돌아온다.
Math.min(lowlink.get(v), indices.get(w)) == Math.min(lowlink.get(0), indices.get(1)) == 0이므로 0의 lowlink를 0으로 갱신해준다. (이미 0으로 박혀있긴 하다.)
0의 경우 SCC의 뿌리이다. 그리고 stack에는 0과 SCC를 공유하는 0, 1, 2 노드가 들어있다.
따라서 do while문에서 stack에서 차례로 pop해 component에 push해준다.
이로써 component에는 SCC 한묶음이 들어있고 이를 components에 push해준다.
시간복잡도
각 노드와 간선을 한번씩 확인하므로 O(V + E)이다.