Package dev.roanh.gmark.util

Class EdgeGraph

java.lang.Object

dev.roanh.gmark.util.UniqueGraph<EdgeGraphData,Void>

dev.roanh.gmark.util.EdgeGraph

public class EdgeGraph
extends UniqueGraph<EdgeGraphData,Void>

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:

• SchemaGraph
• EdgeGraphData

Nested Class Summary

Nested classes/interfaces inherited from class dev.roanh.gmark.util.UniqueGraph

UniqueGraph.GraphEdge<V,E>, UniqueGraph.GraphNode<V,E>

Field Summary

Fields

Modifier and Type	Field	Description
private int	baseMax	Length of the longest path actually used to construct the initial edge graph.
private int	baseMin	Length of the shortest path actually used to construct the initial edge graph.
private int	maxLen	The maximum length of paths to use to construct the graph.
private UniqueGraph.GraphNode<EdgeGraphData,Void>	src	The source node of all paths used to construct the edge graph.
private UniqueGraph.GraphNode<EdgeGraphData,Void>	trg	The target node of all paths used to construct the edge graph.

Constructor Summary

Constructors

Constructor	Description
EdgeGraph(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 Type	Method	Description
private void	addPath(Deque<UniqueGraph.GraphEdge<SelectivityType,Predicate>> path)	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.
List<UniqueGraph.GraphNode<EdgeGraphData,Void>>	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>	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.
int	getBaseMaximum()	Gets the length of the longest path used to construct the initial edge graph.
int	getBaseMinimum()	Gets the length of the shortest path used to construct the initial edge graph.
int	getMaxLength()	Gets that maximum length of paths used to construct the edge graph.
UniqueGraph.GraphNode<EdgeGraphData,Void>	getSource()	Gets the source node of the edge graph.
UniqueGraph.GraphNode<EdgeGraphData,Void>	getTarget()	Gets the target node of the edge graph.
void	printPath()	Randomly draws a path from the edge graph using drawPath() and prints it to standard output.
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.
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.
private Deque<EdgeGraphData>	reverseToSource(UniqueGraph.GraphEdge<EdgeGraphData,Void> edge)	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

Methods inherited from class java.lang.Object

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

Field Details

src

private UniqueGraph.GraphNode<EdgeGraphData,Void> src

The source node of all paths used to construct the edge graph.

trg

private UniqueGraph.GraphNode<EdgeGraphData,Void> trg

The target node of all paths used to construct the edge graph.

maxLen

private int maxLen

The maximum length of paths to use to construct the graph.

baseMin

private int baseMin

Length of the shortest path actually used to construct the initial edge graph.

baseMax

private int baseMax

Length 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(SchemaGraph, int, SelectivityType, SelectivityType, int)

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:

• EdgeGraph(SchemaGraph, int, SelectivityType, SelectivityType)

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

public UniqueGraph.GraphNode<EdgeGraphData,Void> 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

public UniqueGraph.GraphNode<EdgeGraphData,Void> 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:

• drawPath()
• drawPath(int)

printPath

public void printPath()

Randomly draws a path from the edge graph using drawPath() and prints it to standard output.

See Also:

• drawPath()

drawPath

public List<UniqueGraph.GraphNode<EdgeGraphData,Void>> 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(int)
• getMaxLength()

drawPath

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. 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:

• drawPath()
• getMaxLength()

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(Deque)

addPath

private void addPath(Deque<UniqueGraph.GraphEdge<SelectivityType,Predicate>> path)

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:

• computeAllPaths(java.util.Deque<dev.roanh.gmark.util.UniqueGraph.GraphEdge<dev.roanh.gmark.util.SelectivityType, dev.roanh.gmark.core.graph.Predicate>>, dev.roanh.gmark.util.SchemaGraph, int, dev.roanh.gmark.util.UniqueGraph.GraphNode<dev.roanh.gmark.util.SelectivityType, dev.roanh.gmark.core.graph.Predicate>, dev.roanh.gmark.util.UniqueGraph.GraphNode<dev.roanh.gmark.util.SelectivityType, dev.roanh.gmark.core.graph.Predicate>)

findParallel

private Set<EdgeGraphData.IntersectionData> 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:

• reverseParallel(dev.roanh.gmark.util.UniqueGraph.GraphNode<dev.roanh.gmark.util.EdgeGraphData, java.lang.Void>)
• reverseIdentity(dev.roanh.gmark.util.UniqueGraph.GraphNode<dev.roanh.gmark.util.EdgeGraphData, java.lang.Void>)

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:

• reverseToSource(dev.roanh.gmark.util.UniqueGraph.GraphEdge<dev.roanh.gmark.util.EdgeGraphData, java.lang.Void>)

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

private Deque<EdgeGraphData> reverseToSource(UniqueGraph.GraphEdge<EdgeGraphData,Void> edge)

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.