带Boost的可注释控制流程图？

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:

现在,我想在此图表上执行数据流分析,并将该图表提供给每个数据流分析模块。每个模块都应该能够使用自己的数据注释CFG。我需要解决的问题:

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

每个数据流分析模块应独立于其他模块存在,即模块A不应关注模块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.

更新:更具体地说,我基本上想要将我的注释与Graph类型分离。使用通常的顶点/边缘属性时,Graph类型本身始终被包含的属性类型“污染”(因此依赖于顶点/边属性类型)。

2 个解决方案

#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?

请参阅boost图库文档的“使用属性映射”一章。特别是“建设外部物业地图”部分。如果这不能回答你的问题,你能澄清一下缺少什么吗?

#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:

我不知道将*属性集关联到adjacenty_list的任何标准方法。由于我假设你关心性能,我建议采用以下方法。首先,为每个要使用的属性引入“标记”类型,就像BGL一样。不需要在同一个地方定义属性 - 实现专门分析的模块可以在其头文件或源文件中定义标签类型。例如:

struct execution_count { typedef int value_type; };

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

value_type typedef应该给出属性具有的值的类型。

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.

然后,创建从adjacently_list派生的新图类型,并添加新方法get_dynamic_property_map。此方法将返回特定自定义属性的属性映射。稍后将解释类dynamic_property_map。假设您的算法在启动时调用此方法,并且此方法不需要非常快。

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.

这里的技巧是使用boost :: any和type_info来存储图形的任意属性映射集,而不预先指定类型。

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

dynamic_property_map类接受一个顶点并返回该值,最简单的形式可以是:

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.

这假设(1)vertex_descriptor是整数,(2)在创建地图后不添加新顶点。如果添加新顶点,则应覆盖operator []以检查索引是否超出结束。如果是这样,请调整矢量大小。

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:

如果vertex_descriptor不是整数,则需要更多编码。 dynamic_property_map还应该具有图形类型作为模板参数,并且还应该包含对图形的引用。必须调整get_dynamic_property_map。运营商[]必须这样做:

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.

遗憾的是,BGL不支持边缘的“自动编号” - 但您可以从adjacency_list派生并覆盖添加边以填充edge_index_t属性的方法。

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.

注意0.我甚至没有尝试编译上面的代码。虽然我有一次工作解决方案,但现在有几台计算机落后了。

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.

注意1. type_info中的映射实际上不起作用,因为type_info没有定义operator <。您可以自己键定义这样的运算符,或者将type_info :: name的结果放入映射中 - 这在技术上不太可靠。

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

注2.从std :: vector派生仅用于展示。如果这对最终解决方案来说是个好主意,请确定自己。

#1