Contents
- Index
NETWORKS>ROLES&POSITIONS>AUTOMORPHIC>ALL PERMUTATIONS
PURPOSE Partitions the vertices of a graph into orbits by exhaustive search.
DESCRIPTION Two vertices u and v of a labeled graph G are automorphically equivalent if all the vertices can be relabeled to form an isomorphic graph with the labels of u and v interchanged. Automorphic equivalence is an equivalence relation and therefore partitions the vertices into equivalence classes called orbits. This routine finds the orbits by examining all possible relabellings of the graph. For a graph of n vertices there are n! possible Permutations of the labels.
PARAMETERS
Input dataset:
Name of file containing network to be analyzed. Data type: Digraph.
(Output) Orbit Dataset (Default = 'AllAutomorphismsOrbits').
Name of output file to contain orbit indicator vector. This vector has the form (k1,k2,...ki...) where ki assigns vertex i to orbit ki, so that (1 1 2 1 2) assigns vertices 1, 2 and 4 to orbit 1 and 3 and 5 to orbit 2. This vector is not displayed in the LOG FILE.
(Output Automorphism Dataset): (Default = AllAutomorphismsAuto').
Name of file which that gives all automorphisms of the graph. The automorphisms are specified in a numbered list with the original labeling at the head. A value of k in row m column n means that for automorphism number m vertex n was relabeled k.This vector is not displayed in the LOG FILE.
LOG FILE The number of Permutations examined.
The number of relabellings that produced an isomorphism.
The percentage of all permutations that produced an isomorphic graph (the hit rate).
A list of the orbits.
TIMING Exponential.
COMMENTS Computation time for this routine is very slow. It is inadvisable to try this on graphs with more than 10 vertices, impossible on graphs with more than 15.
REFERENCES