如何在boost中實現boost :: property_map以及如何更改它

Question

我在想如何在提升圖中實現屬性映射。例如，

我已經頂點和邊緣屬性定義如下：

//vertex property:--> 
struct NodeInfo { int a , b , c; }; //actual bundled property 

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 the Vertex Property 
typedef boost::property <NodeInfoPropertyTag, NodeInfo> NodeProperty; 


//Similar fashion for Edge Property --> some property for each edge of graph. 
typedef boost::property <EdgeInfoPropertyTag, EdgeInfo> EdgeProperty; 

My圖表被typedef定義如下：現在

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

，在初始化使用上述的typedef G中的曲線圖，我可以分配屬性到頂點和邊的屬性

例如：

Graph_t G; 
    typedef graph_traits<Graph_t>::vertex_descriptor vd_t; 
    // edge_descriptor ed_t; 

    NodeInfo ninfo1, ninfo2; //put some values in ninfo 
    vd_t v = add_vertex (ninfo1, G) //add a vertex in G with property ninfo1 
    vd_t u = add_vertex (ninfo2, G) //add a vertex in G with property ninfo2 


    EdgeInfo einfo; //initialize edgeinfo for edge property 
    add_edge (u, v, einfo, G) edge (u, v) with property einfo is added in G 

要訪問節點屬性的任何頂點的，我可以用任何的2種方法如下：

//method 1: direct method: using Tags 

// for a vertex "v" --> get() 
NodInfo info = boost::get (NodeInfoPropertyTag(), G, v) //get v's property 

//modify info 

//put the modified property 
    put (NodeInfoPropertyTag(), G, v, info) // (put in G, key = v, value = info) 


//method 2 : using property maps. 

//Edge Map and Node Map 
typedef typename boost::property_map <Graph_t, EdgeInfoPropertyTag>::type EdgeMap; 
typedef typename boost::property_map <Graph_t, NodeInfoPropertyTag>::type NodeMap; 


//edge e --> get 
EdgeInfo einfo = boost::get (EdgeMap, e) 

//modify einfo 

//put 
put (EdgeMap, e, einfo) //put in the EdgeMap key = e, value = einfo 

現在，無論是操作基本上是一樣的：即使用

//former is translated to the latter --> 
    get(NodeInfoPropertyTag(), G, "key") is equivalent to get (NodeMap, "key") 

我的問題是：

1. 這些屬性如何存儲在Graph對象中。
2. 它是否存儲在一個地圖，如std :: map <>？或一些列表？或者一些有效的地圖式數據結構。
3. 如果是這樣，我怎麼能修改底層數據結構爲std :: unordered_map，甚至 concurrent_hashmap或boost :: vector_property_map？

注： 我不知道我可以使用vector_prop_map（在這裏），但我真的很想讓 頂點ID變成向量索引和更有效地使用它 - 在邊緣>可能會導致問題雖然

My圖表將包含一個萬個頂點和許多許多的邊緣，以這種方式 搜索的std ::地圖<>仍然會的log（n）本身，但我想便攜性改變 基礎數據結構，以便我可以使用unordered_map/concurrent_hashmap

我需要concurrent_hashmap（來自英特爾TBB），因爲我將並行化我的算法 ，因此會希望同時訪問將由線程修改的屬性圖 。

請提出是否可以控制和修改增強圖中用於存儲邊和頂點屬性的底層數據結構。

Answer 1

這些屬性如何存儲在Graph對象中。

屬性不單獨存儲或類似的東西。

頂點和邊屬性存儲在圖的頂點和邊上。沒有使用std::map或其他關聯容器。無論您提供給adjacency_list的是什麼，因爲VertexProperties和EdgeProperties模板參數將存儲在頂點和邊緣中，即與使用std::list<T>時相同，其中T將存儲在鏈接列表的節點中（以及必要的next-prev指針）。換句話說，adjacency_list將存儲包含VertexProperties類型對象的頂點，以及所需的任何邊界列表（入和出）。

當你使用property_map（通過get/put函數），它只是做一點模板元編程魔術來創建一個薄包裝器，它將只讀/寫一個頂點或邊的正確單個屬性。從概念上講，這就是等價：

NodeInfo info = boost::get (NodeInfoPropertyTag(), G, v); 

// is conceptual equivalent to: 

NodeInfo info = G[v].NodeInfoProperty; 

這是所有的財產，地圖確實，它看起來了頂點屬性（在給定的圖形對象的頂點描述符），並獲取數據成員（或子對象）對應於給定標籤類型的頂點屬性。弄清楚如何爲正確的屬性標籤獲取正確的數據成員（或子對象）是一種模板元編程魔術，可以在編譯時計算出來（無運行時開銷）。而且，通常，從頂點描述符查找頂點屬性是一個常量操作（例如，取消引用指針，按索引查找等）。總體而言，讀取（讀取或寫入）特定頂點的特定屬性是恆定時間操作。就我所知，對於使用adjacency_list的模板參數所做的任何選擇都是如此。

如果是這樣，我該如何修改底層數據結構爲std :: unordered_map，甚至是concurrent_hashmap或boost :: vector_property_map？

您可以通過OutEdgeList，VertexList和EdgeList指定如何存儲頂點和邊。這些屬性本身沒有額外的存儲方法。在這些情況下使用地圖或hashmaps並沒有多大意義。

我真的想使用它，這樣頂點ID變成向量索引

當您爲VertexList參數指定vecS這已經是用的adjacency_list的情況。

我需要concurrent_hashmap（來自英特爾TBB），因爲我會並行化我的算法，因此會希望併發訪問將由線程修改的屬性映射。

您應該考慮使用Parallel Graph庫來代替。

請提出是否可以控制和修改升壓圖中用於存儲邊和頂點屬性的基礎數據結構。

您可以指定用於存儲頂點和邊界列表的數據結構。你可以（理論上）爲這些添加新的容器類型。然而，根據我的經驗，這很難實現，因爲adjacency_list的實現很難將您的思想包裝起來，並且交換其底層容器並不像在Boost網站上宣傳的那麼容易。