Algorithm - Python - 忘れられない週末(節点対の間の経路を見つける、辞書を使ったグラフの表現、例外、深さ優先のグラフの再帰横断)

問題解決の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 (著)、黒川 利明 (翻訳)、オライリージャパン)の19章(忘れられない週末)、練習問題(問題3)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3
def find_path(graph: dict, start: str, end: str, path: list):
    '''
    >>> find_path({'b': ['c'], 'c': ['b', 'd'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'b', 'i', [])
    ['b', 'c', 'd', 'f', 'i']
    >>> find_path({'b': ['c'], 'c': ['b', 'd'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'a', 'i', [])
    >>> find_path({'a': [], 'b': ['c'], 'c': ['b', 'd'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'a', 'i', [])
    >>> find_path({'a': ['b'], 'a': ['b'], 'c': ['d'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'a', 'i', [])
    >>> find_path({'a': ['b'], 'a': ['b'], 'c': ['d'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'c', 'i', [])
    ['c', 'd', 'f', 'i']

    '''
    if start not in graph:
        return None
    if len(path) == 0:
        path = [start]
    if end in graph[start]:
        return path + [end]
    for vertex in graph[start]:
        if vertex in path:
            continue
        path0 = find_path(graph, vertex, end, path + [vertex])
        if path0 is not None:
            return path0
    return None


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

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

$ python3 sample3.py -v
Trying:
    find_path({'b': ['c'], 'c': ['b', 'd'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'b', 'i', [])
Expecting:
    ['b', 'c', 'd', 'f', 'i']
ok
Trying:
    find_path({'b': ['c'], 'c': ['b', 'd'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'a', 'i', [])
Expecting nothing
ok
Trying:
    find_path({'a': [], 'b': ['c'], 'c': ['b', 'd'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'a', 'i', [])
Expecting nothing
ok
Trying:
    find_path({'a': ['b'], 'a': ['b'], 'c': ['d'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'a', 'i', [])
Expecting nothing
ok
Trying:
    find_path({'a': ['b'], 'a': ['b'], 'c': ['d'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}, 'c', 'i', [])
Expecting:
    ['c', 'd', 'f', 'i']
ok
1 items had no tests:
    __main__
1 items passed all tests:
   5 tests in __main__.find_path
5 tests in 2 items.
5 passed and 0 failed.
Test passed.
$