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

コード

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 route(graph: dict, start: str, end: str) -> list:
    '''
    >>> route({'a':['b'], 'b':['a']}, 'a', 'b')
    ['a', 'b']
    >>> route({'a':['b'], 'b':['a']}, 'b', 'a')
    ['b', 'a']
    >>> graph = {'a': ['b', 'c'], 'b': ['a', 'c', 'd'], 'c': ['a', 'b', 'e'], 'd': ['b', 'e'], 'e': ['c', 'd', 'f'], 'f': ['e']}
    >>> route(graph, 'a', 'f')
    ['a', 'c', 'e', 'f']
    >>> route(graph, 'b', 'e')
    ['b', 'c', 'e']
    '''
    if start not in graph:
        raise Exception(f'開始地点{start}が無い')
    visited = {start}
    frontier = {start}
    frontiers = [frontier]
    while frontier:
        new_frontier = set()
        for g in frontier:
            if end in graph[g]:
                break
            s = set(graph[g]) - visited
            visited |= s
            new_frontier |= s
        frontiers.append(new_frontier)
        frontier = new_frontier
    route = [end]
    for frontier in frontiers[::-1]:
        if start in frontier:
            route.append(start)
            route.reverse()
            return route
        for g in frontier:
            if end in graph[g]:
                route.append(g)
                end = g
                break


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    graph = {'a': ['b', 'c', 'e'],
             'b': ['a', 'c'],
             'c': ['a', 'b', 'j'],
             'd': ['e', 'f', 'g'],
             'e': ['a', 'd', 'k'],
             'f': ['d', 'n'],
             'g': ['d', 'h', 'i'],
             'h': ['g', 'm'],
             'i': ['g', 'p'],
             'j': ['c', 'k', 'l'],
             'k': ['e', 'j', 'l'],
             'l': ['j', 'k', 's'],
             'm': ['h', 'n', 'o'],
             'n': ['f', 'm', 'o'],
             'o': ['m', 'n', 'v'],
             'p': ['i', 'q', 'r'],
             'q': ['p', 'w'],
             'r': ['p', 'x'],
             's': ['l', 't', 'u'],
             't': ['s', 'u'],
             'u': ['s', 't', 'v'],
             'v': ['o', 'u', 'w'],
             'w': ['q', 'v', 'y'],
             'x': ['r', 'y', 'z'],
             'y': ['w', 'x', 'z'],
             'z': ['x', 'y']}
    print(is_symmetry(graph))
    print(route(graph, 'b', 'z'))

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

C:\Users\...>py -3 sample3.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
Trying:
    route({'a':['b'], 'b':['a']}, 'a', 'b')
Expecting:
    ['a', 'b']
ok
Trying:
    route({'a':['b'], 'b':['a']}, 'b', 'a')
Expecting:
    ['b', 'a']
ok
Trying:
    graph = {'a': ['b', 'c'], 'b': ['a', 'c', 'd'], 'c': ['a', 'b', 'e'], 'd': ['b', 'e'], 'e': ['c', 'd', 'f'], 'f': ['e']}
Expecting nothing
ok
Trying:
    route(graph, 'a', 'f')
Expecting:
    ['a', 'c', 'e', 'f']
ok
Trying:
    route(graph, 'b', 'e')
Expecting:
    ['b', 'c', 'e']
ok
1 items had no tests:
    __main__
2 items passed all tests:
   5 tests in __main__.is_symmetry
   5 tests in __main__.route
10 tests in 3 items.
10 passed and 0 failed.
Test passed.
True
['b', 'a', 'e', 'd', 'g', 'i', 'p', 'r', 'x', 'z']

C:\Users\...>