Question about how get_automorphisms_vf2 working

Usage
1

Hi everyone, I am new to igraph. I have a graph and I want to get the list of all automorphisms.
It’s my graph:

image
image866×720 59.5 KB

The graph’s edges are:

[[1,2], [1,3], [1,4], [1,5], [2,1], [2,3], [2,4], [2,5], [3,1], [3,2], [3,4], [3,5], [4,1], [4,2], [4,3], [4,5], [5,1], [5,2], [5,3], [5,4]]

Source-code:

from igraph import *
import igraph as ig
print(ig.__version__)

q1 = [[1,2], [1,3], [1,4], [1,5], [2,1], [2,3], [2,4], [2,5], [3,1], [3,2], [3,4], [3,5], [4,1], [4,2], [4,3], [4,5], [5,1], [5,2], [5,3], [5,4]]
g = Graph(edges=q1)
g.summary(verbosity=1)

auts = g.get_automorphisms_vf2()
print(auts)

And automorphisms are:

[[0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 5, 4], [0, 1, 2, 4, 3, 5], [0, 1, 2, 4, 5, 3], [0, 1, 2, 5, 3, 4], [0, 1, 2, 5, 4, 3], [0, 1, 3, 2, 4, 5], [0, 1, 3, 2, 5, 4], [0, 1, 3, 4, 2, 5], [0, 1, 3, 4, 5, 2], [0, 1, 3, 5, 2, 4], [0, 1, 3, 5, 4, 2], [0, 1, 4, 2, 3, 5], [0, 1, 4, 2, 5, 3], [0, 1, 4, 3, 2, 5], [0, 1, 4, 3, 5, 2], [0, 1, 4, 5, 2, 3], [0, 1, 4, 5, 3, 2], [0, 1, 5, 2, 3, 4], [0, 1, 5, 2, 4, 3], [0, 1, 5, 3, 2, 4], [0, 1, 5, 3, 4, 2], [0, 1, 5, 4, 2, 3], [0, 1, 5, 4, 3, 2], [0, 2, 1, 3, 4, 5], [0, 2, 1, 3, 5, 4], [0, 2, 1, 4, 3, 5], [0, 2, 1, 4, 5, 3], [0, 2, 1, 5, 3, 4], [0, 2, 1, 5, 4, 3], [0, 2, 3, 1, 4, 5], [0, 2, 3, 1, 5, 4], [0, 2, 3, 4, 1, 5], [0, 2, 3, 4, 5, 1], [0, 2, 3, 5, 1, 4], [0, 2, 3, 5, 4, 1], [0, 2, 4, 1, 3, 5], [0, 2, 4, 1, 5, 3], [0, 2, 4, 3, 1, 5], [0, 2, 4, 3, 5, 1], [0, 2, 4, 5, 1, 3], [0, 2, 4, 5, 3, 1], [0, 2, 5, 1, 3, 4], [0, 2, 5, 1, 4, 3], [0, 2, 5, 3, 1, 4], [0, 2, 5, 3, 4, 1], [0, 2, 5, 4, 1, 3], [0, 2, 5, 4, 3, 1], [0, 3, 1, 2, 4, 5], [0, 3, 1, 2, 5, 4], [0, 3, 1, 4, 2, 5], [0, 3, 1, 4, 5, 2], [0, 3, 1, 5, 2, 4], [0, 3, 1, 5, 4, 2], [0, 3, 2, 1, 4, 5], [0, 3, 2, 1, 5, 4], [0, 3, 2, 4, 1, 5], [0, 3, 2, 4, 5, 1], [0, 3, 2, 5, 1, 4], [0, 3, 2, 5, 4, 1], [0, 3, 4, 1, 2, 5], [0, 3, 4, 1, 5, 2], [0, 3, 4, 2, 1, 5], [0, 3, 4, 2, 5, 1], [0, 3, 4, 5, 1, 2], [0, 3, 4, 5, 2, 1], [0, 3, 5, 1, 2, 4], [0, 3, 5, 1, 4, 2], [0, 3, 5, 2, 1, 4], [0, 3, 5, 2, 4, 1], [0, 3, 5, 4, 1, 2], [0, 3, 5, 4, 2, 1], [0, 4, 1, 2, 3, 5], [0, 4, 1, 2, 5, 3], [0, 4, 1, 3, 2, 5], [0, 4, 1, 3, 5, 2], [0, 4, 1, 5, 2, 3], [0, 4, 1, 5, 3, 2], [0, 4, 2, 1, 3, 5], [0, 4, 2, 1, 5, 3], [0, 4, 2, 3, 1, 5], [0, 4, 2, 3, 5, 1], [0, 4, 2, 5, 1, 3], [0, 4, 2, 5, 3, 1], [0, 4, 3, 1, 2, 5], [0, 4, 3, 1, 5, 2], [0, 4, 3, 2, 1, 5], [0, 4, 3, 2, 5, 1], [0, 4, 3, 5, 1, 2], [0, 4, 3, 5, 2, 1], [0, 4, 5, 1, 2, 3], [0, 4, 5, 1, 3, 2], [0, 4, 5, 2, 1, 3], [0, 4, 5, 2, 3, 1], [0, 4, 5, 3, 1, 2], [0, 4, 5, 3, 2, 1], [0, 5, 1, 2, 3, 4], [0, 5, 1, 2, 4, 3], [0, 5, 1, 3, 2, 4], [0, 5, 1, 3, 4, 2], [0, 5, 1, 4, 2, 3], [0, 5, 1, 4, 3, 2], [0, 5, 2, 1, 3, 4], [0, 5, 2, 1, 4, 3], [0, 5, 2, 3, 1, 4], [0, 5, 2, 3, 4, 1], [0, 5, 2, 4, 1, 3], [0, 5, 2, 4, 3, 1], [0, 5, 3, 1, 2, 4], [0, 5, 3, 1, 4, 2], [0, 5, 3, 2, 1, 4], [0, 5, 3, 2, 4, 1], [0, 5, 3, 4, 1, 2], [0, 5, 3, 4, 2, 1], [0, 5, 4, 1, 2, 3], [0, 5, 4, 1, 3, 2], [0, 5, 4, 2, 1, 3], [0, 5, 4, 2, 3, 1], [0, 5, 4, 3, 1, 2], [0, 5, 4, 3, 2, 1]]

Would you please help me with how getting automorphism works? And why do we have 0 in the automorphisms list?

Some of the automorphisms:

  • [0, 1, 2, 3, 4, 5]
  • [0, 1, 2, 3, 5, 4]
  • [0, 1, 2, 4, 3, 5]
  • [0, 1, 2, 4, 5, 3]

When we have 1-5, So what is 0?
In the main shape, the graph we have only 5 edges.

igraph c-Code:

Thanks.

2

One thing that you should know is that igraph’s vertex IDs are zero-based, not 1-based. You essentially constructed a graph with 6 vertices: an isolated vertex and a full graph with 5 vertices. This is why you are seeing the extra 0 in the automorphism – it’s the isolated vertex being mapped to itself.