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章(忘れられない週末)、練習問題(パズル問題4)の解答を求めてみる。

コード

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


def articulation_point(graph: dict) -> set:
    '''
    >>> sorted(list(articulation_point({'a': ['b', 'c', 'e'], 'b': ['a', 'c'], 'c': ['a', 'b', 'e'], 'e': ['a', 'c']})))
    []
    >>> sorted(list(articulation_point({'v': ['w'], 'w': ['v', 'y'], 'y': ['w', 'z'], 'z': ['y']})))
    ['w', 'y']
    >>> sorted(list(articulation_point({'j': ['k', 'l'], 'k': ['j', 'l'], 'l': ['j', 'k', 's'], 's': ['l', 't', 'u'], 't': ['s', 'u'], 'u': ['s', 't']})))
    ['l', 's']
    '''
    vertexes = sorted(graph.keys())
    vertex_pairs = [(v1, v2)
                    for v1 in vertexes
                    for v2 in vertexes
                    if v1 < v2 and v1 not in graph[v2] and v2 not in graph[v1]]
    vertex_set = set()
    for v1, v2 in vertex_pairs:
        for vertex in [v for v in vertexes if v not in [v1, v2]]:
            graph_tmp = {k: [t for t in v if t != vertex]
                         for k, v in graph.items()
                         if k != vertex}
            path = find_path(graph_tmp, v1, v2, [])
            if path is None:
                vertex_set.add(vertex)
    return vertex_set


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

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

$ python3 sample4.p -v
Trying:
    sorted(list(articulation_point({'a': ['b', 'c', 'e'], 'b': ['a', 'c'], 'c': ['a', 'b', 'e'], 'e': ['a', 'c']})))
Expecting:
    []
ok
Trying:
    sorted(list(articulation_point({'v': ['w'], 'w': ['v', 'y'], 'y': ['w', 'z'], 'z': ['y']})))
Expecting:n
    ['w', 'y']
ok
Trying:
    sorted(list(articulation_point({'j': ['k', 'l'], 'k': ['j', 'l'], 'l': ['j', 'k', 's'], 's': ['l', 't', 'u'], 't': ['s', 'u'], 'u': ['s', 't']})))
Expecting:
    ['l', 's']
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']}, '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__
2 items passed all tests:
   3 tests in __main__.articulation_point
   5 tests in __main__.find_path
8 tests in 3 items.
8 passed and 0 failed.
Test passed.
$