插入期间检测周期

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; 
}