Creating an isomorphic graph

Dear All,

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!

attachment.html (1.07 KB)

Dear All,

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.

When you construct a new graph given an existing graph, this graph gets
copied. If you pass a 'vorder' property map, this is used to reorder the
new graph. For instance, to create a random permutation:

    >>> vorder = g.vertex_index.copy("int")
    >>> numpy.random.shuffle(vorder.a)
    >>> u = Graph(g, vorder=vorder)
    >>> print(isomorphism(g, u))
    True

(Note that g and u must have identical spectral properties).

Best,
Tiago