dev.roanh.cpqkeys.algo

Class Traces

java.lang.Object

dev.roanh.cpqkeys.algo.Traces

public class Traces
extends java.lang.Object

Binding for Traces.

See Also:

Nauty website

Field Summary

Fields

Modifier and Type	Field and Description
static Algorithm	INSTANCE Algorithm binding for traces.

Constructor Summary

Constructors

Constructor and Description
Traces()

Method Summary

Modifier and Type	Method and Description
private static long[]	computeCanon(dev.roanh.gmark.util.Graph<dev.roanh.gmark.conjunct.cpq.QueryGraphCPQ.Vertex,dev.roanh.gmark.core.graph.Predicate> input) Runs Traces on the given input graph.
private static long[]	computeCanon(int[][] adj, int[] colors) Computes the canonical form of the given coloured graph using traces.

Methods inherited from class java.lang.Object

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

Field Detail

INSTANCE

public static final Algorithm INSTANCE

Algorithm binding for traces.

Constructor Detail

Traces

public Traces()

Method Detail

computeCanon

private static long[] computeCanon(dev.roanh.gmark.util.Graph<dev.roanh.gmark.conjunct.cpq.QueryGraphCPQ.Vertex,dev.roanh.gmark.core.graph.Predicate> input)

Runs Traces on the given input graph. The input graph is first converted to an undirected graph, then has its edge labels converted to nodes and is then converted to a coloured graph and has all its edges duplicated (undirected edges are represented as bidirectional edges).

Parameters:

input - The input graph.

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.

computeCanon

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

Computes the canonical form of the given coloured graph using traces. 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.