Difference between revisions of "Boost/BGL"
From ProgrammingExamples
< Boost
Daviddoria (Talk | contribs) (Created page with ' === Basics === * Create a graph - This is the most fundamental process of using BGL - creating a graph. This example explains 3 methods of creating a g…') |
Daviddoria (Talk | contribs) |
||
| (13 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | |||
=== Basics === | === Basics === | ||
* [[CPP/Boost/CreateGraph|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. | * [[CPP/Boost/CreateGraph|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. | ||
| − | |||
* [[CPP/Boost/BGL/EdgeExists|Check if an edge exists]] - If it does, you also get the edge_descriptor | * [[CPP/Boost/BGL/EdgeExists|Check if an edge exists]] - If it does, you also get the edge_descriptor | ||
* [[CPP/Boost/BGL/CopyAGraph|Copy a graph]] | * [[CPP/Boost/BGL/CopyAGraph|Copy a graph]] | ||
| Line 18: | Line 16: | ||
* [[CPP/Boost/BGL/MakeBFSVisitor|Breadth first search with make_bfs_visitor]] | * [[CPP/Boost/BGL/MakeBFSVisitor|Breadth first search with make_bfs_visitor]] | ||
* [[CPP/Boost/BGL/DepthFirstSearch|Depth first search (DFS)]] | * [[CPP/Boost/BGL/DepthFirstSearch|Depth first search (DFS)]] | ||
| + | |||
| + | === Filtered graphs === | ||
| + | * [[CPP/Boost/BGL/FilteredGraphVertices|Filter a graph's vertices]] | ||
| + | * [[CPP/Boost/BGL/FilteredGraphEdges|Filter a graph's edges]] | ||
| + | |||
| + | === Directed graphs === | ||
| + | * [[CPP/Boost/BGL/Directed/IterateEdges|Iterate over all edges in a directed graph]] | ||
| + | |||
| + | === Undirected graphs === | ||
| + | * [[CPP/Boost/BGL/Undirected/IterateEdges|Iterate over all edges in an undirected graph]] | ||
=== I/O === | === I/O === | ||
| − | * [[ | + | * [[Boost/BGL/IO/ReadGraph|Read a graph from a file]] |
| − | * [[ | + | * [[Boost/BGL/IO/WriteGraph|Write a graph to a file]] |
| − | * [[ | + | * [[Boost/BGL/RelabelInputVertices|Relabel input vertices read from a dot file so they match the labels used in the file]] |
=== Algorithms === | === Algorithms === | ||
| Line 30: | Line 38: | ||
* [[CPP/Boost/BGL/DijkstraComputePath|Find the shortest path (Dijkstra) from one specified vertex to another specified vertex in a graph]] | * [[CPP/Boost/BGL/DijkstraComputePath|Find the shortest path (Dijkstra) from one specified vertex to another specified vertex in a graph]] | ||
* [[CPP/Boost/BGL/BetweennessCentralityClustering|Cluster a graph using betweenness centrality]] | * [[CPP/Boost/BGL/BetweennessCentralityClustering|Cluster a graph using betweenness centrality]] | ||
| + | * [[CPP/Boost/BGL/MaxFlow|Find the max flow of a graph]] | ||
| + | * [[CPP/Boost/BGL/PrimMST|Find the minimum spanning tree of a graph (Prim's algorithm)]] | ||
=== Visualization === | === Visualization === | ||
* [[CPP/Boost/BGL/InvisibleEdges|Create a graph with invisible edges]] | * [[CPP/Boost/BGL/InvisibleEdges|Create a graph with invisible edges]] | ||
| + | |||
| + | === Grid graphs === | ||
| + | |||
| + | * [[CPP/Boost/BGL/GridGraphProperties|Create properties on a grid graph]] | ||
| + | * [[CPP/Boost/BGL/d_ary_heap_indirect|Priority queue that sorts by a property (d_ary_heap_indirect)]] | ||
| + | * [[CPP/Boost/BGL/GridGraphVertexIterator|Grid graph vertex iterator]] | ||
| + | |||
| + | === Utilities === | ||
| + | |||
| + | * [[CPP/Boost/BGL/IndirectPriorityQueue|Priority queue that sorts by a property (d_ary_heap_indirect)]] | ||
Latest revision as of 21:51, 16 November 2016
Contents
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
Directed graphs
Undirected graphs
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 of a graph
- Find the minimum spanning tree of a graph (Prim's algorithm)
Visualization
Grid graphs
- Create properties on a grid graph
- Priority queue that sorts by a property (d_ary_heap_indirect)
- Grid graph vertex iterator
