Package dev.roanh.cpqindex

Class LabelledPath

java.lang.Object
dev.roanh.cpqindex.LabelledPath
public final class LabelledPath extends Object
Represents a path through the graph identified by a source target node pair and a number of label sequences that exist between that node pair. This object is also known as a segment for layers of the index with k > 1.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final LabelledPath
    ancestor
    The ancestor of this segment if any.
    private Index.Block
    block
    After block are computed this is the block this segment is contained in.
    private final SortedSet<LabelSequence>
    labels
    The label sequences that were found that exist between the vertices of the node pair for this path.
    private final Pair
    pair
    The node pair for this labelled path.
    private int
    segHash
    Precomputed hash code value for this segment.
    private int
    segId
    After blocks have been computed this is the ID of the block this segment belong to.
    private final SortedSet<PathPair>
    segs
    For k > 1 segments are constructed by combining segments from previous layers.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LabelledPath(Pair pair, LabelledPath ancestor)
    Constructs a new labelled path with the given pair and ancestor.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addLabel(LabelSequence first, LabelSequence last)
    Adds a new label sequence to this path by concatenating the two given sequences.
    void
    addLabel(dev.roanh.gmark.core.graph.Predicate label)
    Adds a single label to this labelled path.
    void
    addSegment(LabelledPath first, LabelledPath last)
    Adds a new construction segment combination to this segment.
    void
    cacheHashCode()
    Computes and caches the hashcode of this segment to improve sorting performance.
    private <T extends Comparable<T>>
    int
    compare(SortedSet<T> a, SortedSet<T> b)
    Compares two sorted sets of elements.
    int
    compareLabelsTo(LabelledPath other)
    Compares this labelled path against the given other labelled path based on the set of labels.
    int
    comparePathTo(LabelledPath other)
    Compares this segment against the given other segment based on the path pair.
    int
    compareSegmentsTo(LabelledPath other)
    Compares this segment against the given other segment based on the set of segment combinations they were constructed from.
    boolean
    equalLabels(LabelledPath other)
    Tests if the label sequences for this path are equal to the labels for the given other path.
    boolean
    equals(Object obj)
     
    LabelledPath
    getAncestor()
    Gets the ancestor segment for this segment.
    Index.Block
    getBlock()
    Gets the block this segment is in, if set.
    Set<LabelSequence>
    getLabels()
    Gets all the label sequences for this labelled path.
    Pair
    getPair()
    Gets the pair of path for this segment.
    int
    getSegmentId()
    Gets the ID of the block this segment is in.
    Set<PathPair>
    getSegments()
    Gets all segment combinations that create this segment.
    int
    getSource()
    Gets the source vertex of the path for this segment.
    int
    getTarget()
    Gets the target vertex of the path for this segment.
    boolean
    hasAncestor()
    Checks if this segment has an ancestor segment in the previous index layer.
    int
    hashCode()
     
    boolean
    isLoop()
    Tests if this segment is a loop, which means its pair is a loop.
    void
    setBlock(Index.Block block)
    Sets the block for this segment.
    void
    setSegmentId(int id)
    Sets the segment ID for this for segment.
    String
    toString()
     

    Methods inherited from class java.lang.Object

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

  • Field Details

    • pair

      private final Pair pair
      The node pair for this labelled path. All stored label sequences are between the vertices of this pair.

    • labels

      private final SortedSet<LabelSequence> labels
      The label sequences that were found that exist between the vertices of the node pair for this path.

    • segs

      private final SortedSet<PathPair> segs
      For k > 1 segments are constructed by combining segments from previous layers. The combinations of segments this segment was constructed from are in this set.

    • ancestor

      private final LabelledPath ancestor
      The ancestor of this segment if any. The ancestor is the segment in the previous index layer that had the same path pair as this segment.

    • segId

      private int segId
      After blocks have been computed this is the ID of the block this segment belong to. The value will be -1 before that. Segments with equal IDs are in the same block.

    • block

      private Index.Block block
      After block are computed this is the block this segment is contained in.

    • segHash

      private int segHash
      Precomputed hash code value for this segment.

  • Constructor Details

    • LabelledPath

      public LabelledPath(Pair pair, LabelledPath ancestor)
      Constructs a new labelled path with the given pair and ancestor.
      Parameters:
      pair - The path pair for this segment.
      ancestor - The segment in the previous index layer with the same path pair or null.

  • Method Details

    • compareLabelsTo

      public int compareLabelsTo(LabelledPath other)
      Compares this labelled path against the given other labelled path based on the set of labels.
      Parameters:
      other - The other labelled path to compare with.
      Returns:
      A value of 0 if both paths are equal, a value less than 0 if this path is less than the other segment and a value greater than 0 if this path is greater.
      See Also:

    • comparePathTo

      public int comparePathTo(LabelledPath other)
      Compares this segment against the given other segment based on the path pair.
      Parameters:
      other - The other labelled path to compare with.
      Returns:
      A value of 0 if both paths are equal, a value less than 0 if this path is less than the other segment and a value greater than 0 if this path is greater.
      See Also:

    • getLabels

      public Set<LabelSequence> getLabels()
      Gets all the label sequences for this labelled path.
      Returns:
      All label sequence for this labelled path.

    • getPair

      public Pair getPair()
      Gets the pair of path for this segment.
      Returns:
      The path for this segment.

    • getSegments

      public Set<PathPair> getSegments()
      Gets all segment combinations that create this segment.
      Returns:
      All segments for this segment.

    • getAncestor

      public LabelledPath getAncestor()
      Gets the ancestor segment for this segment. The ancestor segment is a segment from the previous index layer with the same path.
      Returns:
      The ancestor segment if any.

    • hasAncestor

      public boolean hasAncestor()
      Checks if this segment has an ancestor segment in the previous index layer. The ancestor segment has an identical path.
      Returns:
      True if this segment has an ancestor.

    • setBlock

      public void setBlock(Index.Block block)
      Sets the block for this segment.
      Parameters:
      block - The block this segment is in.

    • setSegmentId

      public void setSegmentId(int id)
      Sets the segment ID for this for segment. This ID will later determine the ID of the block for this segment.
      Parameters:
      id - The ID for thsi segment.

    • getSource

      public int getSource()
      Gets the source vertex of the path for this segment.
      Returns:
      The source vertex.

    • getTarget

      public int getTarget()
      Gets the target vertex of the path for this segment.
      Returns:
      The target vertex.

    • equalLabels

      public boolean equalLabels(LabelledPath other)
      Tests if the label sequences for this path are equal to the labels for the given other path.
      Parameters:
      other - The other path to compare with.
      Returns:
      True if both paths have identical label sequences.

    • getSegmentId

      public int getSegmentId()
      Gets the ID of the block this segment is in.
      Returns:
      The ID of the block for this segment.

    • getBlock

      public Index.Block getBlock()
      Gets the block this segment is in, if set.
      Returns:
      The block this segment is in.

    • cacheHashCode

      public void cacheHashCode()
      Computes and caches the hashcode of this segment to improve sorting performance.

    • compareSegmentsTo

      public int compareSegmentsTo(LabelledPath other)
      Compares this segment against the given other segment based on the set of segment combinations they were constructed from. Note that cacheHashCode() should either have been called on both segments first or on neither.
      Parameters:
      other - The other segment to compare with.
      Returns:
      A value of 0 if both segments are equal, a value less than 0 if this segment is less than the other segment and a value greater than 0 if this segment is greater.
      See Also:

    • compare

      private <T extends Comparable<T>> int compare(SortedSet<T> a, SortedSet<T> b)
      Compares two sorted sets of elements.
      Type Parameters:
      T - The set data type.
      Parameters:
      a - The first set
      b - The second set.
      Returns:
      A value of 0 if both sets are equal, a value less than 0 if the first set is less than the other set and a value greater than 0 if the first set is greater.

    • addSegment

      public void addSegment(LabelledPath first, LabelledPath last)
      Adds a new construction segment combination to this segment. Note that order matters as the paths are joined.
      Parameters:
      first - The first segment of the combination.
      last - The second segment of the combination.
      See Also:

    • addLabel

      public void addLabel(dev.roanh.gmark.core.graph.Predicate label)
      Adds a single label to this labelled path.
      Parameters:
      label - The label to add.
      See Also:

    • addLabel

      public void addLabel(LabelSequence first, LabelSequence last)
      Adds a new label sequence to this path by concatenating the two given sequences.
      Parameters:
      first - The first label sequence.
      last - The second label sequence to concatenate after the first.
      See Also:

    • isLoop

      public boolean isLoop()
      Tests if this segment is a loop, which means its pair is a loop.
      Returns:
      True if this segment is a loop.
      See Also:

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

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