generate_automorphisms.py

# Function that receives a matrix adjacency and returns edge set
def edge_set(adj_matrix):
  edge_set = []
  for row in range(len(adj_matrix)):
    for col in range(len(adj_matrix[0])):
      if (list(np.sort([row, col])) not in edge_set):
        if adj_matrix[row][col] == 1:
          edge_set.append(list(np.sort([row, col])))
  return sorted(edge_set)


# Function that receives a vertex permutation and edge set and returns the corresponding edge permutation
def edge_permutation(vertex_perm, original_edge_set):
  edge_set_perm = []
  for edge in original_edge_set:
    edge_set_perm.append(edge.copy())
  for edge in edge_set_perm:
    edge[0] = vertex_perm[edge[0]]
    edge[1] = vertex_perm[edge[1]]
  return [original_edge_set, edge_set_perm]


def get_all_vertex_permutations(adj_matrix):
    if get_graph_order(adj_matrix) > 8:
      print("This function is too inefficient for graph order > 8")
      return -1
    all_adj_matrix = []
    original_edge_set = edge_set(adj_matrix)
    idx = list(range(len(adj_matrix)))
    possible_idx_combinations = [
        list(i) for i in itertools.permutations(idx, len(idx))
    ]
    for idx_comb in possible_idx_combinations:
        a = adj_matrix
        a = a[idx_comb]
        a = np.transpose(np.transpose(a)[idx_comb])
        all_adj_matrix.append({
            "perm_vertex":
            idx_comb,
            "perm_edge":
            edge_permutation(idx_comb, original_edge_set),
            "adj_matrix":
            a
        })

    return all_adj_matrix
  
  
def generate_automorphisms(adj_matrix):
  automorphisms_list = []
  for isograph in get_all_vertex_permutations(adj_matrix):
      if edge_set(adj_matrix) == edge_set(isograph["adj_matrix"]):
          automorphisms_list.append(isograph)
  return automorphisms_list