Weblog13

お願い申し上げます。

Contraction Hierarchies (CHs) のプログラムを使ってみたが。。

2012-12-07 10:44:18 | 研究
昨日もCHsのプログラムをいじっていたのだが、問題(?)が発生。
プログラムの機能としては

・ノード順序の構成を作成
・CHsの構成を作成

この2つだ。

しかしアウトプットファイルとして出力すると文字化け?してしまう。
そもそもこのファイルを使ってどうやって最短経路を求めるのだろうか・・・・・。

以下出力ファイル
CH
^A^@^@^@^F^@^@^@^E^@^@^@^@^@^@^@^E^@^@^@^@^@^@^@^C^@^@^@^D^@^@^@^A^@^@^@^B^@^@^@^A^@^@^@^E^@^@^@^B^@^@^@^C^@^@^@^B^@^@^@^C^@^@^@^A^@^@^@^C^@^@^@^C^@^@^@^@^@^@^@^B^@^@^@^C^@^@^@^\
D^@^@^@^B^@^@^@^B^@^@^@^C^@^@^@^E^@^@^@^@^@^@^@^C^@^@^@^C^@^@^@xV4^R

値の文字化けなのかもともとこういうものなのか。
中間ファイルなのか。

Contraction Hierarchiesのコンパイル方法

2012-12-07 01:52:01 | 研究
全対全最短路を超高速で求めるアルゴリズムを発見しました。
このアルゴリズムの詳細はまた今度紹介します。
とりあえず忘れないうちに書き残しておきます。

まずKITのサイトからContraciton Hierarchies(CHs)のプログラムをダウンロードしてきます。

http://algo2.iti.kit.edu/routeplanning.php


そのままコンパイルするとboostが無いと言われるのでboostをインストールします。

$sudo port install boost @1.52.0 (2012/12/06時点で最新)


もしインストールしてもファイルが無いと言われた場合はパスを設定する。
参考サイト様 [Adukan: http://d.hatena.ne.jp/aduka/20081222/1229909299]

export PATH=/opt/local/bin:/opt/local/sbin/:$PATH
export MANPATH=/opt/local/man:$MANPATH
export LIBRARY_PATH=/opt/local/lib:$LIBRARY_PATH
export LD_LIBRARY_PATH=/opt/local/lib:$LD_LIBRARY_PATH
export C_INCLUDE_PATH=/opt/local/include:$C_INCLUDE_PATH
export CPLUS_INCLUDE_PATH=/opt/local/include:$CPLUS_INCLUDE_PATH
export DYLD_FALLBACK_LIBRARY_PATH=/opt/local/lib
export BOOST_ROOT=/opt/local/include/boost:$BOOST_ROOT


ようやくコンパイル!!としてもうまくいかない。
ushortがなんだかというエラーがでる。

そこでdatastr/searchSpaces.hを開いて、


typedef DynamicIndexedSearchSpace< CompleteSearchSpaceEntry<int, EdgeWeight> > DISSInt;
typedef DynamicIndexedSearchSpace< CompleteSearchSpaceEntry<short, ushort > > DISSShort;
typedef IndexedSearchSpace< SearchSpaceEntry<int, EdgeWeight> > ISSInt;
typedef IndexedSearchSpace< SearchSpaceEntry<short, ushort> > ISSShort;


のushortのところを


typedef DynamicIndexedSearchSpace< CompleteSearchSpaceEntry<int, EdgeWeight> > DISSInt;
typedef DynamicIndexedSearchSpace< CompleteSearchSpaceEntry<short, uint16_t> > DISSShort;
typedef IndexedSearchSpace< SearchSpaceEntry<int, EdgeWeight> > ISSInt;
typedef IndexedSearchSpace< SearchSpaceEntry<short, uint16_t > > ISSShort;


uint16_tに変更する。


ここでmakeをするとまだエラーをだす。

g++ -lboost_regex -lboost_iostreams -o main main.o
ld: library not found for -lboost_regex
collect2: ld returned 1 exit status
make: *** [main] Error 1


なぜだかわからないがboost_regexとboost_iostreamsというライブラリが見つからないので、compiler.makeファイルの

LINK = -lboost_regex -lboost_iostreams

の部分を

LINK = -lboost_regex-mt -lboost_iostreams-mt

に変更する。

これでmakeと打てばコンパイル完了である。


せっかくコンパイルしたので実行してみる。


$ ./main -s -p -f docu/example.ddsg -o x -l x -x 190 -y 1 -e 600 -p 1000 -k 1,3.3,2,10,3,10,5
Order nodes with priority-queue...
test 0
edgeDiffMult 190
searchSpaceMult 1
betweennessAdd 0
reachAdd 0
delNeighbMult 0
newEdgesMult 0
maxSettledApprox 0
lazyUpdateRecalcLimit 1000
maxSettledElim 0
maxHops 1-3.3-2-10-3-10-5-
voronoiMult 0
searchPathHopBorderMult 0
updateHops 0
localReduceEdges 1
shortcutOriginalEdgeSumMult 600
searchPathHopBorderOriginalEdges 0
output exact-190-1-0-0-0-0-0-1000-0-1-3.3-2-10-3-10-5-0-0-0-1-600-0.hcn
Open file docu/example.ddsg...
Import Graph: n = 6, m = 5
0 oneway street(s).
** memory usage on hard disk [MB (bytes per node)] **
edges: 0 (27)
node data: 0 (20)
node ID mapping: 0 (4)
TOTAL: 0 (51)

Create node order and hierarchy using a priority queue...
Initialize elimination weights...
.... 10% .... 20% .... 30% .... 40% .... 50% .... 60% .... 70% .... 80% . 100%
#nodes: 6 / #edges: 10
Eliminatate by priority-queue...
.... 10% .... 20% .... 30% .... 40% .... 50% .... 60% .... 70% .... 80% . 100%
#edges: 10 / 20
Write node order (levels) to exact-190-1-0-0-0-0-0-1000-0-1-3.3-2-10-3-10-5-0-0-0-1-600-0.hcn ...
node ordering time: 0.000185013 s
max avg degree: 1.6
#edges: 10
#total expanded edges: 0


これでノードの順序とCHsのグラフができたらしい。
細かい所が全然わからないのでまたブログで連絡します。

gnuplot導入

2012-08-30 16:05:44 | 研究
昨日、ノリと勢いでOSをMountainLionにしました。
さらにgnuplotの記事を見て、自分も使ってみたい!と思ったのでインストールしてみました。
意外とめんどくさかったので、メモとして残しておきます。

1.Xcodeをインストール
まずXcodeをインストールして下さい。
appsoreに行けば見つかると思います。

2.macportsをインストール
インストールを楽にする為にmacportsをインストールしましょう。
http://www.macports.org/
からインストールできます。

3.macportsを使ってみる
macportsの情報を最新のものにするため

$ sudo port -d selfupdate

と入力してください。
そうすると

DEBUG: Copying /Users/******/Library/Preferences/com.apple.dt.Xcode.plist to /opt/local/var/macports/home/Library/Preferences
DEBUG: MacPorts sources location: /opt/local/var/macports/sources/rsync.macports.org/release/tarballs
---> Updating MacPorts base sources using rsync
rsync: failed to connect to rsync.macports.org: Connection refused (61)
rsync error: error in socket IO (code 10) at /SourceCache/rsync/rsync-42/rsync/clientserver.c(105) [receiver=2.6.9]
Command failed: /usr/bin/rsync -rtzv --delete-after rsync://rsync.macports.org/release/tarballs/base.tar /opt/local/var/macports/sources/rsync.macports.org/release/tarballs
Exit code: 10
DEBUG: Error synchronizing MacPorts sources: command execution failed
while executing
"macports::selfupdate [array get global_options] base_updated"
Error: /opt/local/bin/port: port selfupdate failed: Error synchronizing MacPorts sources: command execution failed

と出てきて上手く行かないはずです。

4.ポートをあける

->rsync: failed to connect to rsync.macports.org: Connection refused (61)
->rsync error: error in socket IO (code 10) at /SourceCache/rsync/rsync-42/rsync/clientserver.c(105) [receiver=2.6.9]


と書いてある通りポートが開いていないのが問題です。
そこで~/.profile(無ければ作りましょう)に

http_proxy=http://<proxy_server>:<proxy_port>

と書き込んで下さい。

そして次に/opt/local/etc/macports/sources.confを開いて編集します。(sudoを使って下さい)

#rsync://rsync.macports.org/release/ports/ [default]
http://www.macports.org/files/ports.tar.gz [default]


としていただければ大丈夫です。

$ sudo port -d sync

とコマンドを入力して下さい。これでデータベースが最新のものになるはずです。

5. Command Line Tools for Xcodeのインストール
そこでもう一回

$ sudo port install gnuplot

と入力すると

Warning: The Command Line Tools for Xcode don't appear to be installed; most ports will likely fail to build.
Warning: See http://guide.macports.org/chunked/installing.xcode.html for more information.
---> Computing dependencies for gnuplotError: Unable to execute port: can't read "build.cmd": Failed to locate 'make' in path: '/usr/bin/svn' or at its MacPorts configuration time location, did you move it?


このようになるはずです。
->The Command Line Tools for Xcode don't appear to be installed
と書いてありますので、Xcodeを立ち上げてりんごの隣にある「Xcode」下の「preference」をクリックします。
そこにCommand Line Tools があるのでインストールして下さい。

$ sudo port -d install gnuplot

と入力すると


---> Building aquaterm
DEBUG: Executing org.macports.build (aquaterm)
DEBUG: Assembled command: 'cd "/opt/local/var/macports/build/_opt_local_var_macports_sources_www.macports.org_files_ports_aqua_aquaterm/aquaterm/work/AquaTerm-1.1.1/aquaterm" && /usr/bin/xcodebuild -target "AquaTerm" -configuration Default build OBJROOT=build/ SYMROOT=build/ MACOSX_DEPLOYMENT_TARGET=10.8 ARCHS=x86_64 SDKROOT="" GCC_VERSION=com.apple.compilers.llvm.clang.1_0 LOCAL_APPS_DIR=/Applications/MacPorts LOCAL_FRAMEWORKS_DIR=/opt/local/Library/Frameworks'

You have not agreed to the Xcode license agreements, please run 'xcodebuild -license' (for user-level acceptance) or 'sudo xcodebuild -license' (for system-wide acceptance) from within a Terminal window to review and agree to the Xcode license agreements.
Command failed: cd "/opt/local/var/macports/build/_opt_local_var_macports_sources_www.macports.org_files_ports_aqua_aquaterm/aquaterm/work/AquaTerm-1.1.1/aquaterm" && /usr/bin/xcodebuild -target "AquaTerm" -configuration Default build OBJROOT=build/ SYMROOT=build/ MACOSX_DEPLOYMENT_TARGET=10.8 ARCHS=x86_64 SDKROOT="" GCC_VERSION=com.apple.compilers.llvm.clang.1_0 LOCAL_APPS_DIR=/Applications/MacPorts LOCAL_FRAMEWORKS_DIR=/opt/local/Library/Frameworks
Exit code: 69
Error: org.macports.build for port aquaterm returned: command execution failed
DEBUG: Error code: NONE
DEBUG: Backtrace: command execution failed
while executing
"$procedure $targetname"
Warning: targets not executed for aquaterm: org.macports.activate org.macports.build org.macports.destroot org.macports.install
Error: Failed to install aquaterm
DEBUG: couldn't open "/System/Library/Frameworks/Tcl.framework/Versions/8.5/Resources/tclIndex": no such file or directory
while executing
"open [file join $dir tclIndex]"
Please see the log file for port aquaterm for details:
/opt/local/var/macports/logs/_opt_local_var_macports_sources_www.macports.org_files_ports_aqua_aquaterm/aquaterm/main.log
Error: The following dependencies were not installed: aquaterm expat fontconfig freetype bzip2 zlib libiconv gperf pkgconfig glib2 gettext ncurses libffi perl5 perl5.12 gdbm xz gd2 autoconf help2man p5.12-locale-gettext m4 automake jpeg libpng libtool xpm xorg-libXext xorg-libX11 xorg-bigreqsproto xorg-inputproto xorg-kbproto xorg-libXau xorg-xproto xorg-libXdmcp xorg-libxcb python27 db46 libedit openssl python_select sqlite3 xorg-libpthread-stubs xorg-xcb-proto libxml2 xorg-xcmiscproto xorg-xextproto xorg-xf86bigfontproto xorg-xtrans xorg-util-macros xorg-libXt xorg-libsm xorg-libice lua readline pango Xft2 xrender xorg-renderproto cairo libpixman xorg-xcb-util gobject-introspection pdflib
To report a bug, follow the instructions in the guide:
http://guide.macports.org/#project.tickets
Error: Processing of port gnuplot failed


またこんな事を言ってくるはずです。

->DEBUG: Assembled command: 'cd "/opt/local/var/macports/build/_opt_local_var_macports_sources_www.macports.org_files_ports_aqua_aquaterm/aquaterm/work/AquaTerm-1.1.1/aquaterm" && /usr/bin/xcodebuild -target "AquaTerm" -configuration Default build OBJROOT=build/ SYMROOT=build/ MACOSX_DEPLOYMENT_TARGET=10.8 ARCHS=x86_64 SDKROOT="" GCC_VERSION=com.apple.compilers.llvm.clang.1_0 LOCAL_APPS_DIR=/Applications/MacPorts LOCAL_FRAMEWORKS_DIR=/opt/local/Library/Frameworks'

と言っているので、

$ cd /opt/local/var/macports/build/_opt_local_var_macports_sources_www.macports.org_files_ports_aqua_aquaterm/aquaterm/work/AquaTerm-1.1.1/aquaterm
$ /usr/bin/xcodebuild -target "AquaTerm" -configuration Default build OBJROOT=build/ SYMROOT=build/ MACOSX_DEPLOYMENT_TARGET=10.8 ARCHS=x86_64 SDKROOT="" GCC_VERSION=com.apple.compilers.llvm.clang.1_0 LOCAL_APPS_DIR=/Applications/MacPorts LOCAL_FRAMEWORKS_DIR=/opt/local/Library/Frameworks


を行い

$ sudo xcodebuild -license

でライセンスを開いてaccept と入力します。

そして

$ sudo port install -d gnuplot

と打てば終了です。

(追記)
MacBookAir にはインストール出来たのですが、iMacでは上手く行きませんでした。
ただいま原因を考え中です。

[参考にしたサイト様]
「gnuplot を Mac OS X Lion へインストール」
http://co.maxwell.jp/?page=gnuplot+%A4%F2+Mac+OS+X+Lion+%A4%D8%A5%A4%A5%F3%A5%B9%A5%C8%A1%BC%A5%EB
「ishwt::tracking : プロキシ環境(社内 LANとか)の中でMacPortsを使う」
http://ishwt.net/blog/2011/04/05/use-macports-at-inside-of-proxy/