I would like, given an undirected graph G to create another instance of a graph object GP so that GP is isomorphic to G. 

Thus, the two graphs are essentially the same graph, and the only difference is they way internally are “numbering” the vertices. My intention is to look at their spectra.

So far, I am doing this in a very expensive manner: take the adjacency of G, use its “dense” form, and then shuffle the rows/columns according to a random permutation.

Can I do this more efficiently? I think it should be doable to traverse G (from a random node) and then build GP, as I am “exploring" G. The crucial thing is I want to avoid the “to dense()” operator on the adjacency matrix.

Thanks a lot!