데이터 과학 유망주의 매일 글쓰기 — 82일차
데이터 구조로써의 그래프(Graph)
# Graph, #그래프, # Vertices, # Edges
오늘 한일:
오늘은 그래프(Graph)라는 데이터 구조에 대해 학습했다. 나는 그래프란 단순히 시각화 도구로써, 데이터를 이어 붙여 x-y 평면 등에서 시각화 한 것으로 알고 있었다. 하지만, 그것은 데이터 과학에서의 그래프의 의미에 가깝다. 컴퓨터 과학에서는 조금 다른 의미로 받아들여진다. 컴퓨터 과학에서는, 가장 기본적이면서도 중요한 데이터 구조이기 때문이다.
데이터의 구조는 네트워크(network)와 닮아있다. 한 노드에서 다른 노드로 이어지는 길이 있고, 그 길은 순환형(cyclic)이거나 비순환형(acyclic)이다. 또한 한방향(unidirectional) 또는 양방향(bidirectional) 형의 그래프가 있을 수 있고, 이렇게 방향이 있는 그래프는 directed 그래프라고 한다. 반대로, 방향성이 없는 경우는 undirected 그래프라고 한다. 데이터 구조로써의 그래프를 조금 더 자세히 알아보자.
그래프(Graph)
단순하게 그래프는, 특정한 개체들 사이의 연결로 이루어진 것을 말한다. 서로 이어진 개체들은 vertice라는 이름으로 부르며, 이들을 이어주는 것을 edge라고 부른다.
그래프는 보통 아래와 같은 과정으로 프로그래밍되어 구현된다.
- 그래프의 vertice 표현
- 그래프의 edge 표현
- vertice 추가(필요시)
- edge 추가(필요시)
- 그래프 생성
그래프는 Dictionary를 통해 표현될 수 있는데, 보통 key를 vertice로 하며, value는 edge를 나타내는 방식으로 표현한다. 예를 들어 아래와 같은 그래프를 보자.
위 그래프는 아래와 같이 표현할 수 있다.
v = {1, 2, 3, 4, 5}
e = {12, 13, 21, 24, 25, 31, 42, 52}
이를 파이썬 프로그램으로 표현하자면 아래와 같다. 아래는 그래프의 key인 각 vertice가, 연결되는 노드의 목록을 value로 저장하는 형태의 인접리스트(adjacent list)다.
# 그래프 Dictionary# 그래프 아이템의 Dictionary 설정graph_elements = {1: {"2", "3"},2: {"1", "4", "5"},3: {"1"},4: {"2"},5: {"2"}}# 그래프 출력
print(graph)>> {1: {2, 3}, 2: {1, 4, 5}, 3: {1}, 4: {2}, 5: {2}}
그래프의 vertice 표현
그렇다면 그래프를 그리기 위해, 먼저 그래프의 vertices를 인접리스트를 이용해 표현해보자.
# 그래프의 vertices 표현# graph Dictionary를 생성하기 위한 인접리스트 클래스 선언
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = []
self.gdict = gdict # graph Dictionary의 Key값 접근
def getVertices(self):
return list(self.gdict.keys())# 그래프 인접리스트 설정graph_elements = {1: {"2", "3"},2: {"1", "4", "5"},3: {"1"},4: {"2"},5: {"2"}}# 그래프의 인접리스트화(인접리스트 클래스 인스턴스화, Dictionary를 인자로 활용)
g = graph(graph_elements)# 그래프의 Vertice 출력
print(g.getVertices())>> [1, 2, 3, 4, 5]
그래프의 edge 표현
다음으로, 그래프의 edge를 그려보자. 이것은 좀 더 어려운 과정인데, 사이에 edge를 둔 모든 vertice를 찾아야하기 때문이다. 일단 edge를 저장할 empty list를 선언한다. 이 리스트는 각 vertice에 존재하는 모든 유니크한 edge를 저장한다.
# 그래프의 vertice와 edge를 객체화하기 위한 클래스 선언
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def edges(self):
return self.findedges()# 유니크한 edge를 리스트로 저장할 함수
def findedges(self):
edgename = []
for vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
if {nxtvrtx, vrtx} not in edgename:
edgename.append({vrtx, nxtvrtx})
return edgename
# 그래프 인접리스트 설정graph_elements = {1: {"2", "3"},2: {"1", "4", "5"},3: {"1"},4: {"2"},5: {"2"}}# 인접리스트를 활용해 그래프를 객체화
g = graph(graph_elements)# 그래프의 Edge 표현
print(g.edges())>> [{1, '3'}, {1, '2'}, {'5', 2}, {2, '4'}, {2, '1'}, {3, '1'}, {4, '2'}, {5, '2'}]
앞에 오는 수는 edge의 시작점, 뒤에 오는 수는 edge의 도착점을 말한다. 예를 들어, {1, ‘3’}은 vertice 1에서 3으로 가는 edge며, {3, ‘1’}은 vertice 3에서 1로 가는 edge다. 그러므로 둘은 서로 다른 방향성을 가진 유니크한 edge다.
Vertice 더하기
만약 그래프에 추가적인 vertice를 더하기를 원한다면, 아래와 같이 구현할 수 있다.
# 그래프 vertice 접근을 위한 클래스 선언
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def getVertices(self):
return list(self.gdict.keys())
# vertex를 key로 더하기
def addVertex(self, vrtx):
if vrtx not in self.gdict:
self.gdict[vrtx] = []
# 그래프 인접리스트 설정
graph_elements = {1: {"2", "3"},2: {"1", "4", "5"},3: {"1"},4: {"2"},5: {"2"}}# 인접리스트를 활용해 그래프를 객체화
g = graph(graph_elements)
# vertice 더하기
g.addVertex(6)
# 모든 vertice 출력
print(g.getVertices())>> [1, 2, 3, 4, 5, 6]
Edge 더하기
이미 존재하는 그래프에 추가적인 edge를 더하려면, 새로운 vertice를 tuple로 간주하고, 더하려는 edge가 이미 있는지를 확인한다. edge가 없을 경우 추가하는 방식이다.
# 그래프의 Edge에 접근하기 위한 클래스 선언
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def edges(self):
return self.findedges()# 새로운 edge를 더하는 함수
def AddEdge(self, edge):
edge = set(edge)
(vrtx1, vrtx2) = tuple(edge)
if vrtx1 in self.gdict:
self.gdict[vrtx1].add(vrtx2)
else:
self.gdict[vrtx1] = [vrtx2]
# 모든 edge에 접근하는 함수
def findedges(self):
edgename = []
for vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
if {nxtvrtx, vrtx} not in edgename:
edgename.append({vrtx, nxtvrtx})
return edgename
# 그래프 인접리스트 설정graph_elements = {1: {"2", "3"},2: {"1", "4", "5"},3: {"1"},4: {"2"},5: {"2"}}# 인접리스트를 활용해 그래프를 객체화
g = graph(graph_elements) # '1'에서 '4'로 edge 연결
g.AddEdge({'1','4'}) # '1'에서 '3'으로 edge 연결
g.AddEdge({'1','3'})# 모든 edge 출력
print(g.edges())# 이전 결과와 비교해 {1, '4'}가 추가됨 ({1, '3'}은 이미 있으므로 추가되지 않음)>> [{1, '4'}, {1, '3'}, {1, '2'}, {'5', 2}, {2, '4'}, {2, '1'}, {3, '1'}, {4, '2'}, {5, '2'}]# 이전 결과;
# [{1, '3'}, {1, '2'}, {'5', 2}, {2, '4'}, {2, '1'}, {3, '1'}, {4, '2'}, {5, '2'}]
그래프 그리기
이렇게 해서 모든 edge 정보와 vertice 정보가 주어졌으니 이제는 그래프를 그릴 수 있다. 이전에 더한 새로운 edge(1에서 4로 연결)를 반영하여 그래프를 수정하면 아래와 같다.
앞으로 할일:
오늘은 그래프라는 데이터 구조에 대해 공부해 보았다. 그래프가 사실 시각화 툴이 아닌 전혀 다른 의미를 가지고 있는지 생각조차 하지 못했다. 하지만, 시각화 분야에서의 그래프와도 어떻게 보면 연결이 되는 것 같다. 하나의 데이터 포인트에서 다른 데이터 포인트로 이어지는 과정이 x-y 평면에 그려지는 그래프와 닮았기 때문이다. 또한 그래프에 따라 하나의 점이 여러다른 점에 연결될 수도 있다는 점을 감안하면, 혹시 “시각화 그래프”도 이러한 “그래프 데이터 구조”를 참조한 것이 아닌가 하는 생각이든다.
사실, 이전 과정에서 배웠던 딥러닝의 신경망(Neural Network)역시 이러한 그래프의 구조를 모사하고 있다. 일반적으로 Edge에도 값이 존재하는데, 이 것을 가중치(weight)라고 한다. 이는, 딥러닝에서 역전파(Backpropagation)를 통해 가중치를 업데이트 하는 것과 상당히 관계가 있어 보인다. 딥러닝에서는 edge가 아닌 vertice같은 노드에 있는 가중치였지만.
그렇게 보니, 정말 모든 것이 연결되어 있다는 생각이든다. 이 프로그램의 첫 과정인 통계학 부분부터, 모든 것은 상당히 연관되어 있었다. 데이터 사이언스와 컴퓨터 과학은 상당히 많은 교집합을 갖는다는 것을 깨달았다. 세상의 모든 지식은 서로 거미줄처럼 엮여있다. 예를 들어, 미학에서 가장 아름다움을 느끼는 비율은 수학과 연결되어 있다. 전혀 어울리지 않을 것 같은 학문 사이에도 상당한 교집합이 존재한다. 나는 많은 것을 배우며 그렇게 느낀다. 그래서, 우리가 살면서 경험하고 배워온 모든 것들이 가치가 있다는 사실을 다시 한번 깨닫게 된다. 그렇기에, 모든 배움에 순간에 소홀해서는 안되겠다는 생각이든다. 그때 그때 배운 것들이 나중에 나를 어떻게 도와줄 수 있을지 모르니, 매 순간 새로운 것을 배울 수 있음에 감사하고, 또 적극적으로 배워야겠다고 다짐한다.
내일은 또 어떤 새로운 개념에서, 이전에 배웠던 것들과의 연관성을 보게될까? 과정의 마지막에 거의 들어서 모든 것의 연결을 보게되는 느낌이다. 이번 주 마지막까지 이 놀라운 피날레가 이어질 수 있으면 좋겠다.
내일도 새로운 발견을 기대하며.
참조:
(1) https://www.tutorialspoint.com/python_data_structure/python_graphs.htm
