Eric Grimson, John Guttag, and Ana Bell. 6.0002 Introduction to Computational Thinking and Data Science. Fall 2016. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Lecture 3. Graph-theoretic Models
ある現実に存在するものや,抽象的な概念の集合(nodes)があって,それらの関係性(edges)を記述する方法にGraphがある.あるnodeから出るedgeを辿って他のnodeにたどり着けるとき,渡ってきたedgeたちをからへのpathという.edgeはnode間の関係性を表すが,必ずしも両方向でない関係性(好き嫌い,因果関係,所属)のような関係を記述するgraphをdirected graph(有向グラフ)といい,必ず両方向である関係(血縁,路線図)を記述するgraphをundirected graph(無向グラフ)という.undirected graphはdirected graphの特別な場合である.また,edge間に重みがつけられているgraphもある。.
特に重要なグラフの一種にtreeがある.treeでは任意の2つのedgeが一意のpathで結ばれている.
例
The network graph formed by Wikipedia editors (edges) contributing to different Wikipedia language versions (vertices) during one month in summer 2013
早速graphを実装する.
class Node(object):
def __init__(self, name):
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name
class Edge(object):
def __init__(self, src, dest):
""" Assumes src and dest are nodes"""
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def __str__(self):
return self.src.getName() + '->' \
+ self.dest.geName()
class Digraph(object): # directed graphのクラス
"""
edge is a dict mapping each node
to a list of its children.
"""
def __init__(self):
self.edges = {}
def addNone(self, node):
if node in self.edges:
raise ValueError('Duplicate node')
else:
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
if not (src in self.edges and dest in self.edges):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.edges
def getNode(self, name):
for n in self.edges:
if n.getName() == name:
return n
raise NameError(name)
def __str__(self):
result = ''
for src in self.edges:
for dest in self.edges[src]:
result = result + src.getName() + '->'\
+ dest.getName() + '\n'
return result[:-1] # omit final newline
class Graph(Digraph):
"""
transform a directed graph to a undirected graph
"""
def addEdge(self, edge):
Digraph.addEdge(self, edge)
rev = Edge(edge.getDestination(), edge.getSource())
Digraph.addEdge(self, rev)古典的なグラフ最適化問題に,最短経路問題がある.node1, node2を結ぶ最短のpathを見つける問題である.ループ構造がある可能性があるので,無限ループを避ける工夫が必要.depth-first search(深さ優先探索)とbreadth-first search(幅優先探索)がある.
Depth First search
初期nodeから辿れるpathを目的nodeに到達するか,到達しないと判明するまで(ループ構造は,辿ってきたpathを保存しておいて照合することで回避する)辿る.
def DFS(graph, start, end, path, shortest, toPrint=False):
path = path + [start]
if toPrint:
print('Current DFS path:', printPath(path))
if start == end:
return path
for node in graph.childrenOf(start):
if node not in path: #avoid cycles
if shortest == None or len(path) < len(shortest):
newPath = DFS(graph, node, end, path, shortest, toPrint)
if newPath != Node:
shortest = newPath
elif toPrint:
print('Already visited', node)
return shortest
def shortestPath(graph, start, end, toPrint=False):
""" a wrapper function of DFS"""
return DFS(graph, start, end, [], None, toPrint)Breadth-first Search(BFS)
初期nodeから長さnのpathのnodeに目的nodeがあるかすべて探索してから,長さn+1のpathのnodeたちを調べる.depth-first searchよりもふつう低速である.
def BFS(graph, start, end, toPrint=False):
initPath = [start]
pathQueue = [initPath]
while len(PathQueue) != 0:
tmpPath = pathQueue.pop(0)
if toPrint:
print('Current BFS path:', printPath(tmpPath))
lastNode = tmpPath[-1]
if lastNode == end:
return tmpPath
for nextNode in graph.childrenOf(lastNode):
if nextNode not in tmpPath:
newPath = tmpPath + [nextNode]
PathQueue.append(newPath)
return None
