The visualization component takes as inputs
matrix- A N x M matrix where N is the number of columns and M is the number of rows. Each element of the matrix specifies the i of building block to render.
workflowVisData- A datastructure that represents the graph of all the workflow steps with information on how they are connected and the distance between the node and the root of the graph (assumed to be a directed acyclic graph (DAG)).
matrix is created from
workflowVisData as follows:
Initialize a N x M
matrix. N is longest path in the DAG (
workflowStepOrderis pre-calculated for each node in the graph which provides the path of the node from the root node). M is calculated from the largest frequency of
matrixis initialized with
matrixwith nodes (BFS of on the
workflowVisData). Each time we loop, a node is placed into the matrix and its children are added to the
toExplorequeue to be placed into the matrix in the future. Additionally, two hash maps are created during this process:
nodeIdToCoordmaps nodeId to its encoded
colNum, rowNumstring representing the node's position in the matrix.
nodeToParentCoordsmaps nodeId of a node to an array of the coordinates (encoded
colNum, rowNumstring) of all the node's parents in the matrix.
matrixwith connectors using the hash map generated from the previous step.
Populate Matrix In Depth
There are three major considerations to placing the nodes into the matrix:
Order of visiting the nodes
The order in which we explore the nodes is critical to the correctness of the visualization. Because our algorithm places a node into the matrix every time we loop, it's making a myopic and irrevocable decision that has consequences down the line that would affect the quality of the visualization. Our goal is to minimize the number of intersecting lines in our visualization. the following techniques are employed to achieve this goal:
toExplore queue is maintained as a priority queue (minHeap), with the priority being
priority = -1 / (workflowStepOrder + childOrder)
workflowStepOrderis the number that indicates the distance of the current node from the root node of the visualization and
chilrenOrderis a number between
1which indicates the order in which we will explore the children of a node.
The smaller the priority, the earlier we place the node into the matrix.
How do we determine
childOrder? Given a
children array. There are two cases:
- When the node is not a decision step, it has exactly one child. so the
- When the node is a decision step (fork step), it can have multiple children. Each child has an attribute called
primary, which indicates if it's the master branch and as such, should be place at the very top of the fork (there can only be one
primarybranch per fork). When there are multiple children. This is the case when the node is a decision step. The
xis the index of the child node in a sorted
childrenarray. To sort the
childrenarray, we look at the graph backward beginning from the sink node where all the branches eventually merge into and creates a tree in which the sink node is the root. Then we look backwards from the sink node create a tree until all our leaves are nodes in our
childrenarray. Using the tree and the
primaryattributes, we start sorting. We begin with the node that is the
primarynode and place it at the front of the array. Then we find the next leaf node that shares the closest ancestor as our
- Naive: The column number of the node is
workflowStepOrder * 2.
The row number of the node is determined as follows:
rowNumis the first unoccupied. Each node is placed into the next empty spot in the column array.
- Better: If no parent,
rowNumis the first unoccupied. If has parent,
rowNumis the parent's
- Even Better: If no parent, rowNum is the first unoccupied. If has parent, rowNum is parent rowNum but if that is occupied, then we shift col 2 places to the right.
- Render connectors for step merge from 2 or more rows away
- Sort workflow steps with the same WorkflowStepOrder - encode that in priority
- Support for when a decision step has the same distance from the root node as another node - need to shift things to the right