Package dev.roanh.cpqindex

Class CanonForm

java.lang.Object
dev.roanh.cpqindex.CanonForm
public class CanonForm extends Object
Utility class to compute and represent the canonical form of a CPQ.
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final class 
    CanonForm.CoreHash
    A small wrapper class for binary canonical forms that caches the hash code of the canonical form.
    private static final class 
    CanonForm.LabelData
    Simple object for compiling information on objects with the same label.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final dev.roanh.gmark.conjunct.cpq.CPQ
    cpq
    The CPQ this canonical form was constructed from.
    private final int[][]
    graph
    The adjacency list form of the canonically labelled transformed CPQ query graph.
    private final Map<dev.roanh.gmark.core.graph.Predicate,Integer>
    labels
    A map containing the IDs of vertices with a specific label.
    private static final int
    MAX_LABEL_BITS
    Maximum number of bits that will ever be required to encode a vertex label ID.
    private static final int
    MAX_VERTEX_BITS
    Maximum number of bits that will ever be required to encode a vertex ID.
    private final int
    source
    The vertex ID of the source vertex of the CPQ.
    private final int
    target
    The vertex ID of the target vertex of the CPQ.
    private final boolean
    wasCore
    True if the original input CPQ was a core.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    CanonForm(int source, int target, Map<dev.roanh.gmark.core.graph.Predicate,Integer> labels, int[][] graph, dev.roanh.gmark.conjunct.cpq.CPQ cpq, boolean wasCore)
    Constructs a new canonical form with the given data.

  • Method Summary

    Modifier and Type
    Method
    Description
    static CanonForm
    computeCanon(dev.roanh.gmark.conjunct.cpq.CPQ cpq, boolean isCore)
    Constructs a canonical form for the core of the given CPQ.
    boolean
    equals(Object obj)
     
    dev.roanh.gmark.conjunct.cpq.CPQ
    getCPQ()
    Gets the CPQ this canonical form was constructed from.
    int
    hashCode()
     
    String
    toBase64Canon()
    Computes the Base64 encoded string of toBinaryCanon().
    byte[]
    toBinaryCanon()
    Computes the binary variant of this canonical form.
    static Nauty.ColoredGraph
    toColoredGraph(dev.roanh.gmark.conjunct.cpq.QueryGraphCPQ graph)
    Converts the given input query graph to a coloured graph instance.
    CanonForm.CoreHash
    toHashCanon()
    Computes a wrapped representation of toBinaryCanon() that is more suitable for equality testing.
    String
    toStringCanon()
    Computes the string variant of this canonical form.
    boolean
    wasCore()
    Check if the original input CPQ turned out to be a core.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • MAX_LABEL_BITS

      private static final int MAX_LABEL_BITS
      Maximum number of bits that will ever be required to encode a vertex label ID.
      See Also:

    • MAX_VERTEX_BITS

      private static final int MAX_VERTEX_BITS
      Maximum number of bits that will ever be required to encode a vertex ID.
      See Also:

    • source

      private final int source
      The vertex ID of the source vertex of the CPQ.

    • target

      private final int target
      The vertex ID of the target vertex of the CPQ.

    • labels

      private final Map<dev.roanh.gmark.core.graph.Predicate,Integer> labels
      A map containing the IDs of vertices with a specific label. Note that this is encoded as the length of ranges of IDs with the same label.

    • graph

      private final int[][] graph
      The adjacency list form of the canonically labelled transformed CPQ query graph.

    • cpq

      private final dev.roanh.gmark.conjunct.cpq.CPQ cpq
      The CPQ this canonical form was constructed from.

    • wasCore

      private final boolean wasCore
      True if the original input CPQ was a core.

  • Constructor Details

    • CanonForm

      private CanonForm(int source, int target, Map<dev.roanh.gmark.core.graph.Predicate,Integer> labels, int[][] graph, dev.roanh.gmark.conjunct.cpq.CPQ cpq, boolean wasCore)
      Constructs a new canonical form with the given data.
      Parameters:
      source - The ID of the source vertex.
      target - The ID of the target vertex.
      labels - The IDs of labelled nodes by label.
      graph - The canonically labelled graph.
      cpq - The original CPQ.
      wasCore - True if the original input was a core.

  • Method Details

    • getCPQ

      public dev.roanh.gmark.conjunct.cpq.CPQ getCPQ()
      Gets the CPQ this canonical form was constructed from.
      Returns:
      The CPQ this canonical form was constructed from.

    • wasCore

      public boolean wasCore()
      Check if the original input CPQ turned out to be a core.
      Returns:
      True if the original input was a core.

    • computeCanon

      public static CanonForm computeCanon(dev.roanh.gmark.conjunct.cpq.CPQ cpq, boolean isCore)
      Constructs a canonical form for the core of the given CPQ.
      Parameters:
      cpq - The CPQ to compute a canonical form for.
      isCore - If the given CPQ is guaranteed to be a core.
      Returns:
      The computed canonical form.

    • toColoredGraph

      public static Nauty.ColoredGraph toColoredGraph(dev.roanh.gmark.conjunct.cpq.QueryGraphCPQ graph)
      Converts the given input query graph to a coloured graph instance. This is done by first transforming the graph to an unlabelled graph and then group vertices by label.
      Parameters:
      graph - The input query graph to transform.
      Returns:
      The constructed coloured graph.
      See Also:

    • toStringCanon

      public String toStringCanon()
      Computes the string variant of this canonical form. This representation is human readable, but it is also larger than toBinaryCanon() or toBase64Canon();
      Returns:
      The string form of this canonical form.

    • toBinaryCanon

      public byte[] toBinaryCanon()
      Computes the binary variant of this canonical form. This representation is smaller than the string variant produced by toStringCanon(), but can optionally be encoded in Base64 using toBase64Canon().
      Returns:
      The binary form of this canonical form.

    • toBase64Canon

      public String toBase64Canon()
      Computes the Base64 encoded string of toBinaryCanon().
      Returns:
      The Base64 encoded version of the binary canonical form.

    • toHashCanon

      public CanonForm.CoreHash toHashCanon()
      Computes a wrapped representation of toBinaryCanon() that is more suitable for equality testing.
      Returns:
      The CoreHash wrapped version of the binary canonical form.
      See Also:

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object