Chapter 07無料公開

【rej:06】networkxで東北6県の4色問題【Python】

fz5050
fz5050
2022.03.03に更新
このチャプターの目次

【はじめに】

networkxで4色問題をとく。(東北6県を塗り分ける)

import networkx as nx

# サンプルデータの作成
text2 = '''AO,IW,AK
IW,AO,AK,MY
AK,AO,IW,YM,MY
YM,AK,MY,FK
MY,IW,AK,YM,FK
FK,YM,MY'''

with open("tohoku.adj",mode='w') as f:
    f.write(text2)
    
G = nx.read_adjlist('tohoku.adj', delimiter = ',')

# ノード情報確認(県ラベル相当)
print(G.nodes)

# エッジ情報確認
print(G.edges)


# 隣接状況の可視化
%matplotlib inline
import matplotlib.pyplot as plt


#描画用posデータ作成
pos = {
    'AO':(0.5, 2),
    'IW':(1, 1.5),
    'AK':(0, 1.5),
    'MY':(1, 0.5),
    'YM':(0, 0.5),
    'FK':(1, 0),
}


nx.draw_networkx(G, pos = pos,node_color="r")
plt.show()

# 4色問題を解く
result =  nx.algorithms.coloring.greedy_color(G)
print(result)

# 結果の確認
# G.nodesの並びと色を合わせる
result_color = [ result.get(key) for key in G.nodes]
print(result_color)

# 描画
my_nx_other_param ={
    "node_color":result_color,
    "with_labels":True,
    "cmap":plt.cm.rainbow
}

nx.draw(G,
        pos = pos,
        **my_nx_other_param)

▲3色で塗り分けることができた

コメント

QAP.09:4色問題(グラフの彩色問題)、AND制約とpenalty関数の使い方【量子コンピュータ/アニーリング@Python/Fixstars Amplify】』の最後に少し記述したnetworkxを使ってグラフ彩色問題を解く場合のサンプルとして用意していた。

networkx側の説明自体が長くなりそうだったので没にした。