Home
最新のドキュメントは英語版を参照ください．
Graphillion の本が2015年4月に出版されます．
Graphillion は、グラフセットもしくはグラフ集合に対する検索、最適化および列挙のための Python パッケージです。
- 超大規模グラフを扱うための軽量なデータ構造
- 大規模で複雑なグラフ集合に対する検索、最適化、列挙
- 電力網の評価（DNET）、鉄道網分析（Ekillion）などでの使用実績
- C/C++ により Python を拡張する効率的な実装
- 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, October 2014. (pdf)
Graphillion は開発途上です。 利用していただき、多くの人々に利益をもたらす改良は大歓迎です。
では、Graphillion のインストールとチュートリアルに進みましょう。 Graphllion のパワーと実用性をぜひ体験して下さい。
桁数の大きな数値を効率的に扱うため、Graphillion には 64 ビット環境が必要です。
Graphillion のビルドには、Python バージョン 2.6 以上が必要です (Python.h を使うため Python 開発環境もインストールしてください)。 http://www.python.org/
Graphillion のビルドには、gcc バージョン 4.2 以上が必要です。 http://gcc.gnu.org/
Mac OS X で Graphillion を使うには、Apple が配布している Xcode の Clang をお使い下さい。 でないと、メモリアロケーションエラーが発生する可能性があります。
NetworkX および Matplotlib はグラフの作成および描画のための Python モジュールです。 これらのパッケージは Graphillion には必要ありませんが、チュートリアルで使用します。 次のコマンドでインストールできます。
$ sudo easy_install networkx
$ sudo easy_install matplotlibMac OS X で matplotlib のインストールに失敗する場合は、MacPorts を使用し、sudo port install py-matplotlib を実行して下さい。
Ubuntu では APT を使用し、sudo apt-get install python-matplotlib を実行してください。
次のようにタイプするだけです。
$ sudo easy_install graphillionお使いのＯＳおよび Python に最適なバージョンがインストールされます。
FreeBSD をお使いの場合は、FreeBSD Ports によってもインストールが可能です。
- Anaconda のダウンロードとインストールをおこなう http://www.continuum.io/downloads
- %PATH% 変数に次のパスを追加する (Anaconda のパスは環境に合わせてください)
set PATH=%PATH%;C:\Anaconda;C:\Anaconda\Scripts;C:\Anaconda\DLLs;C:\Anaconda\MinGW\bin;C:\Anaconda\MinGW\x86_64-w64-mingw32\lib
- ソースファイル（tar.gz または zip ファイル）を https://github.com/takemaru/graphillion からダウンロードする (Pypi のソースファイルは使わないでください)
- IPython を実行する
- ソースコードのディレクトリ（setup.py があるディレクトリ）に移動する
-
run setup.py buildを実行してビルドする - （任意）
run setup.py test -qでテストを行う -
run setup.py installを実行してインストールする
ソースコードのアーカイブファイル（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 を参照して下さい。
もしまだ おねえさんといっしょ！ みんなで数えてみよう！ 動画をご覧になっていない場合は、チュートリアルを始める前にぜひご覧下さい。 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():
... tl.how_many_turns(path)
... break # break しないと、複数のパスが昇順で取り出される
...
5パス列挙の応用例として、ＪＲの大都市近郊区間におけるすべての経路を列挙する Ekillion もぜひご覧下さい。
Graphillion は格子グラフ以外のグラフにも使えますし、単純なパス以外の部分グラフも扱うことができます。 次の例として、図のような配電ネットワーク（電力供給網）を考えてみましょう。 このネットワークでは、頂点を家庭、辺をスイッチ付きの電力線だとします。 電力は四隅の発電所から供給されます。
>>> universe = tl.grid(8, 8, 0.37) # 8x8 の格子から 37 % の辺が取り除かれる
>>> GraphSet.set_universe(universe)
>>> tl.draw(universe)
電力フローは、各電力線のスイッチの設定によって決定されます。 もしスイッチがオンであれば（グラフに辺があれば）、電力が送られます。 スイッチがオフであれば（グラフに辺がなければ）電力は送られません。 電力はすべての家庭に供給されなければなりませんが、ネットワークがショート（短絡）しないよう、ループを作ってはいけません。 つまり電力フローは、発電所を根（起点）とするツリーの集合として森になります。 そして、すべての森を次のように見つけることができます。
>>> generators = [1, 9, 73, 81]
>>> 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) のような、オブジェクト・メソッドと呼ばれるメソッド群において、グラフはグラフセットの中からのみ選ばれます。
詳しくはライブラリ・リファレンスを参照して下さい。
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.update(other(s)) |
他のすべてのグラフを追加し、自身(gs)を更新する |
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.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 は、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, October 2014. (pdf)
-
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. (pdf)
-
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)
-
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. (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, "Graphillion: Python module for very large sets of graphs," PyCon APAC, September 2013.
-
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)
