nauty for your iPhone

How often have you been out somewhere, maybe at a restaurant or pub, and suddenly needed to generate some graphs, or determine the canonical labelling of a graph that has come up in conversation, only to be foiled because you don’t have your laptop with you.

Not often, you might say.

But just in case, here are some instructions for installing geng and nauty on your iPhone, so that you can be fully prepared in case the need suddenly arises.

It’s actually pretty easy to do. Start by installing the app iSH from the App Store – this provides a lightweight version of Linux (Alpine Linux) that you can interact with through the normal Unix command-line interface. (This is not just a terminal app making a connection to a remote server – it is actually Linux running on your iDevice.)

Conveniently, it supplies some extra keys on its virtual keyboard, including “tab” (for tab-completion), “ctrl” (for ctrl-C, etc) “esc” (for toggling modes in vi) and a key that is used like a 4-way rocker to replace the arrow keys (just drag your finger right, left, up or down to get the associated key). You may also need to turn on an option called “Disable Screen Dimming” so that the iPhone’s battery saving doesn’t interrupt long running processes like compilation.

Special keys on the iSH terminal

That said, using vi like this is a bit painful, so I used the Mac KeyPad App which you run on the Mac, connect to your iOS device, and then redirects any keystrokes from your Mac keyboard to the iOS device. So editing is now easy.

Next step is to install gcc and associated libraries in order to compile anything. This is easy to do using the iSH/Alpine package manager APK.

$ apk build-base

(Here, I am using the convention that the command-line interface uses a $-sign as a prompt awaiting user input. The actual prompt on your phone/tablet will vary from this, using some combination of the device name and current working directory – mine is “Gordons-iPhone:~#”. In any case, you don’t type the $ but just the command after it.)

Then wait for a while while it connects to the right repositories and downloads and installs the various things. For some reason, I kept getting a spurious message about “Temporary error”, but it seemed to install fine anyway.

Next download the nauty source code using wget direct from Brendan’s webpage, uncompress and extract the files from the tar archive and change into the directory that has just been created. Then run the configure tool to create a makefile.

$ wget http://users.cecs.anu.edu.au/~bdm/nauty/nauty27r3.tar.gz 
$ tar xzf nauty27r3.tar.gz
$ cd nauty27r3
$ ./configure

Now at the moment (i.e., with nauty27r3) this creates a makefile that creates a defective version of geng that crashes, due to the compiler dealing with a particular option incorrectly. So the next step is to edit the makefile manually, and remove the “-march=native” from line 6 of the makefile.

CFLAGS = -O4 -march=native

(Future versions of nauty will work around this problem.)

Now it’s time to go to lunch. Before you go, just start the compilation process.

$ make all

This is very time-consuming, taking about 45 minutes on my iPhone (12 mini), so have a reasonably long lunch. When you get back, it should be done, and now have a fully-functioning version of nauty and geng on an iPhone. (Of course, this works for iPad also.)

So now, I can generate the graphs anywhere and any time!

As you can see from the image, it takes about 4 seconds to generate, but not print out, the graphs on 9 vertices.

Screenshots of nauty in action on iSH

How does this compare to my desktop iMac?

The same task takes 0.08s – about 50 times faster. So “nauty on iOS” is not really going to be very useful on a day-to-day basis, but sometimes it’s fun to do something just because you can.