## 2019年2月5日火曜日

### Algorithm - Python - 6次の隔たり - 集合演算、集合を使ったグラフの幅優先探索(節点対の隔たり、グラフの隔たり、次数)

コード

Python 3

```#!/usr/bin/env python3
def degrees_of_pair(graph: dict, start: str, end: str) -> int:
'''
>>> degrees_of_pair(small, 'c', 'b')
1
>>> degrees_of_pair(small, 'c', 'd')
2
'''
if start not in graph:
return -1
visited = {start}
frontier = {start}
degress = 0
while frontier:
degress += 1
new_frontier = set()
for g in frontier:
if end in graph[g]:
return degress
s = set(graph[g]) - visited
visited |= s
new_frontier |= s
frontier = new_frontier
return degress - 1

def degrees(graph: dict) -> int:
'''
>>> degrees(small)
3
'''
degrees = max([degrees_of_pair(graph, k1, k2)
for k1 in graph
for k2 in graph
if k1 < k2])
return degrees

if __name__ == '__main__':
import doctest
small = {'a': ['b', 'c'],
'b': ['a', 'c', 'd'],
'c': ['a', 'b', 'e'],
'd': ['b', 'e'],
'e': ['c', 'd', 'f'],
'f': ['e']}
globs = globals()
globs.update({'small': small})
doctest.testmod(globs=globs)
```

```C:\Users\...>py -3 sample1.py -v
Trying:
degrees(small)
Expecting:
3
ok
Trying:
degrees_of_pair(small, 'c', 'b')
Expecting:
1
ok
Trying:
degrees_of_pair(small, 'c', 'd')
Expecting:
2
ok
__main__
2 items passed all tests:
1 tests in __main__.degrees
2 tests in __main__.degrees_of_pair
3 tests in 3 items.
3 passed and 0 failed.
Test passed.

C:\Users\...>
```