Graph-tool 11

Sylen·2025년 1월 4일

아래 튜토리얼은 graph_tool.generation 모듈에 포함된 여러 가지 그래프 변환 및 단순화 함수들을 하나씩 살펴보는 과정을 상세히 보여줍니다.

predecessor_tree: 선행자(predecessor) 정보로부터 트리를 생성
line_graph: 라인 그래프(line graph) 생성
condensation_graph: 주어진 파티션(예: 커뮤니티) 정보를 바탕으로 “축약 그래프” 생성
contract_parallel_edges / expand_parallel_edges / remove_parallel_edges / label_parallel_edges: 중복 간선(멀티에지) 처리
remove_self_loops / label_self_loops: 자기루프 처리

아래 코드는 초보자를 대상으로 “파이썬 graph-tool 라이브러리를 어떻게 활용하면 되는지”를 예제로 보여주며, 모든 함수의 사용법과 의의를 간략 설명하고, 간단한 파이썬 예시 코드와 자세한 한글 주석을 포함합니다.

1. `predecessor_tree(g, pred_map)`

1.1. 개념 및 기능

predecessor_tree 함수는, 그래프에서 특정 알고리즘(예: BFS/DFS, 최단경로 등)을 실행한 뒤 생성된 pred_map(각 노드에 대해 “이전 노드”를 가리키는 정보)을 바탕으로, 트리 구조만 뽑아내어 별도의 Graph 객체로 만들어줍니다.

1.2. 파이썬 코드 예시

import graph_tool.all as gt

def example_predecessor_tree():
    # 1) 예시 그래프 준비
    g = gt.Graph(directed=False)
    vlist = [g.add_vertex() for _ in range(6)]
    edges = [(0,1),(1,2),(2,3),(2,4),(1,5)]
    for s,t in edges:
        g.add_edge(vlist[s], vlist[t])
    # => 무방향 그래프이므로 (0-1,1-2,2-3,2-4,1-5) 구조

    # 2) BFS 수행 예시
    #    - BFS 결과, predecessor(이전노드) 정보 획득
    pred = g.new_vertex_property("int64_t")
    dist = gt.shortest_distance(g, source=vlist[0], pred_map=pred)
    # dist, pred = BFS의 거리 및 predecessor

    # 3) predecessor_tree 생성
    tree_g = gt.predecessor_tree(g, pred)

    print("Original graph edges:", list(g.edges()))
    print("Tree edges:", list(tree_g.edges()))

    # 4) 시각화(단순 예시)
    #    - pos는 임의로 배치
    pos_orig = gt.arf_layout(g)  # (다른 레이아웃 사용 가능)
    pos_tree = gt.arf_layout(tree_g)

    #    - 실제 그림을 그리는 예시
    gt.graph_draw(g, pos=pos_orig, output_size=(300,300), output="original_graph.pdf")
    gt.graph_draw(tree_g, pos=pos_tree, output_size=(300,300), output="tree_from_pred.pdf")

if __name__=="__main__":
    example_predecessor_tree()

1.3. 설명

shortest_distance(..., pred_map=pred) 등으로 구한 pred (각 노드별로 어디서 왔는지 알려주는 predecessor) 정보를 이용해 predecessor_tree(g, pred_map) 호출.
반환된 tree_g는 동일한 노드 수를 가지며, 간선은 pred_map이 가리키는 구조만 남긴 트리가 된다.

2. `line_graph(g)`

2.1. 개념 및 기능

라인 그래프(line graph)는 원래 그래프의 “간선”을 새 그래프의 “노드”로 삼는다.
원래 그래프에서 간선끼리 인접(두 간선이 어떤 노드를 공유)하면, 라인 그래프에서는 그 두 노드(=원래 간선)가 연결되는 형태.

2.2. 파이썬 코드 예시

import graph_tool.all as gt

def example_line_graph():
    # 1) 예시 그래프 준비 (무방향)
    g = gt.collection.data["lesmis"]  # Les Miserables 예시
    print("Original G: #V={}, #E={}".format(g.num_vertices(), g.num_edges()))

    # 2) line_graph 생성
    lg, vmap = gt.line_graph(g)
    # lg: 라인 그래프
    # vmap: lg의 각 노드가 g의 어느 edge에 해당하는지 매핑정보

    print("Line Graph LG: #V={}, #E={}".format(lg.num_vertices(), lg.num_edges()))

    # 3) 시각화
    pos_lg = gt.arf_layout(lg)
    gt.graph_draw(lg, pos=pos_lg, output_size=(400,400),
                  output="lesmis_line_graph.pdf")

    # vmap 사용 예시: 라인그래프의 한 노드(ln)에 대해, 원래 그래프의 간선을 찾는다
    # for ln in lg.vertices():
    #    orig_edge = vmap[ln]  # (원래 그래프에서의 EdgeDescriptor)
    #    print("line_graph node:", ln, "corresponds to edge:", orig_edge)

if __name__=="__main__":
    example_line_graph()

2.3. 설명

반환값 lg, vmap에서 lg는 라인 그래프, vmap은 “이 라인 그래프의 노드가 원 그래프의 어느 edge에 해당하는지”를 알려주는 매핑.
무방향 그래프: “두 간선이 어떤 노드를 공유하면 -> 라인 그래프에서 연결”
유향 그래프: “두 간선 e1:u->v, e2:w->x 에서, v=w 이면 라인 그래프에서 e1->e2 연결(방향성)”

3. `condensation_graph(g, prop, ...)`

3.1. 개념 및 기능

각 노드가 어떤 그룹(=커뮤니티, 블록, 파티션 등)에 속하는지(prop)가 주어졌을 때, 그룹별로 노드를 합쳐(축약) 하나의 “집단 노드”로 만들고, 집단끼리의 연결(원래 그래프에서 cross edges)을 새 간선으로 하는 축약 그래프(Condensation Graph)를 만들어준다.
예: SB(스토캐스틱 블록모델)로 커뮤니티를 찾은 뒤, 그룹별로 압축한 “커뮤니티 간 네트워크”를 구할 수 있음.

3.2. 파이썬 코드 예시

import graph_tool.all as gt
import numpy as np

def example_condensation_graph():
    # 1) 예시 그래프
    g = gt.collection.data["polbooks"]  # 정치 관련 서적 co-purchase network
    print("Original Graph: V={}, E={}".format(g.num_vertices(), g.num_edges()))

    # 2) 임의로 블록(그룹) 할당 or SB 추정
    # 여기서는 간단히 무작위 partition
    # 실제론 SB를 fitting해서 get_blocks() 할 것
    b_prop = g.new_vertex_property("int")
    for v in g.vertices():
        b_prop[v] = np.random.randint(0, 3)  # 0,1,2 중 하나

    # 3) condensation_graph 호출
    #    - communities=prop
    #    - self_loops, parallel_edges 등 상황에 맞게
    cg, bb, vcount, ecount, avp, aep = gt.condensation_graph(
        g, b_prop,
        self_loops=True,
        parallel_edges=False
    )

    print("Condensed Graph: V={}, E={}".format(cg.num_vertices(), cg.num_edges()))
    # bb : cond. graph의 각 노드 -> 원래 그룹 ID
    # vcount : condensed node별로 원래 그래프에서 몇 개 노드가 모였는지
    # ecount : condensed edge별로 원래 그래프에서 몇 개 간선이 모였는지

    # 4) 시각화(단순히 ...)
    pos_cg = gt.sfdp_layout(cg)  # 축약그래프 레이아웃
    gt.graph_draw(cg, pos=pos_cg,
                  vertex_text=vcount, vertex_font_size=14,
                  edge_pen_width=gt.prop_to_size(ecount, mi=1, ma=5),
                  output_size=(400,400), output="condensation_example.pdf")

if __name__=="__main__":
    example_condensation_graph()

3.3. 설명

condensation_graph의 인수
- prop: 정수형/또는 해시형 vertex property. 같은 값을 가지는 노드들은 한 그룹으로 압축됨.
- vweight, eweight: 노드/에지 가중치(합산할 때)
- avprops, aeprops: “추가로 어떤 노드/에지 프로퍼티도 그룹 단위로 합산할지” 지정
- self_loops, parallel_edges: 동일 그룹 간 연결을 어떻게 처리할지
반환값:
- condensation_graph,
- bb: condensation_graph의 각 노드가 (원래 어떤 그룹)인지,
- vcount, ecount: 그룹 내 노드/에지 합산 카운트
- avp, aep: 추가로 합산된 property들.

4. 중복 간선(Parallel edges) 및 자기루프(Self loops) 처리

4.1. `contract_parallel_edges(g, weight=None)` 와 `expand_parallel_edges(g, weight)`

contract: 병합(여러 개 평행간선을 1개로)
- weight[e]가 있을 경우, 병합시 “가중치=합산”으로 처리
expand: edge multiplicities를 실제 다중간선으로 다시 펼침.

예시 코드

import graph_tool.all as gt

def example_parallel_edges():
    g = gt.Graph(directed=False)
    # (a) 임의로 병렬 간선을 몇 개 추가
    v1 = g.add_vertex()
    v2 = g.add_vertex()
    e1 = g.add_edge(v1,v2)
    e2 = g.add_edge(v1,v2)
    e3 = g.add_edge(v2,v1) # same undirected edge, but as edge object

    print("Before contract, #edges =", g.num_edges())  # 3

    # (b) contract
    weight_map = gt.contract_parallel_edges(g)
    print("After contract, #edges =", g.num_edges())  # 1
    print("Edge weight:", weight_map[g.edge(v1,v2)])  # 3

    # (c) expand 다시
    gt.expand_parallel_edges(g, weight_map)
    print("After expand, #edges =", g.num_edges())    # 3

if __name__=="__main__":
    example_parallel_edges()

4.2. `remove_parallel_edges(g)`

평행간선이 존재하면, 동일 소스-타겟을 가지는 간선 중 하나만 남기고 나머지는 제거.

4.3. `label_parallel_edges(g, mark_only=False, eprop=None)`

평행간선을 라벨링하는 함수.
- mark_only=True -> 평행간선은 1, 아닌 건 0
- mark_only=False -> 동일 parallel edge set에서 0..k 순으로 라벨링

4.4. `remove_self_loops(g)` / `label_self_loops(...)`

“자기루프”를 제거/라벨링.

자기루프 제거 예시

import graph_tool.all as gt

def example_self_loops():
    g = gt.Graph()
    v1 = g.add_vertex()
    v2 = g.add_vertex()
    e1 = g.add_edge(v1, v1)  # self-loop
    e2 = g.add_edge(v1, v2)
    print("Edges before remove:", list(g.edges()))
    gt.remove_self_loops(g)
    print("Edges after remove:", list(g.edges()))

정리

predecessor_tree: BFS/DFS/최단경로 결과로부터 트리만 추출
line_graph: 간선을 노드로, 간선-간선 인접성으로 구성된 그래프
condensation_graph: 노드를 그룹화하여 압축 그래프 생성
parallel edges(병렬간선) & self-loops 처리
- contract_parallel_edges, expand_parallel_edges, remove_parallel_edges, label_parallel_edges
- remove_self_loops, label_self_loops

이들은 그래프 구조를 단순화하거나, 파티션을 이용해 “집약/축약”하거나, 간선/노드 정보를 재구성하는 과정에서 유용합니다. 각 함수를 적절히 조합해서 복잡한 네트워크를 다루는 전처리, 시각화 단순화, 분석용 그래프 변환 등에 활용할 수 있습니다.

아래 튜토리얼은 graph_tool.generation 모듈에 포함된 그래프 생성, 결합, 구조적 패턴을 만드는 여러 가지 함수를 하나씩 살펴보고, 각 함수를 어떻게 활용할 수 있는지에 대한 개념적 설명과 함께 초보자도 쉽게 따라할 수 있는 예시 코드를 안내합니다. 각 코드 스니펫에는 자세한 한글 주석을 포함하여, 단계별로 무슨 일이 일어나는지, 어떤 옵션과 결과물이 존재하는지 정성껏 풀어내고자 합니다.

목표

graph_union: 두 그래프를 합쳐서 하나의 그래프로 만드는 방법
lattice: ( N )-차원 정사각 격자(lattice) 그래프 생성
complete_graph: 완전 그래프 생성
circular_graph: 원형(고리) 형태의 그래프 생성

(기본 전제: import graph_tool.all as gt 및 import numpy as np 등이 선행되어 있어야 합니다.)

1. `graph_union(g1, g2, ...)`

1.1. 개념 및 기능

graph_union 함수는 두 개의 그래프 (g1, g2)를 합쳐서, 하나의 그래프로 만들어주는 역할을 합니다.
합집합(union)이라 해서, 두 그래프에 겹치는 정점·간선이 있을 때는 중복 없이 하나로 처리되거나, 특정 옵션에 따라 중복이 유지될 수 있습니다.
기본 동작 모드는 “정점 번호가 전혀 무관한 별개의 그래프 두 개를 합치는” 것으로 이해할 수 있습니다.
- 만약 실제로 ‘동일 정점’을 명시적으로 매핑하고 싶다면, intersection 옵션(정수값 -1이 아닌 경우 등)을 통해 제어할 수 있습니다.
props 파라미터로, 그래프들이 가진 PropertyMap(예: 노드 색깔, 간선 가중치 등)을 새로운 그래프에 어떻게 복사할지(전달할지) 지정할 수 있습니다.
include=True 옵션을 주면, g2 그래프가 g1 속으로 직접 삽입(in-place)되어 g1이 수정되는 방식이고, 기본값 False라면 새로운 그래프를 만들어서 반환합니다.

1.2. 간단 예제

아래는 두 개의 그래프 (g1, g2)를 생성 후, graph_union을 이용해 합쳐본 코드 예시입니다.

import graph_tool.all as gt

def demo_graph_union():
    # (1) g1: 5개의 노드, 완전 그래프
    g1 = gt.complete_graph(N=5, self_loops=False, directed=False)
    # (2) g2: 4개의 노드를 가진 원형 그래프 (k=1, 즉 이웃 한 개씩만 연결)
    g2 = gt.circular_graph(N=4, k=1, self_loops=False, directed=False)

    print("Before union:")
    print(" g1 -> vertices:", g1.num_vertices(), " edges:", g1.num_edges())
    print(" g2 -> vertices:", g2.num_vertices(), " edges:", g2.num_edges())

    # (3) graph_union: g1, g2를 합쳐서 새 그래프 u를 만든다.
    #    include=False이므로, g1과 g2는 그대로이고 새로운 그래프 u가 생성됨.
    u = gt.graph_union(g1, g2, intersection=None, include=False)

    print("After union (u):")
    print(" u -> vertices:", u.num_vertices(), " edges:", u.num_edges())

    # 시각화 해보기 (단순한 layout)
    pos = gt.arf_layout(u)
    gt.graph_draw(u, pos=pos, output="demo_graph_union.pdf")
    print(" - Union graph has been drawn to 'demo_graph_union.pdf'")

if __name__ == "__main__":
    demo_graph_union()

1.2.1. 주요 포인트

gt.complete_graph(N=5) : 5개 노드로 이루어진 완전 그래프 (간선 수=10).
gt.circular_graph(N=4, k=1) : 4개 노드로 이루어진 원형 그래프, 각 노드는 이웃 2개와 연결(간선 수=4).
두 그래프가 서로 독립적으로 만들어졌으므로, union 후에는 총 노드 9개, 간선 14개가 예상(겹치는 정점·간선이 없으므로 단순 합).
실제 레이아웃은 gt.sfdp_layout 혹은 gt.arf_layout 등으로 잡을 수 있음.

2. `lattice(shape, periodic=False)`

2.1. 개념 및 기능

lattice 함수는 (N)-차원 정사각 격자를 쉽게 만들어줍니다.
- 예: shape=[10,10] → 2D 격자(10x10).
- 예: shape=[10,20,5] → 3D 격자(10x20x5).
periodic=True로 설정하면, 가장자리와 가장자리끼리 연결되는 토러스(torus) 구조가 됩니다. (2D일 경우, 아래·위 / 왼쪽·오른쪽이 연결)

2.2. 간단 예제

import graph_tool.all as gt

def demo_lattice():
    # (1) 2D 격자 (10x10)
    g_2d = gt.lattice([10, 10], periodic=False)
    print("2D lattice (10x10):",
          "Vertices:", g_2d.num_vertices(),
          "Edges:", g_2d.num_edges())
    
    # (2) 3D 격자 (4x5x6)
    g_3d = gt.lattice([4, 5, 6], periodic=True)  # 주의: periodic=True
    print("3D lattice (4x5x6) with periodic boundaries:",
          "Vertices:", g_3d.num_vertices(),
          "Edges:", g_3d.num_edges())

    # (3) 시각화(예: 2D 격자) - 3D는 2D에 투영해서 그릴 수 있음
    pos_2d = gt.sfdp_layout(g_2d)
    gt.graph_draw(g_2d, pos=pos_2d, output="demo_lattice_2d.pdf")
    print(" - 2D lattice drawn to 'demo_lattice_2d.pdf'")

if __name__=="__main__":
    demo_lattice()

2.2.1. 주요 포인트

2D lattice(10x10)에서 노드 수는 100, 간선 수는 (10(10-1))2=180 (가로 90+ 세로 90).
3D lattice(4x5x6)에서 노드 수는 456=120, periodic=true로 테두리가 서로 연결되어 간선수는 좀 더 증가.
pos_2d = gt.sfdp_layout(...) 등으로 일단 2차원 평면에 배치 가능.

3. `complete_graph(N, self_loops=False, directed=False)`

3.1. 개념 및 기능

complete_graph 함수는 이름 그대로, (N)개의 모든 정점이 서로 연결된 완전 그래프(complete graph)를 생성해 줍니다.
self_loops=True로 하면 자기루프도 포함됩니다.
directed=True면 방향 그래프를 만들며, 이때는 (N(N-1))개의 간선이 생김(무방향일 땐 (N(N-1)/2)).

3.2. 간단 예제

import graph_tool.all as gt

def demo_complete_graph():
    # (1) N=7, 무방향, 자기루프 없음
    g = gt.complete_graph(N=7, self_loops=False, directed=False)
    print("Complete graph N=7:",
          "Vertices:", g.num_vertices(),
          "Edges:", g.num_edges())
    # 7개 노드, 7*(6)/2 = 21개의 간선

    # (2) 시각화
    pos = gt.sfdp_layout(g)  # force-directed layout
    gt.graph_draw(g, pos=pos, output="demo_complete_graph.pdf")
    print(" - complete_graph(7) drawn to 'demo_complete_graph.pdf'")

if __name__=="__main__":
    demo_complete_graph()

4. `circular_graph(N, k=1, self_loops=False, directed=False)`

4.1. 개념 및 기능

circular_graph는 (N)개의 노드를 원형(ring) 형태로 배치하고, 각 노드가 양옆 k개 노드와 연결되도록 함.
- 예: k=1이면, 각 노드는 양 옆 노드 1개씩 연결 → 즉 2-regular cycle.
- 예: k=2이면, 원형에서 양쪽 두 칸 떨어진 노드까지 연결함.
directed=True라면, 한 방향(예: 시계방향)으로만 간선을 잇는 식.

4.2. 간단 예제

import graph_tool.all as gt

def demo_circular_graph():
    # (1) N=8, k=2: 원형에서 이웃 2개씩 연결(즉 좌우 각각 2칸 떨어진 노드와 연결)
    g = gt.circular_graph(N=8, k=2, self_loops=False, directed=False)
    print("Circular graph N=8, k=2:",
          "Vertices:", g.num_vertices(),
          "Edges:", g.num_edges())
    # k=2 => (8 * 2) / 2 = 8개의 간선(?)
    # 실제로는 인접 간선이 좀 더 많으니 결과치 확인

    # (2) 시각화
    pos = gt.circular_layout(g)
    gt.graph_draw(g, pos=pos, output="demo_circular_graph.pdf")
    print(" - circular_graph(8,k=2) drawn to 'demo_circular_graph.pdf'")

if __name__=="__main__":
    demo_circular_graph()

(참고: circular_layout은 노드를 원형으로 배치하기에 딱 좋은 layout 함수.)

마무리

위에서 소개한 graph_tool.generation 모듈의 함수들은, 분산처리/빅데이터 환경에서도 기본 그래프를 생성·결합할 때 매우 유용합니다.

graph_union: 여러 그래프를 단계적으로 합쳐 거대한 그래프를 구성할 수 있음.
lattice: 격자 기반 모델(도시 블록 시뮬레이션, 물리학 Ising 모델, 교통 네트워크 시뮬레이션 등)에 활용.
complete_graph: 완전 연결망 가정 실험용(테스트/비교).
circular_graph: 1차원 고리형, 근접 연결망 테스트용.

각 함수는 내부적으로도 빠르게 동작하며, graph-tool의 강력한 속도와 효율을 유지합니다. 위 코드를 실행하면, 간단한 toy 예시들이 시각화 결과물(PDF, PNG 등)로 확인 가능하니, 단계별로 실험해 보고 원하는 형태의 그래프를 만드는 데 참고해 보세요.

Sylen

AI가 재밌는 걸

이전 포스트

Graph-tool 10

다음 포스트

Graph-tool 11

1. `predecessor_tree(g, pred_map)`

1.1. 개념 및 기능

1.2. 파이썬 코드 예시

1.3. 설명

2. `line_graph(g)`

2.1. 개념 및 기능

2.2. 파이썬 코드 예시

2.3. 설명

3. `condensation_graph(g, prop, ...)`

3.1. 개념 및 기능

3.2. 파이썬 코드 예시

3.3. 설명

4. 중복 간선(Parallel edges) 및 자기루프(Self loops) 처리

4.1. `contract_parallel_edges(g, weight=None)` 와 `expand_parallel_edges(g, weight)`

예시 코드

4.2. `remove_parallel_edges(g)`

4.3. `label_parallel_edges(g, mark_only=False, eprop=None)`

4.4. `remove_self_loops(g)` / `label_self_loops(...)`

자기루프 제거 예시

정리

1. `graph_union(g1, g2, ...)`

1.1. 개념 및 기능

1.2. 간단 예제

1.2.1. 주요 포인트

2. `lattice(shape, periodic=False)`

2.1. 개념 및 기능

2.2. 간단 예제

2.2.1. 주요 포인트

3. `complete_graph(N, self_loops=False, directed=False)`

3.1. 개념 및 기능

3.2. 간단 예제

4. `circular_graph(N, k=1, self_loops=False, directed=False)`

4.1. 개념 및 기능

4.2. 간단 예제

마무리

Graph-tool 10

Graph-tool 논문5

0개의 댓글

Graph-tool 11

1. predecessor_tree(g, pred_map)

1.1. 개념 및 기능

1.2. 파이썬 코드 예시

1.3. 설명

2. line_graph(g)

2.1. 개념 및 기능

2.2. 파이썬 코드 예시

2.3. 설명

3. condensation_graph(g, prop, ...)

3.1. 개념 및 기능

3.2. 파이썬 코드 예시

3.3. 설명

4. 중복 간선(Parallel edges) 및 자기루프(Self loops) 처리

4.1. contract_parallel_edges(g, weight=None) 와 expand_parallel_edges(g, weight)

예시 코드

4.2. remove_parallel_edges(g)

4.3. label_parallel_edges(g, mark_only=False, eprop=None)

4.4. remove_self_loops(g) / label_self_loops(...)

자기루프 제거 예시

정리

1. graph_union(g1, g2, ...)

1.1. 개념 및 기능

1.2. 간단 예제

1.2.1. 주요 포인트

2. lattice(shape, periodic=False)

2.1. 개념 및 기능

2.2. 간단 예제

2.2.1. 주요 포인트

3. complete_graph(N, self_loops=False, directed=False)

3.1. 개념 및 기능

3.2. 간단 예제

4. circular_graph(N, k=1, self_loops=False, directed=False)

4.1. 개념 및 기능

4.2. 간단 예제

마무리

Graph-tool 10

Graph-tool 논문5

0개의 댓글

1. `predecessor_tree(g, pred_map)`

2. `line_graph(g)`

3. `condensation_graph(g, prop, ...)`

4.1. `contract_parallel_edges(g, weight=None)` 와 `expand_parallel_edges(g, weight)`

4.2. `remove_parallel_edges(g)`

4.3. `label_parallel_edges(g, mark_only=False, eprop=None)`

4.4. `remove_self_loops(g)` / `label_self_loops(...)`

1. `graph_union(g1, g2, ...)`

2. `lattice(shape, periodic=False)`

3. `complete_graph(N, self_loops=False, directed=False)`

4. `circular_graph(N, k=1, self_loops=False, directed=False)`