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!
On 05/09/2014 12:38 AM, Helen Lampesis wrote:
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
Helen Lampesis -
Tiago de Paula Peixoto