Package dev.roanh.cpqindex
Class Nauty
java.lang.Object
dev.roanh.cpqindex.Nauty
This class provides and interface to the native binding for nauty.

Nested Class Summary

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionstatic int[]
Computes a canonical labelling of the given coloured graph.protected static int[]
computeCanonSparse
(int[][] adj, int[] colors) Performs a canonical labelling of the given input graph.protected static int[]
prepareColors
(Nauty.ColoredGraph graph) Computes a nauty and traces compatible array of color data.

Constructor Details

Nauty
public Nauty()


Method Details

computeCanonicalLabelling
Computes a canonical labelling of the given coloured graph. The labelling is returned as an array of integers showing how to relabel the vertices in the graph. Each index of this array contains the ID of the vertex that previously had the ID of that index in the array. Parameters:
graph
 The graph to compute a canonical labelling of. Returns:
 The computed relabelling mapping.

computeCanonSparse
protected static int[] computeCanonSparse(int[][] adj, int[] colors) Performs a canonical labelling of the given input graph. Parameters:
adj
 The input graph in adjacency list format,n
arrays with each the indices of the neighbours of then
th vertex.colors
 The array containing raw color information data. Contains vertex indices in blocks of the same color with the start of a block of the same color being indicated by a negated value. All vertex indices are also always one higher than their actual index in the graph. Returns:
 A canonical relabelling of the graph returned as an array of integers showing how to relabel the vertices in the graph. Each index of this array contains the ID of the vertex that previously had the ID of that index in the array.

prepareColors
Computes a nauty and traces compatible array of color data. The returned array will have consecutive sections of nodes with the same color. The node is indicated with a number one higher than the ID of the actual it corresponds to. Negated number indicate the end of a range of nodes with the same color. Parameters:
graph
 The coloured graph to compute color data from. Returns:
 The constructed colour data.
