## 2019年1月20日日曜日

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

コード

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()
```

```\$ 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
__main__
1 items passed all tests:
5 tests in __main__.find_path
5 tests in 2 items.
5 passed and 0 failed.
Test passed.
\$
```