1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" 2"http://www.w3.org/TR/html4/loose.dtd"> 3<HTML> 4<!-- 5 Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 6 7 Distributed under the Boost Software License, Version 1.0. 8 (See accompanying file LICENSE_1_0.txt or copy at 9 http://www.boost.org/LICENSE_1_0.txt) 10 --> 11<Head> 12<meta http-equiv="Content-Type" content="text/html;charset=utf-8" > 13<Title>Table of Contents: Boost Graph Library</Title> 14<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 15 ALINK="#ff0000"> 16<IMG SRC="../../../boost.png" 17 ALT="C++ Boost" width="277" height="86"> 18 19<h1>Table of Contents: the Boost Graph Library 20<a href="http://www.awprofessional.com/title/0201729148"> 21<img src="bgl-cover.jpg" ALT="BGL Book" ALIGN="RIGHT"></a> 22</h1> 23 24 <OL> 25 <LI><A Href="./index.html">Introduction to the BGL</A> 26 <li><a href="../../graph_parallel/doc/html/index.html">Parallel BGL (distributed-memory parallel graph data structures and algorithms)</a> 27 <LI><A Href="./history.html">History</A> 28 <LI><A Href="./users.html">List of BGL Users</A> 29 <LI><A Href="./publications.html">Publications</A> 30 <LI><A Href="./acknowledgements.html">Acknowledgements</A> 31 <LI><A href="./quick_tour.html">A Quick Tour of the Boost Graph Library.</a> 32 <LI><A Href="graph_theory_review.html">Review of Elementary Graph Theory</A> 33 <LI>Boost Graph Library Tutorial 34 <OL> 35 <LI><a 36 href="./using_property_maps.html">Property Maps</a> 37 <LI><a 38 href="./using_adjacency_list.html">The <tt>adjacency_list</tt> class</a> 39 </OL> 40 <LI>Examples 41 <OL> 42 <LI><a href="./file_dependency_example.html">File 43 Dependency Example</a> 44 <LI><a href="./kevin_bacon.html">Six Degrees of Kevin Bacon</a> 45 <LI><a href="./graph_coloring.html">Graph Coloring</a> 46 <LI><a href="./sparse_matrix_ordering.html">Sparse Matrix 47 Ordering</a> 48 </OL> 49 <LI>Extending the Boost Graph Library 50 <OL> 51 <LI><a href="./constructing_algorithms.html">Constructing graph algorithms with BGL</a> 52 <LI><a href="./leda_conversion.html">Converting Existing Graphs to BGL</a> 53 </OL> 54 <LI><A href="./graph_concepts.html">The Boost Graph Interface</A> 55 <OL> 56 <LI><A href="./Graph.html">Graph</A> 57 <LI><A href="./IncidenceGraph.html">Incidence Graph</A> 58 <LI><A href="./BidirectionalGraph.html">Bidirectional Graph</A> 59 <LI><A href="./AdjacencyGraph.html">Adjacency Graph</A> 60 <LI><A href="./VertexListGraph.html">Vertex List Graph</A> 61 <LI><A href="./EdgeListGraph.html">Edge List Graph</A> 62 <LI><A href="./VertexAndEdgeListGraph.html">Vertex and Edge List Graph</A> 63 <LI><A href="./AdjacencyMatrix.html">Adjacency Matrix</A> 64 <LI><A href="./MutableGraph.html">Mutable Graph</A> 65 <LI><A href="./PropertyGraph.html">Property Graph</A> 66 <LI><A href="./MutablePropertyGraph.html">Mutable Property Graph</A> 67 </OL> 68 <li><a href="../../property_map/doc/property_map.html">The Property Map Library</a> (technically not part of the graph library, but used a lot here) 69 <li><img src="figs/python_ico.gif" alt="(Python)"><a href="python.html">Python bindings</a></li> 70 <li><a href="./visitor_concepts.html">Visitor Concepts</a> 71 <OL> 72 <LI><a href="./BFSVisitor.html">BFS Visitor</a> 73 <LI><a href="./DFSVisitor.html">DFS Visitor</a> 74 <LI><a href="./DijkstraVisitor.html">Dijkstra Visitor</a> 75 <LI><a href="./BellmanFordVisitor.html">Bellman Ford Visitor</a> 76 <LI><a href="AStarVisitor.html">A* Visitor</a></LI> 77 <LI><a href="./EventVisitor.html">Event Visitor</a> 78 <LI><a href="./PlanarFaceVisitor.html">Planar Face Visitor</a> 79 <li><a href="TSPTourVisitor.html">TSP Tour Visitor</a></li> 80 </OL> 81 <li>EventVisitorList Adaptors 82 <OL> 83 <LI><a href="EventVisitorList.html">Event Visitor List</a> 84 <LI><a href="bfs_visitor.html"><tt>bfs_visitor</tt></a> 85 <LI><a href="dfs_visitor.html"><tt>dfs_visitor</tt></a> 86 <LI><a href="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a> 87 <LI><a href="bellman_visitor.html"><tt>bellman_visitor</tt></a> 88 <li><a href="astar_visitor.html"><tt>astar_visitor</tt></a></li> 89 </OL> 90 <li>Event Visitors 91 <OL> 92 <LI><a href="predecessor_recorder.html"><tt>predecessor_recorder</tt></a> 93 <LI><a href="edge_predecessor_recorder.html"><tt>edge_predecessor_recorder</tt></a> 94 <LI><a href="distance_recorder.html"><tt>distance_recorder</tt></a> 95 <LI><a href="time_stamper.html"><tt>time_stamper</tt></a> 96 <LI><a href="property_writer.html"><tt>property_writer</tt></a> 97 <LI><a href="property_put.html"><tt>property_put</tt></a> 98 <li><a href="tsp_tour_visitor.html"><tt>tsp_tour_visitor</tt></a></li> 99 <li><a href="tsp_tour_len_visitor.html"><tt>tsp_tour_len_visitor</tt></a></li> 100 </OL> 101 <LI>Graph classes 102 <OL> 103 <LI><A href="./adjacency_list.html"><tt>adjacency_list</tt></a></li> 104 <OL> 105 <LI><A href="./directed_graph.html"><tt>directed_graph</tt></a></li> 106 <LI><A href="./undirected_graph.html"><tt>undirected_graph</tt></a></li> 107 </OL> 108 <LI><A href="./adjacency_matrix.html"><tt>adjacency_matrix</tt></a></li> 109 <li><a href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a></li> 110 </OL></li> 111 <LI>Graph Adaptors 112 <OL> 113 <LI><A href="./subgraph.html"><tt>subgraph</tt></A> 114 <LI><A href="./edge_list.html"><tt>edge_list</tt></A> 115 <LI><A href="./reverse_graph.html"><tt>reverse_graph</tt></A> 116 <LI><A href="./filtered_graph.html"><tt>filtered_graph</tt></A> 117 <LI><A href="../../../boost/graph/vector_as_graph.hpp">Vector as Graph </A><a href="#*">*</a> 118 <LI><A href="../../../boost/graph/matrix_as_graph.hpp">Matrix as Graph</A><a href="#*">*</a> 119 <LI><A href="../../../boost/graph/leda_graph.hpp">Leda Graph </A><a href="#*">*</a> 120 <LI><A href="./stanford_graph.html">Stanford GraphBase</A> 121 <LI>Implicit Graphs 122 <OL> 123 <LI><A href="./grid_graph.html">Multi-dimensional grid graph</A> 124 </OL> 125 </ol> 126 <LI>Iterator Adaptors 127 <OL> 128 <LI><a 129 href="./adjacency_iterator.html"><tt>adjacency_iterator</tt></a> 130 <LI><a 131 href="./inv_adjacency_iterator.html"><tt>inv_adjacency_iterator</tt></a> 132 </OL> 133 <LI>Traits classes 134 <OL> 135 <LI><a href="./graph_traits.html"><tt>graph_traits</tt></a> 136 <LI><a href="./adjacency_list_traits.html"><tt>adjacency_list_traits</tt></a> 137 <LI><a href="./property_map.html"><tt>property_map</tt></a> 138 </OL> 139 <LI>Algorithms 140 <OL> 141 <LI><a href="./bgl_named_params.html">Named parameters (used in many graph algorithms)</a> 142 <li>Basic Operations 143 <ol> 144 <LI><A href="copy_graph.html"><tt>copy_graph</tt></A> 145 <LI><A href="transpose_graph.html"><tt>transpose_graph</tt></A> 146 </ol> 147 <LI>Core Searches 148 <OL> 149 <LI><A href="./breadth_first_search.html"><tt>breadth_first_search</tt></A> 150 <LI><A href="./breadth_first_visit.html"><tt>breadth_first_visit</tt></A> 151 <LI><A 152 href="./depth_first_search.html"><tt>depth_first_search</tt></A> 153 <LI><A href="./depth_first_visit.html"><tt>depth_first_visit</tt></A> 154 <LI><A 155 href="./undirected_dfs.html"><tt>undirected_dfs</tt></A> 156 </OL> 157 158 <li>Other Core Algorithms 159 <ol> 160 <LI><A href="topological_sort.html"><tt>topological_sort</tt></A> 161 <li><a href="transitive_closure.html"><tt>transitive_closure</tt></a> 162 <li><a href="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a></li> 163 </ol> 164 165 <LI>Shortest Paths / Cost Minimization Algorithms 166 <OL> 167 <LI><A href="./dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></A> 168 <LI><A href="./dijkstra_shortest_paths_no_color_map.html"><tt>dijkstra_shortest_paths_no_color_map</tt></A> 169 <LI><A href="./bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></A> 170 <LI><A href="./dag_shortest_paths.html"><tt>dag_shortest_paths</tt></A> 171 <LI><A 172 href="./johnson_all_pairs_shortest.html"><tt>johnson_all_pairs_shortest_paths</tt></A> 173 <li><a href="floyd_warshall_shortest.html"><tt>floyd_warshall_all_pairs_shortest_paths</tt></a></li> 174 <li><a href="r_c_shortest_paths.html"><tt>r_c_shortest_paths</tt> - resource-constrained shortest paths</a></li> 175 <li><a href="astar_search.html"><tt>astar_search</tt> (A* search algorithm)</a></li> 176 </OL> 177 <LI>Minimum Spanning Tree Algorithms 178 <OL> 179 <LI><A 180 href="./kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree</tt></A> 181 <LI><A 182 href="./prim_minimum_spanning_tree.html"><tt>prim_minimum_spanning_tree</tt></A> 183 </OL> 184 <LI>Random Spanning Tree Algorithm 185 <OL> 186 <LI><A 187 href="./random_spanning_tree.html"><tt>random_spanning_tree</tt></A> 188 </OL> 189 <LI>Algorithm for Common Spanning Trees of Two Graphs 190 <OL> 191 <LI><A 192 href="./two_graphs_common_spanning_trees.html"><tt>two_graphs_common_spanning_trees</tt></A> 193 </OL> 194 <LI>Connected Components Algorithms 195 <OL> 196 <LI><A href="./connected_components.html"><tt>connected_components</tt></A> 197 <LI><A href="./strong_components.html"><tt>strong_components</tt></A> 198 199 <LI><a href="biconnected_components.html"><tt>biconnected_components</tt></a> 200 <LI><a href="biconnected_components.html#sec:articulation_points"><tt>articulation_points</tt></a> 201 <LI><a href="./incremental_components.html">Incremental Connected Components</a> 202 <OL> 203 <LI><A href="./incremental_components.html#sec:initialize-incremental-components"><tt>initialize_incremental_components</tt></A> 204 <LI><A href="./incremental_components.html#sec:incremental-components"><tt>incremental_components</tt></A> 205 <LI><A 206 href="./incremental_components.html#sec:same-component"><tt>same_component</tt></A> 207 <LI><A href="./incremental_components.html#sec:component-index"><tt>component_index</tt></A> 208 </OL> 209 </OL></LI> 210 <LI>Maximum Flow and Matching Algorithms 211 <OL> 212 <LI><A href="edmonds_karp_max_flow.html"><tt>edmonds_karp_max_flow</tt></A> 213 <LI><A href="push_relabel_max_flow.html"><tt>push_relabel_max_flow</tt></A> 214 <li><a href="boykov_kolmogorov_max_flow.html"><tt>boykov_kolmogorov_max_flow</tt></a></li> 215 <LI><A href="maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></A> 216 <LI><A href="maximum_weighted_matching.html"><tt>maximum_weighted_matching</tt></A> 217 </OL> 218 <LI>Minimum Cost Maximum Flow Algorithms 219 <OL> 220 <LI><A href="cycle_canceling.html"><tt>cycle_canceling</tt></A> 221 <LI><A href="successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights</tt></A> 222 <li><a href="find_flow_cost.html"><tt>find_flow_cost</tt></a></li> 223 </OL> 224 <LI>Minimum Cut Algorithms 225 <OL> 226 <LI><A href="stoer_wagner_min_cut.html"><tt>stoer_wagner_min_cut</tt></A> 227 </OL> 228 <li>Sparse Matrix Ordering Algorithms 229 <ol> 230 <LI><A 231 href="./cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a> 232 <li><a href="king_ordering.html"><tt>king_ordering</tt></a></li> 233 <LI><a href="./minimum_degree_ordering.html"><tt>minimum_degree_ordering</tt></a> 234 <li><a href="sloan_ordering.htm"><tt>sloan_ordering</tt></a></li> 235 <li><a href="sloan_start_end_vertices.htm"><tt>sloan_start_end_vertices</tt></a></li> 236 </ol> 237 </li> 238 <li>Graph Metrics 239 <ol> 240 <LI><A href="./wavefront.htm"><tt>ith_wavefront</tt>, <tt>max_wavefront</tt>, <tt>aver_wavefront</tt>, and <tt>rms_wavefront</tt></A></LI> 241 <LI><a href="./bandwidth.html#sec:bandwidth"><tt>bandwidth</tt></a> 242 <LI><a href="./bandwidth.html#sec:ith-bandwidth"><tt>ith_bandwidth</tt></a> 243 <LI><A href="betweenness_centrality.html"><tt>brandes_betweenness_centrality</tt></A></LI> 244 <li><a href="howard_cycle_ratio.html"><tt>minimum_cycle_ratio</tt> and <tt>maximum_cycle_ratio</tt></a></li> 245 </ol> 246 </li> 247 <li>Graph Structure Comparisons 248 <ol> 249 <LI><A href="isomorphism.html"><tt>isomorphism</tt></A> 250 <LI><A href="vf2_sub_graph_iso.html"><tt>vf2_sub_graph_iso</tt> (VF2 subgraph isomorphism algorithm)</A> 251 <li><a href="mcgregor_common_subgraphs.html"><tt>mcgregor_common_subgraphs</tt></a></li> 252 </ol> 253 254 <li>Layout Algorithms 255 <ol> 256 <li><a href="topology.html">Topologies used as spaces for graph drawing</a></li> 257 <li><a href="random_layout.html"><tt>random_graph_layout</tt></a></li> 258 <li><a href="circle_layout.html"><tt>circle_layout</tt></a></li> 259 <li><a href="kamada_kawai_spring_layout.html"><tt>kamada_kawai_spring_layout</tt></a></li> 260 <li><a href="fruchterman_reingold.html"><tt>fruchterman_reingold_force_directed_layout</tt></a></li> 261 <li><a href="gursoy_atun_layout.html"><tt>gursoy_atun_layout</tt></a></li> 262 </ol> 263 </li> 264 <li>Clustering algorithms 265 <ol> 266 <li><a href="bc_clustering.html"><tt>betweenness_centrality_clustering</tt></a></li> 267 </ol> 268 </li> 269 <li><a href="planar_graphs.html">Planar Graph Algorithms</a> 270 <ol> 271 <li><a href="boyer_myrvold.html"> 272 <tt>boyer_myrvold_planarity_test</tt></a> 273 <li><a href="planar_face_traversal.html"> 274 <tt>planar_face_traversal</tt></a> 275 <li><a href="planar_canonical_ordering.html"> 276 <tt>planar_canonical_ordering</tt></a> 277 <li><a href="straight_line_drawing.html"> 278 <tt>chrobak_payne_straight_line_drawing</tt></a> 279 <li><a href="is_straight_line_drawing.html"> 280 <tt>is_straight_line_drawing</tt></a> 281 <li><a href="is_kuratowski_subgraph.html"> 282 <tt>is_kuratowski_subgraph</tt></a> 283 <li><a href="make_connected.html"> 284 <tt>make_connected</tt></a> 285 <li><a href="make_biconnected_planar.html"> 286 <tt>make_biconnected_planar</tt></a> 287 <li><a href="make_maximal_planar.html"> 288 <tt>make_maximal_planar</tt></a> 289 </ol> 290 291 <li>Miscellaneous Algorithms 292 <ol> 293 <li><a href="metric_tsp_approx.html"><tt>metric_tsp_approx</tt></a></li> 294 <LI><A href="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></A></li> 295 <LI><A href="edge_coloring.html"><tt>edge_coloring</tt></A></li> 296 <LI><A href="is_bipartite.html"><tt>is_bipartite</tt></A> (including two-coloring of bipartite graphs)</li> 297 <LI><A href="find_odd_cycle.html"><tt>find_odd_cycle</tt></A></li> 298 <LI><A href="maximum_adjacency_search.html"><tt>maximum_adjacency_search</tt></A></li> 299 <LI><A href="hawick_circuits.html"><tt>hawick_circuits</tt></A> (find all circuits of a directed graph)</li> 300 </ol> 301 </li> 302 303 </OL> 304 305 <li>Graph Input/Output 306 <ol> 307 <li>AT&T Graphviz: <a href="read_graphviz.html">read_graphviz</a>, <a href="./write-graphviz.html">write_graphviz</a></li> 308 <li>DIMACS Max-flow: <a href="read_dimacs.html">read_dimacs_max_flow and read_dimacs_min_cut</a>, <a href="write_dimacs.html">write_dimacs_max_flow</a></li> 309 <li>GraphML: <a href="read_graphml.html">read_graphml</a> and <a href="write_graphml.html">write_graphml</a></li> 310 </ol></li> 311 312 <LI>Auxiliary Concepts, Classes, and Functions 313 <OL> 314 <LI><a href="./property.html"><tt>property</tt></a> 315 <LI><a href="./ColorValue.html">ColorValue</a> 316 <LI><a href="./Buffer.html">Buffer</a> 317 <LI><a href="./BasicMatrix.html">BasicMatrix</a> 318 <LI><a href="./incident.html"><tt>incident</tt></a> 319 <LI><a href="./opposite.html"><tt>opposite</tt></a> 320 <LI><a href="./random.html">Tools for random graphs</a> 321 <OL> 322 <LI><a href="./random.html#random_vertex">random_vertex</a> 323 <LI><a href="./random.html#random_edge">random_edge</a> 324 <LI><a href="./random.html#generate_random_graph">generate_random_graph</a> 325 <LI><a href="./random.html#randomize_property">randomize_property</a> 326 <li><a href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a></li> 327 <li><a href="sorted_erdos_renyi_gen.html"><tt>sorted_erdos_renyi_iterator</tt></a></li> 328 <li><a href="plod_generator.html"><tt>plod_iterator</tt></a></li> 329 <li><a href="small_world_generator.html"><tt>small_world_iterator</tt></a></li> 330 </OL> 331 </OL> 332 <LI><a href="./challenge.html">Challenge and To-Do List</a> 333 <LI><a href="./trouble_shooting.html">Trouble Shooting</a> 334 <LI><a href="./known_problems.html">Known Problems</a> 335 <LI><a href="./faq.html">FAQ</a> 336 <LI><a href="https://web.archive.org/web/20071012123707/http://siek.info/bgl.html">BGL Book Errata</a> 337 </OL> 338<p> 339 340<a name="*">*</a> Items marked have not yet been documented. 341 342<br> 343<HR> 344<TABLE> 345<TR valign=top> 346<TD nowrap>Copyright © 2000-2001</TD><TD> 347<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 348Indiana University (<A 349HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 350<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br> 351<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 352Indiana University (<A 353HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 354</TD></TR></TABLE> 355 356</BODY> 357</HTML> 358
