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

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の19章(忘れられない週末)、練習問題(問題1)の解答を求めてみる。

コード

Python 3

#!/usr/bin/env python3


def bipartite_graph_color(
        graph: dict, start: str, coloring: dict, color: str) -> (bool, dict):
    if not start in graph:
        return False, {}
    if not start in coloring:
        coloring[start] = color
    elif coloring[start] != color:
        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)
        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']}
    graph2 = {k: list(reversed(v)) for k, v in graph1.items()}
    for graph in [graph1, graph2]:
        print(graph)
        print(bipartite_graph_color_not_connected(graph, 'a', {}, '赤'))

入出力結果(Terminal、cmd(コマンドプロンプト)、Jupyter(IPython))

$ python3 sample1.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': '青', 'c': '赤', 'd': '青', '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': '青', 'c': '赤', 'd': '青', 'f': '赤', 'i': '青', 'h': '青', 'g': '青', 'e': '赤'})
$