graph_tool.topology 1

Sylen·2025년 1월 4일

아래 튜토리얼은 graph-tool 라이브러리의 shortest_distance() 함수를 이용해, 그래프에서 두 정점 사이(혹은 모든 쌍) 최단 거리(Shortest Path Distance)를 효율적으로 계산하는 과정을 자세히 설명합니다.
초보자를 위해 파이썬 코드 예시, 상세한 한글 주석 및 추가 활용 팁을 포함했습니다.

1. shortest_distance()란?

dist = graph_tool.topology.shortest_distance(
    g,
    source=None,
    target=None,
    weights=None,
    negative_weights=False,
    max_dist=None,
    directed=None,
    dense=False,
    dist_map=None,
    pred_map=False,
    return_reached=False,
    dag=False
)

  • 입력:

    • g: Graph 객체
    • source: 단일 정점(예: g.vertex(0)) 또는 None
    • target: 단일 정점, 여러 정점(iterable), 혹은 None
    • weights: (선택) EdgePropertyMap(가중치). 없으면 비가중 BFS
    • 기타 파라미터: negative_weights, max_dist, directed, dense, dist_map, pred_map, etc.

  • 출력:

    1. dist_map: 최단거리 정보. 반환 형태는 상황별로 다름.
      • source가 주어졌고 target이 없으면 → VertexPropertyMap (모든 정점까지의 거리).
      • target이 정점의 리스트면 → numpy.ndarray (대상 정점들까지 거리만).
      • source=None이면 → 모든 쌍 최단거리를 저장하는 2차원 property map(vec<double>) …
    2. (옵션) pred_map: True거나 혹은 property map을 주면, 최단경로의 predecessor 기록
    3. (옵션) visited: return_reached=True 시 방문된 정점 목록.

1.1 주요 시나리오

  1. 단일 소스 → 모든 정점: Dijkstra/BFS.
  2. 단일 소스 → 일부 target들: dist array(numpy.ndarray)
  3. source=None (모든 쌍) → Johnson/Floyd-Warshall( dense=True ).

2. 예시 1: 단일 소스, 무가중 그래프

가장 기본적인: BFS 방식으로 “특정 정점에서 다른 모든 정점까지” 최단거리.

import graph_tool.all as gt
import numpy as np

def example_shortest_dist_unweighted():
    # 1) 무작위 그래프(100노드), 무방향, 평균 차수 3 근사
    g = gt.random_graph(100, lambda: (3,3), directed=False)
    
    # 2) source = g.vertex(0), 무가중
    dist_map = gt.shortest_distance(g, source=g.vertex(0), weights=None)

    # dist_map은 VertexPropertyMap
    # 각 정점까지의 최단거리 정보가 dist_map[v]에 저장
    # array로 보고싶으면 dist_map.a 로 접근
    print("distance array from node 0:", dist_map.a)

    # 예: 특정 정점 i 의 거리:
    print("distance to vertex 10:", dist_map[g.vertex(10)])

if __name__=="__main__":
    example_shortest_dist_unweighted()

코드 해설

  1. 그래프 생성: 무방향, 100노드, 평균 차수 ~3.
  2. shortest_distance(...) 호출:
    • source=g.vertex(0): 0번 노드부터
    • weights=None: 무가중(BFS).
  3. 결과: dist_map (VertexPropertyMap)
    • dist_map[a] 로 전역 배열(길이=100) 접근 가능.

3. 예시 2: 단일 소스, 일부 타깃(target)만

많은 정점 중, 특정 target들만 거리를 알고 싶을 때. 반환이 numpy.ndarray 임.

def example_shortest_dist_subset_target():
    # 1) 그래프 준비
    g = gt.random_graph(50, lambda: (4,4), directed=False)

    # 2) 소스= v0, 타겟= [v2, v6, v10]
    targets = [g.vertex(2), g.vertex(6), g.vertex(10)]
    dist_array = gt.shortest_distance(g, source=g.vertex(0), target=targets)

    print("Distances to v2, v6, v10:", dist_array)
    # => ex) [3,2,5] 이런 식

if __name__=="__main__":
    example_shortest_dist_subset_target()

4. 예시 3: 모든 쌍 최단거리

  • source=None → Johnson 알고리즘(기본), or dense=True → Floyd-Warshall.
  • 결과: dist_map[v]가 “정점 v에서 다른 모든 정점까지 거리” 배열(2D)이 들어있는 vec<double> type property map.
def example_shortest_dist_allpairs():
    g = gt.random_graph(30, lambda: (3,3), directed=False)

    # 모든 쌍 최단거리
    dist_map = gt.shortest_distance(g, source=None)  
    # => Johnson 알고리즘, dist_map[u][v] => u->v 최단거리

    # 예시: dist_map[g.vertex(0)] 는 vertex 0->모든 노드의 거리 array
    arr0 = dist_map[g.vertex(0)].a
    print("distances from vertex 0:", arr0)
    
    # dist_map[g.vertex(i)][g.vertex(j)] 로 i->j
    dist_0_to_5 = dist_map[g.vertex(0)][g.vertex(5)]
    print("distance 0 -> 5:", dist_0_to_5)

if __name__=="__main__":
    example_shortest_dist_allpairs()

5. 예시 4: 가중치 사용

  • 가중치 있을 때 Dijkstra,
  • negative_weights=True이면 Bellman-Ford (음수 간선, 음수 사이클 X)
  • 소스=None이면 Johnson/Floyd-Warshall
def example_shortest_dist_weighted():
    g = gt.Graph(directed=True)
    # 정점 5개, 임의 간선
    v = [g.add_vertex() for _ in range(5)]
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[2], v[3])
    e4 = g.add_edge(v[0], v[4])

    # 가중치 property
    wprop = g.new_edge_property("double")
    wprop[e1], wprop[e2], wprop[e3], wprop[e4] = 2.5, 1.0, 4.0, 3.2

    # Dijkstra (weights=wprop)
    dist_map = gt.shortest_distance(g, source=v[0], weights=wprop)
    print("Weighted distance from v0 to others:", dist_map.a)
    # ex) [ 0. , 2.5, 3.5, 7.5, 3.2]

if __name__=="__main__":
    example_shortest_dist_weighted()

6. pred_map, return_reached 활용

  • pred_map=True: 최단거리 트리(각 노드의 predecessor) 반환, path 복원 가능.
  • return_reached=True: BFS/Dijkstra 시 방문된 정점 목록(numpy.ndarray)
def example_shortest_dist_pred():
    g = gt.random_graph(6, lambda: (2,2), directed=False)
    dist_map, pred_map, visited = gt.shortest_distance(
        g,
        source=g.vertex(0),
        weights=None,
        pred_map=True,            # 반환
        return_reached=True
    )

    print("Distances:", dist_map.a)
    print("Predecessors:", pred_map.a)
    print("Visited vertices:", visited)  # array of vertex indices
  • pred_map[v] → “v”의 직전 노드(최단경로에서).

7. 주요 파라미터 정리

  • source=None: 모든 쌍 최단거리.
  • target: 단일 정점 or iterable.
  • weights: None=무가중. double=가중치.
  • negative_weights: Bellman-Ford (음수사이클 없을 때).
  • max_dist: BFS시 특정 dist 초과는 탐색 중단(성능↑).
  • directed=None: 그래프 방향성. None=그래프 실제 방향 사용.
  • dense=True: Floyd-Warshall, sparse→Johnson(default).
  • dist_map: 사전에 할당한 property map. (사용 안해도 자동 생성)
  • pred_map: True or property map → predecessor.
  • return_reached: True → 방문된 정점 np.array.

8. 복잡도

  • 소스 O(1)인 경우(단일 소스):
    • 무가중 BFS: (O(V+E))
    • 가중치 Dijkstra: (O(E\log V))
    • negative_weights + Bellman-Ford: (O(VE))
  • 소스=None (모든 쌍):
    • sparse (dense=False) Johnson: (O(VE\log V))
    • dense (dense=True) Floyd-Warshall: (O(V^3))

9. 마무리

shortest_distance()는 graph-tool에서 가장 기초적이고도 강력한 최단거리 계산 함수로, BFS~Bellman-Ford~Johnson~Floyd-Warshall 등을 상황에 맞게 내부적으로 수행:

  1. 단일 소스 or 모든 쌍 최단거리
  2. 가중치 or 무가중
  3. 음수 가중치(음수사이클X) or DAG

정리하자면:

  • 단일 소스, 무가중: BFS
  • 단일 소스, 가중치: Dijkstra
  • 단일 소스, 음수 가중치: Bellman-Ford
  • 모든 쌍: Johnson / Floyd-Warshall

또한, pred_map를 통해 경로 복원도 가능하며, samples 파라미터가 있는 유사 함수(예: distance_histogram) 등과 연계해 시각화하면 네트워크 구조(지름, 평균거리 등)를 폭넓게 분석할 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 shortest_path() 함수를 이용해, 그래프에서 두 정점 사이의 최단 경로(Shortest Path)를 간단히 구하고, 해당 경로에 해당하는 정점 리스트와 간선 리스트를 받아보는 과정을 자세히 설명합니다. 초보자를 위해 파이썬 코드 예시, 상세한 한글 주석, 추가 팁 등을 포함하였습니다.

1. shortest_path() 개요

vlist, elist = graph_tool.topology.shortest_path(
    g,
    source,
    target,
    weights=None,
    negative_weights=False,
    pred_map=None,
    dag=False
)

  • 입력:

    • g: Graph 객체
    • source: 시작 정점(g.vertex(i) 형태)
    • target: 도착 정점(g.vertex(j) 형태)
    • weights: (옵션) EdgePropertyMap (가중치). 없으면 무가중 BFS
    • negative_weights: 음수 가중치 존재 시 True → Bellman-Ford
    • pred_map: (옵션) 최단거리 트리의 predecessor 저장된 map을 이미 가지고 있으면, 직접 경로 복원만 수행
    • dag: (옵션) DAG라면 가중치에 음수가 있어도 빠른 알고리즘 사용

  • 출력:

    • vlist: source부터 target까지의 정점 리스트 (예: [v0, ..., vt])
    • elist: 그에 대응하는 간선 리스트 (예: [e1, e2, ...])

1.1 내부 알고리즘

  • 무가중 → BFS
  • 가중치 weights 지정 → Dijkstra
  • negative_weights=True → Bellman-Ford
  • dag=True & weights → DAG Shortest Path

2. 기본 예시: 무가중 그래프

2.1 코드

import graph_tool.all as gt
import numpy as np

def example_shortest_path_unweighted():
    # 1) 무방향 그래프 생성
    g = gt.random_graph(10, lambda: (2,2), directed=False)
    # => 10개 노드, 평균차수 ~ 2

    # 2) 출발 정점(src)와 도착 정점(dst) 설정
    src = g.vertex(0)
    dst = g.vertex(5)

    # 3) shortest_path: 무가중이므로 BFS
    vlist, elist = gt.shortest_path(
        g,
        source=src,
        target=dst,
        weights=None   # 무가중
    )

    # 4) 결과 출력
    print("Shortest path from %d to %d:" % (src, dst))
    print("Vertex list:", [int(v) for v in vlist])
    print("Edge list  :", [(int(e.source()), int(e.target())) for e in elist])

if __name__=="__main__":
    example_shortest_path_unweighted()

2.2 해설

  1. 그래프 생성: random_graph(10, (2,2), directed=False).
  2. shortest_path() 호출 시 weights=None → BFS 내부 사용.
  3. 반환: (vlist, elist).
  4. vlist: source→target을 잇는 정점들, elist: 그 사이 간선들.
  5. 결과 예) 
    Shortest path from 0 to 5:
Vertex list: [0, 3, 7, 5]
Edge list  : [(0,3), (3,7), (7,5)]

3. 예시: 가중치 있는 그래프 (양수)

3.1 코드

def example_shortest_path_weighted():
    g = gt.Graph(directed=True)
    
    # 정점 5개
    v = [g.add_vertex() for _ in range(5)]
    # 간선 예시
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[2], v[4])
    e4 = g.add_edge(v[0], v[3])
    e5 = g.add_edge(v[3], v[4])

    # 가중치 property
    wprop = g.new_edge_property("double")
    wprop[e1] = 2.0
    wprop[e2] = 1.5
    wprop[e3] = 3.0
    wprop[e4] = 4.0
    wprop[e5] = 1.0

    # Dijkstra로 최단경로
    vlist, elist = gt.shortest_path(
        g,
        source=v[0],
        target=v[4],
        weights=wprop    # 양의 가중치
    )

    print("Shortest path from 0 -> 4:")
    print("Vertices:", [int(vert) for vert in vlist])
    print("Edges   :", [(int(e.source()), int(e.target())) for e in elist])

3.2 설명

  • 유향 그래프 예시, 간선 5개, wprop: double.
  • shortest_path(..., weights=wprop) → Dijkstra internally.
  • 경로와 간선이 같이 반환.

4. 예시: 음수 가중치

  • negative_weights=True 사용 → Bellman-Ford.
  • 음수 사이클이 없어야 함.
def example_shortest_path_negative():
    g = gt.Graph(directed=True)
    v = [g.add_vertex() for _ in range(4)]
    
    # 간선
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[2], v[3])
    e4 = g.add_edge(v[1], v[3])  # 단축 가능
    
    # 음수 가중치 할당 (단, 사이클 없어야)
    wprop = g.new_edge_property("double")
    wprop[e1], wprop[e2], wprop[e3], wprop[e4] = 2.0, -1.0, 3.0, 0.5

    # Bellman-Ford
    vlist, elist = gt.shortest_path(
        g,
        source=v[0],
        target=v[3],
        weights=wprop,
        negative_weights=True  # 음수 허용
    )
    
    print("Shortest path with negative weight from 0 -> 3:")
    print("vlist:", [int(vv) for vv in vlist])
    print("elist:", [(int(e.source()), int(e.target())) for e in elist])

5. pred_map 사용하여 경로 복원

  • pred_map: 기존에 shortest_distance() 등으로 구한 predecessor 정보가 있으면, shortest_path()가 그것을 이용해 경로를 직접 복원만 수행(다시 Dijkstra/BFS 안 함).
def example_pred_map_restore():
    g = gt.random_graph(6, lambda: (2,2), directed=False)

    # dist + pred
    dist_map, pred_map = gt.shortest_distance(
        g, source=g.vertex(0),
        pred_map=True
    )
    # 위에서 pred_map이 나왔다면
    # shortest_path에서 pred_map을 그대로 사용
    vlist, elist = gt.shortest_path(
        g, source=g.vertex(0),
        target=g.vertex(5),
        pred_map=pred_map   # 다시 알고리즘 실행X, pred로 경로 복원
    )
    print("Shortest path using pred_map:", [int(v) for v in vlist])

6. 주의할 점

  1. source·target 모두 필요(단일 or 특정).
  2. 음수 가중치 시 negative_weights=True, 음수 사이클 없는지 주의.
  3. pred_map를 이미 알고 있으면, 계산 생략하고 “경로 복원”만 가능.
  4. 결과 (vlist, elist)는 유일한 최단경로 중 하나. 최단경로가 여러 개 존재할 수 있음.

7. 성능

  • 무가중 BFS: (O(V+E))
  • 양수 가중치 Dijkstra: (O(E\log V))
  • 음수 가중치(사이클X) Bellman-Ford: (O(VE))
  • DAG & weights → topological-based ~ (O(V+E))

8. 마무리

shortest_path()는 단일 source-target 최단경로를 가장 쉽게 구하는 함수이며,

  • 무가중이면 BFS,
  • 양수 가중이면 Dijkstra,
  • 음수 가중이면 Bellman-Ford(사이클 X),
  • DAG시 더 최적화된 방법
    등을 내부적으로 자동 선택합니다.

요약:
1. vlist, elist = gt.shortest_path(g, src, dst, weights=..., negative_weights=...)
2. pred_map로 경로 복원만 수행 가능.

  1. 응용: 최단경로 시각화, 비용/거리/시간 최소 루트 탐색 등.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 random_shortest_path() 함수를 이용해, 두 정점 간의 여러 개의 최단 경로 중 무작위로 하나(혹은 복수)를 뽑아내고자 할 때 사용할 수 있는 방법을 보여줍니다. 초보자를 위해 파이썬 코드 예시, 상세한 한글 주석, 추가 팁 등을 친절하고 정성스럽게 설명합니다.

1. random_shortest_path() 개요

path = graph_tool.topology.random_shortest_path(
    g,
    source, 
    target,
    dist_map=None,
    pred_map=None,
    all_preds_map=None,
    epsilon=1e-8,
    nsamples=1,
    iterator=False,
    **kwargs
)

  • 입력:

    • g: 그래프 객체(Graph)
    • source: 시작 정점 (예: g.vertex(0))
    • target: 도착 정점 (예: g.vertex(5))
    • dist_map: (옵션) source에서 각 노드까지 최단거리를 저장한 VertexPropertyMap
    • pred_map: (옵션) 각 노드의 predecessor를 기록한 VertexPropertyMap
    • all_preds_map: (옵션) 각 노드가 가질 수 있는 모든 predecessor 목록(벡터형)을 담은 VertexPropertyMap
    • epsilon: 부동소수점 오차 허용치(가중치가 유사할 때 “동일” 간주)
    • nsamples: 1보다 큰 값이면 그만큼 여러 개의 무작위 최단경로를 뽑아옴
    • iterator: True로 하면 경로들을 담은 이터레이터를 반환 (크기가 큰 경우 메모리 절약)
    • **kwargs: 내부적으로 shortest_path()에 전달될 기타 파라미터 (예: weights, negative_weights, dag 등)

  • 출력:

    • path: 무작위로 뽑힌 최단경로에 해당하는 정점들의 시퀀스(numpy ndarray).
    • nsamples>1이면, list(혹은 iterator=True 시 generator)로 여러 경로 반환.

1.1 내부 동작 방식

  • 기본적으로 shortest_path()와 유사한 로직으로 최단거리를 구한 뒤, 경로 선택 시 predecessor를 균등 확률로 무작위 선택하여 path를 구성함.
  • dist_map, pred_map 등이 이미 있으면 재계산 없이 바로 경로만 무작위 추출.

2. 간단 예시: 무가중, 단일 경로

다음 코드는 무작위 그래프(무가중)에서, 특정 source와 target 사이의 무작위 최단경로 하나를 뽑아봅니다.

import graph_tool.all as gt
import numpy as np

def example_random_shortest_path_unweighted():
    # 1) 무방향 그래프 생성(노드 10, 평균차수 ~ 2)
    g = gt.random_graph(10, lambda: (2,2), directed=False)

    # 2) source, target 선택
    src = g.vertex(0)
    tgt = g.vertex(7)

    # 3) 무작위 최단 경로 얻기
    path = gt.random_shortest_path(g, source=src, target=tgt)
    # => path: numpy array of vertex IDs in order

    print("Random shortest path from {} to {}:".format(int(src), int(tgt)))
    print("Path (vertices):", path)  # e.g. [0 3 8 7]

if __name__=="__main__":
    example_random_shortest_path_unweighted()

해설

  1. 무방향, 무가중 → 내부적으로 BFS를 수행 후, 다수의 최단경로 중 하나를 무작위 선택.
  2. random_shortest_path(...) 결과는 정점 인덱스를 담은 numpy 배열.
  3. 예) Path (vertices): [0 3 8 7]

3. 여러 개 최단경로 샘플링 (nsamples>1)

nsamples 파라미터로 여러 개를 한 번에 뽑을 수 있습니다.

def example_random_shortest_path_samples():
    g = gt.random_graph(20, lambda: (3,3), directed=False)
    src, tgt = g.vertex(0), g.vertex(15)

    # 한 번에 3개 무작위 최단경로
    paths = gt.random_shortest_path(g, src, tgt, nsamples=3)

    # paths는 list of numpy.ndarray
    for i, p in enumerate(paths):
        print(f"Sample {i+1} path:", p)

출력 예)

Sample 1 path: [ 0  7  4 15]
Sample 2 path: [ 0  1 15]
Sample 3 path: [ 0  2  4 15]

4. 가중치 그래프 예시

def example_random_shortest_path_weighted():
    g = gt.Graph(directed=True)
    v = [g.add_vertex() for _ in range(5)]
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[0], v[2])
    e4 = g.add_edge(v[2], v[4])
    e5 = g.add_edge(v[0], v[3])
    e6 = g.add_edge(v[3], v[4])

    wprop = g.new_edge_property("double")
    wprop[e1] = 1.0
    wprop[e2] = 2.0
    wprop[e3] = 2.5
    wprop[e4] = 1.0
    wprop[e5] = 4.0
    wprop[e6] = 0.5

    # 무작위 최단경로(가중치가 있으므로 Dijkstra + uniform choice among same-dist predecessors)
    path = gt.random_shortest_path(g, source=v[0], target=v[4], weights=wprop)
    print("Random shortest path (weighted) 0->4:", path)

여기서는 0→4의 최단경로가 여러 개 있을 수도 있고(동일 총비용), 그 중 하나를 랜덤 선택.

5. pred_map / dist_map 직접 사용

  • dist_map, pred_map가 이미 있으면, random_shortest_path 호출 시 재계산 안 하고 바로 경로 샘플링 가능.
  • all_preds_map를 제공하면, predecessor가 여러 개인 노드에 대해 경로 선택 시 더 효율적.
def example_random_sp_with_pred():
    g = gt.random_graph(8, lambda: (2,2), directed=False)
    src, tgt = g.vertex(0), g.vertex(5)

    # 미리 shortest_distance로 dist, pred 를 구함
    dist_map, pred_map = gt.shortest_distance(g, source=src, pred_map=True)

    # random_shortest_path()에 pred_map 전달
    path = gt.random_shortest_path(g, source=src, target=tgt, dist_map=dist_map, pred_map=pred_map)
    print("Random path using existing pred_map:", path)

6. iterator 모드 (대량 샘플링 시)

  • iterator=True & nsamples > 1 → 메모리 절약. generator로 경로를 하나씩 yield.
def example_random_shortest_path_iterator():
    g = gt.random_graph(30, lambda: (3,3), directed=False)
    src, tgt = g.vertex(0), g.vertex(20)

    # iterator 모드, nsamples=5
    path_iterator = gt.random_shortest_path(
        g, src, tgt,
        nsamples=5,
        iterator=True
    )

    for i, path in enumerate(path_iterator, start=1):
        print(f"Path #{i}:", path)

7. epsilon 파라미터

  • 부동소수점 가중치가 있을 때, 둘의 거리가 epsilon 이하로 비슷하면 "동일 거리"로 간주 → predecessor 여러 개 발생.
  • 기본 1e-8, 필요 시 조정.

8. 성능 및 주의사항

  • 내부적으로 shortest_path()를 호출 (BFS/Dijkstra/Bellman-Ford 등).
  • 최단거리가 여러 개 존재하면, 균등 확률로 predecessor를 무작위 선택.
  • 큰 그래프에서 nsamples 많이 설정 시 계산 부담.
    • iterator=True로 일부만 실시간 fetch 가능.

9. 요약

random_shortest_path():

  1. 목적: 두 정점 사이 최단경로가 여러 개 있을 경우, 하나 혹은 여러 개를 랜덤하게(균등) 추출.
  2. 사용법:
    path = random_shortest_path(g, source, target, nsamples=..., iterator=...)
  3. 가중치 여부, 음수 여부 등에 따라 내부 알고리즘 다름(= shortest_path()와 동일).
  4. 추가: dist_map, pred_map가 있으면 재계산 불필요.
  5. 여러 개( nsamples>1 ) 및 iterator 모드 → 대규모 상황에도 유리.

결론적으로, 단순 shortest_path()가 아니라, “최단경로 중 임의로 하나(혹은 여러 개)”가 필요할 때, random_shortest_path()를 사용해 균등 샘플링을 달성할 수 있습니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 count_shortest_paths() 함수를 이용하여 두 정점 사이 최단 경로의 개수를 효율적으로 계산하는 방법을 설명합니다. 이 과정에서 초보자를 위해 파이썬 코드 예시, 상세한 한글 주석, 추가 활용 팁 등을 친절하고 정성스럽게 안내합니다.

1. count_shortest_paths() 함수 개요

n_paths = graph_tool.topology.count_shortest_paths(
    g,
    source,
    target,
    dist_map=None,
    pred_map=None,
    all_preds_map=None,
    epsilon=1e-8,
    **kwargs
)

  • 입력:

    • g: Graph 객체
    • source: 시작 정점 (예: g.vertex(i))
    • target: 도착 정점 (예: g.vertex(j))
    • dist_map: (옵션) source에서 각 노드까지 최단 거리를 저장한 VertexPropertyMap. 이미 있으면 재계산 불필요.
    • pred_map: (옵션) 각 노드의 predecessor를 저장한 VertexPropertyMap(int64_t).
    • all_preds_map: (옵션) 각 노드가 가질 수 있는 모든 predecessor 목록(벡터)를 담은 VertexPropertyMap.
    • epsilon: 부동소수 가중치에서 “동일 거리”로 간주할 때의 상대 오차 (기본 1e-8).
    • **kwargs: 추가 파라미터는 내부적으로 shortest_path()에 전달됨 (가중치, negative_weights 등).

  • 출력:

    • n_paths: int형, source→target 최단 경로 개수.

1.1 내부 알고리즘

  • shortest_path()와 동일하게 최단 거리 트리를 구성 후, 경로를 만들어가는 과정에서 predecessor 정보를 통해 경로 수를 세는 방식.
  • dist_map, pred_map 등이 있으면 재계산 없이 바로 count 수행.

2. 예시 1: 무가중 그래프에서 최단 경로 개수

다음 코드는 무방향·무가중 그래프에서 단일 source와 target 사이 최단 경로 개수를 계산합니다.

import graph_tool.all as gt
import numpy as np

def example_count_shortest_paths_unweighted():
    # 1) 무방향 그래프 생성: 노드 10, 평균차수 ~2
    g = gt.random_graph(10, lambda: (2,2), directed=False)

    src = g.vertex(0)
    tgt = g.vertex(7)

    # 2) 최단 경로 개수
    n_paths = gt.count_shortest_paths(
        g,
        source=src,
        target=tgt
    )

    print("Number of shortest paths from {} to {}: {}".format(int(src), int(tgt), n_paths))

if __name__=="__main__":
    example_count_shortest_paths_unweighted()

해설

  1. random_graph(10, (2,2), directed=False) → 무가중, 10노드.
  2. count_shortest_paths(g, src, tgt) → BFS(무가중) 기반.
  3. 출력 예) 
    Number of shortest paths from 0 to 7: 3

3. 예시 2: 가중치 있는 그래프 (양수)

def example_count_shortest_paths_weighted():
    g = gt.Graph(directed=True)
    v = [g.add_vertex() for _ in range(5)]

    # 간선 생성
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[0], v[2])
    e4 = g.add_edge(v[2], v[4])
    e5 = g.add_edge(v[0], v[3])
    e6 = g.add_edge(v[3], v[4])

    # 가중치 property
    wprop = g.new_edge_property("double")
    wprop[e1] = 2.0
    wprop[e2] = 1.0
    wprop[e3] = 2.5
    wprop[e4] = 1.5
    wprop[e5] = 4.0
    wprop[e6] = 1.5

    # 최단 경로 개수: Dijkstra 내부 사용
    n_paths = gt.count_shortest_paths(
        g,
        source=v[0],
        target=v[4],
        weights=wprop
    )
    print("Number of shortest paths (weighted) from 0->4:", n_paths)

설명:

  • 가중치가 양수이므로, Dijkstra 알고리즘으로 최단거리 트리 생성 후, 동일 거리 가지(=동일 total weight) 경로 수 계산.

4. 음수 가중치 (Bellman-Ford)

  • negative_weights=True를 설정.
  • 음수 가중치가 있어도 음수 사이클만 없다면 최단 경로 수 계산 가능.
def example_count_shortest_paths_negative():
    g = gt.Graph(directed=True)
    v = [g.add_vertex() for _ in range(4)]
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[2], v[3])
    wprop = g.new_edge_property("double")
    wprop[e1] = 2.0
    wprop[e2] = -1.0
    wprop[e3] = 3.0

    n_paths = gt.count_shortest_paths(
        g, v[0], v[3],
        weights=wprop,
        negative_weights=True
    )
    print("Num shortest paths with negative edge from 0->3:", n_paths)

5. pred_map, dist_map, all_preds_map

  1. dist_map: source→모든 노드 최단거리 PropertyMap
  2. pred_map: 각 노드의 predecessor (단일)
  3. all_preds_map: 여러 predecessor가 있을 수 있는 상황에서, 각 노드가 가질 수 있는 predecessor 목록(벡터).
    • 최단 경로 개수 계산 시, predecessor가 여러 개인 노드에 대해 곱셈 형태로 count.

이미 shortest_distance() 나 shortest_path()를 통해 dist_map·pred_map을 구했다면, 다시 계산하지 않고:

def example_count_with_pred():
    g = gt.random_graph(6, lambda: (2,2), directed=False)
    src, tgt = g.vertex(0), g.vertex(5)

    # dist_map, pred_map 얻기 ( BFS or Dijkstra )
    dist_map, pred_map = gt.shortest_distance(g, source=src, pred_map=True)

    # count_shortest_paths에 전달
    n_paths = gt.count_shortest_paths(
        g,
        source=src,
        target=tgt,
        dist_map=dist_map,
        pred_map=pred_map
    )
    print(f"From {int(src)} to {int(tgt)}, #paths= {n_paths}")

6. epsilon (부동소수점 오차)

  • floating 가중치에서 약간의 오차로 거리 차이가 미미하지만 “같다”고 간주해야 할 때 사용 (기본 1e-8).

7. 시간복잡도 및 내부 알고리즘

  • 내부적으로 shortest_path()(BFS/Dijkstra/Bellman-Ford 등)로 최단거리/트리를 구함.
  • 이후 predecessor(s)로 경로 수 계산:
    • 무가중 BFS 시 (O(V+E))
    • 양수 가중치 Dijkstra 시 (O(E\log V))
    • 음수(사이클x) Bellman-Ford 시 (O(VE))

8. 정리

count_shortest_paths():
1. shortest_path() 기반 최단 경로 트리 생성.
2. 경로 수 계산(동일 거리 가지 수).
3. dist_map, pred_map 미리 있으면 재사용 가능.
4. 음수 가중치 / DAG도 지원(옵션).

실무 적용: 도시·교통망에서 특정 노선(소스→타깃)의 “모든 최단 경로가 몇 개인가?” 알고 싶을 때 유용. 예) 같은 최단 거리지만 서로 다른 경로가 얼마나 되는지 파악 가능.

최종 예시 코드 전체

import graph_tool.all as gt
import numpy as np

def main():
    # 무작위로 10노드 그래프 생성
    g = gt.random_graph(10, lambda: (2,2), directed=False)

    # source, target 지정
    src, tgt = g.vertex(0), g.vertex(7)

    # 최단 경로 개수 계산
    n_paths = gt.count_shortest_paths(g, src, tgt)
    print(f"Number of shortest paths from {int(src)} to {int(tgt)}: {n_paths}")

if __name__ == "__main__":
    main()

결과 예시:

Number of shortest paths from 0 to 7: 2

이상으로, count_shortest_paths() 함수의 사용법 및 예시를 소개했습니다.

shortest_distance() 함수를 호출할 때, 가중치(weights)를 어떻게 주느냐 또는 negative_weights=True 같은 옵션이 켜져 있느냐에 따라 내부적으로 최단거리를 계산하는 알고리즘이 달라집니다. 이를 정리하면 다음과 같습니다:

1. 무가중 (weights=None)

  • 알고리즘: BFS (너비 우선 탐색)
  • 동작 방식:
    • 간선 가중치가 없으므로, 모든 간선 비용을 동일(=1)로 간주.
    • 루트(소스) 정점에서 시작해 계층적으로 이웃들을 방문.
    • 소스→각 정점까지의 방문 순서(계층)가 곧 최단거리.

예시:

dist_map = gt.shortest_distance(
    g,
    source=g.vertex(0),   # 소스
    weights=None          # 무가중 -> BFS
)

2. 양의 가중치 (weights=EdgePropertyMap, 음수 없음)

  • 알고리즘: Dijkstra
  • 동작 방식:
    • 각 간선의 양의 가중치(비용)를 고려.
    • 우선순위 큐(힙) 사용 → 간선 비용이 작은 쪽을 우선 탐색.
    • 소스→각 정점까지 가중치 합이 최소가 되도록 최단거리 계산.

예시:

wprop = g.new_edge_property("double")
# wprop[e] = ...
dist_map = gt.shortest_distance(
    g,
    source=g.vertex(0),
    weights=wprop,      # 양수 가중치 -> Dijkstra
    negative_weights=False
)

3. 음수 가중치 (negative_weights=True)

  • 알고리즘: Bellman-Ford
  • 동작 방식:
    • 간선에 음수가중치가 있을 때 사용.
    • 음수 간선이 있어도, 음수 사이클은 없어야 최단거리 계산 가능.
    • 모든 간선을 (V-1)번 반복 스캔하는 고전 알고리즘.

예시:

wprop = g.new_edge_property("double")
# wprop[e] = ...
dist_map = gt.shortest_distance(
    g,
    source=g.vertex(0),
    weights=wprop,
    negative_weights=True  # 음수 가중치 -> Bellman-Ford
)

주의: 음수 사이클이 존재하면 최단 경로가 정의되지 않으므로 에러 또는 잘못된 값.

4. 모든 쌍 최단 거리 (source=None)

  • 알고리즘:
    1. 기본적으로 Johnson 알고리즘 (희소 그래프에 적합).
    2. dense=True일 경우, Floyd-Warshall (밀집 그래프).

예시:

# 희소그래프, 모든 쌍 최단거리 -> Johnson 알고리즘
dist_map = gt.shortest_distance(g, source=None)

# 밀집그래프, 모든 쌍 최단거리 -> Floyd-Warshall
dist_map = gt.shortest_distance(g, source=None, dense=True)

5. max_dist, directed, dag 등 추가 옵션

  1. max_dist: BFS/Dijkstra에서 최대 탐색 거리를 제한 → 성능 최적화.
  2. directed: None이면 그래프의 실제 방향성 그대로, True/False로 강제.
  3. dag=True: 방향 그래프가 DAG(사이클X)라면 더 빠른 알고리즘 허용 (가중치가 있어도 음수 가능).

6. 정리

  • shortest_distance()는 가중치 존재 여부와 음수 사용 여부에 따라 내부 알고리즘이 달라집니다:
    1. 무가중 → BFS
    2. 양수 가중치 → Dijkstra
    3. 음수 가중치 (negative_weights=True) → Bellman-Ford
    4. 모든 쌍 (source=None) → Johnson(기본) / Floyd-Warshall(dense=True)
  • 이렇게 자동 선택된 알고리즘으로 최단거리 dist_map을 계산해 주는 것이 shortest_distance()의 핵심 동작 방식입니다.

결과적으로 weights 파라미터를 비우거나(무가중) 혹은 가중치 property map을 넘기고, 필요 시 negative_weights=True와 같은 옵션을 추가하면, 그래프의 상황(음수/양수/무가중)에 맞게 BFS/Dijkstra/Bellman-Ford/Johnson 등의 알고리즘이 자동으로 적용되어 최단거리를 구해주는 것입니다.

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

  • all_shortest_paths(): 두 정점 사이 모든 최단 경로를 찾는 이터레이터
  • all_predecessors(): 단일 최단경로 트리가 아니라, 한 노드에 대해 가능한 여러 predecessor들을 모아주는 기능
  • all_paths(): 특정 두 정점 사이의 모든 경로(cutoff로 길이 제한 가능)

이 세 함수를 초보자의 시각에서 파이썬 코드 예제, 한글 주석, 추가 팁을 포함하여 자세히 설명합니다.

1. all_shortest_paths() : 두 정점 사이 모든 최단 경로

paths_iter = graph_tool.topology.all_shortest_paths(
    g, 
    source, 
    target, 
    dist_map=None, 
    pred_map=None,
    all_preds_map=None,
    epsilon=1e-8,
    edges=False,
    **kwargs
)
  • 역할: source → target로 가는 최단경로가 여러 개 있을 때, 그 모든 경로를 이터레이터 형태로 하나씩 반환.
  • 주요 파라미터:
    • g: 탐색할 Graph 객체
    • source, target: 시작, 도착 정점 (예: g.vertex(0))
    • dist_map: 이미 계산된 소스→모든 정점 최단거리( VertexPropertyMap )가 있다면 사용
    • pred_map or all_preds_map: 이미 계산된 predecessor 정보 (단일 혹은 여러 predecessor)
    • edges=False → 기본은 정점 리스트로 경로 반환. True이면 간선 리스트(Edge 객체들)로 반환.
    • epsilon=1e-8: 부동소수점 가중치 사용 시, "동일 거리"로 취급할 오차범위.
    • **kwargs: 내부적으로 shortest_distance()에 전달 → BFS/Dijkstra/Bellman-Ford 등 사용

리턴: 이터레이터(iterator). 각 경로는 numpy.ndarray 형태(정점 인덱스) 혹은 Edge 리스트.

1.1 간단 예시 (무가중)

import graph_tool.all as gt
import numpy as np

def example_all_shortest_paths_unweighted():
    # 1) 무방향, 무가중 그래프 생성
    g = gt.random_graph(10, lambda: (2,2), directed=False)
    
    # 2) 소스, 타깃
    src = g.vertex(0)
    tgt = g.vertex(7)

    # 3) all_shortest_paths 호출
    paths_iter = gt.all_shortest_paths(g, source=src, target=tgt)
    
    # 4) 결과 출력
    for i, path in enumerate(paths_iter, start=1):
        print(f"Path #{i}:", path)
        # e.g. Path #1: [0 3 5 7], Path #2: [0 2 1 7] ...

if __name__=="__main__":
    example_all_shortest_paths_unweighted()

설명

  • 무가중이므로 내부적으로 BFS + 여러 predecessor를 통해 모든 최단경로를 이터레이터로 제공.
  • path는 정점 인덱스를 담은 numpy.ndarray.

1.2 가중치 그래프의 경우

def example_all_shortest_paths_weighted():
    g = gt.Graph(directed=True)
    # 정점 5개
    v = [g.add_vertex() for _ in range(5)]
    # 간선들
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[0], v[2])
    e4 = g.add_edge(v[2], v[4])
    e5 = g.add_edge(v[1], v[4])
    
    # 가중치
    wprop = g.new_edge_property("double")
    wprop[e1] = 2.0
    wprop[e2] = 1.5
    wprop[e3] = 3.0
    wprop[e4] = 0.5
    wprop[e5] = 2.0
    
    src, tgt = v[0], v[4]
    
    # 모든 최단경로 이터레이터
    paths_iter = gt.all_shortest_paths(
        g, 
        source=src, 
        target=tgt,
        weights=wprop  # 양수 가중치 => Dijkstra
    )
    
    # 출력
    for i, path in enumerate(paths_iter, start=1):
        print(f"Weighted shortest path #{i}: {path}")
  • Dijkstra를 내부적으로 사용.
  • 모든 최단경로를 이터레이터로 반환.

2. all_predecessors(): 여러 predecessor 정보

all_preds_map = graph_tool.topology.all_predecessors(
    g,
    dist_map,
    pred_map,
    weights=None,
    epsilon=1e-8
)
  • 역할: shortest_distance()나 shortest_path()를 통해 얻은 dist_map, pred_map에서, 사실상 여러 predecessor가 존재할 수 있는 노드들의 predecessor를 한꺼번에 정리해주는 함수.
  • 파라미터:
    • g, dist_map, pred_map: 이미 계산된 최단거리, predecessor (단일)
    • weights: 가중치 있으면, "동일 거리" 간주 시 epsilon 적용
  • 결과: all_preds_map 라는 VertexPropertyMap(vector type)이 반환. 즉, all_preds_map[v]가 v의 모든 predecessor 리스트.

2.1 예시

def example_all_predecessors_usage():
    g = gt.random_graph(8, lambda: (2,2), directed=False)
    src = g.vertex(0)
    
    # 1) dist, pred 구하기
    dist_map, pred_map = gt.shortest_distance(
        g, source=src, pred_map=True
    )
    
    # 2) all_predecessors로 여러 predecessor 리스트 맵 구성
    all_preds = gt.all_predecessors(
        g, dist_map, pred_map
    )
    
    # 예: v=5 의 모든 predecessor들
    v5 = g.vertex(5)
    preds_v5 = all_preds[v5]
    print(f"All preds of vertex {int(v5)}:", [int(p) for p in preds_v5])

if __name__=="__main__":
    example_all_predecessors_usage()
  • 그 뒤 all_preds_map를 이용하면, all_shortest_paths(), count_shortest_paths() 등에 건네줌으로써, 여러 predecessor 기반 연산을 더 효율적으로 할 수 있음.

3. all_paths(): 두 정점 사이 모든 경로 (길이 제한 가능)

paths_iter = graph_tool.topology.all_paths(
    g,
    source,
    target,
    cutoff=None,
    edges=False
)
  • 역할: source→target으로 가는 모든 경로를 DFS로 탐색. (최단이 아님!)
  • 파라미터:
    • cutoff: 경로 최대 길이를 지정 (없으면 무한)
    • edges=False: True면 간선 시퀀스, False면 정점 시퀀스
  • 리턴: 이터레이터. 매우 많은 경로가 나올 수 있으므로 주의.

3.1 예시

def example_all_paths():
    g = gt.random_graph(6, lambda: (2,2), directed=False)
    src, tgt = g.vertex(0), g.vertex(4)

    # 모든 경로(최대 길이=4) -> DFS
    path_iter = gt.all_paths(g, source=src, target=tgt, cutoff=4)

    for i, path in enumerate(path_iter, start=1):
        print(f"Path #{i}:", path)
    
    # 만약 경로가 너무 많으면 cutoff를 작게 설정할 것

if __name__=="__main__":
    example_all_paths()

주의: all_paths()는 최단이 아니라 모든 경로이므로, 그래프가 조금만 복잡해도 기하급수적으로 늘어날 수 있음.
cutoff로 길이를 제한하는 것이 일반적.

4. 종합 요약

  • all_shortest_paths():

    • 두 정점(source, target) 사이 모든 최단 경로를 찾음.
    • 반환: 이터레이터(정점 시퀀스 or 간선 시퀀스).
    • 내부적으로 shortest_distance()로 최단거리 계산 후, predecessor를 추적.
    • 최단경로 수가 많을 경우, 메모리·시간 부담 커질 수 있음.

  • all_predecessors():

    • 이미 계산된 단일 predecessor map( pred_map )과 dist_map을 바탕으로, 각 노드가 실제로 가질 수 있는 모든 predecessor를 구해주는 유틸.
    • all_shortest_paths(), count_shortest_paths() 등에 활용 가능.

  • all_paths():

    • DFS로 source→target 사이의 모든 경로를 이터레이터 형태로 열거.
    • cutoff로 최대 경로 길이를 제한 가능.
    • 경로 수가 매우 클 수 있으니 주의.

4.1 알고리즘 및 복잡도

  1. all_shortest_paths():

    • 내부적으로 BFS/Dijkstra/Bellman-Ford로 최단거리 dist 및 predecessor(혹은 all_preds_map) 완성 후, 재귀 혹은 스택 등을 이용해 모든 최단경로를 backtrack.
    • 최단경로 개수가 많으면 그만큼 backtrack 비용도 큼.

  2. all_predecessors():

    • dist_map, pred_map에 기반하여, 각 노드 v에 대해 "동일 거리" predecessor들을 모아 vector로 정리.
    • 시간 복잡도는 O(V+E), 최단거리 계산 자체는 별도.

  3. all_paths():

    • DFS 기반.
    • 경로 개수가 많을 경우 지수적 증가.

5. 최종 예시: all_shortest_paths() + all_predecessors()

import graph_tool.all as gt
import numpy as np

def main():
    # 그래프 생성
    g = gt.random_graph(10, lambda: (2,2), directed=False)

    src, tgt = g.vertex(0), g.vertex(8)

    # 1) dist, pred 구함
    dist_map, pred_map = gt.shortest_distance(g, source=src, pred_map=True)

    # 2) all_predecessors
    all_preds_map = gt.all_predecessors(
        g, dist_map, pred_map, weights=None
    )

    # 3) all_shortest_paths에 all_preds_map 전달
    paths_iter = gt.all_shortest_paths(
        g,
        source=src,
        target=tgt,
        dist_map=dist_map,
        all_preds_map=all_preds_map
    )

    # 출력
    print(f"All shortest paths from {int(src)} to {int(tgt)}:")
    for i, path in enumerate(paths_iter, start=1):
        print(f"Path #{i}:", path)

if __name__=="__main__":
    main()

이 코드에서
1. shortest_distance(..., pred_map=True)로 단일 predecessor map,
2. all_predecessors()로 실제 가능한 모든 predecessor 벡터,
3. all_shortest_paths()에 dist_map·all_preds_map을 넘겨서 모든 최단경로 한번에 추출.

6. 결론

  • all_shortest_paths(): 특정 두 정점 사이 모든 최단경로 이터레이터
  • all_predecessors(): 단일 predecessor map에 대해, 실제로 가질 수 있는 모든 predecessor를 벡터로 만듦
  • all_paths(): 특정 두 정점 사이 DFS 기반 모든 경로 (cutoff로 제한 가능)

graph-tool 라이브러리에서 이들을 잘 활용하면,

  • 여러 최단경로를 모두 열거하거나,
  • predecessor 정보에서 모든 후보를 얻거나,
  • 최단/비최단 구분 없이 모든 경로를 제한적으로 탐색
    등 다양한 네트워크/그래프 분석 시나리오에 적용할 수 있습니다.

이상으로 all_shortest_paths(), all_predecessors(), all_paths() 함수들의 구체적 사용 방법 및 예시였습니다.

아래 튜토리얼에서는 Donald B. Johnson의 논문
“Finding All the Elementary Circuits of a Directed Graph” (SIAM J. Comput., Vol. 4, No. 1, 1975) 내용을 집중적으로 살펴보겠습니다. 이 논문은 방향 그래프(Directed Graph)에서 모든 기본 회로(엘리멘터리 서킷, Elementary Circuit)를 효율적으로 열거(enumeration) 하는 알고리즘을 제시합니다. 기존 알고리즘 대비 시간 복잡도가 향상되었으며, 공간 복잡도도 효율적이라는 점이 중요한 특징입니다.

1. 문제 배경과 용어 정리

  1. 방향 그래프

    • 정점 집합 (V), 간선 집합 (E)
    • 간선은 ((u, v)) 형태 (단, (u \neq v), 중복 간선X, 루프X)

  2. 경로(Path)

    • 정점 시퀀스 ((v0, v_1, \dots, v_k))로서, 모든 연속된 쌍 ((v_i, v{i+1}))가 (E)에 속함.

  3. 회로(Circuit) (혹은 사이클)

    • 경로 중 (v_0 = v_k)인 것.

  4. 기본 회로(엘리멘터리 서킷, Elementary Circuit)

    • 회로 중 (v_0)와 (v_k)만 같고(시작,끝 동일), 중간 정점은 모두 고유하게 한 번씩만 등장.
    • ((v0, v_1, \dots, v{k-1}, v0))에서 (v_1, \dots, v{k-1})는 서로 달라야 함.

  5. 개수

    • 방향 그래프의 기본 회로 수를 (c)라 하자.
    • 논문에서 Johnson 알고리즘의 시간 복잡도는 (O\bigl((n+e)(c+1)\bigr)) ((n)=정점 수, (e)=간선 수)

1.1 기존 알고리즘과 문제점

  • Tiernan (1970), Weinblatt (1972), Tarjan (1973) 등이 제안했던 알고리즘은 최악의 경우(특정 그래프)에서 시간 복잡도가 (O(n \cdot e \cdot (c+1))) 수준.
  • 이 논문에서 Johnson은 더 나은 (O\bigl((n+e)(c+1)\bigr)) 알고리즘을 제시하여 최악 상황에서도 개선됨을 보임.

2. 알고리즘 개요

존슨 알고리즘은 다음과 같은 핵심 아이디어를 가집니다:

  1. 그래프 순회 시, ‘기본 회로’를 찾아낼 때 서로 다른 ‘최소 정점(least vertex)’를 기준으로 그룹핑하여 사이클을 찾음.

    • 예: “사이클의 가장 작은 번호(정점)”를 정하면, 해당 정점보다 작은 번호는 사이클에 포함되지 않도록 서브그래프를 한정.
    • 그래프를 강한 연결 성분(strong component) 단위로도 나누어 처리.

  2. Blocked-Set 기법

    • DFS로 경로를 만들 때, 어떤 정점이 현재 경로에 들어 있으면 blocked[v] = true로 설정하여 중복 방문을 막음.
    • 경로가 실패(회로 형성 못 함) 했을 때도, 이 정보를 B(v)라는 리스트 등에 저장해두어, 불필요한 재탐색을 줄임.

  3. UNBLOCK 과정

    • 만약 어떤 정점이 더 이상 ‘회로 형성 불가능’하지 않으면, blocked[v]를 다시 false로 풀어주는데, 이때 연쇄적으로 연결된 정점들도 풀림.
    • 이 과정을 지연(until needed)시켜, 최단 시간 내에 새 사이클 발견 혹은 탐색 중단을 결정하게 함.

2.1 Pseudo-code (요약)

논문에 제시된 알고리즘은 아래처럼 구성됩니다 (한글화·요약):

ALGORITHM all_elementary_circuits(G):

for s in 1..n:                 # 각 정점을 순차적으로 'root'로 취급
  - 강한 연결성분(Strong Component) 중
    "정점 >= s" 인 부분그래프 중 최소 정점을 s로 하는 SC를 찾음.
  - 만약 그러한 SC가 존재하지 않으면 s+1로 넘어감
  - 그렇지 않다면:
      for each v in SC:
        blocked[v] = false
        B[v] = ∅
      Call CIRCUIT(s)

Procedure CIRCUIT(v):
  push v to stack
  blocked[v] = true
  found_circuit = false

  for w in A(v) do:  # 인접 리스트
    if w == s then
      # 현재 스택 + s로 회로 형성
      output stack + s
      found_circuit = true
    else if not blocked[w] then
      if CIRCUIT(w) == true:
        found_circuit = true

  if found_circuit == true then
    UNBLOCK(v)
  else
    # v에서 인접한 각 w에 v를 B[w]에 추가
    for w in A(v):
      if v not in B[w]:
        B[w].add(v)

  pop v from stack
  return found_circuit

Procedure UNBLOCK(u):
  blocked[u] = false
  for w in B[u]:
    B[u].remove(w)
    if blocked[w] == true:
      UNBLOCK(w)

2.2 Correctness (정당성)

  • 모든 사이클을 찾음:

    • s부터 DFS로 회로 만들 때, blocked[]가 false로 풀리는 시점은 “해당 노드가 더 이상 현재 경로에서 방해 X”임을 보장.
    • 구체적인 증명은 논문 내 “Lemma 1,2”.

  • 중복되지 않음:

    • 각 사이클을 한 번만 출력.
    • “stack 상의 중복 방문을 원천 차단” + “Blocked/B-list” 구조를 적절히 유지.

2.3 시간 복잡도 증명

  • 최악 경우에도, 새 회로가 발견되거나 혹은 재귀에서 돌아오는 시점마다 (O(n+e)) 이하의 작업만 수행됨(= 한 번의 unblocking 단계 + edge traversal).
  • 따라서, 모든 회로(c개)를 찾을 때 총 (O((n+e)(c+1))) 시간.

3. 예시 그래프들에 대한 시간 성능

  • 논문에서 Tarjan(1973) 알고리즘과 비교 예시:
    • 특정 그래프(그림 1, 그림 2)에서 Tarjan은 (O(n \cdot e \cdot (c+1)))에 근접한 성능,
    • Johnson은 (O((n+e)(c+1)))로 더 적은 시간에 가능.
  • 실험 결과:
    1. Worst-case family 그래프에서 Johnson이 훨씬 빠름.
    2. 완전 방향 그래프에서도 Johnson이 Tarjan보다 일정 비율 빠름 (동일 개수만큼 탐색하지만 내부 구현 최적화).

4. 구현 상세 및 팁

  1. Strong Component Decomposition

    • 루프(for s in 1..n) 마다, “정점≥s”인 부분그래프에서 강한 연결 성분 중 최소 정점이 s인 성분만 취급.
    • 이런 전처리로 불필요한 정점 제외.

  2. Blocked / B-list

    • blocked[v]=true이면, 현재 경로에 있거나, 탐색해도 결과가 없다고 이미 판명된 상태.
    • B[v]: 정점 v가 다시 “unblock”될 때 함께 unblock해야 할 이웃들 목록.

  3. 메모리 사용

    • 필요한 자료구조: blocked[] (bool), B[v] (인접 리스트와 유사), stack.
    • 전체 (O(n+e)).

5. 결론 및 의의

  • Donald B. Johnson의 알고리즘은 방향 그래프의 모든 엘리멘터리 서킷을 중복 없이 효율적으로 열거:
    1. 시간: (O\bigl((n + e)(c + 1)\bigr))
    2. 공간: (O(n + e))
  • Tarjan, Tiernan 등 이전 알고리즘보다 최악 사례에서 더 나은 복잡도를 달성.
  • 구현 시:
    • “Blocked”와 “B-list” 구조가 핵심
    • “unblock” 절차가 중복 탐색을 피하면서도 모든 서킷을 누락 없이 찾게 해줌.

활용: 여러 실제 문제(예: 전기회로 분석, 피드백 루프 탐색, 생물·사회 네트워크의 순환 구조 찾기 등)에서 방향 그래프의 모든 단순 사이클(기본회로)을 신속히 열거해야 할 때, Johnson 알고리즘이 유용하다.

6. 부록: 수식 정리

  1. 방향 그래프 기본

    • (G = (V, E)), (|V| = n, |E| = e).
    • 기본회로(사이클) 개수 (c).

  2. 시간 복잡도
    [
    T_\text{Johnson}(n, e, c) = O\bigl( (n + e)\,(c + 1)\bigr).
    ]

  3. 공간 복잡도
    [
    S_\text{Johnson}(n, e) = O(n + e).
    ]

  4. Tarjan 등 기존 알고리즘
    [
    T_\text{Tarjan}(n, e, c) = O\bigl( n\,e\,(c + 1)\bigr).
    ]

7. 참고문헌

  • Donald B. Johnson, "Finding All the Elementary Circuits of a Directed Graph," SIAM Journal on Computing, 4(1), 1975, pp. 77–84.
  • Robert Tarjan, “Enumeration of the elementary circuits of a directed graph,” SIAM J. Comput., 2(3), 1973, pp. 211–216.
  • Tiernan, "An efficient search algorithm to find the elementary circuits of a graph," Comm. ACM, 13(12), 1970, pp. 722–726.
  • 기타 논문...

이상으로, Johnson 알고리즘의 이론·구현·시간 복잡도 등을 설명했습니다. 주요 포인트는 “Blocked 집합과 B-list”를 통해 중복·불필요 탐색을 줄이고, 모든 엘리멘터리 서킷을 효율적으로 열거한다는 점입니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 all_circuits() 함수를 사용해, 방향 그래프(Directed Graph) 내의 모든 회로(cycle) – 즉 엘리멘터리 서킷을 효율적으로 열거하는 방법을 설명합니다. (참고로 언다이렉트 그래프도 내부적으로 양방향 간선을 가진 것으로 취급하여 순회합니다.)
또한 튜토리얼에서는 파이썬 예시 코드, 자세한 한글 주석, 그리고 추가 팁 등을 중점적으로 다뤄, 네트워크 분석 초보자도 쉽게 따라할 수 있도록 했습니다.

1. all_circuits() 함수 개요

all_circuits(g, unique=False)

  • 입력:

    • g: Graph 객체(방향 그래프 권장; undirected도 허용하지만 내부적으로 양방향 간선처럼 취급)
    • unique: (bool, 기본값=False)
      • True일 경우, 멀티 간선(parallel edges)과 자기 루프(self-loop) 무시

  • 출력:

    • cycle_iterator
      • 회로(사이클)을 이루는 정점들의 시퀀스를 순차적으로 반환하는 이터레이터(iterator)

  • 특징

    • 알고리즘은 Johnson (1975) 알고리즘을 기반으로, 모든 엘리멘터리 회로(단순 사이클)를 중복 없이 효율적으로 열거
    • 이터레이터이므로, 한 번에 모든 사이클을 메모리에 담지 않고 순차적으로 회로를 꺼낼 수 있어, 큰 그래프에서도 유용
    • 최악 시간 복잡도:
      [
      O\bigl((n + e) \,(c + 1)\bigr),
      ]
      여기서 (n)은 정점 수, (e)는 간선 수, (c)는 회로 개수.

  • 주의

    • 반환 형식이 정점의 인덱스가 들어 있는 numpy 배열(array) 형태 (예: [0 3 5])
    • 매번 새로운 회로 하나씩 yield (이터레이터)
    • 중복 없이 모든 회로를 찾음. (엘리멘터리 서킷)

2. 기본 예시

2.1 무작위 작은 방향 그래프 생성 후 모든 회로 출력

아래 코드는 작은 방향 그래프를 랜덤으로 만든 뒤, all_circuits()를 호출하여 회로를 출력하는 예시입니다.

import graph_tool.all as gt
import numpy as np

def example_all_circuits_basic():
    # 1) 무작위 방향 그래프 생성: 노드 10개, 각 노드 기대 차수 1
    # directed=True로 명시 or 생략 가능(기본=False인 경우도 있음)
    g = gt.random_graph(10, lambda: (1,1), directed=True)
    
    # 2) 모든 사이클 탐색
    circuits_iterator = gt.all_circuits(g, unique=False)
    
    # 3) 결과 출력
    print("All circuits in the directed graph:")
    count = 0
    for cycle in circuits_iterator:
        count += 1
        print(f"Cycle {count}:", cycle)
    
    if count == 0:
        print("No circuit found.")

if __name__=="__main__":
    example_all_circuits_basic()

2.2 코드 해설

  1. 그래프 생성
    • random_graph(10, lambda: (1,1), directed=True): 정점 10개, 각 정점 기대 out-degree=1 근사 (조금 희소한 방향 그래프)
  2. gt.all_circuits(g, unique=False)
    • 회로를 순차적으로 반환하는 이터레이터.
    • unique=False면 멀티 간선, self-loop 등을 고려.
    • for 문에서 cycle은 예: [0 6], [1 5 4] 등 numpy 배열
  3. 출력된 사이클이 없으면 "No circuit found." 출력.

3. Undirected Graph(무방향 그래프) 사용 시

all_circuits()는 내부적으로 무방향 그래프를 양방향으로 간주해 처리합니다.

  • 예시: 무방향 그래프 하나 구성 → all_circuits() → 실제로는 (u->v, v->u) 식으로 다룰 것.
def example_all_circuits_undirected():
    # 1) 무방향 그래프
    g = gt.random_graph(5, lambda: (2,2), directed=False)

    # 2) 사이클 열거
    for i, cyc in enumerate(gt.all_circuits(g), 1):
        print(f"Undirected cycle {i}:", cyc)

    # 이터레이터 다 소진 후 종료

주의: 무방향 시, 간선 ((u,v))와 ((v,u)) 모두 존재한다고 보고, 그에 따른 사이클 인식이 달라질 수 있음.

4. unique=True 옵션

  • 사이클에 평행 간선이나 self-loop가 있으면, 이들을 무시하여 사실상 유니크한 간선 구조만 인식.
  • 일반적으로 병렬 간선이 없거나 self-loop가 없다면 차이 없음.
def example_all_circuits_unique():
    g = gt.Graph(directed=True)
    v = [g.add_vertex() for _ in range(4)]
    # 예: 병렬 간선
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[0], v[1])  # parallel edge
    e3 = g.add_edge(v[1], v[2])
    e4 = g.add_edge(v[2], v[0])
    
    circuits_iter = gt.all_circuits(g, unique=True)
    # parallel edge (0->1) 2개 중 1개만 고려
    
    for cyc in circuits_iter:
        print("Unique cycle:", cyc)

5. 알고리즘 내부 (Johnson 1975)

  • all_circuits() 함수 내부적으로는 Johnson’s Algorithm (Donald B. Johnson, 1975) 사용.
  • 시간 복잡도: 최악 ((n+e)(c+1)).
  • Blocked / B-list 구조 + DFS를 통해 중복 없이 모든 엘리멘터리 사이클을 찾음.
  • 자세한 개념은 논문 ([johnson-finding-1975]) 참고.

6. 반환 형식과 활용

  • 이터레이터를 통해 회로(numpy array) 하나씩 반환
  • 각 회로: 예) [1, 5, 4, 1] (끝점과 시작점이 같으니 보통 마지막 원소 = 처음 원소)
  • 분석 시:
    • “사이클 길이 분포”,
    • “사이클에 어떤 노드·간선이 얼마나 자주 등장?”
    • 등등이 가능

6.1 메모리·성능 팁

  • 회로 수 (c)가 많다면, 이터레이션 자체가 (O(c)) 단계를 가짐.
  • 그래프가 매우 큰데도 (c)가 상당히 많을 수 있으니, 실질적 사용 시 메모리와 시간 고려 필요.
  • 이터레이터 특성상, 한 번에 하나씩 꺼내서 처리 가능 → 대규모 그래프에서도 부분적 분석 가능.

7. 예시: 회로 전체를 리스트로 모으기 (주의)

이터레이터를 한 번 순회하면 소진되므로, 만약 모두 리스트에 담고 싶다면:

def example_store_all_circuits():
    g = gt.random_graph(6, lambda: (2,2), directed=True)

    all_cycles = list(gt.all_circuits(g))
    # 이 시점에 모든 사이클을 한꺼번에 저장.
    
    print("Total circuits found:", len(all_cycles))
    for cyc in all_cycles:
        print("Cycle:", cyc)
  • 경고: 회로가 많으면(예: 완전그래프) 리스트가 매우 커질 수 있음.
  • 일반적으론 그냥 이터레이터를 사용하면서 온라인(online)처리 권장.

8. 추가: all_paths() vs all_circuits()

  • all_paths(): 특정 source→target의 모든 경로(길이 cutoff 이하)를 DFS로 찾음 → 사이클 포함이지만, 사이클 아닌 경로도 전부
  • all_circuits(): 그래프 전체의 엘리멘터리 사이클만 전부
  • 목적에 따라 다른 함수를 사용

9. 정리

all_circuits()는 방향 그래프 내 모든 사이클(기본회로)를 이터레이터 형태로 반환합니다:

  1. 사용법: 
    for cycle in all_circuits(g, unique=...):
    ...
  2. 알고리즘: Johnson(1975) 기반, 최악에도 (O((n+e)(c+1))) 시간 복잡도
  3. 주의: 사이클이 많을 경우 시간·메모리 부담. → 이터레이터 활용으로 부분 처리 가능
  4. unique=True → 병렬 간선·자기 루프 무시

이상입니다. graph-tool의 all_circuits() 함수를 통해 효율적이고 편리하게 사이클 열거를 할 수 있으며, 네트워크 구조 내에 존재하는 모든 순환 패턴을 분석하는 등 다양한 연구·실무에 활용 가능합니다.

아래 튜토리얼은 graph-tool 라이브러리에서 제공하는 pseudo_diameter() 함수를 이용하여, 그래프의 의사-지름(pseudo-diameter) 을 빠르게 추정(approximation)하는 방법을 설명합니다. 여기서 말하는 의사-지름이란, 그래프의 정확한 지름(diameter)을 구하는 대신, 간단한 BFS/Dijkstra 기반 반복 탐색만으로 “대체로 긴 거리”를 갖는 두 정점을 찾는 기법입니다.
초보자를 위해 파이썬 코드 예시, 자세한 한글 주석, 추가 팁 등을 포함하였으니 참고 바랍니다.

1. pseudo_diameter() 함수 개요

pseudo_diameter(g, source=None, weights=None)

  • 입력:

    • g: 그래프(Graph) 객체
    • source: (옵션) 시작 정점(g.vertex(i)). 미지정 시 그래프의 “첫 번째 정점”을 디폴트로 사용
    • weights: (옵션) 가중치(EdgePropertyMap). 없으면 BFS로, 있으면 Dijkstra로 거리 계산

  • 출력:

    1. dist: (float) 그래프의 의사-지름값(pseudo-diameter)
    2. ends: (pair of Vertex) 이 의사-지름을 만족하는, 혹은 가까운 두 정점

  • 알고리즘 개요:

    1. 임의 혹은 지정된 소스 정점 source에서 BFS(Dijkstra)를 수행, 가장 거리가 먼 정점 target 찾음
    2. target을 새로운 소스로 하여 다시 BFS(Dijkstra) 수행, 다시 가장 먼 정점 찾음
    3. 위 과정을, 더 이상 거리 증가가 없을 때까지 반복
    4. 마지막 단계에서 “가장 마지막 레벨에 있는 정점 중 차수가 가장 작은 정점”을 소스로 한 번 더 수행하여 최종 거리 측정
    5. 그 거리를 “pseudo-diameter”로 취함

  • 시간복잡도:

    • 무가중(BFS) 시 (O(V+E))
    • 가중치(Dijkstra) 시 (O(E \log V))

2. 예시 1: 무가중 그래프에서 의사-지름 구하기

다음 코드는 무방향 그래프(무가중)에 대해 pseudo_diameter()를 수행하여 의사-지름과 해당 두 끝점 정점을 출력합니다.

import graph_tool.all as gt
import numpy as np

def example_pseudo_diameter_unweighted():
    # 1) 무작위 그래프(300 노드), 평균 차수 ~3, 무방향
    g = gt.random_graph(300, lambda: (3,3), directed=False)
    
    # 2) 의사-지름 계산 (BFS 활용)
    dist, ends = gt.pseudo_diameter(g)
    # dist: pseudo-diameter(float), ends: (vertex1, vertex2)
    
    print("Pseudo-diameter:", dist)
    print("End vertices:", int(ends[0]), int(ends[1]))
    
if __name__ == "__main__":
    example_pseudo_diameter_unweighted()

2.1 코드 해설

  1. 그래프 생성: random_graph(300, (3,3), directed=False) → 300개 정점, 각 정점 기대 차수 ~3.
  2. pseudo_diameter(g) → 무가중이므로 BFS 이용해서 의사-지름 탐색.
  3. 반환값:
    • dist (float 형), 의사-지름.
    • ends는 2개 정점(Vertex) 튜플. 예: (Vertex(0), Vertex(157)).
  4. 이 두 정점 사이의 실제 거리(최단거리)는 dist와 동일 또는 근접.

3. 예시 2: 가중치(양수) 그래프에서 의사-지름 구하기

def example_pseudo_diameter_weighted():
    # 1) 방향 그래프 생성
    g = gt.Graph(directed=True)
    
    # 2) 정점 5개
    v = [g.add_vertex() for _ in range(5)]
    
    # 3) 임의 간선 추가
    e1 = g.add_edge(v[0], v[1])
    e2 = g.add_edge(v[1], v[2])
    e3 = g.add_edge(v[2], v[3])
    e4 = g.add_edge(v[0], v[4])
    e5 = g.add_edge(v[3], v[4])

    # 4) 가중치 property (double)
    wprop = g.new_edge_property("double")
    wprop[e1] = 2.0
    wprop[e2] = 1.5
    wprop[e3] = 3.0
    wprop[e4] = 4.2
    wprop[e5] = 1.0

    # 5) pseudo_diameter, Dijkstra 이용
    dist, ends = gt.pseudo_diameter(g, weights=wprop)
    
    print("Pseudo-diameter (weighted):", dist)
    print("End vertices:", int(ends[0]), int(ends[1]))

if __name__=="__main__":
    example_pseudo_diameter_weighted()
  • 이 경우, Dijkstra 알고리즘을 통해 “최대 거리를 갖는 정점 쌍”을 점진적으로 찾는 과정을 반복.
  • 반환된 dist는 부동소수점 값.

4. 특정 소스 정점을 지정하기

def example_pseudo_diameter_with_source():
    g = gt.random_graph(50, lambda: (2,2), directed=False)
    
    # 예: g.vertex(10)를 source로 지정
    src = g.vertex(10)
    
    dist, ends = gt.pseudo_diameter(g, source=src)
    print("Pseudo-diameter from src=10:", dist)
    print("Ends:", int(ends[0]), int(ends[1]))
  • source=src로 시작해 그 반대편 정점(target)을 찾고, 그 target을 다시 소스로… 방식.
  • 특정 정점을 기준으로 멀리 떨어진 곳을 빨리 찾고자 할 때 유용.

5. 알고리즘 내부 요약

  1. (BFS or Dijkstra): source에서 가장 먼 정점 target 찾음
  2. target을 새로운 소스로 동일 과정 반복
  3. 거리 증가가 없을 때까지 계속 → 최종 “가장 먼 쌍”이 의사-지름(pseudo-diameter)
  4. 마지막에 레벨 집합이 여러 개 있을 수 있는데, 그 중 차수가 가장 작은 정점을 “새로운 source”로 한 번 더 점검.

결과적으로, 정확한 지름(모든 쌍 최단거리) 계산보다는 훨씬 빠르고(복잡도 (\mathrm{O}(V+E)) 혹은 (\mathrm{O}(E \log V))), 대규모 그래프에서도 쉽게 최대 거리 근사치를 얻을 수 있음.

6. 시간 복잡도와 팁

  • 시간:
    • 무가중 시 BFS: (\mathrm{O}(V+E))
    • 가중치 시 Dijkstra: (\mathrm{O}(E \log V))
  • 유용성: 그래프의 정확한 지름(diameter)을 구하려면 전체 쌍 shortest path(Johnson/Floyd-Warshall) 필요 → (\mathrm{O}(V \times E\log V)) 혹은 (\mathrm{O}(V^3)). 대규모 그래프에선 비현실적.
  • 따라서: pseudo_diameter()로 근사(approximation)하여, 대략적인 “최대 거리”를 얻는 것이 효율적.

7. 응용: 그래프 시각화에서 “가장 먼 두 점” 자동 선택

  • 네트워크 시각화(예: 도시/교통망) 시, “가장 떨어진 두 도시”를 찾고 싶을 때 유용
  • 의사-지름으로 선정된 두 점은 종종 “layout” 알고리즘에서 초기 anchor로도 사용됨.

8. 마무리

pseudo_diameter()는

  1. 단일 source에서 BFS/Dijkstra로 “가장 먼 정점” 추적,
  2. 그 “가장 먼 정점”을 새 source로 반복,
  3. 마지막 정밀(?) 조정 후, 가장 먼 거리를 pseudo-diameter로 삼음

이라는 접근으로 그래프의 최대 거리(지름)를 빠르게 근사할 수 있습니다. 대규모 그래프에서도 비교적 쉽고 빠르게 “거의 최대 거리”를 찾기에 적합합니다.

  • 요약:
    • 함수 호출: 
      dist, ends = gt.pseudo_diameter(g, source=None, weights=None)
    • 결과: (dist, (vA, vB)) → 의사-지름과 해당 양 끝점
    • 무가중이면 BFS, 가중치면 Dijkstra

실무/연구 등에서 그래프의 지름(diameter)이 필요하지만, “정확 계산은 너무 비싸다” 싶을 때 pseudo_diameter 로 근사값을 사용하는 방법을 추천합니다.

profile
Sylen
AI가 재밌는 걸
이전 포스트

graph_tool.stats

다음 포스트

graph_tool.topology 2 Graph comparison

0개의 댓글