12

06

[Ruby] 循環している有向グラフから循環していない有向グラフを得る

2010.12.06(22:45)

RubyのHashで構成された
循環している有向グラフから循環していない有向グラフを得るプログラム

tsortするには循環がない有向グラフを与えなければならないため、
その前段のプログラムとして作成しました。

以下の、前から後を作るプログラムです。循環のどこを切るかは適当です。
"-------------------------"
前 {"1"=>["2"], "2"=>["1"]}
後 {"1"=>["2"], "2"=>[]}
"-------------------------"
前 {"1"=>["2"], "2"=>["3"], "3"=>["1"]}
後 {"1"=>["2"], "2"=>["3"], "3"=>[]}
"-------------------------"
前 {"1"=>["2"], "2"=>["3"], "3"=>["2"]}
後 {"1"=>["2"], "2"=>["3"], "3"=>[]}
"-------------------------"
前 {"1"=>["2", "5"], "2"=>["3", "4"], "3"=>[], "4"=>["5"], "5"=>[]}
後 {"1"=>["2", "5"], "2"=>["3", "4"], "3"=>[], "4"=>["5"], "5"=>[]}
"-------------------------"
前 {"1"=>["2", "5"], "2"=>["1", "3", "4"], "3"=>[], "4"=>["5"], "5"=>[]}
後 {"1"=>["2", "5"], "2"=>["3", "4"], "3"=>[], "4"=>["5"], "5"=>[]}
"-------------------------"
前 {"1"=>["2", "5"], "2"=>["1", "3", "4"], "3"=>["1"], "4"=>["1", "5"], "5"=>["1"]}
後 {"1"=>["2", "5"], "2"=>["3", "4"], "3"=>[], "4"=>["5"], "5"=>[]}
"-------------------------"

ソース

# 循環参照のあるハッシュから、循環参照を取り除く
# {"1"=>["2","5"], "2"=>["1","3","4"], "3"=>[], "4"=>["5"], "5"=>[]} から
# {"1"=>["2", "5"], "2"=>["3", "4"], "3"=>[], "4"=>["5"], "5"=>[]} を作り出す
def solver(hash, depends, ancestor = nil)
# 祖先の配列
ancestor = [] if ancestor == nil
# 祖先へ戻らない子たち
uni_depends = []
# 全ての子たちについて
depends.each { |depend|
# 祖先へ戻っているなら次へ
next if ancestor.include?(depend)
# 祖先へ戻らない子だった。
uni_depends << depend
# その子を祖先に追加して
ancestor.push(depend)
# その子を再帰的に調べる。深さ優先。祖先へ戻らない子たちを返す
hash[depend] = solver(hash, hash[depend], ancestor)
# 帰ってきたらその子は忘れて次の子へ
ancestor.pop
}
# 祖先へ戻らない子たちの配列を返す
uni_depends
end


使い方

hash = { "1"=>["2"], "2"=>["1"] }
p hash
solver(hash, hash.keys)
p hash


実行結果

{"1"=>["2"], "2"=>["1"]}
{"1"=>["2"], "2"=>[]}
[["1", "2"]]


さらに拡張し、循環グラフも返せるようにする。

# 循環参照のあるハッシュから、循環参照を取り除くとともに、循環グラフを返す
# {"1"=>["2","5"], "2"=>["1","3","4"], "3"=>[], "4"=>["5"], "5"=>[]} から
# {"1"=>["2", "5"], "2"=>["3", "4"], "3"=>[], "4"=>["5"], "5"=>[]} を作り出す
# cyclicに、{"1"=>"2"] を返す
def solver(hash, depends, cyclic, ancestor = nil)
# 祖先の配列
ancestor = [] if ancestor == nil
# 祖先へ戻らない子たち
uni_depends = []
# 全ての子たちについて
depends.each { |depend|
# 祖先へ戻っている場合
if ancestor.include?(depend)
first = ancestor.index(depend)
last = ancestor.size
cyclic << Array.new(ancestor[first,last])
# 祖先へ戻らない場合
else
uni_depends << depend
# その子を祖先に追加して
ancestor.push(depend)
# その子を再帰的に調べる。深さ優先。祖先へ戻らない子たちを返す
hash[depend] = solver(hash, hash[depend], cyclic, ancestor)
# 帰ってきたらその子は忘れて次の子へ
ancestor.pop
end
}
# 祖先へ戻らない子たちの配列を返す
return uni_depends
end


使い方

hash = { "1"=>["2","5"], "2"=>["1","3","4"], "3"=>[], "4"=>["5"], "5"=>[] }
p hash
cyclic = []
solver(hash, hash.keys, cyclic)
p hash
p cyclic


実行結果

{"1"=>["2", "5"], "2"=>["1", "3", "4"], "3"=>[], "4"=>["5"], "5"=>[]}
{"1"=>["2", "5"], "2"=>["3", "4"], "3"=>[], "4"=>["5"], "5"=>[]}
[["1", "2"]]
プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示