Algorithm - Python - 6次の隔たり - 集合演算、集合を使ったグラフの幅優先探索(節点対の隔たり、グラフの隔たり、次数)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の20章(6次の隔たり)、練習問題(問題1)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3
def degrees_of_pair(graph: dict, start: str, end: str) -> int:
    '''
    >>> degrees_of_pair(small, 'c', 'b')
    1
    >>> degrees_of_pair(small, 'c', 'd')
    2
    '''
    if start not in graph:
        return -1
    visited = {start}
    frontier = {start}
    degress = 0
    while frontier:
        degress += 1
        new_frontier = set()
        for g in frontier:
            if end in graph[g]:
                return degress
            s = set(graph[g]) - visited
            visited |= s
            new_frontier |= s
        frontier = new_frontier
    return degress - 1


def degrees(graph: dict) -> int:
    '''
    >>> degrees(small)
    3
    '''
    degrees = max([degrees_of_pair(graph, k1, k2)
                   for k1 in graph
                   for k2 in graph
                   if k1 < k2])
    return degrees


if __name__ == '__main__':
    import doctest
    small = {'a': ['b', 'c'],
             'b': ['a', 'c', 'd'],
             'c': ['a', 'b', 'e'],
             'd': ['b', 'e'],
             'e': ['c', 'd', 'f'],
             'f': ['e']}
    globs = globals()
    globs.update({'small': small})
    doctest.testmod(globs=globs)

入出力結果(cmd(コマンドプロンプト)、Terminal、Jupyter(IPython))

C:\Users\...>py -3 sample1.py -v
Trying:
    degrees(small)
Expecting:
    3
ok
Trying:
    degrees_of_pair(small, 'c', 'b')
Expecting:
    1
ok
Trying:
    degrees_of_pair(small, 'c', 'd')
Expecting:
    2
ok
1 items had no tests:
    __main__
2 items passed all tests:
   1 tests in __main__.degrees
   2 tests in __main__.degrees_of_pair
3 tests in 3 items.
3 passed and 0 failed.
Test passed.

C:\Users\...>