I'm working in a graph algorithm that works on graphs that implement
 BidirectionalGraphConcept and VertexAndEdgeListGraphConcept.
The only additional requirement is that they must have some concrete bundled properties
(I don't want to deal with the, I understand old, method of defining properties).
For example, if g is a graph and v is a valid vertex descriptor of that graph,

This is a really good question because it deals with application-specific graph concepts. These aren't really addressed anywhere in the library. Since your algorithm is generic, you should be thinking about how to "generically" get the properties of the graph. You can do this by abstracting the property reference as a function call. Instead of, g[v].min, you should be writing: vertex_min(g). Or whatever 'min' actually means in this case.

What you're doing is effectively defining application-specific semantics for a graph (that vertices have a min property). In order for a graph to model that property, you just have to provide an overload specific to your graph type.

Andrew Sutton