Detecting Cycles During Insertion

I have a directed graph. New edges are added and removed dynamically at run time. If an edge that is about to be added to the graph creates a cycle, then that edge should not be added. How would I do th开发者_开发技巧is with 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.

}

You will want to run a breadth- or depth-first search before each addition, to see if a cycle will be formed. It will be formed if and only if you are adding an edge (u->v) and u is already reachable from v.

Here is a (hopefully working) code i stole from 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;
}

I edited evgeny's code because it wouldn't compile, and u and v were mixed up. The changes were not accepted, so here is the solution that works for my question.

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