This chapter is from the book
This chapter is from the book
This chapter is from the book
3.6 Graph Setup: Internal Properties
Before addressing the next question about file dependencies, we are going to take some time out to switch to a different graph type. In the previous sections we used arrays to store information such as vertex names. When vertex or edge properties have the same lifetime as the graph object, it can be more convenient to have the properties somehow embedded in the graph itself (we call these internal properties). If you were writing your own graph class you might add data members for these properties to a vertex or edge struct.
The adjacency_list class has template parameters that allow arbitrary properties to be attached to the vertices and edge: the VertexProperties and EdgeProperties parameters. These template parameters expect the argument types to be the property<Tag, T> class, where Tag is a type that specifies the property and T gives the type of the property object. There are a number of predefined property tags (see §15.2.3) such as vertex_name t and edge_weight t. For example, to attach a std::string to each vertex use the following property type:
property<vertex name_t, std::string>
If the predefined property tags do not meet your needs, you can create a new one. One way to do this is to define an enumerated type named vertex_xxx_t or edge_xxx t that contains an enum value with the same name minus the t and give the enum value a unique number. Then use BOOST_INSTALL_PROPERTY to create the required specializations of the property_kind and property_num traits classes.1 Here we create compile-time cost property that we will use in the next section to compute the total compile time.
namespace boost {
enum vertex_compile_cost_t { vertex_compile_cost = 111 };
// a unique #
BOOST_INSTALL_PROPERTY(vertex, compile_cost);
}
The property class has an optional third parameter that can be used to nest multiple property classes thereby attaching multiple properties to each vertex or edge. Here we create a new typedef for the graph, this time adding two vertex properties and an edge property.
typedef adjacency_list<
listS, // Store out-edges of each vertex in a std::list
listS, // Store vertex set in a std::list
directedS, // The file dependency graph is directed
// vertex properties
property<vertex name_t, std::string,
property<vertex compile cost_t, float,
property<vertex distance_t, float,
property<vertex_color_t, default_color_type> > > >,
// an edge property
property<edge_weight_t, float>
> file_dep_graph2;
We have also changed the second template argument to adjacency_list from vecS to listS. This has some important implications. If we were to remove a vertex from the graph it would happen in constant time (with vecS the vertex removal time is linear in the number of vertices and edges). On the down side, the vertex descriptor type is no longer an integer, so storing properties in arrays and using the vertex as an offset will no longer work. However, the separate storage is no longer needed because we now have the vertex properties stored in the graph.
In §1.2.2 we introduced the notion of a property map. To review, a property map is an object that can be used to map from a key (such as a vertex) to a value (such as a vertex name). When properties have been specified for an adjacency_list (as we have just done), property maps for these properties can be obtained using the PropertyGraph interface. The following code shows an example of obtaining two property maps: one for vertex names and another for compile-time cost. The property_map traits class provides the type of the property map.
typedef property_map<file_dep_graph2, vertex_name_t>::type name_map_t;
typedef property_map<file_dep_graph2, vertex_compile_cost_t>::type
compile_cost_map_t;
typedef property_map<file_dep_graph2, vertex_distance_t>::type
distance_map_t;
typedef property_map<file_dep_graph2, vertex_color_t>::type
color_map_t;
The get() function returns a property map object.
Name_map_t name_map = get(vertex_name, g); Compile_cost_map_t compile_cost_map = get(vertex_compile_cost, g); Distance_map_t distance_map = get(vertex_distance, g); Color_map_t color_map = get(vertex_color, g);
There will be another file containing the estimated compile time for each makefile target. We read this file using a std::ifstream and write the properties into the graph using the property maps, name_map and compile_cost_map. These property maps are models of LvalueProper-tyMap so they have an operator[]() that maps from vertex descriptors to a reference to the appriopriate vertex property object.
std::ifstream name_in("makefile-target-names.dat");
std::ifstream compile_cost_in("target-compile-costs.dat");
graph_traits<file_dep_graph2>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
name_in >> name_map[*vi];
compile_cost_in >> compile_cost_map[*vi];
}
In the following sections we will modify the topological sort and DFS functions to use the property map interface to access vertex properties instead of hard-coding access with a pointer to an array.