MIT OCW 6.0002 02日目

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$v_1$から出るedgeを辿って他のnode$v_2$にたどり着けるとき,渡ってきたedgeたちを$v_1$から$v_2$への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