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
  }
}

Mendeley

Just shared my first collection on Mendeley at Favorites. It's the favorites of my collection (articles on isomorphism and some applications). It's missing a few since I haven't imported everything into Mendeley yet.

Useful hotkeys (for mac)

Switching between windows in the same application: Command + Tilde

See all keyboard shortcuts in eclipse: Command + Shift + L

Word completion in eclipse: Ctrl + .

Template completion: (Ctrl + Space, then Ctrl + Space)

Go do declaration: fn + F3

Go to previous location: Apple + Alt + Left arrow

Go to last edit location: Ctrl + Q

Open type: Apple + Shift + T

Open resource: Apple + Shift + R

Food and drink combinations

Newman's Own Honey Flax Flakes and Silk soy milk go really well together.

Orange juice + cranberry juice is really good too.

Recovering an email attachment in python

To decode an attachment from the text of an email (using python), like:

--------------060805040508050904080009
Content-Type: image/jpeg;
name="img_3282.jpg"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
filename="img_3282.jpg"

/9j/4AAQSkZJRgABAQEASABIAAD/4R5TRXhpZgAASUkqAAgAAAAJAA8BAgAGAAAAegAAABAB
AgAYAAAAgAAAABIBAwABAAAAAQAAABoBBQABAAAAmAAAABsBBQABAAAAoAAAACgBAwABAAAA
... ... ...
gFFdbQfZ9xIfe25gnfGOx+X+VTlt1VxCyMUeItGAec+5/SluCRQmiYhjIuHB27lzjPHP6VZm
059iM/7yJh4gCjsAc445GaSb7h02Da1jkgPgy7EGDuU55Hv+dKrUq5QqP//Z

use the following python script:

#!/usr/bin/env python

import sys
import mimetools

def main():
        infile = open(sys.argv[1], 'r')
        outfile = open(sys.argv[2], 'wb')
        mimetools.decode(infile, outfile, 'base64')
        print 'Greg is a bunneh.'

if __name__ == "__main__":
        main()

and you will recover your attachment (for me it was the following image (i didn't catch the disk even though the photo indicates i did) ).

Second blog post ever!