The formatting went bad with the previous email. Sorry about that. Here it is once again. Hello, I'm using a labeled graph typedef boost::labeled_graph,std::string> MyGraph; which lets me access vertices with string ids. I add a vertex and set it's relevant fields this way: MyVertex u = boost::add_vertex(id, g); g[id].category = category; //crashes here g[id].vertex_id = id; Here id is an std::string. And remove them like so: // First we remove all edges from this vertex BGL_FORALL_VERTICES(v, g, MyGraph){ if (QString(g.graph()[v].vertex_id.c_str()).compare(roomIdToBeRemoved) == 0){ ve = v; BGL_FORALL_OUTEDGES(v, e, g, MyGraph) { ev.push_back(e); } } } foreach(MyEdge e, ev){ remove_edge(e,g); } // Then we remove the vertex itself remove_vertex(roomIdToBeRemoved.toStdString().c_str(),g); This so far seems to work. The trouble is, if I want to add a removed vertex once again with the same id, I get the following: Exception Type: EXC_BAD_ACCESS (SIGSEGV) while setting the fields of the newly added vertex (above commented "crashes here"). What might be the reason? I'm using boost functions for removing/adding things.