Table of Contents: the Boost Graph Library

1. Introduction to the BGL

2. Parallel BGL (distributed-memory parallel graph data structures and algorithms)

3. History

4. List of BGL Users

5. Publications

6. Acknowledgements

7. A Quick Tour of the Boost Graph Library.

8. Review of Elementary Graph Theory

9. Boost Graph Library Tutorial

10. Property Maps

11. The adjacency_list class

12. Examples

13. File Dependency Example

14. Six Degrees of Kevin Bacon

15. Graph Coloring

16. Sparse Matrix Ordering

17. Extending the Boost Graph Library

18. Constructing graph algorithms with BGL

19. Converting Existing Graphs to BGL

20. The Boost Graph Interface

21. Graph

22. Incidence Graph

23. Bidirectional Graph

24. Adjacency Graph

25. Vertex List Graph

26. Edge List Graph

27. Vertex and Edge List Graph

28. Adjacency Matrix

29. Mutable Graph

30. Property Graph

31. Mutable Property Graph

32. The Property Map Library (technically not part of the graph library, but used a lot here)

33. Python bindings

34. Visitor Concepts

35. BFS Visitor

36. DFS Visitor

37. Dijkstra Visitor

38. Bellman Ford Visitor

39. A* Visitor

40. Event Visitor

41. Planar Face Visitor

42. TSP Tour Visitor

43. EventVisitorList Adaptors

44. Event Visitor List

45. bfs_visitor

46. dfs_visitor

47. dijkstra_visitor

48. bellman_visitor

49. astar_visitor

50. Event Visitors

51. predecessor_recorder

52. edge_predecessor_recorder

53. distance_recorder

54. time_stamper

55. property_writer

56. property_put

57. tsp_tour_visitor

58. tsp_tour_len_visitor

59. Graph classes

60. adjacency_list

1. [directed\_graph](./directed_graph.html)

2. [undirected\_graph](./undirected_graph.html)

2. adjacency_matrix 3. compressed_sparse_row_graph

19. Graph Adaptors

20. subgraph

21. edge_list

22. reverse_graph

23. filtered_graph

24. Vector as Graph*

25. Matrix as Graph*

26. Leda Graph*

27. Stanford GraphBase

28. Implicit Graphs 1. Multi-dimensional grid graph

29. Iterator Adaptors

30. adjacency_iterator

31. inv_adjacency_iterator

32. Traits classes

33. graph_traits

34. adjacency_list_traits

35. property_map

36. Algorithms

37. Named parameters (used in many graph algorithms)

38. Basic Operations 1. copy_graph 2. transpose_graph

39. Core Searches 1. breadth_first_search 2. breadth_first_visit 3. depth_first_search 4. depth_first_visit 5. undirected_dfs

40. Other Core Algorithms 1. topological_sort 2. transitive_closure 3. lengauer_tarjan_dominator_tree

41. Shortest Paths / Cost Minimization Algorithms 1. dijkstra_shortest_paths 2. dijkstra_shortest_paths_no_color_map 3. bellman_ford_shortest_paths 4. dag_shortest_paths 5. johnson_all_pairs_shortest_paths 6. floyd_warshall_all_pairs_shortest_paths 7. r_c_shortest_paths - resource-constrained shortest paths 8. astar_search (A* search algorithm)

42. Minimum Spanning Tree Algorithms 1. kruskal_minimum_spanning_tree 2. prim_minimum_spanning_tree

43. Random Spanning Tree Algorithm 1. random_spanning_tree

44. Algorithm for Common Spanning Trees of Two Graphs 1. two_graphs_common_spanning_trees

45. Connected Components Algorithms 1. connected_components 2. strong_components 3. biconnected_components 4. articulation_points 5. Incremental Connected Components

    1. initialize_incremental_components
    2. incremental_components
    3. same_component
    4. component_index

46. Maximum Flow and Matching Algorithms 1. edmonds_karp_max_flow 2. push_relabel_max_flow 3. boykov_kolmogorov_max_flow 4. edmonds_maximum_cardinality_matching 5. maximum_weighted_matching

47. Minimum Cost Maximum Flow Algorithms 1. cycle_canceling 2. successive_shortest_path_nonnegative_weights 3. find_flow_cost

48. Minimum Cut Algorithms 1. stoer_wagner_min_cut

49. Sparse Matrix Ordering Algorithms 1. cuthill_mckee_ordering 2. king_ordering 3. minimum_degree_ordering 4. sloan_ordering 5. sloan_start_end_vertices

50. Graph Metrics 1. ith_wavefront, max_wavefront, aver_wavefront, and rms_wavefront 2. bandwidth 3. ith_bandwidth 4. brandes_betweenness_centrality 5. minimum_cycle_ratio and maximum_cycle_ratio

51. Graph Structure Comparisons 1. isomorphism 2. vf2_sub_graph_iso (VF2 subgraph isomorphism algorithm) 3. mcgregor_common_subgraphs

52. Layout Algorithms 1. Topologies used as spaces for graph drawing 2. random_graph_layout 3. circle_layout 4. kamada_kawai_spring_layout 5. fruchterman_reingold_force_directed_layout 6. gursoy_atun_layout

53. Clustering algorithms 1. betweenness_centrality_clustering

54. Planar Graph Algorithms 1. boyer_myrvold_planarity_test 2. planar_face_traversal 3. planar_canonical_ordering 4. chrobak_payne_straight_line_drawing 5. is_straight_line_drawing 6. is_kuratowski_subgraph 7. make_connected 8. make_biconnected_planar 9. make_maximal_planar

55. Miscellaneous Algorithms 1. metric_tsp_approx 2. sequential_vertex_coloring 3. edge_coloring 4. is_bipartite (including two-coloring of bipartite graphs) 5. find_odd_cycle 6. maximum_adjacency_search 7. hawick_circuits (find all circuits of a directed graph)

56. Graph Input/Output

57. AT&T Graphviz: read_graphviz, write_graphviz

58. DIMACS Max-flow: read_dimacs_max_flow and read_dimacs_min_cut, write_dimacs_max_flow

59. GraphML: read_graphml and write_graphml

60. Auxiliary Concepts, Classes, and Functions

61. property

62. ColorValue

63. Buffer

64. BasicMatrix

65. incident

66. opposite

67. Tools for random graphs 1. random_vertex 2. random_edge 3. generate_random_graph 4. randomize_property 5. erdos_renyi_iterator 6. sorted_erdos_renyi_iterator 7. plod_iterator 8. small_world_iterator

68. Challenge and To-Do List

69. Trouble Shooting

70. Known Problems

71. FAQ

72. BGL Book Errata

* Items marked have not yet been documented.

| Copyright © 2000-2001 | Jeremy Siek, Indiana University ([email protected])
Lie-Quan Lee, Indiana University ([email protected])
Andrew Lumsdaine, Indiana University ([email protected]) |