凸多角形の flip graph (2)
ちょこちょこと、いろいろ作業したので、凸多角形の flip graph についての、つづきの記事です。ソースコードは、まだ、ちょっと、色々、機能不足なので、あとで、展開したいと思っています。実際、２・３年前に実装したコードで、なんか途中で飽きちゃったので放置していたのですが、グラフ描画に俄然興味が出てきたので、再開しました。いろいろ修正したいコードがあるみたいです。GitHubとか使う機会が増えてきたので、そっちで管理することを考えてます。GitHubとかって、どうやって使うんですかね？よろしくお願いします。
- Cytoscape で分析
[
:W333]
cytoscape でググると、NetworkAnalyzer っていうプラグインが見つかります。最近のバージョンではデフォルトで組み込まれてるみたいなのですけど（あとで、最新のバージョンに移行しました）、私の環境では、２・３年前のバージョン(2.7.0)なのでインストールが必要でした。で、そのプラグインをインストールして、n = 11 の情報を出力してみました。横みたいな感じです。n = 12 は、メモリ制限1.5G とかにしても読めません。create view 実行しても、なんか、ダメだー。 バージョンを 3.0.2 にしてみたら、描けたー。以降は、3.0.2 で、スクリーンショットとか画像生成してます。
それから、それぞれの flip graph のトポロジ情報をこちらに置いてみました。gml 形式のファイルです。なんか、まだ、いろいろ、おしゃれ感が無いので、そのうち置き換えたいと思います。ともかく cytoscape で import できますよ。あと、ラベルとか属性をきちんと付与できたらいいのですが、できてません。ダメだー。
- nested network を使った各頂点への三角形分割追描画
[
:W333]あと、cytoscape で nested network をちくちく追加して、描画してみた際のスクリーンショットです。これに関しても、cytoscape が出力する cys 形式のファイルを上記のサイトに置きました。たぶん、cytoscape でファイルを開けば、横に示したような画面が表示されると思います。ご参考です。
ファイル (82KB)
これ、14頂点しか無いけど、結構めんどかったです。基本的な手順は、各三角形分割のグラフを1つずつ import して、それぞれの view に対してcircular レイアウトして、vismapper で nested network style を整えます。それから、flip graph を import して、すべての頂点番号が確認できるようレイアウトして、各頂点を右クリックして nested network→add nested network で、頂点番号と対応する番号が付与された三角形分割のグラフを対応づけます。最後に、vismapper で default style を整えつつ、レイアウトを調整します。試行錯誤で1時間くらいかかってしまった。cytoscape の使い方が良く分かっていないからかもしれませんが。あと、7角形もちょっと描こうと思っています。それから、nested network を表現できるグラフ形式など調べてみたいと思います。また、できれば、指定した２つの頂点間の任意の最短路をハイライトしてみたいので、そこら辺を調べてみたいです。
[
:W333]（追記）７角形の flip graph with nested network も描いてみました。これまでは、cytoscape 組み込みの organic っていうレイアウトで描画していましたが、ちょっと辺どうしの交差が多くて，良く分からなかったので、いろいろ試してみて、hierarchic で描画して、辺ができるだけ見やすくなる様に、マウスで頂点をぐりぐり移動してみました。でも、nested network は、７角形までで良いや、って思います。だって、直径を与えるような２頂点がなかなか見つからないんですよね。互いに辺素だから良いだろって感覚ではダメみたいです。これ、対角線増えると、直径を与えるような頂点対を全部出すのって、とても大変そうですね。やっぱり、ちょっと、直径を与える２つの三角形分割を表示してみたいですよね。
(追記) ちょっと、とても気になったので、正解を出してもらうことにしました。igraph で下に示した様に igraph_diameter 関数を実行すると、直径を与えるパスを出力してくれます。実行すると、(1 → 0 → 5 → 9 → 10 → 11) なんですって。ふむむ。わからん。
#include <igraph/igraph.h> #include <stdio.h> int main(int argc, char* argv[]) { igraph_t g; FILE* fp = fopen("07.gml", "r"); igraph_read_graph_gml(&g, fp); igraph_integer_t diameter; igraph_vector_t path; igraph_vector_init(&path, 0); igraph_diameter(&g, &diameter, NULL, NULL, &path, IGRAPH_UNDIRECTED, 0); printf("diameter: %d\n" (int) diameter); for (long int i = 0; i < igraph_vector_size(&path); i++) { printf("%d, ", (int) VECTOR(path)[i]); } printf("\n"); fclose(fp); igraph_destroy(&g); igraph_vector_destroy(&path); return 0; }
(メモ) igraph_diameter 関数の引数について。1. 対象のグラフ 2. 直径が格納される 3.始点指定無し 4. 終点指定無し 5. パスが格納される; 初期化した igraph_vector_t を指定しろって 6. 無向 7. 連結なので 0。非連結成分どうしの距離をどう測るかが選べるみたい。あと、計算量はO(|V|x|E|) なんですって。アルゴリズムの引用もどっかに記述してあると思うのですが、どこなんですかね。あとで。
[
:W333]
あと、NetworkAnalizer で確認して見ると、グラフ中の最短路の総数が1722で、そのうち 150 くらいが距離5みたいです。距離1の最短路の個数と同じくらいです。きれいな分布になってますね。でも、分布みたところで、っていう気もします。
- 何角形まで直径求められるか ＆ メモメモ
できれば、16角形までの直径なんかが調べられると良いなって思うので、備忘録的な表をメモってみました。頂点の個数は、n + 2 の Catalan 数で求められる値です。辺の個数は、頂点の個数に n - 3 を掛けて 2 で割った値です。flip graph の直径は、igraph の igraph_diameter 関数を使いました。'-' は、まだ求められてません。
| n-角形 | 頂点数 | 辺数 | 直径 | . | n-角形 | 頂点数 | 辺数 | 直径 |
|---|---|---|---|---|---|---|---|---|
| 4 | 2 | 1 | 1 | . | 11 | 4862 | 19448 | 12 |
| 5 | 5 | 5 | 2 | . | 12 | 16796 | 75582 | 15 |
| 6 | 14 | 27 | 4 | . | 13 | 58786 | 293930 | 16 |
| 7 | 42 | 84 | 5 | . | 14 | 208012 | 1144066 | 18 |
| 8 | 132 | 330 | 7 | . | 15 | 742900 | 4457400 | - |
| 9 | 429 | 1287 | 9 | . | 16 | 2674440 | 17383860 | - |
| 10 | 1430 | 5005 | 11 | . | 17 | 9694845 | 67863915 | - |
14角形の三角形分割の列挙は、２秒くらいで回答してくれました*1。やっぱり flip graph の生成が遅いです。二日経っても、まだやってます。７角形の flip graph の隣接頂点のラベルなんかを見ると結構離れているので、やっぱり隣接頂点集合を求める手続きをきちんと記述しないといけないんじゃないかと思います。あと、igraph のエッジ追加で１つずつ追加してるのも原因なのかも。ふむむ。あと、並列処理できるように、できるだけコンフリクトしない三角形分割の分類みたいなのも考えてみたいです。良く分かってませんが。ちょっと前に、図書館から 構造化並列プログラミング―効率良い計算を行うためのパターン を借りてみたけど、目次くらいしか見てないです。ダメだー。
（追記）14角形の flip graph が、二日と11時間くらいかかって、出力されました。良かったです。途中、いろいろと計算したり、グラフ描画したり、port update; port upgrade outdated で負荷をかけながらも、よくぞ、無事帰還なされた。とりあえず、15角形に向けて、実装の見直しをしましょう。
