Package dev.roanh.gmark.conjunct.cpq
Class QueryGraphCPQ
java.lang.Object
dev.roanh.gmark.conjunct.cpq.QueryGraphCPQ
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.

Nested Class Summary
Modifier and TypeClassDescriptionstatic final class
Represents a directed edge in a CPQ query graph.private static final class
Represents a set of possible mappings for attributes that were processed in the past, but will not be seen again in future tree nodes.private static class
Represents a pair of vertices used for identity processing.private static final class
Object used to store partial mapping required for the query homomorphism testing algorithm.static class
Shared base interface for query graph elements.private static final class
A row instance represents a single potential homomorphism mapping for a partial map.static final class
Represents a vertex in a CPQ query graph. 
Field Summary
Modifier and TypeFieldDescriptionprivate final Set<QueryGraphCPQ.Edge>
The set of edges for this query graph.private Set<QueryGraphCPQ.Pair>
Set of identity pair that still need to be processed, always null for a fully constructed query graph.private long[]
Bit set with true bits corresponding to edge labels that appear somewhere in this graph.private QueryGraphCPQ.Vertex
The source vertex of the CPQ.private QueryGraphCPQ.Vertex
The target vertex of the CPQ.private final Set<QueryGraphCPQ.Vertex>
The set of vertices for this query graph. 
Constructor Summary
ModifierConstructorDescriptionprivate
No args constructor that creates a completely empty query graph.protected
QueryGraphCPQ
(QueryGraphCPQ.Vertex source, QueryGraphCPQ.Vertex target) Constructs a new query graph containing only the given source and target vertex.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. 
Method Summary
Modifier and TypeMethodDescriptionprivate void
Assigns a unique ID to all components of this query graph.Computes the core of this CPQ query graph.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.private void
expandPartialMap
(QueryGraphCPQ.PartialMap data, RangeList<List<QueryGraphCPQ.QueryGraphComponent>> known) Computes the right hand side of the given partial mapping.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.int
Gets the number of edges in this query graph.getEdges()
Gets the set of edges for this query graph.private QueryGraphCPQ.Pair
Gets a single identity pair that still needs to be processed and removes it from the set.Gets the query graph source vertex.Gets the query graph target vertex.int
Gets the number of vertices in this query graph.getVertexLabel
(QueryGraphCPQ.Vertex vertex) Computes the label for a vertex in a CPQ query graph.Gets the set of vertices for this query graph.boolean
isHomomorphicTo
(QueryGraphCPQ graph) Computes if there is a query homomorphism from this query graphG
to the given other graphG'
.boolean
isLoop()
Checks if this query graph is a loop, that is, the source and target vertex of this query are the same vertex.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.void
reverse()
Reverses the query graph by swapping the source and target vertex.protected void
setTarget
(QueryGraphCPQ.Vertex target) Sets the target vertex of this CPQ query graph.Computes the incidence graph of this query graph.toString()
Converts this query graph to an actual graph instance.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.

Field Details

vertices
The set of vertices for this query graph. 
edges
The set of edges for this query graph. 
source
The source vertex of the CPQ. 
target
The target vertex of the CPQ. 
fid
Set of identity pair that still need to be processed, always null for a fully constructed query graph. 
labelSet
private long[] labelSetBit set with true bits corresponding to edge labels that appear somewhere in this graph.


Constructor Details

QueryGraphCPQ
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
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
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
Gets the query graph source vertex. Returns:
 The source vertex.

getTargetVertex
Gets the query graph target vertex. Returns:
 The target vertex.

setTarget
Sets the target vertex of this CPQ query graph. Parameters:
target
 The new target vertex.

toUniqueGraph
Converts this query graph to an actual graph instance. Returns:
 The constructed graph instance.

getEdges
Gets the set of edges for this query graph. Returns:
 The set of edges for this query graph.

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
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
Computes if there is a query homomorphism from this query graphG
to the given other graphG'
. This implies that any edge traversal made in this graph can be mimicked in the given other graph. FormallyG > G'
orG
is contained inG'
(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
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
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
Gets a single identity pair that still needs to be processed and removes it from the set. Returns:
 The retrieved identity pair.

getVertexLabel
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

filterNull
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 nonnull elements from the given input array in the same order.
