///
///
/**
* Package for the Render Hierarchy for TensorFlow graph.
*/
module tf.graph.render {
/**
* Color parameters for node encoding.
* @type {Object}
*/
export let MetanodeColors = {
SATURATION: 0.6,
LIGHTNESS: 0.85,
/**
* Neutral color to use when the node is expanded (used when coloring by
* compute time, memory and device).
*/
EXPANDED_COLOR: "#f0f0f0",
/**
* Standard hue values for node color palette.
*/
HUES: [220, 100, 180, 40, 20, 340, 260, 300, 140, 60],
STRUCTURE_PALETTE: function(id: number, lightened? : boolean) {
// The code below is a flexible way to computationally create a set
// of colors that go well together.
let hues = MetanodeColors.HUES;
let n = hues.length;
let hue = hues[id % n];
let m = Math.sin(hue * Math.PI / 360);
let sat = lightened ? 30 : 90 - 60 * m;
let light = lightened ? 95 : 80;
return d3.hsl(hue, .01 * sat, .01 * light).toString();
},
DEVICE_PALETTE: function (index: number): string {
return MetanodeColors.STRUCTURE_PALETTE(index);
},
UNKNOWN: "#eee",
GRADIENT_OUTLINE: "#888"
};
/**
* Parameters that affect how the graph is rendered on the screen.
*/
interface RenderGraphParams {
/**
* Whether to extract high degree nodes from the core part of the graph.
*/
enableExtraction: boolean;
/**
* Maximum in-degree that a node can have without being considered as
* high in-degree node.
*/
maxInDegree: number;
/**
* Maximum out-degree that a node can have without being considered as
* high out-degree node.
*/
maxOutDegree: number;
/**
* Maximum number of control edges a node can have before they aren't
* displayed.
*/
maxControlDegree: number;
/**
* Types patterns for predefined out-extract nodes, which are
* sink-like nodes that will be extracted from the main graph.
*/
outExtractTypes: string[];
/**
* Types patterns for predefined in-extract nodes, which are
* source-like nodes that will be extracted from the main graph.
*/
inExtractTypes: string[];
/**
* When removing edges from a high degree node, remove all of its edges if
* detachAllEdgesForHighDegree is true. Otherwise remove all in-edges if
* the node has high in-degree, or all out-edges if the node has high
* out-degree.
*/
detachAllEdgesForHighDegree: boolean;
/**
* After extracting high in/out degree nodes and predefined
* source-like/sink-like, extract isolated nodes to the side
* if this extractIsolatedNodesWithAnnotationsOnOneSide is true.
*/
extractIsolatedNodesWithAnnotationsOnOneSide: boolean;
/**
* Whether to add bridge nodes and edges to the core when building the
* subhierarchy of an expanded metanode. See buildSubhierarchy().
*/
enableBridgegraph: boolean;
/**
* 2 colors, for the minimum and maximum value respectively, whenever we
* have a gradient scale.
*/
minMaxColors: string[];
/**
* Maximum number of annotations to be displayed on a node.
*/
maxAnnotations: number;
}
/**
* Stores the rendering information, such as x and y coordinates,
* for each node in the graph.
*/
export class RenderGraphInformation {
private hierarchy: hierarchy.Hierarchy;
private index: {[nodeName: string]: RenderNodeInformation};
private params: RenderGraphParams;
private deviceColorMap: d3.scale.Ordinal;
private memoryUsageScale: d3.scale.Linear;
private computeTimeScale: d3.scale.Linear;
// Since the rendering information for each node is constructed lazily,
// upon node's expansion by the user, we keep a map between the node's name and
// whether the rendering information was already constructed for that node.
private hasSubhierarchy: {[nodeName: string]: boolean};
root: RenderGroupNodeInformation;
constructor(hierarchy: hierarchy.Hierarchy, params: RenderGraphParams) {
this.hierarchy = hierarchy;
this.index = {};
this.deviceColorMap = d3.scale.ordinal()
.domain(hierarchy.devices)
.range(_.map(d3.range(hierarchy.devices.length),
MetanodeColors.DEVICE_PALETTE));
let topLevelGraph = hierarchy.root.metagraph;
// Find the maximum and minimum memory usage.
let memoryExtent = d3.extent(topLevelGraph.nodes(),
(nodeName, index) => {
let node = topLevelGraph.node(nodeName);
// Some ops don't have stats at all.
if (node.stats != null) {
return node.stats.totalBytes;
}
});
this.memoryUsageScale = d3.scale.linear()
.domain(memoryExtent)
.range(params.minMaxColors);
// Find also the minimum and maximum compute time.
let computeTimeExtent = d3.extent(topLevelGraph.nodes(), (nodeName, index) => {
let node = topLevelGraph.node(nodeName);
// Some ops don't have stats at all.
if (node.stats != null) {
return node.stats.totalMicros;
}
});
this.computeTimeScale = d3.scale.linear()
.domain(computeTimeExtent)
.range(params.minMaxColors);
// Maps node name to whether the rendering hierarchy was already constructed.
this.hasSubhierarchy = {};
this.params = params;
this.root = new RenderGroupNodeInformation(hierarchy.root);
this.index[hierarchy.root.name] = this.root;
this.buildSubhierarchy(hierarchy.root.name);
this.root.expanded = true;
}
getRenderNodeByName(nodeName: string): RenderNodeInformation {
return this.index[nodeName];
}
/**
* Return the nearest ancestor node, including itself, that is visible
* in the visualization. This method is used so that we can select
* (highlight) a node that isn't drawn yet, by selecting (highlighting)
* its nearest ancestor that has been drawn.
*/
getNearestVisibleAncestor(name: string): string {
let path = getHierarchicalPath(name);
for (let i = 0; i < path.length; i++) {
let nodeName = path[i];
// Op nodes have expanded set to false by default.
if (!this.getRenderNodeByName(nodeName).expanded) {
return nodeName;
}
}
// Fallthrough. If everything was expanded return the node.
return name;
}
// TODO(jimbo): Delete this an any code it touches (all deprecated).
setDepth(depth: number): void {
setGroupNodeDepth(this.root, +depth);
}
buildSubhierarchy(nodeName: string): void {
// Terminate if the rendering hierarchy was already constructed
// for this node.
if (nodeName in this.hasSubhierarchy) {
return;
}
let renderNodeInfo = this.index[nodeName];
// If it is not a meta node or a series node, don't do anything.
if (renderNodeInfo.node.type !== NodeType.META &&
renderNodeInfo.node.type !== NodeType.SERIES) {
return;
}
// At this point we know the rendering information is about a group node.
let renderGroupNodeInfo = renderNodeInfo;
let metagraph = renderGroupNodeInfo.node.metagraph;
let coreGraph = renderGroupNodeInfo.coreGraph;
// Create render nodes to represent each child from the metagraph. Although
// these will initially be added to the coreGraph, they may later be
// extracted. Also, due to extraction, the coreGraph may contain disjoint
// groups between which there is no visible path (other than annotations).
_.each(metagraph.nodes(), childName => {
let childNode = metagraph.node(childName);
let childRenderInfo = childNode.isGroupNode ?
new RenderGroupNodeInformation(childNode) :
new RenderNodeInformation(childNode);
this.index[childName] = childRenderInfo;
coreGraph.setNode(childName, childRenderInfo);
if (childRenderInfo.node.stats != null) {
childRenderInfo.memoryColor =
this.memoryUsageScale(childRenderInfo.node.stats.totalBytes);
childRenderInfo.computeTimeColor =
this.computeTimeScale(childRenderInfo.node.stats.totalMicros);
}
if (!childNode.isGroupNode) {
_.each((childNode).inEmbeddings, embedding => {
let renderMetaedgeInfo = new RenderMetaedgeInformation(null);
addInAnnotation(childRenderInfo, embedding, null, renderMetaedgeInfo,
AnnotationType.CONSTANT, this.params);
this.index[embedding.name] = new RenderNodeInformation(embedding);
});
_.each((childNode).outEmbeddings, embedding => {
let renderMetaedgeInfo = new RenderMetaedgeInformation(null);
addOutAnnotation(childRenderInfo, embedding, null, renderMetaedgeInfo,
AnnotationType.SUMMARY, this.params);
this.index[embedding.name] = new RenderNodeInformation(embedding);
});
let device = (childRenderInfo.node).device;
if (device != null) {
childRenderInfo.deviceColors = [{
color: this.deviceColorMap(device),
proportion: 1.0
}];
}
} else {
// Make a list of tuples (device, proportion), where proportion
// is the fraction of op nodes that have that device.
let pairs = _.pairs(( childNode).deviceHistogram);
if (pairs.length > 0) {
// Compute the total # of devices.
let numDevices = _.sum(pairs, _.last);
childRenderInfo.deviceColors = _.map(pairs, pair => {
return {
color: this.deviceColorMap(pair[0]),
// Normalize to a proportion of total # of devices.
proportion: pair[1] / numDevices
};
});
}
}
});
// Add render metaedge info for edges in the metagraph.
_.each(metagraph.edges(), edgeObj => {
let metaedge = metagraph.edge(edgeObj);
let renderMetaedgeInfo = new RenderMetaedgeInformation(metaedge);
coreGraph.setEdge(edgeObj.v, edgeObj.w, renderMetaedgeInfo);
});
if (this.params.enableExtraction &&
renderGroupNodeInfo.node.type === NodeType.META) {
extractHighDegrees(renderGroupNodeInfo, this.params);
}
// Record that we constructed the rendering hierarchy for this node, so we
// don't construct it another time.
this.hasSubhierarchy[nodeName] = true;
// Look up the parent node's render information and short circuit if none.
let parentNode = renderGroupNodeInfo.node.parentNode;
if (!parentNode) {
return;
}
let parentNodeInfo =
this.index[parentNode.name];
// Utility function for computing the name of a bridge node.
let getBridgeNodeName = (inbound, ...rest) =>
rest.concat([inbound ? "IN" : "OUT"]).join("~~");
// Build out the bridgegraph.
let bridgegraph = this.hierarchy.getBridgegraph(nodeName);
// Look for popular nodes so we can make annotations instead of paths.
let otherCounts = {
// Counts of edges coming INTO other nodes by name (outgoing from self).
in: <{[nodeName: string]: number}> {},
// Counts of edges going OUT from other nodes by name (coming into self).
out: <{[nodeName: string]: number}> {},
// Counts of all control edges involving other nodes by name.
control: <{[nodeName: string]: number}> {},
};
_.each(bridgegraph.edges(), e => {
// An edge is inbound if its destination node is in the metagraph.
let inbound = !!metagraph.node(e.w);
let otherName = inbound ? e.v : e.w;
let metaedge = bridgegraph.edge(e);
if (!metaedge.numRegularEdges) {
otherCounts.control[otherName] =
(otherCounts.control[otherName] || 0) + 1;
} else if (inbound) {
otherCounts.out[otherName] = (otherCounts.out[otherName] || 0) + 1;
} else {
otherCounts.in[otherName] = (otherCounts.in[otherName] || 0) + 1;
}
});
// Add annotations and edges for bridgegraph relationships.
let hierarchyNodeMap = this.hierarchy.getNodeMap();
_.each(bridgegraph.edges(), bridgeEdgeObj => {
let bridgeMetaedge = bridgegraph.edge(bridgeEdgeObj);
// Determine whether this bridge edge is incoming by checking the
// metagraph for a node that matches the destination end.
let inbound = !!metagraph.node(bridgeEdgeObj.w);
// Based on the direction of the edge, one endpoint will be an immediate
// child of this renderNodeInfo, and the other endpoint will be a sibling
// of the parent (or an ancestor further up).
let [childName, otherName] =
inbound ?
[bridgeEdgeObj.w, bridgeEdgeObj.v] :
[bridgeEdgeObj.v, bridgeEdgeObj.w];
let childRenderInfo = this.index[childName];
let otherRenderInfo = this.index[otherName];
let otherNode =
otherRenderInfo ?
otherRenderInfo.node :
hierarchyNodeMap[otherName];
// Determine whether this edge is a control edge between nodes where
// either node is high-degree with respect to control edges. This will
// be a signal to show it as an annotation instead of a bridge edge.
let isHighDegreeControlEdge = !bridgeMetaedge.numRegularEdges &&
otherCounts.control[otherName] > this.params.maxControlDegree;
let [annotations, childAnnotations] =
inbound ?
[renderNodeInfo.inAnnotations, childRenderInfo.inAnnotations] :
[renderNodeInfo.outAnnotations, childRenderInfo.outAnnotations];
let isOtherHighDegree =
inbound ?
otherCounts.out[otherName] > this.params.maxOutDegree :
otherCounts.in[otherName] > this.params.maxInDegree;
// The adjoining render metaedge info from the parent's coreGraph, if any.
// It will either be a Metaedge involving this node directly, if it
// previously came from a metagraph, or it'll be a Metaedge involving
// a previously created bridge node standing in for the other node.
let adjoiningMetaedge = null;
// We can only hope to render a bridge path if:
// - bridgegraph paths are enabled,
// - the other node is not too high-degree,
// - the child is in the core (not extracted for being high-degree), and
// - there's a path (in the traversal sense) between child and other.
let canDrawBridgePath = false;
if (this.params.enableBridgegraph &&
!isOtherHighDegree &&
!isHighDegreeControlEdge &&
childRenderInfo.isInCore()) {
// Utility function for finding an adjoining metaedge.
let findAdjoiningMetaedge = targetName => {
let adjoiningEdgeObj: graphlib.EdgeObject =
inbound ?
{ v: targetName, w: nodeName } :
{ v: nodeName, w: targetName };
return
parentNodeInfo.coreGraph.edge(adjoiningEdgeObj);
};
adjoiningMetaedge = findAdjoiningMetaedge(otherName);
if (!adjoiningMetaedge) {
adjoiningMetaedge = findAdjoiningMetaedge(
getBridgeNodeName(inbound, otherName, parentNode.name));
}
canDrawBridgePath = !!adjoiningMetaedge;
}
// Although dataflow edges are acyclic, control dependency edges may
// actually point "backwards" in the graph. If this bridgeMetaedge is
// a control dependency, we need to determine whether it's backwards
// pointing so that we render it appropriately.
//
// For instance, say we're rendering a graph with nodes named A/B and Z/Y,
// and we're currently rendering the bridgegraph for A. Further, let's say
// that there was an original BaseEdge from A/B->Z/Y and a CONTROL EDGE
// from Z/Y=>A/B.
//
// +----------------+
// | A |
// | +-----+ | +------+
// | | B |>----->|>------->| Z |
// | | | | | |
// | | | * | | |
// | | |<=====<|<=======<| |
// | +-----+ | +------+
// +----------------+
//
// When we render the subhierarchy for Metanode A, we'll come across a
// control-only Metaedge in the bridgegraph from Z=>A/B (*). The question
// is whether this edge is backwards.
//
// To answer that question, we follow the chain of adjoining metaedges
// until we reach the topmost one. In this case, that's the control-only
// Metaedge Z=>A in the ROOT's metagraph. We determine that this edge
// is backwards by looking at the topological ordering of ROOT's metagraph
// (which ignores control edges) and seeing that Z comes AFTER A.
//
// The property of being backwards is independent of whether the edge
// is inbound or outbound. In the preceeding example, if we were building
// the subhierarchy for Z, we'd find bridge edge Z/Y=>A, walk to its
// topmost adjoining metaedge Z=>A and discover that it's backwards.
let backwards = false;
if (adjoiningMetaedge && !bridgeMetaedge.numRegularEdges) {
// Find the top-most adjoining render metaedge information, and the
// GroupNode whose metagraph must contain the associated metaedge.
let topAdjoiningMetaedge = adjoiningMetaedge;
let topGroupNode = parentNodeInfo.node;
while (topAdjoiningMetaedge.adjoiningMetaedge) {
topAdjoiningMetaedge = topAdjoiningMetaedge.adjoiningMetaedge;
topGroupNode = topGroupNode.parentNode;
}
// Check against the topological ordering for the top node. The current
// bridge metaedge we're evaluating is backwards if its source comes
// after its destination.
let ordering = this.hierarchy.getTopologicalOrdering(topGroupNode.name);
let e = topAdjoiningMetaedge.metaedge;
backwards = ordering[e.v] > ordering[e.w];
}
// Render backwards control edges as annotations.
canDrawBridgePath = canDrawBridgePath && !backwards;
// If we can't make a bridge path for any reason, then we add an
// annotation instead.
if (!canDrawBridgePath) {
childAnnotations.push(new Annotation(
otherNode,
otherRenderInfo,
new RenderMetaedgeInformation(bridgeMetaedge),
AnnotationType.SHORTCUT,
inbound), this.params);
return;
}
// At this point, all conditions have been met for drawing a bridge path.
// Find or create the IN/OUT node representing otherNode.
let bridgeContainerName = getBridgeNodeName(inbound, nodeName);
let bridgeNodeName = getBridgeNodeName(inbound, otherName, nodeName);
let bridgeNodeRenderInfo = coreGraph.node(bridgeNodeName);
if (!bridgeNodeRenderInfo) {
// Find or create the directional container for the bridge node.
let bridgeContainerInfo = coreGraph.node(bridgeContainerName);
if (!bridgeContainerInfo) {
let bridgeContainerNode: BridgeNode = {
// Important node properties.
name: bridgeContainerName,
type: NodeType.BRIDGE,
// Unused node properties.
isGroupNode: false,
cardinality: 0,
parentNode: null,
stats: null,
// BridgeNode properties.
inbound: inbound,
};
bridgeContainerInfo =
new RenderNodeInformation(bridgeContainerNode);
this.index[bridgeContainerName] = bridgeContainerInfo;
coreGraph.setNode(bridgeContainerName, bridgeContainerInfo);
}
let bridgeNode: BridgeNode = {
// Important node properties.
name: bridgeNodeName,
type: NodeType.BRIDGE,
// Unimportant node properties.
isGroupNode: false,
cardinality: 1,
parentNode: null,
stats: null,
// BridgeNode properties.
inbound: inbound,
};
bridgeNodeRenderInfo = new RenderNodeInformation(bridgeNode);
this.index[bridgeNodeName] = bridgeNodeRenderInfo;
coreGraph.setNode(bridgeNodeName, bridgeNodeRenderInfo);
// Set bridgeNode to be a graphlib child of the container node.
coreGraph.setParent(bridgeNodeName, bridgeContainerName);
bridgeContainerInfo.node.cardinality++;
}
// Create and add a bridge render metaedge.
let bridgeRenderMetaedge =
new RenderMetaedgeInformation(bridgeMetaedge);
bridgeRenderMetaedge.adjoiningMetaedge = adjoiningMetaedge;
inbound ?
coreGraph.setEdge(bridgeNodeName, childName, bridgeRenderMetaedge) :
coreGraph.setEdge(childName, bridgeNodeName, bridgeRenderMetaedge);
}); // End _.each(bridgegraph.edges).
// For each bridge container (IN and/or OUT), add structural edges between
// terminal nodes and that container. A terminal node is one which has no
// non-bridge edges in the direction of the container.
//
// For example, consider a Metanode A which contains two child nodes A/B
// and A/C. Let's say it has one edge in the metagraph from A/B->A/C, and
// one edge in the bridgegraph from Z->A/C.
//
// At this point, we've added a container bridge node IN to house all
// incoming bridge nodes. We'v alse added a bridge node Z' (with parent IN)
// to A, and a bridge edge from Z'->C.
//
// +----------------------+
// | A +---+ |
// | +------>| C | |
// | | +---+ |
// | | ^ |
// | | | |
// | | +----|----+ |
// | | | IN | | |
// | +---+ | +---+ | |
// | | B | | | Z'| | |
// | +---+ | +---+ | |
// | +---------+ |
// +----------------------+
//
// With no other help, dagre would lay out B and Z' on the same level,
// because both of them have no incoming edges. In other words, B is a
// terminal node in the INCOMING direction.
//
// But we want to force dagre to lay out Z' (and everything in IN) lower
// than all non-bridge nodes, so that there's enough room for the bridge
// edges after they've been adjusted to meet up with paths coming in from
// outside.
//
// To force Z' (and all other bridge nodes) to be lowest in the graph, we
// identify terminal nodes like B and give them structural edges to
// a new structural bridge node S which we add to IN.
//
// +----------------------+
// | A +---+ |
// | +--->| C | |
// | | +---+ |
// | +---+ ^ |
// | | B | | |
// | +---+ | |
// | ^ | |
// | | | |
// | +----|------|----+ |
// | |IN | | | |
// | | +---+ +---+ | |
// | | | S | | Z'| | |
// | | +---+ +---+ | |
// | +----------------+ |
// +----------------------+
//
// This ensures that dagre will lay out the bridge containers strictly at
// the ends of the graph. The structural edges will never be seen in the
// visualization except as a debugging aid.
_.each([true, false], inbound => {
let bridgeContainerName = getBridgeNodeName(inbound, nodeName);
let bridgeContainerInfo = coreGraph.node(bridgeContainerName);
if (!bridgeContainerInfo) {
return;
}
_.each(coreGraph.nodes(), childName => {
// Short-circuit if this child is a bridge node or it's not a terminal
// node in the direction we're interested in.
let childNodeInfo = coreGraph.node(childName);
if (childNodeInfo.node.type === NodeType.BRIDGE) {
return;
}
let isTerminal = inbound ?
!coreGraph.predecessors(childName).length :
!coreGraph.successors(childName).length;
if (!isTerminal) {
return;
}
// Find or create a bridge node in the container for all structural
// metaedges. It would have been nice to skip this step and simply
// set a metaedge between the terminal node and the container node, but
// in that case, something about the graph upsets dagre.layout()'s
// longestPath algorithm (was getting errors due to an undefined).
let structuralNodeName =
getBridgeNodeName(inbound, nodeName, "STRUCTURAL_TARGET");
let structuralRenderInfo = coreGraph.node(structuralNodeName);
if (!structuralRenderInfo) {
let bridgeNode: BridgeNode = {
// Important Node properties.
name: structuralNodeName,
type: NodeType.BRIDGE,
// Unimportant Node properties.
isGroupNode: false,
cardinality: 1,
parentNode: null,
stats: null,
// BridgeNode properties.
inbound: inbound,
};
structuralRenderInfo = new RenderNodeInformation(bridgeNode);
structuralRenderInfo.structural = true;
this.index[structuralNodeName] = structuralRenderInfo;
coreGraph.setNode(structuralNodeName, structuralRenderInfo);
bridgeContainerInfo.node.cardinality++;
coreGraph.setParent(structuralNodeName, bridgeContainerName);
}
// Create the structural Metaedge and insert it.
let structuralMetaedgeInfo = new RenderMetaedgeInformation(null);
structuralMetaedgeInfo.structural = true;
structuralMetaedgeInfo.weight--; // Reduce weight for dagre layout.
inbound ?
coreGraph.setEdge(
structuralNodeName, childName, structuralMetaedgeInfo) :
coreGraph.setEdge(
childName, structuralNodeName, structuralMetaedgeInfo);
});
});
}
}
/**
* A class for rendering annotation object which contains label
* about the node embedded as annotation, type of annotation and the location
* of both the annotation's node and edge.
*
* Annotation objects include embedded constants, embedded summary, and
* edge shortcuts.
*/
export class Annotation {
node: Node;
renderNodeInfo: RenderNodeInformation;
renderMetaedgeInfo: RenderMetaedgeInformation;
annotationType: AnnotationType;
/**
* Center position of annotation relative to the host
* node's center x.
*/
dx: number;
/**
* Center position of annotation relative to the host
* node's center y.
*/
dy: number;
width: number;
height: number;
/**
* A flag whether it is an in-annotation (if true) or
* out-annotation (if false).
*/
isIn: boolean;
/** Label horizontal offset from the end of the node shape */
labelOffset: number;
/**
* Array of points for edges from the annotation to its host
* node. Each point contains the point location, relative to
* the host node's center.
*/
points: {dx: number, dy: number}[];
/**
* Creates a new Annotation.
*
* @param node The underlying node this annotation points to.
* @param renderNodeInfo The render information for the underlying node
* this annotation points to. This can be null if the annotation
* denotes an embedding (constant, summary), in which case we
* use the node property.
* @param renderMetaedgeInfo The render information for the edge associated
* with the annotation.
* @param type The type of the annotation.
* @param isIn True if it is an in-annotation. False if it is an
* out-annotation.
*/
constructor(node: Node, renderNodeInfo: RenderNodeInformation,
renderMetaedgeInfo: RenderMetaedgeInformation, type: AnnotationType,
isIn: boolean) {
this.node = node;
this.renderNodeInfo = renderNodeInfo;
this.renderMetaedgeInfo = renderMetaedgeInfo;
this.annotationType = type;
// Properties specified by layout
this.dx = 0;
this.dy = 0;
this.width = 0;
this.height = 0;
this.isIn = isIn;
this.points = [];
}
};
export enum AnnotationType {SHORTCUT, CONSTANT, SUMMARY, ELLIPSIS};
/**
* Manages a list of annotations. Two will be used for each
* RenderNodeInformation, one for in annotations and one for out annotations.
*/
export class AnnotationList {
/**
* List of visually drawable annotations, may include an ellipses annotation
* if the number added exceeds the number specified by maxAnnotations.
*/
list: Annotation[];
/**
* Set of nodes which have been added as annotations to this list, so we can
* prevent duplicates.
*/
nodeNames: { [nodeName: string]: boolean };
constructor() {
this.list = [];
this.nodeNames = {};
}
/**
* Append an annotation to the list, or a stand-in ellipsis annotation instead
* if this would make it too many.
*/
push(annotation: Annotation, params: RenderGraphParams): void {
if (annotation.node.name in this.nodeNames) {
return; // Skip duplicate annotation.
}
this.nodeNames[annotation.node.name] = true;
if (this.list.length < params.maxAnnotations) {
this.list.push(annotation);
return;
}
let lastAnnotation = this.list[this.list.length - 1];
if (lastAnnotation.annotationType === AnnotationType.ELLIPSIS) {
let ellipsisNode = lastAnnotation.node;
ellipsisNode.setNumMoreNodes(++ellipsisNode.numMoreNodes);
return;
}
let ellipsisNode = new tf.graph.EllipsisNodeImpl(1);
this.list.push(new Annotation(ellipsisNode,
new RenderNodeInformation(ellipsisNode), null,
AnnotationType.ELLIPSIS, annotation.isIn));
}
}
/**
* Contains rendering information about a node in the hierarchical graph.
*/
export class RenderNodeInformation {
/** Reference to the original underlying Node from the hierarchical graph. */
node: Node;
/** Whether the node is expanded or not. */
expanded: boolean;
/**
* List of rendering information about in-annotations like constants and
* shortcuts to high-degree nodes.
*/
inAnnotations: AnnotationList;
/** List of rendering information about out-annotations (e.g. summary nodes) */
outAnnotations: AnnotationList;
// --- Params specified by layout --- //
/** Center x position */
x: number;
/** Center y position */
y: number;
/** Width of the node's shape */
width: number;
/** Height of the node's shape. */
height: number;
/** Width of the bounding box for all in-annotations. */
inboxWidth: number;
/** Width of the bounding box for all out-annotations. */
outboxWidth: number;
/**
* Whether the node should be excluded from the scene.
* This is only used when there are too many items in a series so we only
* want to include top N ones.
*/
// TODO(jimbo): Now that series rendering is non-recursive, remove this and
// all its uses from the code base.
excluded: boolean;
// --- Params used in drawing the bridge paths --- //
/**
* All bridge nodes are meant to be invisible, but whereas most represent a
* relationship from the underlying graph hierarchy, some exist solely for
* layout reasons. Specifically, those bridge nodes which have only structural
* rendering metaedges.
*/
structural: boolean;
// --- Params for the size of the node box --- //
/** Label vertical offset from the center of node shape */
labelOffset: number;
/** X-space between each extracted node and the core graph. */
extractXOffset: number;
/** Rectangle radius (for making rounded rectangle) */
radius: number;
// --- Params for expanded node --- //
/** Label height for expanded node. */
labelHeight: number;
// Paddings between inner subscene and the border of the expanded node.
paddingTop: number;
paddingLeft: number;
paddingRight: number;
paddingBottom: number;
/** Width of the whole node including its shape and its annotations */
outerWidth: number;
/** Height of the whole node including its shape and its annotations */
outerHeight: number;
/**
* Whether a node is extracted as source-like (having high out-degree or matching
* predefined in-extract pattern.)
*/
isInExtract: boolean;
/**
* Whether a node is extracted as sink-like (having high in-degree or matching
* predefined out-extract pattern.)
*/
isOutExtract: boolean;
/**
* List of (color, proportion) tuples based on the proportion of devices of
* its children. If this node is an op node, this list will have only one
* color with proportion 1.0.
*/
deviceColors: {color: string, proportion: number}[];
/**
* Color according to the memory usage of this node.
*/
memoryColor: string;
/**
* Color according to the compute time of this node.
*/
computeTimeColor: string;
constructor(node: Node) {
this.node = node;
this.expanded = false;
this.inAnnotations = new AnnotationList();
this.outAnnotations = new AnnotationList();
// Params specified by layout
this.x = 0;
this.y = 0;
this.width = 0;
this.height = 0;
this.inboxWidth = 0;
this.outboxWidth = 0;
this.excluded = false;
// Params for bridge paths.
this.structural = false;
// Params for node box.
this.labelOffset = 0;
this.extractXOffset = 0;
this.radius = 0;
// Params for expanded node
this.labelHeight = 0;
this.paddingTop = 0;
this.paddingLeft = 0;
this.paddingRight = 0;
this.paddingBottom = 0;
this.outerWidth = 0;
this.outerHeight = 0;
this.isInExtract = false;
this.isOutExtract = false;
}
isInCore(): boolean {
return !this.isInExtract && !this.isOutExtract;
}
}
/**
* Contains rendering information about a Metaedge from the underlying
* hierarchical graph. It may be from either a metagraph or a bridgegraph.
*/
export class RenderMetaedgeInformation {
/**
* Reference to the original underlying Metaedge from the hierarchical graph,
* if any. This will be null for the edges which connect OpNodes to their
* embeddings, for example.
*/
metaedge: Metaedge;
/**
* Reference to the adjoining RenderMeteaedgeInformation from the parent's
* coreGraph. This is used during layout to determine the point at which this
* edge should touch the node's bounding box. This property will be null for
* edges which terminate at a node on both ends (all non-bridge edges).
*/
adjoiningMetaedge: RenderMetaedgeInformation;
/**
* Most of the time, a RenderMetaedgeInformation object represents a real
* edge between nodes in the underlying graph structure. But sometimes, an
* edge only exsts for layout purposes. These structural edges are added
* during buildSubhierarchy() to force dagre.layout() to put bridge nodes
* at the ends of the flow.
* @see buildSubhierarchy()
*/
structural: boolean;
/**
* Weight of the edge, used by dagre when deciding how important an edge is.
* Edges with higher weight are made shorter and straighter. The default
* dagre uses is 1.
*/
weight: number;
/**
* X and Y coordinate pairs of the points in the path of the edge.
* @see tf.graph.node.subsceneAdjustPaths
*/
points: any[];
/**
* D3 selection of the group containing the path that displays this edge.
*/
edgeGroup: d3.Selection;
constructor(metaedge: Metaedge) {
this.metaedge = metaedge;
this.adjoiningMetaedge = null;
this.structural = false;
this.weight = 1;
}
}
function addInAnnotation(node: RenderNodeInformation, predecessor: Node,
predecessorRenderInfo: RenderNodeInformation, edge: any,
type: AnnotationType, params: RenderGraphParams): void {
let annotation = new Annotation(predecessor, predecessorRenderInfo, edge,
type, true);
node.inAnnotations.push(annotation, params);
}
function addOutAnnotation(node: RenderNodeInformation, successor: Node,
successorRenderInfo: RenderNodeInformation, edge: any,
type: AnnotationType, params: RenderGraphParams): void {
let annotation = new Annotation(successor, successorRenderInfo, edge,
type, false);
node.outAnnotations.push(annotation, params);
}
function setGraphDepth(graph: graphlib.Graph,
depth: number) {
_.each(graph.nodes(), nodeName => {
let child = graph.node(nodeName);
child.expanded = depth > 1; // set all child of depth 1 to collapsed
if (depth > 0) {
switch (child.node.type) {
case NodeType.META:
case NodeType.SERIES:
setGroupNodeDepth(child, depth - 1);
break;
// Do nothing for leaf
}
}
});
};
export class RenderGroupNodeInformation extends RenderNodeInformation {
node: GroupNode;
/**
* The core graph is derived from the underlying node's metagraph, minus
* the extracted source-like and sink-like nodes.
*/
coreGraph: graphlib.Graph;
/** Size of the bounding box for a metanode's core graph. */
coreBox: {
width: number,
height: number,
};
/** Size of the bounding box for a metanode's isolated in-extract children. */
inExtractBox: {width: number, height: number};
/** Size of the bounding box for a metanode's isolated out-extract children. */
outExtractBox: {width: number, height: number};
/** Array of isolated in-extract nodes. */
isolatedInExtract: RenderNodeInformation[];
/** Array of isolated out-extract nodes. */
isolatedOutExtract: RenderNodeInformation[];
constructor(groupNode: GroupNode) {
super(groupNode);
let metagraph = groupNode.metagraph;
let gl = metagraph.graph();
this.coreGraph =
createGraph(
gl.name, GraphType.CORE, { compound: true });
this.coreBox = {width: 0, height: 0};
this.inExtractBox = {width: 0, height: 0};
this.outExtractBox = {width: 0, height: 0};
this.isolatedInExtract = [];
this.isolatedOutExtract = [];
}
}
function setGroupNodeDepth(renderInfo: RenderGroupNodeInformation,
depth: number): void {
if (renderInfo.coreGraph) {
setGraphDepth(renderInfo.coreGraph, depth);
}
}
/**
* Remove an edge from the graph and add annotations to both ends of the edge.
*
* @param The core graph.
* @param v Source name.
* @param w Sink name.
*/
function createShortcut(graph: graphlib.Graph,
v: string, w: string, params: RenderGraphParams) {
let src = graph.node(v);
let sink = graph.node(w);
let edge = graph.edge(v, w);
// Add each annotation.
addOutAnnotation(src, sink.node, sink, edge, AnnotationType.SHORTCUT, params);
addInAnnotation(sink, src.node, src, edge, AnnotationType.SHORTCUT, params);
// Remove the edge from the core graph.
graph.removeEdge(v, w);
}
/**
* Remove edges from a node, and set its isOutExtract property to true,
* and remove the node and move it to isolatedOutExtract.
*
* If detachAllEdgesForHighDegree is true, extract all of its edges.
* Otherwise, only extract all in-edges.
*/
function makeOutExtract(renderNode: RenderGroupNodeInformation, n: string,
params: RenderGraphParams) {
let graph = renderNode.coreGraph;
graph.node(n).isOutExtract = true;
_.each(graph.predecessors(n), (p, index) => {
createShortcut(graph, p, n, params);
});
if (params.detachAllEdgesForHighDegree) {
_.each(graph.successors(n), (s, index) => {
createShortcut(graph, n, s, params);
});
}
if (params.detachAllEdgesForHighDegree || graph.neighbors(n).length === 0) {
renderNode.isolatedOutExtract.push(graph.node(n));
graph.removeNode(n);
}
}
/**
* Remove edges from a node, set its isInExtract property to true,
* and remove the node and move it to isolatedInExtract.
* If detachAllEdgesForHighDegree is true, extract all of its edges.
* Otherwise, only remove all out-edges.
*/
function makeInExtract(renderNode: RenderGroupNodeInformation, n: string,
params: RenderGraphParams) {
let graph = renderNode.coreGraph;
graph.node(n).isInExtract = true;
_.each(graph.successors(n), (s, index) => {
createShortcut(graph, n, s, params);
});
if (params.detachAllEdgesForHighDegree) {
_.each(graph.predecessors(n), (p, index) => {
createShortcut(graph, p, n, params);
});
}
// Remove the node from the core graph if conditions are met.
if (params.detachAllEdgesForHighDegree || graph.neighbors(n).length === 0) {
renderNode.isolatedInExtract.push(graph.node(n));
graph.removeNode(n);
}
}
/**
* Check whether the node's type is a member of the given list of types.
*
* @param node Node.
* @param types List of type to match.
*/
function hasTypeIn(node: Node, types: string[]): boolean {
if (node.type === NodeType.OP) {
for (let i = 0; i < types.length; i++) {
if ((node).op === types[i]) { return true; }
}
} else if (node.type === NodeType.META) {
let rootOpNode = (node).getRootOp();
if (rootOpNode) {
for (let i = 0; i < types.length; i++) {
if (rootOpNode.op === types[i]) { return true; }
}
}
}
return false;
}
/** Remove edges from pre-defined out-extract patterns */
function extractPredefinedSink(renderNode: RenderGroupNodeInformation,
params: RenderGraphParams) {
let graph = renderNode.coreGraph;
_.each(graph.nodes(), n => {
let renderInfo = graph.node(n);
if (hasTypeIn(renderInfo.node, params.outExtractTypes)) {
makeOutExtract(renderNode, n, params);
}
});
}
/** Remove edges from pre-defined in-extract patterns */
function extractPredefinedSource(renderNode: RenderGroupNodeInformation,
params: RenderGraphParams) {
let graph = renderNode.coreGraph;
_.each(graph.nodes(), n => {
let renderInfo = graph.node(n);
if (hasTypeIn(renderInfo.node, params.inExtractTypes)) {
makeInExtract(renderNode, n, params);
}
});
}
/** Extract from nodes with in-degree > maxInDegree */
function extractHighInDegree(renderNode: RenderGroupNodeInformation,
params: RenderGraphParams) {
let graph = renderNode.coreGraph;
let maxInDegree = params.maxInDegree;
// detect first so degrees don't get affected by other removal
let highInDegreeNames = _.filter(graph.nodes(), n => {
// Count the in-degree based on only regular edges, unless there are
// no regular edges, in which case use the number of control edges.
// This is done so that control edges don't effect if nodes are extracted
// from the core graph, unless the node is only used for control.
let numEdgesToCount = _.reduce(graph.predecessors(n), (numEdgesToCount, pred) => {
let metaedge = graph.edge(pred, n).metaedge;
return numEdgesToCount + (metaedge.numRegularEdges ? 1 : 0);
}, 0);
if (numEdgesToCount === 0 && graph.predecessors(n).length > 0) {
numEdgesToCount = graph.predecessors(n).length;
}
return numEdgesToCount > maxInDegree;
});
_.each(highInDegreeNames, n => {
makeOutExtract(renderNode, n, params);
});
}
/** Extract nodes with out-degree > maxOutDegree */
function extractHighOutDegree(renderNode: RenderGroupNodeInformation,
params: RenderGraphParams) {
let graph = renderNode.coreGraph;
let maxOutDegree = params.maxOutDegree;
// detect first so degrees don't get affected by other removal
let highOutDegreeNames = _.filter(graph.nodes(), n => {
// Count the out-degree based on only regular edges, unless there are
// no regular edges, in which case use the number of control edges.
// This is done so that control edges don't effect if nodes are extracted
// from the core graph, unless the node is only used for control.
let numEdgesToCount = _.reduce(graph.successors(n), (numEdgesToCount, succ) => {
let metaedge = graph.edge(n, succ).metaedge;
return numEdgesToCount + (metaedge.numRegularEdges ? 1 : 0);
}, 0);
if (numEdgesToCount === 0 && graph.successors(n).length > 0) {
numEdgesToCount = graph.successors(n).length;
}
return numEdgesToCount > maxOutDegree;
});
_.each(highOutDegreeNames, n => {
makeInExtract(renderNode, n, params);
});
}
/** Remove control edges from nodes that have too many control edges */
function removeControlEdges(renderNode: RenderGroupNodeInformation,
params: RenderGraphParams) {
let graph = renderNode.coreGraph;
// Collect control edges into a map by node name.
let map = <{[nodeName: string]: graphlib.EdgeObject[]}>{};
_.each(graph.edges(), e => {
if (!graph.edge(e).metaedge.numRegularEdges) {
(map[e.v] = map[e.v] || []).push(e);
(map[e.w] = map[e.w] || []).push(e);
}
});
// For each node with too many control edges, turn them into annotations.
_.each(map, (edges, nodeName) => {
if (edges.length > params.maxControlDegree) {
_.each(edges, e => createShortcut(graph, e.v, e.w, params));
}
});
}
/**
* Given an integer, picks a hue that is far apart from other colors.
* The formula for picking color that avoid collision is:
* hue = (color range * golden ratio * index) % color range
*/
export function mapIndexToHue(id: number): number {
let GOLDEN_RATIO = 1.61803398875;
// Hue of 0 is reserved for the gray nodes.
let MIN_HUE = 1;
let MAX_HUE = 359;
let COLOR_RANGE = MAX_HUE - MIN_HUE;
return MIN_HUE + ((COLOR_RANGE * GOLDEN_RATIO * id) % COLOR_RANGE);
};
/**
* Remove edges and add to annotation instead.
*
* For root node, consider predefined types for source and sink.
* We do not extract predefined type from non-root so that Variables and the
* sgd node (op type = "NoOp") do not get extract from inside own group.
*
* The order of extraction is important here as swapping the order can totally
* screw up the graph layout.
*
* @param {Render.Node} renderNode Node to manipulate.
* @param {Object} params render Graph construction parameters. See
* 's output
*/
function extractHighDegrees(renderNode: RenderGroupNodeInformation,
params: RenderGraphParams) {
if (params.outExtractTypes) {
extractPredefinedSink(renderNode, params);
}
// This has to come before extract high in-degree to protect the core part
// that takes many variables.
if (params.inExtractTypes) {
extractPredefinedSource(renderNode, params);
}
// This has to come before extract high out-degree to protect the core part
// that output to many places as there are more high-degree sinks than
// sources.
if (params.maxInDegree) {
extractHighInDegree(renderNode, params);
}
if (params.maxOutDegree) {
extractHighOutDegree(renderNode, params);
}
if (params.maxControlDegree) {
removeControlEdges(renderNode, params);
}
// Extract isolated nodes, which can be
// (1) source-like and sink-like nodes that are not originally isolated but
// become isolated after further removal.
// (2) isolated nodes with annotations on one-side. These might be either
// - nodes that originally have high out-degree but because we remove
// high in-degree nodes first, they no longer have high in-degree when
// we check. (Detecting all high-degree before removing also leads to
// another problem.)
// - nodes that do not have high degree, but their neighbors are all
// extracted, so it might make sense to extract them too.
let graph = renderNode.coreGraph;
_.each(graph.nodes(), n => {
let child = graph.node(n);
let degree = graph.neighbors(n).length;
if (degree === 0) {
let hasOutAnnotations = child.outAnnotations.list.length > 0;
let hasInAnnotations = child.inAnnotations.list.length > 0;
if (child.isInExtract) { // Is source-like.
// This case only happens if detachAllEdgesForHighDegree is false.
// (Otherwise all source-like nodes are all isolated already.)
renderNode.isolatedInExtract.push(child);
graph.removeNode(n);
} else if (child.isOutExtract) { // Is sink-like.
// This case only happens if detachAllEdgesForHighDegree is false.
// // (Otherwise all sink-like nodes are all isolated already.)
renderNode.isolatedOutExtract.push(child);
graph.removeNode(n);
} else if (params.extractIsolatedNodesWithAnnotationsOnOneSide) {
if (hasOutAnnotations && !hasInAnnotations) {
child.isInExtract = true; // for ones with high out-annotations
renderNode.isolatedInExtract.push(child);
graph.removeNode(n);
} else if (hasInAnnotations && !hasOutAnnotations) {
child.isOutExtract = true; // for ones with high in-annotations
renderNode.isolatedOutExtract.push(child);
graph.removeNode(n);
} else {
// if a low degree node has both in- & out- annotations, do nothing
// because it is unclear which side it should go to.
}
}
}
});
}
} // close module tf.graph.render