Difference between revisions of "Boost/BGL"

Revision as of 10:41, 3 September 2012

Basics

• Create a graph - This is the most fundamental process of using BGL - creating a graph. This example explains 3 methods of creating a graph, using adjacency_list directly, and also using the directed_graph and undirected_graph subclasses.
• Check if an edge exists - If it does, you also get the edge_descriptor
• Copy a graph
• Access an edge
• Remove a vertex from a graph
• Remove an edge from a graph
• Add properties to edges
• Add properties to vertices
• Bundled properties
• Get a list of neighboring (adjacent) vertices
• Directed graphs only give access to out edges
• Bidirectional graphs give access to both in and out edges
• Number of incoming, outgoing, and total edges
• Breadth first search (BFS with a custom visitor)
• Breadth first search with make_bfs_visitor
• Depth first search (DFS)

Filtered graphs

• Filter a graph's vertices
• Filter a graph's edges

Directed graphs

• Iterate over all edges in a directed graph

Undirected graphs

• Iterate over all edges in an undirected graph

I/O

• Read a graph from a file
• Write a graph to a file
• Relabel input vertices read from a dot file so they match the labels used in the file

Algorithms

• Find the shortest path (Dijkstra) from a specified vertex to all other vertices in a directed graph
• Find the shortest path (Dijkstra) from a specified vertex to all other vertices in an undirected graph
• Find the shortest path (Dijkstra) from one specified vertex to another specified vertex in a graph
• Cluster a graph using betweenness centrality
• Find the max flow (a path) between a source and sink node.

Visualization

• Create a graph with invisible edges

Grid graphs

• Create properties on a grid graph
• Priority queue that sorts by a property (d_ary_heap_indirect)
• Grid graph vertex iterator

Utilities

• Priority queue that sorts by a property (d_ary_heap_indirect)