Annotatable Control Flow Graph with Boost?

Question

I have a control flow graph representing a single procedure of my intermediate language code. Nodes and Edges are annotated via vertex/edge properties and contain instructions resp branch information.

Now I want to perform data flow analysis on this graph and feed that graph into each data flow analysis module. Each module should be able to annotate the CFG with its own data.
Problems I need to solve:

• I don't know upfront how many annotations are introduced by the data flow analysis modules (because I will implement additional analysis modules in the future)
• I don't know anything about the type of annotation introduced by a specific data flow analysis module
• Each data flow analysis module should exist independently from the other modules, i.e. module A shouldn't be concerned about the annotations introduced by module B

Do you see any chance to realize all of the above requirements? Any comments or advises are highly appreciated

Update:
To be more specific, I basically want to decouple my annotations from the Graph type. When using the usual vertex/edge properties the Graph type itself is always "polluted" (and is therefore dependent on the vertex/edge property types) by the contained property types.

Answer 1

See the "Using Property Maps" chapter of the documentation of the boost graph library. Especially the "Constructing an Exterior Property Map" section. If that doesn't answer your question, could you clarify what is missing?

Answer 2

I don't know any standard way to associate unbounded set of properties to an adjacenty_list. Since I assume you care about performance, I'd suggest the following approach. First, instroduce 'tag' types for every property you want to use, much like BGL does. The properties need not be defined in the same place -- a module implementing specialized analysis can define a tag type in it's header or source file. For example:

struct execution_count { typedef int value_type; };

The value_type typedef should give the type of value the property has.

Then, create new graph type derived from adjacently_list, and add new method, get_dynamic_property_map. This method will return a property map for a specific custom property. The class dynamic_property_map will be explained later. It is assumed that your algorithm call this method on start, and this method need not be very fast.

std::map<std::type_info, boost::any> dynamic_properties_;
template<class Property>
dynamic_property_map<typename Property::value_type>
get_dynamic_property_map()
{
    typedef typename Property::value_type V;
    if (!dynamic_properties_.count(typeid(Property))
        dynamic_properties_.insert(make_pair(typeid(Property),
            new dynamic_property_map<V>();
    boost::any a = dynamic_properties_[typeid(Property)];
    return *boost::any_cast<dynamic_property_map<V>*>(a);
}

The trick here is to use boost::any and type_info to store arbitrary set of property maps for a graph, without specifying the types in advance.

The dynamic_property_map class takes a vertex and returns the value, and in the simplest form can be:

template<class T>
class dynamic_property_map : public std::vector<T> {};

This assumes that (1) vertex_descriptor is integer and (2) you don't add new vertices after map is created. If you add new vertices, then you should override operator[] to check if the index is beyond the end. If so, resize the vector.

If vertex_descriptor is not integer, you need more coding. The dynamic_property_map should also has graph type as template parameter, and should also hold a reference to the graph. The get_dynamic_property_map will have to be adjusted. The operator[] will have to do this:

template<class V, class G>
V& dynamic_property_map<V, G>::operator[](
      typename graph_traits<G>::vertex_descriptor v)
{
    int index = get(vertex_index_t, g_ /* member referring to graph */, v);
    return std::vector<V>::operator[](index);
}

You probably need a way to store properties on edges too. Then, add another overload like above.

Unfortunately, BGL does not support 'autonumbering' of edges -- but you can derive from adjacency_list and override methods that add edges to fill in edge_index_t property.

Hope this helps.

Note 0. I did not even try to compile the above code. While I had a working solution once, it's now several computers behind.

Note 1. Map from type_info won't actually work, as type_info does not define operator<. You can key define such operator yourself, or put result of type_info::name into the map -- which is technically less reliable.

Note 2. Deriving from std::vector is used for exposition only. Decide yourself if that's a good idea for final solution.