Package dev.roanh.gmark.util
Class EdgeGraph
The edge graph is a graph constructed from an input graph such that
all edges in the original input graph are nodes in the edge graph. In
addition, nodes are connected when there exists a node between them in
the original graph. The purpose of the edge graph is to encode all
possible paths between two preselected nodes in the input graph. For
this purpose two special nodes are added to the edge graph to represent
the source and target. All paths in the edge graph must originate from
the source node and end at the target node.
 See Also:

Nested Class Summary
Nested classes/interfaces inherited from class dev.roanh.gmark.util.UniqueGraph
UniqueGraph.GraphEdge<V,
E>, UniqueGraph.GraphNode<V, E> 
Field Summary
Modifier and TypeFieldDescriptionprivate int
Length of the longest path actually used to construct the initial edge graph.private int
Length of the shortest path actually used to construct the initial edge graph.private int
The maximum length of paths to use to construct the graph.private UniqueGraph.GraphNode<EdgeGraphData,
Void> The source node of all paths used to construct the edge graph.private UniqueGraph.GraphNode<EdgeGraphData,
Void> The target node of all paths used to construct the edge graph. 
Constructor Summary
ConstructorDescriptionEdgeGraph
(SchemaGraph gs, int maxLen, SelectivityType source, SelectivityType target) Constructs a new edge graph from the given schema graph.EdgeGraph
(SchemaGraph gs, int maxLen, SelectivityType source, SelectivityType target, int recursion) Constructs a new edge graph from the given schema graph. 
Method Summary
Modifier and TypeMethodDescriptionprivate void
Adds the given path drawn from the schema graph to the edge graph where the edge in the drawn path are converted to nodes and the path is attached to the edge graph source and target nodes.private void
computeAllPaths
(Deque<UniqueGraph.GraphEdge<SelectivityType, Predicate>> path, SchemaGraph gs, int maxLen, UniqueGraph.GraphNode<SelectivityType, Predicate> source, UniqueGraph.GraphNode<SelectivityType, Predicate> target) Computes all paths from the given source node to the given target node in the schema graph that at most the given max length.drawPath()
Draws a random path from the edge graph that starts at the edge graph source node and ends at the edge graph target node.protected List<UniqueGraph.GraphNode<EdgeGraphData,
Void>> drawPath
(int minLen) Draws a random path from the edge graph that starts at the edge graph source node and ends at the edge graph target node.private Set<EdgeGraphData.IntersectionData>
Attempts to find paths in the graph that can be used for an intersection with some other path in the graph or with identity.int
Gets the length of the longest path used to construct the initial edge graph.int
Gets the length of the shortest path used to construct the initial edge graph.int
Gets that maximum length of paths used to construct the edge graph.Gets the source node of the edge graph.Gets the target node of the edge graph.void
Randomly draws a path from the edge graph usingdrawPath()
and prints it to standard output.private EdgeGraphData.IntersectionData
Attempts to find a section of a path from the given target node to the source node that can be intersected with identity.private EdgeGraphData.IntersectionData
Attempts to find two distinct paths from the given node back to the source node of the graph.private Deque<EdgeGraphData>
Reverses a path from the given edge all the way to source node of the graph.Methods inherited from class dev.roanh.gmark.util.UniqueGraph
addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueEdge, addUniqueNode, copy, getEdge, getEdge, getEdgeCount, getEdges, getNode, getNodeCount, getNodes, removeNodeIf, toAdjacencyList

Field Details

src
The source node of all paths used to construct the edge graph. 
trg
The target node of all paths used to construct the edge graph. 
maxLen
private int maxLenThe maximum length of paths to use to construct the graph. 
baseMin
private int baseMinLength of the shortest path actually used to construct the initial edge graph. 
baseMax
private int baseMaxLength of the longest path actually used to construct the initial edge graph.


Constructor Details

EdgeGraph
public EdgeGraph(SchemaGraph gs, int maxLen, SelectivityType source, SelectivityType target) throws GenerationException Constructs a new edge graph from the given schema graph. The edge graph is built up using all paths of at most the given maximum length between the given source and target node in the schema graph. Drawn paths will then be recursively intersected up to a maximum recursive depth of 5. Parameters:
gs
 The schema graph.maxLen
 The maximum length of paths to draw from the schema graph.source
 The schema graph source node.target
 The schema graph target node. Throws:
GenerationException
 When there are no paths between the given source and target node. See Also:

EdgeGraph
public EdgeGraph(SchemaGraph gs, int maxLen, SelectivityType source, SelectivityType target, int recursion) throws GenerationException Constructs a new edge graph from the given schema graph. The edge graph is built up using all paths of at most the given maximum length between the given source and target node in the schema graph. Drawn paths will then be recursively intersected up to the given maximum recursive depth. Parameters:
gs
 The schema graph.maxLen
 The maximum length of paths to draw from the schema graph.source
 The schema graph source node.target
 The schema graph target node.recursion
 The maximum recursive depth. Throws:
GenerationException
 When there are no paths between the given source and target node. See Also:


Method Details

getBaseMinimum
public int getBaseMinimum()Gets the length of the shortest path used to construct the initial edge graph. Returns:
 The length of the shortest construction path.

getBaseMaximum
public int getBaseMaximum()Gets the length of the longest path used to construct the initial edge graph. Returns:
 The length of the longest construction path.

getSource
Gets the source node of the edge graph. Every node in the edge graph can be reached from the source node. Returns:
 The edge graph source node.

getTarget
Gets the target node of the edge graph. The target node is reachable by every node in the edge graph. Returns:
 The edge graph target node.

getMaxLength
public int getMaxLength()Gets that maximum length of paths used to construct the edge graph. This value is also used to bound the length of paths drawn from the edge graph. Returns:
 The maximum path length.
 See Also:

printPath
public void printPath()Randomly draws a path from the edge graph usingdrawPath()
and prints it to standard output. See Also:

drawPath
Draws a random path from the edge graph that starts at the edge graph source node and ends at the edge graph target node. The length of the path will be at least 1 and at most configured edge graph maximum length. Returns:
 The randomly drawn path.
 See Also:

drawPath
Draws a random path from the edge graph that starts at the edge graph source node and ends at the edge graph target node. The length of the path will be at least the given minimum length and at most configured edge graph maximum length. Care should be taken when passing large values for the minimum length as they might cause a valid to path to never be found. Parameters:
minLen
 The minimum length of the drawn path. Returns:
 The randomly drawn path.
 See Also:

computeAllPaths
private void computeAllPaths(Deque<UniqueGraph.GraphEdge<SelectivityType, Predicate>> path, SchemaGraph gs, int maxLen, UniqueGraph.GraphNode<SelectivityType, Predicate> source, UniqueGraph.GraphNode<SelectivityType, Predicate> target) Computes all paths from the given source node to the given target node in the schema graph that at most the given max length. These paths are then added to the edge graph with their edges converted to nodes. Parameters:
path
 The empty path deque to pass information between recursive calls of this subroutine.gs
 The schema graph.maxLen
 The maximum path length from source to target.source
 The source node in the schema graph.target
 The target node in the schema graph. See Also:

addPath
Adds the given path drawn from the schema graph to the edge graph where the edge in the drawn path are converted to nodes and the path is attached to the edge graph source and target nodes. Parameters:
path
 The path to add to the edge graph. See Also:

findParallel
Attempts to find paths in the graph that can be used for an intersection with some other path in the graph or with identity. The intersections that are found are then returned. Returns:
 The found intersections that could be made.
 See Also:

reverseIdentity
private EdgeGraphData.IntersectionData reverseIdentity(UniqueGraph.GraphNode<EdgeGraphData, Void> target) Attempts to find a section of a path from the given target node to the source node that can be intersected with identity. This is done by reversing a path from the given target node to the source node of the graph and then checking for each path node if it is of the same type as the target node. If such a path node is found then data for an intersection is returned if the final selectivity of the path is at most linear. Parameters:
target
 The target node to find identity intersections for. Returns:
 The data for an identity intersection if it was found or
null
otherwise.  See Also:

reverseParallel
private EdgeGraphData.IntersectionData reverseParallel(UniqueGraph.GraphNode<EdgeGraphData, Void> target) Attempts to find two distinct paths from the given node back to the source node of the graph. If two paths are found then the identical prefix path is removed from both paths. This leaves two paths that can start from the same node and end at the given target node. These two paths are returned as the intersection data together with these shared source and target nodes. Parameters:
target
 The target node to find parallel paths to. Returns:
 Data about two parallel paths or
null
if two paths like that were not found.

reverseToSource
Reverses a path from the given edge all the way to source node of the graph. The returned deque will contain from front to back all the nodes encountered from the source node to a node connected to (out edge) the given edge. The source node itself is not included in the result. Parameters:
edge
 The edge to reverse. Returns:
 A path of nodes leading to the given edge from the source.
