読者です 読者をやめる 読者になる 読者になる

DAG (Directed acyclic graph) - 有向非巡回グラフ

先日、JJUG CCC 2015 Fallに参加して、灰色のサイトで有名なひしだまさん(ひしだま (@hishidama) | Twitter)の「GH-6 Java8 Stream APIとApache SparkとAsakusa Frameworkの類似点・相違点」を聞いた際に出てきた「DAG (Directed acyclic graph) - 有向非巡回グラフ」が面白そうだったので調べてみた。

DAGとは

Wikiによると、

グラフ理論における閉路のない有向グラフの事。
有向グラフは頂点と有向辺(方向を示す矢印付きの辺)からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである。

wikipedia:有向非巡回グラフ

となっている。

DAGの例

Wikiの例はわかりづらいので、JJUG CCC 2015 Fallのひしだまさんのスライドを見ると、18枚目に例が載っている。

左は向きがない(無向)なのでDAGではない。
中央は菱型の条件分岐で上に戻っている(巡回)のでDAGではない。
右は向きがあって(有向)条件分岐があるが循環していない(非巡回)のでDAGであると言える。

ひしだまさんの発表は、DAGで例題を示し、Stream APIとSparkとAsakusaFWの相違点について説明するという流れになっていた。
説明も聞いていたが、自分はこのDAGが気になってしまって、心の半分がDAGに持って行かれていたことは内緒としておきたい・・・。

DAGの活用

DAGを使うと、今まで言葉でしか説明していなかったものや、なんとなく図式化していたものを明確に説明できるのではないだろうか。

例えば

社員一覧画面は、社員マスタからデータを取得し表示する。
ただし所属は所属マスタから取得し表示すること。

のようなものは下記のように表せる。
f:id:nave_kazu:20151130154420p:plain

うん。わかりやすい。


もう少し複雑な例だと日締め処理のバッチなど。

その日一日の取引内容を集計する。
集計結果はPDF化し担当部署長宛にメールにて通知する。

のようなものは下記のように表せる。
f:id:nave_kazu:20151130154422p:plain

ここまでやってて、もっとDAGを用いるのに適した分野があることに気付いた。
そう、料理のレシピだ。

DAGを用いた料理のレシピ

例えばみんなのきょうの料理に掲載されている「かじきのガーリック炒めレシピ」だと、このようになる。
f:id:nave_kazu:20151130154424p:plain

ちなみにカレーのレシピはこのようになる。
f:id:nave_kazu:20151130154427p:plain

このように、DAGの応用範囲は広いということがわかった。
料理のレシピはDAGでも併せて記述するべきだと思う。