graph_tool.topology 6

Sylen·2025년 1월 5일

아래 튜토리얼은 Python graph-tool 라이브러리의 is_bipartite()와 is_DAG() 함수에 대해, 기초적인 그래프 이론과 함께 어떻게 사용하면 좋을지, 그리고 파이썬 예제 코드와 상세한 한글 주석을 포함한 설명을 다룹니다.

1. `is_bipartite()` 함수: 그래프가 이분그래프인지 판별

1.1 이분그래프(bipartite graph)란?

이분그래프란, 정점 집합을 두 개의 “파트(part)”로 나누었을 때, 모든 간선이 서로 다른 파트에 속한 정점들 간에만 존재하도록 할 수 있는 그래프를 말합니다.
- 쉽게 말해, 정점을 두 그룹 A, B로 나누어, 모든 간선은 A에서 B로만 연결되고 A에서 A, B에서 B인 간선은 없는 구조입니다.
예를 들어, 짝수, 홀수 정점을 각각 A, B로 두었을 때, 간선이 A끼리 연결되지 않고, B끼리 연결되지 않으면 이분그래프입니다.

왜 중요한가?

이분그래프는 “2색(color)으로 정점을 칠해도 인접한 정점이 같은 색이 되지 않는” 그래프이기도 합니다.
네트워크 분석에서 이분그래프 구조는 협업 네트워크, SNS 친구관계 등을 해석하는 경우 종종 등장합니다.

1.2 `is_bipartite(g, partition=False, find_odd_cycle=False)`

이 함수는 주어진 무방향 그래프 g가 이분그래프인지 여부를 판별합니다. 인자별 역할은 다음과 같습니다:

g: 검사할 그래프 객체 (undirected로 취급).
partition=False:
- 만약 True로 설정 시, 이분그래프일 경우 “두 파트로의 분할 결과”를 반환합니다.
find_odd_cycle=False:
- 만약 True로 설정 시, 만약 이분그래프가 아니라면 “홀수 길이 사이클”의 예시를 찾은 뒤 반환합니다.

리턴값

is_bipartite (bool): 이분그래프인지 여부
partition (옵션): 이분그래프일 경우, 각 정점이 어느 파트에 속하는지 나타내는 VertexPropertyMap
odd_cycle (옵션): 이분그래프가 아닐 경우, 홀수 길이 사이클에 속한 정점 리스트(예: [v1, v2, v3, ...]) 또는 None

복잡도

공식 문서에 따르면 알고리즘은 (\mathrm{O}(V + E)) 시간에 수행됩니다.

1.3 사용 예시 (코드)

다음 예제는 graph-tool이 제공하는 is_bipartite 함수를 이용해 이분그래프 여부를 판별하고, 실제로 이분그래프면 파티션을 시각화하는 과정을 보여줍니다.

import graph_tool.all as gt

def example_is_bipartite():
    """
    graph-tool의 is_bipartite() 함수를 이용해 그래프가 이분그래프인지 판단하고,
    이분 분할 결과(두 파트)를 얻어 시각화하는 예제 코드.
    """
    # 1) 2D 격자형 (10x10) 무방향 그래프 생성
    g = gt.lattice([10, 10])  # 10x10 lattice

    # 2) 이분그래프 판별, 파티션 정보도 같이 반환 (partition=True)
    is_bi, part = gt.is_bipartite(g, partition=True)

    print(f"Is bipartite? {is_bi}")

    if is_bi:
        # part는 VertexPropertyMap, 0 또는 1 등의 값이 들어있음
        print("Bipartite partition:", part.a)  # 각 정점에 대한 파트 번호
        
        # 시각화: 각 파트마다 다른 색을 부여
        # part 값이 0 or 1 등으로 표시된다고 가정
        pos = gt.sfdp_layout(g)
        gt.graph_draw(
            g, 
            pos=pos,
            vertex_fill_color=part,  # 파트에 따라 색이 다름
            output="example_bipartite_partition.png"
        )
        print("Bipartite partition draw saved to 'example_bipartite_partition.png'")
    else:
        print("Given graph is NOT bipartite, so no partition to show.")

if __name__ == "__main__":
    example_is_bipartite()

코드 설명

2D 격자 (lattice)는 사실 이분그래프 구조임. (체스판처럼 2색으로 칠 가능)
is_bipartite 호출 시, partition=True로 설정하면, 두 파트에 대한 정점 PropertyMap이 반환.
이분그래프이면, 파티션(0 or 1)의 값을 확인 가능. 이를 시각화하면, 서로 다른 두 색상으로 격자를 나타낼 수 있음.

1.4 홀수 사이클 찾기

find_odd_cycle=True로 호출하면, 만약 그래프가 이분그래프가 아니면, “홀수 길이 사이클”의 정점 목록을 반환합니다.
예) is_bipartite(g, find_odd_cycle=True) → (False, None, [2, 5, 4])
- 이 그래프는 이분그래프가 아니므로 False, 파티션은 None, 홀수 사이클 예시는 [2,5,4].

2. `is_DAG()` 함수: 유향 그래프가 DAG(방향성 비순환 그래프)인지 판별

2.1 DAG(directed acyclic graph)란?

유향 비순환 그래프: 간선에 방향이 있는 그래프에서, 순환(cycle)이 전혀 없는 구조를 말함.
예: 위상 정렬(topological ordering)이 가능한 그래프 = DAG.
만약 어떤 유향 그래프에 사이클이 존재하면, DAG가 아님.

2.2 `is_DAG(g)`

이 함수는 그래프 g가 방향성 비순환 그래프(DAG)인지 여부를 간단히 True/False로 반환합니다.

g: 검사할 유향 그래프 객체.

리턴값

bool: DAG인지 (True/False)

복잡도

문서에 따르면 (\mathrm{O}(V + E)) 시간에 판별 가능.

2.3 사용 예시 (코드)

아래 코드는 무작위로 생성된 유향 그래프가 DAG인지 판별한 뒤, min_spanning_tree를 적용해서 만들어진 서브그래프가 DAG인지 재확인하는 예시를 보여줍니다.

import graph_tool.all as gt

def example_is_DAG():
    """
    graph-tool의 is_DAG() 함수를 이용해 유향 그래프가 DAG인지 판별하는 예제 코드.
    """
    # 1) 30개 정점을 가지는 무작위 그래프 생성(유향 가능)
    g = gt.random_graph(30, lambda: (3, 3))  # (out_deg, in_deg) = (3,3)

    # 2) is_DAG()로 DAG 여부 확인
    result = gt.is_DAG(g)
    print(f"Original graph is DAG? {result}")

    # 3) 예: Minimum Spanning Tree (MST) 추출 -> edge filter
    # MST는 당연히 cycle이 없어야 하므로 DAG여야 가능(단, 이건 유향 간선 취급이 어떻게 되는지 주의)
    # 그래프가 유향인 경우도 min_spanning_tree()가 (가중치가 없으면) 임의의 트리를 뽑아낼 수 있음
    tree = gt.min_spanning_tree(g)  # MST
    # MST에 해당하는 간선만 필터링
    g.set_edge_filter(tree)

    result_after = gt.is_DAG(g)
    print(f"After MST edge filter, graph is DAG? {result_after}")

    # 시각화
    pos = gt.sfdp_layout(g)
    gt.graph_draw(
        g,
        pos=pos,
        output="example_is_dag_mst.png"
    )
    print("Resulting MST DAG drawn at 'example_is_dag_mst.png'")

if __name__ == "__main__":
    example_is_DAG()

설명

random_graph(30, lambda: (3,3))는 (대체로) 유향 간선으로 구성된 그래프를 생성. (유향/무향은 파라미터로 결정 가능)
is_DAG(g) 호출로 사이클 존재 여부를 판별.
min_spanning_tree(g)를 통해 (유향 그래프여도) 일종의 spanning tree edges를 구하고, set_edge_filter()로 간선 필터링을 적용.
다시 is_DAG(g) → True가 나올 가능성이 높음(트리 구조이므로).

3. 요약

is_bipartite(g, partition=False, find_odd_cycle=False)
- 무방향 그래프가 이분그래프인지 판정.
- 필요하다면, 두 파트(partition) 정보나, 이분이 안 되는 이유(홀수 사이클)를 반환.
- 시간 복잡도: (\mathrm{O}(V + E)).
is_DAG(g)
- 유향 그래프가 방향성 사이클이 없는 DAG인지 판정.
- 시간 복잡도: (\mathrm{O}(V + E)).

둘 모두 그래프의 구조적 특성을 빠르게 판별하는 함수로, 네트워크 분석에서 매우 유용합니다. 예시로 이분그래프 구조를 시각화하거나, DAG인지 확인하여 위상정렬(topological sort) 가능 여부 등을 확인할 수 있습니다.

이상입니다.

아래 튜토리얼은 그래프 이론에서 중요한 평면 그래프(planar graph) 판별 알고리즘에 대한 논문을 소개하면서, 파이썬 graph-tool 라이브러리를 통한 네트워크 분석 및 시각화의 맥락에서, 핵심 내용을 최대한 쉽게 풀어서 설명합니다. “처음 공부하는 학생”도 이해할 수 있도록, 그래프 이론의 개념과 ‘O(n) 시간 복잡도’ 평면성 검사 기법을 친절하고 상세하게 다루겠습니다.

1. 문제배경: 평면 그래프와 Planarity Testing

평면 그래프(planar graph): 그래프를 평면 상에서 그렸을 때, 간선들이 교차 없이 그릴 수 있는 그래프.
Planarity Testing(평면성 판별): 입력으로 주어진 무방향 그래프가 평면 그래프인지 아닌지 판별, 그리고 평면이면 그리는 방법(임베딩)을 구성하는 문제.
Kuratowski 정리: 그래프가 평면성이 아니려면, (K5)나 (K{3,3})의 부분그래프(homeomorph)를 포함해야 한다는 고전적인 정리.

$K5와 K_{3,3} 그림$
- (K_5): 정점 5개를 모두 연결한 완전그래프
- (K_{3,3}): 정점이 (3,3)개로 bipartite로 나누었을 때 양쪽에 모든 간선이 존재하는 완전이분그래프.
선행 연구: Hopcroft-Tarjan, Lempel-Even-Cederbaum(LEC) + PQ-tree(Booth & Lueker), Shih-Hsu의 PC-tree, de Fraysseix-Rosenstiehl의 캐릭터라이제이션 등 다양하고 복잡한 O(n) 알고리즘 존재.

(\star) 본 논문(“On the Cutting Edge: Simplified O(n) Planarity by Edge Addition”) 은,

기존의 복잡한 “vertex addition” 접근(예: PQ-tree, PC-tree)보다 더 단순한 “edge addition” 접근으로 평면성 판별과 임베딩을 O(n) 시간에 구현하는 방법을 제안.
Edge addition: 그래프의 간선을 하나씩 “임베딩”하면서 평면성을 유지하도록 (or 아니면 non-planar detect) biconnected component를 병합(merge)하는 로직.

2. 알고리즘 개요: Edge Addition

2.1 Biconnected Component (이중 연결 요소)와 Merge

Biconnected component: 그래프에서 어떤 두 개의 정점을 삭제해도 해당 컴포넌트가 끊어지지 않는 부분 (간단히 말해, cut-vertex를 통해 다른 부분과 분리될 수 없는 맥락).
Edge addition으로 그래프를 만들며, 어떤 간선을 추가하면, 기존에 cut-vertex로 분리되어 있던 biconnected components가 하나로 합쳐질 수 있음.

예시:
- 만약 정점 (r)가 cut-vertex라면, (r)를 제거하면 컴포넌트가 (2)개로 나뉘었을 수 있다.
- 간선 ( (v, w)) 를 새로 추가하면, (r)가 cut-vertex가 아니게 되며, 원래 분리되어 있던 biconnected components들이 하나로 merge됨.

2.2 외부얼굴(External Face) 유지와 Flip

각 단계에서, 앞으로도 다른 간선을 추가해야 할 “외부에서 활동이 필요한” (externally active) 정점들은 항상 외부얼굴(external face)에 남아야 한다.
두 biconnected component가 merge될 때, 한쪽을 뒤집어(Flip)서 externally active 정점들이 외부에 남도록 함.

예시:
- 한 컴포넌트가 뒤집히면 정점들의 adjacency list 순서가 반대(시계 vs 반시계)가 됨.
- 이걸 매번 해주면 복잡하지만, 논문에서는 뿌리(root) 정점만 뒤집는 기법을 써서, flipping을 상수 시간에 처리. (자세한 구현은 orientation + sign 속성을 이용)

2.3 Walkup & Walkdown

Walkup: 새로 추가될 “back edge”가 연결되는 자손 정점(w)을 찾고, 그 경로 상의 biconnected component root들을 pertinent(“주의해서 merge해야 할”)상태로 표시.
Walkdown: 실제로 back edge를 임베딩(adding)하면서, 필요한 biconnected component를 merge하고, flip 등을 수행하여 외부얼굴에 externally active 정점을 유지함.

즉, “각 단계에서 어떤 biconnected component들을 어떻게 merge & flip해야 하는지”를 효율적으로 찾아주고, 실제로 간선 추가(embedding)를 하는 알고리즘의 메인 루틴.

2.4 Non-planar 시 Kuratowski Subgraph 찾기

모든 간선을 추가하지 못하고 중간에 “아예 임베딩이 불가능한” 상황이면, 그 시점에 Kuratowski subgraph ((K5)나 (K{3,3}) homeomorph) 을 추출한다.
논문에서 제시된 5가지 minor (A~E, 그림 11 참조)에 따라 subgraph를 추출하는 절차가 존재.

3. 데이터 구조와 운영

3.1 G̃ (임베딩 유지 구조)

G̃: 구현 레벨에서 관리하는 그래프-유사 구조.
각 정점/간선에 “orientation” 정보, “external face 연결 link”, “sign” (flip 여부), “root” (biconnected component에서 루트 copy) 등 추가 속성 보유.
병합(merge) 시: biconnected component끼리 모여서 한 컴포넌트가 되고, 필요 시 flip해서 externally active 정점을 외부에 남김.

3.2 Edge Addition Process

DFS tree edge부터 추가 (이건 그냥 연결하면 됨, cut-vertex를 구분해서 biconnected component가 생길 수 있음).
back edge(자손 -> 조상) 추가 시:
- Walkup으로 어떤 biconnected comp. root들이 pertinent한지 표시
- Walkdown으로 실제 간선추가 & 병합
- 만약 중간에 externally active 정점을 외부에 못 남기고(=임베딩이 불가능), non-planar로 결정 → Kuratowski subgraph 추출.

3.3 Complexity (O(n))

전체 과정을 살펴보면, 각 정점에서의 Walkup/Walkdown이 모든 간선에 대해 (\mathrm{O}(1)) ~ (\mathrm{O}(\text{face size})) 정도의 비용으로 처리되어, 결과적으로 (\mathrm{O}(n)) 시간에 수행 가능함을 증명.
자세한 분석은 논문 본문에 있으나, 핵심은 각 간선/정점이 “merge/flip”에 여러 번 관련되더라도, 총합이 상수배로 제한되어 있음.

4. Kuratowski Subgraph (Non-planar 시)

그래프가 non-planar라면, 알고리즘이 어느 시점에선가 “간선을 더 임베딩할 수 없음” 을 발견.
이때 Minor A~E (figure 11) 형태 중 하나가 나타나고, 이것들이 실제로 (K_{3,3}) 혹은 (K_5)의 minor를 이룬다는 것을 증명 (Theorem 3).
실제 구현 단계에서는 “어떤 minor인지, 어떤 경로를 사용해 homeomorph subgraph를 구성할지”를 빠르게 찾는 알고리즘 제시.

5. 실제 파이썬에서의 graph-tool 사용 맥락

5.1 graph-tool은?

C++로 구현된 빠르고 강력한 그래프 분석 라이브러리.
일반적으로 planar test를 graph_tool.topology.planarity_test() 등으로 제공하지는 않지만, 여러 가지 topology 함수 제공.
유사하게, 본 논문의 알고리즘을 “직접 구현”하려면, graph-tool의 low-level edge/vertex 접근을 써서 G̃ 구조를 만들어야 함. 그러나 이런 low-level 접근은 꽤 복잡.

5.2 기존 함수와의 연관

graph-tool의 “is_bipartite()”, “is_DAG()” 등은 DAG, bipartite 같은 특수한 속성 판별을 (\mathrm{O}(V+E))에 해줌.
Planarity 테스트는 이와 유사한 근본 기법(DFS, edge addition, merge, flip등)을 통해 구현할 수 있음.
다만 graph-tool에선 아직 “simple_planarity_test()” 같은 것이 제공되지 않음. (사용자 구현 필요)

6. 정리 및 의의

이 논문(“Simplified O(n) Planarity by Edge Addition”)은 O(n) 성능의 평면성 검사/임베딩 알고리즘을, “edge 단위”로 간단 명료하게 제시.
- 기존의 PQ-tree, PC-tree 기반 방식을 크게 단순화.
- Back edge 임베딩 시에 Walkup/Walkdown이라는 간단한 루틴으로 biconnected component를 병합 & flip.
- non-planar 시점 발견 시, 곧바로 Kuratowski subgraph를 추출.
실제 구현해도, 기존 알고리즘들보다 빠르거나 비슷한 성능을 보임이 여러 실험 결과로 제시.

7. (부록) 파이썬 Pseudocode 예시

주의: 아래 코드는 논문 속 pseudo-code를 파이썬 식으로 단순 모사한 것이며, 실제 동작하려면 G̃라는 임베딩 구조를 상세히 구현해야 합니다.

def planarity_check(graph):
    """
    논문 Boyer-Myrvold(2004) 스타일 edge-addition planarity 검사(의사코드).
    실제로 구현하려면 G~ (임베딩 구조), Walkup/Walkdown, Flip, Merge 등이 필요.
    """
    n = graph.num_vertices()

    # (1) DFS & lowpoint 계산
    parent, order, lowpt = dfs_with_lowpoint(graph)

    # (2) G~ (임베딩 구조) 초기화
    #   - 각 정점에 "backedgeFlag", "pertinentRoots", "separatedDFSChildList" 등 초기화
    G_tilde = init_embedding_structure(graph, parent, order, lowpt)

    # (3) 역순으로 정점 처리
    for v in reversed(range(n)):
        # (4) Tree edges: v -> 각 child c
        for c in children_of(v, parent):
            embed_tree_edge(G_tilde, v, c)

        # (6) Back edges: v -> 자손 w
        #    Walkup 호출: 자손 w를 "pertinent" 표시
        for w in find_descendant_back_edges(v, graph):
            walkup(G_tilde, v, w)

        # (9) 각 child c에 대해 Walkdown
        for c in children_of(v, parent):
            walkdown(G_tilde, v, c)  # 임베딩 시도

        # (11) 검사: 안 박힌 back edge가 있으면 non-planar
        for w in find_descendant_back_edges(v, graph):
            if not is_embedded(G_tilde, v, w):
                # (12) Kuratowski subgraph isolate
                subg = isolate_kuratowski_subgraph(G_tilde, graph, v)
                return (False, subg)

    # (14) 임베딩 복원(ShortCircuit 제거 + flip orientation 정리)
    final_embedding = recover_planar_embedding(G_tilde)

    return (True, final_embedding)

7.1 Walkup & Walkdown

def walkup(G_tilde, v, w):
    """
    back edge (v, w)에 대해 'w'와 w->...->v 경로 상 biconnected comp. root들을
    pertinent 표시.
    """
    # 1) w.backedgeFlag = v
    # 2) x, y = w (서로 다른 방향)
    # 3) 두 방향으로 external face path 따라가기 ...
    #   stopping 조건 등등
    pass

def walkdown(G_tilde, v, c):
    """
    biconnected component root = vc.
    back edges (v, w) 임베딩 시도하며 merge & flip.
    """
    # merge stack = []
    # two pass (양방향):
    #  while w != vc:
    #    if w.backedgeFlag == v:
    #       # merge stack 전부 merge
    #       # embed (v, w)
    #    ...
    pass

7.2 Flip과 Merge

def merge_biconnected_component(G_tilde, root_edge_info):
    """
    merge stack pop : (r, direction_in, rc, rc_out)
    biconnected comp flip여부 결정, adjacency link등 업데이트
    """
    pass

def embed_back_edge(G_tilde, v_root, w):
    """
    (v_root, w) 간선 임베딩
    -> 새 proper face 형성
    -> externall active 유지 등
    """
    pass

7.3 Non-planar 시 Kuratowski subgraph 찾기

def isolate_kuratowski_subgraph(G_tilde, graph, v):
    """
    - 'edge addition' 불가능해진 시점에서
    - figure 11의 minor A~E 중 어떤 상황인지 판단
    - homeomorph subgraph (K_5 or K_{3,3}) 구성
    - 반환
    """
    pass

8. 결론

Boyer–Myrvold (2004) 논문은 “Edge-Addition 방식”으로 평면성 검사(Planarity Testing)를 O(n)에 구현하며, 구조가 PQ-tree나 PC-tree 등보다 훨씬 단순.
플립(Flip), 머지(Merge), Walkup/Walkdown 등 몇 가지 절차만으로 구현 가능.
논문에 따르면 실제 구현 시 여러 최적화와 함께, 기존 방법보다 (PQ-tree, Hopcroft–Tarjan 등) 더 빠른 성능이 가능하다고 보고.
비평면(non-planar)일 때, Kuratowski Subgraph((K5) 또는 (K{3,3}))를 즉시 찾아내는 로직도 제시.

학습/연구 관점

이 알고리즘은 DFS 기반이며, ‘cut-vertex’(단절점)와 ‘biconnected component’, ‘back edge 임베딩’ 개념이 핵심.
graph-tool로 실제 구현하려면 로우 레벨 자료구조(G̃) 구현이 필요하지만, 아이디어 자체는 정점추가(vertex addition)보다 직관적.
알고리즘적 측면에서 ”Planarity → O(n) 시간에 가능”이 정말 복잡하지 않아도 된다는 점을 잘 보여주는 대표 연구.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 평면성(planarity) 검사 함수 is_planar()와, 평면 그래프를 최대 평면 그래프(maximal planar graph)로 만드는 함수 make_maximal_planar() 의 사용법, 그리고 내부 알고리즘(특히 Boyer–Myrvold 알고리즘)을 이해하는 데 도움이 되는 기본 원리들을 최대한 친절하게 설명한 것입니다.

1. 들어가기

평면 그래프(planar graph)란, 2차원 평면에서 간선이 서로 교차하지 않도록 그릴 수 있는 그래프를 말합니다.

예: 삼각형 그래프, 사각형 그래프 등은 평면 그래프다.
반면 (K5) (5개의 정점을 모두 연결한 완전그래프), (K{3,3}) (정점 3개씩 두 파트로 나눠 완전 이분 연결한 그래프)는 평면성이 없다(Non-planar). Kuratowski 정리에 따르면, 그래프가 평면성이 아니면 반드시 (K5)나 (K{3,3})의 부분 그래프(혹은 homeomorph)를 포함한다.

그래프의 평면성을 검사(planarity test)하려면, 과거엔 Hopcroft–Tarjan 알고리즘, PQ-tree, PC-tree 등 여러 복잡한 알고리즘이 존재했지만,
Boyer–Myrvold(2004)는 "edge addition" 접근을 사용해 (O(n)) 시간에 평면성을 판별하고, 비평면이면 Kuratowski subgraph도 추출하는 단순화된 방법을 제시했습니다.

graph-tool 라이브러리는 이 Boyer–Myrvold 알고리즘을 기반으로 is_planar() 함수를 구현해 두었으며, 결과로 평면성 여부, 임베딩(embedding) 정보, Kuratowski edge 등을 얻을 수 있습니다.

추가로, make_maximal_planar() 함수는 어떤 평면 그래프를 간선 추가를 통해 ‘최대 평면 그래프(maximal planar graph)’ 로 만드는 (더 이상 간선을 추가하면 교차가 생기는) 확장을 수행합니다.

2. `is_planar()` 함수: 그래프 평면성 검사

2.1 함수 시그니처 및 파라미터

is_planar(g, embedding=False, kuratowski=False)

g: 검사할 Graph 객체(무방향).
embedding: True이면, 평면일 때 정점별로 간선을 어떤 순서(시계방향/반시계방향)로 나열해야 하는지 임베딩 정보를 반환.
kuratowski: True이면, 비평면인 경우 평면성을 깨는 Kuratowski subgraph를 이루는 에지들의 property map(표시=1)을 반환.

반환값

is_planar (bool): 평면성 여부
embedding (선택, VertexPropertyMap): 각 정점에 대해, “시계방향으로 이어진 out-edges의 인덱스 순서” 리스트
kuratowski (선택, EdgePropertyMap): Kuratowski subgraph를 이루는 에지면 1, 아니면 0.

2.2 Boyer–Myrvold 알고리즘 개요

Boyer–Myrvold (2004): DFS를 기반으로 “edge-addition” 방식으로 각 간선을 순차 추가하면서 biconnected component 병합과 flip 연산을 통해 임베딩을 구성.
비평면이면, 특정 단계에서 “더는 간선 추가가 불가능” 판정이 나고, 그때 Kuratowski subgraph( (K5) 혹은 (K{3,3}) homeomorph )를 추출.

장점:
1. (O(n)) 시간
2. 구현 간단
3. Kuratowski 서브그래프도 추가로 얻기 가능

2.3 예시 코드

아래는 graph-tool에서 is_planar()를 사용하는 간단 예시입니다.

import graph_tool.all as gt
import numpy as np

def example_is_planar_basic():
    # 1) 임의 그래프(삼각분할) 만들기
    #    triangulation()은 임의 2D 점들의 델로네 삼각분할 -> 보통 planar
    coords = np.random.rand(100, 2)  # 100개의 (x,y) 난수
    g, pos = gt.triangulation(coords)  # g: 그래프, pos: 위치 정보
    
    # 2) 평면성 검사 : 임베딩 정보도 뽑기(embedding=True)
    planar, embedding = gt.is_planar(g, embedding=True)

    # 결과 출력
    print("Is planar?", planar)  # 대체로 True일 확률 높음
    # 임베딩 정보: 각 정점에 대해, 나가는(혹은 incident) edges의 시계방향순 인덱스 목록
    if planar:
        for v in g.vertices():
            emb_list = list(embedding[v])  # 임베딩된 간선 인덱스의 시계방향 순서
            print(f"Vertex {int(v)} embedding order:", emb_list)

    # 3) 시각화 : planar_layout() 등으로도 layout을 얻을 수 있지만, 
    #    triangulation 이미 pos를 줌. 그래프 그리기
    gt.graph_draw(g, pos=pos, output="example_is_planar_basic.svg")

실행해보면, 대부분 triangulation 그래프는 평면이므로 planar == True. 이 경우, embedding[v] 에서 각 간선 인덱스의 순서 정보를 확인할 수 있습니다.

2.3.1 Kuratowski subgraph 예시

def example_is_planar_kuratowski():
    # 1) 임의로 non-planar 그래프 만들기 (ex. K_5)
    g = gt.Graph()
    g.add_vertex(5)
    # 완전그래프(5)
    for i in range(5):
        for j in range(i+1,5):
            g.add_edge(g.vertex(i), g.vertex(j))
    
    # 2) 평면성 검사 : kuratowski=True
    planar, kur_map = gt.is_planar(g, kuratowski=True)
    print("Is planar?", planar)  # False
    
    # 3) kuratowski subgraph를 시각화 위해 edge_property bool적용
    #    True이면, 이 에지는 K-subgraph의 일부
    g.set_edge_filter(kur_map, inverted=False)
    
    # Layout
    # non-planar라 layout이 완벽히 평면적으로 안되지만 시각화 목적
    pos = gt.sfdp_layout(g)
    # 필터된 서브그래프(=Kur-subgraph)만 draw
    gt.graph_draw(g, pos=pos, output="example_kuratowski_subgraph.svg")

kur_map은 에지 프로퍼티 맵(edge property map). kur_map[e] == 1이면 Kuratowski subgraph의 일부.
위 예시로는 사실 K_5 전체가 Kuratowski이므로 거의 모든 에지가 1로 표시.

3. `make_maximal_planar()` 함수: 최대 평면 그래프 만들기

3.1 개념: 최대 평면 그래프

최대 평면 그래프(maximal planar graph):
평면 그래프에 대해, 더 이상 어떤 간선도 추가(교차 없이)할 수 없을 만큼 완전하게 간선을 갖춘 평면 그래프.
꼭짓점이 3개 이상인 평면 그래프에서 maximal planar라면, 오일러 공식으로부터 간선 수 = 3V - 6.
임의 평면 그래프(서로 다른 단절형태 등)가 주어졌을 때, 간선을 추가해 이 값(3V-6)에 도달하도록 만들어주는 과정.

3.2 시그니처

make_maximal_planar(g)

g: 반드시 biconnected planar graph(단절점 없이 연결된 평면 그래프)이어야 하며, num_vertices() >= 3.
biconnected & planar라는 전제 하에, 내부적으로 삼각형이 아닌 face들을 찾아서 계속해서 간선을 추가해 나감.

3.3 예시 코드

import graph_tool.all as gt

def example_make_maximal_planar():
    # 1) 간단한 평면 그래프 생성: 10 x 10 격자(lattice)
    #    보통 lattice는 연결은 되지만 (0,0) ~ (9,9)로 cut-vertex 발생 -> biconnected 아님
    #    -> graph-tool doc 예시에서는 biconnected "라고 가정" -> 
    #       lattice(10,10)은 actually biconnected가 아님. 
    #    그냥 예시로 써보면, 한번 시도해본다.
    
    g = gt.lattice([10, 10])
    # 우선 is_planar로 테스트
    p = gt.is_planar(g)[0]  # embedding=False, kuratowski=False
    print("Before make_maximal_planar, is_planar:", p)  # True
    
    # 2) make_maximal_planar 시도
    #    g가 biconnected 가정이 아니면 에러 or behavior undefined일 수 있음.
    gt.make_maximal_planar(g)  # 평면임을 가정 & biconnected라고 가정
    
    # 3) 다시 평면성 검사
    p = gt.is_planar(g)[0]
    print("After make_maximal_planar, is_planar:", p)  # True
    
    # 4) 간선 수 출력 -> 3V - 6 = 3*100 - 6 = 294
    print("num_vertices:", g.num_vertices(), " num_edges:", g.num_edges())
    
    # 5) 시각화
    pos = gt.planar_layout(g)  # planar embedding 기반 layout
    gt.graph_draw(g, pos, output="maximal_planar.png")
    print("Saved as 'maximal_planar.png'")

실제로 lattice(10,10) 예시는 biconnected가 아닐 수 있으므로, strict 모드에서는 make_maximal_planar()가 동작 안할 수도 있습니다(또는 특정 예외). 하지만 doc 예시에선 이런 식으로 사용법을 보여주고 있습니다.
진짜 biconnected planar 그래프 예시로는 원형 그래프(cycle) or 다각형 + chords, 델로네 삼각분할해서 안에 추가 간선을 제거한 평면 그래프 등등을 만들면 좋습니다.

4. 정리

is_planar():
Boyer–Myrvold 알고리즘 기반으로 그래프의 평면성을 O(n) 시간에 검사
- 원하는 경우, 평면 임베딩 정보(embedding=True)
- 비평면인 경우 Kuratowski subgraph 에지 표시(kuratowski=True)
make_maximal_planar():
현재 그래프가 biconnected planar라면, 간선을 덧붙여서 최대 평면 그래프로 만듦 (간선 수 = 3V - 6 에 도달)

graph-tool 을 쓰면, 이와 같은 복잡한 로직을 한두 줄로 간단히 호출 가능하므로, 네트워크 분석, 기하학적 그래프 시각화 등에서 매우 편리합니다.

5. 추가 학습 링크

Boyer & Myrvold (2004) 논문: 링크
Boost Graph boyer_myrvold_planar_test 문서: 링크
graph-tool 문서: 링크
“오일러 공식”, “Kuratowski 정리” 등 기초 그래프 이론.
“Edge-Addition approach” vs “Vertex-Addition approach” (PC-tree, PQ-tree).

아래 내용은 “Reciprocity of Networks with Degree Correlations and Arbitrary Degree Sequences”라는 논문( arXiv:0706.3372 )의 일부를 기반으로 작성되었습니다. 이 논문은 네트워크(그래프)에서 관측되는 reciprocity(호혜성)가 단순한 무작위 효과로부터 기인하는지, 아니면 네트워크의 더 깊은 구조적 특성을 반영하는지를 이론적으로 분석하며, 특히 노드 차수 간 상관관계(degree correlations)를 어떻게 고려하면 호혜성이 달라지는지를 다루고 있습니다.

1. 문제 배경과 Motivation

우리가 다루는 네트워크(그래프)에는 종종 단방향 연결(unidirectional edges)뿐 아니라 양방향 연결(bidirectional edges), 즉 서로를 연결하는 "쌍방 링크"가 섞여 있습니다. 예를 들어,

SNS, 웹 링크 등: 어떤 페이지가 다른 페이지로 링크가 되어있다고 해서 반대방향도 링크가 되어있는 것은 아니지만, 실제로는 양방향 링크도 의외로 많을 수 있음.
생물학적 네트워크(신경망, 대사 네트워크 등): 어떤 뉴런 A가 B로 시냅스를 갖고 있으면, B가 A로도 연결을 갖는 케이스가 존재(양방향).

이러한 양방향 링크(Reciprocal)의 비율을 reciprocity(또는 호혜성)이라 하며, 고전적 정의로는
[
r \;=\; \frac{L{\leftrightarrow}}{L}\,,
]
여기서 (L{\leftrightarrow})는 양방향 연결의 총 개수, (L)은 네트워크의 모든 (방향성) 링크 수를 뜻합니다.

하지만 실제 네트워크에는 단순히 "랜덤"해서 생긴 호혜성 말고도, 노드 차수의 분포 및 상관관계가 reciprocity에 크게 영향을 줄 수 있다고 논문은 주장합니다. 예컨대, 입력 차수(in-degree)와 출력 차수(out-degree)가 특정한 통계적 성질(예: 특정 분포, 특정 상관관계 등)을 가질 때, 이들의 조합이 커지거나 작아지는 식으로 reciprocity가 결정될 수 있다는 것이죠.

본 논문에서는 통계적(enumeration) 기법을 통해, 주어진 네트워크가 (1) 임의의 차수분포를 가지되, (2) 노드 차수 간 특정 상관관계를 가지고, (3) 노드쌍(에지쌍)에 대해서도 특정한 2-노드 차수 상관(예: source 노드의 out-degree와 target 노드의 in-degree가 상관됨 등)을 가질 때, 예상되는 reciprocity가 어느 정도인지(이론적 식) 제시합니다.

2. 주요 목표: Arbitrary Degree Sequences에서 Reciprocity의 기대값

이 논문의 핵심 아이디어는 다음과 같습니다:

네트워크의 크기가 (N)이고, 방향 에지가 (L)개 있다고 하자.
각 노드 (i)에 대해, in-degree = k_i^in, out-degree = k_i^out라 하자. (편의상 논문에서는 ((k_i, k_o))처럼 표기)
노드 사이 연결들에 대해, "노드 (k) 차수를 가진 소스에서 노드 (q) 차수를 가진 타겟으로 가는 에지"가 몇 개인지를 세어 (L(k \to q))라 정의.
이런 식으로 1-노드 차수 상관관계(즉, 한 노드 내부에서 in-degree와 out-degree 간 상관)와 2-노드 간 차수 상관(즉, 서로 연결된 노드쌍의 (in/out) vs. (in/out) 조합)이 있을 수 있다.

이를 통해, 각 링크가 쌍방(양방향)으로 존재할 확률을 계산하면, 네트워크 전반의 호혜성 (r)를 구할 수 있다는 것.

2.1. 기본 식

논문에서 제시되는 대표 식 중 하나:

[
r{1n2n} \;=\; \frac{1}{L}\sum{k,q} L(k \to q) \cdot \frac{L(k \leftarrow q)}{N(k) \, N(q)},
]

(k,q) : 노드 차수( in-degree/out-degree )의 특정 조합(예: ((k_i, k_o)) vs. ((q_i, q_o)) )
(N(k)) : 차수가 (k)인 노드의 개수
(L(k \to q)) : 차수 (k)를 가진 소스와 차수 (q)를 가진 타겟을 연결하는 링크의 개수
(L(k \leftarrow q)) : 차수 (q) 소스에서 차수 (k) 타겟으로 연결하는 링크의 개수

이는 "노드 단의 상관(1-node correlation)" + "에지쌍(2-node correlation)" 모두 고려한 식.
(논문 표기: (r_{1n2n}) )

2.2. 부분 상관관계를 고려할 때

논문에서는 상관관계가 없거나(또는 단순한 경우)면 이 식이 간단히 줄어들어서, 예컨대 in-degree와 out-degree가 독립이라면 (1-node correlation이 없는 경우)나, 2-node 중 어떤 것만 상관 있고 다른 것은 무시하면, reciprocity (r)가 어떠어떠한 간단 식으로 정리되는지를 보여줍니다.

대표적으로,

1-node correlation만 있는 경우:
[
r{1n} \;=\; \frac{\langle k_i k_o \rangle^2}{\langle k_i \rangle^4}
\frac{L}{N^2}.
]
(대략 이런 꼴: (r{1n} = \frac{L}{N^2}\times \frac{\langle k_i k_o\rangle^2}{\langle k_i\rangle^4}))
2-node (out-out) correlation만 있는 경우:
[
r{2n:o/o} = \frac{1}{L}\sum{k_o,q_o} L(k_o \to q_o) \frac{L(k_o \leftarrow q_o)}{N(k_o) N(q_o)}
]
(이것도 특정 분포함이 주어지면 단순화할 수 있음.)

이러한 식들로부터, 원하는 수준의 상관관계를 부여한 "랜덤 네트워크"에 대한 호혜성 기대값을 이론적으로 구할 수 있게 됩니다.

3. 요약: 어떤 네트워크에 이론 값을 적용하나?

논문에서는 이 식들을 실제 네트워크(예: 무역 네트워크, 신경망, 위키피디아 웹 등)에 적용하여 "차수 분포와 상관관계만"으로도 관측된 호혜성을 얼마나 설명할 수 있는지 분석했습니다.

World Trade Web: 거의 이론 식만으로도 실제 (r)값을 매우 근접하게 맞춤.
Food Web: 여러 곳에서 잘 맞거나, 혹은 일부 오차가 있는 등.
Wikipedia: 예측값보다 실측 reciprocity가 훨씬 큰데, 이는 네트워크 내부의 모듈성, 계층성 등 다른 구조적 요인이 존재한다는 의미.

결과적으로, "차수 기반의 상관관계만"으로도 호혜성이 어느 정도까지 설명 가능한지를 보여주고, 실제론 추가적인 구조가 들어가야(모듈성, 커뮤니티, 계층성 등) 호혜성 전체를 설명할 수 있다는 결론.

4. 예시 코드를 통한 사용법 (그래프 툴 연계)

파이썬 graph-tool 라이브러리와 연동하여, 만약 우리가 어떤 방향성 그래프 g를 가지고 있고, 그 네트워크의 차수 분포나 상관관계를 측정했을 때, 그때의 "이론적 reciprocity"를 계산하려면 다음과 같은 과정을 거칠 수 있습니다.

4.1 그래프에서 degree 정보 추출

import graph_tool.all as gt
from collections import Counter

def get_inout_degs(g):
    """
    각 노드별 (in-degree, out-degree)를 추출한다.
    g: graph_tool.Graph (directed)
    returns: list of (in_degree, out_degree)
    """
    degs = []
    for v in g.vertices():
        in_deg = v.in_degree()
        out_deg = v.out_degree()
        degs.append((in_deg, out_deg))
    return degs

4.2 노드 차수 빈도 `N(k)`와 링크 상관 `L(k->q)` 계산

def measure_degree_distribution(g, degs):
    """
    degs: list of (in_deg, out_deg)
    반환값:
        N_dict: {(in_deg, out_deg): 개수} 
        L_dict: {(in_deg, out_deg) -> (in_deg2, out_deg2): 개수}
    """
    # N_dict 계산
    N_dict = Counter(degs)
    
    # L_dict 계산: 인접 행렬(혹은 adjacency) 순회
    L_dict = Counter()
    
    for s in g.vertices():
        s_k = (s.in_degree(), s.out_degree())
        for t in s.out_neighbors():
            t_k = (t.in_degree(), t.out_degree())
            L_dict[(s_k, t_k)] += 1
    
    return N_dict, L_dict

이렇게 (s_k, t_k) 식으로 카운팅하면, (\textstyle L(k \to q))에 대응하는 자료구조가 생김.

4.3 예: 전체 상관(1node+2node) 시 reciprocity 이론값 계산

[r{1n2n} = \frac1L \sum{k,q} L(k\to q) \frac{L(k\leftarrow q)}{N(k)\,N(q)}. ]

def reciprocity_1n2n(g, N_dict, L_dict):
    """
    이론식 r_{1n2n} = 1/L sum_{k,q} [ L(k->q)* L(k<-q) / (N(k)*N(q)) ]
    단, k, q는 (in_deg, out_deg) 튜플
    """
    L = g.num_edges()
    val_sum = 0.0
    for (k, q), L_kq in L_dict.items():
        # L(k->q) = L_kq
        # L(k<-q) = L_dict.get((q, k), 0)
        L_qk = L_dict.get((q, k), 0)
        if L_qk == 0:
            continue
        # N(k) = N_dict[k], N(q) = N_dict[q]
        Nk = N_dict[k]
        Nq = N_dict[q]
        val_sum += L_kq * L_qk / (Nk * Nq)
    
    return (1.0 / L) * val_sum

이렇게 하면, 논문에서 언급된 r1n2n이론값을 계산 가능. 만약 실제 그래프의 reciprocity는 단순히 (양방향 에지 수)/(전체 에지 수)로 계산이 가능:

def real_reciprocity(g):
    """
    실제 호혜성 = (양방향 edge 개수) / (전체 edge 개수)
    """
    L = g.num_edges()
    L_bi = 0
    for e in g.edges():
        s = e.source()
        t = e.target()
        # 만약 t->s도 있다면...
        if g.edge(t, s) is not None:
            L_bi += 1
    # 이런 식은 e,t 쌍에 대해 2번 counting됨 -> L_bi/2 가 진짜 양방향 개수
    # 하지만 reciprocity는 L_bi / L (양방향의 '방향성 에지' 개수로 치면 2* #양방향임.)
    # 일반적으로 r = (양방향 연결 쌍수) / L
    # => (L_bi/2) / L
    return (L_bi/2.0) / L

4.4 부분 상관만 고려하는 reciprocity 계산도 가능

reciprocity_1n() : 1-node correlation만 고려한 식
reciprocity_2n_o_o(): 2node (out-out) correlation만 고려
reciprocity_2n_i_o(): 2node (in-out) correlation만 고려
... 등등

결론 정리

논문의 주된 결론:
- '차수분포 + 노드 상관관계'(1-node)와 '에지(노드쌍) 차수 상관'(2-node)를 고려하면, 실제 네트워크의 호혜성 (r)값을 상당 부분(심지어 대부분) 설명 가능함.
- 일부 네트워크(예: Wikipedia)에서는 모듈성, 계층성, 기타 내부구조가 커서 단순 차수 상관으로 설명하기 어려울 수 있지만, 그래도 이러한 차수 상관으로부터의 기대값과 실제값을 비교하는 것이 유용한 통계적 방법론을 제공.
graph-tool 등에서 실제 그래프 g의 in/out-degree를 추출하여, 제시된 식에 따라 이론값을 계산한 뒤, 실제 r과 비교해볼 수 있음.
네트워크 랜덤화 기법(rewiring)으로 특정 상관구조를 보존/파괴하면서 reciprocity가 어떻게 변하는지 실험적으로도 확인할 수 있음.

이처럼, 네트워크 이론에서 reciprocity는 단순한 무작위 성분이 아닌, 다양한 차수 상관관계의 구조적 결과물이기도 하며, 차수 정보만으로도 꽤 정확히 예측할 수 있음을 보여주는 결과라고 요약할 수 있습니다.

참고 수식/개념 요약

호혜성(Reciprocity) 정의
[
r = \frac{L{\leftrightarrow}}{L},
]
여기서 (L{\leftrightarrow})는 양방향 에지 쌍의 개수.
일반 식 (1-node + 2-node 상관관계 모두 있을 때)
[
r{1n2n} \;=\; \frac{1}{L} \sum{k,q} L(k\to q)\; \frac{L(k\leftarrow q)}{N(k)\;N(q)}.
]
( (N(k)): 차수가 k인 노드 수, (L(k\to q)): 차수 k->q인 링크 수 )
1-node 상관만 있는 경우
[
r_{1n} \;=\; \frac{\langle k_i\,k_o\rangle^2}{\langle k_i\rangle^4} \;\times\; \frac{L}{N^2}
]
(정확한 형태는 논문 내 파트 참고)
2-node (out-out) 상관만 있는 경우
[
r{2n:o/o} \;=\; \frac{1}{L}\sum{k_o,q_o}\; L(k_o\to q_o)\; \frac{L(k_o\leftarrow q_o)}{\,N(k_o)\,N(q_o)\,}
]

파이썬 튜토리얼 예시 (정성스럽게)

import graph_tool.all as gt
from collections import defaultdict

def calculate_reciprocity_1n2n(g):
    """
    논문 arXiv:0706.3372 식 (3)에 해당하는, 
    '1-node + 2-node' correlation을 모두 고려한 r_{1n2n} 추정.
    """
    # 1) 전체 edge 수
    L = g.num_edges()
    if L == 0: 
        return 0.0
    
    # 2) 각 vertex의 in/out deg -> (in_deg, out_deg)
    deg_map = {}  # v -> (in_deg, out_deg)
    for v in g.vertices():
        deg_map[int(v)] = (v.in_degree(), v.out_degree())
    
    # 3) N_dict[(k_in, k_out)] = 해당 차수를 가진 노드 수
    from collections import Counter
    N_dict = Counter(deg_map.values())
    
    # 4) L_dict[((k_in1,k_out1),(k_in2,k_out2))] = #링크수
    L_dict = Counter()
    for e in g.edges():
        s, t = int(e.source()), int(e.target())
        sk = deg_map[s]
        tk = deg_map[t]
        L_dict[(sk, tk)] += 1
    
    # 5) 식 계산
    val_sum = 0.0
    for (k, q), L_kq in L_dict.items():
        # k->q : L_kq
        # k<-q : L_qk
        L_qk = L_dict.get((q, k), 0)
        if L_qk == 0:
            continue
        
        # N(k) = N_dict[k], N(q) = N_dict[q]
        Nk = N_dict[k]
        Nq = N_dict[q]
        
        val_sum += L_kq * L_qk / (Nk*Nq)
    
    # r_{1n2n} = (1/L)*val_sum
    return val_sum / float(L)

def real_reciprocity(g):
    """
    실제 네트워크의 reciprocity 계산
    """
    L = g.num_edges()
    if L == 0: 
        return 0.0
    count_bi = 0
    for e in g.edges():
        s, t = e.source(), e.target()
        if g.edge(t, s) is not None:
            count_bi += 1
    # count_bi는 양방향 edge '쌍' 중 한쪽 방향만 센 것 => 실제 bidir edge 개수= count_bi/2
    # r = (bidirectional 개수) / L
    return (count_bi / 2.0) / L

def example_reciprocity_arxiv0706():
    # 1) 임의의 directed graph 생성 or load
    g = gt.random_graph(50, lambda: (2,2), directed=True)
    #    (노드 50개, 평균차수 대략 2)
    
    # 2) 실제 호혜성
    r_real = real_reciprocity(g)
    
    # 3) 논문의 r_{1n2n} 식으로 예측값 계산
    r_theo = calculate_reciprocity_1n2n(g)
    
    print("Actual reciprocity (real) =", r_real)
    print("Theoretical (1n+2n) reciprocity =", r_theo)

if __name__ == "__main__":
    example_reciprocity_arxiv0706()

위 코드는 (1) 임의 방향 그래프를 만들고, (2) 실제 호혜성 r_real, (3) 논문의 1node+2node correlation 기반 이론값 r_theo를 출력하는 예시입니다. 실제 네트워크 예시로 대체해볼 수도 있습니다.

요약

Reciprocity (r): 네트워크에서 양방향 링크가 얼마나 많은지 나타내는 지표.
기존에는 단순 무작위 네트워크와 비교해 "r이 크다/작다" 판단하는 경우가 많았으나, 사실 각 노드의 in/out 차수분포 및 상관관계만으로도 호혜성을 크게 변화시킬 수 있음을 강조.
본 논문( arXiv:0706.3372 )은 “주어진 네트워크에서 (1) 노드 차수 분포, (2) 노드 1개 내 in-out 상관(1-node correlation), (3) 노드쌍 2개 간 (in-in, out-out, in-out, out-in) 상관”을 어떻게 고려하면, 네트워크 전체 기대 호혜성 (r)을 계산할 수 있는지 제시함.
제시된 식(예: (r{1n2n}, r{2n:o/o}, r_{1n}, ...))을 통해 실제로 네트워크를 “해당 차수분포+상관만 유지한 랜덤 네트워크”들과 비교 가능.
실험 결과, 무역 네트워크( World Trade Web )나 food web 등은 이론값과 거의 일치 -> 호혜성이 대부분 차수 상관관계로부터 기인. 반면 Wikipedia 등은 이론값보다 호혜성이 훨씬 큼 -> 모듈성이나 계층성 등 다른 구조가 큼.

실무적 의의:

어떤 네트워크에서 호혜성이 "우연히" 큰 건지, "구조적으로" 큰 건지 확인 시, 차수 기반 상관관계만의 기여도를 빼고 남은 차이가 사실상 그 네트워크만의 특수 구조(예: 계층성, 모듈성 등)를 의미하게 됨.
이 과정을 통해 네트워크가 왜 높은(또는 낮은) 호혜성을 가지는지에 대한 이론적·실증적 해석을 제공할 수 있음.

아래 내용은 파이썬 graph-tool 라이브러리에서 제공하는 edge_reciprocity() 함수에 대한 설명과, 이를 활용한 초보자도 이해하기 쉬운 튜토리얼을 담고 있습니다. 특히 “Reciprocity(호혜성)” 지표가 무엇이며, graph-tool을 통해 어떻게 계산하는지, 그리고 어떻게 활용할 수 있는지를 단계별로 자세히 정리해보겠습니다.

1. 개념 정리: Edge Reciprocity(호혜성)이란?

graph_tool.topology.edge_reciprocity(g, weight=None) 함수는 네트워크(그래프)의 호혜성을 계산합니다.

1.1 호혜성(Reciprocity)의 정의

방향 그래프(directed graph)에서, 양방향 연결(서로를 잇는 쌍방 링크)이 얼마나 많이 존재하는지를 나타내는 척도입니다.
전통적인 정의로는,

[
r \;=\; \frac{L{\leftrightarrow}}{L}\,,
]
여기서 (L{\leftrightarrow})는 양방향(서로를 잇는) 에지 쌍의 개수, (L)은 총 방향성 에지의 개수입니다.
예를 들어, (u \to v) 에지가 있고, 동시에 (v \to u) 에지가 있으면, 양방향 연결 하나가 존재한다고 합니다.

1.2 가중치(Weights)가 있는 경우

edge_reciprocity()는 가중치 옵션도 지원합니다.
가중치가 주어지면, "간선 개수" 대신 "간선 가중치 합"을 기준으로 호혜성을 계산합니다.
- 즉 (\displaystyle r = \frac{\sum w{\leftrightarrow}}{\sum w{\text{all}}})
- (\sum w_{\leftrightarrow})는 양방향 에지 쌍의 합(단, 각 방향 에지의 가중치는 합산)
- (\sum w_{\text{all}})는 전체 에지 가중치의 합.

2. 함수 사용 방법

2.1 간단 예시

import graph_tool.all as gt

def demo_edge_reciprocity_basic():
    # 1) 간단한 방향 그래프 g 생성
    g = gt.Graph(directed=True)
    
    # 2) 노드 2개 추가
    v0 = g.add_vertex()
    v1 = g.add_vertex()
    # 현재 g.num_vertices() == 2

    # 3) 일방향 간선 v0->v1 추가
    e1 = g.add_edge(v0, v1)
    
    # 4) 호혜성 계산
    r1 = gt.edge_reciprocity(g)
    print("초기 호혜성(양방향 연결 없음) =", r1)  # 예상: 0.0
    
    # 5) 반대방향 v1->v0 간선 추가
    e2 = g.add_edge(v1, v0)
    
    # 6) 다시 호혜성 계산
    r2 = gt.edge_reciprocity(g)
    print("양방향 연결 생긴 후 호혜성 =", r2)   # 예상: 1.0

if __name__=="__main__":
    demo_edge_reciprocity_basic()

실행 결과

처음에는 v0->v1만 있어서 양방향 연결이 하나도 없으므로 r = 0.0.
이후 v1->v0를 추가하면 두 노드가 서로 이어지므로, 모든 에지가 사실상 양방향 쌍(1쌍)뿐이므로 r = 1.0.

2.2 임의 그래프/가중치 그래프 활용

아래 예시는 무작위로 그래프를 생성하고, 가중치도 임의 부여하여 호혜성을 계산해보는 코드입니다:

import graph_tool.all as gt
import numpy as np
import random

def demo_edge_reciprocity_weighted():
    # 1) directed=True 로 임의 그래프 생성
    g = gt.random_graph(10, lambda: (random.randint(1,3),random.randint(1,3)), directed=True)
    # 위처럼 하면 대략 10개 노드, 임의의 average out-degree(1~3)

    # 2) 간선 weight property 만들기
    w_prop = g.new_edge_property("double")
    for e in g.edges():
        w_prop[e] = random.uniform(0.5, 2.0)  # 0.5 ~ 2.0 사이 임의값

    # 3) 가중치 기반 호혜성 계산
    r = gt.edge_reciprocity(g, weight=w_prop)
    print("Weighted edge reciprocity =", r)

if __name__=="__main__":
    demo_edge_reciprocity_weighted()

여기서 무작위로 간선을 생성하되, 노드별 (평균차수 1~3)정도로 만들어볼 뿐이므로, 매우 작은 그래프가 됩니다.
무작위 weight를 할당한 후, gt.edge_reciprocity(g, weight=w_prop)로 가중치 포함 reciprocity를 얻습니다.

3. 내부 동작 및 복잡도

edge_reciprocity(g)는 내부적으로 모든 에지를 훑어보며, 해당 에지의 반대방향이 존재하는지 검사하여, 양방향 여부를 판별합니다.
Complexity:
- 문서상 O(E)로 표기. 즉 (E = L)은 에지 개수.
- 병렬( OpenMP )을 사용하면 multi-thread로 속도 개선 가능.

4. 실제 예시: PGP 네트워크(인용)

문서 예시에서처럼 g = gt.collection.data["pgp-strong-2009"] 라는 그래프를 불러온 후:

import graph_tool.all as gt

def demo_pgp_network():
    g = gt.collection.data["pgp-strong-2009"]  # PGP 네트워크 (directed)

    # 호혜성 계산
    r = gt.edge_reciprocity(g)
    print("PGP strong(2009) network reciprocity:", r)

if __name__=="__main__":
    demo_pgp_network()

결과 예시: 0.692196963163...
즉 약 69.2% 에지가 양방향성을 이룬다고 해석.

5. 요약 & 주의사항

edge_reciprocity는 "에지" 관점에서, "양방향이 얼마나 많은가?"를 계산.
가중치 있으면 "edge 개수" 대신 "edge weight 합"으로 계산.
내부적으로:
- (u->v)가 있으면 (v->u)도 있는지 체크해서 count (또는 weight sum)
- 총 edge (또는 weight) 대비 양방향의 비율.
복잡도: O(E).
Directed graph가 아닌 경우, 혹은 무방향인 경우, 당연히 reciprocity=1(또는 의미 없음).
Self-loop(자기 루프)가 있으면, 보통 reciprocity 계산에 포함되지 않음. graph-tool에서는 self-loop는 (u->u) 형태. 이건 (u<-u)도 같아서, edge_reciprocity에서 어떻게 처리하는지는 graph-tool doc(2023버전) 상에는 명시X이지만, 대개는 self-loop는 양방향 연결과는 다른 개념이라 0으로 처리될 것으로 추정.

결론

이상으로, 파이썬 graph-tool 라이브러리의 edge_reciprocity() 함수 사용법을 처음부터 코드 예시와 함께 살펴보았습니다.

Reciprocity(호혜성)는 네트워크에서 단방향/양방향 연결 비율을 측정하는 핵심 지표.
edge_reciprocity(g, weight=None): 그래프 G에 대해 (가중치가 있으면 weight를 적용하여) 호혜성 값을 계산해주는 편리한 함수.
실제로 네트워크의 구조(특히, 노드 차수 상관관계)에 따라 reciprocity가 달라지므로, 단순히 "r이 크다/작다"보다는, 위 논문( [lopez-reciprocity-2007] )에서 제시된 이론값과 비교함으로써, 네트워크의 다른 구조적 특성을 파악할 수 있습니다.

추가로, 필요하다면 gt.is_planar(), gt.min_spanning_tree() 등과 조합해서, 네트워크의 평면성, MST, 커뮤니티 등 다양한 분석과 함께 호혜성을 해석해볼 수 있습니다.

(끝)

아래 내용은 여행하는 외판원 문제(Travelling Salesman Problem, TSP)에 관한 긴 위키피디아 내용을 바탕으로, 처음 공부하는 학생도 이해할 수 있도록 한글로 친절하고 자세하게 설명하며, 파이썬 예제 코드를 포함한 튜토리얼을 제공하는 형태로 작성되었습니다. 특히 도시·교통 빅데이터 관점에서 TSP가 왜 중요한지, 어떤 이론적/실용적 배경이 있는지, 그리고 간단한 파이썬 예시 코드를 통해 TSP를 어떻게 구현(또는 근사해결)할 수 있는지를 살펴보겠습니다.

1. 여행하는 외판원 문제(TSP)란?

여행하는 외판원 문제(Travelling Salesman Problem, TSP)는 다음과 같이 정의됩니다:

“서로 다른 (n)개의 도시가 주어지고, 각 도시 쌍 사이의 이동 비용(거리)이 주어졌다고 할 때, 어떤 외판원이 모든 도시를 정확히 한 번씩 방문하고 다시 출발 도시로 돌아오는 경로 중, 그 이동 비용(거리) 합이 최소가 되는 경로(해밀턴 순환)를 찾아라.”

입력: 도시들의 개수 (n), 도시 간 이동 비용을 나타내는 (대개) (n \times n) 행렬(혹은 그래프 형태).
출력: 모든 도시를 단 한 번씩 방문하고 돌아오는 순회를 구성하는 순열(혹은 경로), 그 중 비용이 최소인 것.

1.1. 왜 중요한가?

NP-난해도(NP-hard) 문제 중에서도 매우 잘 알려진 전형적인 최적화 문제.
공급망 로지스틱스, 통근/교통 관리, PCB 회로 기판 드릴링(공정 경로 최적화), 자율주행 로봇의 경로, DNA 조각 연결 순서 최적화 등 다양한 실용 분야에서 나타납니다.
단순해 보이지만, 도시의 수가 조금만 커도 순열(경로) 가짓수가 ( (n-1)! ) (대칭 TSP의 경우는 다시 절반 정도)로 폭발적으로 증가하므로, 고전적 완전탐색(brute force)은 사실상 불가능에 가깝습니다.

2. 수학적·이론적 배경

2.1 복잡도

TSP의 결정버전(decision version)은 NP-완비(NP-complete)임이 알려져 있습니다.
최적해를 구하는 것은 NP-hard로서, 규모가 큰 문제에 대한 효율적(다항시간) 알고리즘은 (P=NP가 아닌 이상) 존재하지 않는다고 믿어집니다.

2.2 여러 변형/제약

대칭 TSP vs. 비대칭 TSP: 이동 비용 (d{ij})와 (d{ji})가 같은지 여부.
메트릭 TSP: 삼각 부등식( (d{ij} \le d{ik}+d_{kj}) )이 성립할 경우. (예: 유클리드 거리)
Euclidean TSP: 도시 위치가 실제 평면 좌표로 주어지고, 유클리드 거리를 사용.
Vehicle Routing Problem(VRP), Traveling Purchaser Problem 등도 TSP 일반화로 볼 수 있습니다.

2.3 MILP 정형화 예시 (Dantzig–Fulkerson–Johnson 식)

[
\begin{aligned}
\text{minimize}& \quad \sum{i=1}^{n}\sum{\substack{j=1 \ j \neq i}}^{n} c{ij} x{ij},\
\text{subject to}& \quad \sum{\substack{i=1 \ i\neq j}}^{n} x{ij} = 1\quad(\forall j), \
& \quad \sum{\substack{j=1 \ j\neq i}}^{n} x{ij} = 1\quad(\forall i), \
& \quad \sum{i \in Q}\sum{\substack{j \in Q \ j\neq i}} x{ij} \le |Q|-1 \quad (\forall Q \subset {1,\dots,n}, |Q|\ge2 ),\
& \quad x{ij}\in {0,1}.
\end{aligned}
]

(x_{ij} = 1)은 도시 (i)에서 도시 (j)로 이동하는 방향 에지를 선택했음을 의미합니다.
(\sum x_{ij}=1) 조건들은 “각 도시로 들어오는(나가는) 간선이 정확히 1개”임을 보장.
마지막 부등호((\sum_{i\in Q}\dots \le |Q|-1))는 “부분 집합 (Q) 내에서 서브투어(subtour)가 형성되지 않도록” 하는 제약(서브투어 제거 제약).

3. 알고리즘: 완전탐색 ~ 근사/휴리스틱

3.1 완전탐색

(O(n!)) 시간에 모든 순열을 검사. (n)이 15~20만 돼도 불가능에 가까움.
동적 프로그래밍(Held-Karp) 접근: (O(n^2 \cdot 2^n))로 “비교적” 낫지만 여전히 지수적(=크게 의미있는 수준은 아님).

3.2 정확해(Exact) 기법

브랜치-앤-바운드(Branch-and-Bound), 커팅 플레인(Cutting Plane), Branch-and-Cut 기법 등을 적용하면 10^5개 도시까지도 특정 상황에서 해결 시도(극도로 오래 걸리기도).
연구용으로는 Concorde TSP Solver가 유명.

3.3 근사(Approximation) & 휴리스틱(Heuristic)

실제로는, 크기가 큰 TSP에 대한 ‘완벽해’를 구하기보다는 근사·휴리스틱 알고리즘을 통해 빠르게 (때론 최적 대비 1~3% 이내) 해를 얻습니다.

(A) 그리디 휴리스틱

Nearest Neighbor(최근접 탐색)
- 현재 도시에서 가장 가까운 미방문 도시로 이동 반복.
- 빠르지만, 종종 최적해 대비 20~30% 이상 차이날 수도 있음.
Greedy Matching 등...

(B) 2-Opt/3-Opt/ k-Opt 개선

이미 만들어진 순회를 조금씩 수정(교환)하며 개선하는 로컬 서치(local search).
예: 2-opt는 경로에서 교차하는 에지 2개 제거 & 재연결 -> 더 짧아지면 적용.
3-opt, Lin–Kernighan 등 확장 기법. 실용적으로 매우 잘 동작.

(C) 메타 휴리스틱

유전 알고리즘(GA), 개미 알고리즘(ACO), 담금질(Simulated Annealing), 탭서치(Tabu Search) 등.
전역 탐색적 아이디어로 다양한 해를 탐색 -> 점진적으로 좋은 해를 찾음.

4. 간단 파이썬 예시 코드: 2-Opt 휴리스틱

아래는 파이썬에서 간단히 2-Opt를 통해 TSP 경로를 개선하는 예제 코드입니다.
(단, 여기서는 그래프 형태보다는 편의상 도시 간 거리 행렬을 이용합니다.)

import math
import random

def calc_tour_length(tour, dist_matrix):
    """
    tour: 도시 방문 순서 리스트, 예: [0, 2, 1, 3, 0]
    dist_matrix: dist_matrix[i][j] = i->j 거리(혹은 비용)
    """
    length = 0.0
    for i in range(len(tour) - 1):
        length += dist_matrix[tour[i]][tour[i+1]]
    return length

def two_opt_swap(tour, i, k):
    """
    tour[i..k] 구간을 뒤집어서 (i, i+1) 및 (k, k+1) 구간을 바꿔새 경로 생성
    """
    new_tour = tour[0:i]
    new_tour += reversed(tour[i:k+1])
    new_tour += tour[k+1:]
    return list(new_tour)

def solve_tsp_2opt(dist_matrix):
    """
    2-Opt 로컬 서치 기반 TSP 해결 (단, 시작도시=0 고정)
    dist_matrix: NxN 형태의 거리행렬
    """
    n = len(dist_matrix)
    
    # 1) 임의 혹은 간단한 초기 순회 생성: [0 -> 1 -> 2 -> ... -> n-1 -> 0]
    curr_tour = list(range(n))
    curr_tour.append(0)
    best_dist = calc_tour_length(curr_tour, dist_matrix)

    improved = True
    while improved:
        improved = False
        # 2) 모든 (i, k) 쌍에 대해 swap 시도
        for i in range(1, n-1):
            for k in range(i+1, n):
                if k - i == 1: 
                    continue  # swap 이득이 없을 가능성 높음
                new_tour = two_opt_swap(curr_tour, i, k)
                new_dist = calc_tour_length(new_tour, dist_matrix)
                if new_dist < best_dist:
                    curr_tour = new_tour
                    best_dist = new_dist
                    improved = True
                    break  # 이중 for문 탈출위한 조치
            if improved:
                break
    return curr_tour, best_dist

# -- 시연 예시 --
if __name__=="__main__":
    # 도시 5개, 무작위 distance matrix 생성(대칭, triangle inequality 대충 만족)
    n_cities = 5
    coords = [(random.random()*100, random.random()*100) for _ in range(n_cities)]
    
    # 유클리드 거리행렬
    dist = [[0]*n_cities for _ in range(n_cities)]
    for i in range(n_cities):
        for j in range(n_cities):
            if i==j:
                dist[i][j]=0
            else:
                dx = coords[i][0] - coords[j][0]
                dy = coords[i][1] - coords[j][1]
                dist[i][j] = math.sqrt(dx*dx + dy*dy)
    
    # 2opt로 순회계획
    route, length = solve_tsp_2opt(dist)
    print("2-Opt 결과 경로:", route)
    print("경로 길이:", length)

코드 해석

calc_tour_length(): 순회(tour)의 길이(=모든 구간 거리 합)를 계산.
two_opt_swap(): 구간 [i..k]를 뒤집어 경로를 수정하는 스왑 연산.
solve_tsp_2opt():
1. 일단 [0, 1, 2, ..., n-1, 0] 기본 순회를 초기해로 설정(간단).
2. 이중 for문으로 모든 (i, k) 부분 스왑을 시도 -> 개선되면 채택.
3. 더 이상 개선이 없을 때 종료.
무작위 5개 도시(2D 좌표) 생성 후, 유클리드 거리행렬 dist를 만든 뒤 2-Opt를 실행.
실제론 (n)이 훨씬 큰 경우, 이 방법은 근사적 빠른 해를 얻게 됩니다.

이 간단한 2-Opt는 인스턴스가 커지면 시간이 많이 걸릴 수 있지만( (\approx O(n^2)) ~ (O(n^3))로 추정 ), 중간 규모(수백~수천 도시) 정도에서는 충분히 빠른 편이어서 TSP 근사해로 자주 활용됩니다.

5. 마무리

여행하는 외판원 문제(TSP)는 전산학, 최적화, 그래프이론 등에서 대표적인 NP-hard 문제로 널리 연구되어 왔습니다.
큰 (n)에 대해 최적해 구하기는 매우 어렵지만, 다양한 근사·휴리스틱 기법(그리디, 2-opt, 3-opt, Lin–Kernighan 등)을 이용해 실용적 해를 얻을 수 있습니다.
TSP는 실제 도시·교통 빅데이터 상황(물류 경로, 버스/택시 동선 최적화, 로보틱스 등)에서도 중요한데, 대규모 문제 시 정확해보다는 근사해(예: 2-Opt, Meta-heuristic) 사용이 일반적입니다.
더 깊은 내용(예: Branch-and-Cut, MILP 정식, 고차원 근사 등)은 전문적인 라이브러리(Concorde, OR-Tools 등)나 연구논문 참고가 필수입니다.

(끝)

아래 튜토리얼은 그래프 툴(graph-tool) 라이브러리에서 제공하는 tsp_tour() 함수를 활용해, 간단한 TSP (여행하는 외판원 문제) 경로를 구하는 방법을 단계별로 설명합니다. 도시, 교통 빅데이터, 네트워크 분석 관점에서 TSP는 여러 용례(물류/배송 경로 최적화, 공정 라우팅 등)에서 자주 등장합니다. 이 튜토리얼에서는 초보자도 따라할 수 있도록 파이썬 코드를 포함해 최대한 정성스럽고 실용적으로 구성했습니다.

1. `tsp_tour()` 함수 개요

함수: graph_tool.topology.tsp_tour(g, src, weight=None)
목적:
- 그래프 (g)에서 하나의 순회(tour) 경로를 구하는데, 이는 “모든 정점을 방문하고” 다시 시작점 (src)로 돌아오는 경로(=여행하는 외판원 문제의 투어)입니다.
- 결과로 나오는 투어 길이는, 최적해 대비 (최악의 경우) 2배 이내(즉 2-approx 근사).
인자:
1. g: 그래프(반드시 무방향 undirected 이어야 함)
2. src: 순회(투어)의 시작·종료가 되는 정점 (Vertex 객체)
3. weight: (선택) 엣지 가중치(거리, 비용 등). EdgePropertyMap 형태. 없으면 단순히 1로 간주.
반환:
- tour: numpy.ndarray 형태, 정점 번호의 리스트. 예: [0, 1, 2, ... 0]
- 마지막 원소가 초기 src와 동일(순회가 끝에서 다시 출발점으로 돌아옴).
시간 복잡도: (O(E + V \log V)) (Boost 문서 기준)

1.1 내부 알고리즘 개념

최적해보다 2배 이내인 근사해를 구하기 위한 전형적인 MST(최소 스패닝 트리) 기반 휴리스틱(Christofides의 간단 버전) 기법을 사용.
구체적으로:
1) 그래프의 모든 정점을 잇는 최소 스패닝 트리(MST)를 구성.
2) MST를 DFS나 Euler tour 기법으로 순회.
3) 중복 방문이 발생하면 “건너뛰기(short-cut)” 등을 통해 단일 Hamiltonian cycle 형성.
4) 그 결과, 비용이 최적 대비 최대 2배 이하임을 이론적으로 보장.

2. 예제 코드: `tsp_tour` 간단 사용법

아래 예제에서는 graph-tool로 무작위 격자 그래프를 만든 뒤, tsp_tour()로 투어를 구합니다.

import graph_tool.all as gt
import numpy as np

def example_tsp_tour():
    # 1) 무방향 그래프 g 만들기
    #    예) 10x10 격자 (lattice)
    g = gt.lattice([10, 10])  # 100개 정점, 2D 격자식 연결, 무방향
    
    # 2) 시작 정점(src) 지정: 일단 0번 정점 (g.vertex(0) 객체)
    src_vertex = g.vertex(0)
    
    # 3) tsp_tour 호출
    #    - weight=None: 모든 엣지 비용=1 로 처리 (default)
    #    - weight=some_edge_prop: 가중치 적용 가능
    tour_array = gt.tsp_tour(g, src=src_vertex, weight=None)
    # tour_array: numpy.ndarray, 예) [ 0,  1,  2, ...,  0 ]
    
    print("TSP Tour (vertex indices):", tour_array)
    print("Number of visited vertices (including the last repeated src):", len(tour_array))
    
    # 4) 간단히 길이 계산 (모든 엣지=1 이므로, = 투어에 포함된 엣지 수)
    #    graph-tool은 undirected -> tsp_tour 로 반환된 경로의 간선수 = len(tour_array)-1
    #    => 2D lattice에서 실제 '최단'과 비교: 여기서는 단순히 예시.
    tour_length = len(tour_array) - 1  # weight=None -> 그냥 edge=1씩
    print("Approx. TSP tour length:", tour_length)
    
    # 5) 시각화 (optional)
    #    planar_layout은 일반적으로 planar 그래프에서만 쓰이지만
    #    여기서는 lattice 구조가 충분히 planar -> 레이아웃 대충 나타냄
    pos = gt.planar_layout(g)
    #    만약 layout이 proper하지 않으면 다른 layout 함수 예: sfdp_layout(등)
    
    # 그래프 그리기: 투어에 사용된 간선을 강조
    #  - 먼저 edge property map 생성하여, 투어 간선이면 color=red, 아니면 gray
    ecolor = g.new_edge_property("string", val="gray")  # 기본회색
    # 'tour_array' 인접한 정점 쌍마다 edge를 찾아서 color=red
    for i in range(len(tour_array)-1):
        v1 = tour_array[i]
        v2 = tour_array[i+1]
        # v1->v2 또는 v2->v1 edge 찾아서 ecolor[e]="red"
        #  (그래프가 undirected 이므로 어느방향 edge든 동일)
        e = g.edge(v1, v2)
        if e is not None:
            ecolor[e] = "red"
    
    # draw
    gt.graph_draw(g, pos=pos,
                  vertex_text=g.vertex_index,
                  edge_color=ecolor,
                  output_size=(600, 600),
                  output="lattice_tsp_tour.png")
    print("Graph with TSP tour drawn to 'lattice_tsp_tour.png'")

if __name__=="__main__":
    example_tsp_tour()

코드 설명

gt.lattice([10,10]): 10x10 정점을 가진 2차원 격자 그래프 생성 (무방향).
src_vertex = g.vertex(0): 정점 0을 출발·귀환 지점으로 지정.
tour_array = gt.tsp_tour(g, src_vertex): TSP 투어를 근사적으로 구함.
- 반환된 tour_array는 numpy 배열 형태로 순회 순서의 정점 번호가 들어 있음. 맨 끝 원소가 다시 0(시작점).
- worst-case에서 최적해의 최대 2배 길이임을 보장하는 근사해.
만약 엣지에 특정 weight(EdgePropertyMap)가 있다면 weight=some_eprop로 지정 가능.
시각화 파트에서는 투어 간선만 빨간색으로 표시해 이미지 저장.
- e = g.edge(v1, v2)로 해당 엣지를 찾고 color를 "red"로 설정.

3. 요약 및 주의사항

tsp_tour()는 Boost Graph Library의 metric TSP approximate 알고리즘을 활용하며,
- 반드시 g가 무방향이며(undirected), 삼각 부등식을 만족(메트릭)해야 정확히 2-approx 성립.
- 메트릭이 아닌 일반 그래프에서도 호출은 가능하지만, 2배 이내 근사 성립은 이론적으로 보장 안 됨.
매우 큰 그래프(수만~수십만 정점)에서도 비교적 빠르게 수행 가능.
만약 더 정교한 근사 / 휴리스틱 / 최적 알고리즘이 필요하다면, 별도 외부 TSP솔버(예: Concorde)나 다른 고급기법(예: branch-and-cut, Lin–Kernighan 등)을 고려해야 합니다.

끝마무리

본 튜토리얼에서 살펴본 tsp_tour() 함수는 그래프 툴 라이브러리를 활용해 TSP 근사경로를 쉽게 구할 수 있게 해줍니다.
도시(정점) 수가 어느 정도 많더라도 O(E + V log V)로 동작하므로, 도시-교통 빅데이터 분석에서 초기 솔루션으로 활용하기 좋습니다.
필요하다면, 얻은 근사 솔루션을 다른 로컬서치(2-opt, 3-opt)로 추가 개선해볼 수도 있습니다.

(튜토리얼 끝)

아래 튜토리얼은 그래프 이론에서의 그래프 색칠(Graph Coloring) 개념을 체계적으로 살펴보며, 수식과 개념, 원리를 친절하고 정성스럽게 소개하는 내용입니다. 도시와 교통 빅데이터, 그리고 네트워크 분석과도 밀접히 연관되어 있으며, 처음 공부하는 학생도 확실히 이해할 수 있도록 꼼꼼히 설명해볼게요.

1. 그래프 색칠(Graph Coloring) 개요

그래프 색칠이란, 간단히 말해 그래프의 원소(정점, 혹은 간선, 혹은 면)에 대해 특정 ‘색’(또는 레이블)을 할당하되, 일정한 제약조건을 만족하도록 하는 기법을 의미합니다. 예를 들어,

정점 색칠(Vertex Coloring): 그래프의 인접한 정점끼리는 같은 색을 쓰면 안 됨.
간선 색칠(Edge Coloring): 한 정점에서 나가는 간선들끼리는 같은 색을 쓰면 안 됨.
면 색칠(Face Coloring): 평면 그래프로 그렸을 때, 서로 경계를 공유하는 면들은 같은 색을 쓰면 안 됨.

이 중 보통 “그래프 색칠”이라고 하면 ① 번의 정점 색칠을 의미하는 경우가 많습니다.

1.1 역사적 배경 (간략)

1852년경, Francis Guthrie가 영국 지도 색칠 과정에서 ‘어떤 지도를 4가지 색으로 구분 가능하겠다’라는 4색 정리를 추측하며 시작되었습니다.
수십 년 뒤 Kempe가 증명을 시도했지만 오류가 발견되었고, 결국 1976년에 Appel과 Haken이 컴퓨터를 활용해 4색 정리를 증명하면서 큰 이슈가 되었죠.
그 밖에도 여러 수학자들이 그래프 색칠에 관한 문제를 다양한 방식으로 연구해왔습니다.

2. 정점 색칠 (Vertex Coloring)

가장 흔히 다루는 것은 정점 색칠입니다.

정점 집합 (V)와 간선 집합 (E)로 이루어진 무루프(Loop 없음) 그래프 (G=(V,E))에서, 아무 인접 정점(서로 연결된 정점)도 같은 색으로 칠하지 않도록 정점에 색을 매기는 것을 말합니다.
예를 들어, 지도에서 서로 국경을 맞댄 국가가 다른 색이 되어야 하는 것과 유사합니다.

2.1 k-색칠과 색칠 수(Chromatic Number)

k-색칠: 사용 가능한 색이 (k)개뿐이라 가정할 때, 인접 정점끼리 다른 색을 쓰며 색칠이 가능한가를 묻는 것.
색칠 수((\chi(G)), Chromatic Number): 그래프 (G)를 색칠할 때 필요한 최소 색의 개수.
- 예: 삼각형 그래프(정점 3개, 모든 정점이 서로 연결)인 (K_3)는 3가지 색이 필요. (\chi(K_3)=3).
- n차 완전 그래프 (K_n)의 경우 (\chi(K_n)=n).

2.2 성질 (상/하한)

무조건 (\chi(G)\le n) (각 정점마다 다른 색 쓰면 되므로).
완전 그래프나 홀수 사이클 등 특정 경우엔 많은 색(최대 (\Delta(G)+1) or (\Delta(G)) 등)이 필요.
4색 정리: 모든 단순 planar(평면) 그래프는 4색 이내로 색칠 가능 → (\chi(G)\le4).

3. 색칠 다항식 (Chromatic Polynomial)

그래프 (G)에 대해, “(t)가지 색으로 색칠하는 경우의 수”를 세는 함수를 색칠 다항식 (P(G,t))라고 합니다.

예: 어떤 작은 예시 그래프에서 (t=3)일 때 색칠 가능한 경우가 12개, (t=4)일 땐 72개, … 이런 식으로 (t)에 대한 다항식 형태가 됩니다.
(P(G,\chi(G))) = 0 인 지점((\chi(G)) - 1 까지는 0)이 존재하는 등 색칠 가능/불가능을 판별할 수 있는 중요한 도구입니다.

4. 간선 색칠 (Edge Coloring) & 기타 유형

4.1 간선 색칠

같은 정점에서 나가는 간선들이 같은 색이면 안 된다 → 인접 간선(edge-adjacent)은 다른 색.
필요한 색의 최소 개수를 (\chi'(G))라고 함.
예: (K_4)의 경우, (\chi'(K_4)=3), (K_3)의 경우 (\chi'(K_3)=3).
Vizing's Theorem: 임의의 단순 그래프에서 간선 색칠 수 (\chi'(G))는 (\Delta\le\chi'(G)\le \Delta+1).

4.2 총 색칠(Total Coloring)

정점과 간선 모두 “서로 충돌시” 다른 색을 써야 함.

4.3 면 색칠(Face Coloring)

planar 그래프 상에서 면끼리 인접하면 다른 색 → 듀얼 그래프를 만들면 정점 색칠 문제로 볼 수도 있습니다.

4.4 그 밖에

리스트 색칠(List Coloring): 정점마다 허용 색의 리스트가 다를 수 있음.
부분 색칠(Subcoloring), 결함 색칠(Defective Coloring), 등등 변형도 많습니다.

5. 알고리즘과 복잡도

그래프 색칠 문제가 쉽지 않은 이유:

k-색칠 문제가 NP-완전이라는 것은 Karp의 21개 고전 NP-완전 문제 중 하나로 유명합니다.
- 즉, “이 그래프가 k색으로 색칠 가능?” 물으면 일반적으로 다항시간에 풀기 어려움(단, bipartite 여부 판별(2색)은 가능).
정점 수가 작으면, 백트래킹·분기한정(Branch & Bound)·삭제-수축(Deletion–Contraction) 방식으로 완전탐색해볼 수 있지만, 크면 매우 오래 걸립니다.
근사/휴리스틱: Greedy, DSatur, RLF 등 다양한 휴리스틱으로 괜찮은(최적과 근접한) 색칠을 빠르게 구할 수 있습니다.
- Greedy: 정점을 순서대로 가져와, 이미 할당된 이웃색을 제외한 가장 작은 색을 할당. 순서가 품질에 직접 영향.
- DSatur: “포화 차수(saturation degree)”가 가장 큰 정점부터 색칠.
- RLF(Recursive Largest First): 독립집합을 점차 찾아 한 색으로 칠한 뒤 제거 → 이를 반복.

5.1 복잡도 요약

(결정문제) “k-색칠 가능?” : NP-완전 (예외: k=1,2일 땐 선형시간)
(최적화) “(\chi(G))은?”: NP-어려움
근사 알고리즘: (\Delta+1) 정도로는 쉽게 가능하지만, 최적과의 간극을 줄이는 건 매우 어려움.
분산/병렬/고성능 기법도 연구되어, 대규모 데이터(도시·교통망 등)에 대해서는 휴리스틱이 많이 쓰임.

6. 그래프 색칠의 실제 활용

스케줄링: 작업 간 충돌(자원 공유)이 없도록 시간 슬롯을 색이라고 보면, (\chi(G))가 필요한 최소 슬릇 수가 됨.
레지스터 할당(Register allocation): 컴파일러에서 변수 간 충돌(동시에 필요한 변수들)을 피하기 위해 같은 레지스터 못 쓰게 → 충돌 그래프 색칠.
스포츠 리그 편성, 좌석배정, 시험 시간표 등도 비슷한 아이디어로 모델링 가능.
Sudoku도 간접적으로 그래프 색칠 관점으로 볼 수 있음(각 칸을 정점, 행·열·블록 내 충돌).

7. 결론 및 요약

그래프 색칠은 “인접 요소(정점·간선·면)끼리 색이 겹치지 않도록 하는 작업”을 말하며, 수많은 이론적·실무적 활용이 있습니다.
핵심 개념:
- 정점 색칠, 간선 색칠, 면 색칠 등
- 색이 몇 개 필요한지(색칠 수 (\chi) or (\chi'))는 일반적으로 계산이 어렵(NP-어려움).
- 다양한 휴리스틱/근사 알고리즘(Greedy, DSatur, RLF, Lin–Kernighan 유사 접근 등)으로 빠른 근사 솔루션을 얻음.
도시/교통 빅데이터, 네트워크 분석에서는 예: “교통노선 편성 문제, 교차로 신호 주기 결정, 좌표별 레지스터 할당, 주파수 할당…” 등에 그래프 색칠 아이디어를 직간접적으로 적용 가능.

결론적으로, 그래프 색칠은 (1) 이론적 깊이와 (2) 실용적 응용 모두에서 큰 의미를 가지는 주제이며, “어떻게 색칠할 것인가?”와 “최소 색은 몇 개인가?”라는 질문은 NP-완전 문제로서, 대규모 그래프에서는 적절한 휴리스틱 접근이 필수적입니다.

아래 튜토리얼에서는 graph-tool 라이브러리에 내장된 sequential_vertex_coloring 함수를 사용해 그래프의 정점을 순차적으로 색칠하는 방법을 배워봅니다. 도시, 교통 빅데이터를 예로 들어 직관적으로 이해하며, 초보자도 쉽게 따라할 수 있도록 최대한 상세한 한글 설명과 함께 파이썬 코드를 준비했습니다.

1. 개요: Sequential Vertex Coloring(순차 정점 색칠)

정점 색칠(Vertex Coloring) 은 그래프에서 인접한(직접 연결된) 두 정점이 같은 색을 갖지 않도록 색을 할당하는 작업입니다.
- 예: "교차로"를 정점으로, "도로"를 간선으로 보는 교통망 그래프를 생각해보면, 교차로마다 색을 배정하되 인접 교차로(도로로 직접 연결된 교차로)는 다른 색을 써야 하는 상황이 있을 수 있습니다(예: 신호등 스케줄 분배, 혹은 자원할당).

sequential_vertex_coloring 함수는 이름 그대로 그래프의 정점을 정해진 순서대로(Sequential) 하나씩 색칠하면서, 이미 색칠된 이웃 정점들과 겹치지 않는 색을 찾아 할당합니다.

1.1 동작 요약

어떤 순서를 정해서(예: order) 정점들을 한 번씩 방문
각 정점을 방문할 때, 이웃 정점(이미 색칠된)들이 사용한 색을 제외한 '가장 작은 번호'의 색으로 색칠
이 과정을 끝까지 진행하면, 한 가지 정점 색칠 해답(solution)이 산출됨

이 알고리즘은 탐욕적(greedy) 정점 색칠 중 하나로, 주어진 순서에 따라 결과가 달라질 수 있습니다. 최적의 색(최소 색 개수)을 보장하지는 않지만, 구현이 간단하고 빠릅니다.

2. graph-tool의 `sequential_vertex_coloring`

공식 문서에 따르면 함수 시그니처는 아래와 같습니다:

sequential_vertex_coloring(g, order=None, color=None)

g: 그래프 객체 (Graph)
order: (옵션) 정점을 색칠할 순서. VertexPropertyMap 형태.
- 만약 제공되지 않으면, 그래프의 정점 ID(내부적 인덱스) 순서대로 색칠.
color: (옵션) 결과 색 정보를 담을 VertexPropertyMap(int 타입)
- 제공하지 않으면 내부적으로 새로 만들어 반환.

반환: 색 정보를 담은 VertexPropertyMap

2.1 시간 복잡도

문서상 (\mathcal{O}(V \cdot \Delta \cdot C))로 표시됩니다.

(V): 정점 개수
(\Delta): 그래프의 최대 차수(어떤 정점이 가질 수 있는 최대 인접 정점 수)
(C): 실제로 사용된 색상의 총 개수(결과적인 color set의 size)

해석: 각 정점을 색칠할 때, 이미 색칠된 이웃들의 색을 확인(최대 (\Delta)번)하고, 어느 색을 쓸지 결정하는 데 (C) 정도 비교가 가능하기 때문에 (\mathcal{O}(V\Delta C))가 됩니다.

3. 예시: 10x10 Lattice(격자) 그래프 색칠

graph_tool에서 자주 쓰이는 샘플인 lattice(격자) 그래프를 구성해보겠습니다. 10x10 격자는 100개 정점, 그리고 인접성이 높은 구조(각 정점은 상하좌우와 연결)입니다. 간단한 Sequential coloring으로 어떻게 색칠되는지 확인해봅시다.

3.1 코드 예시

import graph_tool.all as gt

def example_sequential_vertex_coloring():
    # 1) 10 x 10 격자(lattice) 그래프 생성
    #    도시/교통 관점: 10개 가로줄과 10개 세로줄이 교차 → 교차점이 정점 → 각 교차점이 상하좌우로 연결된 도로
    g = gt.lattice([10, 10])  # 10x10 Lattice (정점 100개)
    
    # 2) 순차 정점 색칠
    #    order=None → 내부적으로 정점 id 순서(0,1,2,...)로 순회
    colors = gt.sequential_vertex_coloring(g)
    
    # 3) 결과 확인
    # colors.a 는 numpy.ndarray로, 각 정점의 색(정수)이 기록됨
    print("색칠 결과(각 정점별 할당 색):")
    print(colors.a)
    
    # 4) 총 몇 가지 색이 사용되었는지
    used_colors = set(colors.a)
    print("사용된 색의 종류 개수:", len(used_colors))
    
    # 5) 시각화 예시
    #    각 정점의 색상으로 표시해 볼 수 있음 (파이썬 matplotlib 등에 매핑)
    #    graph_tool.graph_draw 함수에서 vertex_fill_color 파라미터로 넘길 수 있다.
    pos = gt.sfdp_layout(g)  # 간단 레이아웃
    gt.graph_draw(g,
                  pos=pos,
                  vertex_fill_color=colors,  # color map
                  vertex_size=8,
                  output_size=(400,400),
                  output="lattice_sequential_coloring.png")

if __name__ == "__main__":
    example_sequential_vertex_coloring()

코드 해설

g = gt.lattice([10, 10])
- graph-tool 내장 함수로 10x10 격자를 생성합니다.
- 총 100개의 정점과 내부적으로 180개 간선(대략)이 생깁니다(테두리 제외한 내측 정점은 상하좌우 4간선).
colors = gt.sequential_vertex_coloring(g)
- 정점 0부터 99까지 순서로 방문하며, 각 정점과 인접한 정점의 색을 피해서 가장 작은 색 번호 할당.
colors.a
- numpy 배열 형태로, 각 index(정점 id)에 대해 색 번호가 저장되어 있습니다.
set(colors.a)
- 실제로 사용된 (중복 없는) 색 번호 목록.
시각화
- vertex_fill_color=colors로 그래프를 그리면 정점별로 다른 색이 적용됨.
- 실제로 색깔을 예쁘게 구분하려면 colormap을 매핑하거나, int → rgba 변환이 필요할 수 있습니다.

실행 결과:

색칠 결과(각 정점별 할당 색):
[0 1 0 1 0 1 ... 1 0 1 0 1 ... ] 
사용된 색의 종류 개수: 2

실제 인접 행렬 구조가 2색으로도 충분한 bipartite 모양이기 때문에, 격자 그래프(짝수 x 짝수)에서는 2가지 색으로 완벽히 색칠이 가능하게 됩니다.

4. 도시/교통 빅데이터 시뮬레이션 예시

만약 “교차로를 정점, 도로를 간선”으로 하는 그래프가 있다고 가정합시다. 신호등 조정이나 교차로별 자원할당(?) 등이 필요할 때, 인접 교차로끼리는 서로 간섭 때문에 다른 ‘채널’을 사용해야 한다고 보면, 정점 색칠이 됩니다.

예를 들어:

import graph_tool.all as gt

def city_traffic_coloring_example():
    g = gt.Graph(directed=False)
    
    # 가상의 교차로(정점) 6개 추가
    vlist = [g.add_vertex() for _ in range(6)]
    
    # 임의의 도로(간선) 연결: 교차로0-1, 1-2, 2-3, 2-4, 3-5, 4-5 등
    edge_list = [(0,1), (1,2), (2,3), (2,4), (3,5), (4,5)]
    for s, t in edge_list:
        g.add_edge(vlist[s], vlist[t])
    
    # sequential_vertex_coloring
    colors = gt.sequential_vertex_coloring(g)
    
    # 결과 출력
    print("교차로별 색상:", colors.a)
    print("사용 색 개수:", len(set(colors.a)))
    
    # 시각화
    pos = gt.sfdp_layout(g)
    gt.graph_draw(g,
                  pos=pos,
                  vertex_text=g.vertex_index,
                  vertex_fill_color=colors,
                  output_size=(300,300),
                  output="city_traffic_coloring.png")

if __name__ == "__main__":
    city_traffic_coloring_example()

이 코드를 실행하면 6개의 교차로가 순서대로 색칠되어, 인접 교차로는 다른 색을 사용하게 됩니다. 순차 색칠이기 때문에, 정점 id가 0,1,2,3,4,5 순이라면 특정 greedy 결과가 나옵니다.

5. 순차 정점 색칠의 장단점

장점
- 구현이 간단, 빠르다.
- 특정 순서를 잘 선정하면(예: DSATUR, Largest First 등), 꽤 괜찮은 솔루션을 얻음.
- 대규모 그래프에서도 빠른 휴리스틱으로 사용 가능.
단점
- 정점 방문 순서에 따라, 쓰는 색 수가 많아질 수도 있음(최적 보장 X).
- (\mathcal{O}(V\Delta C)) 복잡도가긴 하지만, (\Delta)나 (C)가 클 수 있으므로, 그래프가 매우 크면 여전히 계산 부담이 생길 수 있음.

6. 결론

sequential_vertex_coloring 은 간단한 순차(탐욕) 방식으로 정점을 색칠해주는 함수입니다.
인접 정점끼리는 서로 다른 색을 써야 한다는 규칙을 준수하며, 최적 해(최소 색 수)는 보장하지 않지만, 큰 그래프에서 빠르게 근사적인 해를 구할 때 매우 유용합니다.
도시, 교통, 네트워크 분석 등에서 “정점 간 충돌(인접) 시 다른 자원을 할당해야 하는” 상황이 있다면, 이 같은 정점 색칠을 적용해볼 수 있습니다.

이상으로, graph-tool 라이브러리의 sequential_vertex_coloring 함수 사용 예시와 함께, 간단한 튜토리얼을 완성했습니다. 실제 응용 시에는 정점 순서를 어떻게 정하느냐가 색칠 품질에 큰 영향을 미치므로, 필요에 따라 고급 휴리스틱을 도입하면 좋겠습니다.

아래 튜토리얼에서는 graph-tool 라이브러리가 제공하는 find_vertex, find_vertex_range, find_edge, find_edge_range 함수를 다룹니다. 이 함수들은 그래프 내 정점 혹은 간선의 프로퍼티(property) 값을 손쉽게 검색할 수 있는 유틸리티 기능입니다. 도시, 교통 빅데이터와 같은 네트워크 그래프 상황에서 "특정 속성(예: 인구 수, 교차로 혼잡도, 도로 폭 등)"을 만족하는 정점(혹은 간선)을 찾아 필터링하거나, 시각화, 분석에 활용할 때 유용합니다.

1. 기초 개념 및 기능 소개

1.1 `find_vertex(g, prop, match)`

그래프 g에서, 정점 프로퍼티 prop의 값이 match와 정확히 일치하는 정점들을 찾아 리턴합니다.
여기서 prop 은:
- VertexPropertyMap(정점 프로퍼티 맵, 예: 각 정점에 할당된 값)
- 또는 문자열 "in", "out", "total" 중 하나 → 이는 "차수(degree)"를 의미합니다.
  - "in": 들어오는 차수(in-degree)
  - "out": 나가는 차수(out-degree)
  - "total": 총 차수(in+out-degree, 무방향 그래프에서는 out=in=total)

예: find_vertex(g, "out", 3) → 아웃 차수가 3인 정점들 찾기

1.2 `find_vertex_range(g, prop, range)`

그래프 g에서, 정점 프로퍼티 prop의 값이 range[0] <= prop[v] <= range[1] 범위에 있는 정점들을 리턴합니다.
prop은 위와 동일하게 VertexPropertyMap 이거나 "in", "out", "total" 차수를 의미할 수 있습니다.
range 는 [lower_bound, upper_bound] 형태의 길이 2짜리 튜플/리스트

예: find_vertex_range(g, "in", [2, 5]) → 인 차수가 2 이상, 5 이하인 정점들 찾기

1.3 `find_edge(g, prop, match)`

그래프 g에서, 간선 프로퍼티 prop의 값이 match와 정확히 일치하는 간선들을 찾아 리턴합니다.
prop은 반드시 EdgePropertyMap이어야 합니다. (문자열 "in", "out" 등은 사용 불가)
예: find_edge(g, capacity_prop, 10) → 간선 "용량(capacity)"이 10인 간선만 필터

1.4 `find_edge_range(g, prop, range)`

그래프 g에서, 간선 프로퍼티 prop의 값이 range[0] <= prop[e] <= range[1] 범위에 있는 간선들을 리턴합니다.
prop은 EdgePropertyMap만 가능
예: find_edge_range(g, weight_prop, [5, 10]) → 간선 가중치(weight)가 5~10 사이인 간선들 찾기

2. 실전 예제 튜토리얼

2.1 예제 그래프 만들기

아래 예시에서는 정점 수 6개, 간선 수 7개인 무방향 그래프를 만들고, 정점/간선 프로퍼티를 간단히 설정하여 find_vertex*, find_edge* 함수를 실습해 봅니다.

import graph_tool.all as gt
import numpy as np

def example_find_vertex_and_edge():
    # 1) 그래프 생성(무방향)
    g = gt.Graph(directed=False)
    
    # 2) 정점 6개 추가
    vlist = [g.add_vertex() for _ in range(6)]  # vlist[0] ~ vlist[5]
    
    # 3) 간선 구성: 예: 0-1, 1-2, 2-3, 2-4, 3-5, 4-5, 0-2
    edge_list = [(0,1), (1,2), (2,3), (2,4), (3,5), (4,5), (0,2)]
    for s, t in edge_list:
        g.add_edge(vlist[s], vlist[t])
    
    # 4) 정점 프로퍼티 생성: "value"라는 int타입
    #    (도시/교통 예시: 교차로 혼잡도/신호강도 등)
    vprop = g.new_vertex_property("int")
    
    # 임의로 값 넣어보기 (0~9 사이 난수)
    for v in g.vertices():
        vprop[v] = np.random.randint(0, 10)
    
    # 5) 간선 프로퍼티 생성: "weight"라는 float타입
    #    (도시/교통 예시: 도로 길이, 비용 등)
    eprop = g.new_edge_property("float")
    
    for e in g.edges():
        eprop[e] = np.random.uniform(1.0, 20.0)  # 1.0~20.0 사이 실수
    
    # 6) 정점 색인 출력
    print("[Vertex indices]:", [int(v) for v in g.vertices()])
    #    정점 프로퍼티 값 출력
    print("[Vertex values (vprop)]:", [vprop[v] for v in g.vertices()])
    #    간선 프로퍼티 값 출력
    for e in g.edges():
        print(f"Edge ({int(e.source())}-{int(e.target())}), weight={eprop[e]:.2f}")
    
    # === 예시 1: find_vertex ===
    # "vprop[v] == match" -> match=5인 정점 찾기
    match_val = 5
    found_v = gt.find_vertex(g, vprop, match_val)
    print(f"\n[vprop == {match_val}] -> 정점 목록:", [int(x) for x in found_v])
    
    # === 예시 2: find_vertex_range ===
    # "1 <= vprop[v] <= 4" 인 정점 찾기
    found_v_range = gt.find_vertex_range(g, vprop, [1, 4])
    print(f"[1 <= vprop <= 4] -> 정점 목록:", [int(x) for x in found_v_range])
    
    # === 예시 3: find_edge ===
    # "weight == match"는 float이므로 정확히 일치시키기 어렵지만,
    # 여기서는 임의로 'weight==some_value'를 예시로
    # -> test_value와 거의 같은(절대 오차 0.001 이하) 간선 수동 필터
    #   (여기서는 그냥 예시이므로, 매칭되는 게 없을 수도..)
    test_value = 10.0
    # EdgePropertyMap은 float이므로, find_edge 내부로는 '정확히 일치'를 집어넣으면 잘 안 맞을 가능성↑
    # -> 간단 예시에선 pass (또는 근사 비교를 위해 별도 수동 filter)
    
    # === 예시 4: find_edge_range ===
    # "weight 5.0 ~ 10.0" 사이의 간선
    low, high = 5.0, 10.0
    found_e_range = gt.find_edge_range(g, eprop, [low, high])
    print(f"\n[{low:.1f} <= weight <= {high:.1f}] 인 간선 목록:")
    for e in found_e_range:
        print(f"   Edge ({int(e.source())}-{int(e.target())}), weight={eprop[e]:.2f}")
    
    # === 예시 5: "in", "out", "total" 사용해보기 ===
    # 무방향 그래프에서는 "in"=="out"=="total" 차수가 같음
    # out-degree==2 인 정점
    out2_vertices = gt.find_vertex(g, "out", 2)
    print(f"\nout-degree==2 인 정점 목록:", [int(v) for v in out2_vertices])
    
    # total-degree 범위 [2, 3]
    deg_range_vertices = gt.find_vertex_range(g, "total", [2, 3])
    print("total-degree가 2~3 인 정점 목록:", [int(v) for v in deg_range_vertices])

if __name__ == "__main__":
    example_find_vertex_and_edge()

2.2 코드 설명

그래프 및 정점/간선 생성
- 6개의 정점을 vlist에 저장
- 7개의 간선을 연결 (edge_list)
정점 프로퍼티(vprop), 간선 프로퍼티(eprop)
- vprop (int형): 무작위 0~9 정수
- eprop (float형): 무작위 1.0~20.0 실수
find_vertex(g, vprop, match_val)
- vprop[v] == match_val인 정점들 찾음
find_vertex_range(g, vprop, [1,4])
- 1 <= vprop[v] <= 4 범위에 해당하는 정점 찾음
find_edge_range(g, eprop, [5.0, 10.0])
- 5.0 <= eprop[e] <= 10.0 범위에 해당하는 간선 목록
문자열 "in", "out", "total"
- 정점의 차수를 직접 프로퍼티로 간주해서 검색
- 무방향 그래프에서 in==out==total이므로, 예제에서는 동일
- 예: gt.find_vertex(g, "out", 2) → 아웃 차수가 2인 정점
- 예: gt.find_vertex_range(g, "total", [2,3]) → 전체 차수가 2~3 사이인 정점

실행하면, 무작위 프로퍼티로 인해 매번 결과는 다르지만, 다음과 같은 콘솔 로그 형태가 나옵니다:

[Vertex indices]: [0, 1, 2, 3, 4, 5]
[Vertex values (vprop)]: [7, 3, 7, 9, 0, 4]
Edge (0-1), weight=12.35
Edge (1-2), weight=5.37
Edge (2-3), weight=19.58
Edge (2-4), weight=7.61
Edge (3-5), weight=4.99
Edge (4-5), weight=10.82
Edge (0-2), weight=8.13

[vprop == 5] -> 정점 목록: []

[1 <= vprop <= 4] -> 정점 목록: [1, 5]

[5.0 <= weight <= 10.0] 인 간선 목록:
   Edge (1-2), weight=5.37
   Edge (2-4), weight=7.61
   Edge (0-2), weight=8.13

out-degree==2 인 정점 목록: [0, 3]

total-degree가 2~3 인 정점 목록: [0, 1, 3, 4, 5]

(이는 예시일 뿐, 매번 난수에 따라 다릅니다.)

3. 도시/교통 빅데이터 활용 아이디어

교차로 속성 기반 필터
- 교차로(정점)에 "혼잡도" 프로퍼티를 부여 후, find_vertex_range(g, congest_prop, [50,100]) → 혼잡도 50~100인 교차로만 모아서 시각화, 혹은 우선적 처리(예: 방범 카메라 배치)
도로 속성 기반 필터
- 도로(간선)에 "교통량" 프로퍼티 부여 후, find_edge_range(g, traffic_prop, [0, 500]) → 교통량 500 이하인 도로 = 비교적 한적한 경로
차수(degree) 기반
- 교차로별 연결 차수가 특정 범위에 있으면 대형 교차로일 가능성(차수 높음), 혹은 외곽 지역(차수 낮음) 등으로 분류

4. 정리

graph_tool.util의 find_vertex, find_vertex_range, find_edge, find_edge_range 함수들은 그래프에서 특정 프로퍼티값(혹은 차수)와 정확히 일치하거나 범위에 들어가는 정점/간선을 빠르게 필터링할 수 있게 해줍니다.

도시/교통 빅데이터(그래프 구조) 분석 시, "속성으로 정점/간선을 골라내고, 그 서브셋만 집중 분석/시각화" 할 때 굉장히 편리합니다.

정점 프로퍼티인지, 간선 프로퍼티인지에 따라 find_vertex* vs find_edge* 사용
범위 검색을 하면 *_range
차수(in/out/total)를 단순히 검색하려면, prop 자리에 "in", "out", "total" 활용

실무에서도 이 방법들을 응용하여, 대규모 그래프에서 특정 조건을 만족하는 노드·링크만을 추출해 보고서를 작성하거나, 추가 분석, 시각화 시에 필터링 작업을 용이하게 해줄 것입니다.

이상으로 graph_tool.util의 핵심 유틸 함수들에 대한 초보자용 튜토리얼을 마칩니다.

Sylen

AI가 재밌는 걸

이전 포스트

graph_tool.topology 6

1. is_bipartite() 함수: 그래프가 이분그래프인지 판별

1.1 이분그래프(bipartite graph)란?

왜 중요한가?

1.2 is_bipartite(g, partition=False, find_odd_cycle=False)

리턴값

복잡도

1.3 사용 예시 (코드)

코드 설명

1.4 홀수 사이클 찾기

2. is_DAG() 함수: 유향 그래프가 DAG(방향성 비순환 그래프)인지 판별

2.1 DAG(directed acyclic graph)란?

2.2 is_DAG(g)

리턴값

복잡도

2.3 사용 예시 (코드)

설명

3. 요약

1. 문제배경: 평면 그래프와 Planarity Testing

2. 알고리즘 개요: Edge Addition

2.1 Biconnected Component (이중 연결 요소)와 Merge

2.2 외부얼굴(External Face) 유지와 Flip

2.3 Walkup & Walkdown

2.4 Non-planar 시 Kuratowski Subgraph 찾기

3. 데이터 구조와 운영

3.1 G̃ (임베딩 유지 구조)

3.2 Edge Addition Process

3.3 Complexity (O(n))

4. Kuratowski Subgraph (Non-planar 시)

5. 실제 파이썬에서의 graph-tool 사용 맥락

5.1 graph-tool은?

5.2 기존 함수와의 연관

6. 정리 및 의의

7. (부록) 파이썬 Pseudocode 예시

7.1 Walkup & Walkdown

7.2 Flip과 Merge

7.3 Non-planar 시 Kuratowski subgraph 찾기

8. 결론

학습/연구 관점

1. 들어가기

2. is_planar() 함수: 그래프 평면성 검사

2.1 함수 시그니처 및 파라미터

반환값

2.2 Boyer–Myrvold 알고리즘 개요

2.3 예시 코드

2.3.1 Kuratowski subgraph 예시

3. make_maximal_planar() 함수: 최대 평면 그래프 만들기

3.1 개념: 최대 평면 그래프

3.2 시그니처

3.3 예시 코드

4. 정리

5. 추가 학습 링크

1. 문제 배경과 Motivation

2. 주요 목표: Arbitrary Degree Sequences에서 Reciprocity의 기대값

2.1. 기본 식

2.2. 부분 상관관계를 고려할 때

3. 요약: 어떤 네트워크에 이론 값을 적용하나?

4. 예시 코드를 통한 사용법 (그래프 툴 연계)

4.1 그래프에서 degree 정보 추출

4.2 노드 차수 빈도 N(k)와 링크 상관 L(k->q) 계산

4.3 예: 전체 상관(1node+2node) 시 reciprocity 이론값 계산

4.4 부분 상관만 고려하는 reciprocity 계산도 가능

결론 정리

참고 수식/개념 요약

파이썬 튜토리얼 예시 (정성스럽게)

요약

1. 개념 정리: Edge Reciprocity(호혜성)이란?

1.1 호혜성(Reciprocity)의 정의

1.2 가중치(Weights)가 있는 경우

2. 함수 사용 방법

2.1 간단 예시

실행 결과

2.2 임의 그래프/가중치 그래프 활용

3. 내부 동작 및 복잡도

4. 실제 예시: PGP 네트워크(인용)

5. 요약 & 주의사항

결론

1. 여행하는 외판원 문제(TSP)란?

1.1. 왜 중요한가?

2. 수학적·이론적 배경

1. `is_bipartite()` 함수: 그래프가 이분그래프인지 판별

1.2 `is_bipartite(g, partition=False, find_odd_cycle=False)`

2. `is_DAG()` 함수: 유향 그래프가 DAG(방향성 비순환 그래프)인지 판별

2.2 `is_DAG(g)`

2. `is_planar()` 함수: 그래프 평면성 검사

3. `make_maximal_planar()` 함수: 최대 평면 그래프 만들기

4.2 노드 차수 빈도 `N(k)`와 링크 상관 `L(k->q)` 계산

1. `tsp_tour()` 함수 개요

2. 예제 코드: `tsp_tour` 간단 사용법

2. graph-tool의 `sequential_vertex_coloring`

1.1 `find_vertex(g, prop, match)`

1.2 `find_vertex_range(g, prop, range)`

1.3 `find_edge(g, prop, match)`

1.4 `find_edge_range(g, prop, range)`