Home
最新のドキュメントは英語版を参照ください．
- Graphillion 1.0 がとうとうリリースされました．
- 2015年4月に，Graphillion の本が出版されます．
- 2015年1-2月に，奈良先端科学技術大学院大学の川原純先生による講義で Graphillion が使われました．
Graphillion は、グラフセットもしくはグラフ集合に対する検索、最適化および列挙のための Python パッケージです。
- 超大規模グラフを扱うための軽量なデータ構造
- 膨大な数のグラフに対する検索、最適化、列挙
- 電力網の評価（DNET）、鉄道網分析（Ekillion）などでの使用実績 (詳しくは 参考資料)
- C/C++ により Python を拡張する効率的な実装
- OpenMP による 並列計算
- NetworkX のようなグラフツールとの連携
- オープンソースの MIT ライセンス
- 600 以上のテストをクリアした信頼性
- Python によるメリット：高速なプロトタイピング、教えやすさ、マルチ・プラットフォーム
Graphillion について興味を持たれた方は、以下の動画もご覧ください。
-
Graphillion はなぜ必要か？ おねえさんといっしょ！ みんなで数えてみよう！（100万再生を突破！）
-
Graphillion とは何か？ Graphillion: 数え上げおねえさんを救え
Graphillion は、効率的なグラフセット操作のための Python ライブラリです。 NetworkX のような既存のグラフツールが１つのグラフを操作するために設計されているのと比較して、Graphillion は大規模なグラフ集合を効率的に扱うことができます。 驚くべきことに、Graphillion は１兆の１兆倍といった数のグラフをたった１台のコンピュータで扱うことができます。
「グラフセット」という概念は一般的ではないかもしれませんが、グラフから複数のサブグラフを切り出すような場合に必要となる考え方です。 たとえば、道路地図から走行可能なルートを割り出したり、電力網において実現可能な送電経路を調べたり、あるいは化学反応ネットワークの構造を評価したりする場合です。 サブグラフの数はグラフサイズによって指数関数的に増加するので、数百程度のエッジからなるグラフでも、サブグラフは何兆という数になり得ます。 上の動画でも示したように、このサブグラフを単純に数え上げていては何百万年もかかってしまいます。 Graphillion は、この問題を解決します。
Graphillion によって、複雑かつ非凸型制約のグラフセットに対する効率的で網羅的な検索が可能となります。 加えて、複雑なグラフセットから上位ｋ個の最適グラフを見つけたり、集合に含まれる全グラフから共通の特性を抽出することもできます。 これらの特徴により、Graphillion はグラフ・データベース、組み合わせ最適化、グラフ構造分析などさまざまな目的に応用できます。 電力網の評価を含むいくつかの使用例を、このあとのチュートリアルで紹介します。
Graphillion は MIT ライセンスの下で自由に使用することができます。 また Graphillion は主に JST ERATO 湊離散構造処理系プロジェクトにて開発されています。 論文に Graphillion を使用される場合は、以下の論文を記載くださいますようお願いいたします。
Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato: "Graphillion: Software Library Designed for Very Large Sets of Labeled Graphs," International Journal on Software Tools for Technology Transfer, Springer, vol.18, issue 1, pp.57-66, February 2016. (pdf)
Graphillion は開発途上です。 利用していただき、多くの人々に利益をもたらす改良は大歓迎です。
では、Graphillion のインストールとチュートリアルに進みましょう。 Graphllion のパワーと実用性をぜひ体験して下さい。
- 64ビットマシン
- 桁数の大きな数値を扱うために必要
- Python 2.7/3.4 以上
- NetworkX and Matplotlib (任意)
$ sudo pip install networkx
$ sudo pip install matplotlib- Python 開発環境 (
Python.h)- macOS では XCode に含まれています．Ubuntu では
apt-get install python-devでインストールできます．
- macOS では XCode に含まれています．Ubuntu では
- GCC や Clang などの C++ コンパイラ
- Graphillion のビルドには、gcc バージョン 4.2 以上が必要です。
- Mac OS X で Graphillion を使うには、Apple が配布している Xcode の Clang をお使い下さい。でないと、メモリアロケーションエラーが発生する可能性があります。
-
Visual C++ 2015 Redistributable Packages
- Windows で Graphillion を実行するために必要です．
桁数の大きな数値を効率的に扱うため、Graphillion には 64 ビット環境が必要です。
次のようにタイプするだけです。
$ sudo pip install graphillionお使いの OS および Python に最適なバージョンがインストールされます。
FreeBSD をお使いの場合は、FreeBSD Ports によってもインストールが可能です。
ソースコードのアーカイブファイル（tar.gz または zip ファイル）をダウンロードして、または GitHub ソースコード・リポジトリからチェックアウトして、インストールすることができます。
- ソースコード（tar.gz または zip ファイル）を https://github.com/takemaru/graphillion からダウンロードする
- アーカイブを展開し、ソースコードのディレクトリ（setup.py があるディレクトリ）に移動する
-
python setup.py buildを実行してビルドする - （任意）
python setup.py test -qでテストを行う -
sudo python setup.py installを実行してインストールする
- Graphillion のリポジトリをクローンする
git clone https://github.com/takemaru/graphillion.git - "graphillion" ディレクトリに移動する
-
python setup.py buildを実行してビルドする - （任意）
python setup.py test -qでテストを行う -
sudo python setup.py installを実行してインストールする
もしシステムにソフトウェアをインストールする権限を持っていない場合は、-user、-prefix、-home オプションを setup.py に指定して、別のディレクトリへインストールすることができます。
以下の例を参照して下さい。
$ python setup.py install --prefix=/home/username/python
or
$ python setup.py install --home=~
or
$ python setup.py install --userもし標準的な site-packages ディレクトリ以外に Python をインストールした場合は、PYTHONPATH 変数を適切に設定する必要があります。
詳しくは http://docs.python.org/inst/search-path.html を参照して下さい。
Graphillion for Windows をご覧ください．
もしまだ おねえさんといっしょ！ みんなで数えてみよう！ 動画をご覧になっていない場合は、チュートリアルを始める前にぜひご覧下さい。 100万回以上再生されているこの動画を見れば、Graphillion の必要性が納得できると思います。 また Graphillion: 数え上げおねえさんを救え 動画は、このチュートリアルの要約になっています。
これらの動画によって、Graphillion の必要性と特徴は理解いただけたと思います。 それでは Graphillion について詳しく見ていきましょう。
まず、Graphillion で使われる用語についていくつか紹介します。
| 用語 | 説明 | 例 |
|---|---|---|
| 頂点(vertex) | 任意のハッシュ可能オブジェクト |
1, 'v1', (x, y)
|
| 辺(edge) | 頂点のタプル（組） | (1, 2) |
| 重み付き辺(weighted edge) | 重みを持った頂点のタプル | (1, 2, -1.5) |
| グラフ(graph) | （重みを持った）辺のリスト | [(1, 2, -1.5), (1, 3)] |
| グラフ集合(set of graphs) | グラフセット | GraphSet([[(1, 2), (1, 3)], [(1, 2), (2, 3)]]) |
数値、テキスト文字列などハッシュ可能なあらゆるオブジェクトが頂点（ノード）になることができます。 辺（リンク）は頂点のペアとして定義され、グラフは辺のリストとして定義されます。 現時点では、Graphillion は無向グラフにのみ対応します。 グラフセットオブジェクトにはグラフの集合が格納されます。
何よりもまず、Python を起動し Graphillion およびヘルパー・モジュールをインポートしましょう。 ヘルパー・モジュールは、チュートリアルで用いるグラフの作成や描画に関するいくつかの機能を提供します。
$ python
>>> from graphillion import GraphSet
>>> import graphillion.tutorial as tl # チュートリアルのためのヘルパー・モジュールまずはじめに、「ユニバース」を定義します。ユニバースはグラフであり、Graphillion が扱うグラフはこのグラフの部分グラフとなります。 このチュートリアルでは、８×８の格子グラフをユニバースとして使います（グラフサイズは９×９とみなすべきですが、ここでは動画での定義に従うことにします）。
>>> universe = tl.grid(8, 8)
>>> GraphSet.set_universe(universe)
>>> tl.draw(universe) # ユニバースをポップアップウィンドウで表示する
対角頂点間を結ぶすべてのパスを見つけてみましょう。 動画では、スーパーコンピュータで４時間かかる処理でしたよね。
>>> start = 1
>>> goal = 81
>>> paths = GraphSet.paths(start, goal)
>>> len(paths) # 結果が大規模のときは paths.len() を使う
3266598486981642とても早かったでしょう？
（もし結果が 980466698 なら、あなたのマシンは32ビット環境ではないでしょうか？ Graphillion の実行には64ビット環境が必要です）
paths オブジェクトにはすべてのパスが含まれているので、それらを一つずつ列挙することができます。
>>> for path in paths:
... path
... # Ctrl-C で止めないと何年もかかってしまう
>>> tl.draw(paths.choice()) # パスのひとつを表示する
次に、Graphillion のフィルタリングおよび検索能力を示すために、条件を与えてパスを選んでみましょう。 図のように、宝箱とその鍵が格子グラフ上にあると仮定しましょう。
鍵を取ってから宝箱を通るすべてのパスを考えます。同じ場所を２度通ってはいけません。 まず宝箱を通らずに鍵にたどりつくすべてのパスを検索し、それから宝箱を通ってゴールにたどり着くすべてのパスを検索します。
>>> key = 64
>>> treasure = 18
>>> paths_to_key = GraphSet.paths(start, key).excluding(treasure) # 宝箱を通らずに鍵にたどり着くパス
>>> treasure_paths = paths.including(paths_to_key).including(treasure) # 鍵と宝箱を通ってゴールにたどり着くパス
>>> len(treasure_paths)
789438891932744
>>> tl.draw(treasure_paths.choice()) # パスのひとつを表示する
いま求めた（鍵と宝箱を通ってゴールにたどり着く）パスが、最初に求めた全パスのサブセットになっていることを確認しましょう。
>>> treasure_paths < paths # Graphillion において "<" は "subset-of" の意味
Trueランダムサンプリングによる統計的処理について紹介しておきましょう。 Graphillion はグラフセットから一様乱数に従うサンプル（グラフ）を選択することができます。 「宝箱パスが何回曲がるか」のヒストグラムを描くと次のようになります。
>>> i = 0
>>> data = []
>>> for path in treasure_paths.rand_iter():
... data.append(tl.how_many_turns(path)) # パスが曲がる回数を数える
... if i == 100: break
... i += 1
...
>>> tl.hist(data)
１つのパスがおおよそ30〜50回曲がることをヒストグラムは示しています。
Graphillion なしでは、10^14 パスもの大規模な集合からこのような複雑な性質を調査することは容易ではありません。
また、Graphillion が提供する最適化メソッド min_iter() を用いると、その宝物パスが５回曲がっていることもわかります。
>>> for path in treasure_paths.min_iter():
... print(tl.how_many_turns(path))
... break # break しないと、複数のパスが昇順で取り出される
...
5パス列挙の応用例として、ＪＲの大都市近郊区間におけるすべての経路を列挙する Ekillion もぜひご覧下さい。
Graphillion は格子グラフ以外のグラフにも使えますし、単純なパス以外の部分グラフも扱うことができます。 次の例として、図のような配電ネットワーク（電力供給網）を考えてみましょう。 このネットワークでは、頂点を家庭、辺をスイッチ付きの電力線だとします。 電力は四隅の発電所から供給されます。
>>> universe = tl.grid(8, 8, 0.37) # 8x8 の格子からランダムに 37 % の辺が取り除かれる
>>> GraphSet.set_universe(universe)
>>> generators = [1, 9, 73, 81]
>>> tl.draw(universe)
電力フローは、各電力線のスイッチの設定によって決定されます。
もしスイッチがオンであれば（グラフに辺があれば）、電力が送られます。
スイッチがオフであれば（グラフに辺がなければ）電力は送られません。
電力はすべての家庭に供給されなければなりませんが、ネットワークがショート（短絡）しないよう、ループを作ってはいけません。
つまり電力フローは、発電所を根（起点）とするツリーの集合として森になります。
そして、すべての森を次のように見つけることができます (上述のように，ネットワークは tl.grid() によってランダムに生成されるため，下記の数値 54060425088 は異なるかもしれません)。
>>> forests = GraphSet.forests(roots=generators, is_spanning=True) # forest にはすべての家庭をカバーし、かつループのない電力フローが格納される
>>> len(forests)
54060425088
>>> tl.draw(forests.choice())
１つの発電所から供給できる電力量には限りがあります。 上の図で示した例にはとても大きなツリーが含まれており、左上の発電所はその供給量を超えてしまうでしょう。 そこで、１つの発電所につき23家庭までにしか電力を供給できないことにしましょう。 それにはまず、供給量を超えた「危険な」ケースを見つけ出し、それを除いた「安全な」ケースを求めることにします。
>>> too_large_trees = GraphSet() # 空のグラフセット
>>> for substation in generators:
... too_large_trees |= GraphSet.trees(root=substation).larger(23) # 危険な電力フロー
...
>>> safe_forests = forests.excluding(too_large_trees) # 危険なケースを取り除いた、安全な電力フロー
>>> len(safe_forests)
294859080
>>> tl.draw(safe_forests.choice())
安全なフローを求めることができたので、最適化のテクニックを利用して、スイッチの設定を現在のものから安全なものに切り替えてみましょう。 現在の設定は次のように求めます。
>>> closed_switches = (forests - safe_forests).choice() # 安全でない電力フローにおけるオン状態(closed)スイッチの集合
>>> tl.draw(closed_switches)
新しい設定は安全なフローを実現しなければいけませんが、それと同時にスイッチの操作（オンからオフ、またはオフからオン）も少なくしたいものです。 そこで次の表のように、スイッチの現在および新しい状態に応じてスコア（辺の重み）をつけることにします。
| 現在 \ 新状態 | オフ | オン |
|---|---|---|
| オフ | 0 | -1 |
| オン | 0 | 1 |
>>> scores = {} # 新しい設定におけるオン状態スイッチのスコア（デフォルトは 0）
>>> for switch in universe:
... # もし現在の状態がオンならスコアは 1、でなければスコアは -1
... scores[switch] = 1 if switch in closed_switches else -1
...スコアが最大となる設定（森）を求めてみます。 得られた設定はスコアが最大であり、かつスイッチ操作は最小となります。 さきほど見た現在の設定と比較すると、とても似ているのがわかりますね。 たった８か所のスイッチを変更するだけで、危険な設定から安全な設定になっているのがわかります。
>>> for forest in safe_forests.max_iter(scores):
... tl.draw(forest)
... break # break しないと、複数の設定がスコアの高いものから取り出される
...
最後に、安全な電力供給を妨げるような深刻な障害について考えておきましょう。 そのためには最小のブロッキングセット、より一般的には極小ヒッティングセットを探す必要があります。 ヒッティングセットとは、与えられたすべての集合が、ヒッティングセット中の少なくとも１つの要素によってヒットされる（集合がその要素を含む）ような状態をいいます。 たとえば {1,2}, {2,3}, {3} の３つの集合が与えられているとき、極小ヒッティングセットは {1,3} および {2,3} となります。 ヒッティングセットは致命的な障害のパターンを示してくれます。 もしヒッティングセットに含まれる電力線に障害が発生した場合、電力フローが構成されなくなってしまいます。
>>> failures = safe_forests.blocking().minimal() # すべての極小ブロッキングセットからなる集合理解を助けるために、ネットワークからヒッティングセットに含まれるすべての電力線を取り除いてみましょう。 すると、安全なフローはひとつも残りません。
>>> failure = failures.choice() # ヒッティングセット（クリティカルな電力線の集合）
>>> for line in failure:
... safe_forests = safe_forests.excluding(line) # ヒッティングセットに含まれる電力線を取り除く
...
>>> len(safe_forests)
0たとえば５本未満の電力線からなる小さなヒッティングセットはネットワークの脆弱性であることが示唆されます。 いま 767 の小さな障害パターンが見つかりました。 これらは念入りに調査する必要があります。
>>> len(failures.smaller(5))
767実際の電力供給ネットワークはより複雑ですが、私たちはこれらのアイデアを用いて電力供給ネットワークを研究しています。 電力ロスを最小化し、非凸制約のもと非線形目的関数をもちいてネットワークを最適化するツールは DNET でご覧いただけます。
Graphillion では、グラフリスト、辺の制約、パスやツリーのようなグラフタイプ、の３つ方法でグラフセットを生成することができます。
チュートリアル で紹介したように、まずはグラフセットで作業する前にはユニバースを定義するのを忘れないようにして下さい。 このセクションでは、次のユニバースを用います。
>>> from graphillion import GraphSet
>>> universe = [(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (5, 6)]
>>> GraphSet.set_universe(universe)グラフセットを作成するもっとも簡単な方法です。 グラフのリストを指定して、グラフセットを作成します。
次の例では、１本の辺を持つグラフと、２本の辺を持つグラフの２つをまず作成しています。 グラフセットは、この２つのグラフから作成されています。
>>> graph1 = [(1, 4)]
>>> graph2 = [(1, 2), (2, 3)]
>>> gs = GraphSet([graph1, graph2])
>>> gs
GraphSet([[(1, 4)], [(1, 2), (2, 3)]])もし引数を与えないと空のリスト [] が与えられたことになり、空のグラフセットが作成されます。
>>> gs = GraphSet()
>>> gs
GraphSet([])辺の制約とは、含まれる辺・含まれない辺を指定するものです。 制約は、含まれる辺および取り除かれる辺のリストからなる辞書型オブジェクト（dict）で表現されます。 辞書に当てはまらない辺については考慮されません。 そのような辺はグラフセットに含まれるかもしれませんし、取り除かれるかもしれません。
次の例は、辺 (1,4) が含まれ、かつ辺 (1,2) および (2,3) が含まれないグラフセットが作成されます。
>>> edges1 = [(1, 4)]
>>> edges2 = [(1, 2), (2, 3)]
>>> GraphSet({'include': edges1, 'exclude': edges2})
GraphSet([[(1, 4)], [(1, 4), (2, 5)], [(1, 4), (3, 6)], ...空の辞書 {} は何の制約も指定されなかったことになり、その場合ユニバースに含まれるすべてのグラフを含むグラフセットが返されます（N をユニバースの辺の数だとすると、2^N のグラフが得られます）。
>>> gs = GraphSet({})
>>> len(gs)
128 # 2^7パスやツリーといったグラフのタイプを指定して、その条件を満たすすべてのグラフからなるグラフセットを作成することができます。 Graphillion は次のタイプをサポートします。
- 接続要素
- クリーク
- ツリー
- フォレスト
- サイクル
- パス
たとえば paths() メソッドは、２つの頂点間のすべてのパスを探索します。
>>> paths = GraphSet.paths(1, 6)
>>> paths
GraphSet([[(1, 2), (2, 3), (3, 6)], [(1, 2), (2, 5), (5, 6)], [(1, 4), (4, 5 ...各タイプの引数については、ライブラリ・リファレンスを参照して下さい。
より複雑なグラフタイプを指定するために、Graphillion は低レベルのgraphs() インタフェースを提供しています。
実際には、個々のメソッドはこの低レベルのインタフェースを内部的に呼び出しています。
以下の例は、paths(1,6) と同じことをしています。
>>> start = 1
>>> end = 6
>>> zero_or_two = xrange(0, 3, 2)
>>> degree_constraints = {start: 1, end: 1,
... 2: zero_or_two, 3: zero_or_two,
... 4: zero_or_two, 5: zero_or_two}
>>> GraphSet.graphs(vertex_groups=[[start, end]],
... degree_constraints=degree_constraints,
... no_loop=True)
GraphSet([[(1, 2), (2, 3), (3, 6)], [(1, 2), (2, 5), (5, 6)], [(1, 4), (4, 5 ...たとえば gs.paths(1, 6) のような、オブジェクト・メソッドと呼ばれるメソッド群において、グラフはグラフセットの中からのみ選ばれます。
詳しくはライブラリ・リファレンスを参照して下さい。
graphs() メソッドの内部 C++ コードは TdZdd としても配布されています。
Graphillion は、グラフセット内のグラフを操作するためのさまざまなメソッドを用意しています。 これらの操作は選択、変更、比較のいずれかに分類されます（ただし、そのうちいくつかは Python の集合演算機能によって実現されています）。 さらに Graphillion は、イテレータやシリアライゼーションの機能も提供します。 これらについて詳しくはライブラリ・リファレンスを参照して下さい。
グラフセットからグラフを選択するには、以下のメソッドが使えます（２つのグラフセットを対象とするメソッドもあります）。 これらの操作によって、新しいグラフが生成されることはありません。
| メソッド | 説明 |
|---|---|
gs.union(other(s)), gs (pipe) other
|
自身(gs)と他のすべてのグラフからなる、新しいグラフセットを返す |
gs.intersection(other(s)), gs & other
|
自身(gs)と他のすべてとの共通部分となるグラフからなる、新しいグラフセットを返す |
gs.difference(other(s)), gs - other
|
自身(gs)に含まれるグラフのうち、他のグラフに含まれないグラフからなる、新しいグラフセットを返す |
gs.symmetric_difference(other(s)), gs ^ other
|
自身(gs)か、他(other)のどちらか一方に含まれるグラフからなる、新しいグラフセットを返す |
gs.quotient(other), gs / other
|
「商」を表す新しいグラフセットを返す |
gs.remainder(other), gs % other
|
「剰余」を表す新しいグラフセットを返す |
gs.update(other(s)) |
他のすべてのグラフを追加し、自身(gs)を更新する |
gs.join(other) |
自身(gs)と他(other)の join を表す新しいグラフセットを返す |
gs.meet(other) |
自身(gs)と他(other)の meet を表す新しいグラフセットを返す |
gs.subgraphs(other) |
他(other)グラフの部分グラフからなる新しいグラフセットを返す |
gs.supergraphs(other) |
他(other)グラフのスーパーグラフからなる新しいグラフセットを返す |
gs.non_subgraphs(other) |
他(other)グラフの非部分グラフからなる新しいグラフセットを返す |
gs.non_supergraphs(other) |
他(other)グラフの非スーパーグラフからなる新しいグラフセットを返す |
gs.including(obj) |
obj（グラフセット、グラフ、辺、頂点）のスーパーグラフからなる、新しいグラフセットを返す |
gs.excluding(obj) |
obj（グラフセット、グラフ、辺、頂点）を含まない、新しいグラフセットを返す |
gs.included(obj) |
obj（グラフセット、グラフ、辺、頂点）に含まれるグラフの部分グラフからなる、新しいグラフセットを返す |
gs.larger(size) |
辺数が size より多いグラフからなる、新しいグラフセットを返す |
gs.smaller(size) |
辺数が size より少ないグラフからなる、新しいグラフセットを返す |
gs.len(size) |
辺数が size のグラフからなる、新しいグラフセットを返す |
gs.minimal() |
極小グラフからなる、新しいグラフセットを返す |
gs.maximal() |
極大グラフからなる、新しいグラフセットを返す |
グラフタイプを指定する作成メソッドは、選択メソッドとしても使用できます。
| メソッド | 説明 |
|---|---|
gs.graphs(constraints) |
指定された制約を満たすグラフからなる、グラフセットを返す |
gs.connected_components(vertices) |
接続された要素からなる、グラフセットを返す |
gs.cliques(k) |
頂点数がｋ個のクリークからなる、グラフセットを返す |
gs.trees(root, is_spanning) |
ツリーからなるグラフセットを返す |
gs.forests(roots, is_spanning) |
フォレスト（ツリーの集合）からなるグラフセットを返す |
gs.cycles(is_hamilton) |
サイクルからなるグラフセットを返す |
gs.paths(terminal1, terminal2, is_hamilton) |
パスからなるグラフセットを返す |
以下のメソッドは新しいグラフを作成します。
いくつかのメソッドは gs (self) に格納されたグラフを変更しますが、他のメソッドは新たに作成されたグラフからなるグラフセットを返します。
| メソッド | 説明 |
|---|---|
gs.add(graph_or_edge) |
与えられたグラフを gs に加える、もしくは gs 内のグラフに辺を接合する |
gs.remove(obj), gs.discard(obj)
|
gs からグラフ、辺、頂点を削除する |
gs.flip(edge) |
gs 内のすべてのグラフの辺について、状態を反転する |
gs.clear() |
gs からすべてのグラフを削除する |
| メソッド | 説明 |
|---|---|
~gs |
gs に格納されていないグラフからなる、新しいグラフセットを返す |
gs.complement() |
gs に格納されているグラフの補グラフからなる、新しいグラフセットを返す |
gs.blocking() |
すべてのヒッティングセットからなる、新しいグラフセットを返す |
gs.hitting() |
gs.blocking() と同じ |
以下のメソッドは、グラフセットの比較および評価を行います。
| メソッド | 説明 |
|---|---|
gs.isdisjoint(other) |
gs と other とのあいだに共通のグラフがなければ True を返す |
gs.issubset(other) |
gs のすべてのグラフが other に含まれているかどうかを評価する |
gs.issuperset(other) |
other のすべてのグラフが gs に含まれているかどうかを評価する |
obj in gs |
obj（グラフ、辺、頂点）が gs に含まれていれば True、でなければ False を返す |
len(gs), gs.len()
|
gs に含まれるグラフの数を返す |
gs.probability(probabilities) |
与えられた probabilities に対し，gs の実現確率を返す |
Graphillion はさまざまなイテレータを提供します。
rand_iter() は統計的な分析におけるランダムサンプリングに使えます。
min_iter() と max_iter() は最適化に使え、１個だけでなく上位ｋ個のグラフを得ることができます。
pop() と choice() はイテレータではありませんが、グラフセットを返します。
| メソッド | 説明 |
|---|---|
iter(gs) |
グラフに対してイテレーション（反復処理）を行う |
gs.rand_iter() |
一様乱数に従いグラフのイテレーションを行う |
gs.min_iter() |
重みの昇順でグラフのイテレーションを行う |
gs.max_iter() |
重みの降順でグラフのイテレーションを行う |
gs.pop() |
gs から任意のグラフを取り除き、残りを返す |
gs.choice() |
gs から任意のグラフを返す |
Graphillion はグラフセットをファイルに書き出したり、ファイルから読み込んだりすることができます。 これらのメソッドは、ユニバースの pickle 化（データ構造の保存・復元）と同時に行われます。 詳しくはライブラリ・リファレンスを参照して下さい。
| メソッド | 説明 |
|---|---|
gs.dump(fp) |
gs をシリアライズしファイル fp に書き出す |
GraphSet.load(fp) |
シリアライズされたファイル fp を読み込み、新しいグラフセットを返す |
Graphillion は Python の持つ集合演算メソッドをサポートします。 これらのメソッドはグラフを集合の要素として扱い、グラフの構造については意識しません。
-
gs.union(other),gs | other, -
gs.intersection(other),gs & other, -
gs.difference(other),gs - other, -
gs.symmetric_difference(other),gs ^ other, -
gs.update(other),gs |= other, -
gs.add(graph), -
gs.remove(graph),gs.discard(graph), -
gs.clear(), -
gs.isdisjoint(gs), -
gs.issubset(gs), -
gs.issuperset(gs), -
graph in gs, -
len(gs), -
gs.pop(), and -
gs.copy().
Graphillion は，OpenMP (多くの環境で共有メモリ型並列計算を行うためのAPI) を用いて並列計算を実行します．利用したい CPU コア数を，環境変数 OMP_NUM_THREADS として設定してください．たとえば，4コアを利用するのであれば下記のようになります．
$ OMP_NUM_THREADS=4 python your_graphillion_script.py現在 (v1.0) 並列化の対象となっているメソッドは下記になります．
GraphSet.graphs(constraints)GraphSet.connected_components(vertices)GraphSet.cliques(k)GraphSet.trees(root, is_spanning)GraphSet.forests(roots, is_spanning)GraphSet.cycles(is_hamilton)GraphSet.paths(terminal1, terminal2, is_hamilton)
Graphillion は、NetworkX のような既存のグラフツールと透過的に併用することができます。
Graphillion では、networkx.Graph など任意のオブジェクトはグラフとして認識されます。
エッジリストから新しいグラフオブジェクトを生成するには２つのメソッドを定義します。 １つはエッジリストをグラフに変換するために使われ、もう１つはその逆です。 NetworkX の例を見てみましょう。
>>> import networkx as nx
>>> GraphSet.converters['to_graph'] = nx.Graph
>>> GraphSet.converters['to_edges'] = nx.Graph.edgesNetworkX のグラフオブジェクトは、このように Graphillion に引き渡すことができます。
>>> g = nx.Graph(...) # NetworkX のグラフを生成する
>>> GraphSet.set_universe(g)同様に、Graphillion は NetworkX のグラフオブジェクトを受け取ることもできます。
>>> gs.choice() # NeworkX のグラフオブジェクトを返す
<networkx.classes.graph.Graph object at 0x100456d10>グラフ可視化のために、NetworkX はいくつかのノード配置アルゴリズムと共に Matplotlib プロットパッケージへのインタフェースを提供しています。
>>> nx.draw(gs.choice())
>>> import matplotlib.pyplot as plt
>>> plt.show() # ポップアップウィンドウを表示するpydoc を使えば、ターミナルウィンドウでもライブラリ・リファレンスが参照できます。
$ pydoc graphillion.GraphSetHTML で参照するには次のようにします。
$ pydoc -w graphillion.GraphSetこちらを参照ください。
- より効率的な内部データ変換
- 最適化のためのより効率的な検索アルゴリズム
- 最適化における非線形目的関数
- ヒッティングセットやクリークのためのよい効率的なアルゴリズム
- Python の乱数と内部乱数シードとの同期
- パフォーマンスに関するドキュメント化
- マルチスレッディング
- ガベージコレクション
- メーリングリスト
- コーディングルール
- 開発者向けドキュメント
-
Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato: "Graphillion: Software Library Designed for Very Large Sets of Labeled Graphs," International Journal on Software Tools for Technology Transfer, Springer, vol.18, issue 1, pp.57-66, February 2016. (pdf)
-
Yuma Inoue and Shin-ichi Minato, "Acceleration of ZDD Construction for Subgraph Enumeration via Path-width Optimization," TCS Technical Reports, TCS-TR-A-16-80, October 2016. (pdf)
-
Hana Ito, Yuma Inoue, and Shin-ichi Minato, "Experiments and Considerations on Variable Ordering in Top-Down Construction of ZDDs," Forum on Information Technology, vol.14, no.1, pp.115-116, September 2015. (pdf, in Japanese)
-
ERATO湊離散構造処理系プロジェクト 著, 湊真一 編, “超高速グラフ列挙アルゴリズム –<フカシギの数え方>が拓く，組合せ問題の新アプローチ−,” 森北出版, 2015年4月. (amazon)
-
川原純, "graphillion – 莫大な数の部分グラフを扱う Python ライブラリ," Pythonセミナー, 2014年12月. (pdf, in Japanese)
-
Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato, "Frontier-based Search for Enumerating All Constrained Subgraphs with Compressed Representation," Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-14-76, September 2014. (pdf)
-
井上武, "Graphillion updates," ERATO 湊離散構造処理プロジェクト セミナー, 2014年2月. (pdf)
-
Hiroaki Iwashita and Shin-ichi Minato, "Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications," TCS Technical Reports, TCS-TR-A-13-69, December 2013. (pdf)
-
Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato, "Graphillion: ZDD-based Software Library for Very Large Sets of Graphs," Proc. of the 18th Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI), Poster Presentation, October 2013. (html)
-
Takeru Inoue, "Graphillion: Python module for very large sets of graphs," PyCon APAC, September 2013.
-
井上武, "[招待講演] Graphillion：巨大なグラフ集合を扱うソフトウェアライブラリ," 信学技報, vol. 113, no. 140, IN2013-43, pp. 43-47, 2013年7月. (pdf)
-
Takahisa Toda, "Hypergraph Transversal Computation with Binary Decision Diagrams," Proc. of 12th International Symposium on Experimental Algorithms (SEA), pp.91-102, June 2013. (doi)
-
Daisuke Yoshino and Eiji Hato, "Fast Enumeration Method of Travel Route of DRT Using Zero-suppressed Binary Decision Diagram," Journal of Japan Society of Civil Engineers, vol.72, no.5, pp.1229-1239, December 2016. (doi)
-
Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka, "Solving the Longest Oneway-Ticket Problem and Enumerating Letter Graphs by Augmenting the Two Representative Approaches with ZDDs," Proc. of the Computational Intelligence in Information Systems Conference (CIIS), pp.294-305, November 2016. (doi)
-
Yuji Takenobu, Norihito Yasuda, Shunsuke Kawano, Yasuhiro Hayashi, and Shin-ichi Minato, "Evaluation of Annual Energy Loss Reduction Based on Reconfiguration Scheduling," IEEE Transactions on Smart Grid, September 2016. (doi)
-
Masashi Hashimoto, Tomihiro Utsumi, and Takeru Inoue, "[Invited Talk] Availability Analyses for Photonic Network by Minimal Blocking Set using ZDD based Graphillion," Technical Report of IEICE, vol.116, no.205, PN2016-22, pp.45-51, September 2016. (html, in Japanese)
-
Y. Takenobu, S. Kawano, Y. Hayashi, N. Yasuda and S. Minato, "Maximizing hosting capacity of distributed generation by network reconfiguration in distribution system," Proc. of Power Systems Computation Conference (PSCC), pp.1-7, June 2016. (doi)
-
Subaru Fukuda and Naoshi Sakamoto, "A Failure Estimation System for Networks Applying Graphillion," Technical Report of IEICE, vol.115, no.483, NS2015-212, pp.255-260, March 2016. (html, in Japanese)
-
Arthur Choi, Nazgol Tavabi, and Adnan Darwiche, "Structured Features in Naive Bayes Classification," AAAI, pp.3233-3240, February 2016. (pdf)
-
Ikki Fujiwara, Satoshi Fujita, Koji Nakano, Takeru Inoue, and Michihiro Koibuchi, "Let's Solve the Order/Degree Problem to Make the Lowest-latency Interconnections," Technical Report of IEICE, vol.115, no.174, CPSY2015-38, pp.223-228, August 2015. (html, in Japanese)
-
Atsushi Takizawa, Yushi Miyata, and Naoki Katoh, "Enumeration of Floor Plans Based on a Zero-Suppressed Binary Decision Diagram," International Journal of Architectural Computing, vol.13, no.1, pp.25-44, March 2015. (pdf)
-
Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi, and Shin-ichi Minato, "Enumerating Eulerian Trails via Hamiltonian Path Enumeration," International Workshop on Algorithms and Computation (WALCOM), pp.161-174, February 2015. (doi)
-
Takeru Inoue, Norihito Yasuda, Shunsuke Kawano, Yuji Takenobu, Shin-ichi Minato, and Yasuhiro Hayashi, "Distribution Network Verification for Secure Restoration by Enumerating All Critical Failures," IEEE Transactions on Smart Grid, October 2014. (doi)
-
Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi, "Distribution Loss Minimization with Guaranteed Error Bound," IEEE Transactions on Smart Grid, vol.5, issue.1, pp.102-111, January 2014. (doi)
-
Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato, "Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs," Algorithms 2012, 5(2), pp.176-213, 2012. (doi)
- Michihiro Koibuchi, Ikki Fujiwara, Fabien Chaix, and Henri Casanova, "Towards Ideal Hop Counts in Interconnection Networks with Arbitrary Size," Proc. of 4th International Symposium on Computing and Networking (CANDAR), pp.188-194, November 2016. (doi)
- Shin-ichi Minato, "Power of Enumeration -- BDD/ZDD-Based Techniques for Discrete Structure Manipulation," IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), pp.143-143, July 2016. (doi)
- Masahiro Kawahara, Takehide Soh, Mutsunori Banbara, and Naoyuki Tamura, "Constraint Models for SAT-based Subgraph Search," Proc. of the 30th Annual Conference of the Japanese Society for Artificial Intelligence, 1D4-OS-02a-4, June 2016. (pdf, in Japanese)
- Shin-ichi Minato, "Counting by ZDD," Encyclopedia of Algorithms, Springer, pp.454-458, April 2016. (doi)
- Yasuhiro Takei, Masanori Hariyama, and Michitaka Kameyama, "Evaluation of an FPGA-Based Shortest-Path-Search Accelerator," Proc. of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), pp.613-617, 2015. (pdf)
- Tsutomu Sasao and Jon T. Butler, "Applications of Zero-Suppressed Decision Diagrams," Morgan & Claypool Publishers, November 2014. (doi)