在Boost圖庫中給定頂點的鄰居的隨機選擇或隨機選擇的有效方法？

我需要使用Boost Graph Library從我的圖中給定的頂點中選擇一個隨機的鄰居或鄰居。我從一個RNG收到一個索引i，並且需要選擇第i個邊緣（它們可以是任意順序，只需要在呼叫間保持一致）。爲此，我利用了std::advance像這樣：在Boost圖庫中給定頂點的鄰居的隨機選擇或隨機選擇的有效方法？

typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; 
Graph g; // Given graph 
int i; 
int v; // Given vertex 
// 
// Code to generate random index (guaranteed to be valid) and store it in i 
// 
typename graph_traits <graph_t>::in_edge_iterator ei, ei_end; 
tie(ei,ei_end) = in_edges(v,g); 
std::advance(ei,i); 
// Now ei points to the ith out edge, and is ready to use 
// Return the corresponding in-neighbor 
return source(*ei,g);

現在能正常工作，而我得到正確的輸出。不過，我需要知道這是否有效，即std::advance將在固定時間內工作，而不管i的值如何，因爲我已經使用vecS來存儲鄰接列表了？如果不是，有沒有一種有效的方法？

我應該提到，我只需要選擇一個隨機的鄰居或鄰居，所以如果你有辦法做到這一點，而不處理邊緣，那也會很好。

來源

2017-02-25 NILobachevsky

我試着增加迭代器作爲指針，它的工作原理。我換成

std::advance(ei,i);

與

ei+=i;

現在它運行在固定的時間在i對進出邊迭代兩者。然而，前者在i中需要時間線性。

出於某種原因，儘管我可以像上面那樣進行隨機訪問，但在其他答案中描述的檢查是否存在迭代器失敗。

來源

2017-02-27 12:58:10 NILobachevsky

如果你想確保advance(ei. i)是o(1)，你可以簡單地添加一個static_assert：

static_assert( 
    std:::is_base_of< 
      std::random_access_iterator_tag, 
      typename std:::iterator_traits< decltype(ei) >::iterator_category 
    >::value, 
    "Not a random access iterator!")

這將無法編譯，如果ei不是一個隨機訪問迭代器。

至於實際問題，具有OutEdgeList（在adjacency_list第一模板參數）= vecS是足以具有隨機存取out_edges。我相信沒有指定in_edges返回的迭代器是否是隨機訪問。

來源

2017-02-25 14:36:15 sbabbi

感謝您的回答。有趣的是，assert在_both_ out和邊緣失敗。如果考慮到邊緣顯然應該是隨機訪問？有沒有另一種方法來有效地選擇一個隨機的鄰居（不必涉及迭代邊緣）？ – NILobachevsky

我剛剛通過一個簡單的基準確認了兩種迭代器都不是隨機訪問;該訪問在索引中需要時間線性。即使當我嘗試使用adjacency_iterator（assert也不存在）時，這似乎是真的 – NILobachevsky

那麼[documentation]（http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/adjacency_list.html ）'out_edges'明確指出，如果你使用'vecS'，返回的迭代器應該是隨機訪問..所以現在我感到困惑。 – sbabbi

在Boost圖庫中給定頂點的鄰居的隨機選擇或隨機選擇的有效方法？

回答

相關問題