graph

グラフのはなし・その11

さて前回 mro のトポロジカルソートを使った実装までできたのですが, mro の失敗が検知できない不十分なアルゴリズムで実装してしまいました.今回はその不十分なところを修正するために, 今まで 2 つ (「未探索」と「探索済」) しかなかったノードの状態を 3…

グラフのはなし・その10

さて今回は C3 アルゴリズムをトポロジカルソートで書けることを示してみましょう. 戦略 さて C3 アルゴリズムの肝は何だったかと言うと, それぞれの親クラスにとっての祖先クラスの順序と, 親クラスどうしの順序が食い違わないように, 祖先クラスを並べるこ…

グラフのはなし・その9

今日は Perl や Python のクラスの多重継承で使われているアルゴリズム C3 を紹介します.多重継承でメソッドを呼び出した場合, 複数の親クラスを持つので今呼び出しているメソッドがどの親に属しているのかを調べなければなりません. そしてその順序も決めて…

グラフのはなし・その8

さて今日は目標の1つであったトポロジカルソートのプログラムを見てみましょう. 基本的な構造は昨日の深さ優先探索 (DFS) と同じです. 今日トポロジカルソートを行う DAG (輪っか無しの矢印グラフ) はこれです. 0 -> 1 -> 3 | `-> 4 | V `-> 2 -> 5 `-> 6昨…

グラフのはなし・その7

ちょっと今日は趣向を変えて, プログラムで語ってみます.昨日まで理論の話だったので, 少し頭を切り替えて Python で深さ優先探索を書いてみます. ソースコード こんなふうなグラフを 0 からスタートして深さ優先探索してみましょう. このグラフは DAG にな…

グラフのはなし・その6

さて, 今日からは探索やソートの話をしていきます.探索やソートについては以前も触れましたが, ここで簡単におさらいをしておきます. ソート (sort) とは ソートは日本語に訳すと「並びかえ」になります. 文字通りなんらかの順序でものを並べかえる作業のこ…

グラフのはなし・その5

さて今日は「順序をグラフで書こう」の話の 3 回目.今まで全順序, 半順序と扱ってきましたが, それぞれ順序のルールがかなり縛りのきついものだったので, グラフの形も分かりやすいものでした. 覚えていますか? 全順序は一直線のグラフになりましたし, 半順…

グラフのはなし・その4

だんだん連載記事を書く時刻が遅くなっている cocoatomo です。はてダの日付変更線が3:00くらいらしいので助かってます。追記: 今日は書かずに寝てしまったので、次の日の朝に更新してます。さて今日は昨日持ち越した、半順序をグラフで表現してみようという…

グラフのはなし・その3

これまで順序の話として全順序, 半順序, 前順序について書いてきました.今日はその順序をグラフで書くとどうなるか? という話をします. 全順序をグラフで では簡単な全順序を用意してそのグラフを見てみましょう.3つの点に A, B, C と名前を付けて, A ≦ B C …

グラフのはなし・その2

昨日は休講にしてしまいましたが、今日はやります。 さて、一昨日「グラフとはどんなものか?」という話をしました。次にグラフの点の順序付けの話をするのですが、話の展開をどういったペースで書けばいいのかまだ感触が掴めないので、まずは簡単な例から話…

グラフのはなし

今日は昨日までと話題を変えてグラフの話をします. でも順序の話とつながっている話なのです. どうつながっているかは追々. グラフとは? グラフと聞くと y = f(x) を xy 平面に書いたものを思い浮かべる人がいるかもしれませんが, ここで言うグラフはそのグ…