使用Boost创建可注释的控制流程图？

Question

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

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

• 我不知道数据流分析模块会引入多少注释（因为我将来还要实现其他分析模块）
• 我不了解特定数据流分析模块引入的注释类型
• 每个数据流分析模块应独立存在，即模块A不应关心模块B引入的注释

您能否看到实现所有上述要求的机会？非常感谢您的任何评论或建议。

更新： 更具体地说，我基本上想将我的注释从图形类型中解耦出来。当使用通常的顶点/边缘属性时，图形类型本身总是被所包含的属性类型“污染”（因此依赖于顶点/边缘属性类型）。

- newgre

---

你的问题原始版本提到了你拥有的GraphProperty类。那个类是否已经处理存储不同类型的任意注释集合？我需要了解这一点，以便确定你需要多详细的答案。 - Vladimir Prus

我从帖子中删除了我的Graph便利类，因为我认为它会让人们感到困惑。我有这个图形便利类，它存储一些永远不会改变的属性。注释旨在存储信息，这些信息对于每个数据流模块都是独特的。这就是为什么我想要解耦这些信息的原因。 - newgre

Answer 1

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

struct execution_count { typedef int value_type; };

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

然后，创建从 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);
}

这里的技巧是使用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.从std::vector派生仅用于阐述。请自行决定是否将其用于最终解决方案。

- Vladimir Prus

---

总的来说，我喜欢你的解决方案，但我不确定如何处理你答案中注释1描述的问题。还有更具体的想法吗？ - newgre

struct type_info_ptr_compare { bool operator()(const std::type_info* p1, const std::type_info* p2) { return p1->before(*p2); } };std::map<type_info*, boost::any, type_info_ptr_compare> dynamic_properties_.请注意，原始代码中有一个从type_info映射的错误。这是个错误，因为type_info不可复制，所以你需要从type_info*映射。 - Vladimir Prus

Answer 2

请查看boost图形库文档中的“使用属性映射”章节，特别是“构建外部属性映射”的部分。如果这无法回答您的问题，请说明缺少什么信息。

- AProgrammer

---

你是否有一个使用外部属性映射和简单图形的示例？Boost文档对此似乎相当模糊。 - newgre