## 2019年1月22日火曜日

### 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

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:
return vertex_set

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

```\$ 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
__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.
\$
```