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次の隔たり)、練習問題(パズル問題4)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3
def is_symmetry(graph: dict) -> bool:
    '''
    >>> is_symmetry({})
    True
    >>> is_symmetry({'a': ['b']})
    False
    >>> is_symmetry({'a': ['b'], 'b': {'a'}})
    True
    >>> is_symmetry({'a':['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']})
    True
    >>> is_symmetry({'a':['b', 'c'], 'b': ['a'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']})
    False
    '''
    for k, v in graph.items():
        for t in v:
            if t not in graph or k not in graph[t]:
                return False
    return True


def degrees_of_pair(
        graph: dict, start: str, end: str, visited: set = None) -> int:
    '''
    >>> smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
    >>> d = {k: [a for a, _ in v] for k, v in smallw.items()}
    >>> is_symmetry(d)
    True
    >>> degrees_of_pair(smallw, 'a', 'c', set())
    2
    >>> degrees_of_pair(smallw, 'a', 'f', set())
    5
    '''
    if visited is None:
        visited = set()
    visited_tmp = visited | {start}
    degrees = None
    for node, weight in graph[start]:
        if node in visited_tmp:
            continue
        if node == end:
            if degrees is None or weight < degrees:
                degrees = weight
        else:
            degrees_tmp = degrees_of_pair(graph, node, end, visited_tmp)
            if degrees_tmp == -1:
                continue
            degrees_tmp += weight
            if degrees is None or degrees_tmp < degrees:
                degrees = degrees_tmp
    if degrees is None:
        return -1
    return degrees


def degrees_of_separation(graph: dict, start: str) -> int:
    '''
    >>> smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
    >>> degrees_of_separation(smallw, 'a')
    5
    >>> degrees_of_separation(smallw, 'b')
    4
    '''
    max_degrees = 0
    for end in graph:
        degrees = degrees_of_pair(graph, start, end)
        if degrees > max_degrees:
            max_degrees = degrees
    return max_degrees


if __name__ == '__main__':
    import doctest
    doctest.testmod()

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

C:\Users\...>py -3 sample4.py -v
Trying:
    smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
Expecting nothing
ok
Trying:
    d = {k: [a for a, _ in v] for k, v in smallw.items()}
Expecting nothing
ok
Trying:
    is_symmetry(d)
Expecting:
    True
ok
Trying:
    degrees_of_pair(smallw, 'a', 'c', set())
Expecting:
    2
ok
Trying:
    degrees_of_pair(smallw, 'a', 'f', set())
Expecting:
    5
ok
Trying:
    smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
Expecting nothing
ok
Trying:
    degrees_of_separation(smallw, 'a')
Expecting:
    5
ok
Trying:
    degrees_of_separation(smallw, 'b')
Expecting:
    4
ok
Trying:
    is_symmetry({})
Expecting:
    True
ok
Trying:
    is_symmetry({'a': ['b']})
Expecting:
    False
ok
Trying:
    is_symmetry({'a': ['b'], 'b': {'a'}})
Expecting:
    True
ok
Trying:
    is_symmetry({'a':['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']})
Expecting:
    True
ok
Trying:
    is_symmetry({'a':['b', 'c'], 'b': ['a'], 'c': ['a', 'b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f':['d', 'e']})
Expecting:
    False
ok
1 items had no tests:
    __main__
3 items passed all tests:
   5 tests in __main__.degrees_of_pair
   3 tests in __main__.degrees_of_separation
   5 tests in __main__.is_symmetry
13 tests in 4 items.
13 passed and 0 failed.
Test passed.

C:\Users\...>