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章(忘れられない週末)、練習問題(問題2)の解答を求めてみる。

問題の例のグラフ(graphc)

コード

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', {}, '赤'))

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

$ 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': '青'})
$