恆定頂點IDS中的adjacency_list

我想保持外部屬性頂點和的adjacency_list圖的邊（和用於頂點的基團）。我需要能夠通過它們的屬性訪問頂點。例如，我想遍歷指定一些權重的所有頂點，並獲得它們的外邊緣。恆定頂點IDS中的adjacency_list

不過，我也需要我的頂點容器是集。在此容器中，添加\移除頂點可能會使頂點描述符無效。

的問題是，外部性，現在可以映射到無效vertex_descriptors。

class manage_data { 
... 
    auto get_interesting(int weight) { 
     return ver_by_weight.equal_range(weight); 
    } 
    void do_stuff (...) { 
     auto for_later_use = get_interesting(); 
     ... 
     boost::remove_vertex(unrelated_vertex, graph_); 
     ... 
     use_vec(for_later_use.front()); //bug 
    } 
    }

一種方法似乎是添加一個vertex_index屬性。這是行不通的，因爲它是一個方向 - 你可以通過vertex_descriptor獲得vertex_index，但不能反過來。這意味着我不能在兩個只知道索引的頂點之間添加邊。

另一個有前途的解決方案是使用標記圖。該圖可以僅通過標籤添加邊。通過存儲具有標籤ID的外部數據，我可以變得相當遠。不幸的是，並非所有的adjacency_list接口都是使用標籤重新實現的，例如out_edges。這意味着我仍然需要能夠訪問頂點描述符，並且不可能（在合理的時間內）僅使用標籤，如可以看到的那樣here

更好的解決方案是將上述兩個一個vertex_label屬性。這看起來過於複雜，並且不起作用（以上例子）。

它不應該是常見的頂點涉及到外部數據？你怎麼能這樣做？

來源

2017-05-17 bravesirrobin

「所有頂點分配了一定的重量」 - 你的意思是邊緣？ – sehe

否，如示例代碼 - ver_by_weight.equal_range（weight）。 – bravesirrobin

您可以使用從頂點描述符的雙向映射到自己的ID。

現在，只要你使用任何基於節點的容器選擇器頂點的容器，你所有的設置。

看一看BIMAP並可能transform_value_property_map提供最大的便利（儘管你可能並不需要所有的幻想，特別是如果該圖主要是隻讀的 - 或如僅收縮）

也見

來源

2017-05-18 00:52:09 sehe

如何在頂點描述符變爲無效時使用雙向映射？我只能使用內部屬性，所以圖類將更新我的頂點描述符。 BGL是否具有內在的雙向屬性？ – bravesirrobin

什麼是基於節點的容器選擇器？ :) – bravesirrobin

基於節點的是分配數據結構時使用節點。所以，'listS'或'setS'可以。「當頂點描述符變爲無效時」 - 當使用這些基於節點的容器時，它們不會¹。（¹只有實際刪除的描述符變爲無效） – sehe

恆定頂點IDS中的adjacency_list

回答

相關問題