Joakim Grahl Knudsen

UiB : MatNat : Informatikk : Selmer Center

Nauty C++ wrapper class

For my 2010 PhD thesis, I wrote a wrapper class to simplify (at least for me) the use of the graph automorphism software package Nauty (which is C code) from within C++ code.

The source code for this "wgraph" is available on request. I'm working on cleaning it up a bit, making it more useful, so please let me know if you could use some of this and/or would want to help.

The Nauty graph (adjacency matrix) format is implemented as an array of unsigned ints, where the most significant bits are used to pack in the bits (i.e., edges of the graph). This way, the graph can also be represented as a printable string of ASCII characters, in a format called graph6. This format is adapted for compact encoding of bipartite graphs, using the parity check matrix of the associated linear code. If the adjacency matrix of the n-node bipartite graph is,

G = [0 H][H^T 0]

(where H^T means the transpose of submatrix H), the parity check matrix is H. H is then a m x N matrix. If H can be written as

H = [I P]

where I is a m x m identity matrix, the matrix is in systematic form. This "H-part" of G can be represented compactly using a proposed "bing format" (bipartite Nauty graph), and also listed out as a string similar to graph6.
We also propose a "row-canonical" representation of a parity-check matrix (see ngCanonise method, below) which allows comparison of bing's (matrices) up to row-equivalence.

The "wgraph" source code has several operators overloaded, and allows

H[j][i] = 1

assignment and

H[j][i] == 1

conditional testing.

Furthermore, several helper methods are written to implement various (more or less) useful functions within linear algebra and coding theory (as well as some other stuff):

```
	addI	
```
Adds
```
m x m
```
identity submatrix (to the left or right of the parity check matrix)
```
	all_edges	
```
```
	array_to_ng	
```
```
	bing_to_ng	
```
```
	bing_to_simplegraph *	
```
```
	canonise *	
```
```
	checkSyndrome	
```
```
	copy_graph	
```
```
	count46cycles	
```
```
	count4cycles	
```
```
	delI	
```
```
	empty_row	
```
```
	expand	
```
```
	expand_ng	
```
```
	FindColPerms	
```
```
	findN	
```
```
	flip	
```
```
	getPT	
```
```
	getRow	
```
```
	HammingDistance	
```
```
	HammingWeight	
```
```
	initMLD	
```
```
	is_member	
```
```
	iset	
```
```
	MLD	
```
```
	nauty_biplabel *	
```
```
	nauty_putam	
```
```
	neut_graph	
```
```
	neut_row	
```
```
	ng_AND	
```
```
	ng_compare	
```
```
	ng_flipBit	
```
```
	ng_graphsize	
```
```
	ng_OR	
```
```
	ng_setBit	
```
```
	ng_sizelen	
```
```
	ng_to_array	
```
```
	ng_to_bing	
```
```
	ng_to_matrix	
```
```
	ng_to_sg	
```
```
	ng_XOR	
```
```
	ngCanonise	
```
```
	ngHeader	
```
```
	ngPivot	
```
```
	ngSwap	
```
```
	ngSwapRows	
```
```
	ngtog6	
```
```
	permute	
```
```
	print_bits	
```
```
	print_ng	
```
```
	print_ngRow	
```
```
	reduce	
```
```
	sg_to_ng	
```
```
	sort	
```
```
	stobing	
```
```
	stong	
```
```
	testGVBound	
```
```
	transpose	
```

Updated April 2016, J. G. Knudsen

spam blocker - help fight spam email!