Кто-нибудь использует boost.graph в своих задачах?
Как впечатления?

А то он какой-то слишком уж монстровидный и думаю
стоит ли уделять ему время или легче написать свой маленький велосипед?
Алгоритмы на графах в принципе хорошо описаны.