I'm trying to develop (or if possible find an implementation of) an algorithm to classify the symmetry group of an undirected graph.
Consider an undirected graph $G = \{N, E\}$, where $N = \{n_i\}$ - nodes and $E = \{(n_i, n_j)\}$ - edges. Nauty one of the popular tools people use to work with graph symmetries can be used to obtain generators of the symmetry group. Let's call the symmetry (automorphism) group $A(G)$ and it's generators $a_1...a_l$. I want to consider a simple graph, that is, the graph in which the orbit of $A(G)$ is all the nodes of $G$ (any graph can be factorized in the independent graphs, some of which may have only one node, that have this property). The question is how can I algorithmically classify $A(G)$ i.e. how can I tell that it's $D_4$ or $C_{15}$ or $S_3$ or whatever else? My only idea is to come up with the logic similar to what people do with point groups in crystals, like here, but I wonder if there is an easier way.
I may not be formulating this clearly, so I would be happy to correct it in accordance to your corrections. Thanks in advance!
I published a preprint in which I discuss solution to this problem in section VII.
There are two steps to this problem: (1) decompose the automorphism group into subgroups to be classified and (2) classify each subgroup.
I was able to solve problem 1 by using the approach proposed by MacArthur et. al.. Namely, I used geometric decomposition (see the paper for more details) of the automorphism group, which factorizes the symmetry group into normal subgroups acting on the different parts of the graph.
Problem 2 was solved after a very helpful discussion with @verret. Proposed approach is computational and is based on a very simple idea: take a subgroup and check if it is isomorphic to any of the traditional symmetry groups. In my case I compared them with $S_n$, $D_n$, $C_n$ and $A_n$, for $n$ between 1 and the number of nodes.
Implementation of the solution to both problems (1) and (2) and a little more can be found at my GitHub.