taiji's contents

Boost にある Graph ライブラリ(BGL) はグラフ理論を扱うテンプレートライブラリです。極めて便利なのですが、STL(Standard Template Library)と同様に、実装されている各アルゴリズムの計算量に配慮して利用することが肝要となります。

ここでは、BGLのドキュメントから時間計算量についてまとめました。

9. Boost Graph Library Tutorial

9.2. The adjacency_list class

9.2.1. VertexList

add_vertex	constant
remove_vertex	constant for listS
remove_vertex	O(E+V) for vecS
vertex	constant

9.2.2. OutEdgeList

add_edge	constant for Sequence like vecS
add_edge	O(log(E/V)) for UniqueAssociativeContainer like setS
remove_edge	A(E/V) for Sequence
remove_edge	A(log(E/V)) for setS
edge	O(E/V) for Sequence
edge	O(log(E/V)) for AssociativeContainer
clear_vertex	O(E+V) for directed with Sequence
clear_vertex	O(V log(E/V)) for AssociativeContainer
clear_vertex	O(E^2/V^2) or O(E/V log(E/V)) for undirected
remove_vertex	O(E+V)

12. The Boost Graph Interface

12.4. Adjacency Graph

adjacent_vertices

constant

12.8. AdjacencyMatrix

edge

constant

12.9. Mutable Graph

add_edge	constant or O(log(E/V))
remove_edge	O(E)
add_vertex	constant
clear_vertex	O(E+V)
remove_vertex	O(E+V)

18. Graph classes

18.2. adjacency_matrix

breadth_first_search

O(V^2) instead of adjacency_list's O(V+E)

22.2. Basic Operations

copy_graph	O(V+E)
transpose_graph	O(V+E)

22.3. Core Searches

breadth_first_search	O(E+V)
breadth_first_visit	O(E)
depth_first_search	O(E+V)
depth_first_visit	O(E)
undirected_dfs	O(E+V)

22.4. Other Core Algorithms

topological_sort	O(V+E)
transitive_closure	O(V E)
lengauer_tarjan_dominator_tree	O((V+E)log(V+E))

22.5. Shortest Paths / Cost Minimization Algorithms

dijkstra_shortest_paths	O(V log V)
dijkstra_shortest_paths_no_color_map	O(V log V)
bellman_ford_shortest_paths	O(V E)
dag_shortest_paths	O(V+E)
johnson_all_pairs_shortest_paths	O(V E log V)
floyd_warshall_initialized_all_pairs_shortest_paths	O(V^3)
r_c_shortest_paths	NP-hard so dynamic programming
astar_search	O((E+V)log V)

22.6. Minimum Spanning Tree Algorithms

kruskal_minimum_spanning_tree	O(E log E)
prim_minimum_spanning_tree	O(E log V)

22.7. Connected Components Algorithms

connected_components	O(V+E)
strong_components	O(V+E)
biconnected_components	O(V+E)
articulation_points	〃

22.7.5 Incremental Connected Components

whole process	O(V+E alpha(E，V)) where alpha is the inverse of Ackermann's function
incremental_components	O(E)
same_component	O(alpha(E，V)) where alpha is the inverse of Ackermann's function

22.8. Maximum Flow and Matching Algorithms

edmonds_karp_max_flow	O(V E^2) or O(V E U) for integer capacity bounded by U
push_relabel_max_flow	O(V^3)
edmonds_maximum_cardinality_matching	O(VE alpha(E，V)) where alpha is the inverse of Ackermann's function

22.9. Sparse Matrix Ordering Algorithms

cuthill_mckee_ordering	O(m log(m)V) where m=max{degree(v)|v in V}
minimum_degree_ordering	NP-complete so heuristics
king_ordering	O(m^2 log(m)E) where m=max{degree(v)|v in V}
sloan_ordering	O(log(m)E) where m=max{degree(v)|v in V}

22.10. Graph Metrics

brandes_betweenness_centrality	O(VE) for unweighted or O(VE+V(V+E)log V)
maximum_cycle_ratio，minimum_cycle_ratio	unknown

22.11. Graph Structure Comparisons

isomorphism	O(V!)
mcgregor_common_subgraphs	O(V_1 V_2)

22.12. Layout Algorithms

random_graph_layout	O(V)
fruchterman_reingold_force_directed_layout	O(V^2+E)

22.14. Planar Graph Algorithms

boyer_myrvold_planarity_test	O(V) or O(V+E)
planar_face_traversal	O(V+E)
planar_canonical_ordering	O(V+E)
chrobak_payne_straight_line_drawing	O(V+E)
is_straight_line_drawing	O(V log V)
is_kuratowski_subgraph	O(V)
make_biconnected_planar	O(V)
make_connected	O(V+E)
make_maximal_planar	O(V+E)

22.15. Miscellaneous Algorithms

metric_tsp_approx	O(E log V) or O(V^2) for non-vecS vertices
sequential_vertex_coloring	O(V(d+k)) where d is the maximum degree of the vertices，and k is the number of colors

24. Auxiliary Concepts, Classes, and Functions

incident	O(1)
opposite	O(1)

24.7. Tools for random graphs

random_vertex	O(V)
random_edge	O(E)
generate_random_graph	O(V E)

ドキュメントには直接書かれていないが、参考文献等を辿ればわかることなどは随時補足していこうと思います。

Boost にある Spirit は、EBNF(Extended Backus Naur Form)に似た形式を直接 C++ のコードとして表現することによって、構文解析の機能を提供するライブラリです。

Spirit で使用されている演算子を優先順位でまとめてみました。

Spirit	Name	EBNF	Spiritでの分類	Description
+a	Positive	a+	Optional and Loops	１回以上のマッチ
*a	Kleene star	a*	Optional and Loops	０回以上のマッチ
!a	Optional	a?	Optional and Loops	０回または１回のマッチ
~a	Negation	[^...]	charset	C-aにマッチ(Cは文字集合全体)
a % b	List	a (b a)*	Optional and Loops	１回以上の b 区切り a のリストのマッチ。a>>*(b>>a) と同義
a - b	Difference	a - b	Set	a にマッチかつ b にマッチしない。
a >> b	Sequence	a b	Sequencing	a，b の並びにマッチ
a & b	Intersection	なし	Set	a，b の両方にマッチ
a ^ b	XOR	a - b | b - a	Set	a か b にマッチし両方にはマッチしない。a-b|b-a と同義
a | b	Union，Alternative	a | b	Set	a か b にマッチ
a && b	Sequential-and	a b	Sequencing	a，b の並びにマッチ。a >> b と同義
a || b	Sequential-or	(a b) | a | b，(a b?) | b	Sequencing	a，b の並びもしくはどちらかにマッチ。a>>b|a|b，(a>>!b)|b と同義

私は git://vcs.aihara.co.jp/logdo.git の xpsed で sed スクリプトを構文解析するために使用しましたが、その後、新しい Spirit V2.1 がリリースされたので改めて試す予定。

C++ の演算子をオーバーロードしたクラスを使っていると、演算子の本来の意味から乖離していたりすると、覚えているはずの演算子の優先順位が頭の中で混乱する場合があるので、今一度まとめてみた。

C/C++ の演算子と優先順位：

演算子	例	用途	結合	継承
::	x::y	スコープ(Scope resolution) [C++ only]	→	x
++ --	x++ x--	後置増分、減分(Postfix increment and decrement)	←	o
()	x(y)	関数呼出し(Function call)	←	o
[]	x[y]	配列添字(Array subscripting)	←	o
．	x.y	ドット(Element selection by reference)	←	x
->	x->y	アロー(Element selection through pointer)	←	o
++ --	++x --y	前置増分、減分(Prefix increment and decrement)	→	o
+ -	+x -x	単項正、負(Unary plus and minus)	→	o
&	&x	単項アドレス(Address-of)	→	o
*	*x	単項間接(Indirection)	→	o
! ~	!x ~x	論理否定、ビット否定	→	o
()	(x)y	型キャスト(Type cast)	→	o
sizeof	sizeof x	サイズ(Size-of)	→	x
new new[]	new x new[] y	動的メモリ確保(Dynamic memory allocation) [C++ only]	→	o
delete delete[]	delete x delete[] y	動的メモリ解放(Dynamic memory deallocation) [C++ only]	→	o
.*	x.*y	メンバへのポインタ(Pointer to member) [C++ only]	→	x
->*	x->*y	メンバへのポインタ(Pointer to member) [C++ only]	→	o
* / %	x*y x/y x%y	二項乗、除、法(Multiplication，division，and modulus)	→	o
+ -	x+y x-y	二項加、減(Addition and subtraction)	→	o
<< >>	x<<y x>>y	ビット左、右シフト(Bitwise left shift and right shift)	→	o
< <=	x<y x<=y	関係不等号(Relational "less than" and "or equal to")	→	o
> >=	x>y x>=y	関係不等号(Relational "greater than" and "or equal to")	→	o
== !=	x==y x!=y	関係等号、不等号(Relational "equal to" and "not equal to")	→	o
&	x&y	ビットAND(Bitwise AND)	→	o
^	x^y	ビットXOR(Bitwise XOR)	→	o
|	x|y	ビットOR(Bitwise OR)	→	o
&&	x&&y	論理AND(Logical AND)	→	*
||	x||y	論理OR(Logical OR)	→	*
? :	x?y:z	三項条件(Ternary conditional)	←	x
=	x=y	単純代入(Direct assignment)	←	o
+= -=	x+=y	複合代入(Assignment by sum and difference)	←	o
*= /= %=	x*=y	複合代入(Assignment by product，quotient，and remainder)	←	o
<<= >>=	x<<=y	複合代入(Assignment by bitwise left shift and right shift)	←	o
&= ^= |=	x+=y	複合代入(Assignment by bitwise AND，XOR，and OR)	←	o
，	x，y	コンマ(Comma)	→	*

てゆーか、手元でまとめてあったのを表組で投稿してみた。

Tokyo Promenade がサクサクなので Solaris の非力なサーバマシンにも入れてみた。32bit だと tokyocabinet がビルドできなかったので以下のような感じ。

• tokyocabinet を ./configure CFLAGS=-m64 && make && make check && su root -c 'make install' して、
• tokyopromenade を ./configure CFLAGS=-m64 && make && make check && su root -c 'make install' して、
• 以下のように ~/public_html/tp にセットアップした。

basedir=tp
[ -d "$basedir" ] || mkdir "$basedir"
(cd "$basedir"	&&
cp -p /opt/local/share/tokyopromenade/promenade.* .	&&
cp -p /opt/local/share/tokyopromenade/passwd.txt .	&&
prommgr create promenade.tct	&&
prommgr import promenade.tct /opt/local/share/tokyopromenade/misc/help-*.tpw	&&
mkdir upload	&&
su root -c 'chgrp -R www .'	&&
su root -c 'chmod -R g+w .'	&&
cat <<EOF > .htaccess	&&
Options FollowSymLinks ExecCGI MultiViews
Order allow,deny
Allow from all
DirectoryIndex promenade.cgi
<Files ~ "passwd">
    Order allow,deny
    Deny from all
    Satisfy All
</Files>
EOF
ln -s /opt/local/libexec/promenade.cgi .	&&
echo done
)

Solaris でも問題なくキビキビ動作しているようだ。

Mac OS X に Tokyo Promenade をインストールして、パーソナル Web 共有の ~/Site/tp/ に導入してみた。その手順は、

• tokyocabinet を configure && make && make check && sudo make install する。
• tokyopromenade を configure && make && make check && sudo make install する。
• 後は基本的にドキュメント通りだけど、ここでは以下のようにした。

basedir=tp
[ -d "$basedir" ] || mkdir "$basedir"
(cd "$basedir"	&&
cp -p /opt/local/share/tokyopromenade/promenade.* .	&&
cp -p /opt/local/share/tokyopromenade/passwd.txt .	&&
prommgr create promenade.tct	&&
prommgr import promenade.tct /opt/local/share/tokyopromenade/misc/help-*.tpw	&&
mkdir upload	&&
sudo chgrp -R www .	&&
sudo chmod -R g+w .	&&
cat <<EOF > .htaccess	&&
Options FollowSymLinks ExecCGI MultiViews
Order allow,deny
Allow from all
DirectoryIndex promenade.cgi
<Files ~ "passwd">
    Order allow,deny
    Deny from all
    Satisfy All
</Files>
EOF
ln -s /opt/local/libexec/promenade.cgi .	&&
echo done
)

admin のデフォルトパスワードはドキュメントに書いてあるので、それでブラウザでログインして、パスワードを変えたり、新しいユーザを作成すればよい。

記事をWiki記法で執筆して、いざ投稿してみよう！