Package dev.roanh.gmark.lang.cpq

Class QueryGraphCPQ

java.lang.Object
dev.roanh.gmark.lang.cpq.QueryGraphCPQ
public class QueryGraphCPQ extends Object
Object representing the query graph of a CPQ. This is effectively a visual representation of the CPQ as a graph. The implementation for query graph construction is loosely based on an algorithm proposed by Seiji Maekawa. The algorithm for query graph core computation and query homomorphism testing are from my Master's thesis.
See Also:

  • Field Details

    • vertices

      private final Set<QueryGraphCPQ.Vertex> vertices
      The set of vertices for this query graph.

    • edges

      private final Set<QueryGraphCPQ.Edge> edges
      The set of edges for this query graph.

    • source

      private QueryGraphCPQ.Vertex source
      The source vertex of the CPQ.

    • target

      private QueryGraphCPQ.Vertex target
      The target vertex of the CPQ.

    • fid

      private Set<QueryGraphCPQ.Pair> fid
      Set of identity pair that still need to be processed, always null for a fully constructed query graph.

    • labelSet

      private long[] labelSet
      Bit set with true bits corresponding to edge labels that appear somewhere in this graph.

  • Constructor Details

    • QueryGraphCPQ

      protected QueryGraphCPQ(QueryGraphCPQ.Vertex source, QueryGraphCPQ.Vertex target)
      Constructs a new query graph containing only the given source and target vertex. This effectively constructs a query graph for the identity CPQ.
      Parameters:
      source - The CPQ source vertex.
      target - The CPQ target vertex.

    • QueryGraphCPQ

      protected QueryGraphCPQ(Predicate label, QueryGraphCPQ.Vertex source, QueryGraphCPQ.Vertex target)
      Constructs a new query graph for the CPQ containing only a single edge label traversal.
      Parameters:
      label - The label being traversed.
      source - The CPQ source vertex where the edge traversal starts.
      target - The CPQ target vertex where the edge traversal ends.

    • QueryGraphCPQ

      private QueryGraphCPQ()
      No args constructor that creates a completely empty query graph.

  • Method Details

    • reverse

      public void reverse()
      Reverses the query graph by swapping the source and target vertex. Naturally, this changes nothing for graphs that are a loop.
      See Also:

    • getVertexCount

      public int getVertexCount()
      Gets the number of vertices in this query graph.
      Returns:
      The number of vertices in this query graph.

    • getEdgeCount

      public int getEdgeCount()
      Gets the number of edges in this query graph.
      Returns:
      The number of edges in this query graph.

    • union

      protected QueryGraphCPQ union(QueryGraphCPQ other)
      Computes the union of this query graph and the given other query graph by merging the vertex, edge and identity sets. Note that this method does not create a new query graph and instead updates this graph with the data from the given other graph.
      Parameters:
      other - The graph to merge with.
      Returns:
      The computed union graph (equal to this graph).

    • getSourceVertex

      public QueryGraphCPQ.Vertex getSourceVertex()
      Gets the query graph source vertex.
      Returns:
      The source vertex.

    • getTargetVertex

      public QueryGraphCPQ.Vertex getTargetVertex()
      Gets the query graph target vertex.
      Returns:
      The target vertex.

    • setTarget

      protected void setTarget(QueryGraphCPQ.Vertex target)
      Sets the target vertex of this CPQ query graph.
      Parameters:
      target - The new target vertex.

    • toUniqueGraph

      public UniqueGraph<QueryGraphCPQ.Vertex,Predicate> toUniqueGraph()
      Converts this query graph to an actual graph instance.
      Returns:
      The constructed graph instance.

    • getEdges

      public Set<QueryGraphCPQ.Edge> getEdges()
      Gets the set of edges for this query graph.
      Returns:
      The set of edges for this query graph.

    • getVertices

      public Set<QueryGraphCPQ.Vertex> getVertices()
      Gets the set of vertices for this query graph.
      Returns:
      The set of vertices for this query graph.

    • isLoop

      public boolean isLoop()
      Checks if this query graph is a loop, that is, the source and target vertex of this query are the same vertex.
      Returns:
      True if this query graph is a loop.

    • toIncidenceGraph

      public <M> SimpleGraph<QueryGraphCPQ.QueryGraphComponent,M> toIncidenceGraph()
      Computes the incidence graph of this query graph. The incidence graph of a query graph is a graph where both vertices and edges from the query graph are represented as vertices. Edges are only present between an edge nodes and vertex nodes and only if the vertex node represents a vertex that was one of the end points of the edge node in the original query graph.
      Type Parameters:
      M - The graph metadata data type.
      Returns:
      The incidence graph for this graph.
      See Also:

    • isHomomorphicTo

      public boolean isHomomorphicTo(QueryGraphCPQ graph)
      Computes if there is a query homomorphism from this query graph G to the given other graph G'. This implies that any edge traversal made in this graph can be mimicked in the given other graph. Formally G -> G' or G is contained in G' (as a subgraph).
      Parameters:
      graph - The other graph to test for query homomorphism to.
      Returns:
      True when this query graph is query homomorphic to the given graph.
      See Also:

    • computeMappings

      private RangeList<List<QueryGraphCPQ.QueryGraphComponent>> computeMappings(QueryGraphCPQ graph)
      Computes mappings from the vertices and edges of this graph to similar vertices and edges in the other given graph.
      Parameters:
      graph - The graph to compute mappings to.
      Returns:
      The mappings between this graph and the given other graph, if no mappings are found for some vertex or edge then null is returned.

    • expandPartialMap

      private void expandPartialMap(QueryGraphCPQ.PartialMap data, RangeList<List<QueryGraphCPQ.QueryGraphComponent>> known)
      Computes the right hand side of the given partial mapping. Both sides of the mapping are also extended with dependent variables.
      Parameters:
      data - The partial map to expand.
      known - A map of know mappings for individual vertices and edges.

    • computeCore

      public QueryGraphCPQ computeCore()
      Computes the core of this CPQ query graph. The core is the smallest graph query homomorphically equivalent to this CPQ query graph.
      Returns:
      The core of this CPQ query graph.

    • merge

      protected void merge()
      Executes the final merge step of the query graph construction algorithm, this step merges vertices that need to be merged together into the same vertex due to intersections with the identity operation.

    • assignIdentifiers

      private void assignIdentifiers()
      Assigns a unique ID to all components of this query graph.

    • getIdentityPair

      private QueryGraphCPQ.Pair getIdentityPair()
      Gets a single identity pair that still needs to be processed and removes it from the set.
      Returns:
      The retrieved identity pair.

    • getVertexLabel

      public String getVertexLabel(QueryGraphCPQ.Vertex vertex)
      Computes the label for a vertex in a CPQ query graph. Note this graph is technically not labelled but a source and target vertex can be identified (and might be identical).
      Parameters:
      vertex - The vertex to get the label for.
      Returns:
      The label for the given vertex.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • filterNull

      private static final QueryGraphCPQ.Row[] filterNull(QueryGraphCPQ.Row[] data, int nulls)
      Small utility function that returns a copy of the given input array with all null entries removed.
      Parameters:
      data - The input array containing null values.
      nulls - The number of null values in the passed array, if 0 then the input array is returned.
      Returns:
      An array containing all non-null elements from the given input array in the same order.