class ExecutionGraph extends java.lang.Object
Represents a directed acyclic graph (DAG) for defining pipeline stage dependencies and scheduling them in a parallel topological-sort order. An ExecutionGraph is constructed by passing sets of arcs (aka edges/branches) that may or may not intersect on common nodes.
a w z
⇘ ⇙
b x
⇙ ⇘ ⇙
c y
⇘ ⇙
d
Can be constructed any number of ways as long as all the arcs are
represented in the given sets.
def graph = ExecutionGraph([
["a", "b", "c", "d"], // defines edges a → b, b → c, c → d
["w", "b", "y"], // defines edges w → b, b → y
["x", "y", "d"], // defines edges x → y, y → d
["z"], // defines no edge but an isolate node
])
def graph = ExecutionGraph([
["a", "b", "y"],
["w", "b", "c", "d"],
["x", "y"],
["z"],
])
graph.stack().each { println it.join("|") }
Would output:
a|w|z b|x c|y d
Modifiers | Name | Description |
---|---|---|
protected java.util.Set |
isolates |
Set of graph isolates, nodes that are unconnected from all other nodes. |
protected java.util.Map |
progression |
Map of graph progression, nodes and their successor (out) nodes. |
protected java.util.Map |
recession |
Map of graph recession, nodes and their predecessor (in) nodes. |
Constructor and description |
---|
ExecutionGraph
(java.util.List arcs) Constructs a directed execution graph using the given sets of edge sequences (arcs). |
Type Params | Return Type | Name and description |
---|---|---|
|
protected void |
addArc(java.util.List arc) |
|
void |
addIsolate(java.lang.Object isolate) Appends a new arc of nodes to the graph. |
|
void |
addSuccession(java.lang.Object predecessor, java.lang.Object successors) |
|
java.util.Set |
ancestorsOf(java.lang.Object node) All ancestors of (nodes eventually leading to) the given node. |
|
boolean |
equals(ExecutionGraph other) Whether the given graph is equal to this one. |
|
int |
inDegreeOf(java.lang.Object node) The number of nodes that lead directly to the given one. |
|
java.util.Set |
inTo(java.lang.Object node) The nodes that lead directly to the given one. |
|
java.util.Set |
leaves() Returns all nodes that have no outgoing edges. |
|
java.util.Set |
nodes() All nodes in the graph. |
|
ExecutionGraph |
or(ExecutionGraph other) Returns a union of this graph and the given one. |
|
int |
outDegreeOf(java.lang.Object node) The number of nodes the given one directly leads to. |
|
java.util.Set |
outOf(java.lang.Object node) The nodes the given one directly leads to. |
|
ExecutionGraph |
plus(ExecutionGraph other) Returns a concatenation of this graph and the given one. |
|
java.util.Set |
roots() Returns all nodes that have no incoming edges. |
|
java.util.List |
stack() Returns each concurrent node "frames" of the graph in a topological sort order. |
|
java.lang.String |
toString() A string representation of the graph compatible with dot . |
Methods inherited from class | Name |
---|---|
class java.lang.Object |
java.lang.Object#wait(long), java.lang.Object#wait(long, int), java.lang.Object#wait(), java.lang.Object#equals(java.lang.Object), java.lang.Object#toString(), java.lang.Object#hashCode(), java.lang.Object#getClass(), java.lang.Object#notify(), java.lang.Object#notifyAll() |
Set of graph isolates, nodes that are unconnected from all other nodes.
Map of graph progression, nodes and their successor (out) nodes.
progression
.
a w z [
⇘ ⇙ a:[b], w:[b],
b x
⇙ ⇘ ⇙ b:[c, y], x:[y],
c y
⇘ ⇙ c:[d], y:[d],
d ]
Map of graph recession, nodes and their predecessor (in) nodes. Allows for efficient backward traversal.
recession
.
a w z [
⇘ ⇙ b:[a, w],
b x
⇙ ⇘ ⇙ c:[b], y:[b, x],
c y
⇘ ⇙ d:[c, y],
d ]
Constructs a directed execution graph using the given sets of edge sequences (arcs).
Appends a new arc of nodes to the graph.
a
⇘
b
⇘
c
Appended with graph << ["x", "b", "y", "z"]
becomes.
a x
⇘ ⇙
b
⇙ ⇘
y c
⇘
z
All ancestors of (nodes eventually leading to) the given node.
Whether the given graph is equal to this one.
The number of nodes that lead directly to the given one.
The nodes that lead directly to the given one.
Returns all nodes that have no outgoing edges.
All nodes in the graph.
Returns a union of this graph and the given one.
The number of nodes the given one directly leads to.
The nodes the given one directly leads to.
Returns a concatenation of this graph and the given one.
Returns all nodes that have no incoming edges.
Returns each concurrent node "frames" of the graph in a topological sort order. See ExecutionGraph for examples. A java.lang.RuntimeException will be thrown in the event a graph cycle is detected.
A string representation of the graph compatible with dot
.
$ echo "[graph.toString() value]" | dot -Tsvg > graph.svg