As far as I can tell from the code, Graph::vertices() gets its list from Graph::AdjacencyMap::paths(), and all three implementations (::Light, ::Heavy, and ::Vertex) use a hash to store them. Hashes are unordered, so if you need a sorted order, you will have to to sort them yourself. Either that, or modify the internals of the Graph module so vertices aren't stored in a hash but in a sorted data structure.