明日からgraphlib、みんなで使おう

Python 3.9で標準ライブラリにgraphlibが追加されました。graphlibはグラフ理論におけるグラフのトポロジカルソートを行うライブラリです。グラフ理論におけるグラフとは何か、トポロジカルソートとは何にか、結局graphlibは何に使えるのか、すべて（なるべく）解説します。明日からgraphlib、みんなで使おう。

導入

Python 3.9で標準ライブラリにgraphlibが追加されました。 しかし、公式ドキュメントにはgraphlibが導入されたモチベーションや利用例に乏しく、すでにトポロジカルソートの存在を知っている人しか使えないライブラリになっています。 結局、graphlibは何に使えるのか、電池が液漏れする前に（なるべく）すべて解説します。

グラフ理論速習

graphとは数学のグラフ理論におけるグラフを意味します。 グラフとは（大雑把に説明すれば）物事とその関係性を数学的にモデル化したものであり、鉄道網における駅と線路、人間関係における人間と友人関係など、日常生活においてグラフでモデル化できるものはたくさんあります。

• グラフとは
• 無向グラフと有向グラフ（今回扱うのは有向グラフ）
• 線型順序について（半順序関係、全順序関係）

トポロジカルソート、有向非巡回グラフ（DAG）について

任意のグラフがトポロジカルソートできるわけではありません。 グラフが有向非巡回グラフであることと、グラフがトポロジカルソート可能であることは同義であることを説明します。

• 有向非巡回グラフの定義
• トポロジカルソートの定義
• グラフが有向非巡回グラフであることと、グラフがトポロジカルソート可能であることは同義

graphlibの使い方

ここまで理解できれば、明日からgraphlibを使えるようになります。 少なくとも、頭の片隅にgraphlibが入り、必要になった瞬間に思い出せるようになります。

• graphlibの使い方
• 応用例: タスクの処理（タスク処理順序の決定、簡易的なタスクランナーの実装）

Pythonの標準ライブラリはbatteries includedの名の通り非常に充実していますが、中には使い方が難しいものもあります。 そのようなライブラリの存在を知って欲しい、という思いがあります。 graphlibを選んだのは、発表者の学生時代の専攻が数学のグラフ理論であるからです。

graphlibの使い方となります。 また、graphlibの存在は、Pythonが数学や理論計算機科学との親和性が高いことを示しているので、それも伝えたいと考えています。

Pythonに関しては文法を知っていれば十分です。 数学に関しては説明しますが、やはり難しいかもしれません。