응용그래프 (Applied Graph Theory) - Week 1
강의 개요와 목표
그래프 이론은 컴퓨터 과학의 가장 기본적이며 중요한 도구이다. 그래프 이론은 문제의 모형만들기와 그 해결에 사용되고 있다. 강의의 목표는 2가지로 하나는 그래프 이론 자체에 대한 이해로서 수학적인 접근을 해야 한다. 그 다음에는 실제 현실적인 문제를 그래프로 모형화하고 이것을 해결하는 그래프 알고리즘을 개발하는 것이다.
이번 강의의 목적은 컴퓨터 과학(공학)에서 흔히 볼 수 있는 여러 계산문제를 그래프에 기반하여 모델링하고, 이를 바탕으로 미리 개발된 그래프 알고리즘을 활용하여 해결하는 것이다
수강생들은 자신이 처음부터 모든 것을 설계, 구현하는 식으로 코드를 작성하려고 생각하지 말고 알고리즘의 기본적인 원리를 습득한 뒤, 이미 개발된 알고리즘를 활용하여 보다 높은 차원의 문제를 해결하면 실제 현장에서 효율적이다.
Graph Algorithm Tool (★)
Graph Visualization Tool (★)
실습
-
Graphviz
from graphviz import Digraph g = Digraph('G', filename='cluster.gv') # NOTE: the subgraph name needs to begin with 'cluster' (all lowercase) # so that Graphviz recognizes it as a special cluster subgraph with g.subgraph(name='cluster_0') as c: c.attr(style='filled') c.attr(color='lightgrey') c.node_attr.update(style='filled', color='white') c.edges([('a0', 'a1'), ('a1', 'a2'), ('a2', 'a3')]) c.attr(label='process #1') with g.subgraph(name='cluster_1') as c: c.node_attr.update(style='filled') c.edges([('b0', 'b1'), ('b1', 'b2'), ('b2', 'b3')]) c.attr(label='process #2') c.attr(color='blue') g.edge('start', 'a0') g.edge('start', 'b0') g.edge('a1', 'b3') g.edge('b2', 'a3') g.edge('a3', 'a0') g.edge('a3', 'end') g.edge('b3', 'end') g.node('start', shape='Mdiamond') g.node('end', shape='Msquare') g.view()
-
Networkx
import matplotlib.pyplot as plt import networkx as nx import numpy numpy.random.seed(9) G = nx.grid_2d_graph(4,4) #4x4 grid pos= nx.spring_layout(G,iterations=100) plt.subplot(221) nx.draw(G,pos,node_color='y',font_size=8) plt.subplot(222) nx.draw(G,pos,node_color='k',node_size=3,with_labels=True) plt.subplot(223) nx.draw(G,pos,node_color='r',node_size=250,with_labels=False,width=3) plt.subplot(224) H=G.to_directed() nx.draw(H,pos,node_color='b',node_size=20,with_labels=False) #plt.savefig("four_grids.png") plt.show()
-
GraphTea
과제
기하 그래프의 최단거리
[문제] 어떤 단순 그래프의 특정 두 지점 s 와 t 에 이르는 최단경로를 계산해서 이 경로를 그림으로 표시하는 Python 프로그램과 NetworkX의 알고리즘을 이용해서 작성하시오.
[입력] 입력파일의 이름은 graph.txt 이다. 입력 파일의 첫 줄에는 2개의 정수 N과 L이 주어진다. N은 정점(vertices)의 개수를 나타내고 L은 두 정점이 연결되는 제한 길이를 표시한다. 이어지는 N개의 줄에는 각 i 번째의 정점 V_i 의 위치좌표 (X_i, Y_i)의 두 정수 X_i, Y_i 가 주어진다. 정점의 번호는 1번부터 2, .. N으로 지정된다. 만일 두 정점 V_i 와 Y_i 의 거리가 L이하면 두 정점은 edge로 연결된다. 즉 아래를 만족하면 edge (i , j)가 생성된다.
여러분은 이렇게 생성된 그래프의 두 정점 s, t 사이의 shortest path를 다른 색으로 확인할 수 있도록 표현하여 그림으로 visualize해야 한다. 시작점, 도착점 s, t 는 입력파일 graph.txt의 제일 마지막 줄에 주어진다.
[조건] 입력되는 그래프의 정점의 개수는 10개 이상, 50개 이하이다. L에 따라서 최단거리가 없을 수도 있다.
코드
import matplotlib.pyplot as plt
import networkx as nx
import math
def getFile():
fp = open("graph.txt")
condition = fp.readline().replace('\n','').split(' ')
num_vertex, edge_condition = int(condition[0]) , float(condition[1])
vertexList = []
for i in range(num_vertex):
tmp = fp.readline().replace('\n','').split(' ')
tmp = [int(i) for i in tmp]
vertexList.append(tmp)
target_position = fp.readline().replace('\n', '').split(' ')
target_position = [int(i) for i in target_position]
return edge_condition,vertexList,target_position
def getGraph(graph,vertexList):
index = 1
for location in vertexList:
graph.add_node(index, color='black', pos=location)
index += 1
pos = nx.get_node_attributes(graph,'pos')
return graph, pos
def getDistance(tmp1, tmp2):
return math.hypot(tmp2[0] - tmp1[0], tmp2[1] - tmp1[1])
def getEdge(vertexList,limitEdge):
edgeList =[]
length = len(vertexList)
for i in range(length-1):
for j in range(i+1,length):
dist = getDistance(vertexList[i],vertexList[j])
if dist < limitEdge:
edgeList.append((i+1,j+1))
return edgeList
def main():
G = nx.Graph()
limitEdge , vertexList , position = getFile()
edgeList = getEdge(vertexList, limitEdge)
G,pos = getGraph(G,vertexList)
# To add distance between node
# if not : G.add_edges_from(edgeList , color = 'black') is simple.
for i in range(len(edgeList)):
first,second = vertexList[edgeList[i][0]-1], vertexList[edgeList[i][1]-1]
dist = getDistance(first,second)
G.add_edge(edgeList[i][0], edgeList[i][1], color='black', label=round(dist,3), weight=1)
start_Position,end_Position = position[0], position[1]
shortest_path_length = 0
if nx.has_path(G,start_Position,end_Position):
shortestPath = nx.shortest_path(G, start_Position, end_Position)
for i in range(len(shortestPath) - 1):
G.add_edge(shortestPath[i], shortestPath[i + 1], color='r', weight=3)
shortest_path_length += getDistance(vertexList[shortestPath[i]-1],vertexList[shortestPath[i+1]-1])
edges = G.edges()
colors = [G[u][v]['color'] for u, v in edges]
weights = [G[u][v]['weight'] for u, v in edges]
edge_labels = dict([((u, v,), d['label']) for u, v, d in G.edges(data=True)])
comment = str(shortest_path_length) if shortest_path_length != 0 else 'None'
plt.figure(num='LeeHoYong_graph.jpg')
nx.draw(G, pos, node_color = 'black', font_color='white', edge_color = colors, width = weights, with_labels=True)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.plot(0,0,'r',label='Shortest_Path_Length : ' + comment)
plt.legend()
plt.savefig('LeeHoYong_graph.jpg') # after installing [ pip install pillow ]
plt.show()
if __name__ == '__main__':
main()
결과
