Boost：從最短路徑創建圖表

目前我正在使用boost圖庫。我的圖表包括自定義頂點和邊屬性：Boost：從最短路徑創建圖表

typedef boost::labeled_graph<boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, Vertex, Edge>, int> Graph; Graph g;

我需要計算最短路徑（Dijkstra算法）的功能，因此用戶必須選擇一個或多個開始和結束節點。選擇節點並計算每個開始和結束節點之間的最短路徑後，應該創建一個新圖。最後，新圖應該包含所有位於每條最短路徑上的頂點/邊。

我的想法是：

1：我做

類型的計算最短路徑的回溯

typedef std::vector< VertexDescriptor> Path;

2：我檢查，如果頂點已經包含在新的圖形。（我不知道如何處理那個），如果是的話，我將頂點複製到新的Graph中。 3，我檢查邊是否已經包含在新圖中，如果是的話，我將邊複製到新圖中。

Graph graphPaths; 
Path::reverse_iterator rit; 
VertexDescriptor lastNode = *path.rbegin(); 

for (rit = path.rbegin(); rit != path.rend(); ++rit) { 
    // Vertex v = 
     // check if vertices already exist in new GraphPath 
    if (graphPaths[indexMap[*rit]] == NULL) { 
     Vertex v = g[indexMap[*rit]]; 
     VertexDescriptor vd = boost::add_vertex(indexMap[*rit], graphPaths); 
     graphPaths[indexMap[*rit]] = v; 
    } 

    // check if edge is already included in new Graph 
     if (!boost::edge(lastNode, *rit, graphPaths).second) { 

     Graph::edge_descriptor ep = boost::edge(lastNode, *rit, g).first; 
     boost::add_edge_by_label(indexMap[lastNode], indexMap[*rit], g[ep], 
      graphPaths); 
     } 

    } 
    lastNode = *rit; 
}

如何檢查圖形中是否存在頂點。您是否有其他想法來改進流程或解決問題。

感謝邁克爾

來源

2016-11-02 Jacks

我會考慮在原有圖形做filtered_graph適配器，過濾掉所有的頂點/在有趣的路徑邊緣沒有去過。

然後這是一個簡單的copy_graph創建新的圖形。

如果將圖形類型更改爲filtered_graph的labeled_graph，則根據性能折衷情況，甚至不需要該副本。

來源

2016-11-03 16:02:44 sehe

Boost：從最短路徑創建圖表

回答

相關問題