## 2019年1月17日木曜日

### Algorithm - Python - 忘れられない週末(色分けできない閉路、グラフ彩色(2彩色)、2部グラフ、非連結、辞書を使ったグラフの表現、例外、深さ優先のグラフの再帰横断)

コード

Python 3

```#!/usr/bin/env python3

def bipartite_graph_color(graph: dict, start: str, coloring: dict, color: str,
path: list) -> (bool, dict):
path.append(start)
if not start in graph:
return False, {}
if not start in coloring:
coloring[start] = color
elif coloring[start] != color:
print(f'Here was a cyclic path that cannot be colored {path}')
return False, {}
else:
return True, coloring
if color == '赤':
color = '青'
else:
color = '赤'
for vertex in graph[start]:
bln, coloring = bipartite_graph_color(
graph, vertex, coloring, color, path)
if not bln:
return False, {}
return True, coloring

def bipartite_graph_color_not_connected(
graph: dict, start: str, coloring: dict, color: str) -> (bool, dict):
bln, coloring = bipartite_graph_color(
graph, start, coloring, color, [])
graph_keys = set(graph)
coloring_keys = set(coloring)
if bln and graph_keys == coloring_keys:
return True, coloring
return bipartite_graph_color(
graph, (graph_keys - coloring_keys).pop(), coloring, color, [])

if __name__ == '__main__':
graph1 = {'a': ['b'],
'b': ['a'],
'c': ['d'],
'd': ['c', 'e', 'f'],
'e': ['d'],
'f': ['d', 'g', 'h', 'i'],
'g': ['f'],
'h': ['f'],
'i': ['f']}
graph_c = {'a': ['b', 'd', 'c'],
'b': ['c', 'a'],
'c': ['d', 'b', 'a'],
'd': ['a', 'c', 'b']}
graph_d = {'a': ['b', 'c'],
'b': ['a', 'd'],
'c': ['a', 'd'],
'd': ['b', 'c']}
graphs = [graph1, graph_c, graph_d]
for graph in graphs:
graph0 = {k: list(reversed(v)) for k, v in graph.items()}
for g in [graph, graph0]:
print(g)
print(bipartite_graph_color_not_connected(g, 'a', {}, '赤'))
```

```\$ python3 sample2.py
{'a': ['b'], 'b': ['a'], 'c': ['d'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}
(True, {'a': '赤', 'b': '青', 'd': '赤', 'c': '青', 'e': '青', 'f': '青', 'g': '赤', 'h': '赤', 'i': '赤'})
{'a': ['b'], 'b': ['a'], 'c': ['d'], 'd': ['f', 'e', 'c'], 'e': ['d'], 'f': ['i', 'h', 'g', 'd'], 'g': ['f'], 'h': ['f'], 'i': ['f']}
(True, {'a': '赤', 'b': '青', 'd': '赤', 'f': '青', 'i': '赤', 'h': '赤', 'g': '赤', 'e': '青', 'c': '青'})
{'a': ['b', 'd', 'c'], 'b': ['c', 'a'], 'c': ['d', 'b', 'a'], 'd': ['a', 'c', 'b']}
Here was a cyclic path that cannot be colored ['a', 'b', 'c', 'd', 'a', 'c', 'b']
Here was a cyclic path that cannot be colored ['a', 'b', 'c', 'd', 'a', 'c', 'b']
(False, {})
{'a': ['c', 'd', 'b'], 'b': ['a', 'c'], 'c': ['a', 'b', 'd'], 'd': ['b', 'c', 'a']}
Here was a cyclic path that cannot be colored ['a', 'c', 'a', 'b', 'a']
Here was a cyclic path that cannot be colored ['a', 'c', 'a', 'b', 'a']
(False, {})
{'a': ['b', 'c'], 'b': ['a', 'd'], 'c': ['a', 'd'], 'd': ['b', 'c']}
(True, {'a': '赤', 'b': '青', 'd': '赤', 'c': '青'})
{'a': ['c', 'b'], 'b': ['d', 'a'], 'c': ['d', 'a'], 'd': ['c', 'b']}
(True, {'a': '赤', 'c': '青', 'd': '赤', 'b': '青'})
\$
```