- 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
Adding Values to Vertices and Edges
When you use a graph, normally you’ll want to associate information with the vertices and edges. The Graph library uses an interesting approach for this goal. Items such as names or colors are stored in properties, which consist of a name (or tag) such as distance or name, and a type such as float or string. You can add properties to both vertices and edges.
BOOST_DEF_PROPERTY(edge, name);
When you define a graph, you can specify the types of properties associated with the graph. You can add as many properties as you want to vertices and edges. To define properties, first you create a template type for each property type, and then you define the graph type before you instantiate the graph. For example, suppose you want to attach a distance to each edge, and a city name to each vertex. Here’s the code to define the two property types:
typedef property<edge_weight_t, int> EdgeWeightProperty; typedef property<vertex_name_t, std::string> VertexNameProperty;
The first line defines the EdgeWeightProperty type. The first parameter to the template is the tag for the property. I’m using one of the predefined tags, edge_weight_t, which means edge weight. The second parameter is int, meaning this property will hold an integer. The second line defines the second property; the tag is vertex_name_t, and the type is string.
Now that you have the property types defined, you can define a graph type:
typedef adjacency_list<vecS, vecS, undirectedS, VertexNameProperty, EdgeWeightProperty> Graph;
I’m using three predefined values for the first three parameters. The first and second parameters (vecS in both cases) indicate that I want the graph to use vectors for its internal storage, and the third parameter (undirectedS) says that I want an undirected graph. The fourth and fifth parameters (VertexNameProperty, EdgeWeightProperty, respectively) are the property types that I just defined, with the vertex type first, followed by the edge type.
At this point, you might wonder how you can specify more than one type of property for the edges and vertices. Here’s how: Chain the properties together. The basic property template includes a parameter that can contain a property you already defined. Here’s the vertex property definition again, but this time I’m defining two properties for vertex, a name and an index (using the predefined tag vertex_index2_t):
typedef property<vertex_index2_t, int> VertexIndexProperty; typedef property<vertex_name_t, std::string, VertexIndexProperty> VertexNameProperty;
I’ve defined the index first, but the order really doesn’t matter. The VertexNameProperty contains the VertexIndexProperty as its third parameter, thus creating a chain. You then pass the VertexNameProperty type to the fourth parameter of the graph definition, as before.
You also can condense your code a bit. This code is a bit less readable to somebody who is new to the Graph library, although once you understand the property mechanism it’s pretty straightforward:
typedef property<vertex_name_t, std::string, property<vertex_index2_t, int> > VertexProperties;
I renamed the type VertexProperties, since it now contains two different properties. Also, notice the standard required space between the closing angle brackets, which is always needed in C++ so the parser doesn’t think it’s an insertion operator (>>). Don’t forget that space, or you’ll end up with compilation errors.