凸多角形の flip graph (3)

15頂点以上の凸多角形の flip graph を生成したり特徴を観察するために、アルゴリズムを整えて実装を見直してみました。結構、フルスクラッチ系で、だいぶ書き直しました。ちょっとだけ速くなっていて、15角形の flip graph は、2日と12時間くらいで生成できました。でも、今のままだと、16角形は難しいですね。

あと、本質的な改善点は、flip graph の頂点列挙と隣接関係生成には無いことが判りました。少なくとも、16角形の flip graph を出力する上で。15角形の場合、頂点集合 (std::vector) と辺集合 (std::vector >) の生成は、数秒で終わります。で、処理の大半は、igraph_add_edges 関数みたいです。これは、もう、ちょっと、他のグラフライブラリを当たってみたくなります。下に示したライブラリが c++ としては、有名みたいですね。そのうち。

• boost graph library
• lemon graph library

ちょっと、直径とかおいといて、どれくらいの時間で、グラフ構造を作ってくれるのかみてみたい気もします。lemon graph library は、知りませんでした。楽しげですね。でも、そろそろ、flip graph の生成については、どうでも良くなってきました。なので、現状の igraph 使ってる版のソースコードを GitHub で公開して、区切りたいと思います*1。

https://github.com/s-teramo/fgg

コメントの追記や、単体テストのコードの作成など、細かい修正をしないといけないので、コミットは続けますが、ソースコードは、それほど手を加えないようにします。不具合等の問題があれば、お知らせ下さい。それでは、さようならー。

*1:超絶きたないコードだし、需要があるのか判りませんが。また、数年後、何かを切っ掛けに、触れたくなるかもしれないので。