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