ps:strongly_connected_component
강한 연결 요소 (Strongly Connected Component / SCC)
- 내가 학생시절 배울때 들었던 이 용어의 번역은 '강결합 요소'였다. 그런데 검색해보니 강결합요소, 강연결요소, 강한 결합 요소, 강한 연결 요소 등등이 모두 사용되고 있었다.. 일단 한국어 위키피디아를 기준으로 강한 연결요소라고 제목을 달아놓긴 했는데.. 웬만하면 그냥 SCC라고 부르는게 편할것 같다.
- 기본 개념은 strongly connected component를 참고.
- 노드들을 SCC들로 분할해서, SCC들이 노드가 되도록 만든 그래프를 condensation graph 라고 부른다.
알고리즘
- 보통 SCC를 설명하는 블로그들에서는 Kosaraju 알고리즘과 Tarjan 알고리즘을 언급한다. 둘다 시간 복잡도는 O(V+E)로 동일하다.
- 코사라주 알고리즘은 좀더 이해하기는 간단하다. 하지만 역방향 그래프를 추가로 만들어줘야 하는게 좀 번거롭다. 그래서 타잔 알고리즘을 좀더 많이 쓰는것 같다.
- 각 알고리즘의 동작 방식은 아래 링크들을 참고
- https://jason9319.tistory.com/98 - 코사라주, 타잔
- cp-algorithm - 코사라주
- kks 블로그 - 타잔
- 나도 처음에는 타잔 알고리즘을 구현해서 문제를 풀기는 했는데, DFS를 재귀로 짜면 깔끔하지만 비재귀로 바꿔서 구현하기가 좀 까다로운 형태였다.
- 타잔 알고리즘의 비재귀 구현 예시 - stackoverflow
- 그래서 좀더 찾아보던중 pyrival에서 비교적 깔끔한 비재귀 DFS기반 구현체를 발견했다 - 소스코드. 타잔 알고리즘의 느낌으로 이해해보기에는 조금 다른부분이 많아서 의아해하다가, 아예 다른 알고리즘인 것을 뒤늦게 알게 되었다. 위키피디아에 코사라주, 타잔과 더불어 소개된 Path-based strong component algorithm이었다.
- Path-based strong component algorithm의 위키 설명에 따르면, 그냥 path를 스택에 저장했다가 그걸 이용해서 처리하는 방식이면 대충 다 뭉퉁그려서 이렇게 부르는것 같고, 디테일하게는 여러 버전이 있는듯 하다. path 스택을 사용하지 않고, discovery order들만 저장해서 처리하는 타잔 알고리즘이 좀더 아름다운 느낌이긴 한데, 비재귀로 구현할때는 이게 더 구현이 간단했다.
- 시간복잡도는 여전히 O(V+E)이다
- 그래서 나도 그냥 pyrival의 구현체를 사용하기로 했다.
- 4196 에서 타잔 알고리즘과 함께 간단하게 돌려본 결과는 이쪽이 제일 빨랐다. 엥?
- 재귀 타잔:1420~1476ms, 비재귀 타잔: 1308ms, 비재귀 path-based: 1192ms 의 시간이 걸렸다.
- 메모리는 이쪽이 좀더 많이 먹는것 같다.
- 추가: 이후에 Path-based algorithm 대신, Path-based algorithm중 가장 최근 발표된 버전으로 알려진 Gabow의 알고리즘으로 검색보니 약간의 추가된 자료를 찾을수 있었다.
- https://talzuchung-kty.tistory.com/17 을 참고하면, Gabow 알고리즘이 Tarjan 알고리즘보다 좀더 빠르게 돌아간다는 논문이 있다고 한다.. 오..
- 세줄요약
- SCC 알고리즘은, 잘 알려진 Kosaraju, Tarjan 알고리즘과 좀 덜 알려진 Path-based strong component algorithm 이 있다.
- Path-based algorithm은 여러 버전이 있는데, 그중 Gabow의 알고리즘이 가장 최근(2000년)에 나왔고, 실험적으로 Tarjan 알고리즘보다 좀더 빠르다
- 그래서 나도 Gabow의 Path-based algorithm을 사용하겠다.
구현 / 설계
- 알고리즘의 구현에 있어서는 Pyrival의 코드 를 살짝만 고쳐서 사용하기로 했다.
- 비재귀라 재귀 깊이 초과 문제에서 안전하고, 속도도 가장 빠르다
- 설계에 있어서 고려사항들
- scc를 사용하는 문제들 중 다수는 scc로 만든 condensation graph를 필요로 한다.
- condensation graph에서, 소스 노드나 싱크 노드들을 구하는 문제
- 사실 이거는 굳이 condensation graph를 전부 만들지 않고 그냥 node to scc 매핑들로부터 바로 풀어나가는 것이 좀 더 효율적이긴 하다. 하지만 condensation graph를 만들어놓고 작업하는게 개념적으로 이해하는 것이나, 구현하는 것이나 더 간단하다..
- condensation graph에서, 위상정렬 순서에 기반해서 DP를 수행하는 문제
- 등등..
- 그래서 결정 사항들
- SCC를 만드는 함수
- SCC to nodes 매핑만 리턴할것인가 (list[list[int]]) node to SCC 매핑도 리턴할것인가?
- SCC를 리턴한다는 컨셉이라면, node의 리스트가 하나의 SCC이므로 SCC의 리스트만 리턴하면 충분할것인데..
- 근데 오히려 이후 작업에는 node to SCC가 필요한 경우가 더 많다. condesantion graph를 만든다거나, 2-sat에서 해의 유무를 체크한다던가..
- 근데 이 경우에도 SCC의 갯수를 알아야 할 경우는 종종 있다.. 그냥 node to SCC 에 max를 돌리면 되긴 하지만..
- 사실 한쪽에서 다른쪽을 만들어내는 것은 매우 간단하긴 하다..
- 차라리 역발상으로 node to SCC 매핑만 리턴할까???? ⇒ 그럴듯한것 같기도 했으나.. 둘다 필요하다..
- 둘다 리턴하는 것으로 결정.
- 이름은 뭘로 할까?
- 일반적으로는 find_scc일텐데.. 근데 teflib에서는 동사절로 함수이름을 짓기 보다는 그냥 알고리즘 이름을 써왔잖아.. 그냥 길어도 strongly_connected_component로 이름을 짓자.
- component or components? ⇒ scc만 리턴할때는 후자도 일리가 있다고 생각했는데.. node to SCC매핑도 같이 넘기기로 했으니까 알고리즘 이름을 택해서 전자로 가는게 맞다.
- condesantion graph를 만드는 함수를 따로 만들것인가? 먼저 scc를 구하고 그것을 인자로 넘기는 식으로 할까, 아니면 아예 한번에 할까?
- 만들자. 그리고 한번에 다 처리되도록 하자.
sccs, scc_by_nodes = tgraph.strongly_connected_component(graph) scc_graph = tgraph.condensation_graph(graph, sccs, scc_by_nodes)- 이것보다
scc_graph, sccs, scc_by_nodes = tgraph.condensation_graph(graph)- 이게 나은것 같다. 리턴값이 3개나 되는것은 안예쁘지만, 그래도 이게 많이 심플하다.
코드
사용예
- …
- 문제들
- 축구전술 : 100,000 / 100,000
- 도미노 : 100,000 / 100,000
- ATM : 500,000 / 500,000
ps/strongly_connected_component.txt · 마지막으로 수정됨: 2023/03/13 02:02 저자 teferi
토론