I fully agree. Despite the syntactical clunkiness and the need to learn some new concepts, BGL's design is beautiful -- surprisingly, it mostly achieves the STL

I fully agree. Despite the syntactical clunkiness and the need to learn some new concepts, BGL's design is beautiful -- surprisingly, it mostly achieves the STL goal of implementing M algorithms on N different representations using just O(M+N) code (vs. the usual O(M*N)), without sacrificing efficiency. Like the OP, after much wandering through the desert I had come to the conclusion that there was no way to generically yet performantly model graphs -- but once I understood (the basics of) BGL, I was persuaded otherwise. It's a little disappointing that BGL didn't make an appearance in TFA.