graph_tool.topology 4

Sylen·2025년 1월 5일

아래는 1956년에 J. B. Kruskal이 쓴 고전 논문 "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem" (미국수학회 ( \textit{Proceedings of the American Mathematical Society}) 7권 1호, 48–50쪽)을 기반으로, 최소 스패닝 트리(MST)와 이 문제의 해법에 대해 최대한 친절하고 구체적으로 설명한 내용입니다. 특히 Kruskal 알고리즘(그의 “Construction A”)을 중심으로 증명 및 아이디어를 정리하였고, 간단히 TSP와의 연결점도 살펴봅니다.

1. 문제 배경 및 요약

문제 정의
- 주어진 연결 그래프 (G=(V,E))에서, 각 간선 (e \in E)마다 양의 실수 가중치(“길이”)가 주어진다고 하자.
- 목표: 전체 정점 (V)를 모두 포함(spanning)하면서, 간선들의 합(“길이”의 총합)이 최소가 되는 부분트리(subtree), 즉 최소 스패닝 트리(MST)를 구하는 것.
Kruskal의 주요 정리
- “모든 간선의 가중치가 서로 모두 다르게 주어졌을 때, MST는 유일(unique) 하다.”
  [
  \text{If all edge weights are distinct, then MST is unique.}
  ]
- 이 논문에서 Kruskal은 MST를 구하는 간단한 방법(=Kruskal 알고리즘)을 제시하고, 그 알고리즘을 통해 MST가 유일함을 보이는 증명을 제공했습니다.
TSP와의 연결
- 논문 제목에 “Traveling Salesman Problem(TSP)”이 언급되나, 실제로 TSP 자체를 풀기 위한 알고리즘이 제시된 것은 아님.
- Kruskal은 MST와 “최단 비분기(unbranched) 스패닝 트리” (즉, 모든 간선이 경로 형태로 연결된 트리, ‘지Hamiltonian path’와 유사)를 대비시키면서, TSP의 변형 문제(“unbranched spanning subtree” 최소화)와 MST 문제의 차이점을 언급.
- 결론적으로 TSP의 순회경로(사이클)와 MST는 구조가 크게 다름을 보이지만, MST 문제는 TSP의 특정 변형 문제(트리 형태)와 표면적으로 관련이 있다는 점을 지적함.

2. Kruskal 논문이 해결하려는 두 가지 문제

논문에서는 먼저 아래 두 문제를 제시합니다.

Problem 1: “연결 그래프 (G)에서 전체 정점을 스패닝하면서 간선 길이의 합이 최소가 되는 트리를 구하는 실용적(구체적) 방법을 제시하라.” → 이게 바로 “MST 구하기” 문제.
Problem 2: “연결 그래프 (G)에서 전체 정점을 스패닝하지만, 간선들이 뻗어나가지 않고(=분기가 없는) 경로 형태를 이루는(=한 줄로 연결된) 부분트리 중 길이 합이 최소인 것을 구하라.” → 이는 사실상 Hamiltonian path류 문제와 유사. TSP의 1차 변형 문제와 닮았으나, MST와 달리 훨씬 더 어려움.

Kruskal은 Problem 1을 성공적으로 풀어내지만, Problem 2는 그리 간단하지 않음을 지적합니다. TSP도 “Hamiltonian cycle”을 찾는 문제이므로, “unbranched spanning subtree”를 찾는 문제와 근본적으로 다루기 더 어려운 문제라는 점을 은연중에 언급합니다.

3. Kruskal 알고리즘 (Construction A)

Kruskal이 논문에서 소개한 “Construction A” 알고리즘(=지금 널리 알려진 Kruskal MST 알고리즘)을 정리하면 다음과 같습니다.

초기화: MST를 구성할 간선 집합 ( E_{\mathrm{MST}} )를 비어 있게 시작.
간선 정렬: 모든 간선을 길이(가중치)가 증가하는 순으로 정렬한다 (Kruskal 논문에서는 “짧은 간선부터 차례로 본다” 정도로 서술).
간선 하나씩 추가:
- 간선 목록을 짧은 순서대로 순회하면서, 현재 간선 ( e )를 추가했을 때 사이클이 생기지 않는다면 ( e )를 ( E_{\mathrm{MST}} )에 포함.
- 사이클이 생긴다면(즉, 이미 선택한 간선과 함께 루프를 형성한다면) 버린다.
스패닝 완성 시 종료: 모든 정점을 연결할 수 있을 만큼(즉, ( |V|-1 )개의 간선이 선택되면) 종료.
결과: ( E_{\mathrm{MST}} )가 MST를 이룬다.

이 과정을 Kruskal은 간단명료하게 설명했으며, 이어서 왜 이것이 MST가 되는지를 간단한 루프-대체(loop replacement) 논리를 통해 증명합니다.

“가장 짧은 간선을 하나씩 추가하는 과정에서, 사이클을 유발하는 간선은 배제. 이 방식으로 최종 얻는 트리는 길이 합이 최소임을 증명 가능.”

3.1 MST의 유일성 증명 (간선 가중치가 모두 다를 때)

Kruskal이 밝힌 핵심 정리는:

“모든 간선 길이가 서로 달라서 (\forall e_i \neq e_j)라면, MST는 단 하나뿐이다.”

이를 Kruskal 알고리즘 관점에서 증명 개략은 아래와 같습니다:

간선 길이가 모두 다르므로, “Construction A”에서 각 단계에서 선택되는 간선이 오직 하나로 정해진다(동일한 길이를 가진 간선이 없으므로 동률이 없음).
따라서 Kruskal 알고리즘이 “짧은 간선부터 필요한 만큼 추가”하는 과정은 유일하게 결정되는 절차.
만일 다른 방법으로 만든 어떤 “스패닝 트리” (T)가 있더라도, Kruskal 알고리즘이 택하지 않은 더 짧은 간선을 대체해서 길이를 더 줄일 수 있음을 보이면서 모순을 일으켜, 결국 Kruskal 알고리즘이 만든 결과가 유일한 MST임을 결론짓는다.

이것이 Joseph Kruskal이 짧은 2페이지 남짓 논문에서 빠르게 전개한 내용의 요지입니다.

4. Kruskal 논문의 그래프 이론 정리 (예비정리)

Kruskal 논문은 증명을 위해 먼저 다음과 같은 그래프 이론의 기초 정리를 (상당히 간단하게) 기술합니다:

“연결 그래프 (G)에서, (T\subseteq G)가 아래 조건을 모두 만족하면, 이것은 스패닝 트리임이 서로 동치다.”
1. (T)는 (G)의 스패닝 부분그래프이며, 간선 수는 (|V|-1).
2. (T)는 루프가 없는(=forest) “극대 확장” 부분그래프이자, 연결성 유지.
3. (\dots)

이 정리는 MST 증명 시 필수적으로 사용하는 루프 교환(loop replacement) 논법의 기초를 제공합니다. Kruskal 증명은 이 정리를 참조해서 간단히 마무리합니다.

5. TSP와 MST

TSP (Traveling Salesman Problem): 모든 정점을 단 한 번씩 방문하여 시작점으로 돌아오는 “최단 해밀턴 순환”을 찾는 문제. NP-난해로 잘 알려짐.
MST는 모든 정점을 연결하는 트리이되, 정점을 한 번씩 방문하는 것은 같지만 사이클이 없어야 하며(트리이므로) 경로 수가 분기될 수 있음. TSP에서 요구하는 “단일 해밀턴 순환”과 달리, MST는 여러 가지 경로(branch)로 구성될 수 있음.
Kruskal은 논문에서 TSP가 “unbranched spanning subtree(즉, 가지가 없는 경로)”를 찾는 것과 연관이 있음을 지적하지만, MST 문제와는 전혀 다른 (훨씬 더 어려운) 범주라는 점을 강조.

정리하면, MST는 그래프 전체를 커버하고 그 중 간선 합이 최소인 트리를 찾는 것, TSP는 그래프 전체 정점을 정확히 한 번씩 방문하는 순회를 찾는 것이라 구조가 다르지만, 둘 다 “간선 길이”가 주어진 그래프에서 “최적 비용 구조”를 찾는 문제라는 공통점을 갖는다고 볼 수 있습니다.

6. 결론 및 의의

Joseph Kruskal(1956)의 고전적인 논문은 Kruskal MST 알고리즘을 간단명료한 “Construction A” 방식으로 제시하고, 간단한 대체(arguing by loops) 증명을 통해 간선 길이가 모두 다르면 MST가 유일함을 밝혔다.
이 결과는 현재에도 MST 분야에서 가장 널리 쓰이는 알고리즘 중 하나가 되어, Prim 알고리즘, Borůvka 알고리즘 등과 함께 교과서적으로 정립되었다.
Traveling Salesman Problem과 MST 문제를 함께 언급한 이유는, “스패닝” 및 “간선 길이 최소화”라는 측면에서 유사해 보여도(Problem 1 vs Problem 2), 실제로는 분기 구조나 해밀턴 순환 유무에서 결정적으로 달라 TSP가 훨씬 어렵다는 사실을 부각하기 위함이라 할 수 있다.

따라서 Kruskal 논문은 매우 짧은 분량임에도 최소 스패닝 트리와 관련된 핵심 아이디어(정렬 & 루프 미포함 간선 추가)를 간결하게 서술하고, 한편으로 TSP 등 스패닝 관련 문제와 대조점을 제시해 이후 그래프이론/알고리즘 발전에 큰 영향을 미친 역사적 문헌이라 할 수 있습니다.

참고 문헌

J. B. Kruskal (1956), “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,” Proc. of the American Mathematical Society, 7(1), 48–50.
Otakar Borůvka (1926), “On a minimal problem,” Práce Moravské Přírodovědecké Společnosti, 3, 37–58.
Prim, R. C. (1957), “Shortest connection networks and some generalizations,” Bell System Technical Journal, 36(6), 1389–1401.
Cormen, T. H. et al., Introduction to Algorithms, MIT Press, MST 부분(Chapter 23).
Wikipedia: Minimum spanning tree & Traveling salesman problem.

아래 튜토리얼은 graph-tool 라이브러리의 min_spanning_tree() 함수를 이용하여 최소 스패닝 트리(Minimum Spanning Tree, MST)를 구하는 전 과정을 자세히 소개합니다. 초보자도 쉽게 따라 할 수 있도록 파이썬 코드, 상세한 한글 주석 및 추가 팁 등을 포함했으며, 알고리즘 원리(Prim, Kruskal)와 활용 방법을 친절하게 설명합니다.

1. 최소 스패닝 트리(MST)란?

정의: 연결 그래프 ( G=(V,E) )에서, 모든 정점 (V)를 포함하면서, 간선들의 가중치 총합이 최소가 되는 트리(Tree) 구조를 의미합니다.
예: 도시들을 노드로 두고, 도시 간 도로 비용(가중치)을 간선으로 연결했을 때, 도로 비용 합이 최소가 되도록 모든 도시를 연결하고 싶을 때 MST를 찾으면 됩니다.

1.1 MST를 구하는 대표 알고리즘

Kruskal 알고리즘: 간선을 오름차순 정렬 후, 사이클을 형성하지 않는 선에서 간선을 하나씩 추가.
Prim 알고리즘: 임의의 루트 정점에서 시작해, 이미 연결된 부분과 가장 짧게 연결될 수 있는 간선을 차례로 추가.

graph-tool에서는 min_spanning_tree() 함수 내에서 root 인자를 주지 않으면 Kruskal, 주면 Prim 방식을 사용합니다.

2. `min_spanning_tree()` 함수 개요

tree = gt.min_spanning_tree(
    g, 
    weights=None,   # 간선 가중치
    root=None,      # 루트를 지정하면 Prim 알고리즘, 아니면 Kruskal
    tree_map=None   # MST 결과를 담을 EdgePropertyMap (bool)
)

인자 설명:
- g: 그래프 객체 (Graph).
- weights: EdgePropertyMap 형태의 가중치. 없으면 모든 간선 동일 가중치로 취급 → 임의 MST.
- root:
  - None일 경우 → Kruskal 알고리즘 사용.
  - 정점을 지정할 경우 → Prim 알고리즘 사용(해당 정점을 루트로).
- tree_map: MST를 표시할 EdgePropertyMap을 직접 넘길 수도 있음(1이면 트리에 포함, 0이면 비포함).
반환 값:
- tree_map: EdgePropertyMap (bool 배열). MST에 속하는 간선에 True (==1), 그 외 False (==0).
시간 복잡도:
- Kruskal: 간선을 정렬 → ( O(|E|\log|E|) ).
- Prim: ( O(|E| + |V|\log|V|) ) 정도 (구현 세부에 따라 다름).
- 문서상으로 (\tilde{O}(|E|\alpha(|E|,|V|))) 형태로도 알려져 있음(Union-Find 구조 최적화 시).

3. 예시 코드 튜토리얼

이제 실제 파이썬 graph-tool에서 MST를 구하는 예제를 단계별로 살펴봅시다.

3.1 샘플 그래프 생성

우선 임의의 점들을 생성 후, Delaunay 삼각분할로 그래프를 만든 뒤, 각 간선의 길이를 유클리드 거리로 설정해보겠습니다.

import graph_tool.all as gt
import numpy as np

def example_min_spanning_tree():
    # 1) 무작위 2D 좌표 (400개)
    coords = np.random.rand(400, 2) * 10  # 0~10 사이
    # 2) Delaunay 삼각분할 -> 그래프 g, 좌표 pos
    g, pos = gt.triangulation(coords, type="delaunay")
    
    # 3) 간선 가중치 설정(유클리드 거리)
    weight_ep = g.new_edge_property("double")
    import math
    for e in g.edges():
        # pos[e.source()]와 pos[e.target()] 사이 거리
        xy_s = pos[e.source()].a  # np.array 형태
        xy_t = pos[e.target()].a
        dist = np.linalg.norm(xy_s - xy_t)
        weight_ep[e] = dist
    
    # 4) MST 구하기 (Kruskal 알고리즘)
    mst_eprop = gt.min_spanning_tree(g, weights=weight_ep, root=None)
    # mst_eprop은 bool 타입의 EdgePropertyMap
    
    # 5) 시각화: 원본 그래프 + MST 비교
    # (a) 원본 그래프
    gt.graph_draw(g, pos=pos, output="triang_orig.pdf")

    # (b) MST만 필터링
    mst_view = gt.GraphView(g, efilt=mst_eprop)
    gt.graph_draw(mst_view, pos=pos, output="triang_min_span_tree.pdf")
    
    # (c) MST 간선 수와 총 가중치 출력
    mst_edges = [e for e in g.edges() if mst_eprop[e]]
    total_weight = sum(weight_ep[e] for e in mst_edges)
    print(f"MST has {len(mst_edges)} edges, total weight={total_weight:.3f}")

if __name__=="__main__":
    example_min_spanning_tree()

코드 해설

Delaunay 삼각분할: 평면 점집합에서 그래프(삼각분할)와 좌표 info를 받음.
각 간선에 대해 유클리드 거리를 계산 → weight_ep[e] 할당.
min_spanning_tree(g, weight_ep) 호출:
- root=None → Kruskal 방식.
- 결과는 mst_eprop이라는 bool형 EdgePropertyMap으로 표시됨.
GraphView를 통해 MST만 필터링하여 시각화 가능.

실행 결과:

triang_orig.pdf: 400점에 대한 Delaunay 그래프(굉장히 촘촘).
triang_min_span_tree.pdf: 같은 좌표지만 MST 간선만 남겨 훨씬 간선 수가 적음.
콘솔에 MST has 399 edges, total weight=xxx.xxx 등이 출력.

3.2 Prim 알고리즘으로 MST 구하기

만약 특정 루트 정점을 정하고 싶다면 root=v0 식으로 인자에 정점을 넘겨주면 됩니다.

def example_min_spanning_tree_prim():
    g = gt.price_network(300)
    # 간선 weight 없으므로, 가중치=None -> 모든 간선 동일취급
    # 이때 root를 지정하면, Prim 알고리즘으로 MST 계산
    some_vertex = list(g.vertices())[0]  # 0번 정점을 root로
    mst_eprop = gt.min_spanning_tree(
        g, weights=None, root=some_vertex
    )
    # 후속 처리 동일
    ...

root 지정 시 = Prim, 미지정 = Kruskal.

4. 내부 알고리즘 개념

Kruskal:
- 간선들을 가중치 오름차순으로 정렬.
- 순서대로 간선을 확인하며, 현재 간선이 사이클을 만들지 않으면 포함.
- (|V|-1)개 간선이 선택되면 완료.
Prim:
- 임의 루트 하나 잡고, 방문한 정점 집합에서 출발.
- 방문한 정점과 방문 안 한 정점을 잇는 간선 중 가중치가 최소인 것을 선택하여 새로운 정점 방문.
- 모든 정점을 방문할 때까지 반복.

graph-tool은 자동으로 union-find(크루스컬)나 우선순위큐(프림) 등을 사용하여 MST를 빠르게 찾습니다.

5. 반환 결과 활용

tree_map[e] == True인 간선만 모으면 MST가 됩니다.
GraphView(g, efilt=tree_map)로 서브그래프를 뽑아 시각화나 추가 분석에 활용 가능.
MST 총 가중치: sum(weights[e] for e in g.edges() if tree_map[e]).

6. 주의사항 및 팁

가중치 설정:
- weights 인자가 없으면, 단순히 “간선 수가 최소인(=임의 MST)”을 찾음 (동등가중 그래프).
루트 지정:
- 미지정 → Kruskal.
- 지정 → Prim.
- 일반적으로 간선 수가 많으면 Kruskal, 정점 수가 많아도 괜찮습니다. 그러나 graph-tool 내부 구현에 따라 성능은 비슷합니다.
간선 중복/루프:
- 그래프가 유향이면, GraphView(g, directed=False) 형태로 무향 변환 시 MST를 구할 수 있음.
- 자기 루프나 병렬 간선은 MST와 직접적으로 상관없을 가능성이 큼(필요하면 filter).
시각화:
- MST만 별도 GraphView로 필터링하여 graph_draw.

결론

min_spanning_tree() 함수는 graph-tool에서 MST를 손쉽게 구하고 시각화할 수 있는 핵심 API입니다.

Kruskal(root=None) or Prim(root=정점) 알고리즘을 내부적으로 사용.
결과를 bool형 EdgePropertyMap으로 반환.
필터링(GraphView)을 통해 MST만 시각화하거나 가중치 합 계산 등 후처리 가능.

위 예시들을 토대로, 원하는 그래프(랜덤, 실제 데이터, Delaunay 등)에 적용하여 MST를 구하고 분석해볼 수 있습니다.
행복한 코딩 되세요!

아래 튜토리얼은 graph-tool 라이브러리를 사용하여, Wilson 알고리즘(loop-erased random walk 기반)으로 무작위 스패닝 트리(Random Spanning Tree)를 효율적으로 생성하는 과정을 설명합니다. 이 알고리즘은 Aldous-Broder 알고리즘(무작위 워크로 스패닝 트리를 생성)과 유사하지만, “cover time”보다 더 빠른 평균 시간 안에 스패닝 트리를 생성할 수 있도록 개선되었다는 특징이 있습니다.

Wilson 알고리즘의 핵심 아이디어 및 구현 과정을 수식, 개념, 원리에 초점을 맞추어, 초보자에게도 친절한 방식으로 자세히 설명하고, 파이썬 코드와 주석을 통해 실제 예시를 시도해보겠습니다.

1. Wilson 알고리즘 (무작위 스패닝 트리) 개요

1.1 문제 배경

스패닝 트리: 그래프 (G)가 있을 때, 모든 정점을 포함하면서 사이클이 없는 부분 그래프를 말합니다.
무작위 스패닝 트리: 스패닝 트리를 “동등한 확률” (혹은 가중치가 있다면 해당 비례확률)로 하나 뽑는 것.
- 대표 알고리즘:
  - Aldous-Broder: 임의 정점에서 시작하는 단순 랜덤워크로 모든 정점을 방문하면서, “처음 방문된 간선”들을 트리에 추가 → 결과로 나오는 트리가 균일한 확률분포로 샘플링된다는 정리.
  - Wilson: loop-erased random walk(사이클이 생기면 사이클을 지워버리는 방식)을 이용하여 더 효율적으로 뽑을 수 있음.

1.2 Wilson 알고리즘의 핵심 아이디어

Wilson 알고리즘(=loop-erased random walk 기반) 전체적인 흐름:

루트(root) 하나를 선택 (통상은 임의로 뽑거나, 별도 분포로 정해서).
해당 루트는 이미 스패닝 트리에 포함되었다고 가정.
다른 정점들 각각에 대해:
- 해당 정점에서 루트(혹은 이미 트리에 속한 정점)로 가는 loop-erased random walk(사이클이 생길 때마다 제거) 경로를 찾음.
- 그 경로를 트리에 추가.
모든 정점이 추가될 때까지 반복 → 최종적으로 무작위 스패닝 트리가 완성.

Loop-Erased Random Walk

“단순 랜덤 워크”를 하면서 사이클을 발견하면, 그 사이클을 경로에서 제거해버리는 절차.
결과적으로 “사이클 없는 경로”만 남게 됨.

2. 알고리즘 원리 (수식, 확률적 증명)

2.1 왜 균일 분포(Uniform Distribution)인가?

Aldous-Broder: “처음 방문” 간선을 선택할 때, 간선들이 균일 분포로 선택됨을 증명.
Wilson: “loop-erased random walk”로 각 정점이 트리에 연결되는 과정에서, 최종적으로 모든 스패닝 트리가 균일 확률 분포로 생성된다는 사실이 수학적으로 증명됨.
- “Cycle-popping” 관점: 스택 형태로 successor(다음 이동할 정점)를 무작위로 정해두고, 사이클이 관찰되면 해당 사이클의 스택 항목을 pop(버림)하는 과정을 거치면 결과적으로 트리가 유일하게 정해짐.

2.2 평균 실행 시간: Mean Hitting Time

Aldous-Broder 알고리즘은 cover time(그래프 내 모든 정점 방문에 걸리는 무작위워크 시간)을 상한으로 하는 반면,
Wilson 알고리즘은 mean hitting time(정점 분포에 따른 평균 방문 시간)으로 줄어든다는 것이 큰 이점.
일반적으로 mean hitting time (r)은 cover time (T_c)보다 작거나 동일하며, 특수 그래프에서는 훨씬 더 작아질 수 있음.

3. 파이썬 graph-tool 예시: Wilson 알고리즘 구현

graph_tool 라이브러리는 MST나 Aldous-Broder 방식(무작위 스패닝 트리)을 직접 지원하지 않습니다. 하지만, 우리는 Wilson 알고리즘을 커스텀으로 구현할 수 있습니다. 아래 코드는 간단한 형태로서, 무방향 그래프에서 “loop-erased random walk”를 구현한 뒤, 이를 이용해 스패닝 트리를 샘플링합니다.

주의: 예시는 시연 목적의 프로토타입 코드이며, 대규모 그래프에서는 최적화가 더 필요할 수 있습니다.

3.1 Wilson 알고리즘: 코드 개요

아래 wilson_random_spanning_tree(g, root=None) 함수를 구현해봅시다.

root 없으면, 그래프 정점 중 임의로 하나를 루트로 선택.
tree_edges(EdgePropertyMap 또는 Python 세트 형태) 초기화 → 공집합.
in_tree(VertexPropertyMap[bool]) 초기화 → 루트만 True.
모든 정점에 대해:
- 만약 해당 정점이 in_tree[v] == False라면:
  1) v에서 시작하는 무작위 워크를 하면서, loop-erased 경로를 계산.
  2) 경로의 마지막 정점이 이미 트리에 속하면, 그 경로를 tree에 추가.
완성된 tree_edges가 Wilson 알고리즘으로 생성된 무작위 스패닝 트리.

Loop-erased 경로 구현

임시 경로를 저장하며 진행: path = [].
새로 방문하려는 정점이 path 상에서 이미 존재한다면, 그 구간을 사이클로 인식 → 해당 구간 제거.
최종적으로 사이클이 없는 경로가 남게 됨.

3.2 전체 코드 예시

import graph_tool.all as gt
import random

def loop_erased_walk(g, start, in_tree):
    """
    g: graph-tool의 Graph 객체 (무방향)
    start: 시작 정점 (정수 idx 아님, graph-tool의 Vertex)
    in_tree: 이미 트리에 속한 정점을 표시하는 bool property map
    """
    path = []
    current = start
    # Python list로 'loop-erased' 경로를 관리

    while True:
        path.append(current)
        
        # 만약 current가 이미 트리에 속해 있다면 경로 종결
        if in_tree[current]:
            break
        
        # 아니면, current에서 임의 이웃 중 하나로 이동
        nbrs = list(current.out_neighbours())  # 무방향 그래프이므로 out_neighbours() == in_neighbours()
        next_v = random.choice(nbrs)
        
        # loop check: path 내 next_v가 있으면 사이클 부분 제거
        if next_v in path:
            # idx 찾기
            idx = path.index(next_v)
            # 사이클 부분 path[idx+1 ... 끝] 제거
            path = path[:idx+1]
            # 그리고 다시 진행
            current = path[-1]
        else:
            current = next_v

    return path

def wilson_random_spanning_tree(g, root=None):
    """
    Wilson 알고리즘으로 무작위 스패닝 트리를 생성
    g : graph_tool.Graph (무방향)
    root: (선택) Vertex. None이면 임의로 선택
    """
    # 1) 루트 설정
    if root is None:
        # 임의의 정점 하나 고르기
        root = random.choice(list(g.vertices()))

    # EdgePropertyMap 초기화: MST에 속하면 True
    tree_edge = g.new_edge_property("bool", val=False)
    # 정점이 트리에 속하는지 여부
    in_tree = g.new_vertex_property("bool", val=False)
    
    # 루트는 트리에 속한다고 표시
    in_tree[root] = True

    # 2) 각 정점에 대해 루트와 연결되지 않았다면 loop-erased walk로 경로 찾고 트리에 삽입
    for v in g.vertices():
        if not in_tree[v]:
            path = loop_erased_walk(g, v, in_tree)
            # path를 따라가며 트리에 추가
            # path[-1]는 이미 in_tree -> path는 loop-erased 경로
            # 간선 (path[i], path[i+1]) 추가
            for i in range(len(path)-1):
                # (path[i], path[i+1])가 스패닝트리에 들어간다
                e = g.edge(path[i], path[i+1])
                if e is None:
                    # or g.edge(...) might return multiple edges, handle as needed
                    raise RuntimeError("Edge not found or parallel edges exist.")
                tree_edge[e] = True
                in_tree[path[i]] = True
            # 마지막 정점도 표시
            in_tree[path[-1]] = True
    
    return tree_edge

### Demonstration Example

def example_wilson_tree():
    # 작은 예시 그래프
    # 6개 정점, 대충 임의 간선
    g = gt.Graph(directed=False)
    g.add_vertex(6)  # 정점 0..5

    edge_list = [(0,1),(1,2),(2,3),(3,4),(4,5),(0,2),(1,3),(2,4),(1,5)]
    for s,t in edge_list:
        g.add_edge(g.vertex(s), g.vertex(t))
    
    # Wilson 알고리즘으로 무작위 스패닝 트리
    root_vertex = g.vertex(0)
    st_eprop = wilson_random_spanning_tree(g, root_vertex)

    # 스패닝 트리 시각화
    # - 정점 좌표 임의
    pos = gt.arf_layout(g)  # or sfdp_layout, etc.
    
    # 전체 그래프 그리기
    gt.graph_draw(
        g, pos=pos,
        edge_color="gray",
        vertex_fill_color="white",
        output="orig_graph.pdf"
    )
    
    # 스패닝 트리만 표시
    # efilt=st_eprop로 필터링
    st_view = gt.GraphView(g, efilt=st_eprop)
    gt.graph_draw(
        st_view, pos=pos,
        edge_color="blue",
        vertex_fill_color="white",
        pen_width=2.0,
        output="wilson_spanning_tree.pdf"
    )

if __name__=="__main__":
    example_wilson_tree()

코드 해설

loop_erased_walk(g, start, in_tree):
- start부터 시작, 이미 트리에 속해있는 정점(in_tree == True)에 도달할 때까지 이동.
- 경로 중간에 사이클이 생기면 해당 사이클을 제거(loop-erase).
wilson_random_spanning_tree(g, root):
- 루트가 지정되지 않으면 임의 정점으로 선택.
- 각 정점 v에 대해, in_tree[v] == False 이면 loop-erased walk로 v에서 루트(혹은 트리에 속한 정점)에 도달하는 경로 계산 → 경로 내 간선들을 트리에 편입(tree_edge[e] = True).
시각화:
- GraphView(g, efilt=tree_edge)로 필터링하여 무작위 스패닝 트리를 별도로 그릴 수 있음.

결과: 실행할 때마다 다른 스패닝 트리가 무작위로 생성됩니다.

4. 고찰 및 성능

Mean hitting time:
- Wilson 알고리즘은 모든 정점을 순서대로 붙이는 구조이므로,
- 특정 분포(예: stationary distribution (\pi))로 root를 잡으면, 평균적으로 (2r) (혹은 (22r) 수준) random step만에 트리 생성을 마칠 수 있음.
Cover time와 대비: Aldous-Broder의 경우 (\le ) cover time (T_c)지만, Wilson은 그보다 작은 mean hitting time (r)로 충분한 경우가 많아서 더 효율적.
Directed graph: Eulerian 등 특정 조건에서 간단하게 적용 가능. 일반 경우에는 변형(Extra ‘death node’ 기법)으로도 구현할 수 있음.

5. 결론

Wilson 알고리즘은 무작위 스패닝 트리를 효율적으로(cover time보다 더 빠른 평균 시간) 생성하는 강력한 방법입니다.

사이클 제거(Loop-Erased Random Walk)라는 직관적 방법으로, 간단한 구현과 수학적 균일성 보장을 동시에 얻습니다.
graph-tool에 내장된 함수는 아니므로, 본 튜토리얼에서 소개한 커스텀 코드를 통해 구현할 수 있으며, 중간 시각화나 분석도 자유롭게 가능.

큰 그래프에서도, 랜덤워크 기반 기법(특히 Wilson)이 cover time 대비 효율적일 수 있으므로, 무작위 트리 생성이나 표본 추출(예: Markov Chain Monte Carlo 과정)의 한 단계로 사용 가능함이 장점입니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 random_spanning_tree() 함수를 이용해, Wilson 알고리즘 기반으로 무작위 스패닝 트리를 생성하는 전반적인 과정을 단계별로 설명합니다. 또한, 수식, 개념, 원리를 최대한 자세히 다루고, 이를 적용한 실용적인 파이썬 코드와 함께 초보자도 쉽게 따라 할 수 있도록 정성스럽게 안내합니다.

1. `random_spanning_tree()` 함수 개요

random_spanning_tree(
    g, 
    weights=None, 
    root=None, 
    tree_map=None
)

입력:
- g: graph-tool의 Graph 객체(무방향 혹은 유방향).
- weights(옵션): 각 간선에 대한 가중치(EdgePropertyMap). 특정 간선 집합(스패닝 트리)의 선택확률이 간선 가중치의 곱에 비례하여 뽑힘.
- root(옵션): 스패닝 트리의 루트 정점. 미지정 시, 확률적으로 뽑힘.
- tree_map(옵션): 스패닝 트리를 표시할 EdgePropertyMap. (기존 것이 있으면 덮어쓰거나, 없으면 새로 만든다.)
출력:
- tree_map: 스패닝 트리 여부를 (1/0)로 표시한 bool(또는 int) 타입의 EdgePropertyMap. (에지가 트리에 속하면 1, 아니면 0)

1.1 알고리즘(원리) 요약

이 함수는 내부적으로 Wilson 알고리즘(= ‘loop-erased random walk’ 기반)을 사용하여 무작위 스패닝 트리를 생성합니다.
Wilson 알고리즘은 Aldous-Broder보다 평균적(typical)으로 더 빠른 수행 시간을 보장:
- 시간 복잡도: (\mathrm{O}(T)) (여기서 (T)는 mean hitting time).
- 최악의 경우: (\mathrm{O}(n)) (정점 수).
- “대부분”의 sparse random graph에서는 (\mathrm{O}(n))보다도 실제 체감이 빠를 수 있음.

1.2 분포(확률) 정리

가중치가 없으면: 모든 스패닝 트리가 균일 분포로 뽑힘.
가중치(EdgePropertyMap)가 있으면: 스패닝 트리가 간선 가중치의 곱에 비례한 확률로 뽑힘 → 이론적으로 Matrix-Tree Theorem(Kirchhoff 등)과 동등한 결과.

2. Wilson 알고리즘 원리 자세히 살펴보기

Wilson 알고리즘은 크게 다음 단계를 통해 스패닝 트리를 생성합니다.

루트 정하기
- 사용자가 지정한 루트가 없으면, 라이브러리는 임의(steady-state 분포)에 따라 루트를 택하거나, (undirected면 uniform하게) 정함.
트리에 포함되지 않은 정점 (v)마다:
- (v)에서 시작하는 loop-erased random walk를 수행하여, 이미 트리에 속해있는 정점(또는 루트)에 도달할 때까지 진행.
- 사이클이 형성될 경우, 그 사이클을 경로에서 제거(loop-erased).
- 최종 경로 간선을 모두 트리에 추가 → (v)가 트리에 편입됨.
모든 정점이 트리에 편입될 때까지 반복 → 최종적으로 무작위 스패닝 트리가 완성.

2.1 루프 소거(Loop-Erasing)와 사이클 팝핑(Cycle Popping)

사이클이 생기면 즉시 제거함으로써, 트리에 사이클이 들어가지 않도록 함.
David B. Wilson의 문헌에서는 스택/사이클 팝핑 관점에서 증명:
- 스택(top)의 항목이 사이클 형성 시 pop으로 제거.
- 최종 남는 간선 구조가 스패닝 트리가 됨.

2.2 시간 복잡도 해설

본 알고리즘의 평균 실행 횟수(랜덤 successor 호출 횟수)는:
- (\mathrm{O}(r)), 여기서 (r) = mean hitting time.
- 많은 그래프에서 (r \ll T_c) (cover time) 이므로 효율적.

3. `random_spanning_tree()` 함수 사용 튜토리얼

이제 실제 파이썬에서 이 함수를 어떻게 사용하는지 안내합니다.

3.1 기본 예시

코드 예시

import graph_tool.all as gt
import numpy as np

def tutorial_random_spanning_tree():
    # 1) 무작위 그래프 생성 (Delaunay 삼각분할 예시)
    coords = np.random.rand(400, 2)
    g, pos = gt.triangulation(coords, type="delaunay")

    # 2) (옵션) 간선 가중치 설정
    #    - 여기서는 유클리디안 거리
    weight = g.new_edge_property("double")
    for e in g.edges():
        src, tgt = e.source(), e.target()
        p_src = pos[src].a  # numpy array
        p_tgt = pos[tgt].a
        dist = np.linalg.norm(p_src - p_tgt)
        weight[e] = dist

    # 3) random_spanning_tree() 호출
    #    - weights=weight: 간선 가중치 고려
    #    - root=None : 루트 무작위 선택
    #    - 반환값은 EdgePropertyMap (bool or int)
    tree_ep = gt.random_spanning_tree(g, weights=weight, root=None)

    print("Random spanning tree property map created:", tree_ep)
    # tree_ep[e] == 1이면 스패닝 트리에 속함

    # 4) 시각화
    #    - 전체 그래프 (회색)
    gt.graph_draw(g, pos=pos,
                  edge_color="gray", vertex_fill_color="white",
                  output="delaunay_orig.pdf")

    #    - tree_ep로 필터링한 스패닝 트리 (파랑)
    st_view = gt.GraphView(g, efilt=tree_ep)
    gt.graph_draw(st_view, pos=pos,
                  edge_color="blue", vertex_fill_color="white",
                  pen_width=2.0,
                  output="delaunay_rst.pdf")

if __name__ == "__main__":
    tutorial_random_spanning_tree()

코드 설명

삼각분할(Delaunay)으로 400개 무작위 좌표를 연결한 그래프 g와 각 정점 좌표 pos를 만듭니다.
간선마다 “유클리디안 거리”를 가중치로 설정. (weight[e] = dist)
gt.random_spanning_tree(g, weights=weight, root=None) 을 호출:
- 무작위 루트 선택
- Wilson 알고리즘(또는 Aldous-Broder, Eulerian 등 내부 최적화)에 기반하여 무작위 스패닝 트리를 생성
결과인 tree_ep(EdgePropertyMap)에 1로 표시된 간선이 스패닝 트리에 속함.
그래프 시각화:
- gt.graph_draw(...)로 전체 그래프
- GraphView(g, efilt=tree_ep)로 스패닝 트리만 필터링해서 별도 파일로 그림.

실행 결과

매번 실행할 때마다 다른 모양(스패닝 트리)이 무작위로 생성됨.
(중요) 만약 directed graph라면? 내부적으로 Eulerian이거나, Markov chain 등 조건에 따라 약간 달리 동작하지만, random_spanning_tree()가 자동 처리.

4. 고급 활용

루트를 직접 지정:
```
root_v = g.vertex(0)
tree_ep = gt.random_spanning_tree(g, weights=None, root=root_v)
```
- 이렇게 하면, 해당 루트로 스패닝 트리가 잡힘. (가중치가 있으면 확률 (\propto) 간선 곱)
MCMC-like 응용: Markov chain의 steady-state에서 임의 정점(루트) 뽑고, Wilson 기반으로 빠르게 spanning tree … 등등.
Directed Graph (Eulerian 등): “Stationary 분포”가 존재하는 그래프에서, root=None이면 적절히 임의 루트가 정해지거나,
- “death node”기법(문서 내 언급)으로 일반 방향 그래프에서도 동작.

5. 복잡도와 성능

이론적:
- 평균 시간은 (\mathrm{O}(T)), (T)는 mean hitting time.
- 최악은 (\mathrm{O}(n)).
- Sparse random graph 등에서는 (\mathrm{O}(n)) 근방, 종종 더 빠른 경우도.
실무:
- 1) graph-tool 내부 C++ 최적화가 잘 되어있다.
- 2) 임의워크(랜덤 successor) 호출 횟수가 많지 않음 → 대체로 빠른편.

6. 마무리

graph_tool.topology.random_spanning_tree()는 무작위 스패닝 트리를 빠르게 생성해주는 매우 유용한 함수입니다.

가중치가 없으면 균일 분포, 가중치 있으면 간선 곱에 비례한 확률로 트리가 샘플됨.
Aldous-Broder와 달리 Wilson(루프 소거)의 장점을 통해 cover time보다 적은 비용을 달성 가능(평균적).
대규모 그래프에서 MCMC, 신호처리, 복잡 네트워크 분석 등 다방면에서 활용.

본 튜토리얼 코드로 간단히 시도해보고, 실제 프로젝트에서는 다양한 파라미터(루트 지정, directed=Eulerian 여부, 가중치 설정)를 응용할 수 있습니다. 모두 즐거운 그래프 분석 되시길 바랍니다!

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 세 가지 주요 알고리즘, 즉

지배자 트리(dominator_tree)
위상 정렬(topological_sort)
트랜지티브 클로저(transitive_closure)

를 중심으로, 원리를 쉽게 설명하고 예시 파이썬 코드를 통해 사용 방법을 안내합니다. 각 알고리즘이 동작하는 수식, 개념, 원리를 이해하고, 이를 친절하고 정성스러운 코드 예제로 실습해봅시다.

1. `dominator_tree()`: 지배자 트리(Dominator Tree)

1.1 이론 개념과 원리

지배자(dominator): 방향 그래프 (G=(V,E))가 주어졌을 때, 특정 루트(엔트리) (r)에서 어떤 정점 (v)로 가는 모든 경로가 반드시 거치는 정점을 (u)라고 하면, “(u)는 (v)를 지배한다(dominates)” 라고 표현합니다.
직접 지배자(idom, immediate dominator): (v)의 지배자 중 가장 가까운(=다른 지배자를 모두 지배) 정점. 이 관계로 구성한 트리가 지배자 트리.
컴파일러 최적화에서 흔히 사용하는 개념:
- 예: 제어 흐름 그래프(CFG)에서 엔트리 블록이 다른 블록을 지배하는지 검사 → 루프나 분기 최적화, dead code 제거 등.

1.2 시간 복잡도

알고리즘은 Lengauer-Tarjan 알고리즘을 사용.
(\mathrm{O}((V+E)\log(V+E))) 의 시간으로 처리.

1.3 파이썬 예시 코드

아래는 dominator_tree()를 사용하는 간단 예시. (실제로는 더 복잡한 방향 그래프에서 주로 사용)

import graph_tool.all as gt

def example_dominator_tree():
    # 1) 임의 방향 그래프 생성
    #    여기서는 예시로 random_graph() + filter 이용
    g = gt.random_graph(100, lambda: (2, 2))  # 임의 edge 개수 (2,2)
    # 하지만 random_graph로 만든 건 기본적으로 무방향으로 생성
    # -> min_spanning_tree(...) 해도 트리가 생길 때 방향성은 임의
    #    예시를 위해 edge를 임의방향으로 바꿔도 됨
    
    # 2) 지배자 트리를 구할 그래프를 만든 뒤, entry(루트) 정함
    #    아래는 min_spanning_tree()로 간단히 "트리"를 구성 후
    #    (방향 그래프 가정) 무향이면 set_edge_filter() 시, in_degree==0 인 정점이 root
    stree = gt.min_spanning_tree(g)  # MST edges
    g.set_edge_filter(stree)         # MST로 필터
    # root 후보: in_degree()==0 인 정점(이게 entry)
    roots = [v for v in g.vertices() if v.in_degree() == 0]
    if len(roots) == 0:
        print("No root found!") 
        return
    root = roots[0]
    
    # 3) dominator_tree 계산
    dom_map = gt.dominator_tree(g, root)
    # dom_map[v] = v의 즉시 지배자 idom(v)의 정점 인덱스
    
    # 4) 결과 확인
    print("Dominator map array:", dom_map.a)
    # dom_map.a[v_idx] -> 그 v_idx 정점의 idom
    # 만약 본인이 루트면 dom_map[v]==v_idx(자기자신 또는 0)?

if __name__=="__main__":
    example_dominator_tree()

코드 설명

random_graph(100, lambda: (2,2))로 임의의 무방향 그래프 만들기(정확히는 edge가 (2,2)로 Poisson-ish).
그 뒤 min_spanning_tree(g) → MST edge filter → 방향성 문제는 단순예시라 건너뛰거나, 별도 그래프를 만들어도 됨.
root = in_degree()==0 (엔트리)
dom = gt.dominator_tree(g, root) 호출
dom[a]는 각 정점의 immediate dominator가 누구인지 인덱스로 표현.

2. `topological_sort()`: 위상 정렬

2.1 이론 개념과 원리

위상 정렬: 방향 비순환 그래프(DAG)에 대해, 모든 간선 ((u \to v))에 대해 (u)가 (v)보다 순서상 앞에 오도록 하는 정점의 선형 나열.
- 예: 작업 스케줄링(선행 작업이 먼저), 의존성 그래프 등.
조건: 그래프가 사이클이 없어야 함(DAG).
시간 복잡도: (\mathrm{O}(V+E)).
알고리즘 예) Kahn's 알고리즘, DFS 기반 알고리즘(포스트오더 역순).

2.2 파이썬 예시 코드

import graph_tool.all as gt

def example_topological_sort():
    # 1) 임의 방향 그래프 생성
    g = gt.random_graph(30, lambda: (3, 3), directed=True)  # directed=True
    # 2) (옵션) 무작위 간선이 cycle을 생성할 수도 있음
    #    실제로는 DAG인지 확인이 필요하나, 여기선 예시
    #    min_spanning_tree()로 필터링하면 cycle 제거된다고 가정
    tree_ep = gt.min_spanning_tree(g)
    g.set_edge_filter(tree_ep)  # MST는 cycle 없음 → DAG
    
    # 3) topological_sort
    sort_order = gt.topological_sort(g)
    # sort_order: 정점 인덱스를 위상 정렬 순서대로 배열
    print("Topological sort order:", sort_order)
    
    # 4) 예시: 정점 라벨(인덱스) 순서대로 출력
    #    - sort_order[-1] 가 DAG 상 마지막 정점
    #    - sort_order[0]  가 첫 정점
    
    # (추가) 정점 속성 만들어 시각화 등 응용 가능
    #        예: topological 레벨(순서) 표시
    level_vprop = g.new_vertex_property("int")
    for i, v in enumerate(sort_order):
        level_vprop[v] = i
    # level_vprop[v] = 위상정렬 상 v의 위치 (작을수록 앞)
    
    # (시각화) 생략

if __name__=="__main__":
    example_topological_sort()

코드 설명

random_graph(30, lambda: (3,3), directed=True)로 임의 방향 그래프 생성.
min_spanning_tree(g) 하면 cycle 없는 트리만 남음 → DAG 가정.
sort_order = topological_sort(g)
출력값은 PropertyMap이 아닌, 정점 인덱스의 ndarray(길이 = 정점 수).
원하는 응용: 정점마다 위상 레벨이나 순서를 property로 저장 → 시각화 또는 추가 계산.

3. `transitive_closure()`: 트랜지티브 클로저

3.1 이론 개념과 원리

트랜지티브 클로저(전달 폐포): 방향 그래프 (G=(V,E))에서, 두 정점 (u,v)를 연결하는 경로가 존재하면 ((u\to v))를 새로 추가하는 과정으로 얻는 “최소의(혹은 완전한)” 변형 그래프.
- 간단히 말해 “(u)에서 (v)로 갈 수 있으면 edge ((u\to v))가 생김.”
- 무한히 추가되지 않도록 “경로 존재하면 곧바로 1-hop edge”라고 표현.
시간 복잡도:
- 최악의 경우 (\mathrm{O}(V^3)) (Floyd-Warshall 같은).
- 또는 임의의 빠른 방법(행렬 곱으로 (\mathrm{O}(n^\alpha)}) 가능하나 상수 큼), sparse 그래프는 BFS 여러 번 등.
생성 결과:
- tc: 원본 그래프와 동일한 정점 집합, but edge set이 “경로 있으면 간선”형태.
- Undirected일 땐 connected component마다 Complete subgraph(=clique) 형성 → cluster graph.

3.2 파이썬 예시 코드

import graph_tool.all as gt

def example_transitive_closure():
    # 1) 임의 방향 그래프 생성
    g = gt.random_graph(30, lambda: (3,3), directed=True)
    
    # 2) transitive_closure
    tc = gt.transitive_closure(g)
    # tc: closure 그래프 (Graph 객체)
    
    # 3) 결과 확인: tc.edges() -> path 있으면 edge 존재
    print("Original edges:", g.num_edges())
    print("Closure edges:", tc.num_edges())
    
    # (option) 시각화하려면, pos는 g->tc 복사 등 필요
    # usage: gt.graph_draw(tc, ...)

if __name__=="__main__":
    example_transitive_closure()

코드 설명

유향 그래프 g 생성 (30노드, 평균 차수 (3,3)).
transitive_closure(g) → 새 그래프 tc가 반환됨.
- tc는 “모든 경로가 존재하는 pair(u,v)”에 대해 direct edge(u->v)를 갖음.
노드 수는 동일, but edge 수는 커질 수 있음(최대 (n*(n-1)) or (n(n-1)/2)).
BFS/DFS 여러 번을 내부적으로 돌리거나, Floyd-Warshall 계열로 처리.

4. 정리 및 마무리

dominator_tree(): 지정한 루트로부터 지배 관계(Immediate dominator) 파악 → 컴파일러 CFG 최적화 등에 활용. 시간: (\mathrm{O}((V+E)\log(V+E))).
topological_sort(): DAG 위상정렬. 시간: (\mathrm{O}(V+E)). 정점 순서 ndarray를 반환.
transitive_closure(): 그래프의 전달폐포. 각 정점쌍 ((u,v))에 대해 “경로 존재?” → 있으면 ((u->v)) 에지 추가. 시간: (\mathrm{O}(V^3)) 최악.
- 반환은 새 Graph 객체(closured graph).
- Undirected일 경우 component별로 clique화.

위 함수들은 graph-tool 라이브러리에서 직관적인 인터페이스를 제공하므로, DAG나 dominator, reachability 등의 복잡한 그래프 문제를 매우 쉽게 해법으로 연결할 수 있습니다.

본문 예시 코드를 토대로, 프로토타입을 만들고, 원하는 시각화나 파이프라인에 적용해 보세요.
복잡한 컴파일러 CFG(지배자 트리), 작업스케줄링(위상정렬), 경로 질의(트랜지티브 클로저) 등 다방면에 응용 가능하답니다.

이상으로, dominator_tree, topological_sort, transitive_closure 각 기능을 수식, 개념, 구현 예시와 함께 살펴봤습니다. 즐거운 그래프 분석 & 최적화 작업에 도움이 되길 바랍니다!

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 label_components() 함수를 이용하여 그래프 내의 연결 요소(undirected에서의 component, directed에서의 strongly connected component 등)를 효율적으로 찾고, 각 정점마다 어떤 컴포넌트에 속하는지 라벨링(label) 하는 과정을 자세히 설명합니다. 초보자를 위해 한글 주석과 실용적 예시 위주로 서술하였으니, 도시·교통(분산처리) 및 네트워크 분석에 참고하시길 바랍니다.

1. `label_components()` 함수의 역할과 개념

label_components(g, vprop=None, directed=None, attractors=False)
- 그래프 g에서 연결 요소(undirected) 또는 강한 연결 요소(SCC, strongly connected components, directed일 때)를 찾아, 각각의 정점에 컴포넌트 번호를 할당.
- 반환:
  1. comp: 정점별로 컴포넌트 라벨이 담긴 VertexPropertyMap
  2. hist: 각 컴포넌트 번호별 정점 개수(히스토그램)
  3. (옵션) is_attractor: directed이고 attractors=True일 때, 그 컴포넌트가 “attractor”(밖에서 들어오긴 해도 밖으로는 못 나가는 SCC)인지 여부(Boolean 배열)
directed = None일 때:
- 그래프의 실제 방향성에 따라 undirected면 연결요소, directed면 SCC 식으로 해석.
- True / False로 강제 지정하면, 무향 or 유향으로 처리 가능.
시간 복잡도:
- (\mathrm{O}(V+E)) = 선형 시간 (그래프의 정점 수, 간선 수에 비례).

2. 파이썬 예시 코드

아래 예시 코드는 무작위 그래프를 생성한 뒤, label_components()로 연결/강연결 요소 라벨을 구하는 과정을 보여줍니다.

import graph_tool.all as gt
import numpy as np

def example_label_components():
    # 1) 무작위 그래프 생성 (기본은 무방향)
    #    directed=True 옵션으로 유향 그래프 생성 가능
    #    여기서는 일단 무작위 그래프 (100노드) 만들기
    #    평균 차수 ~2 (푸아송 분포)로 edge를 생성
    g = gt.random_graph(100, lambda: (np.random.poisson(2), np.random.poisson(2)), directed=False)
    
    # 2) label_components 호출
    #    attractors=True로 하면, directed 그래프 시 attractor 정보도 반환
    #    여기서는 무향이라 attractors=True 의미가 크게 없지만 예시로 넣음
    comp, hist, is_attractor = gt.label_components(
        g,                # 그래프
        directed=None,    # None이면 g의 방향성에 맞춤. (g가 무향이라 연결요소)
        attractors=True
    )
    
    # 3) 결과 확인
    # comp.a : 정점 개수 길이의 ndarray, comp.a[v_idx] = 해당 정점이 속한 컴포넌트 번호
    print("Component array (label_components):")
    print(comp.a)
    
    # hist : 각 라벨(0..N-1)별로 몇 개 정점이 있는지
    print("Histogram of component labels:")
    print(hist)
    
    # is_attractor: 무향 그래프일 때는 보통 다 False (혹은 의미 X)
    # directed 그래프라면, SCC가 attractor인지 여부
    print("Is attractor array:")
    print(is_attractor)
    
    # 4) 컴포넌트별로 다른 색상 시각화 등 응용 가능
    #    예: comp_color = g.new_vertex_property("vector<double>")
    #        ... 라벨별로 색상 부여
    
    # 시각화 간단 예시 (무지개 컬러)
    import matplotlib.pyplot as plt
    from matplotlib import cm
    
    # (a) 시각화용 레이아웃
    pos = gt.sfdp_layout(g)
    
    # (b) 각 라벨을 [0,1] 범위로 정규화해서 colormap에 대응
    max_label = np.max(comp.a)
    vcolor = g.new_vertex_property("vector<double>")
    for v in g.vertices():
        label = comp[v]
        norm_value = label / max_label if max_label > 0 else 0
        # cmap -> (r,g,b)
        (r,g,b, _) = cm.rainbow(norm_value)
        vcolor[v] = (r,g,b,1.0)
    
    # (c) draw
    gt.graph_draw(
        g,
        pos=pos,
        vertex_fill_color=vcolor,
        output_size=(600,600),
        output="example_label_components.png"
    )
    print("Graph with color-coded components drawn to 'example_label_components.png'")

if __name__ == "__main__":
    example_label_components()

코드 해설

그래프 생성:
- random_graph(100, lambda: (np.random.poisson(2), np.random.poisson(2)), directed=False)
- 노드 100개, edge 개수는 (2,2) 푸아송 분포 시도. 무향.
label_components(...) 호출:
- 파라미터 directed=None → 무향 그래프 분석 시, 연결 요소 찾음.
- attractors=True: 유향 그래프 시 attractor 여부, 여기선 무향이라 큰 의미X.
- 반환: comp, hist, is_attractor.
결과:
- comp.a: 각 정점별 컴포넌트 라벨 (0부터 시작).
- hist: 라벨별 정점 수 (히스토그램).
- is_attractor: (무향은 대체로 False).
시각화:
- sfdp_layout로 좌표 배치
- 라벨별로 색상 할당하여 vertex_fill_color에 적용
- 출력.

3. 응용 예시

연결성 분석:
- 무향 그래프에서 comp.a[v]가 같은 정점끼리는 연결됨 (Connected Component).
- 예: 대규모 네트워크(도시, 도로망)에서 고립된 군집 파악
강연결성 분석:
- 유향 그래프에서 comp.a[v] = SCC 번호. → SCC 간 축약(condensation graph) 가능
is_attractor:
- 유향 그래프에서 outdegree(해당 SCC에서 밖으로 나갈 간선X)면 attractor.
- 예: 어떤 구간 안으로는 들어올 수 있지만, 나갈 수 없는 지점(교통망 dead-end?).
클러스터링 시각화:
- 무향 그래프의 Component별로 색을 칠하면 직관적.

4. 마무리

label_components()는 그래프의 연결성·군집 분석을 빠르고 쉽게 할 수 있는 강력한 함수입니다. 무향 그래프에서 연결요소, 유향 그래프에서 강연결요소(SCC) 라벨을 구해주고, 필요 시 attractor 여부까지 알려주므로, 다양한 네트워크 분석(도시·교통망 등)에서 활용할 수 있습니다.

시간 복잡도: (\mathrm{O}(V+E)) (선형)
결과물:
1. comp: 정점별 컴포넌트 라벨 PropertyMap
2. hist: 각 라벨별 정점 개수
3. (옵션)is_attractor: 유향 그래프 시 attractor 여부

그래프 분석 시, 이 정보를 이용해 정점 군집별로 색상 시각화, SCC Condensation(압축), 또는 특정 컴포넌트만 추출 등 후속 처리를 자유롭게 진행하면 됩니다. Have Fun!

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 label_biconnected_components() 함수를 이용해, 무방향 그래프에서 이중 연결 요소(biconnected components) 및 단절점(articulation point)을 효율적으로 찾아내고 라벨링하는 과정을 단계별로 설명합니다. 초보자를 위해 한글 주석과 실용적인 예시 위주로 구성하였으니, 도시·교통망(분산처리) 및 네트워크 분석 시 참고하시길 바랍니다.

1. 이중 연결 요소(biconnected components)와 단절점(articulation point) 개념

연결 그래프는 “서로 다른 두 정점 간 경로가 항상 존재”함을 의미합니다.
이중(bi) 연결: 그래프에서 어떤 단일 정점을 제거(해당 정점과 그에 연결된 간선 포함)해도 그래프가 분리되지 않으면, 그 그래프는 이중 연결(biconnected)되었다고 합니다.
이중 연결 요소(biconnected component): 이중 연결을 만족하는 최대 부분 그래프들을 말합니다.
- 무향 그래프에서, 하나의 간선(Edge)은 정확히 하나의 이중 연결 요소에만 속할 수 있지만, 어떤 정점(Vertex)은 여러 이중 연결 요소에 공유될 수 있습니다.
단절점(articulation point): 어떤 정점을 제거하면 그래프의 연결 요소(connected component) 수가 증가하는 정점. 즉, 제거 시 그래프가 분리되는 원인이 되는 '중요'한 정점.
- 이중 연결 요소들 사이를 ‘공유’하는 정점들이 곧 단절점이 됩니다.

2. `label_biconnected_components()` 함수 개요

원형:

bicomp, articulation, num_comps = label_biconnected_components(
    g,
    eprop=None,
    vprop=None
)

입력:
- g : 그래프(Graph 객체). 무방향 그래프에 대해 작동.
- eprop : (옵션) 간선 property map. 이 함수가 “이중 연결 요소 번호”를 기록할 때 사용할 에지용 PropertyMap. 없으면 새로 생성.
- vprop : (옵션) 정점 property map. “단절점 여부(불리언)”를 기록할 때 사용할 PropertyMap. 없으면 새로 생성.
출력:
1. bicomp : EdgePropertyMap - 각 간선이 속한 이중 연결 요소의 라벨 번호(0..N-1).
2. articulation : VertexPropertyMap (Boolean) - 단절점(articulation point)이면 1(True), 아니면 0(False).
3. num_comps : int - 이중 연결 요소(간선 기준) 총 개수.
동작/의미:
- 무방향 그래프에서 biconnected component를 찾아서, 간선마다 어떤 컴포넌트 라벨인지 배정.
- 단절점(articulation point)도 T/F로 반환.
- 시간 복잡도: (\mathrm{O}(V + E)) (그래프 정점 수 V, 간선 수 E에 선형)

3. 파이썬 코드 예시

다음 코드는 100개 노드를 갖는 무작위 그래프를 만들고, label_biconnected_components() 함수를 호출하여 각 간선의 이중 연결 요소 라벨과 단절점 여부를 계산합니다.

import graph_tool.all as gt
import numpy as np

def example_label_biconnected():
    # 1) 무작위 그래프 생성 (무방향)
    #    노드=100, 평균 차수 ~2 로 edge를 생성
    g = gt.random_graph(
        100,
        lambda: np.random.poisson(2),
        directed=False
    )
    
    # 2) 이중 연결 요소 라벨링 함수 호출
    #    반환: (bicomp, articulation, hist)
    #    - bicomp: 각 간선이 속한 이중 연결 요소 번호 (EdgePropertyMap)
    #    - articulation: 각 정점에 대한 단절점 여부 (VertexPropertyMap, bool)
    #    - hist: 이중 연결 컴포넌트 개수 크기를 갖는 배열 (각 라벨에 속하는 간선 수)
    bicomp, art, hist = gt.label_biconnected_components(g)
    
    # 3) 결과 확인
    print("Edge biconnected component labels (bicomp.a):", bicomp.a)
    print("Articulation points array (art.a):", art.a)
    print("hist array (각 이중 연결 컴포넌트 별 간선수):", hist)
    
    # 이중 연결 컴포넌트의 개수
    num_bc = len(hist)
    print(f"Number of biconnected components: {num_bc}")

    # 4) 시각화(이중 연결 요소에 따라 간선 색 구분 등)
    pos = gt.sfdp_layout(g)

    # 간선 색상 설정
    from matplotlib import cm
    ecolor = g.new_edge_property("vector<double>")
    
    # 라벨 정규화 대비
    max_label = float(num_bc - 1) if num_bc > 1 else 1.0
    
    for e in g.edges():
        label_val = bicomp[e]
        norm_val = label_val / max_label
        (r,g_,b,a_) = cm.tab20(norm_val)
        ecolor[e] = (r,g_,b,1.0)
    
    # 단절점 색상: articulation[v] = 1이면 빨간색, 아니면 회색
    vcolor = g.new_vertex_property("vector<double>")
    for v in g.vertices():
        if art[v] == 1:
            vcolor[v] = (1.0,0.0,0.0,1.0)  # red
        else:
            vcolor[v] = (0.5,0.5,0.5,1.0)  # gray

    gt.graph_draw(
        g,
        pos=pos,
        vertex_fill_color=vcolor,
        edge_color=ecolor,
        output_size=(600,600),
        output="example_label_biconnected.png"
    )
    print("Graph with biconnected components colored on edges, and articulation points in red saved to example_label_biconnected.png")

if __name__=="__main__":
    example_label_biconnected()

코드 해설

그래프 생성
- random_graph(100, lambda: np.random.poisson(2), directed=False): 노드 100개, 무작위로 간선 형성(평균 차수 ~2).
label_biconnected_components() 호출
- biconnected component(이중 연결 요소) 라벨이 edge basis로 할당됨.
- articulation points(단절점)는 vertex basis로 bool 값.
- num_comps: 총 이중 연결 요소(간선 기준) 개수.
결과 확인:
- bicomp.a: 각 간선별 라벨 배열 (길이=간선 수).
- art.a: 정점별 단절점 여부 (길이=정점 수, 1 or 0).
- num_comps: 이중 연결 요소 개수.
시각화:
- edge_color를 biconnected 라벨별로 구분.
- vertex_fill_color는 (단절점=빨강, 나머지=회색).
- 그림 출력.

4. 결과 해석 및 활용

간선의 biconnected component 라벨:
- 하나의 간선은 정확히 하나의 이중 연결 요소에만 속함. 같은 라벨을 공유하는 간선들은 함께 이중 연결됨.
단절점(articulation):
- 여러 개의 이중 연결 요소를 공유하거나, 그래프 내에서 특정 정점을 제거했을 때 그래프 분리가 발생.
- 예) 도시·도로망 분석 시, 그 정점을 끊으면 지역이 분리되는 “중요 교차점”.
활용 예시:
- 도시/교통: 네트워크망에서 “bridge(단절 간선)”와 유사하게, “articulation point(단절점)” 등은 재난 대비 취약 지점으로 중요.
- 분산처리: 네트워크 토폴로지에서 이중 연결이 잘 보장되는지(단일 노드 장애에 대한 탄력성).
- 시각화/클러스터링: biconnected comp를 서로 다른 색으로 표현 → 네트워크 구조 파악.

5. 마무리

요약:
- label_biconnected_components() : 무방향 그래프에서 이중 연결 요소 라벨링 + 단절점 판별.
- 시간 복잡도: (\mathrm{O}(V+E)).
- 반환: (1) 간선 라벨맵(bicomp), (2) 단절점맵(articulation), (3) 이중 연결 컴포넌트 총 개수.
추가로:
- 연결성이 복잡한 큰 그래프에서도 빠르게 작동 (선형 알고리즘).
- 도로망/사회네트워크 등 다양한 응용 시 이중 연결 구조 및 단절점 찾기에 유용.

도시·교통망 및 다양한 네트워크에서 “한 노드(교차점) 장애가 발생하면 망이 분리되는가?”를 확인하는 중요한 단계가 이 함수로 쉽게 처리 가능합니다. 이 튜토리얼이 초보자들의 학습 및 실무 활용에 도움이 되길 바랍니다.

아래 튜토리얼에서는 graph-tool 라이브러리의 label_largest_component() 함수를 활용하여 그래프에서 최대 연결 요소(무향 그래프의 경우) 혹은 최대 강결합 컴포넌트(유향 그래프의 경우)를 효율적으로 찾고, 그 결과를 시각화하는 과정을 살펴보겠습니다. 도시, 교통 빅데이터, 분산처리, 네트워크 분석 분야에서 네트워크의 가장 큰 연결 성분(또는 가장 큰 강결합 컴포넌트)을 추출하는 것은 분석 및 시각화에서 매우 유용하게 쓰입니다.

1. 함수 개요

label_largest_component(
    g, 
    directed=None
)

입력:
- g: 그래프 객체
- directed: (옵션) Bool 값. None이면 g의 방향성 따라 감안.
  - 무향 그래프이면 최대 연결 요소
  - 유향 그래프이면 최대 강결합 컴포넌트(SCC) 중 가장 큰 것
출력:
- comp: Boolean vertex property map(정점별 True/False)
  - True면 최대 컴포넌트에 속한 정점
  - False면 속하지 않음
시간 복잡도:
- 연결 요소(혹은 강결합 컴포넌트) 탐색이므로, 일반적으로 (O(V + E)).
주요 특징:
- 무향 그래프: 최대 연결 요소
- 유향 그래프: 최대 강결합 컴포넌트(SCC)
- 예: comp[v] == True 면 그 정점 (v)가 해당 최대 컴포넌트에 속한다는 의미.

2. 기본 사용 예시

아래 예시는 100개 노드를 갖는 무작위 그래프(평균 차수 ~1)를 생성한 뒤, label_largest_component()로 최대 연결 요소를 라벨링합니다.

import graph_tool.all as gt
import numpy as np

def example_label_largest_component():
    # 1) 무작위 그래프 생성
    #    노드=100, 무향, 평균 차수 ~1
    g = gt.random_graph(100, lambda: np.random.poisson(1), directed=False)
    
    # 2) 최대 연결 요소 라벨 (boolean VPropMap) 얻기
    comp = gt.label_largest_component(g, directed=None)
    # comp[v] == True : 최대 연결(강결합) 컴포넌트에 속함
    # comp[v] == False: 속하지 않음
    
    print("Largest component membership array:")
    print(comp.a)
    # ex) [0 1 0 0 1 1 0 0 ... ] 의 형태, 0->False / 1->True
    
    # 3) GraphView로 최대 연결 요소만 추출 가능
    u = gt.GraphView(g, vfilt=comp)
    print("Number of vertices in largest component:", u.num_vertices())
    
    # 4) 시각화
    # (a) 레이아웃
    pos = gt.sfdp_layout(g)
    
    # (b) 정점 색상 설정: True=노랑, False=회색
    vcolor = g.new_vertex_property("vector<double>")
    for v in g.vertices():
        if comp[v]:  # True
            vcolor[v] = (1.0, 1.0, 0.0, 1.0)  # yellow
        else:
            vcolor[v] = (0.7, 0.7, 0.7, 1.0)  # light gray
    
    # (c) 시각화
    gt.graph_draw(
        g,
        pos=pos,
        vertex_fill_color=vcolor,
        output_size=(600, 600),
        output="example_largest_component.png"
    )
    print("Graph with largest component in yellow saved to example_largest_component.png")

if __name__ == "__main__":
    example_label_largest_component()

코드 해설

그래프 생성
- gt.random_graph(100, lambda: np.random.poisson(1), directed=False)
  - 노드=100, 간선 수는 푸아송(1) 분포 이용 -> 대략 평균 차수 ~2(여기선 1이므로 ~1)
  - 무향(directed=False)
함수 호출
- comp = gt.label_largest_component(g, directed=None)
  - comp는 VertexPropertyMap (bool 타입)
  - comp[v]==True일 때, 정점 v가 최대 연결 요소 소속
결과 활용
- print(comp.a) -> numpy 배열 형태로 True/False(혹은 0/1)로 출력
- u = gt.GraphView(g, vfilt=comp) -> 최대 연결 요소만 필터링한 서브그래프
시각화
- pos = gt.sfdp_layout(g): Layout 계산
- vcolor[v] = ...: comp[v]가 True면 (1,1,0), False면 (0.7,0.7,0.7)
- graph_draw(..., vertex_fill_color=vcolor, ...)로 최종 그리기

3. 유향 그래프인 경우

directed=True로 호출하면 “최대 강결합 컴포넌트(SCC)”를 찾습니다.
예:

def example_largest_scc():
    g = gt.random_graph(100, lambda: np.random.poisson(2), directed=True)
    comp = gt.label_largest_component(g, directed=True)
    # comp[v]가 True인 부분집합이 g에서 가장 큰 SCC
    
    # 서브그래프
    scc_view = gt.GraphView(g, vfilt=comp)
    print("Vertices in largest strongly connected component:", scc_view.num_vertices())

이와 같이 하면 가장 큰 SCC만 필터링한 그래프 scc_view를 얻을 수 있습니다.

4. 추가 Tip

None vs False vs True
- directed=None이면 g.is_directed() 상태 따라 자동 결정
- directed=False -> 무조건 무향 그래프로 간주 -> 최대 연결 요소
- directed=True -> 유향 그래프로 간주 -> 최대 강결합 컴포넌트
뷰(View) 이용
- GraphView(g, vfilt=comp)로 해당 컴포넌트 그래프만 쉽게 추출, 이후 다양한 알고리즘(예: BFS, DFS, centrality 등) 적용 가능
Performance
- 복잡도 (O(V + E)). 1000, 1만 노드 이상의 그래프에서도 빠르게 구동 가능
Articulation point(절점), Bridge(단절선), Biconnected component(이중 연결 요소) 등과의 관계
- label_largest_component()로 전체 그래프에서 가장 큰 연결 성분 찾은 후, label_biconnected_components()로 biconnected component도 구할 수 있음.
- 유향 그래프의 경우 label_components()(SCC), label_out_component()(단일 루트 out-component) 등도 존재

5. 마무리

label_largest_component() 함수는 가장 큰 연결 요소 혹은 가장 큰 강결합 컴포넌트를 찾아서, 정점별 bool 라벨을 빠르게 반환해줍니다. 빅데이터 환경에서도 (O(V+E)) 알고리즘이므로 효율적이며, 필터링해서 시각화나 후처리(중심성 분석, 모형화 등)에 바로 활용하기 좋습니다.

위 튜토리얼 코드와 함께 실습해보면, 도시·교통 빅데이터나 분산처리/그래프분석 파이프라인에서 가장 큰 연결 성분을 추출해, 노이즈/고립된 노드 등을 제외한 핵심 네트워크 부분을 포착할 수 있습니다.

아래 튜토리얼에서는 graph-tool 라이브러리의 extract_largest_component() 함수를 이용해, 그래프에서 최대 연결 요소(무향 그래프인 경우) 혹은 최대 강결합 컴포넌트(유향 그래프인 경우)를 별도의 GraphView(또는 Graph 객체)로 추출하는 방법을 살펴봅니다. 도시·교통 빅데이터, 분산처리 및 네트워크 분석 시, 필요에 따라 고립된 부분을 제외하고 핵심 구성요소만 따로 떼어 분석하고자 할 때 유용한 함수입니다.

1. `extract_largest_component()` 함수 개요

extract_largest_component(
    g, 
    directed=None, 
    prune=False
) -> GraphView or Graph

입력:
- g: Graph 객체
- directed: (옵션) Bool 값.
  - None이면 g.is_directed() 상태에 맞춰 동작
  - False -> 무향 그래프로 취급, 최대 연결 요소를 추출
  - True -> 유향 그래프로 취급, 최대 강결합(Strongly Connected) 컴포넌트 추출
- prune: (옵션) Bool 값.
  - False면, 원본 그래프(노드·엣지)에 필터만 걸어둔 GraphView 객체 반환
  - True면, 해당 컴포넌트만을 별도의 Graph 객체로 복사(pruned graph)해서 반환
출력:
- comp: GraphView(기본) 또는 Graph(prune=True일 때)
  - 최대 연결(또는 강결합) 컴포넌트만 남은 서브그래프
시간 복잡도:
- 일반적으로 연결성/강결합 컴포넌트 판별은 (O(V+E)) 정도

2. 기본 예시: 무향 그래프

다음 코드는 노드 100개, 평균 차수 ~1인 무작위 무향 그래프를 생성한 후, extract_largest_component()를 통해 가장 큰 연결 성분을 GraphView로 얻는 예시입니다.

import graph_tool.all as gt
import numpy as np

def example_extract_largest_component():
    # 1) 무작위 그래프 생성
    #    노드=100, 무향, 평균 차수 ~1
    g = gt.random_graph(100, lambda: np.random.poisson(1), directed=False)

    # 2) 최대 연결 요소만 추출 (GraphView)
    u = gt.extract_largest_component(g, directed=None, prune=False)
    # directed=None -> g의 방향성(무향)에 맞춰 "최대 연결 성분" 판단
    # prune=False   -> GraphView 반환

    print("Extracted largest component as GraphView:")
    print(u)  # 정보 출력

    # GraphView인 u는 g의 일부분(가장 큰 component)에 대해서만 노드/엣지가 유효

    # 3) u로 작업 가능
    print(f"#vertices in largest component: {u.num_vertices()}")
    print(f"#edges in largest component: {u.num_edges()}")
    
    # 4) 시각화
    # (a) 레이아웃
    pos = gt.sfdp_layout(g)  # 원본 그래프에 대해 레이아웃
    
    # (b) 뷰(u)에 속한 정점만 색 강조
    in_comp_vp = g.new_vertex_property("bool")
    for v in g.vertices():
        in_comp_vp[v] = u.vertex_index[v] != -1  # u 안에 존재하면 True

    # 정점 색: True=노랑, False=회색
    vcolor = g.new_vertex_property("vector<double>")
    for v in g.vertices():
        if in_comp_vp[v]:
            vcolor[v] = (1.0,1.0,0.0,1.0)  # yellow
        else:
            vcolor[v] = (0.7,0.7,0.7,1.0)  # light gray

    # (c) draw
    gt.graph_draw(
        g,
        pos=pos,
        vertex_fill_color=vcolor,
        output_size=(600,600),
        output="largest_component_graphview.png"
    )
    print("Graph with largest component in yellow saved to largest_component_graphview.png")

if __name__=="__main__":
    example_extract_largest_component()

코드 해설

그래프 생성
- gt.random_graph(100, lambda: np.random.poisson(1), directed=False)
  - 100개 노드, 평균 차수 ~1 (푸아송(1))
최대 연결 요소 추출
- u = gt.extract_largest_component(g, directed=None, prune=False)
  - u는 GraphView 형태
  - u.num_vertices(), u.num_edges() 등 가능
시각화
- 원본 그래프 g 기준으로 레이아웃(pos) 계산
- u.vertex_index[v] == -1이면 v는 u에 없음 → 회색. 그렇지 않으면 노랑색
- graph_draw()로 시각화

3. 유향 그래프의 최대 강결합 컴포넌트

directed=True 옵션을 명시하면, 그래프를 유향으로 간주하고 가장 큰 강결합 컴포넌트(SCC)를 추출합니다.

def example_extract_largest_scc():
    g = gt.random_graph(100, lambda: np.random.poisson(2), directed=True)
    scc_view = gt.extract_largest_component(g, directed=True, prune=False)
    
    print("Extracted largest strongly connected component (GraphView):")
    print(scc_view)

이렇게 하면, scc_view가 GraphView 형태로, 가장 큰 SCC만 필터링된 그래프를 얻을 수 있습니다.

4. `prune=True` 사용

prune=True로 하면, 반환값이 GraphView가 아니라 Graph 객체로, 해당 컴포넌트를 ‘복사’한 결과물을 얻습니다.

def example_prune_largest_component():
    g = gt.random_graph(50, lambda: np.random.poisson(3), directed=False)

    # prune=True -> Graph 객체 반환 (필터링한 부분만 복제)
    largest_comp_graph = gt.extract_largest_component(g, directed=None, prune=True)
    print("Pruned Graph object of largest component:")
    print(largest_comp_graph)  # <Graph object>, 별개 객체
    
    # 개수
    print(f"#vertices: {largest_comp_graph.num_vertices()}")
    print(f"#edges   : {largest_comp_graph.num_edges()}")

주의: GraphView는 원본 그래프를 참조하기 때문에, 원본 그래프가 변하면 뷰도 영향을 받지만, prune=True 시 반환된 Graph는 독립적인 복제본.

5. 성능 및 응용

해당 함수 내부적으로 label_components()(또는 label_components(..., directed=True))와 동일한 원리로 최대 연결 성분만 필터링
시간 복잡도: (O(V+E))
응용:
- 분산처리 네트워크에서 핵심 연결 성분만 추출
- 강결합 컴포넌트 중 가장 큰 부분만 따로 떼어, 향후 BFS/DFS나 centrality 분석, 시각화 진행

6. 최종 예시 코드

다음은 최종적으로 무향 그래프에서 가장 큰 연결 성분을 Graph 객체로 복제(prune=True)하여 시각화하는 예시입니다.

import graph_tool.all as gt
import numpy as np

def tutorial_extract_largest_comp():
    # (1) 그래프 생성
    g = gt.random_graph(80, lambda: np.random.poisson(2), directed=False)
    
    # (2) 최대 연결 성분만 복제
    largest_subgraph = gt.extract_largest_component(g, directed=False, prune=True)
    print("Extracted largest component as separate Graph (prune=True):")
    print(largest_subgraph)
    
    # (3) 시각화
    #    - 원본과 분리되었으므로, layout 별도 계산
    pos_orig = gt.sfdp_layout(g)
    pos_sub  = gt.sfdp_layout(largest_subgraph)
    
    gt.graph_draw(
        g,
        pos=pos_orig,
        output_size=(600,600),
        output="original_random_graph.png"
    )
    gt.graph_draw(
        largest_subgraph,
        pos=pos_sub,
        output_size=(600,600),
        output="largest_comp_pruned_graph.png"
    )
    
    print(f"largest_subgraph: #vertices={largest_subgraph.num_vertices()}, #edges={largest_subgraph.num_edges()}")
    print("Saved 2 PNGs: original_random_graph.png, largest_comp_pruned_graph.png")

if __name__=="__main__":
    tutorial_extract_largest_comp()

코드 요약

노드 80개 무작위 무향 그래프(random_graph) 생성
extract_largest_component(..., prune=True) → 최댓 연결 성분을 Graph로 리턴
레이아웃 각각 계산해 시각화

결론

extract_largest_component()는 그래프에서 가장 큰 연결(또는 가장 큰 강결합) 컴포넌트를 쉽고 빠르게 추출할 수 있는 편리한 함수입니다.

GraphView(동적 필터) 또는 Graph(복제본)로 돌려받을 수 있어, 이후 다양한 분석에 곧바로 활용하기 좋습니다.
빅데이터 네트워크, 교통망 등에서 흔히 나타나는 다수의 작은 컴포넌트(또는 SCC)를 제외하고, 본질적으로 가장 연결이 많은 부분만 집중적으로 살펴보는 경우에 매우 유용합니다.

아래 내용은 그래프 툴(graph-tool) 라이브러리에서 제공하는 label_out_component 함수와 관련하여, 원리와 구현 아이디어, 그리고 활용 방법을 단계별로 풀어서 설명합니다. 예시는 무향 그래프이지만, 유향 그래프에도 동일/유사하게 적용 가능하므로 참고해 주세요.

1. `label_out_component()` 함수 개요

함수 프로토타입:

label_out_component(
    g: Graph,
    root: Vertex,
    label: VertexPropertyMap[bool] = None
) -> VertexPropertyMap[bool]

기능: 특정 root 정점에서 출발하여, 그 정점으로부터 (유향 그래프라면 out-going 방향으로) 도달 가능한 정점(즉, same out-component)에 대해 True 라벨을 매기고, 나머지는 False로 설정하는 Boolean 타입의 정점 property map을 반환.
- 무향 그래프의 경우: root 정점이 속한 연결요소의 정점들을 True.
- 유향 그래프의 경우: root 정점에서 나가는 방향으로 reachable한 정점들을 True.
매개변수:
- g: 그래프 객체(Graph). 무향/유향 상관없음. 단, g.is_directed()에 따라 유향/무향 모드가 달라짐.
- root: 라벨링을 시작할 루트 정점(g.vertex(i) 형태).
- label: (옵션) 미리 만들어둔 Boolean형 VertexPropertyMap. 없으면 내부적으로 새로 생성해서 반환.
반환값: VertexPropertyMap (bool)
- .a (NumPy array)에 True/False가 들어있음
- True: root에서 도달 가능(무향 그래프면 동일 연결요소).
시간 복잡도: (\mathrm{O}(V + E))

즉, 그래프에서 BFS/DFS와 유사한 방식으로 root에서 닿을 수 있는 정점만 찾는 함수라고 볼 수 있습니다.

2. 예시 코드 및 튜토리얼

아래는 간단한 예시 코드입니다.

100개의 정점을 가진 무작위 그래프 g를 생성.
정점 root = g.vertex(2)을 루트로 해서, 도달 가능한 정점만 골라 라벨링.
결과(out_label.a)를 이용해 True/False 시각화.

import graph_tool.all as gt
import numpy as np

def example_label_out_component():
    # 1) 그래프 생성: 100개 노드, 평균 차수 ~2.2인 무작위 그래프(무향)
    g = gt.random_graph(100, lambda: np.random.poisson(2.2), directed=False)
    
    # 2) root 정점 선택
    root_vertex = g.vertex(2)
    
    # 3) label_out_component 호출
    #    -> root_vertex로부터 도달 가능한 정점들을 True로 라벨링
    out_label = gt.label_out_component(g, root_vertex)
    
    # 4) 결과 출력
    print("Out-component array from root=2 (bool):")
    print(out_label.a)  # 길이가 정점수(100)인 True/False array
    
    # 5) g에서 out_label == True 인 정점들만 추출해서 GraphView 만들기
    sub_g = gt.GraphView(g, vfilt=out_label)
    print("Size of sub_g (which is the component of root):")
    print(f"Vertices = {sub_g.num_vertices()}, Edges = {sub_g.num_edges()}")
    
    # 6) 시각화
    import matplotlib.pyplot as plt
    from matplotlib import cm
    
    # (a) 위치 계산
    pos = gt.sfdp_layout(g)
    
    # (b) True/False -> 빨강 / 회색
    vcolor = g.new_vertex_property("vector<double>")
    for v in g.vertices():
        if out_label[v]:
            vcolor[v] = (1, 0, 0, 1)   # red
        else:
            vcolor[v] = (0.7, 0.7, 0.7, 1)  # gray
            
    # (c) draw
    gt.graph_draw(
        g,
        pos=pos,
        vertex_fill_color=vcolor,
        output_size=(600,600),
        output="out_component_example.png"
    )
    print("Saved to out_component_example.png (red=out-component).")

if __name__=="__main__":
    example_label_out_component()

핵심 포인트

label_out_component():
- 무향 그래프: root가 속한 연결 요소
- 유향 그래프: root에서 나가는 방향으로 닿을 수 있는 정점 집합
결과: Boolean property map
- True/False로 필터링(GraphView)에 활용 가능
시간복잡도: BFS/DFS 유사 (\mathrm{O}(V+E)).

3. 유향 그래프에서 in-component 얻기

만약 “어떤 정점 root에 도착 가능한 정점들”을 구하고 싶다면? 즉, in-component 개념이 필요하다면, 그래프를 reverse 한 뒤(GraphView(g, reversed=True, directed=True)) label_out_component()를 쓰면 됩니다:

def example_in_component_directed():
    # 유향 그래프 만들기
    g = gt.random_graph(50, lambda: np.random.poisson(2), directed=True)
    # in-component: reverse해서 out-component를 구함
    root = g.vertex(0)
    rev_view = gt.GraphView(g, reversed=True, directed=True)
    
    in_label = gt.label_out_component(rev_view, rev_view.vertex(0))
    
    print("In-component label array (from root=0 in reversed graph):")
    print(in_label.a)

위처럼 하면, in_label[v]가 True인 정점은 원래 그래프 g에서 v -> root 경로가 있음을 의미(역방향에서 root->v).

4. 커스텀 label property map 활용

label_out_component() 세 번째 인수로 미리 준비한 Boolean VertexPropertyMap을 넘길 수도 있습니다. 예:

def example_custom_label():
    g = gt.random_graph(40, lambda: np.random.poisson(2), directed=False)
    root = g.vertex(10)
    # 미리 bool prop map 만들기
    bool_prop = g.new_vertex_property("bool")
    
    ret_prop = gt.label_out_component(g, root, label=bool_prop)
    # ret_prop와 bool_prop는 동일 객체
    print("Is ret_prop is bool_prop? ->", ret_prop is bool_prop)

5. 결론 및 요약

label_out_component(g, root):
- 무향 그래프: root 정점이 속한 연결요소를 bool 라벨로 반환
- 유향 그래프: root에서 나가는 방향으로 reachable한 정점들을 bool 라벨로 반환
시간복잡도: BFS/DFS 기반으로 (\mathrm{O}(V + E)).
활용:
- 특정 정점이 속한 부분그래프 추출
- Directed graph: 한 정점에서 파생되는 영향권이나 reachability 분석
- In-component도 reverse 그래프로 처리 가능
- 필터링된 그래프(GraphView)나 시각화 등에 응용

이상으로 label_out_component 함수의 원리와 사용 예시를 살펴보았습니다. 실무나 연구에서 유향/무향 그래프에서 특정 노드의 도달 가능 영역을 찾고 시각화/분석하는 데 유용하게 쓰일 것입니다.

Sylen

AI가 재밌는 걸

이전 포스트

graph_tool.topology 3

다음 포스트

graph_tool.topology 4

1. 문제 배경 및 요약

2. Kruskal 논문이 해결하려는 두 가지 문제

3. Kruskal 알고리즘 (Construction A)

3.1 MST의 유일성 증명 (간선 가중치가 모두 다를 때)

4. Kruskal 논문의 그래프 이론 정리 (예비정리)

5. TSP와 MST

6. 결론 및 의의

참고 문헌

1. 최소 스패닝 트리(MST)란?

1.1 MST를 구하는 대표 알고리즘

2. min_spanning_tree() 함수 개요

3. 예시 코드 튜토리얼

3.1 샘플 그래프 생성

코드 해설

3.2 Prim 알고리즘으로 MST 구하기

4. 내부 알고리즘 개념

5. 반환 결과 활용

6. 주의사항 및 팁

결론

1. Wilson 알고리즘 (무작위 스패닝 트리) 개요

1.1 문제 배경

1.2 Wilson 알고리즘의 핵심 아이디어

Loop-Erased Random Walk

2. 알고리즘 원리 (수식, 확률적 증명)

2.1 왜 균일 분포(Uniform Distribution)인가?

2.2 평균 실행 시간: Mean Hitting Time

3. 파이썬 graph-tool 예시: Wilson 알고리즘 구현

3.1 Wilson 알고리즘: 코드 개요

Loop-erased 경로 구현

3.2 전체 코드 예시

코드 해설

4. 고찰 및 성능

5. 결론

1. random_spanning_tree() 함수 개요

1.1 알고리즘(원리) 요약

1.2 분포(확률) 정리

2. Wilson 알고리즘 원리 자세히 살펴보기

2.1 루프 소거(Loop-Erasing)와 사이클 팝핑(Cycle Popping)

2.2 시간 복잡도 해설

3. random_spanning_tree() 함수 사용 튜토리얼

3.1 기본 예시

코드 예시

코드 설명

실행 결과

4. 고급 활용

5. 복잡도와 성능

6. 마무리

1. dominator_tree(): 지배자 트리(Dominator Tree)

1.1 이론 개념과 원리

1.2 시간 복잡도

1.3 파이썬 예시 코드

코드 설명

2. topological_sort(): 위상 정렬

2.1 이론 개념과 원리

2.2 파이썬 예시 코드

코드 설명

3. transitive_closure(): 트랜지티브 클로저

3.1 이론 개념과 원리

3.2 파이썬 예시 코드

코드 설명

4. 정리 및 마무리

1. label_components() 함수의 역할과 개념

2. 파이썬 예시 코드

코드 해설

3. 응용 예시

4. 마무리

1. 이중 연결 요소(biconnected components)와 단절점(articulation point) 개념

2. label_biconnected_components() 함수 개요

3. 파이썬 코드 예시

코드 해설

4. 결과 해석 및 활용

5. 마무리

1. 함수 개요

2. 기본 사용 예시

코드 해설

3. 유향 그래프인 경우

4. 추가 Tip

5. 마무리

1. extract_largest_component() 함수 개요

2. `min_spanning_tree()` 함수 개요

1. `random_spanning_tree()` 함수 개요

3. `random_spanning_tree()` 함수 사용 튜토리얼

1. `dominator_tree()`: 지배자 트리(Dominator Tree)

2. `topological_sort()`: 위상 정렬

3. `transitive_closure()`: 트랜지티브 클로저

1. `label_components()` 함수의 역할과 개념

2. `label_biconnected_components()` 함수 개요

1. `extract_largest_component()` 함수 개요

4. `prune=True` 사용

1. `label_out_component()` 함수 개요