]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | </OL> | |
217 | <LI>Minimum Cost Maximum Flow Algorithms | |
218 | <OL> | |
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> | |
222 | </OL> | |
223 | <LI>Minimum Cut Algorithms | |
224 | <OL> | |
225 | <LI><A href="stoer_wagner_min_cut.html"><tt>stoer_wagner_min_cut</tt></A> | |
226 | </OL> | |
227 | <li>Sparse Matrix Ordering Algorithms | |
228 | <ol> | |
229 | <LI><A | |
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> | |
235 | </ol> | |
236 | </li> | |
237 | <li>Graph Metrics | |
238 | <ol> | |
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> | |
244 | </ol> | |
245 | </li> | |
246 | <li>Graph Structure Comparisons | |
247 | <ol> | |
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> | |
251 | </ol> | |
252 | ||
253 | <li>Layout Algorithms | |
254 | <ol> | |
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> | |
261 | </ol> | |
262 | </li> | |
263 | <li>Clustering algorithms | |
264 | <ol> | |
265 | <li><a href="bc_clustering.html"><tt>betweenness_centrality_clustering</tt></a></li> | |
266 | </ol> | |
267 | </li> | |
268 | <li><a href="planar_graphs.html">Planar Graph Algorithms</a> | |
269 | <ol> | |
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> | |
288 | </ol> | |
289 | ||
290 | <li>Miscellaneous Algorithms | |
291 | <ol> | |
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> | |
299 | </ol> | |
300 | </li> | |
301 | ||
302 | </OL> | |
303 | ||
304 | <li>Graph Input/Output | |
305 | <ol> | |
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> | |
309 | </ol></li> | |
310 | ||
311 | <LI>Auxiliary Concepts, Classes, and Functions | |
312 | <OL> | |
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> | |
320 | <OL> | |
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> | |
329 | </OL> | |
330 | </OL> | |
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> | |
336 | </OL> | |
337 | <p> | |
338 | ||
339 | <a name="*">*</a> Items marked have not yet been documented. | |
340 | ||
341 | <br> | |
342 | <HR> | |
343 | <TABLE> | |
344 | <TR valign=top> | |
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>) | |
353 | </TD></TR></TABLE> | |
354 | ||
355 | </BODY> | |
356 | </HTML> |