does get_automorphisms_vf2() in igraph python support vertex attributes and edge attributes?

I am trying to generate an automorphism graphs for a set of 2D particles on a grid.
Where I assign vertex attribute depending on particle type, and edge attributes depending on pairwise particle distances (since the particles live on a grid most edges share distances with other edges)

As a small example of this I have the following:


nodes = 4
node_attributes = {0: '0', 1: '0', 2: '1', 3: '2'}
edge_attributes = {0: '1', 1: '2', 2: '5', 3: '1', 4: '4', 5: '3'}
edges = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

g = ig.Graph(n=n, edges=edges,directed=False,vertex_attrs=node_attributes,edge_attrs=edge_attributes)
print(g.get_automorphisms_vf2())

But this just seems to produce all permutations of the nodes and does not take the vertex attributes or edge_attributes into consideration as far as I can see?

You need to pass vertex and edge colours explicitly. See the docs:

The colours must be integers, not strings.

Note that attributes are not used automatically by VF2 (or other) isomorphism functions. You need to specify “colours” explicitly, and colours must be discrete values, represented as integers.


Furthermore, the specification of the vertex and edge attributes in the code above is not correct. node_attributes should be a mapping from attribute names to iterables with as many elements as the vertex count. So if you have four vertices, and you want to assign 4, 5, 6, 7 to the vertex attribute named "foo", then use {"name": [4, 5, 6, 7]} as the vertex attribute specification during graph creation.


@tamas The documentation could use some improvement here. I am looking at this, and it wasn’t clear why the above code didn’t trigger an error.

There’s an undocumented behaviour of graph.vs[something] = value such that if value is not an iterable, it is interpreted as a common value for all attributes. So the code above ended up creating vertex attributes named 0, 1, 2 and3, all with a common value for all vertices. I’m not really eager to document it as I now think it was a bad idea to introduce this shortcut and I’m not sure I want to keep it in the future.

I’ve extended the docs of Graph.__init__ a bit to clarify that they keys should be attribute names.

1 Like

Just curious:

A string is an iterable though. Are strings treated specially?

Yes, they are, but I don’t want to go to such intricate details. Strings are treated as non-iterables for the purpose of the above mentioned shortcut.

Thank you both for the illuminating comments, they helped getting the automorphism working!

Now that it is working, I have to admit that I am not quite sure how to use this to achieve what I want though…
As mentioned earlier I have diffrent types of particles on a 2D grid, and I want to generate a unique canonical string representation of the complete graph for each of these particle systems.
Below I show 6 simple examples, where the first 4 should all be isomorph and the last two should be different.

coordinates = [[0,0],[-1,0],[1,0],[-1,1]]
node_colors = [0,1,1,1]

coordinates = [[0,0],[1,0],[-1,0],[-1,1]] #Just a simple permutation of nodes, so should be isomorph
node_colors = [0,1,1,1]

coordinates = [[1,1],[0,1],[2,1],[0,2]] #Just a simple translation of all nodes, so should be isomorph
node_colors = [0,1,1,1]

coordinates = [[0,0],[-1,0],[1,0],[1,1]] # This is a mirroring so should also be isomorph
node_colors = [0,1,1,1]

coordinates = [[0,0],[-2,0],[2,0],[-2,2]] # All distances are now twice as long, so this should be a new graph
node_colors = [0,1,1,1]

coordinates = [[0,0],[-1,0],[1,0],[-1,1]] # Different node colors, so different graph
node_colors = [3,1,1,1]

I can compute the automorphism of each of these using the code below, as well as the canonical representation (though that does not take into account the edge_colors, which I guess is irrelevant?):


import torch
import numpy as np
import igraph as ig


def dist_matrix(x,precision=3):
    x = np.asarray(x)
    dist = np.sqrt((x**2).sum(axis=1)[:, None] - 2 * x.dot(x.transpose()) + ((x**2).sum(axis=1)[None, :]))
    return np.round(dist,decimals=precision)

def generate_all_possible_edge_len_dict(n,precision=3):
    x = torch.arange(n).repeat(n)
    y = torch.arange(n).repeat_interleave(n)
    xy = torch.stack((x,y),dim=1).numpy()
    D = dist_matrix(xy,precision)
    all_possible_edge_lens = np.unique(D)
    val = np.arange(len(all_possible_edge_lens))
    edge_color_lookup = dict(zip(all_possible_edge_lens, val))
    return edge_color_lookup

edge_color_lookup = generate_all_possible_edge_len_dict(5)#.tolist()

def generate_edges_and_edge_colors(coordinates):
    n = len(coordinates)

    D = dist_matrix(coordinates)
    edges = torch.combinations(torch.arange(n), 2).numpy()
    edge_distances = [D[edge[0], edge[1]] for edge in edges]
    edge_colors = [edge_color_lookup[edge] for edge in edge_distances]
    return edges.tolist(), edge_colors

coordinates = [[0,0],[-1,0],[1,0],[-1,1]]
node_colors = [0,1,1,1]
edges, edge_colors = generate_edges_and_edge_colors(coordinates)
g = ig.Graph(n=len(coordinates), edges=edges,directed=False)
print(g.get_automorphisms_vf2(color=node_colors,edge_color=edge_colors))

permute = g.canonical_permutation(color=node_colors)
canonical_representation=g.permute_vertices(permute)

Given the automorphism and the canonical representation I am sure I should be able to build some uniquely identifying string expression for these different kinds of graphs, but I am not really sure how to go about this? Is there any function/method in igraph for something like this? or does anyone have any recommendations about how to build such a thing?
I’m imagining the string would be some kind of unique ordering of the nodes, their colors as well as the edge_colors. Something like:

permute = g.canonical_permutation(color=node_colors)
canonical_representation=g.permute_vertices(permute)
coordinates_c = [coordinates[p] for p in permute]
edges_c = canonical_representation.get_edgelist()
node_colors_c = [node_colors[p] for p in permute]
_, edge_colors_c = generate_edges_and_edge_colors(coordinates_c)
rep = f"node_colors={node_colors_c},edges={edges_c},edge_colors={edge_colors_c}"

which might look like:
‘node_colors=[0, 1, 1, 1],edges=[(0, 3), (0, 2), (0, 1), (2, 3), (1, 3), (1, 2)],edge_colors=[2, 1, 1, 4, 1, 3]’

However, this does not use the automorphism method at all, so I think there must be something wrong with it?