質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

1回答

943閲覧

python3 Welsh・. Powell を実装

black925

総合スコア12

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

1クリップ

投稿2019/01/08 07:05

編集2019/01/08 09:06

イメージ説明python3系でグラフ理論のWelsh・. Powellアルゴリズムを用いてそのグラフを彩色する際に何色必要か求めたいのですが、問題となるグラフのソートまでできたのですが
次数の高い順に色を塗っていくところがうまくできません

python3

1#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる) 2A = [0, 'B', 0, 0, 0, 0, 0, 0] 3B = ['A', 0, 'C', 'D', 'E', 0, 'G', 0] 4C = [0, 'B', 0, 'D', 0, 0, 0, 0] 5D = [0, 'B', 'C', 0, 'E', 'F', 0, 'H'] 6E = [0, 'B', 0, 'D', 0, 'F', 'G', 0] 7F = [0, 0, 0, 'D', 'E', 0, 'G', 'H'] 8G = [0, 'B', 0, 0, 'E', 'F', 0, 'H'] 9H = [0, 0, 0, 'D', 0, 'F', 'G', 0] 10 11graph = [A, B, C, D, E, F, G, H] 12graph_str = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] 13copy_graph = copy.copy(graph_str) 14d_graph = list() 15 16print(graph_str) 17 18#次数を求める 19for node in graph: 20 #dgraphに接点数を格納 21 tmp = node.count(0) 22 tmp = len(graph)-tmp 23 d_graph.append(tmp) 24 25 26 27print('接点数',d_graph) 28 29#次数でバブルソート 30for i in range(len(d_graph)): 31 for j in range(len(d_graph)-1, i, -1): 32 if d_graph[j] > d_graph[j-1]: 33 d_graph[j], d_graph[j-1] = d_graph[j-1], d_graph[j] 34 tmp = str(graph_str[j]) 35 graph_str[j] = str(graph_str[j-1]) 36 graph_str[j-1] = str(tmp) 37 38print('接点数順でソート大→小') 39print(graph_str)

とりあえず上記でソートまでです
これ以降をお願い致します。

グラフは上記で、隣り合ったノードは同じ色で塗らないといったものです

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

can110

2019/01/08 08:59

何にどんな風に色を塗ればよいか分からないので、イメージ画像またはできているまでのソースコードを提示すると回答得られるかもしれません。
black925

2019/01/08 09:13

Welsh_Powellのアルゴリズムなんですが隣り合ったノードは違う色で塗ったら合計で何色必要かというものです 1,ノードの次数を求める 2,次数順にソートする 3,まだ塗ってない中で次数が一番高いものに色を塗る 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る 3と4を繰り返す です
black925

2019/01/10 04:13

実際に動かしてみたところFとHが隣り合っているのに同じグループになってしまい、 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る の際にすでに割り振られているノードから再度つながりがあるか確認する必要がありました(Hを割り振る際にHのつながりからFはスルーしたい) if n in graph_str: の後に for subnode_2 in (graph_map[n]): if subnode_ 2 in graph_map:    スルーする みたく書けばいいと思うのですがうまくいかなくて詰まっています 何かいい方法がありますか?
guest

回答1

0

ベストアンサー

以下の要領で、各ノードに色を割り当てることができます。
実際の画像への?色塗りはご自身で実装ください。

Python

1import copy 2 3#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる) 4A = [0, 'B', 0, 0, 0, 0, 0, 0] 5B = ['A', 0, 'C', 'D', 'E', 0, 'G', 0] 6C = [0, 'B', 0, 'D', 0, 0, 0, 0] 7D = [0, 'B', 'C', 0, 'E', 'F', 0, 'H'] 8E = [0, 'B', 0, 'D', 0, 'F', 'G', 0] 9F = [0, 0, 0, 'D', 'E', 0, 'G', 'H'] 10G = [0, 'B', 0, 0, 'E', 'F', 0, 'H'] 11H = [0, 0, 0, 'D', 0, 'F', 'G', 0] 12 13graph = [A, B, C, D, E, F, G, H] 14graph_str = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] 15copy_graph = copy.copy(graph_str) 16d_graph = list() 17 18print(graph_str) 19 20# 各ノードに接続しているノードマップ 21graph_map = {k:v for k,v in zip(graph_str,graph)} 22print(graph_map) 23 24#次数を求める 25for node in graph: 26 #dgraphに接点数を格納 27 tmp = node.count(0) 28 tmp = len(graph)-tmp 29 d_graph.append(tmp) 30 31print('接点数',d_graph) 32 33#次数でバブルソート 34for i in range(len(d_graph)): 35 for j in range(len(d_graph)-1, i, -1): 36 if d_graph[j] > d_graph[j-1]: 37 d_graph[j], d_graph[j-1] = d_graph[j-1], d_graph[j] 38 tmp = str(graph_str[j]) 39 graph_str[j] = str(graph_str[j-1]) 40 graph_str[j-1] = str(tmp) 41 42print('接点数順でソート大→小') 43print(graph_str) 44 45graph_color = {} # 各ノードの色インデックスを保持 46color_idx = 0 # 現在の色インデックス 47while len(graph_str) > 0: 48 # 3,まだ塗ってない中で次数が一番高いものに色を塗る 49 node = graph_str.pop(0) 50 graph_color[node] = color_idx 51 52 # 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る 53 for idx,sub_node in enumerate(graph_map[node]): 54 if sub_node == 0: # このノードに接続していない 55 n = copy_graph[idx] 56 if n in graph_str: 57 # 同じ色を割り当てる 58 graph_color[n] = color_idx 59 graph_str.remove(n) 60 color_idx += 1 61 62print(graph_color) # {'A': 1, 'B': 0, 'E': 2, 'D': 1, 'C': 2, 'F': 0, 'H': 0, 'G': 1}

コメントを受けて修正

Bの着色時、FHBに接続していないので同色で着色していましたが、FHがつながっていることが考慮されていませんでした。
これを考慮し、なおかつコードを全面的に修正しました。

Python

1# 2# 隣接ノード'edge'が指定した色'clr'を持っているか 3# 4def has_color(edge,clr,graph_clr): 5 for e in edge: 6 if e in graph_clr: 7 if graph_clr[e] == clr: 8 return True 9 return False 10 11#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる) 12A = ['B'] 13B = ['A','C','D','E','G'] 14C = ['B','D'] 15D = ['B','C','E','F','H'] 16E = ['B','D','F','G'] 17F = ['D','E','G','H'] 18G = ['B','E','F','H'] 19H = ['D','F','G'] 20 21# ノード→エッジマップを作成 22edges = [A, B, C, D, E, F, G, H] 23nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] 24graph_map = {k:v for k,v in zip(nodes,edges)} 25#print(graph_map) 26 27#次数を求め、降順でソート 28graph_dim = {k:len(v) for k,v in graph_map.items()} 29graph_dim = sorted( graph_dim.items(), key=lambda x: x[1], reverse=True) 30#print(graph_dim) 31 32# 3,まだ塗ってない中で次数が一番高いものに色を塗る 33clr = 0 # あらたに塗る色番号 34graph_clr = {}# ノード→色番号マップ 35for i, node_dim in enumerate(graph_dim): 36 node = node_dim[0] 37 if node in graph_clr: # すでに着色済み 38 continue 39 graph_clr[node] = clr 40 41 # 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る 42 # ※この条件だけだとFとHが同じ色になる 43 for j in range(i+1,len(graph_dim)): # 次の次数の大きいものから順に走査 44 sub_node = graph_dim[j][0] 45 if sub_node in graph_clr: # すでに着色済み 46 continue 47 if sub_node in graph_map[node]: # 現在のノードとつながっている 48 continue 49 # 隣接ノードがすでに同色で着色済み ※この条件が必要 50 if has_color(graph_map[sub_node],clr,graph_clr): 51 continue 52 graph_clr[sub_node] = clr 53 54 clr += 1 55 56print(graph_clr) # {'C': 2, 'D': 0, 'E': 2, 'A': 0, 'G': 0, 'F': 1, 'B': 1, 'H': 2}

投稿2019/01/09 05:10

編集2019/01/10 08:03
can110

総合スコア38234

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

black925

2019/01/09 09:16

ありがとうございます コメントが多くてたすかります
black925

2019/01/10 04:14

上のほうにもかいたのですが 実際に動かしてみたところFとHが隣り合っているのに同じグループになってしまい、 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る の際にすでに割り振られているノードから再度つながりがあるか確認する必要がありました(Hを割り振る際にHのつながりからFはスルーしたい) if n in graph_str: の後に for subnode_2 in (graph_map[n]): if subnode_ 2 in graph_map:    スルーする みたく書けばいいと思うのですがうまくいかなくて詰まっています 何かいい方法がありますか?
can110

2019/01/10 07:16

>すでに割り振られているノードから再度つながりがあるか確認する必要がありました(Hを割り振る際にHのつながりからFはスルーしたい) ちょっと考えてみます。
black925

2019/01/10 08:27

何度もすみません、本当に助かります
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問