dev.roanh.cpqkeys.algo

Class Nauty

java.lang.Object

dev.roanh.cpqkeys.algo.Nauty

public class Nauty
extends java.lang.Object

Binding for Nauty.

See Also:

Nauty website

Field Summary

Fields

Modifier and Type	Field and Description
static Algorithm	DENSE Algorithm binding for the dense version of nauty.
static Algorithm	SPARSE Algorithm binding for the sparse version of nauty.

Constructor Summary

Constructors

Constructor and Description
Nauty()

Method Summary

Modifier and Type	Method and Description
private static long[]	computeCanonDense(int[][] adj, int[] colors) Computes the canonical form of the given coloured graph using the dense version of nauty.
private static long[]	computeCanonSparse(int[][] adj, int[] colors) Computes the canonical form of the given coloured graph using the sparse version of nauty.
protected static int[]	prepareColors(GraphUtil.ColoredGraph graph) Computes a nauty and traces compatible array of color data.
private static long[]	runNauty(dev.roanh.gmark.util.Graph<dev.roanh.gmark.conjunct.cpq.QueryGraphCPQ.Vertex,dev.roanh.gmark.core.graph.Predicate> input, java.util.function.BiFunction<int[][],int[],long[]> version) Runs either the dense or sparse version of nauty on the given input graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DENSE

public static final Algorithm DENSE

Algorithm binding for the dense version of nauty.

SPARSE

public static final Algorithm SPARSE

Algorithm binding for the sparse version of nauty.

Constructor Detail

Nauty

public Nauty()

Method Detail

runNauty

private static long[] runNauty(dev.roanh.gmark.util.Graph<dev.roanh.gmark.conjunct.cpq.QueryGraphCPQ.Vertex,dev.roanh.gmark.core.graph.Predicate> input,
                               java.util.function.BiFunction<int[][],int[],long[]> version)

Runs either the dense or sparse version of nauty on the given input graph. The input graph first has its edge labels converted to nodes, and is then converted to a coloured graph.

Parameters:

input - The input graph.

version - The version of nauty to run, either the dense or sparse version.

Returns:

An array of time measurements containing in the first index the graph transform time, in the second index the native setup time (graph construction) and in the third index the canonization time. All times are in nanoseconds.

prepareColors

protected static int[] prepareColors(GraphUtil.ColoredGraph graph)

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.

computeCanonSparse

private static long[] computeCanonSparse(int[][] adj,
                                         int[] colors)

Computes the canonical form of the given coloured graph using the sparse version of nauty. Returns the time in nanoseconds required for computations.

Parameters:

adj - The input graph in adjacency list format, n arrays with each the indices of the neighbours of the n-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:

An array with two elements, first the time in nanoseconds it took to construct the graph and second the time in nanoseconds it took to compute the canonical form of the graph.

computeCanonDense

private static long[] computeCanonDense(int[][] adj,
                                        int[] colors)

Computes the canonical form of the given coloured graph using the dense version of nauty. Returns the time in nanoseconds required for computations.

Parameters:

adj - The input graph in adjacency list format, n arrays with each the indices of the neighbours of the n-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:

An array with two elements, first the time in nanoseconds it took to construct the graph and second the time in nanoseconds it took to compute the canonical form of the graph.