我不知道任何将无限集合的属性与邻接表关联的标准方法。由于我假设您关心性能,因此建议采用以下方法。首先,为要使用的每个属性引入“标记”类型,就像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_ , 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
派生仅用于阐述。请自行决定是否将其用于最终解决方案。