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

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

ただいまの
回答率

87.60%

python3 Welsh・. Powell を実装

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,151

score 12

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

#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる)
A = [0, 'B', 0, 0, 0, 0, 0, 0]
B = ['A', 0, 'C', 'D', 'E', 0, 'G', 0]
C = [0, 'B', 0, 'D', 0, 0, 0, 0]
D = [0, 'B', 'C', 0, 'E', 'F', 0, 'H']
E = [0, 'B', 0, 'D', 0, 'F', 'G', 0]
F = [0, 0, 0, 'D', 'E', 0, 'G', 'H']
G = [0, 'B', 0, 0, 'E', 'F', 0, 'H']
H = [0, 0, 0, 'D', 0, 'F', 'G', 0]

graph = [A, B, C, D, E, F, G, H]
graph_str = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
copy_graph = copy.copy(graph_str)
d_graph = list()

print(graph_str)

#次数を求める
for node in graph:
    #dgraphに接点数を格納
    tmp = node.count(0)
    tmp = len(graph)-tmp
    d_graph.append(tmp)



print('接点数',d_graph)

#次数でバブルソート
for i in range(len(d_graph)):
    for j in range(len(d_graph)-1, i, -1):
        if d_graph[j] > d_graph[j-1]:
            d_graph[j], d_graph[j-1] = d_graph[j-1], d_graph[j]
            tmp = str(graph_str[j])
            graph_str[j] = str(graph_str[j-1])
            graph_str[j-1] = str(tmp)

print('接点数順でソート大→小')
print(graph_str)

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

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • can110

    2019/01/08 17:59

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

    キャンセル

  • black925

    2019/01/08 18:13

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

    キャンセル

  • black925

    2019/01/10 13: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: 
      スルーする
    みたく書けばいいと思うのですがうまくいかなくて詰まっています
    何かいい方法がありますか?

    キャンセル

回答 1

checkベストアンサー

+1

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

import copy

#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる)
A = [0, 'B', 0, 0, 0, 0, 0, 0]
B = ['A', 0, 'C', 'D', 'E', 0, 'G', 0]
C = [0, 'B', 0, 'D', 0, 0, 0, 0]
D = [0, 'B', 'C', 0, 'E', 'F', 0, 'H']
E = [0, 'B', 0, 'D', 0, 'F', 'G', 0]
F = [0, 0, 0, 'D', 'E', 0, 'G', 'H']
G = [0, 'B', 0, 0, 'E', 'F', 0, 'H']
H = [0, 0, 0, 'D', 0, 'F', 'G', 0]

graph = [A, B, C, D, E, F, G, H]
graph_str = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
copy_graph = copy.copy(graph_str)
d_graph = list()

print(graph_str)

# 各ノードに接続しているノードマップ
graph_map = {k:v for k,v in zip(graph_str,graph)}
print(graph_map)

#次数を求める
for node in graph:
    #dgraphに接点数を格納
    tmp = node.count(0)
    tmp = len(graph)-tmp
    d_graph.append(tmp)

print('接点数',d_graph)

#次数でバブルソート
for i in range(len(d_graph)):
    for j in range(len(d_graph)-1, i, -1):
        if d_graph[j] > d_graph[j-1]:
            d_graph[j], d_graph[j-1] = d_graph[j-1], d_graph[j]
            tmp = str(graph_str[j])
            graph_str[j] = str(graph_str[j-1])
            graph_str[j-1] = str(tmp)

print('接点数順でソート大→小')
print(graph_str)

graph_color = {} # 各ノードの色インデックスを保持
color_idx = 0    # 現在の色インデックス
while len(graph_str) > 0:
    # 3,まだ塗ってない中で次数が一番高いものに色を塗る
    node = graph_str.pop(0)
    graph_color[node] = color_idx

    # 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る
    for idx,sub_node in enumerate(graph_map[node]):
        if sub_node == 0: # このノードに接続していない
            n = copy_graph[idx]
            if n in graph_str:
                # 同じ色を割り当てる
                graph_color[n] = color_idx
                graph_str.remove(n)
    color_idx += 1

print(graph_color) # {'A': 1, 'B': 0, 'E': 2, 'D': 1, 'C': 2, 'F': 0, 'H': 0, 'G': 1}

コメントを受けて修正

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

#
# 隣接ノード'edge'が指定した色'clr'を持っているか
#
def has_color(edge,clr,graph_clr):
    for e in edge:
        if e in graph_clr:
            if graph_clr[e] == clr:
                return True
    return False

#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる)
A = ['B']
B = ['A','C','D','E','G']
C = ['B','D']
D = ['B','C','E','F','H']
E = ['B','D','F','G']
F = ['D','E','G','H']
G = ['B','E','F','H']
H = ['D','F','G']

# ノード→エッジマップを作成
edges = [A, B, C, D, E, F, G, H]
nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
graph_map = {k:v for k,v in zip(nodes,edges)}
#print(graph_map)

#次数を求め、降順でソート
graph_dim = {k:len(v) for k,v in graph_map.items()}
graph_dim = sorted( graph_dim.items(), key=lambda x: x[1], reverse=True)
#print(graph_dim)

# 3,まだ塗ってない中で次数が一番高いものに色を塗る
clr = 0       # あらたに塗る色番号
graph_clr = {}# ノード→色番号マップ
for i, node_dim in enumerate(graph_dim):
    node = node_dim[0]
    if node in graph_clr: # すでに着色済み
        continue
    graph_clr[node] = clr

    # 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る
    # ※この条件だけだとFとHが同じ色になる
    for j in range(i+1,len(graph_dim)): # 次の次数の大きいものから順に走査
        sub_node = graph_dim[j][0]
        if sub_node in graph_clr:       # すでに着色済み
            continue
        if sub_node in graph_map[node]: # 現在のノードとつながっている
            continue
        # 隣接ノードがすでに同色で着色済み ※この条件が必要
        if has_color(graph_map[sub_node],clr,graph_clr):
            continue
        graph_clr[sub_node] = clr

    clr += 1

print(graph_clr) # {'C': 2, 'D': 0, 'E': 2, 'A': 0, 'G': 0, 'F': 1, 'B': 1, 'H': 2}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/09 18:16

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

    キャンセル

  • 2019/01/10 13: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: 
      スルーする
    みたく書けばいいと思うのですがうまくいかなくて詰まっています
    何かいい方法がありますか?

    キャンセル

  • 2019/01/10 16:16

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

    キャンセル

  • 2019/01/10 17:27

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

    キャンセル

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

  • ただいまの回答率 87.60%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る