Canonical Labelling by Nauty

はじめに

　先のページで、論文「Learning Convolutional Neural Networks for Graphs」の紹介を行った。その中で、Canonical Labellingを行う際に、Nautyというツール（ライブラリ）を用いていた。ここでは、Nautyの提供するC言語インタフェースを用いて、Canonical Labellingを行う手順を示す。

Nautyのインストール

　ここからソースをダウンロードする。コンパイル手順はソースに含まれるREADMEに書いてある。 上の処理が終わると、ディレクトリnauty26r7の直下に実行ファイル、オブジェクトファイル、ソースファイル、ユーザガイドが混在する状態になる。上の例では、--prefixを指定してあるが、ディレクトリに含まれるmakefileにはinstall命令が記述されていない（後で気づいた）。make installできないので、実行ファイル等を手で適当な場所にコピーする必要がある。ユーザガイドはオンラインでも見ることができる。

開発環境

1. Xcode Version 8.2.1 (C++ Language Dialect: C++14)
2. boost library
3. cpplinq

サンプル1

　最初に、ユーザガイドのp4の冒頭にある下図を取り上げる。

図1

図1の上段2つのグラフは同型（isomorphic）であるが、頂点の隣接関係は異なっている。これらを2つをcanonizeすると、頂点の隣接関係の等しい2つのグラフを得ることができる（図1の下段）。2つの同型のグラフは、canonical labellingにより、頂点の隣接関係の等しいグラフになる。言い換えれば、canonical labellingを用いれば、2つのグラフが同型であるか否かを判定することができるのである。この判定を、NautyのC言語インタフェースを用いて実装したものを以下に示す。 上の出力を検討してみる。最初に、図1左側のグラフについて（図2）。

図2

108行目でdensenautyを呼び出した後、配列labに以下の値が設定される。 これは以下を表現している。 すなわち、図2の上段の元のグラフの頂点番号3は0に、6は1に置き換えることを意味する（他の頂点についても同様）。配列relabelling1は分かり易いように表現方法を変えただけの値である。 これは を意味する。すなわち、元グラフの頂点番号0を6に、1を5に置き換える（他の頂点も同様）。図1右側の2つのグラフについても同じように解釈すれば良い。結局、図1下段の2つのグラフが得られたことになる（図3）。

図3

これら2つのグラフを見ると、頂点{5,1,4,0}の位置は異なるが、全頂点の隣接関係は全く同じである。これを確認しているのが148行目である。

サンプル2

　次にユーザガイドのp5冒頭にある図を考える（図4）。

図4

グラフの形はサンプル1と同じであるが、partitioning(coloring）が導入されている。頂点が色分けされている場合、同じ色に属する頂点についてcanonical labellingが実行される（サンプル1は全ての頂点が同じ色を持つと解釈される）。実装例は以下の通り。 9行目で色分けを行うことをNautyに伝えている。実際に色分けを行なっているのは、31,32行目と58,59行目である。Nautyでは色分けを2つの配列lab,ptnを用いて表現する。図4左側の2つのグラフの色分けは以下の2つの配列で記述される。 labには頂点番号が任意の順番で格納される。この格納順にptnで色の分離位置を表現する。0の場合そこが色の境界である。0以外の値のとき同じ色である。すなわち、{0,2}と{1,3,4,5,6,7}に色分けされることになる。図4では前者は黒、後者は白で描かれている。図4右側の2つのグラフの色分け（58,59行目）も同様である。densenautyの呼び出し（39,66行目）の後のlabにはcanonize後のラベルが格納され、この解釈方法はサンプル1と同じである。canonize後に得るグラフは図4の下段である。これら2つのグラフの頂点の隣接関係は異なる。これを確認しているのが80行目である。最後に、headerファイルとmain関数を示す。

論文「Learning Convolutional Neural Networks for Graphs」への適用

　論文「Learning Convolutional Neural Networks for Graphs」では、最初に、betweenness centralityやWLアルゴリズムにより頂点のラベル付けを行なった。そして、同じラベルを持つ頂点が存在する場合、この縮退を解くためにNautyを用いている。同じラベル値を持つ頂点を同じ色を持つ頂点と解釈し、Nautyを適用すれば良いだろう。　

How to build pcl-1.7.1 on iMac (OS X ver. 10.9.4)

in Japanese

At first I tried to build libpcl by using the macports. After installing the libraries on which libpcl depends, I failed to build it. It seems difficult for me to install libpcl through the macports. So I decided to build it from the source code.

After downloading the source code from here, I decompressed it. The dependent libraries are already installed by the macports. Unfortunately an error caused the building to stop. The error is due to the definitions of the non-member template functions described in pcl-pcl-1.7.1/io/include/pcl/io/ply/ply_parser.h. It may be clang's bug. I fixed it in accordance with this site. The fixed code is as follows:
1. delete definitions of two functions named at: 2. delete definitions of funcions named at once more: 3. move the deleted four definitions to a different area as: Again make. I got an error as: Seeing this site, I fixed it as Again make. I had a different error: I gave up the compilation of all modules libpcl has. Since the modules that I am unable to compile are just ones relate to linemode, I excluded them from the building targets. To this aim, I commented out lines from 114 to 121 in pcl-pcl-1.7.1/tools/CMakeLists.txt. Again, make. Mission accomplished!
The sample code worked well.

gnuplotの図を保存する。

覚え書き

以下をdecompose_curve.pltとして保存し、 コマンドライン上で を実行すると、指定したディレクトリにこんなpng画像が保存される。

同様に以下をdecompose_surface.pltとして保存し、 以下を実行すると、 こんな画像が保存される。

曲面をグリッドにするには、こんなフォーマットでファイルを作る。 つまり、

1. データを、空行を使って、ブロックに分ける。
2. 各ブロックはX座標あるいはY座標が同じである。

このフォマットを使ったファイル bspline_surface、bezier_surface_0_0、bezier_surface_0_1があるとして、以下のpltファイルを実行すると こうなる。

How to install pcl-1.7.1 into iMac (OS X ver. 10.9.4)

in English

最初、macportsを使ってlibpclのインストールを試みた。 依存ファイルのインストールのあと、libpclのコンパイルに失敗。 いろいろ調べてmacportsを諦める。

ここからソースをダウンロードして、解凍。 依存ライブラリは既にmacportsでインストールされている。 途中でエラー。 pcl-pcl-1.7.1/io/include/pcl/io/ply/ply_parser.hに記述してあるtemplateの定義が原因。clangのバグ。 ここを見てソースを修正する。修正後のソースは以下の通り。
at関数の定義を2つ削除。 さらに、at関数の定義を2つ削除。 削除した4つの定義を移動する。 あらためて 今度は、こんなエラー。 ここを見て以下のように修正する。 再度、 今度はこんなエラー すべてのmoduleをコンパイルすることを諦める。コンパイルできないmoduleは、linemod関係のものだけなので、これらをコンパイル対象から外す。pcl-pcl-1.7.1/tools/CMakeLists.txtの114行目から121行目までをコメントアウト。 あらためて、 できた。ここにあるサンプルは動作した。

Xcodeでboost/numeric/bindings/lapack/syevd.hppを使うには。

覚え書き
Xcode Version 5.1.1 においてboost/numeric/bindings/lapack/syevd.hpp をincludeしたときは、Other Linker Flagsに -framework accelerateを追加する必要がある。(macportでインストールしたlapackやblasをリンクしてみたがコンパイルできなかった。)

opencv-2.4.6.1をApple LLVM version 5.0でコンパイルする

ソースをダウンロードして解凍する。 以下を実行。 こんなエラーが出た。 ここの指摘に従って、cmakeのオプションに-DBUILD_PERF_TESTS=OFFを追加。 再度、make。今度はこんなエラーが出た。 opencv-2.4.6.1/modules/legacy/src/dpstereo.cppにあるマクロ が原因である。マクロをinline関数に書き換える。 再度make。今度は上手いく。 完了。

Mac OS X 10.9 Mavericksでport selfupdate

Mac OS X 10.9 Mavericksにしたあと を実行すると、こんなエラーが出た。 以下を実行。 再度 を実行、今度は無事、MacPorts 2.2.1にアップデートできた。 続けて、 を実行。しばらくするとこれが出た。 サポートしてないとのことなのでこれを実行（llvm-3.0に依存したportsを全てアンインストール）。 再度、 を実行。最後にこれを実行。 完了。

How to build Boost-1.53.0 by Apple LLVM version 4.2 comiler

in Japanese

First install the Command Line Tools of Xcode-4.6.1 and check the version. Download and decompress the boost-1.53.0. Run the following commands: When using it on the Xcode, we need to add a variable DYLD_LIBRARY to "Product→Edit Scheme→Arguments→Environment Variables" and set the path to dylib to the variable.

How to build Opencv 2.4.5 by Apple LLVM compiler 4.2

in Japanese

Download and decompress the source code. Run the following commands: That's all.

opencv 2.4.5をApple LLVM compiler 4.2でコンパイルする

in English

ソースをダウンロードして解凍する。 以下を実行。 完了。

boost 1.53.0をApple LLVM compiler 4.2でコンパイルする

in English

最初にXcode-4.6.1のCommand Line Toolsをインストールする。そして確認。 boost_1_53_0をダウンロードして解凍。 解凍したディレクトリに入って以下を実行。 Xcodeで動かす時は、Product→Edit Scheme→Arguments→Environment Variablesに変数DYLD_LIBRARY_PATHを追加し、dylibへのパスを設定する。

macportsメンテナンスルーチン

覚え書き
デフォルトのgccであることを最初に確認しておく。 また、python24に依存したportsを全てアンインストールするときは 特定のパッケージを無視するときは 参考サイト

[追記]2017/02/25
OSをmacOS Sierra v10.12にアップグレードしたあとこのサイトの項目「Migration procedure」の1と2だけを実行した。macports.confは触っていない。

Installation of Open Dynamics Engine to iMac

Introduction 

Recently I installed the Open Dynamics Engine(ODE) to my iMac and compiled its sample program on the Xcode. In this page, I describe my procedure to do so.

Development Environment 

1. iMac
2. Mac OS X 10.8.1
3. Processor：3.06GHz Intel Core 2 Duo
4. Memory：4GB
5. Xcode4.4.1

Installation 

It's simple because the Macports supports the ODE. The ODE consists of two libraries:

1. the library to calculate the rigid body dynamics, which is called "ode"
2. the library to draw the dynamics by use of the OpenGL, which is called "drawstuff"

The Macports installs only "ode." As I also want to use "drawstuff", I downloaded the source code of ODE from here. Here are its installation instructions. At this point, the script warned that there is no libtoolize. I enabled statements from the 36th line to the 38th one in autogen.sh. The comments in the script tell us that the libtoolize corresponds to glibtoolize in Mac. I tried again. In turn, it's successful. The procedure compiles not only the "drawstuff" but also the "ode." I don't need the "ode" because it's already installed by the Macports. I manually copied the "drawstuff" as follows: The preparation to compile a sample program is completed.

Interface of ODE 

Here is the following statement: Though the library itself is written in C++, it appears that the library is more in favor of being used through the C interfaces. But, my favorite language is C++...

Sample Program 

Here is a beginner course of the ODE in Japanses. Using C++, I rewrote the sample source code "サンプルプログラム６マルチ" in the 6th chapter of the course. This page gives us an explanation about the C interfaces, but I could not find the corresponding page to the C++ ones. Fortunately the "ode" library provides us with the header file "odecpp.h." It helps me rewrite the sample in the C++. My source code is as follows: A path in the 10th line is the path to a directory included in the ODE source code.

Compile Options 

Header Search Path:

Path	Purpose
/opt/local/include/	to include ode header
/usr/local/include/	to include drawstuff header

Library Search Path:

Path	Purpose
/opt/local/lib	to find "ode" library
/usr/local/lib	to find the "drawstuff" library

Other Linker Flags:

-lode -ldrawstuff -framework OpenGL -framework GLUT

Apple LLVM compiler 4.0 - Language:

C++ Language Dialect	C++11 [-std=c++11]
C++ Standard Library	libc++ (LLVM C++ standard library with C++11 support)

Run 

Red balls fall to the ground, and bounce. The variable contact.surface.bounce in the 55th line corresponds to the reflection coefficient. When it equals to 1, the completely-elastic collision is realized. The range is [0, 1].

Open Dynamics EngineのMacへのインストール

はじめに 

物理エンジンのオープンソースOpen Dynamics Engine(ODE)をXcodeで動かしてみました。

開発環境 

1. iMac
2. Mac OS X 10.8.1
3. Processor：3.06GHz Intel Core 2 Duo
4. Memory：4GB
5. Xcode4.4.1

インストール 

macportsにあるので簡単です。 ODEは２つのライブラリから構成されています。

1. 剛体の力学を計算するライブラリ(ode)
2. 描画するライブラリ(drawstuff)

上記のportでインストールされるのはodeのみです。drawstuffもインストールしたいのでここからソースを取ってきます。インストール方法はここにあります。 ここで、libtoolizeがない！というエラーが出ました。 autogen.shの36行目から38行目までのコメントアウトを外します。Macではlibtoolizeはglibtoolizeに相当すると書いてあります。 再度挑戦。 今度は上手く行きました。odeとdrawstuffがコンパイルされています。odeは既にportで入れたので、drawstuffだけを手でコピーしました。 これでサンプルを動かす準備が整いました。

ODEのインターフェース 

ここ にこんな文章があります。 ライブラリ自身はC++で書かれていますが、Cインターフェースを使って欲しいというのが作者の願いのようです。でも、やっぱりC++で書いてみたいです。

サンプルプログラム 

こちらにODEの初級講座があります。これの第６回のソース「サンプルプログラム６マルチ」をC++で書き直してみました。Cインターフェースの解説はこちらにありますが、C++の解説はありません。ですが、odecpp.hなるヘッダが提供されています。これを見ながら実装しました。すこし長いですが全文を貼付けます。10行目のパスは、ODEのソースに含まれているディレクトリへのパスです。drawstuffはOpenGLを使って実装されているので、得意な人にとっては扱いやすいと思います。ソースの解説は...もう少し精通してからにします。

コンパイルオプション 

Header Search Path:

パス	目的
/opt/local/include/	odeヘッダー
/usr/local/include/	drawstuffヘッダー

Library Search Path:

パス	目的
/opt/local/lib	odeライブラリ
/usr/local/lib	drawstuffライブラリ

Other Linker Flags:

-lode -ldrawstuff -framework OpenGL -framework GLUT

Apple LLVM compiler 4.0 - Language:

C++ Language Dialect	C++11 [-std=c++11]
C++ Standard Library	libc++ (LLVM C++ standard library with C++11 support)

実行 

並んだ赤玉が地面に着地して弾みます。55行目のbounceが反発係数です。1のとき完全弾性衝突です。0から1までの間の値を設定します。

Mountain LionはX11を含まない。

Point Cloud Library(PCL)のViewerを起動したら、こんなエラーが出ました。

ERROR: In /opt/local/var/macports/build/_opt_local_var_macports_sources_rsync.macports.org_release_ports_graphics_vtk5/vtk5/work/VTK/Rendering/vtkXOpenGLRenderWindow.cxx, line 1496 vtkXOpenGLRenderWindow (0x7ffc10445250): bad X server connection. DISPLAY=Segmentation fault: 11

bad X server connectionとあるので、Applicationディレクトリ内のX11をクリックしたら、Mountain LionはX11を含みませんという主旨のダイアログがでました。必要ならここからインストールできるよとあるので、それに従ってインストール。 直りました。

Mountain Lionへのアップデート

Mountain Lionへアップデートしたら、デプスセンサXtion Pro Liveが起動しなくなりました。起動時にこんな警告が出ます。
ネットで調べると、primesensorのドライバが動作していないようです。バイナリ版をインストールし直しました。 念のため、OpenNIもインストールし直します。 無事動くようになりました。

さて、Xcodeを4.3から4.4へアップデートしたら、macportsがこけました。 解決方法はこちらです。

Installation of Point Cloud Library to iMac

Introduction

    At the tutorial in SSII2012, a brief introduction to the Point Cloud Library(PCL) was provided. It is the library for processing a point cloud (i.e. 3D point group) generated by a depth sensor. The Kinect and Xtion are familiar devices as the depth sensors. Recently I bought the Xtion Pro Live. So, in this page, I describe the procedures to run a sample program in PCL with the Xtion Pro Live.

My Environment

1. iMac
2. Processor：3.06GHz Intel Core 2 Duo
3. Mac OS X 10.7.4
4. Xcode 4.3.3

Installation of Prerequisite Libraries

    First, I installed the following packages by using macports.

1. cmake @2.8.8
2. boost  @1.49.0
3. eigen3 @3.0.5
4. flann @1.7.1
5. vtk5 @5.8.0
6. qhull @2012.1
7. libusb @1.0.9 

The versions of all packages are those which port search displays. Only for libusb, the variant universal is needed. It takes a long time to compile vtk5.
    Next, I downloaded binary packages of the OpenNI and Sensor from this site.

1. openni-bin-dev-macosx-v1.5.4.0.tar.bz2 
2. sensor-bin-macosx-v5.1.2.1.tar.bz2
3. nite-bin-macosx-v1.5.2.21.tar.bz2

Though the NITE is not needed for installing the PCL, I installed it for future reference. Decompressing them, a script file install.sh is found for each directory. All you have to do is just as follows: At this point, preparation for installing the PCL is completed.

Installation of Point Cloud Library (PCL)

    From this site, I could download the binary package of the PCL, and install it easily. However, when compiling a sample program in PCL, the link with the dependent library failed. Probably, it's because the versions of the prerequisite libraries are different from those consistent with the binary package of the PCL. So, I decided to compile the source codes of the PCL. The file PCL-1.5.1-Source.tar.bz2 can be downloaded from this site. The way to make is here. The default place where libraries and headers are installed is /usr/local.

Execution of Sample Program

    The tool cmake is recommended for compiling the program including PCL. In this page, I show how to compile it on the Xcode4.3.3.

creation of new project

I create a new project as Command Line Tool.

adding of a sample program

I added this file to the project.

setting for compilation

Other Linker Flags:
-lpcl_common -lpcl_visualization -lboost_thread-mt -lpcl_io -lpcl_filters 
Header Search Paths:
/usr/local/include/pcl-1.5/ /opt/local/include /opt/local/include/eigen3/ /usr/include/ni/ /opt/local/include/vtk-5.8/
Library Search Paths:
/usr/local/lib /opt/local/lib 

execution

When executing the project after connecting with the Xtion Pro Live, the following error occurred.

Open failed: File not found!
node depth problems
node image problems
node ir problems

This site tells us that

• create a new directory /etc/primesense
• copy the following file into the directory
  OpenNI-Bin-Dev-MacOSX-v1.5.4.0/Samples/Config/SamplesConfig.xml

After doing so, I got the same error. I ran grep to the file PCL-1.5.1-Source/io/src/openni_camera/openni_device.cpp, and found two places where SamplesConfig.xml must exist:

• /etc/openni/SamplesConfig.xml
• /etc/primesense/SamplesConfig.xml

Therefore, I also copied the SamplesConfig.xml into the directory /etc/openni/. Then, the program works well except for the following warning:
node ir problems

Unsolved Issues

    In the case of Debug mode, the program works well. But, in the case of Release mode, it encounters the segmentation fault.

Point Cloud LibraryのiMacへのインストール 補足

前回書き終えてふと思い出しました。cmakeはxcodeやvisual studioのプロジェクトを作れることを。 「..」は１つ上の階層にCMakeLists.txtがあるので。 出来上がったプロジェクトをコンパイルすると、これが出ます。

The scheme 'openni_grabber' contains no buildables that can be built for the SDKs supported by the run destination My Mac 64-bit. Make sure your targets all specify SDKs that are supported by this version of Xcode.

調べると、Base SDKをCurrent Mac OSに変更すれば良いらしい。確かにコンパイルできました。

Point Cloud LibraryのiMacへのインストール

はじめに

 

 SSII2012のチュートリアルで、Point Cloud Libraryが紹介されていた。これは、デプスセンサの出力値（３次元点群）を処理するためのライブラリである。デプスセンサとしてKinectが有名である。今回、Kinect互換デバイス、Xtion Pro Liveを購入した。以下、サンプルを動かすまでの手順を記す。

環境

1. iMac
2. プロセッサ：3.06GHz Intel Core 2 Duo
3. Mac OS X 10.7.4
4. Xcode 4.3.3

依存ライブラリのインストール 

 

最初に、macportsを使って以下のパッケージをインストールした。

1. cmake @2.8.8
2. boost  @1.49.0
3. eigen3 @3.0.5
4. flann @1.7.1
5. vtk5 @5.8.0
6. qhull @2012.1
7. libusb @1.0.9 

いずれのバージョンも、port searchで見つかる最新版である。ただし、libusbだけはuniversalというバリアントを付加する必要がある。 また、vtk5のコンパイルには少々時間がかかる。
次に、OpenNIとSensorのバイナリをここからダウンロードした。

1. openni-bin-dev-macosx-v1.5.4.0.tar.bz2 
2. sensor-bin-macosx-v5.1.2.1.tar.bz2
3. nite-bin-macosx-v1.5.2.21.tar.bz2

niteは必要ないが、ついでである。これを解凍するとディレクトリ内にinstall.shがあるのでこれを実行すれば良い。 ここまでで、Point Cloud Libraryをインストールする準備が整った。

Point Cloud Library（PCL）のインストール 

 

ここからバイナリを手に入れることができる。しかし、PCLのサンプルをコンパイルした際、依存ライブラリとのリンクに失敗した。推奨されている依存ライブラリのバージョンと異なるからであろう。なのでソースからコンパイルすることとした。ソースはここからダウンロードできる。

1. PCL-1.5.1-Source.tar.bz2

インストール方法はここにある。 デフォルトのインストール先は、/usr/localである。以上でPCLがインストールされた。

サンプルプログラムの実行 

 

PCLを使ったプログラムのコンパイルにはcmakeが推奨されている。今回試した限りではXcodeでも可能である。以下手順を示す。

新規プロジェクトの作成

Command Line Toolとしてプロクジェクトを作成する。

サンプルプログラムの登録

ここにあるサンプルプログラムをプロジェクトに登録する。

コンパイルオプションの設定

Other Linker Flagsに以下を追加する。
-lpcl_common -lpcl_visualization -lboost_thread-mt -lpcl_io -lpcl_filters 

Header Search Pathsに以下を追加する。
/usr/local/include/pcl-1.5/ /opt/local/include /opt/local/include/eigen3/ /usr/include/ni/ /opt/local/include/vtk-5.8/

Library Search Pathsに以下を追加する。
/usr/local/lib /opt/local/lib 

 

実行 

実行すると、以下のエラーが出る。
Open failed: File not found!
node depth problems
node image problems
node ir problems
ここによると、新規にディレクトリ/etc/primesenseを作成し、以下のファイルをその中にコピーせよとある。

• OpenNI-Bin-Dev-MacOSX-v1.5.4.0/Samples/Config/SamplesConfig.xml

その通りにしても同じエラーが出る。PCLのソース（PCL-1.5.1-Source/io/src/openni_camera/openni_device.cpp）をgrepすると以下の２カ所からSamplesConfig.xmlを読んでいることが分る。

• /etc/openni/SamplesConfig.xml
• /etc/primesense/SamplesConfig.xml

従って、/etc/openni/の方にもSamplesConfig.xmlをコピーした。これで実行できた。ただし、
node ir problems
は依然として出たままである。また、Releaseモードでは落ちる。Debugモードでは動く。素直にcmakeを実行した方が良い。追記。