Написал примитивный роутер для прокладки маршрута по данным ОСМ, тоже столкнулся с тем что надо проверять связность и достижимость вершин графа, обратил внимание на unclassified. Как-то их многовато в одном классе, целая половина от общего числа. А что конкретно Вы имели в виду под проверкой классификации?