Is there a way to add an edge if I don't know the vertex indices? For
instance, let's say I've only got the two Foo pointers and I want to
add an edge between them.

I figured out a way to do it:

 graph_traits<Graph>::vertex_descriptor u = add_vertex(&foo1, g);
 graph_traits<Graph>::vertex_descriptor v = add_vertex(&foo2, g);
 add_edge(u, v, g);