I just tried to include adjacency_matrix.hpp and now I don't get errors about those functions anymore. It's strange to have to inclue this header in a template library that doesn't explicitly deal with any concrete implementations of graph concepts. In fact, I don't need to include adjacency_list.hpp for it to work with adjacency_list. I just need to include graph_concepts.hpp and graph_traits.hpp. Anyway, I'm still getting lots of errors in a code that perfectly compiles and works with adjacency lists. If anybody is interested, I can send the listing of compiler errors.

But the compiler needs to know about the existence of these functions. There aren't any "most-general" versions defined anywhere. If you're not including a graph implementation, there's no way the compiler can know about the interface.

You might be able to get around this by including the adjacency_matrix.hpp in your .cpp files before the headers that are using the generic interface.