1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.01 Transitional//EN"
2 "http://www.w3.org/TR/html4/loose.dtd">
5 Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
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)
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"
16 <IMG SRC=
"../../../boost.png"
17 ALT=
"C++ Boost" width=
"277" height=
"86">
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>
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
36 href=
"./using_property_maps.html">Property Maps
</a>
38 href=
"./using_adjacency_list.html">The
<tt>adjacency_list
</tt> class
</a>
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
49 <LI>Extending the Boost Graph Library
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>
54 <LI><A href=
"./graph_concepts.html">The Boost Graph Interface
</A>
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>
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>
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>
81 <li>EventVisitorList Adaptors
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>
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>
103 <LI><A href=
"./adjacency_list.html"><tt>adjacency_list
</tt></a></li>
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>
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>
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>
123 <LI><A href=
"./grid_graph.html">Multi-dimensional grid graph
</A>
126 <LI>Iterator Adaptors
129 href=
"./adjacency_iterator.html"><tt>adjacency_iterator
</tt></a>
131 href=
"./inv_adjacency_iterator.html"><tt>inv_adjacency_iterator
</tt></a>
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>
141 <LI><a href=
"./bgl_named_params.html">Named parameters (used in many graph algorithms)
</a>
144 <LI><A href=
"copy_graph.html"><tt>copy_graph
</tt></A>
145 <LI><A href=
"transpose_graph.html"><tt>transpose_graph
</tt></A>
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>
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>
155 href=
"./undirected_dfs.html"><tt>undirected_dfs
</tt></A>
158 <li>Other Core Algorithms
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>
165 <LI>Shortest Paths / Cost Minimization Algorithms
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>
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>
177 <LI>Minimum Spanning Tree Algorithms
180 href=
"./kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree
</tt></A>
182 href=
"./prim_minimum_spanning_tree.html"><tt>prim_minimum_spanning_tree
</tt></A>
184 <LI>Random Spanning Tree Algorithm
187 href=
"./random_spanning_tree.html"><tt>random_spanning_tree
</tt></A>
189 <LI>Algorithm for Common Spanning Trees of Two Graphs
192 href=
"./two_graphs_common_spanning_trees.html"><tt>two_graphs_common_spanning_trees
</tt></A>
194 <LI>Connected Components Algorithms
196 <LI><A href=
"./connected_components.html"><tt>connected_components
</tt></A>
197 <LI><A href=
"./strong_components.html"><tt>strong_components
</tt></A>
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>
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>
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>
210 <LI>Maximum Flow and Matching Algorithms
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>
217 <LI>Minimum Cost Maximum Flow Algorithms
219 <LI><A href=
"cycle_canceling.html"><tt>cycle_canceling
</tt></A>
220 <LI><A href=
"successive_shortest_path_nonnegative_weights.html"><tt>successive_shortest_path_nonnegative_weights
</tt></A>
221 <li><a href=
"find_flow_cost.html"><tt>find_flow_cost
</tt></a></li>
223 <LI>Minimum Cut Algorithms
225 <LI><A href=
"stoer_wagner_min_cut.html"><tt>stoer_wagner_min_cut
</tt></A>
227 <li>Sparse Matrix Ordering Algorithms
230 href=
"./cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering
</tt></a>
231 <li><a href=
"king_ordering.html"><tt>king_ordering
</tt></a></li>
232 <LI><a href=
"./minimum_degree_ordering.html"><tt>minimum_degree_ordering
</tt></a>
233 <li><a href=
"sloan_ordering.htm"><tt>sloan_ordering
</tt></a></li>
234 <li><a href=
"sloan_start_end_vertices.htm"><tt>sloan_start_end_vertices
</tt></a></li>
239 <LI><A href=
"./wavefront.htm"><tt>ith_wavefront
</tt>,
<tt>max_wavefront
</tt>,
<tt>aver_wavefront
</tt>, and
<tt>rms_wavefront
</tt></A></LI>
240 <LI><a href=
"./bandwidth.html#sec:bandwidth"><tt>bandwidth
</tt></a>
241 <LI><a href=
"./bandwidth.html#sec:ith-bandwidth"><tt>ith_bandwidth
</tt></a>
242 <LI><A href=
"betweenness_centrality.html"><tt>brandes_betweenness_centrality
</tt></A></LI>
243 <li><a href=
"howard_cycle_ratio.html"><tt>minimum_cycle_ratio
</tt> and
<tt>maximum_cycle_ratio
</tt></a></li>
246 <li>Graph Structure Comparisons
248 <LI><A href=
"isomorphism.html"><tt>isomorphism
</tt></A>
249 <LI><A href=
"vf2_sub_graph_iso.html"><tt>vf2_sub_graph_iso
</tt> (VF2 subgraph isomorphism algorithm)
</A>
250 <li><a href=
"mcgregor_common_subgraphs.html"><tt>mcgregor_common_subgraphs
</tt></a></li>
253 <li>Layout Algorithms
255 <li><a href=
"topology.html">Topologies used as spaces for graph drawing
</a></li>
256 <li><a href=
"random_layout.html"><tt>random_graph_layout
</tt></a></li>
257 <li><a href=
"circle_layout.html"><tt>circle_layout
</tt></a></li>
258 <li><a href=
"kamada_kawai_spring_layout.html"><tt>kamada_kawai_spring_layout
</tt></a></li>
259 <li><a href=
"fruchterman_reingold.html"><tt>fruchterman_reingold_force_directed_layout
</tt></a></li>
260 <li><a href=
"gursoy_atun_layout.html"><tt>gursoy_atun_layout
</tt></a></li>
263 <li>Clustering algorithms
265 <li><a href=
"bc_clustering.html"><tt>betweenness_centrality_clustering
</tt></a></li>
268 <li><a href=
"planar_graphs.html">Planar Graph Algorithms
</a>
270 <li><a href=
"boyer_myrvold.html">
271 <tt>boyer_myrvold_planarity_test
</tt></a>
272 <li><a href=
"planar_face_traversal.html">
273 <tt>planar_face_traversal
</tt></a>
274 <li><a href=
"planar_canonical_ordering.html">
275 <tt>planar_canonical_ordering
</tt></a>
276 <li><a href=
"straight_line_drawing.html">
277 <tt>chrobak_payne_straight_line_drawing
</tt></a>
278 <li><a href=
"is_straight_line_drawing.html">
279 <tt>is_straight_line_drawing
</tt></a>
280 <li><a href=
"is_kuratowski_subgraph.html">
281 <tt>is_kuratowski_subgraph
</tt></a>
282 <li><a href=
"make_connected.html">
283 <tt>make_connected
</tt></a>
284 <li><a href=
"make_biconnected_planar.html">
285 <tt>make_biconnected_planar
</tt></a>
286 <li><a href=
"make_maximal_planar.html">
287 <tt>make_maximal_planar
</tt></a>
290 <li>Miscellaneous Algorithms
292 <li><a href=
"metric_tsp_approx.html"><tt>metric_tsp_approx
</tt></a></li>
293 <LI><A href=
"sequential_vertex_coloring.html"><tt>sequential_vertex_coloring
</tt></A></li>
294 <LI><A href=
"edge_coloring.html"><tt>edge_coloring
</tt></A></li>
295 <LI><A href=
"is_bipartite.html"><tt>is_bipartite
</tt></A> (including two-coloring of bipartite graphs)
</li>
296 <LI><A href=
"find_odd_cycle.html"><tt>find_odd_cycle
</tt></A></li>
297 <LI><A href=
"maximum_adjacency_search.html"><tt>maximum_adjacency_search
</tt></A></li>
298 <LI><A href=
"hawick_circuits.html"><tt>hawick_circuits
</tt></A> (find all circuits of a directed graph)
</li>
304 <li>Graph Input/Output
306 <li>AT
&T Graphviz:
<a href=
"read_graphviz.html">read_graphviz
</a>,
<a href=
"./write-graphviz.html">write_graphviz
</a></li>
307 <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>
308 <li>GraphML:
<a href=
"read_graphml.html">read_graphml
</a> and
<a href=
"write_graphml.html">write_graphml
</a></li>
311 <LI>Auxiliary Concepts, Classes, and Functions
313 <LI><a href=
"./property.html"><tt>property
</tt></a>
314 <LI><a href=
"./ColorValue.html">ColorValue
</a>
315 <LI><a href=
"./Buffer.html">Buffer
</a>
316 <LI><a href=
"./BasicMatrix.html">BasicMatrix
</a>
317 <LI><a href=
"./incident.html"><tt>incident
</tt></a>
318 <LI><a href=
"./opposite.html"><tt>opposite
</tt></a>
319 <LI><a href=
"./random.html">Tools for random graphs
</a>
321 <LI><a href=
"./random.html#random_vertex">random_vertex
</a>
322 <LI><a href=
"./random.html#random_edge">random_edge
</a>
323 <LI><a href=
"./random.html#generate_random_graph">generate_random_graph
</a>
324 <LI><a href=
"./random.html#randomize_property">randomize_property
</a>
325 <li><a href=
"erdos_renyi_generator.html"><tt>erdos_renyi_iterator
</tt></a></li>
326 <li><a href=
"sorted_erdos_renyi_gen.html"><tt>sorted_erdos_renyi_iterator
</tt></a></li>
327 <li><a href=
"plod_generator.html"><tt>plod_iterator
</tt></a></li>
328 <li><a href=
"small_world_generator.html"><tt>small_world_iterator
</tt></a></li>
331 <LI><a href=
"./challenge.html">Challenge and To-Do List
</a>
332 <LI><a href=
"./trouble_shooting.html">Trouble Shooting
</a>
333 <LI><a href=
"./known_problems.html">Known Problems
</a>
334 <LI><a href=
"./faq.html">FAQ
</a>
335 <LI><a href=
"http://siek.info/bgl.html">BGL Book Errata
</a>
339 <a name=
"*">*
</a> Items marked have not yet been documented.
345 <TD nowrap
>Copyright
© 2000-
2001</TD><TD>
346 <A HREF=
"http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek
</A>,
347 Indiana University (
<A
348 HREF=
"mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu
</A>)
<br>
349 <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>
350 <A HREF=
"http://www.osl.iu.edu/~lums">Andrew Lumsdaine
</A>,
351 Indiana University (
<A
352 HREF=
"mailto:lums@osl.iu.edu">lums@osl.iu.edu
</A>)