- Grasping Graph Theory
- Old and Famous Problems
- Graphs, Computers, and Popular Culture
- Constructing a Simple Graph with Boost
- Adding Values to Vertices and Edges
- Manipulating Property Values
- Adding Vertices and Edges
- Iterating Through the Edges and Vertices
- Solving Problems with Graphs and Boost
- Conclusion
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Constructing a Simple Graph with Boost
If you have to code a graph theory algorithm, you can either build the graph data structures yourself, or use a library. The one I’m using for this article is found in the Boost library. Let’s take a look at a first sample to show you how to use the Boost library’s support for graph theory.
In general, a graph can be represented in a computer as a set of vertices and a set of edges connecting the vertices; the edges are simply pairs of vertices. Further, each vertex and each edge can have additional data attached to it, such as a number representing a weight, in the case of edges. This is essentially how Boost’s Graph library works.
The Boost Graph library exists as templates, which means that you create your own classes and types based on the templates. However, the parameters for the templates all have defaults, so you can create a graph easily without having to do any customization.
Here’s a short piece of code that demonstrates creating a graph and inserting vertices and edges into the graph. This code compiles completely, but it doesn’t really do much other than create the graph:
#include <iostream>
#include <stdlib.h>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
int main(int argc, char *argv[])
{
adjacency_list<> mygraph;
add_edge(1, 2, mygraph);
add_edge(1, 3, mygraph);
add_edge(1, 4, mygraph);
add_edge(2, 4, mygraph);
return 0;
}
The mygraph variable is the graph itself. The type is adjacency_list, which is the fundamental graph template type in the Boost Graph library. I used the defaults for the parameters; thus, the parameters are an empty set with angle brackets (<>).
The add_edge function is a template helper function for adding items to the graph. To use it, you pass the values for two vertices. If the vertices don’t already exist in the graph, they’ll be added; then the edge connecting the two vertices will be added. Thus, the preceding code creates a graph with four vertices, numbered 1, 2, 3, and 4, with edges connecting 1 and 2, 1 and 3, 1 and 4, and finally 2 and 4.
This is just a basic example. To create more complex graphs, you’ll need to define more data to associate with your edges and vertices. I take up that task in the next section.