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

コード

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


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

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

C:\Users\...>py -3 sample2.py -v
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__
1 items passed all tests:
   5 tests in __main__.is_symmetry
5 tests in 2 items.
5 passed and 0 failed.
Test passed.

C:\Users\...>