Package dev.roanh.cpqindex

Class Nauty

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

  • Constructor Details

    • Nauty

      public Nauty()

  • Method Details

    • computeCanonicalLabelling

      public static int[] computeCanonicalLabelling(Nauty.ColoredGraph graph)
      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 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:
      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

      protected static int[] prepareColors(Nauty.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.