libs/graph/doc/table_of_contents.html

   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&amp;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 &copy; 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>