## 2019年2月23日土曜日

### Algorithm - Python - 6次の隔たり - 集合演算、集合を使ったグラフの幅優先探索(辞書、無向グラフ、前線、最短経路)

コード

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

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