Here are some visualizations of a naive search for a canonical labeling and the generators of the automorphism group of the isomorphs of the graph a--b--c. Its generators are {(a c)} and its isomorphs are (in order of smallest to largest) b--a--c, a--b--c, and a--c--b.
In order here means sorted by their edge-sets lexicographically, so that {ab, ac} < {ab, bc} < {ac, cb}. This ordering happens to be the same as concatenating the rows of the graph's adjacency matrix to form a 9-bit binary number and then preferring the larger number.
Naive means that
- there is no refinement (i.e. degree partitioning or anything like that) and
- the weakest node-invariant is used (nothing on non-leaf nodes, and the adjacency-matrix on leaf nodes) and
- there is no automorphism pruning.
This amounts to enumerating all permutations.
Here are the search trees for
- b--a--c,
- a--b--c, and
- a--c--b.
Here's a guide on how to read the trees
- Traverse the tree in a depth-first left-to right manner
- Begin with all of the vertices in their own partition
- Individualize the smallest unindividualized vertex (and repeat)
- Bold lines indicate a "better" invariant is found
- Dashed lines between nodes indicate a "worse" invariant is found
- Normal lines indicate an identical invariant is found, which corresponds to an automorphism
- Dashed lines between vertices in a partition indicate that they "should" be split (they are in different orbits)
- This is pretty cool (the divisions are not known until after the algorithm terminates, so it's blatantly cheating), and shows explicitly why different paths lead to different adjacency matrices.
- The divisions are not known until after the search terminates, so it's blatantly cheating.
- This is also probably the most confusing part (partly because it overloads the dashed line), but I think the concept is really helpful in understanding what's going on.
