Graph isomorphism visualizations

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.

Shrinking text to the width of other text in latex

This snippet will shrink the text of the first argument to be the width of the second argument. For instance, \shrinktowidthof{AA}{A} will give you two small 'AA's. The if statement means it'll only happen if the first argument is wider than the second, so \shrinktowidthof{a}{A} will just output a normal 'a'. I believe this uses the ifthen, calc, and xstring packages. You also need to do \newlength{\scaleratio} somewhere.

\newcommand{\shrinktowidthof}[2] {
  \setlength{\scaleratio} {
    {1.0pt * \ratio{\widthof{#2}}{\widthof{#1}}}
  }
  \ifthenelse{\lengthtest{\scaleratio < 1.0pt}} {
    \setlength{\scaleratio}{\scaleratio}
    \tokenize{\tokenized}{\the\scaleratio}
    \StrBefore{\tokenized}{pt}[\result]
    \scalebox{\result}{#1}
  } {
    #1
  }
}