The "easy" workaround is to simply have the graph refer to BasicBlock by pointer instead of actually owning it. Pointers are definitely default and copy constructible :)

Yes, I had tried that, and the pointers are added to the graph okay using add_vertex, but when I try to pull them out using, say, graph[0], my program segfaults. I have no idea what I'm doing wrong.

It's not surprising that graph[0] crashes for directed_graph; it's vertex descriptors are actually list iterators. It turns out that 0 is an implicit constructor for directed_graph<...>::null_vertex().

The (current BGL) documentation doesn't spell this out very well, and almost none of the examples demonstrate this fact. I think you could use:

graph[vertex(g, 0)]

but that might be O(n).

I should do maybe:

typedef adjacency_list<vecS, vecS, directedS, BasicBlock*> TimingGraph;

If you're not going to remove vertices, then that's probably a good bet. I forget if this is good for removing edges also. I'm guessing "no".