typedef property<vertex_name_t, std::string> VertexProp;
//this crashes
typedef adjacency_list < vecS, vecS, undirectedS,VertexProp, no_property > graph_t;
//this doesn't
//typedef adjacency_list < vecS, listS, undirectedS,VertexProp, no_property > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
typedef property_map<graph_t, vertex_name_t>::type id_name_map_t;
typedef graph_traits<graph_t>::vertex_iterator vi_t;
std::pair<vi_t,vi_t> vi;

Try writing this using bundled properties:

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/bundles.html
 
Andrew Sutton
andrew.n.sutton@gmail.com