Will Chen wrote:

So it looks like it's basically a 0-based integer. When I start adding vertices to an empty graph, the first one comes back as 0, the second as 1, third as 2...etc.

Is it always an integer? When is it not an integer?

for a given graph type, vertex_descriptor is some type that identifies vertices. For adjacency_list types is can be intereger (when vertices are stored as vector), or something like list::iterator (when vertices are stored as list). For other graph types it can be something else -- e.g. when wrapping third-party graph type it could be SomeOtherGraphNode*.

I really want a way to easily convert vertex_descriptor's and edge_descriptor's to and from strings. Any ideas?

To what strings? If that's some strings you assign to vertices yourself, you can either use vertex_name_t property, or, if using bundled properties, to include std::string member in the structure for vertex. If that's some "automatic" identifier, that you cannot generally have one automatically. You have to iterate over all vertices or edges, assigning identifiers, before any algorithm that requires such identifiers. vertex_id_t is the standard name of the property for non-bundled properties case, IIRC. - Volodya