連結成分¶
本稿では NetworkX の提供する機能を利用して、グラフの連結成分を得る方法について述べる。まず、ある有向グラフの強連結成分を得る手順について、例を挙げて説明する。それから、「強」でない種類の連結成分について記すつもりだ。
強連結成分¶
有向グラフの強連結成分を求めることは、興味のある問題であることが多い。例えば、有向グラフの強連結成分の集まりと、成分同士を接続する元のグラフの辺の組の集まりとで、有向部分グラフを考えることがある。その連結部分をひとつ取ってみれば、これは DAG となっている。
とりあえず、ここで考えるサンプルコードを示す。コードの流れは次のようなものである。
グラフを構築する
強連結成分を得る
自明でない強連結成分を標準出力に書き出す
#!/usr/bin/env python
"""strongly_connected_components.py: demonstrate strongly_connected_components.
"""
from itertools import groupby
import networkx as nx
def main():
"""The main function."""
G = setup_recipe()
print_strongly_connected_components(G)
def setup_recipe():
if __name__ == '__main__':
main()
コード中のグラフ G は原作版ドラクエ 8 の錬金レシピの依存関係を基に構成した（多重）有向グラフだ。素材アイテムおよび生成アイテムがグラフの点であり、アイテム間の依存関係を生成方向に結んだ線分がグラフのエッジとなる。また、生成アイテムに必要な素材アイテム数をそのエッジの重みとした（今回の例では意味は重要でない）。
def setup_recipe():
"""Create a multi directed graph.
Returns:
(MultiDiGraph): A multi directed graph.
"""
def add_recipe(G, target, *sources):
for s, g in groupby(sorted(sources)):
G.add_edge(s, target, weight=len(list(g)))
G = nx.MultiDiGraph()
add_recipe(G, '上やくそう', 'やくそう', 'やくそう')
add_recipe(G, '特やくそう', '上やくそう', '上やくそう')
add_recipe(G, 'いやし草', 'やくそう', 'やくそう', 'やくそう')
add_recipe(G, 'いやし草', 'やくそう', '上やくそう')
add_recipe(G, 'アモールの水', 'せいすい', '上やくそう')
add_recipe(G, '上どくけし草', 'やくそう', 'どくけし草')
add_recipe(G, '特どくけし草', 'やくそう', 'どくけし草', 'どくけし草')
add_recipe(G, '特どくけし草', '上どくけし草', '上どくけし草')
add_recipe(G, 'きつけ草', 'やくそう', 'やくそう', 'まんげつ草')
add_recipe(G, 'きつけ草', 'まんげつ草', '上やくそう')
add_recipe(G, '月のめぐみ', 'まんげつそう', 'まんげつそう', 'まんげつそう')
add_recipe(G, '万能ぐすり', '特やくそう', '特やくそう')
add_recipe(G, '超万能ぐすり', '万能ぐすり', 'いやし草', 'きつけ草')
add_recipe(G, '超万能ぐすり', '特やくそう', '特やくそう', '特やくそう')
add_recipe(G, 'せかいじゅのしずく', 'せかいじゅの葉', 'まほうのせいすい')
add_recipe(G, 'まほうのせいすい', 'せいすい', 'ふしぎなきのみ')
add_recipe(G, 'エルフの飲み薬', 'まほうのせいすい', 'せかいじゅのしずく')
add_recipe(G, 'せいすい', 'アモールの水', '岩塩')
add_recipe(G, 'キメラのつばさ', 'こうもりのはね', 'こうもりのはね')
add_recipe(G, 'おかしな薬', 'せいすい', 'こうもりのはね', 'うしのふん')
add_recipe(G, 'おかしな薬', 'やくそう', 'どくけし草', 'まんげつ草')
add_recipe(G, '賢者の石', '金塊', 'オリハルコン', 'せかいじゅのしずく')
add_recipe(G, 'ふしぎなタンバリン', '太陽のかんむり', 'まじゅうの皮', '怒りのタトゥー')
add_recipe(G, 'ふつうのチーズ', 'おいしいミルク', 'レンネットのこな')
add_recipe(G, 'ふつうのチーズ', '超辛チーズ', 'かがやくチーズ')
add_recipe(G, '辛口チーズ', 'ふつうのチーズ', '赤いカビ')
add_recipe(G, '激辛チーズ', '辛口チーズ', 'あかいカビ', 'あかいカビ')
add_recipe(G, '超辛チーズ', '激辛チーズ', 'ごくじょうのカビ', 'ドラゴンのふん')
add_recipe(G, '冷たいチーズ', 'ふつうのチーズ', 'みず草のカビ')
add_recipe(G, 'こおりのチーズ', '冷たいチーズ', 'みず草のカビ')
add_recipe(G, 'こごえるチーズ', 'こおりのチーズ', 'みず草のカビ', 'みず草のカビ')
add_recipe(G, 'かがやくチーズ', 'こごえるチーズ', 'ごくじょうのカビ', 'ドラゴンのふん')
add_recipe(G, 'いやしのチーズ', 'ふつうのチーズ', 'アモールの水')
add_recipe(G, 'ベホマラチーズ', 'おいしいミルク', 'ごくじょうのカビ', 'アモールの水')
add_recipe(G, '天使のチーズ', 'おいしいミルク', 'ごくじょうのカビ', 'せかいじゅのしずく')
add_recipe(G, 'かちかちチーズ', 'ふつうのチーズ', '岩塩')
add_recipe(G, 'やわらかチーズ', 'おいしいミルク', 'レンネットのこな', '岩塩')
add_recipe(G, 'フバフバチーズ', 'ふつうのチーズ', 'まほうのせいすい')
add_recipe(G, 'はりきりチーズ', '激辛チーズ', 'こごえるチーズ', '岩塩')
add_recipe(G, 'ごくじょうのカビ', 'あかいカビ', 'みず草のカビ', 'せかいじゅの葉')
add_recipe(G, '盗賊の鍵', '鉄のクギ', 'ブロンズナイフ')
add_recipe(G, 'どうのつるぎ', 'ブロンズナイフ', 'ブロンズナイフ')
add_recipe(G, '古びたつるぎ', 'はぐれメタルの剣', 'おかしな薬', 'うしのふん')
add_recipe(G, '聖銀のレイピア', 'テンペラーソード', 'まよけの聖印')
add_recipe(G, 'はやぶさの剣・改', 'はやぶさの剣', 'ほしふる腕輪')
add_recipe(G, '堕天使のレイピア', '聖銀のレイピア', 'あくまのしっぽ', 'こうもりのはね')
add_recipe(G, 'ゾンビバスター', 'ゾンビキラー', 'まよけの聖印')
add_recipe(G, 'もろはのつるぎ', 'もろはのつるぎ・改', 'あくまのしっぽ')
add_recipe(G, 'もろはのつるぎ・改', 'もろはのつるぎ', '聖者の灰', '聖者の灰')
add_recipe(G, '疾風のレイピア', '堕天使のレイピア', 'しっぷうのバンダナ', 'しっぷうのバンダナ')
add_recipe(G, 'ドラゴンスレイヤー', 'ドラゴンキラー', 'ごうけつのうでわ')
add_recipe(G, 'ふぶきのつるぎ', 'バスターソード', 'こおりのやいば', 'こごえるチーズ')
add_recipe(G, 'きせきのつるぎ・改', 'きせきの剣', '命のブレスレット')
add_recipe(G, 'ライトシャムシール', 'ルーンスタッフ', 'ライトシールド', 'ひかりのドレス')
add_recipe(G, 'はぐれメタルの剣', '古びたつるぎ', 'スライムのかんむり', 'オリハルコン')
add_recipe(G, '鉄のヤリ', 'ひのきのぼう', 'ダガーナイフ')
add_recipe(G, 'ロングスピア', '鉄のヤリ', 'ひのきのぼう', 'ひのきのぼう')
add_recipe(G, 'ホーリーランス', 'ロングスピア', '金のロザリオ')
add_recipe(G, '砂塵のヤリ', 'パルチザン', '聖者の灰')
add_recipe(G, 'デーモンスピア', 'バトルフォーク', 'どくばり', 'あくまのしっぽ')
add_recipe(G, 'ハイブーメラン', 'ブーメラン', '鉄のクギ')
add_recipe(G, 'ウイングエッジ', 'やいばのブーメラン', 'こうもりのはね', 'はがねのかま')
add_recipe(G, '炎のブーメラン', 'ツインスワロー', '炎の盾')
add_recipe(G, 'メタルウイング', 'ウイングエッジ', 'メタルキングのヤリ')
add_recipe(G, '石のオノ', '石のぼうし', 'ひのきのぼう')
add_recipe(G, '金のオノ', '鉄のオノ', '金塊')
add_recipe(G, '鉄のオノ', '鉄のかま', '鉄のかま')
add_recipe(G, 'さんぞくのオノ', 'とうぞくのかぎ', 'バトルアックス')
add_recipe(G, 'ムーンアックス', '金のオノ', '月のめぐみ')
add_recipe(G, 'キングアックス', '金のオノ', 'スライムのかんむり')
add_recipe(G, '大かなづち', '大きづち', '鉄かぶと', '鉄かぶと')
add_recipe(G, 'ウォーハンマー・改', 'ウォーハンマー', 'ごうけつの腕輪')
add_recipe(G, 'メガトンハンマー', 'ウォーハンマー・改', 'はおうのオノ', 'オリハルコン')
add_recipe(G, 'じごくのおおかま', 'はがねのかま', 'どくがのナイフ', 'サタンヘルム')
add_recipe(G, 'キラーピアス', 'スライムピアス', '怒りのタトゥー', 'はやてのリング')
add_recipe(G, 'アサシンダガー', 'イーグルダガー', 'どくばり')
add_recipe(G, 'こあくまのナイフ', 'アサシンダガー', 'あくまのしっぽ')
add_recipe(G, '皮のムチ', 'あくまのしっぽ', '聖者の灰')
add_recipe(G, 'ヘビ皮のムチ', '皮のムチ', 'うろこの盾')
add_recipe(G, 'ドラゴンテイル', 'ヘビ皮のムチ', '竜のうろこ', '竜のうろこ')
add_recipe(G, 'あくまのムチ', 'バスターウィップ', 'あくまのしっぽ')
add_recipe(G, 'バスターウィップ', 'あくまのムチ', '聖者の灰')
add_recipe(G, 'マグマの杖', 'まどうしの杖', 'ばくだん岩のかけら', 'ばくだん岩のかけら')
add_recipe(G, 'まふうじの杖', 'まどうしの杖', 'ルーンスタッフ')
add_recipe(G, 'ふっかつの杖', 'ルーンスタッフ', '命のブレスレット', 'せかいじゅの葉')
add_recipe(G, 'クロスボウ', '力の指輪', 'ひのきのぼう', 'ひのきのぼう',)
add_recipe(G, 'クロスボウ', 'ショートボウ', 'チェーンクロス')
add_recipe(G, 'エロスの弓', 'クロスボウ', 'ガーターベルト')
add_recipe(G, 'ケイロンの弓', 'エロスの弓', '力の盾')
add_recipe(G, 'オーディーンボウ', 'ケイロンの弓', 'エロスの弓', 'ビッグボウガン')
add_recipe(G, 'たびびとの服', '布の服', '布の服')
add_recipe(G, 'ステテコパンツ', 'とうぞくのこしみの', 'バンダナ')
add_recipe(G, '皮のよろい', 'たびびとの服', 'まじゅうの皮')
add_recipe(G, '皮のこしまき', 'ステテコパンツ', 'まじゅうの皮')
add_recipe(G, '騎士団の服', 'たびびとの服', '騎士団の盾')
add_recipe(G, '皮のドレス', 'おどりこのふく', 'まじゅうの皮')
add_recipe(G, 'うろこのよろい', '皮のよろい', '竜のうろこ')
add_recipe(G, 'くさりかたびら', 'たびびとのふく', 'チェーンクロス')
add_recipe(G, 'せいどうのよろい', 'せいどうの盾', 'くさりかたびら')
add_recipe(G, '鉄のむねあて', '鉄の盾', '鉄の盾')
add_recipe(G, '毛皮のポンチョ', 'まじゅうの皮', 'まじゅうの皮')
add_recipe(G, 'やすらぎのローブ', 'みかわしの服', 'ステテコパンツ')
add_recipe(G, 'バニースーツ', 'シルクのビスチェ', 'うさぎのしっぽ')
add_recipe(G, 'ゾンビメイル', 'シルバーメイル', 'ゾンビキラー', 'プラチナメイル', 'あくまのしっぽ')
add_recipe(G, '銀のむねあて', '鉄のむねあて', 'シルバートレイ', 'シルバートレイ')
add_recipe(G, 'けんじゃのローブ', 'まほうの法衣', 'インテリハット')
add_recipe(G, 'マジカルスカート', 'マジカルハット', 'マジカルメイス', 'とうぞくのこしみの')
add_recipe(G, 'まほうのよろい', 'はがねのよろい', 'いのりの指輪', 'まもりのルビー')
add_recipe(G, 'ダンシングメイル', 'おどりこの服', 'シルバーメイル')
add_recipe(G, 'ドラゴンメイル', 'シルバーメイル', '竜のうろこ', '竜のうろこ')
add_recipe(G, 'ひかりのドレス', 'スパンコールドレス', 'まもりのルビー', '金のブレスレット')
add_recipe(G, 'やいばのよろい', 'まほうのよろい', 'やいばのブーメラン')
add_recipe(G, 'プラチナメイル', 'ゾンビメイル', '聖者の灰')
add_recipe(G, '天使のローブ', 'みずのはごろも', 'マジカルスカート')
add_recipe(G, '紅蓮のローブ', 'けんじゃのローブ', 'まほうのせいすい', 'ヌーク草')
add_recipe(G, 'バンデットメイル', 'あつでのよろい', 'さんぞくのオノ', 'とうぞくのこしみの')
add_recipe(G, 'やみのころも', 'みかわしの服', 'こうもりのはね', 'あくまのしっぽ')
add_recipe(G, 'ミラーアーマー', 'シルバーメイル', 'ミラーシールド', 'ミラーシールド')
add_recipe(G, 'プリンセスローブ', '天使のローブ', 'ひかりのドレス', '金のロザリオ')
add_recipe(G, 'ギガントアーマー', 'バンデットメイル', 'ごうけつのうでわ', 'ごうけつのうでわ')
add_recipe(G, 'しんぴのビスチェ', 'あぶないビスチェ', 'ひかりのドレス')
add_recipe(G, 'メタルキングよろい', 'はぐれメタルよろい', 'スライムのかんむり', 'オリハルコン')
add_recipe(G, '皮のたて', 'まじゅうの皮', 'なべのふた')
add_recipe(G, 'うろこの盾', '皮の盾', '竜のうろこ')
add_recipe(G, 'せいどうの盾', '皮の盾', 'ブロンズナイフ')
add_recipe(G, '騎士団の盾', '鉄の盾', '騎士団の服')
add_recipe(G, 'ホワイトシールド', '鉄の盾', 'シルバートレイ', 'ライトシールド', 'おいしいミルク', 'おいしいミルク')
add_recipe(G, 'まほうの盾', 'はがねの盾', 'いのりの指輪', 'まもりのルビー')
add_recipe(G, 'ドラゴンシールド', 'はがねの盾', '竜のうろこ', '竜のうろこ')
add_recipe(G, 'こおりの盾', 'まほうの盾', 'こおりのやいば')
add_recipe(G, 'ほのおの盾', 'まほうの盾', '炎のブーメラン')
add_recipe(G, '力の盾', 'まほうの盾', '力の指輪', 'ベホマラチーズ')
add_recipe(G, '聖女の盾', 'ミラーシールド', 'ホワイトシールド', 'せいすい')
add_recipe(G, 'みかがみの盾', 'ミラーシールド', 'アモールの水', 'まほうのせいすい')
add_recipe(G, 'はめつの盾', 'メタルキングの盾', 'あくまのしっぽ')
add_recipe(G, '死神の盾', '女神の盾', 'あくまのしっぽ')
add_recipe(G, '女神の盾', '死神の盾', '聖者の灰')
add_recipe(G, 'メタルキングの盾', 'はめつの盾', '聖者の灰', 'オリハルコン')
add_recipe(G, 'とんがりぼうし', 'かわのぼうし', '鉄のクギ')
add_recipe(G, 'ターバン', 'バンダナ', 'バンダナ')
add_recipe(G, 'はねぼうし', 'かわのぼうし', 'キメラのつばさ')
add_recipe(G, 'うさみみバンド', 'うさぎのしっぽ', 'ヘアバンド')
add_recipe(G, '石のぼうし', '石のオノ', 'とんがりぼうし')
add_recipe(G, '毛皮のフード', 'はねぼうし', '毛皮のポンチョ')
add_recipe(G, 'かぜのぼうし', 'はねぼうし', 'しっぷうのバンダナ')
add_recipe(G, 'ブロンズキャップ', '石のぼうし', 'ブロンズナイフ', 'ブロンズナイフ')
add_recipe(G, 'しっぷうのバンダナ', 'はやてのリング', 'バンダナ')
add_recipe(G, '銀のかみかざり', 'サンゴのかみかざり', 'シルバートレイ')
add_recipe(G, 'しあわせのぼうし', 'はねぼうし', 'しあわせのくつ')
add_recipe(G, 'インテリハット', 'マジカルハット', 'インテリメガネ')
add_recipe(G, 'サタンヘルム', 'ミスリルヘルム', 'あくまのしっぽ')
add_recipe(G, '知力のかぶと', 'インテリハット', 'アイアンヘッドギア')
add_recipe(G, 'ミスリルヘルム', 'サタンヘルム', '聖者の灰')
add_recipe(G, '猛牛ヘルム', 'ミスリルヘルム', 'うしのふん', 'おいしいミルク')
add_recipe(G, '黄金のティアラ', '知力のかぶと', '銀のかみかざり', '金塊')
add_recipe(G, 'ファントムマスク', 'アイアンヘッドギア', 'やみのころも')
add_recipe(G, 'ドクロのかぶと', '太陽のかんむり', 'あくまのしっぽ')
add_recipe(G, '太陽のかんむり', 'ドクロのかぶと', '聖者の灰')
add_recipe(G, '力の指輪', 'いのりの指輪', '力のたね')
add_recipe(G, 'パワーベルト', '皮のこしまき', '力の指輪')
add_recipe(G, 'ごうけつの腕輪', '力の指輪', 'パワーベルト')
add_recipe(G, '命のブレスレット', '命の指輪', '金のブレスレット')
add_recipe(G, 'いのりの指輪', '金の指輪', 'ふしぎなきのみ')
add_recipe(G, '破幻のリング', '金の指輪', '砂塵のヤリ')
add_recipe(G, '破毒のリング', '金の指輪', 'どくばり')
add_recipe(G, 'まよけの聖印', '怒りのタトゥー', 'せいすい', '金のロザリオ')
add_recipe(G, 'まんげつのリング', '金の指輪', 'どくがのナイフ')
add_recipe(G, '目覚ましリング', '金の指輪', 'まどろみ剣')
add_recipe(G, '理性のリング', '金の指輪', '堕天使のレイピア')
add_recipe(G, '命の指輪', 'いのりの指輪', '命のきのみ')
add_recipe(G, 'スーパーリング', 'まんげつのリング', '破幻のリング', '破毒のリング')
add_recipe(G, 'まもりのルビー', 'いのりの指輪', 'まもりのたね')
add_recipe(G, 'はやてのリング', 'いのりの指輪', 'すばやさのたね')
add_recipe(G, 'ほしふるうでわ', 'はやてのリング', 'はやてのリング', 'オリハルコン')
add_recipe(G, 'ドクロの指輪', 'ソーサリーリング', 'あくまのしっぽ')
add_recipe(G, 'ソーサリーリング', 'ドクロの指輪', '聖者の灰', '聖者の灰')
add_recipe(G, 'インテリメガネ', '目覚しリング', '理性のリング', 'かしこさのたね')
add_recipe(G, '女神の指輪', '命の指輪', '黄金のティアラ', 'オリハルコン')
return G
まず、興味のある有向グラフの強連結成分をすべて求めることにする。ただし、連結成分のうち構成する点がひとつしかないものについては興味がないので、複数点からなる連結成分だけを出力する。
def print_strongly_connected_components(G):
"""Print strongly connected components to stdout.
Args:
G (Graph): A directed graph.
Returns:
None
"""
components = nx.strongly_connected_components(G)
for i in components:
if len(i) > 1:
print(i)
本コードを実行すると、次の結果が得られる。これが意味するところは、各連結成分内では、その各アイテム（ノード）に錬金操作に関する推移律が成り立つということだ。例えば「ふつうのチーズ」から（複数の）錬金操作を経ての「超辛チーズ」の生成可能性を示している。逆に「超辛チーズ」から「ふつうのチーズ」の生成可能性も示している（ゲームでは勿体ないからやらないほうがよい）。
['太陽のかんむり', 'ドクロのかぶと']
['超辛チーズ', 'ふつうのチーズ', '辛口チーズ', '激辛チーズ', '冷たいチーズ', 'こおりのチーズ', 'こごえるチーズ', 'かがやくチーズ']
['古びたつるぎ', 'はぐれメタルの剣']
['アモールの水', 'せいすい']
['あくまのムチ', 'バスターウィップ']
['騎士団の盾', '騎士団の服']
['石のぼうし', '石のオノ']
['女神の盾', '死神の盾']
['はめつの盾', 'メタルキングの盾']
['サタンヘルム', 'ミスリルヘルム']
['ゾンビメイル', 'プラチナメイル']
['ドクロの指輪', 'ソーサリーリング']
['もろはのつるぎ', 'もろはのつるぎ・改']
その他の連結成分¶
Todo
その他の連結成分について述べる。
