파이썬 SciPy 그래프

파이썬 SciPy 그래프

그래프는 필수적인 데이터 구조이다.

SciPy는 이러한 데이터 구조를 사용하기 위한 scipy.sparse.csgraph 모듈을 제공한다.

 

파이썬 SciPy 인접 행렬(Adjacent matrix)

인접 행렬은 nxn 행렬이다. 여기서 n은 그래프의 요소 수이다.

그리고 값은 요소 간의 연결을 나타낸다.

예제:

인접 행렬

 

이와 같은 그래프의 경우, 원소 A, B, C를 사용하면 연결은 다음과 같다:

A & B는 무게 1로 연결되어 있다.
A&C는 무게 2로 연결되어 있다.
C&B가 연결되어 있지 않다.

인접 행렬은 다음과 같다:

A B C    A:[0 1 2]      B:[1 0 0]    C:[2 0 0]

 

아래는 인접 행렬을 사용할 때 가장 많이 사용되는 몇 가지 방법을 따른다.

 

파이썬 SciPy 그래프 연결된 컴포넌트

connected_components() 메서드로 연결된 모든 구성 요소를 찾는다.

import numpy as np from scipy.sparse.csgraph import connected_components from scipy.sparse import csr_matrix arr = np.array([   [0, 1, 2],   [1, 0, 0],   [2, 0, 0] ]) print('arr : \n', arr) newarr = csr_matrix(arr) print('newarr = csr_matrix(arr)\n') print('connected_components(newarr) : \n', connected_components(newarr))

위의 코드를 실행하면 아래 그림과 같다.

파이썬 SciPy  그래프  connected_components() 활용 예제

 

파이썬 SciPy 그래프 Dijkstra

dijkstra 방법을 사용하여 한 원소에서 다른 원소로 가는 그래프에서 가장 짧은 경로를 찾는다.

다음과 같은 인수가 필요합니다:

return_precedors: boolean(트래버설의 전체 경로를 반환하려면 True). 그렇지 않으면 False이다.
indices: 해당 요소의 모든 경로만 반환하는 요소의 인덱스이다.
limit: 경로의 최대 가중치.

요소 1에서 요소 2까지의 최단 경로 찾기:

import numpy as np from scipy.sparse.csgraph import dijkstra from scipy.sparse import csr_matrix arr = np.array([   [0, 1, 2],   [1, 0, 0],   [2, 0, 0] ]) print('arr : \n', arr) newarr = csr_matrix(arr) print('dijkstra(newarr, return_predecessors=True, indices=0) : \n', dijkstra(newarr, return_predecessors=True, indices=0))

위의 코드를 실행하면 아래 그림과 같다.

파이썬 SciPy  그래프  dijkstra () 활용 예제

 

파이썬 SciPy 그래프 Floyd Warshall

floyd_warshall() 메소드를 사용하여 모든 요소 쌍 사이의 최단 경로를 찾는다.

모든 원소 쌍 사이의 최단 경로를 찾는다:

import numpy as np from scipy.sparse.csgraph import floyd_warshall from scipy.sparse import csr_matrix arr = np.array([   [0, 1, 2],   [1, 0, 0],   [2, 0, 0] ]) print('arr : \n', arr) newarr = csr_matrix(arr) print('floyd_warshall(newarr, return_predecessors=True) : \n', floyd_warshall(newarr, return_predecessors=True))

위의 코드를 실행하면 아래 그림과 같다.

파이썬 SciPy  그래프  floyd_warshall () 활용 예제

 

파이썬 SciPy 그래프 Bellman Ford

bellman_ford() 방법은 모든 원소 쌍 사이에서 가장 짧은 경로를 찾을 수도 있지만, 이 방법은 음의 가중치도 처리할 수 있다.

음의 가중치를 가진 주어진 그래프를 사용하여 원소 1에서 2까지의 최단 경로를 찾는다:

import numpy as np from scipy.sparse.csgraph import bellman_ford from scipy.sparse import csr_matrix arr = np.array([   [0, -1, 2],   [1, 0, 0],   [2, 0, 0] ]) print('arr : \n', arr) newarr = csr_matrix(arr) print('bellman_ford(newarr, return_predecessors=True, indices=0)') print(bellman_ford(newarr, return_predecessors=True, indices=0))

위의 코드를 실행하면 아래 그림과 같다.

파이썬 SciPy 그래프 bellman_ford () 활용 예제

 

파이썬 SciPy 그래프 검색 - 깊이우선 검색(Depth first order)

depth_first_order() 메서드는 노드에서 depth 첫 번째 순회를 반환한다.

이 함수는 다음 인수를 사용한다:
그래프.
그래프를 횡단할 시작 요소이다.

주어진 인접 행렬에 대해 그래프 깊이를 먼저 횡단한다:

import numpy as np from scipy.sparse.csgraph import depth_first_order from scipy.sparse import csr_matrix arr = np.array([   [0, 1, 0, 1],   [1, 1, 1, 1],   [2, 1, 1, 0],   [0, 1, 0, 1] ]) print('arr : \n', arr) newarr = csr_matrix(arr) print('\ndepth_first_order(newarr, 1)') print(depth_first_order(newarr, 1))

위의 코드를 실행하면 아래 그림과 같다.

파이썬 SciPy 그래프 depth_first_order () 활용 예제

 

파이썬 SciPy 그래프 검색 - 너비우선 검색(Breadth first order)

width_first_order() 메서드는 노드에서 width 첫 번째 순회를 반환한다.

이 함수는 다음 인수를 사용한다:
그래프.
그래프를 횡단할 시작 요소입니다.

주어진 인접 행렬에 대해 그래프 너비를 먼저 탐색합니다:

import numpy as np from scipy.sparse.csgraph import breadth_first_order from scipy.sparse import csr_matrix arr = np.array([   [0, 1, 0, 1],   [1, 1, 1, 1],   [2, 1, 1, 0],   [0, 1, 0, 1] ]) print('arr : \n', arr) newarr = csr_matrix(arr) print('breadth_first_order(newarr, 1)') print(breadth_first_order(newarr, 1))

위의 코드를 실행하면 아래 그림과 같다.

파이썬 SciPy 그래프 breadth_first_order () 활용 예제

 

이번 글에서는 파이썬 SciPy 그래프에 대해서 살펴보았다.

파이썬 SciPy 그래프를 행렬로 표현하는 connected_matrxi() 메소드, connected_component() 메소드, 그래프의 가장 짧은 검색을 위해 dijkstra() 메소드, floyd_warsahll(), bellman_ford(), depth_first_order(), breadth_first_order() 메소드 관련 실습을 하였다.

꼭 손으로 눈으로 머리로 익히며 실습하기를 바란다.

모두 화이팅입니다.!!!

 

출처 : 이 글의 출처는 w3schools사이트를 참고하였으며 필자가 추가하여 정리한 글입니다.