插入期間檢測週期

Question

我有一個有向圖。運行時會動態添加和刪除新邊。如果將要添加到圖形的邊創建一個循環，則不應該添加該邊。我如何用BGL來做到這一點？

typedef boost::adjacency_list< 
    boost::listS, boost::vecS, 
    boost::directedS 
    > Graph; 

int main(int, char*[]){ 

    Graph G; 
    add_edge(0, 1, G); 
    add_edge(1, 2, G); 
    add_edge(2, 3, G); 
    add_edge(3, 0, G); //creates cycle, should abort. 

} 

Answer 1

偷了我編輯葉夫根的代碼，因爲它不會編譯，u和v進行混合。這些更改沒有被接受，所以這裏是適用於我的問題的解決方案。

bool should_we_add(Graph &G, int u, int v){ 

    std::vector<int> distances(num_vertices(G), 0); 

    breadth_first_search(G, vertex(v, G), 
       visitor(make_bfs_visitor(record_distances(&distances[0], on_tree_edge())))); 

    if(distances[u] != 0){ 
    // it is reachable, do NOT add the edge 
    cout << "Cycle!" << endl; 
    return false; 
    } 
    return true; 
} 

Answer 2

您需要在每次添加之前運行寬度或深度優先搜索，以查看是否會形成循環。它將形成當且僅當您正在添加邊緣(u->v)和u已可從v到達。

這裏是一個（希望工作）的代碼，我從here

bool should_we_add(Graph &G) { 
    typedef Graph::vertex_descriptor Vertex; 
    std::vector<int> distances(N, 0); // where N is number of vertices in your graph 

    // The source vertex 
    Vertex s = boost::vertices(G)[u]; // this is your starting vertex 

    boost::breadth_first_search(G, s, 
      boost::visitor(boost::make_bfs_visitor(boost::record_distances(&distances[0], boost::on_tree_edge())))); 

    if (distances[v] != 0) { 
     // it is reachable, do NOT add the edge 
     cout << "Cycle!" << endl; 
     return false; 
    } 
    return true; 
}