It's not really a case of using size_t. It's a case where graphs that use size_t map those values onto vertices [0, n) and implicitly (or is it explicitly? Depends on perspective, I guess) define an interior property vertex_index_t. For most graph types with vertex_descriptor type == size_t, the call:

im = get(vertex_index, g)

returns a vertex index map (im), and calling

get(im, v)

with v a vertex descriptor actually just returns v.

For graphs with void* descriptors (or otherwise), there is no implicit vertex index map. The first call above will fail unless you explicitly create a vertex_index_t property for the graph. Then you still have to *assign* the indices. It's not done automatically.

For your graph impl, if you're using something like size_t that maps onto vertices, then you could probably get around this by providing the following function (or something similar).

identity_property_map get(vertex_index_t, my_graph_type& g) {
  return identity_property_map();
}

Calls to get(vertex_index, g) where g is an object of your graph type will use this overload. identity_property_map, I forget if it actually exists, is basically the type of im in the examples above. I also forget the constness of these things...

This approach may help solve your problems.
 

That's unfortunate :) I'll take a look tomorrow. Maybe Nick or Jeremiah is more familiar with it?