Invoke graphsymmetry without arguments to obtain usage information.
The input to graphsymmetry is a symbolic adjacency matrix, preceded by an integer representing the number of vertices. The above graph is represented by (dihedron.g):
# # graphsymmetry input for chiral tri-dihedron. # # number of vertices 5 # adjacency matrix # 0 1 2 3 4 x b - r r # 0 - x b r r # 1 b - x r r # 2 r r r x - # 3 r r r - x # 4
Comments are preceded by #. Blank lines are ignored.
Matrix symbols along the diagonal represent vertex color; all other matrix symbols represent arc color.
The above symbols x, -, r, b have no special meaning; they were arbitrarily chosen in this example to represent 'black vertex', 'no arc', 'red arc', and 'blue arc', respectively. Symbols may be more than one character long.
The graphsymmetry output is:
file: dihedron.g group size: 6 group summary: 1 elements of order 1 1 elements of order 2 2 elements of order 3 2 elements of order 6 permutations: 0 ( 0 )( 1 )( 2 )( 3 )( 4 ) 1 ( 0 )( 1 )( 2 )( 3 4 ) 2 ( 0 1 2 )( 3 )( 4 ) 3 ( 0 1 2 )( 3 4 ) 4 ( 0 2 1 )( 3 )( 4 ) 5 ( 0 2 1 )( 3 4 )Try changing vertex/arc colors in the above example. For example, join vertices 3 and 4 with a directed arc --- this will cut the size of the group in half (since vertices 3 and 4 are no longer interchangeable).
Invoke symmetry without arguments to obtain usage information.
The input to symmetry looks like (dihedron.v):
# # tri-dihedron in three-dimensional space # # number of vertices, number of dimensions 5 3 # vertices, one per line 1 0 0 -0.5 0.866025403784439 0 -0.5 -0.866025403784439 0 0 0 1 0 0 -1
Comments are preceded by #. Blank lines are ignored.
The symmetry output is:
file: dihedron.v vertices: 0 1 0 0 1 -0.5 0.866025403784439 0 2 -0.5 -0.866025403784439 0 3 0 0 1 4 0 0 -1 group size: 12 group summary: 1 elements of order 1 7 elements of order 2 2 elements of order 3 2 elements of order 6 permutations: 0 ( 0 )( 1 )( 2 )( 3 )( 4 ) 1 ( 0 )( 1 )( 2 )( 3 4 ) 2 ( 0 )( 1 2 )( 3 )( 4 ) 3 ( 0 )( 1 2 )( 3 4 ) 4 ( 0 1 )( 2 )( 3 )( 4 ) 5 ( 0 1 )( 2 )( 3 4 ) 6 ( 0 1 2 )( 3 )( 4 ) 7 ( 0 1 2 )( 3 4 ) 8 ( 0 2 1 )( 3 )( 4 ) 9 ( 0 2 1 )( 3 4 ) 10 ( 0 2 )( 1 )( 3 )( 4 ) 11 ( 0 2 )( 1 )( 3 4 )The group size is double that of the above graphsymmetry example because the vertices 0,1,2 are no longer connected by directed arcs but by undirected distances.
Invoke spacegroup without arguments to obtain usage information.
spacegroup is a ruby script whose function is similar to that of symmetry except it additionally gives eigenvalues of the group elements. The script is easy to modify; for example you could print the actual transforms and the corresponding the eigenvectors, if you wished.
The input to spacegroup is the same as that of symmetry. The spacegroup output for the above example is:
vertices: 0 1.0000000000000000 0.0000000000000000 0.0000000000000000 1 -0.5000000000000000 0.8660254037844390 0.0000000000000000 2 -0.5000000000000000 -0.8660254037844390 0.0000000000000000 3 0.0000000000000000 0.0000000000000000 1.0000000000000000 4 0.0000000000000000 0.0000000000000000 -1.0000000000000000 group size: 12 1 elements of order 1 7 elements of order 2 2 elements of order 3 2 elements of order 6 ---------------------------------------------------------------------- elem: 0 ordr: 1 eigv: 1.00, 1.00, 1.00 perm: (0) ---------------------------------------------------------------------- elem: 1 ordr: 2 eigv: 1.00, 1.00, -1.00 perm: (3 4) ---------------------------------------------------------------------- elem: 2 ordr: 2 eigv: 1.00, -1.00, 1.00 perm: (1 2) ---------------------------------------------------------------------- elem: 3 ordr: 2 eigv: 1.00, -1.00, -1.00 perm: (1 2)(3 4) ---------------------------------------------------------------------- elem: 4 ordr: 2 eigv: -1.00, 1.00, 1.00 perm: (0 1) ---------------------------------------------------------------------- elem: 5 ordr: 2 eigv: -1.00, 1.00, -1.00 perm: (0 1)(3 4) ---------------------------------------------------------------------- elem: 6 ordr: 3 eigv: R(120.00), 1.00 perm: (0 1 2) ---------------------------------------------------------------------- elem: 7 ordr: 6 eigv: R(120.00), -1.00 perm: (0 1 2)(3 4) ---------------------------------------------------------------------- elem: 8 ordr: 3 eigv: R(120.00), 1.00 perm: (0 2 1) ---------------------------------------------------------------------- elem: 9 ordr: 6 eigv: R(120.00), -1.00 perm: (0 2 1)(3 4) ---------------------------------------------------------------------- elem: 10 ordr: 2 eigv: -1.00, 1.00, 1.00 perm: (0 2) ---------------------------------------------------------------------- elem: 11 ordr: 2 eigv: -1.00, 1.00, -1.00 perm: (0 2)(3 4) ----------------------------------------------------------------------
Given a finite set of vectors V lying in n-dimensional space, the simplest algorithm to detect the symmetry group of V is to start with a reference basis of n vectors (taken from V) and build each transformation taking this basis to all n-tuples of the vectors in V. (There are P(|V|, n) such n-tuples.) If a resultant transformation is both orthogonal and leaves V invariant, then you have an element of the symmetry group.
We can refine this algorithm by only considering the n-tuples which have the same respective intra-tuple distances as the reference basis. For if the angles between the vectors in a given n-tuple do not match in correspondence with those of the reference basis, the resulting transformation will certainly not be orthogonal.
But wait, we can refine this idea even more. Why not include more vectors in the test? Instead of starting with a reference basis, start with a reference (n+1)-tuple of (dependent) vectors spanning n dimensions, and find all (n+1)-tuples of V which have the same respective intra-tuple distances as the reference tuple.
But we can also do this for (n+2)-tuples and all the way up to |V|-tuples. Now we can dispense with the orthogonality and invariance checks altogether!
The final algorithm is nothing more than an edge-matcher. With the help of some data structures which hash out edge lengths with vertex/vertex-set pairs, it efficiently constructs permutations from the ground up, choosing each new set of partial permutations based on the criteria of what is feasible from the given edge lengths, eventually finishing with a set of permutations whose members fix every edge length.Notice that we have removed the need for an ambient space by dealing only with edge lengths. Thus the same algorithm works equally well for graphs, directed graphs, and even arc-colored, vertex-colored directed graphs.
The algorithm's time order is difficult to analyze since it depends strongly upon the data given. For N vertices, the worst case is N-factorial time for maximally symmetric data (the symmetric group SN), while the best case is relatively constant time for minimally symmetric data (the 1-element identity group). However this assumes the data has already been read; overall I would estimate the algorithm to be N2 (since we must consider all edges) multiplied by the group order.
Anecdotal examples seem promising thus far. The symmetry group of the 600-cell four-dimensional polytope (group size of 14400) is found in about 2 seconds on my little 1.5Ghz Athlon. The symmetry group of the 6-dimensional cube is also found in about 2 seconds (group size of 46080).