首页 文章

将boost图中的内部属性转换为boost图中的外部属性容器

提问于
浏览 次
0

参考我的问题enter link description here中提到的代码，我想转换内部属性

struct NodeInfo {  int a , b , c; }; 
 struct EdgeInfo {  int timestamp; ... };
 struct NodeInfoPropertyTag {          // tag and kind  (as in boost documentation)
  typedef boost::vertex_property_tag kind;
  static  std::size_t const num;
 };

std :: size_t const NodeInfoPropertyTag :: num =（std :: size_t）＆NodeInfoPropertyTag :: num;

我想将这些属性用作外部图形属性 . 所以我的图表会变成类似的东西

typedef boost::adjacency_list <vecS, vecS, undirectedS, no_property, no_property>   Graph_t;

在前面的代码中，定义了property_maps，初始化了graph，并且为了修改顶点或边缘属性，我使用标记类来标识每个顶点或边缘并使用它：

//get
   NodInfo   info  =  boost::get (NodeInfoPropertyTag(), G, v) 

   //put 
    put (NodeInfoPropertyTag(), G, v, info)

现在，我想将这些NodeInfo和EdgeInfo作为外部属性：for_each（vertex）：将每个顶点的属性存储在一个向量中（比方说）for_each（edge）：将每个边的属性存储在一个向量中（比如说）

我在stackoverflow上看到了类似的问题，用于添加/修改外部属性，但遗憾的是无法让它满足我的要求 .

我根据code中建议的解决方案编写了一个迭代器属性映射 . 我也可以使用get（）和put（）函数：HERE

我想编写自己的get（）和put（）函数（在我自己的命名空间中）而不是调用boost :: get（）和boost :: put（）但是我需要我的实现与boost的相同:: get（）和put（）：

ie.
using namespace my_space {
  template <typename tag_t, typename graph_t, typename key_t, typename value_t>
  value_t get (tag_t tag, graph_t& G, key_t& key) {
  //TODO
  //return  from external property map  -->  vector map 
  }

  template <typename tag_t, typename graph_t, typename key_t, typename value_t>
  void put (tag_t& tag, graph_t&G, key_t& key, value_t& value) {
   //TODO
   // put in external property map
  }
  • 不知何故，我需要一种机制来使用Tag_type和graph_t，它将为我提供实际的外部属性映射 . 即：

//当我使用它时，NodeInfo ninfo = my_space :: get（my_vertex_tag，G，v）; --->

//它应该从我的命名空间调用get（）并返回外部容器的内容

put（my_edge_tag，G，key，value） - >调用我实现的put， - >插入或修改带有index = key的edge e的vector中的属性（我不知道如何将每个edge_descriptor链接到唯一的edge_index但我正在努力）

我阅读了文档，但不知何故，我无法将内部属性链接到外部属性 . 迭代器属性映射有什么替代方法吗？我可以使用关联属性映射在外部存储vertex_properties吗？我唯一的要求是：我想使用标签和图形G作为get（）和put（）的参数 . 可以有多个标记及其对应的外部属性容器，并且get（）和put（）调用应解析为该特定容器 . 我可以使用get（）和put（）的模板专门化吗？我不太确定该怎么做

原因：减少Graph对象G的大小（因为数百万个边和节点）图存储/序列化比较容易 .

如果问题不明确，请告诉我

c++ c++11 boost boost-graph

1 回答

  • 1

    我能看到的最佳解决方案是使用迭代器属性映射，然后在访问它时锁定 .

    您将需要映射到顶点索引和容器，然后您将创建外部属性映射 .

    //typedef an index map for vertex
typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;

//Get the actual graph's vertex indexmap
VertexIndexMap vertexIndexMap = get(boost::vertex_index, G);

//Create a container with size equal to verts in G
vector<double> vertexWeights(num_vertices(G));

//Create the property map
boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
    vertexWeightMap(vertexWeights.begin(), vertexIndexMap);

    这将创建一个iterator_property_map . 这并不意味着使用迭代器的性能 . 它将vertex_descriptor映射到容器中的迭代器（offset） . 我相信它使用unordered_map，因此映射是O（1）常量时间 .

    这是我经常用来包装容器以与boost图一起使用的方法 .

    要确保此容器已同步，您应使用互斥锁锁定对该容器的访问 . 使用互斥锁检查 . http://www.boost.org/doc/libs/1_55_0/doc/html/thread/synchronization.html

    或者如果您正在使用TBB，正如您在另一个问题中提到的那样，我确信TBB将拥有自己的互斥锁，它们可能更适合您的线程 .

    最后考虑一下为什么要这样做 . 您需要容器才能使用boost标签 . 为什么？可能要利用一些内置的boost算法 . 这没关系，但我不认为你会通过使用线程而不费力而从增强图算法中挤出任何额外的性能 . 在没有大量精力和通信开销的情况下，很难加速规范图算法（最短路径，最小生成树，BFS，DFS） . 如果你想加速像Betweenness或Dijkstra这样的东西，可以使用更简单的算法并并行化所有对部分 . 也许问一个关于你尝试并行化的算法的问题会得到更好的回应 .

    回复于

相关问题