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

Usage
1

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?

2

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.

3

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
4

Just curious:

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

5

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.

6

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?