## 2019年2月24日日曜日

### 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 degrees_of_pair(
graph: dict, start: str, end: str, visited: set = None) -> int:
'''
>>> smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
>>> d = {k: [a for a, _ in v] for k, v in smallw.items()}
>>> is_symmetry(d)
True
>>> degrees_of_pair(smallw, 'a', 'c', set())
2
>>> degrees_of_pair(smallw, 'a', 'f', set())
5
'''
if visited is None:
visited = set()
visited_tmp = visited | {start}
degrees = None
for node, weight in graph[start]:
if node in visited_tmp:
continue
if node == end:
if degrees is None or weight < degrees:
degrees = weight
else:
degrees_tmp = degrees_of_pair(graph, node, end, visited_tmp)
if degrees_tmp == -1:
continue
degrees_tmp += weight
if degrees is None or degrees_tmp < degrees:
degrees = degrees_tmp
if degrees is None:
return -1
return degrees

def degrees_of_separation(graph: dict, start: str) -> int:
'''
>>> smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
>>> degrees_of_separation(smallw, 'a')
5
>>> degrees_of_separation(smallw, 'b')
4
'''
max_degrees = 0
for end in graph:
degrees = degrees_of_pair(graph, start, end)
if degrees > max_degrees:
max_degrees = degrees
return max_degrees

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

```C:\Users\...>py -3 sample4.py -v
Trying:
smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
Expecting nothing
ok
Trying:
d = {k: [a for a, _ in v] for k, v in smallw.items()}
Expecting nothing
ok
Trying:
is_symmetry(d)
Expecting:
True
ok
Trying:
degrees_of_pair(smallw, 'a', 'c', set())
Expecting:
2
ok
Trying:
degrees_of_pair(smallw, 'a', 'f', set())
Expecting:
5
ok
Trying:
smallw = {'a': [('b', 1), ('c', 2)], 'b': [('a', 1), ('c', 1), ('d', 1)], 'c': [('a', 2), ('b', 1), ('e', 2)], 'd': [('b', 1), ('e', 1)], 'e': [('c', 2), ('d', 1), ('f', 2)], 'f': [('e', 2)]}
Expecting nothing
ok
Trying:
degrees_of_separation(smallw, 'a')
Expecting:
5
ok
Trying:
degrees_of_separation(smallw, 'b')
Expecting:
4
ok
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
__main__
3 items passed all tests:
5 tests in __main__.degrees_of_pair
3 tests in __main__.degrees_of_separation
5 tests in __main__.is_symmetry
13 tests in 4 items.
13 passed and 0 failed.
Test passed.

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