4

我有一个控制流图，表示我的中间语言代码的单个过程。节点和边通过顶点/边属性进行注释，并包含指令和分支信息。

现在我想对该图执行数据流分析，并将该图输入每个数据流分析模块。每个模块都应该能够用自己的数据注释 CFG 。
我需要解决的问题：

  • 我不知道数据流分析模块引入了多少注解（因为我以后会实现额外的分析模块）
  • 我对特定数据流分析模块引入的注解类型一无所知
  • 每个数据流分析模块应该独立于其他模块存在，即模块A不应该关心模块B引入的注解

您是否有机会实现上述所有要求？任何意见或建议都非常感谢

更新：
更具体地说，我基本上想将我的注释与 Graph 类型分离。当使用通常的顶点/边属性时，图形类型本身总是被包含的属性类型“污染”（因此取决于顶点/边属性类型）。

4

2 回答 2

3

请参阅 boost 图形库文档的“使用属性映射”一章。尤其是“构建外部属性映射”部分。如果那不能回答您的问题，您能否澄清缺少的内容？

于 2009-07-23T14:12:13.453 回答
3

我不知道将无界属性集与相邻列表相关联的任何标准方法。由于我假设您关心性能，因此我建议采用以下方法。首先，为您要使用的每个属性引入“标记”类型，就像 BGL 所做的那样。这些属性不需要在同一个地方定义——一个实现专门分析的模块可以在它的头文件或源文件中定义一个标签类型。例如：

struct execution_count { typedef int value_type; };

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

然后，创建从相邻列表派生的新图形类型，并添加新方法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);
}

这里的技巧是使用 boost::any 和 type_info 来存储图的任意一组属性映射，而无需提前指定类型。

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

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

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

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

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);
}

您可能还需要一种在边缘上存储属性的方法。然后，像上面一样添加另一个重载。

不幸的是，BGL 不支持边的“自动编号”——但您可以派生adjacency_list并覆盖添加边以填充 edge_index_t 属性的方法。

希望这可以帮助。

注0。我什至没有尝试编译上面的代码。虽然我曾经有一个可行的解决方案，但现在落后了几台计算机。

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

注 2. Deriving fromstd::vector仅用于说明。自己决定这是否是最终解决方案的好主意。

于 2009-07-27T11:17:55.263 回答