diff options
Diffstat (limited to 'tensorflow/tensorboard/components/tf-graph-common/lib')
13 files changed, 6035 insertions, 0 deletions
diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/colors.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/colors.ts new file mode 100644 index 0000000000..8912483c09 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/colors.ts @@ -0,0 +1,133 @@ +module tf { + +/** + * Mapping from color palette name to color pallette, which contains + * exact colors for multiple states of a single color pallette. + */ +export let COLORS = [ + { + "name": "Google Blue", + "color": "#4184f3", + "active": "#3a53c5", + "disabled": "#cad8fc" + }, + { + "name": "Google Red", + "color": "#db4437", + "active": "#8f2a0c", + "disabled": "#e8c6c1" + }, + { + "name": "Google Yellow", + "color": "#f4b400", + "active": "#db9200", + "disabled": "#f7e8b0" + }, + { + "name": "Google Green", + "color": "#0f9d58", + "active": "#488046", + "disabled": "#c2e1cc" + }, + { + "name": "Purple", + "color": "#aa46bb", + "active": "#5c1398", + "disabled": "#d7bce6" + }, + { + "name": "Teal", + "color": "#00abc0", + "active": "#47828e", + "disabled": "#c2eaf2" + }, + { + "name": "Deep Orange", + "color": "#ff6f42", + "active": "#ca4a06", + "disabled": "#f2cbba" + }, + { + "name": "Lime", + "color": "#9d9c23", + "active": "#7f771d", + "disabled": "#f1f4c2" + }, + { + "name": "Indigo", + "color": "#5b6abf", + "active": "#3e47a9", + "disabled": "#c5c8e8" + }, + { + "name": "Pink", + "color": "#ef6191", + "active": "#ca1c60", + "disabled": "#e9b9ce" + }, + { + "name": "Deep Teal", + "color": "#00786a", + "active": "#2b4f43", + "disabled": "#bededa" + }, + { + "name": "Deep Pink", + "color": "#c1175a", + "active": "#75084f", + "disabled": "#de8cae" + }, + { + "name": "Gray", + "color": "#9E9E9E", // 500 + "active": "#424242", // 800 + "disabled": "F5F5F5" // 100 + } +].reduce((m, c) => { + m[c.name] = c; + return m; +}, {}); + +/** + * Mapping from op category to color palette name + * e.g., OP_GROUP_COLORS["state_ops"] = "Google Blue"; + */ +export let OP_GROUP_COLORS = [ + { + color: "Google Red", + groups: ["gen_legacy_ops", "legacy_ops", "legacy_flogs_input", + "legacy_image_input", "legacy_input_example_input", + "legacy_sequence_input", "legacy_seti_input_input"] + }, { + color: "Deep Orange", + groups: ["constant_ops"] + }, { + color: "Indigo", + groups: ["state_ops"] + }, { + color: "Purple", + groups: ["nn_ops", "nn"] + }, { + color: "Google Green", + groups: ["math_ops"] + }, { + color: "Lime", + groups: ["array_ops"] + }, { + color: "Teal", + groups: ["control_flow_ops", "data_flow_ops"] + }, { + color: "Pink", + groups: ["summary_ops"] + }, { + color: "Deep Pink", + groups: ["io_ops"] + } +].reduce((m, c) => { + c.groups.forEach(function(group) { + m[group] = c.color; + }); + return m; +}, {}); + +} diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/common.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/common.ts new file mode 100644 index 0000000000..ed148bf719 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/common.ts @@ -0,0 +1,236 @@ +/// <reference path="../../../typings/tsd.d.ts" /> + +declare module graphlib { + + interface GraphOptions { + name: string; + /** + * Direction for rank nodes. Can be TB, BT, LR, or RL, where T = top, + * B = bottom, L = left, and R = right. + */ + rankdir: string; + type: string|number; + /** Number of pixels between each rank in the layout. */ + ranksep?: number; + /** Number of pixels that separate nodes horizontally in the layout. */ + nodesep?: number; + } + + export interface EdgeObject { + v: string; + w: string; + name?: string; + } + + export class Graph<N, E> { + constructor(opt?: Object); + setNode(name: string, value?: N): void; + hasNode(name: string): boolean; + setEdge(fromName: string, toName: string, value?: E): void; + hasEdge(fromName: string, toName: string): boolean; + edge(fromName: string, toName: string): E; + edge(edgeObject: EdgeObject): E; + removeEdge(v: string, w: string): void; + nodes(): string[]; + node(name: string): N; + removeNode(name: string): void; + setGraph(graphOptions: GraphOptions): void; + graph(): GraphOptions; + nodeCount(): number; + neighbors(name: string): string[]; + successors(name: string): string[]; + predecessors(name: string): string[]; + edges(): EdgeObject[]; + outEdges(name: string): E[]; + inEdges(name: string): E[]; + /** Returns those nodes in the graph that have no in-edges. Takes O(|V|) time. */ + sources(): string[]; + /** + * Remove the node with the id v in the graph or do nothing if + * the node is not in the graph. If the node was removed this + * function also removes any incident edges. Returns the graph, + * allowing this to be chained with other functions. Takes O(|E|) time. + */ + removeNode(name: string): Graph<N, E>; + setParent(name: string, parentName: string): void; + } +} + +module tf { +/** + * Recommended delay (ms) when running an expensive task asynchronously + * that gives enough time for the progress bar to update its UI. + */ +const ASYNC_TASK_DELAY = 20; + +export function time<T>(msg: string, task: () => T) { + let start = Date.now(); + let result = task(); + /* tslint:disable */ + console.log(msg, ":", Date.now() - start, "ms"); + /* tslint:enable */ + return result; +} + +/** + * Tracks task progress. Each task being passed a progress tracker needs + * to call the below-defined methods to notify the caller about the gradual + * progress of the task. + */ +export interface ProgressTracker { + updateProgress(incrementValue: number): void; + setMessage(msg: string): void; + reportError(msg: string): void; +} + +/** + * Creates a tracker for a subtask given the parent tracker, the total progress + * of the subtask and the subtask message. The parent task should pass a + * subtracker to its subtasks. The subtask reports its own progress which + * becames relative to the main task. + */ +export function getSubtaskTracker(parentTracker: ProgressTracker, + impactOnTotalProgress: number, subtaskMsg: string): ProgressTracker { + return { + setMessage: function(progressMsg) { + // The parent should show a concatenation of its message along with + // its subtask tracker message. + parentTracker.setMessage(subtaskMsg + " : " + progressMsg); + }, + updateProgress: function(incrementValue) { + // Update the parent progress relative to the child progress. + // For example, if the sub-task progresses by 30%, and the impact on the + // total progress is 50%, then the task progresses by 30% * 50% = 15%. + parentTracker + .updateProgress(incrementValue * impactOnTotalProgress / 100); + }, + reportError: function(errorMsg) { + // The parent should show a concatenation of its message along with + // its subtask error message. + parentTracker.reportError(subtaskMsg + " : " + errorMsg); + } + }; +} + +/** + * Runs an expensive task asynchronously and returns a promise of the result. + */ +export function runAsyncTask<T>(msg: string, incProgressValue: number, + task: () => T, tracker: ProgressTracker): Promise<T> { + return new Promise((resolve, reject) => { + // Update the progress message to say the current running task. + tracker.setMessage(msg); + // Run the expensive task with a delay that gives enough time for the + // UI to update. + setTimeout(function() { + try { + var result = tf.time(msg, task); + // Update the progress value. + tracker.updateProgress(incProgressValue); + // Return the result to be used by other tasks. + resolve(result); + } catch (e) { + reject(result); + } + }, ASYNC_TASK_DELAY); + }); +} + +/** + * Returns a query selector with escaped special characters that are not + * allowed in a query selector. + */ +export function escapeQuerySelector(querySelector: string): string { + return querySelector.replace( /([:.\[\],/\\\(\)])/g, "\\$1" ); +} + +/** + * TensorFlow node definition as definied in the graph proto file. + */ +export interface TFNode { + /** Name of the node */ + name: string; + /** List of nodes that are inputs for this node. */ + input: string[]; + /** The name of the device where the computation will run. */ + device: string; + /** The name of the operation associated with this node. */ + op: string; + /** List of attributes that describe/modify the operation. */ + attr: {key: string, value: Object}[]; +} + +/** + * TensorFlow stats file definition as defined in the stats proto file. + */ +export interface TFStats { + devStats: {device: string, nodeStats: TFNodeStats[]}[]; +} + +/** + * TensorFlow stats for a node as defined in the stats proto file. + */ +export interface TFNodeStats { + nodeName: string; + // The next 4 properties are currently stored as string in json + // and must be parsed. + allStartMicros: number; + opStartRelMicros: number; + opEndRelMicros: number; + allEndRelMicros: number; + memory: { + allocatorName: string; + totalBytes: number; // Stored as string in json and should be parsed. + peakBytes: number; // Stored as string in json and should be parsed. + }[]; + /** Output sizes recorded for a single execution of a graph node */ + output: TFNodeOutput[]; + timelineLabel: string; + scheduledMicros: string; + threadId: string; +} + +/** + * Description for the output tensor(s) of an operation in the graph. + */ +export interface TFNodeOutput { + slot: number; // Stored as string in json and should be parsed. + /** Was the tensor allocated by this Op or a previous computation */ + allocationType: string; + tensorDescription: { + /** Data type of tensor elements */ + dtype: string; + /** Shape of the tensor */ + shape: { + /** + * Dimensions of the tensor, such as [{name: "input", size: 30}, + * {name: "output", size: 40}] for a 30 x 40 2D tensor. The names + * are optional. The order of entries in "dim" matters: It indicates + * the layout of the values in the tensor in-memory representation. + */ + dim: { + /** Size of the tensor in that dimension */ + size: number, // Stored as string in json and should be parsed. + /** Optional name of the tensor dimension */ + name?: string + }[]; + }; + /** Information about the size and allocator used for the data */ + allocationDescription: { + // The next 2 properties are stored as string in json and + // should be parsed. + /** Total number of bytes requested */ + requestedBytes: number; + /** Total number of bytes allocated, if known */ + allocatedBytes?: number; + /** Name of the allocator used */ + allocatorName: string; + }; + }; +} +} // close module tf + +/** + * Declaring dagre var used for dagre layout. + */ +declare var dagre: { layout(graph: graphlib.Graph<any, any>): void; }; diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/graph.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/graph.ts new file mode 100644 index 0000000000..64e537154b --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/graph.ts @@ -0,0 +1,889 @@ +/// <reference path="../../../typings/tsd.d.ts" /> +/// <reference path="common.ts" /> +module tf.graph { + +/** Delimiter used in node names to denote namespaces. */ +export const NAMESPACE_DELIM = "/"; +const FULL_GRAPH_NAME = "fullGraph"; +export const ROOT_NAME = "__root__"; + +// Separator between the source and the destination name of the edge. +export const EDGE_KEY_DELIM = "--"; + +export enum GraphType {FULL, EMBEDDED, META, SERIES, CORE, SHADOW, BRIDGE, + EDGE}; +export enum NodeType {META, OP, SERIES, BRIDGE, ELLIPSIS}; + +/** + * A BaseEdge is the label object (in the graphlib sense) for an edge in the + * original, full graph produced after parsing. Subsequent graphs, like those + * which belong to Metanodes, should not use BaseEdge objects, but instead + * contain Metaedges (which in turn may contain any number of BaseEdges). + */ +export interface BaseEdge extends graphlib.EdgeObject { + isControlDependency: boolean; + isReferenceEdge: boolean; +} + +/** + * A SlimGraph is inspired by graphlib.Graph, but having only the functionality + * that we need. + */ +export class SlimGraph { + nodes: { [nodeName: string]: OpNode }; + edges: BaseEdge[]; + + constructor() { + this.nodes = {}; + this.edges = []; + } +} + +interface NormalizedInput { + name: string; + hasNumberPart: boolean; + isControlDependency: boolean; +} + +interface BuildParams { + enableEmbedding: boolean; + inEmbeddingTypes: string[]; + outEmbeddingTypes: string[]; + refEdges: { [inputEdge: string]: boolean }; +} + +/** + * The most basic information about a node in the hierarchical graph. + */ +export interface Node { + /** The name of the node, used frequently to look up nodes by name. */ + name: string; + /** Which type of node this is. */ + type: NodeType; + /** + * Whether this node is a type that may contain other nodes. Those types + * should extend from GroupNode. + * + * For an OpNode, isGroupNode will be false, even though it may have + * embeddings. These embedding Nodes will have their parentNode set to the + * OpNode. However, embeddings are later rendered as annotations, not as + * children to be made visible on expansion (like a Metanode or SeriesNode). + */ + isGroupNode: boolean; + /** + * The number of nodes this node represents. For OpNodes, this will be 1, and + * for GroupNodes it will be a count of the total number of descendents it + * contains. + */ + cardinality: number; + /** + * The Node which is this Node's parent. This is of type Node and not + * GroupNode because of embeddings, which will have a parent OpNode. + */ + parentNode: Node; + /** Runtime execution stats for this node, if available */ + stats: NodeStats; +} + +export interface OpNode extends Node { + op: string; + device: string; + attr: {key: string, value: Object}[]; + inputs: NormalizedInput[]; + inEmbeddings: OpNode[]; + outEmbeddings: OpNode[]; +} + +export interface BridgeNode extends Node { + /** + * Whether this bridge node represents edges coming into its parent node. + */ + inbound: boolean; +} + +/** + * A node that is used when there are more than the maximum number of allowed + * annotations hanging off of a node. This node represents an ellipsis + * annotation, indicating a number of additional annotations. + */ +export interface EllipsisNode extends Node { + /** + * The number of nodes this ellipsis represents. + */ + numMoreNodes: number; + + /** + * Sets the number of nodes this ellipsis represents and changes the node + * name accordingly. + */ + setNumMoreNodes(numNodes: number); +} + +export interface GroupNode extends Node { + /** + * The metagraph contains nodes and metaedges between the immediate children + * of this group. The node label objects may be other GroupNodes (like + * SeriesNodes and Metanodes) or individual OpNodes. All edge label objects + * are Metaedges, each of which contains references to the original + * BaseEdge(s) from which it was created. + */ + metagraph: graphlib.Graph<GroupNode|OpNode, Metaedge>; + + /** + * The bridgegraph contains only edges which link immediate children of this + * group with nodes outside of the metagraph. As in the metagraph, all edge + * label objects are Metaedges which contain references to the original + * BaseEdge(s) that contribute to it. + * + * For a Metaedge in the bridgegraph, its external endpoint will be the same + * as the metagraph edge from which it came. This is most easily explained + * by example. + * + * Consider an original graph that contains a BaseEdge A/B/C->Z/Y/X. + * + * +-------+ (BaseEdge) +-------+ + * | A/B/C |>----------------->| Z/Y/X | + * +-------+ +-------+ + * + * When we construct the Root's metagraph, it will contain nodes for A and Z, + * and a Metaedge A->Z. The A->Z Metaedge will contain the original BaseEdge + * A/B/C->Z/Y/X in its baseEdgeGraph. The Root's bridgegraph will always be + * empty. + * + * +---+ (Root.metagraph edge) +---+ + * | A |>--------------------------->| Z | + * +---+ +---+ + * + * Now consider the Metanode A. Its metagraph will contain a Metanode for A/B + * and no edges. A's bridgegraph will have one Metaedge from A/B->Z, which + * was derived from the Root's Metaedge A->Z. That Metaedge will contain the + * original BaseEdge in its baseEdgeGraph. + * + * +---------+ + * | A | + * | +---+ | (A.bridgegraph edge) +---+ + * | | B |>---------------------------->| Z | + * | +---+ | +---+ + * +---------+ + * + * Finally, consider the Metanode A/B. Its metagraph will contain a Metanode + * for A/B/C and again no edges. A/B's bridgegraph will have one Metaedge + * from A/B/C->Z, which was derived from A's bridgegraph Metaedge A/B->Z. + * As before, the A/B/C->Z Metaedge will contain the original BaseEdge in its + * baseEdgeGraph. + * + * +---------------+ + * | A | + * | +---------+ | + * | | B | | + * | | +---+ | | (A/B.bridgegraph edge) +---+ + * | | | C |>----------------------------------->| Z | + * | | +---+ | | +---+ + * | +---------+ | + * +---------------+ + * + * Likewise, under the Metanode Z and Z/Y, to compute the bridgegraph, we'll + * end up with Metaedges A->Z/Y and A->Z/Y/X respectively. So the original + * BaseEdge A/B/C->Z/Y/X becomes four different Metaedges in four different + * bridgegraphs: + * + * + A/B->Z in GroupNode A's bridgegraph, + * + A/B/C->Z in GroupNode A/B's bridgegraph, + * + A->Z/Y in GroupNode Z's bridgegraph, and + * + A->Z/Y/X in GroupNode Z/Y's bridgegraph. + * + * Considering any BaseEdge then, if N is the number of path segments in the + * source and M is the number of path semgents in the destination, then the + * total number of bridgegraph edges you could create would be (N-1)(M-1). + * + * For this reason, it is computationally expensive to generate all the + * bridgegraphs for all the Metanodes, and instead they should be computed + * on demand as needed. + */ + bridgegraph: graphlib.Graph<GroupNode|OpNode, Metaedge>; + + /** + * Stores how many times each device name appears in its children + * op nodes. Used to color group nodes by devices. + */ + deviceHistogram: {[device: string]: number}; + + /** + * Flag indicating whether this GroupNode's metagraph contains any edges that + * are not control edges. Used to quickly determine how to draw a collapsed + * series (vertically or horizontally). + */ + hasNonControlEdges: boolean; +} + +export interface Metanode extends GroupNode { + depth: number; + templateId: string; + opHistogram: {[op: string]: number}; + getFirstChild(): GroupNode|OpNode; + getRootOp(): OpNode; + /** Return name of all leaves inside a metanode. */ + leaves(): string[]; +} + +export interface SeriesNode extends GroupNode { + hasLoop: boolean; + prefix: string; + suffix: string; + clusterId: number; + ids: number[]; + parent: string; +} + +export class EllipsisNodeImpl implements EllipsisNode { + name: string; + numMoreNodes: number; + stats: NodeStats; + type: NodeType; + isGroupNode: boolean; + cardinality: number; + parentNode: Node; + + /** + * Constructs a new ellipsis annotation node. + * + * @param numNodes The number of additional annotations this node represents. + */ + constructor(numNodes: number) { + this.type = NodeType.ELLIPSIS; + this.isGroupNode = false; + this.cardinality = 1; + this.parentNode = null; + this.stats = null; + this.setNumMoreNodes(numNodes); + } + + setNumMoreNodes(numNodes: number) { + this.numMoreNodes = numNodes; + this.name = "... " + numNodes + " more"; + } +}; + +/** + * A label object for nodes in the full graph and leaf nodes in the render + * graph. + */ +class OpNodeImpl implements OpNode { + name: string; + op: string; + device: string; + stats: NodeStats; + attr: {key: string, value: Object}[]; + inputs: NormalizedInput[]; + type: NodeType; + isGroupNode: boolean; + cardinality: number; + inEmbeddings: OpNode[]; + outEmbeddings: OpNode[]; + parentNode: Node; + + /** + * Constructs a new Op node. + * + * @param rawNode The raw node. + * @param normalizedInputs An array of normalized + * inputs that denote the incoming edges to the current node. Each input + * contains the normalized name of the source node, whether it has a number + * part and whether it is a control dependency. + */ + constructor(rawNode: tf.TFNode, normalizedInputs: NormalizedInput[]) { + this.op = rawNode.op; + this.name = rawNode.name; + this.device = rawNode.device; + this.attr = rawNode.attr; + this.inputs = normalizedInputs; + // additional properties + this.type = NodeType.OP; + this.isGroupNode = false; + this.cardinality = 1; + this.inEmbeddings = []; + this.outEmbeddings = []; + this.parentNode = null; + } +}; + +export function createMetanode(name: string, opt = {}): Metanode { + return new MetanodeImpl(name, opt); +} + +/** + * Joins the information from the stats file (memory, compute time) with the graph + * information. + */ +export function joinStatsInfoWithGraph(graph: SlimGraph, + statsJson: TFStats): void { + _.each(statsJson.devStats, stats => { + _.each(stats.nodeStats, nodeStats => { + // Lookup the node in the graph by its original name, e.g. A. If not + // found, lookup by the rewritten name A/(A) in case the name is both + // a namespace and a node name. + let nodeName = nodeStats.nodeName in graph.nodes ? + nodeStats.nodeName : + nodeStats.nodeName + NAMESPACE_DELIM + "(" + nodeStats.nodeName + ")"; + if (nodeName in graph.nodes) { + // Compute the total bytes used. + let totalBytes = 0; + if (nodeStats.memory) { + _.each(nodeStats.memory, alloc => { + if (alloc.totalBytes) { + totalBytes += Number(alloc.totalBytes); + } + }); + } + let outputSize: number[][] = null; + if (nodeStats.output) { + outputSize = _.map(nodeStats.output, output => { + return _.map(output.tensorDescription.shape.dim, + dim => Number(dim.size)); + }); + } + graph.nodes[nodeName].stats = new NodeStats(totalBytes, + Number(nodeStats.allEndRelMicros), outputSize); + } + }); + }); +} + +/** + * Execution stats for the node. + */ +class NodeStats { + constructor(totalBytes: number, totalMicros: number, outputSize: number[][]) { + this.totalBytes = totalBytes; + this.totalMicros = totalMicros; + this.outputSize = outputSize; + } + + /** + * Total number of bytes used for the node. Sum of all childen + * if it is a Group node. + */ + totalBytes: number; + /** + * Total number of compute time in microseconds used for the node. + * Sum of all children if it is a Group node. + */ + totalMicros: number; + /** + * The shape of each output tensors, if there are any. + * Empty if it is a Group node. + */ + outputSize: number[][]; + + /** + * Combines the specified stats with the current stats. + * Modifies the current object. This methos is used to + * compute aggregate stats for group nodes. + */ + combine(stats: NodeStats): void { + if (stats.totalBytes != null) { + this.totalBytes += stats.totalBytes; + } + if (stats.totalMicros != null) { + this.totalMicros += stats.totalMicros; + } + } +} + +class MetanodeImpl implements Metanode { + name: string; + stats: NodeStats; + type: NodeType; + depth: number; + isGroupNode: boolean; + cardinality: number; + metagraph: graphlib.Graph<GroupNode|OpNode, Metaedge>; + bridgegraph: graphlib.Graph<GroupNode|OpNode, Metaedge>; + templateId: string; + opHistogram: {[op: string]: number}; + deviceHistogram: {[op: string]: number}; + parentNode: Node; + hasNonControlEdges: boolean; + + /** A label object for meta-nodes in the graph hierarchy */ + constructor(name: string, opt = {}) { + this.name = name; + this.type = NodeType.META; + /** number of levels under this group */ + this.depth = 1; + this.isGroupNode = true; + /** # of leaf nodes (including embedded ones) */ + this.cardinality = 0; + /** graph contains metanodes, nodes, edges + * and metaedges for main items within this metanode + */ + this.metagraph = + createGraph<GroupNode|OpNode, Metaedge>(name, GraphType.META, opt); + /** bridgegraph must be constructed lazily-see hierarchy.getBridgegraph() */ + this.bridgegraph = null; + /** + * A dictionary that count ops type of nodes in this metanode + * (op type => count). + */ + this.opHistogram = {}; + this.deviceHistogram = {}; + /** unique id for a metanode of similar subgraph */ + this.templateId = null; + /** Metanode which contains this node, if any */ + this.parentNode = null; + this.stats = new NodeStats(0, 0, null); + this.hasNonControlEdges = false; + } + + getFirstChild(): GroupNode|OpNode { + return this.metagraph.node(this.metagraph.nodes()[0]); + } + + /** + * Returns the op node associated with the metanode. + * For example, if the metanode is "sgd", the associated + * op node is sgd/(sgd). + */ + getRootOp(): OpNode { + let nameSplit = this.name.split("/"); + let rootOpName = this.name + "/(" + nameSplit[nameSplit.length - 1] + ")"; + return <OpNode>this.metagraph.node(rootOpName); + } + + /** + * Return an array of the names of all the leaves (non-GroupNodes) inside + * this metanode. This performs a breadth-first search of the tree, so + * immediate child leaves will appear earlier in the output array than + * descendant leaves. + */ + leaves(): string[] { + let leaves = []; + let queue = [<Node> this]; + let metagraph; // Defined here due to a limitation of ES6->5 compilation. + while (queue.length) { + let node = queue.shift(); + if (node.isGroupNode) { + metagraph = (<GroupNode> node).metagraph; + _.each(metagraph.nodes(), name => queue.push(metagraph.node(name))); + } else { + leaves.push(node.name); + } + } + return leaves; + } +}; + +export interface Metaedge extends graphlib.EdgeObject { + + /** + * Stores the original BaseEdges represented by this Metaedge. + */ + baseEdgeList: BaseEdge[]; + + /** + * Whether this edge represents a relationship that is inbound (or outbound) + * to the object which contains this information. For example, in a Metanode's + * bridgegraph, each edge connects an immediate child to something outside + * the Metanode. If the destination of the edge is inside the Metanode, then + * its inbound property should be true. If the destination is outside the + * Metanode, then its inbound property should be false. + * + * The property is optional because not all edges can be described as + * inbound/outbound. For example, in a Metanode's metagraph, all of the edges + * connect immediate children of the Metanode. None should have an inbound + * property, or they should be null/undefined. + */ + inbound?: boolean; + + /** + * Number of regular edges (not control dependency edges). + */ + numRegularEdges: number; + + /** + * Number of control dependency edges. + */ + numControlEdges: number; + + /** + * Number of reference edges, which is an edge to an operation + * that takes a reference to its input and changes its value. + */ + numRefEdges: number; + + addBaseEdge(edge: BaseEdge): void; +} + +export function createMetaedge(v: string, w: string): Metaedge { + return new MetaedgeImpl(v, w); +} + +/** + * A label object for edges between metanodes of subgraphs in the render graph. + */ +class MetaedgeImpl implements Metaedge { + v: string; + w: string; + baseEdgeList: BaseEdge[]; + inbound: boolean; + numRegularEdges: number; + numControlEdges: number; + numRefEdges: number; + + constructor(v: string, w: string) { + this.v = v; + this.w = w; + this.baseEdgeList = []; + this.inbound = null; + this.numRegularEdges = 0; + this.numControlEdges = 0; + this.numRefEdges = 0; + } + + addBaseEdge(edge: BaseEdge): void { + this.baseEdgeList.push(edge); + if (edge.isControlDependency) { + this.numControlEdges += 1; + } else { + this.numRegularEdges += 1; + } + if (edge.isReferenceEdge) { + this.numRefEdges += 1; + } + } +} + +export function createSeriesNode(prefix: string, suffix: string, + parent: string, clusterId: number, name: string): SeriesNode { + return new SeriesNodeImpl(prefix, suffix, parent, clusterId, name); +} + +export function getSeriesNodeName(prefix: string, suffix: string, + parent: string, startId?: number, endId?: number): string { + let numRepresentation = + (typeof startId !== "undefined" && typeof endId !== "undefined") ? + "[" + startId + "-" + endId + "]" : "#"; + let pattern = prefix + numRepresentation + suffix; + return (parent ? parent + "/" : "") + pattern; +} + +class SeriesNodeImpl implements SeriesNode { + name: string; + type: NodeType; + stats: NodeStats; + hasLoop: boolean; + prefix: string; + suffix: string; + clusterId: number; + ids: number[]; + parent: string; + isGroupNode: boolean; + cardinality: number; + metagraph: graphlib.Graph<GroupNode|OpNode, Metaedge>; + bridgegraph: graphlib.Graph<GroupNode|OpNode, Metaedge>; + parentNode: Node; + deviceHistogram: {[op: string]: number}; + hasNonControlEdges: boolean; + + constructor(prefix: string, suffix: string, parent: string, + clusterId: number, name: string) { + this.name = name || getSeriesNodeName(prefix, suffix, parent); + this.type = NodeType.SERIES; + this.hasLoop = false; + this.prefix = prefix; + this.suffix = suffix; + this.clusterId = clusterId; + this.ids = []; + this.parent = parent; + this.isGroupNode = true; + this.cardinality = 0; + this.metagraph = createGraph<Metanode, Metaedge>(name, GraphType.SERIES); + // bridgegraph must be constructed lazily-see hierarchy.getBridgegraph() + this.bridgegraph = null; + this.parentNode = null; + this.deviceHistogram = {}; + this.hasNonControlEdges = false; + this.stats = new NodeStats(0, 0, null); + } +} + +/** + * Normalizes the inputs and extracts associated metadata: + * 1) Inputs can contain a colon followed by a number at the end + * (e.g. inputName:1) and we remove this from the input name, and take note + * that the input was numbered. + * 2) Control dependency inputs contain caret at the beginning and we + * remove this and annotate the edge as a control dependency. + * @param inputs Array of unnormalized names of input nodes. + */ +function normalizeInputs(inputs: string[]): NormalizedInput[] { + return _.reduce(inputs, function(normalizedInputs, inputName) { + let start = inputName[0] === "^"; + let colon = inputName.lastIndexOf(":"); + let end = colon !== -1 && + inputName.length - colon > 1 && + !(/\D/).test(inputName.substring(colon + 1)) ? + colon : inputName.length; + let name = inputName.substring(start ? 1 : 0, end); + if (normalizedInputs.length === 0 || + name !== normalizedInputs[normalizedInputs.length - 1].name) { + normalizedInputs.push({ + name: name, + hasNumberPart: end !== inputName.length, + isControlDependency: start + }); + } + return normalizedInputs; + }, []); +} + +export function build(rawNodes: tf.TFNode[], params: BuildParams, + tracker: ProgressTracker): Promise<SlimGraph|void> { + /** + * A dictionary that maps each in-embedding node name to its host node label + * object. + */ + let inEmbedding: {[nodeName: string]: OpNode} = {}; + /** + * A dictionary that maps each node name to an array of the node's + * out-embedding node label objects. + */ + let outEmbeddings: {[inputName: string]: OpNode[]} = {}; + let isInEmbeddedPred = getEmbedPredicate(params.inEmbeddingTypes); + let isOutEmbeddedPred = getEmbedPredicate(params.outEmbeddingTypes); + let embeddingNodeNames: string[] = []; + /** + * A list of all the non-embedding node names which appear in the processed + * list of raw nodes. Here we pre-allocate enough room for all the rawNodes, + * even though there will some number of embeddings. The excess array length + * is spliced off later. + * + * Experimentation shows that around 30% of the array will go unused, and + * even for very large networks that amounts to less than 10k spaces. + */ + let nodeNames = new Array<string>(rawNodes.length); + + return runAsyncTask("Normalizing names", 30, () => { + let opNodes = new Array<OpNode>(rawNodes.length); + let index = 0; + _.each(rawNodes, rawNode => { + let normalizedInputs = normalizeInputs(rawNode.input); + let opNode = new OpNodeImpl(rawNode, normalizedInputs); + if (isInEmbeddedPred(opNode)) { + embeddingNodeNames.push(opNode.name); + inEmbedding[opNode.name] = opNode; + return; + } + + if (isOutEmbeddedPred(opNode)) { + embeddingNodeNames.push(opNode.name); + _.each(opNode.inputs, input => { + let inputName = input.name; + outEmbeddings[inputName] = outEmbeddings[inputName] || []; + outEmbeddings[inputName].push(opNode); + }); + return; + } + // The node is not an embedding, so add it to the names and nodes lists. + opNodes[index] = opNode; + nodeNames[index] = opNode.name; + index++; + }); + opNodes.splice(index); + nodeNames.splice(index); + return opNodes; + }, tracker) + .then((opNodes) => { + // Create the graph data structure from the graphlib library. + return runAsyncTask("Building the data structure", 70, () => { + let normalizedNameDict = mapStrictHierarchy(nodeNames, + embeddingNodeNames); + let graph = new SlimGraph; + + // Add the nodes to the graph. + _.each(opNodes, opNode => { + let normalizedName = normalizedNameDict[opNode.name] || opNode.name; + graph.nodes[normalizedName] = opNode; + // Check if the node has out-embeddings. If yes, add them to to the + // node. + if (opNode.name in outEmbeddings) { + opNode.outEmbeddings = outEmbeddings[opNode.name]; + // Normalize the names of the out-embeddings. + _.each(opNode.outEmbeddings, node => { + node.name = normalizedNameDict[node.name] || node.name; + }); + } + // Update the name of the node. + opNode.name = normalizedName; + }); + + // Visit each node's inputs to add the edges to the graph. If the input + // is an in-embedding, then add it to the node's in-embeddings instead. + _.each(opNodes, opNode => { + _.each(opNode.inputs, (input, i) => { + let inputName = input.name; + if (inputName in inEmbedding) { + opNode.inEmbeddings.push(inEmbedding[inputName]); + } else { + graph.edges.push({ + v: normalizedNameDict[inputName] || inputName, + w: opNode.name, + isControlDependency: input.isControlDependency, + // Check if this op type and input number corresponds to a + // reference edge using the refEdges dictionary in the params. + isReferenceEdge: (params.refEdges[opNode.op + " " + i] === true) + }); + } + }); + }); + + // Normalize the names of in-embeddings. + _.each(inEmbedding, (node, name) => { + node.name = normalizedNameDict[node.name] || node.name; + }); + + return graph; + }, tracker); + }) + .catch(function(reason) { + throw new Error("Failure creating graph"); + }); +}; + +/** + * Create a new graphlib.Graph() instance with default parameters + */ +export function createGraph<N, E>(name: string, type, opt = {}): + graphlib.Graph<N, E> { + let graph = new graphlib.Graph<N, E>(opt); + graph.setGraph({ + name: name, + rankdir: "BT", // BT,TB,LR,RL + type: type + }); + return graph; +}; + +/** + * Create a predicate for checking whether a node should be embedded based on + * the specified types. + */ +function getEmbedPredicate(types: string[]) { + return function(node) { + // check types + for (let i = 0; i < types.length; i++) { + let regExp = new RegExp(types[i]); + if (node.op.match(regExp)) { return true; } + } + return false; + }; +}; + +/** + * Returns a strict node name (name => name/(name)) to avoid conflicts + * where the node name is also a namespace. + */ +function getStrictName(name: string): string { + let parts = name.split(NAMESPACE_DELIM); + return name + NAMESPACE_DELIM + "(" + parts[parts.length - 1] + ")"; +} + +/** + * For each op node (embedding or non-embedding), rename it if there is a + * non-embedding node under its namespace. For example, assume node name "A". + * If there is a non-embedding node under its namespace (e.g. "A/B"), "A" will + * be renamed to "A/(A)". Then the namespace "A" will contain 2 nodes: "(A)" + * and "B". If all the nodes under "A" are embedding nodes (e.g. constant and + * summary), keep "A" as an Op node and don't create a namespace. + * + * @param nodeNames An array of regular (non-embedding) node names. + * @param embeddingNodeNames An array of embedding node names. + * @return Dictionary object mapping names that need to be renamed to + * new names. + */ +function mapStrictHierarchy(nodeNames: string[], + embeddingNodeNames: string[]): {[oldName: string]: string} { + /** Dictionary that maps the old new to the new name */ + let newNameDictionary: {[oldName: string]: string} = {}; + /** Set used to store all namespaces. */ + let namespaceSet: {[namespace: string]: boolean} = {}; + // sort the nodes to make prefix check faster + nodeNames.sort(); + // look for nodes with a prefix a,a/b -> a/(a),a/b + for (let i = 0; i < nodeNames.length - 1; ++i) { + let a = nodeNames[i]; + // Get all the parent namespaces of the current node + // and add them in the namespace set. + _.each(getHierarchicalPath(a).slice(0, -1), ns => { + namespaceSet[ns] = true; + }); + let b = nodeNames[i + 1]; + if (_.startsWith(b, a + NAMESPACE_DELIM)) { + newNameDictionary[a] = getStrictName(a); + } + } + // Go through all the embedding node names and rename them in case they + // collide with namespaces. + _.each(embeddingNodeNames, embeddingName => { + if (embeddingName in namespaceSet) { + // Rename to follow strict hierarchy. + newNameDictionary[embeddingName] = getStrictName(embeddingName); + } + }); + return newNameDictionary; +}; + +/** + * Returns a list of the degrees of each node in the graph. + */ +function degreeSequence(graph: graphlib.Graph<any, any>): number[] { + let degrees = graph.nodes().map(function(name) { + return graph.neighbors(name).length; + }); + degrees.sort(); + return degrees; +}; + +/** + * Returns if the degree sequence of the two graphs is the same. + */ +export function hasSimilarDegreeSequence(graph1: graphlib.Graph<any, any>, + graph2: graphlib.Graph<any, any>): boolean { + let dg1 = degreeSequence(graph1); + let dg2 = degreeSequence(graph2); + + for (let i = 0; i < dg1.length; i++) { + if (dg1[i] !== dg2[i]) { + return false; + } + } + return true; +}; + +/** + * Returns the hierarchical path of the current node, based on the node's name. + * For example, if the name is 'a/b/c', the returned path is ['a', 'a/b', 'a/b/c']. + */ +export function getHierarchicalPath(name: string, + seriesNames?: { [name: string]: string }): string[] { + let path: string[] = []; + let i = name.indexOf(NAMESPACE_DELIM); + // Push all parent portions of the path. + while (i >= 0) { + path.push(name.substring(0, i)); + i = name.indexOf(NAMESPACE_DELIM, i + 1); + } + // If the node's path is under a series, then add the series node name to the + // hierarchical path as the parent of the leaf. + if (seriesNames) { + let seriesName = seriesNames[name]; + if (seriesName) { + path.push(seriesName); + } + } + // Push the leaf of the path. + path.push(name); + return path; +}; + +} // close module tf.graph diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/hierarchy.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/hierarchy.ts new file mode 100644 index 0000000000..6c9333de4c --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/hierarchy.ts @@ -0,0 +1,715 @@ +/// <reference path="graph.ts" /> +/// <reference path="template.ts" /> + +/** + * Package for the Graph Hierarchy for TensorFlow graph. + */ +module tf.graph.hierarchy { + +const LOG_PREFIX_MSG = "Graph hierarchy: "; + +/** + * Class used as output for getPredecessors and getSuccessors methods + */ +interface Edges { + control: string[]; + regular: string[]; +} + +export interface Hierarchy { + root: Metanode; + templates: {[templateId: string]: string[]}; + /** List of all device names */ + devices: string[]; + getNodeMap(): {[nodeName: string]: GroupNode|OpNode}; + node(name: string): GroupNode|OpNode; + setNode(name: string, node: GroupNode|OpNode): void; + getBridgegraph(nodeName: string): graphlib.Graph<GroupNode|OpNode, Metaedge>; + getPredecessors(nodeName: string): Edges; + getSuccessors(nodeName: string): Edges; + getTopologicalOrdering(nodeName: string): { [childName: string]: number }; +} + +/** + * Class for the Graph Hierarchy for TensorFlow graph. + */ +class HierarchyImpl implements Hierarchy { + root: Metanode; + templates: {[templateId: string]: string[]}; + private index: {[nodeName: string]: GroupNode|OpNode}; + devices: string[]; + orderings: { [nodeName: string]: { [childName: string]: number } }; + + constructor() { + this.root = createMetanode(ROOT_NAME, {compound: true}); + this.templates = null; + this.devices = null; + /** + * @type {Object} Dictionary object that maps node name to the node + * (could be op-node, metanode, or series-node) + */ + this.index = {}; + this.index[ROOT_NAME] = this.root; + this.orderings = {}; + } + + getNodeMap(): {[nodeName: string]: GroupNode|OpNode} { + return this.index; + } + + node(name: string): GroupNode|OpNode { + return this.index[name]; + } + + setNode(name: string, node: GroupNode|OpNode): void { + this.index[name] = node; + } + + /** + * Given the name of a node in this hierarchy, get its bridgegraph, creating + * it on the fly if necessary. If the node is not a GroupNode, then this + * method returns null. If the provided name does not map to a node in the + * hierarchy, an error will be thrown. + */ + getBridgegraph(nodeName: string): graphlib.Graph<GroupNode|OpNode, Metaedge> { + let node = this.index[nodeName]; + if (!node) { + throw Error("Could not find node in hierarchy: " + nodeName); + } + if (!("metagraph" in node)) { + return null; + } + let groupNode = <GroupNode> node; + if (groupNode.bridgegraph) { + return groupNode.bridgegraph; + } + let bridgegraph = groupNode.bridgegraph = + createGraph<GroupNode|OpNode, Metaedge>( + "BRIDGEGRAPH", GraphType.BRIDGE); + if (!node.parentNode || !("metagraph" in node.parentNode)) { + return bridgegraph; + } + + let parentNode = <GroupNode>node.parentNode; + let parentMetagraph = parentNode.metagraph; + let parentBridgegraph = this.getBridgegraph(parentNode.name); + + // For each of the parent node's two Metaedge containing graphs, process + // each Metaedge involving this node. + _.each([parentMetagraph, parentBridgegraph], parentGraph => { + _(parentGraph.edges()) + .filter(e => e.v === nodeName || e.w === nodeName) + .each(parentEdgeObj => { + + let inbound = parentEdgeObj.w === nodeName; + let parentMetaedge = parentGraph.edge(parentEdgeObj); + + // The parent's Metaedge represents some number of underlying + // BaseEdges from the original full graph. For each of those, we need + // to determine which immediate child is involved and make sure + // there's a Metaedge in the bridgegraph that covers it. + _.each(parentMetaedge.baseEdgeList, baseEdge => { + + // Based on the direction, figure out which is the descendant node + // and which is the "other" node (sibling of parent or ancestor). + let [descendantName, otherName] = + inbound ? + [baseEdge.w, parentEdgeObj.v] : + [baseEdge.v, parentEdgeObj.w]; + + // Determine the immediate child containing this descendant node. + let childName = this.getChildName(nodeName, descendantName); + + // Look for an existing Metaedge in the bridgegraph (or create a + // new one) that covers the relationship between child and other. + let bridgeEdgeObj = <graphlib.EdgeObject> { + v: inbound ? otherName : childName, + w: inbound ? childName : otherName, + }; + let bridgeMetaedge = bridgegraph.edge(bridgeEdgeObj); + if (!bridgeMetaedge) { + bridgeMetaedge = createMetaedge(bridgeEdgeObj.v, bridgeEdgeObj.w); + bridgeMetaedge.inbound = inbound; + bridgegraph.setEdge(bridgeEdgeObj.v, bridgeEdgeObj.w, + bridgeMetaedge); + } + + // Copy the BaseEdge from the parent's Metaedge into this + // bridgegraph Metaedge. + bridgeMetaedge.addBaseEdge(baseEdge); + }); + }) + .value(); // force lodash chain execution. + }); + + return bridgegraph; + } + + /** + * Utility function for determining the name of the immediate child under a + * node for a given descendant path. If the descendant corresponds to no + * immediate child, an error is thrown. + */ + getChildName(nodeName: string, descendantName: string): string { + // Walk up the hierarchy from the descendant to find the child. + let currentNode: Node = this.index[descendantName]; + while (currentNode) { + if (currentNode.parentNode && currentNode.parentNode.name === nodeName) { + return currentNode.name; + } + currentNode = currentNode.parentNode; + } + throw Error("Could not find immediate child for descendant: " + + descendantName); + }; + + /** + * Given the name of a node, return the names of its predecssors. + * For an OpNode, this will contain the targets from the underlying BaseEdges. + * For a GroupNode, this will contain the targets truncated to siblings of + * the shared ancestor. + * + * For example, consider an original non-control BaseEdge A/B/C->Z/Y/X. Their + * shared ancestor is the ROOT node. A and Z are the highest siblings. Here + * are the results of calling getPredecessors(): + * + * - getPredecessors("Z/Y/X") === {regular: ["A/B/C"], control: []}; + * - getPredecessors("Z/Y") === {regular: ["A"], control: []}; + * - getPredecessors("Z") === {regular: ["A"], control: []}; + * + * The reason getPredecessors("Z/Y") returns ["A"] (and not ["A/B"] as you + * might intuitively expect) is because it's not clear how far down the + * other end of the hierarchy to traverse in the general case. + * + * Continuing this example, say there was another BaseEdge A/K->Z/Y/W. When + * we look at Z/Y's predecessors, the best we can say is ["A"] without getting + * into the details of which of of Z/Y's descendant nodes have predecessors to + * which of A's descendants. + * + * On the other hand, for an OpNode it's clear what the final predecssors + * ought to be. There is no ambiguity. + */ + getPredecessors(nodeName: string): Edges { + let node = this.index[nodeName]; + if (!node) { + throw Error("Could not find node with name: " + nodeName); + } + + let predecessors = this.getOneWayEdges(node, true); + + // Add embedded predecessors, such as constants. + if (!node.isGroupNode) { + _.each((<OpNode>node).inEmbeddings, embeddedNode => { + predecessors.regular.push(embeddedNode.name); + }); + } + return predecessors; + } + + /** + * Given the name of a node, return an array of the names of its successors. + * For an OpNode, this will contain the targets from the underlying BaseEdges. + * For a GroupNode, this will contain the targets truncated to sibling of + * the shared ancestor. + * + * This is the inverse of getPredecessors(). See that method's documentation + * for an in-depth example. + */ + getSuccessors(nodeName: string): Edges { + let node = this.index[nodeName]; + if (!node) { + throw Error("Could not find node with name: " + nodeName); + } + + let successors = this.getOneWayEdges(node, false); + + // Add embedded successors, such as summaries. + if (!node.isGroupNode) { + _.each((<OpNode>node).outEmbeddings, embeddedNode => { + successors.regular.push(embeddedNode.name); + }); + } + return successors; + } + + /** Helper method for getPredeccessors and getSuccessors */ + getOneWayEdges(node: GroupNode|OpNode, inEdges: boolean) { + let edges = { control: [], regular: [] }; + // A node with no parent cannot have any edges. + if (!node.parentNode) { + return edges; + } + if (node.parentNode.isGroupNode) { + let parentNode = <GroupNode>node.parentNode; + let metagraph = parentNode.metagraph; + let bridgegraph = this.getBridgegraph(parentNode.name); + findEdgeTargetsInGraph(metagraph, node, inEdges, edges); + findEdgeTargetsInGraph(bridgegraph, node, inEdges, edges); + } + return edges; + } + + /** + * For a given GroupNode, get or calculate an object which describes a + * topological ordering of child nodes within that GroupNode's metagraph. + * + * This ordering is used when rendering bridge control edges which are + * sometimes backwards relative to the dataflow. + * + * For example, say we have a graph with two edges A->B and A->C, and we're + * interested in the ordering under ROOT. In this case, any of the following + * would be legitimate return values: + * + * - { "A": 0, "B": 1, "C": 2 } -- most likely + * - { "A": 0, "B": 2, "C": 1 } -- less likely + * - { "A": 12, "B": 100, "C": 99 } -- unlikely, but still OK + * + * The algorithm does not guarantee that all numbers from 0-N (where N is + * the number of nodes) appear exactly once. Rather it guarantees that if + * there is a path between two nodes, the earlier one will have a lower + * number in the ordering hash. + * + * When generating the ordering, we ignore control Metaedges (those which + * represent only BaseEdges that have isControlDependency set to true). + * + * If there is no node with the specified name, an error is thrown. If the + * node with the specified name is not a group node, null is returned. + */ + getTopologicalOrdering(nodeName: string): { [childName: string]: number } { + let node = this.index[nodeName]; + if (!node) { + throw Error("Could not find node with name: " + nodeName); + } + if (!node.isGroupNode) { + return null; + } + if (nodeName in this.orderings) { + return this.orderings[nodeName]; + } + + // Mapping of a child node names to lists of their successors. + let successors: { [childName: string]: string[] } = {}; + + // Set of node names which have appeared as a destination. + let destinations: { [childName: string]: boolean } = {}; + + let metagraph = (<GroupNode> node).metagraph; + _.each(metagraph.edges(), (e: graphlib.EdgeObject) => { + if (!metagraph.edge(e).numRegularEdges) { + return; // Skip control edges. + } + + // Keep track of successors and destinations. + if (!(e.v in successors)) { + successors[e.v] = []; + } + successors[e.v].push(e.w); + destinations[e.w] = true; + }); + + // Seed the queue with true sources (those that are not destinations). + let queue: string[] = + _.difference(_.keys(successors), _.keys(destinations)); + + // Produce an ordering by traversing the graph breadth first. + let ordering = this.orderings[nodeName] = {}; + let index = 0; + while (queue.length) { + let childName = queue.shift(); + ordering[childName] = index++; + _.each(successors[childName], succName => queue.push(succName)); + delete successors[childName]; // Prevent cycles from infinite looping. + } + return ordering; + } + +} + +/** + * Internal utility function - given a graph (should be either a metagraph or a + * bridgegraph) and a node which is known to be in that graph, determine + * the other ends of edges that involve that node in the direction specified + * by whether it's inbound. + * + * For example if you wanted to find the predecessors of a node, you'd call + * this method for the parent's metagraph and bridgegraph, specifying inbound + * as true (look at the source of inbound edges to the specified node). + * + * Discovered target names are appended to the targets array. + */ +function findEdgeTargetsInGraph( + graph: graphlib.Graph<GroupNode|OpNode, Metaedge>, + node: Node, inbound: boolean, targets: Edges): void { + _.each(<Metaedge[]> graph.edges(), e => { + let [selfName, otherName] = inbound ? [e.w, e.v] : [e.v, e.w]; + if (selfName === node.name) { + if (node.isGroupNode) { + let targetList = graph.edge(e).numRegularEdges + ? targets.regular : targets.control; + targetList.push(otherName); + } else { + _.each(graph.edge(e).baseEdgeList, baseEdge => { + let targetList = baseEdge.isControlDependency + ? targets.control : targets.regular; + targetList.push(inbound ? baseEdge.v : baseEdge.w); + }); + } + } + }); +} + +interface HierarchyParams { + verifyTemplate: boolean; + groupSeries: boolean; +} + +/** + * @param graph The raw graph. + * @param params Parameters used when building a hierarchy. + */ +export function build(graph: tf.graph.SlimGraph, params: HierarchyParams, + tracker: ProgressTracker): Promise<Hierarchy|void> { + let h = new HierarchyImpl(); + let seriesNames: { [name: string]: string } = {}; + return runAsyncTask("Adding nodes", 20, () => { + // Get all the possible device names. + let deviceNames = {}; + _.each(graph.nodes, (node, nodeName) => { + if (node.device != null) { + deviceNames[node.device] = true; + } + }); + h.devices = _.keys(deviceNames); + addNodes(h, graph); + }, tracker) + .then(() => { + return runAsyncTask("Detect series", 20, () => { + if (params.groupSeries) { + groupSeries(h.root, h, seriesNames); + } + }, tracker); + }) + .then(() => { + return runAsyncTask("Adding edges", 30, () => { + addEdges(h, graph, seriesNames); + }, tracker); + }) + .then(() => { + return runAsyncTask("Finding similar subgraphs", 30, () => { + h.templates = template.detect(h, params.verifyTemplate); + }, tracker); + }) + .then(() => { + return h; + }).catch(function(reason) { + throw new Error("Failure creating graph hierarchy"); + }); +}; + +/** + * Creates the metanodes in the hierarchical graph and assigns parent-child + * relationship between them. + */ +function addNodes(h: Hierarchy, graph: SlimGraph) { + _.each(graph.nodes, (node, nodeName) => { + let path = getHierarchicalPath(node.name); + let parent: Metanode = h.root; + + parent.depth = Math.max(path.length, parent.depth); + + // Create parent metanodes for each depth. For example if the node name + // is 'a/b/c', then create metanodes 'a' and 'a/b', where 'a/b' is a child + // of a. + for (let i = 0; i < path.length; i++) { + parent.depth = Math.max(parent.depth, path.length - i); + parent.cardinality += node.cardinality; + parent.opHistogram[node.op] = (parent.opHistogram[node.op] || 0) + 1; + if (node.stats) { + parent.stats.combine(node.stats); + } + if (node.device != null) { + parent.deviceHistogram[node.device] = + (parent.deviceHistogram[node.device] || 0) + 1; + } + if (i === path.length - 1) { break; } + let name = path[i]; + let child = <Metanode>h.node(name); + if (!child) { + child = createMetanode(name); + child.parentNode = parent; + h.setNode(name, child); + parent.metagraph.setNode(name, child); + } + parent = child; + } + // Assuming node name is 'a/b/c', assign the OpNode as a child of the metanode 'a/b'. + h.setNode(node.name, node); + node.parentNode = parent; + parent.metagraph.setNode(node.name, node); + + // Add each of the in-embeddings and out-embeddings in the hierarchy. + _.each(node.inEmbeddings, function(embedding) { + h.setNode(embedding.name, embedding); + embedding.parentNode = node; + }); + _.each(node.outEmbeddings, function(embedding) { + h.setNode(embedding.name, embedding); + embedding.parentNode = node; + }); + }); +}; + +/** + * For each metanode in the hierarchical graph, this method adds: + * the edges in the metagraph. These are edges between nodes + * that share the same parent. + */ +function addEdges(h: Hierarchy, graph: SlimGraph, + seriesNames: { [name: string]: string }) { + + let nodeIndex = h.getNodeMap(); + + // Ancestor paths for the source and destination nodes of an edge. These are + // reused for each edge rather than allocating new ones. It's about 10% faster + // than allocating new ones on each pass through the loop. + let sourcePath: string[] = []; + let destPath: string[] = []; + + // Insert the ancestor path for a node into the provided array, including the + // node itself. Return the index of the last node inserted (always ROOT). + let getPath = (node: Node, path: string[]): number => { + let i = 0; + while (node) { + path[i++] = node.name; + node = node.parentNode; + } + return i - 1; + }; + + _.each(graph.edges, baseEdge => { + + // Get the hierarchical paths for the source and destination of the edge. + let sourceAncestorIndex = getPath(graph.nodes[baseEdge.v], sourcePath); + let destAncestorIndex = getPath(graph.nodes[baseEdge.w], destPath); + + // Find the lowest shared ancestor between source and dest by looking for + // the highest nodes that differ between their ancestor paths. + while (sourcePath[sourceAncestorIndex] === destPath[destAncestorIndex]) { + sourceAncestorIndex--; + destAncestorIndex--; + if (sourceAncestorIndex < 0 || destAncestorIndex < 0) { + // This would only occur if the two nodes were the same (a cycle in the + // graph), or if one endpoint was a strict ancestor of the other. The + // latter shouldn't happen because we rename nodes which are both + // metanodes and op nodes. E.g. "A/B" becomes "A/B/(B)". + throw Error("No difference found between ancestor paths."); + } + } + + let sharedAncestorNode = + <GroupNode>nodeIndex[sourcePath[sourceAncestorIndex + 1]]; + let sourceAncestorName = sourcePath[sourceAncestorIndex]; + let destAncestorName = destPath[destAncestorIndex]; + + // Find or create the Metaedge which should contain this BaseEdge inside + // the shared ancestor. + let metaedge = + sharedAncestorNode.metagraph.edge(sourceAncestorName, destAncestorName); + if (!metaedge) { + metaedge = createMetaedge(sourceAncestorName, destAncestorName); + sharedAncestorNode.metagraph + .setEdge(sourceAncestorName, destAncestorName, metaedge); + } + if (!sharedAncestorNode.hasNonControlEdges && + !baseEdge.isControlDependency) { + sharedAncestorNode.hasNonControlEdges = true; + } + metaedge.addBaseEdge(baseEdge); + + }); + +}; + +/** + * Using the hierarchy template information, detect series in the provided + * metanode. For each detected series, create a new SeriesNode + * and remove series members from the metanode's metagraph and move them to + * the new series node's metagraph. + * + * @param metanode + * @param hierarchy + * @return A dictionary from node name to series node name that contains the node + */ +function groupSeries(metanode: Metanode, hierarchy: Hierarchy, + seriesNames: { [name: string]: string }) { + let metagraph = metanode.metagraph; + _.each(metagraph.nodes(), n => { + let child = metagraph.node(n); + if (child.type === tf.graph.NodeType.META) { + groupSeries(<Metanode>child, hierarchy, seriesNames); + } + }); + + let clusters = clusterNodes(metagraph); + let seriesDict = detectSeries(clusters, metagraph); + + // Add each series node to the graph and add its grouped children to its own + // metagraph. + _.each(seriesDict, function(seriesNode: SeriesNode, seriesName: string) { + let nodeMemberNames = seriesNode.metagraph.nodes(); + let firstMember = seriesNode.metagraph.node(nodeMemberNames[0]); + let seriesType = firstMember.type; + + hierarchy.setNode(seriesName, seriesNode); // add to the index + metagraph.setNode(seriesName, seriesNode); + _.each(nodeMemberNames, n => { + let child = <OpNode> metagraph.node(n); + seriesNode.metagraph.setNode(n, child); + seriesNode.parentNode = child.parentNode; + seriesNode.cardinality++; + if (child.device != null) { + seriesNode.deviceHistogram[child.device] = + (seriesNode.deviceHistogram[child.device] || 0) + 1; + } + child.parentNode = seriesNode; + seriesNames[n] = seriesName; + + if (child.stats) { + seriesNode.stats.combine(child.stats); + } + + // Remove now-grouped node from its original parent's metagraph. + metagraph.removeNode(n); + }); + }); +}; + +/** cluster op-nodes with similar op */ +function clusterNodes(metagraph: graphlib.Graph<GroupNode|OpNode, Metaedge>): + {[clusterId: string]: string[]} { + let result: {[clusterId: string]: string[]} = {}; + return _.reduce(metagraph.nodes(), function(clusters: {[clusterId: string]: string[]}, n: string) { + let child = metagraph.node(n); + if (child.type === NodeType.META) { + // skip metanodes + return clusters; + } + let template = (<OpNode>child).op; + if (template) { + clusters[template] = clusters[template] || []; + clusters[template].push(child.name); + } + return clusters; + }, result); +} + +/** + * For each cluster of op-nodes based op type, try to detect groupings. + * Infer series name using by trying to find pattern "<number>" in the node + * name. + * + * @param clusters Dictionary output from clusterNodes(). + * @param metagraph + * @return A dictionary from series name => seriesNode + */ +function detectSeries(clusters: {[clusterId: string]: string[]}, + metagraph: graphlib.Graph<GroupNode|OpNode, Metaedge>): + {[seriesName: string]: SeriesNode} { + let seriesDict: {[seriesName: string]: SeriesNode} = {}; + _.each(clusters, function(members, clusterId: string) { + if (members.length <= 1) { return; } // isolated clusters can't make series + + /** @type {Object} A dictionary mapping seriesName to seriesInfoArray, + * which is an array that contains objects with name, id, prefix, suffix, + * and parent properties. + */ + let candidatesDict = {}; + + // Group all nodes that have the same name, with the exception of a + // number at the end of the name after an underscore, which is allowed to + // vary. + _.each(members, function(name: string) { + let isGroup = name.charAt(name.length - 1) === "*"; + let namepath = name.split("/"); + let leaf = namepath[namepath.length - 1]; + let parent = namepath.slice(0, namepath.length - 1).join("/"); + let matches = leaf.match(/^(\D*)_(\d+)$/); + + let prefix; + let id; + let suffix = ""; + if (matches) { // if found "<number>" in the name, assign id. + prefix = matches[1]; // the front non-numeric characters + id = matches[2]; // the digits + } else { // for node without "_<number>", make them zero-th items. + prefix = isGroup ? leaf.substr(0, leaf.length - 1) : leaf; + if (prefix.charAt(prefix.length - 1) !== "_") { + prefix += "_"; + } + id = 0; + suffix = isGroup ? "*" : ""; + } + let seriesName = getSeriesNodeName(prefix, suffix, parent); + candidatesDict[seriesName] = candidatesDict[seriesName] || []; + let seriesNode = createSeriesNode(prefix, suffix, parent, +id, name); + candidatesDict[seriesName].push(seriesNode); + }); + + // In each group of nodes, group nodes in bunches that have monotonically + // increasing numbers in their names. Each of these bunches is a series. + _.each(candidatesDict, function(seriesInfoArray: SeriesNode[], seriesName) { + if (seriesInfoArray.length < 2) { + return; + } + seriesInfoArray.sort(function(a, b) { + return (+a.clusterId) - (+b.clusterId); + }); + + // Loop through the nodes sorted by its detected series number, grouping + // all nodes with monotonically-increasing series numbers. + let seriesNodes = [seriesInfoArray[0]]; + for (let index = 1; index < seriesInfoArray.length; index++) { + let nextNode = seriesInfoArray[index]; + if (nextNode.clusterId === seriesNodes[seriesNodes.length - 1].clusterId + 1) { + seriesNodes.push(nextNode); + continue; + } + addSeriesToDict(seriesNodes, seriesDict, +clusterId, metagraph); + seriesNodes = [nextNode]; + } + addSeriesToDict(seriesNodes, seriesDict, +clusterId, metagraph); + }); + }); + return seriesDict; +} + +/** + * Add a series to the provided dictionary mapping series names to series. + * + * @param seriesNodes the nodes in the series. Contains + * name, id, prefix, suffix and parent properties of the node. + * @param seriesDict the dictionary of series + * @param clusterId ID of the template of the nodes of the series + * @param metagraph + */ +function addSeriesToDict(seriesNodes: SeriesNode[], + seriesDict: {[seriesName: string] : SeriesNode}, + clusterId: number, + metagraph: graphlib.Graph<GroupNode|OpNode, Metaedge>) { + if (seriesNodes.length > 1) { + let curSeriesName = getSeriesNodeName( + seriesNodes[0].prefix, seriesNodes[0].suffix, + seriesNodes[0].parent, seriesNodes[0].clusterId, + seriesNodes[seriesNodes.length - 1].clusterId); + let curSeriesNode = createSeriesNode(seriesNodes[0].prefix, + seriesNodes[0].suffix, seriesNodes[0].parent, clusterId, + curSeriesName); + _.each(seriesNodes, function(node) { + curSeriesNode.ids.push(node.clusterId); + curSeriesNode.metagraph.setNode(node.name, metagraph.node(node.name)); + }); + seriesDict[curSeriesName] = curSeriesNode; + } +} + +} // close module tf.graph.hierarchy diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/layout.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/layout.ts new file mode 100644 index 0000000000..4eb3cab011 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/layout.ts @@ -0,0 +1,628 @@ +/// <reference path="graph.ts" /> +/// <reference path="render.ts" /> + +module tf.graph.layout { + +/** Set of parameters that define the look and feel of the graph. */ +export const PARAMS = { + animation: { + /** Default duration for graph animations in ms. */ + duration: 250 + }, + graph: { + /** Graph parameter for metanode. */ + meta: { + /** + * Dagre's nodesep param - number of pixels that + * separate nodes horizontally in the layout. + * + * See https://github.com/cpettitt/dagre/wiki#configuring-the-layout + */ + nodeSep: 110, + /** + * Dagre's ranksep param - number of pixels + * between each rank in the layout. + * + * See https://github.com/cpettitt/dagre/wiki#configuring-the-layout + */ + rankSep: 25 + }, + /** Graph parameter for metanode. */ + series: { + /** + * Dagre's nodesep param - number of pixels that + * separate nodes horizontally in the layout. + * + * See https://github.com/cpettitt/dagre/wiki#configuring-the-layout + */ + nodeSep: 90, + /** + * Dagre's ranksep param - number of pixels + * between each rank in the layout. + * + * See https://github.com/cpettitt/dagre/wiki#configuring-the-layout + */ + rankSep: 25, + }, + /** + * Padding is used to correctly position the graph SVG inside of its parent + * element. The padding amounts are applied using an SVG transform of X and + * Y coordinates. + */ + padding: { + paddingTop: 40, + paddingLeft: 20 + } + }, + subscene: { + meta: { + paddingTop: 10, + paddingBottom: 10, + paddingLeft: 10, + paddingRight: 10, + /** + * Used to leave room for the label on top of the highest node in + * the core graph. + */ + labelHeight: 20, + /** X-space between each extracted node and the core graph. */ + extractXOffset: 50, + /** Y-space between each extracted node. */ + extractYOffset: 20 + }, + series: { + paddingTop: 10, + paddingBottom: 10, + paddingLeft: 10, + paddingRight: 10, + labelHeight: 10 + } + }, + nodeSize: { + /** Size of meta nodes. */ + meta: { + radius: 5, + width: 60, + /** A scale for the node's height based on number of nodes inside */ + height: d3.scale.linear().domain([1, 200]).range([15, 60]).clamp(true), + /** The radius of the circle denoting the expand button. */ + expandButtonRadius: 3 + }, + /** Size of op nodes. */ + op: { + width: 15, + height: 6, + radius: 3, // for making annotation touching ellipse + labelOffset: -8 + }, + /** Size of series nodes. */ + series: { + expanded: { + // For expanded series nodes, width and height will be + // computed to account for the subscene. + radius: 10, + labelOffset: 0, + }, + vertical: { + // When unexpanded, series whose underlying metagraphs contain + // one or more non-control edges will show as a vertical stack + // of ellipses. + width: 16, + height: 13, + labelOffset: -13, + }, + horizontal: { + // When unexpanded, series whose underlying metagraphs contain + // no non-control edges will show as a horizontal stack of + // ellipses. + width: 24, + height: 8, + radius: 10, // Forces annotations to center line. + labelOffset: -10, + }, + }, + /** Size of bridge nodes. */ + bridge: { + // NOTE: bridge nodes will normally be invisible, but they must + // take up some space so that the layout step leaves room for + // their edges. + width: 20, + height: 20, + radius: 2, + labelOffset: 0 + } + }, + shortcutSize: { + /** Size of shortcuts for op nodes */ + op: { + width: 10, + height: 4 + }, + /** Size of shortcuts for meta nodes */ + meta: { + width: 12, + height: 4, + radius: 1 + }, + /** Size of shortcuts for series nodes */ + series: { + width: 14, + height: 4, + } + }, + annotations: { + /** X-space between the shape and each annotation-node. */ + xOffset: 10, + /** Y-space between each annotation-node. */ + yOffset: 3, + /** X-space between each annotation-node and its label. */ + labelOffset: 2, + /** Estimate max width for annotation label */ + labelWidth: 35 + }, + constant: { + size: { + width: 4, + height: 4 + } + }, + series: { + /** Maximum number of repeated item for unexpanded series node. */ + maxStackCount: 3, + /** + * Positioning offset ratio for collapsed stack + * of parallel series (series without edges between its members). + */ + parallelStackOffsetRatio: 0.2, + /** + * Positioning offset ratio for collapsed stack + * of tower series (series with edges between its members). + */ + towerStackOffsetRatio: 0.5 + }, + minimap : { + /** The maximum width/height the minimap can have. */ + size: 150 + } +}; + +/** Calculate layout for a scene of a group node. */ +export function scene(renderNodeInfo: render.RenderGroupNodeInformation) + : void { + // Update layout, size, and annotations of its children nodes and edges. + if (renderNodeInfo.node.isGroupNode) { + layoutChildren(renderNodeInfo); + } + + // Update position of its children nodes and edges + if (renderNodeInfo.node.type === NodeType.META) { + layoutMetanode(renderNodeInfo); + } else if (renderNodeInfo.node.type === NodeType.SERIES) { + layoutSeriesNode(renderNodeInfo); + } +}; + +/** + * Update layout, size, and annotations of its children nodes and edges. + */ +function layoutChildren(renderNodeInfo: render.RenderGroupNodeInformation) + : void { + let children = renderNodeInfo.coreGraph.nodes().map(n => { + return renderNodeInfo.coreGraph.node(n); + }).concat(renderNodeInfo.isolatedInExtract, + renderNodeInfo.isolatedOutExtract); + + _.each(children, childNodeInfo => { + // Set size of each child + switch (childNodeInfo.node.type) { + case NodeType.OP: + _.extend(childNodeInfo, PARAMS.nodeSize.op); + break; + case NodeType.BRIDGE: + _.extend(childNodeInfo, PARAMS.nodeSize.bridge); + break; + case NodeType.META: + if (!childNodeInfo.expanded) { + // set fixed width and scalable height based on cardinality + _.extend(childNodeInfo, PARAMS.nodeSize.meta); + childNodeInfo.height = + PARAMS.nodeSize.meta.height(childNodeInfo.node.cardinality); + } else { + let childGroupNodeInfo = + <render.RenderGroupNodeInformation>childNodeInfo; + scene(childGroupNodeInfo); // Recursively layout its subscene. + } + break; + case NodeType.SERIES: + if (childNodeInfo.expanded) { + _.extend(childNodeInfo, PARAMS.nodeSize.series.expanded); + let childGroupNodeInfo = + <render.RenderGroupNodeInformation>childNodeInfo; + scene(childGroupNodeInfo); // Recursively layout its subscene. + } else { + let childGroupNodeInfo = + <render.RenderGroupNodeInformation>childNodeInfo; + let seriesParams = + childGroupNodeInfo.node.hasNonControlEdges ? + PARAMS.nodeSize.series.vertical : + PARAMS.nodeSize.series.horizontal; + _.extend(childNodeInfo, seriesParams); + } + break; + default: + throw Error("Unrecognized node type: " + childNodeInfo.node.type); + } + + // Layout each child's annotations + layoutAnnotation(childNodeInfo); + }); +} + +/** + * Calculate layout for a graph using dagre + * @param graph the graph to be laid out + * @param params layout parameters + * @return width and height of the core graph + */ +function dagreLayout(graph: graphlib.Graph<any, any>, params) + : {height: number, width: number} { + _.extend(graph.graph(), { + nodeSep: params.nodeSep, + rankSep: params.rankSep + }); + + let bridgeNodeNames = []; + let nonBridgeNodeNames = []; + + // Split out nodes into bridge and non-bridge nodes, and calculate the total + // width we should use for bridge nodes. + _.each(graph.nodes(), nodeName => { + let nodeInfo = graph.node(nodeName); + if (nodeInfo.node.type === NodeType.BRIDGE) { + bridgeNodeNames.push(nodeName); + } else { + nonBridgeNodeNames.push(nodeName); + } + }); + + // If there are no non-bridge nodes, then the graph has zero size. + if (!nonBridgeNodeNames.length) { + return { + width: 0, + height: 0, + }; + } + + dagre.layout(graph); + + let graphLabel = graph.graph(); + + // Calculate the true bounding box of the graph by iterating over nodes and + // edges rather than accepting dagre's word for it. In particular, we should + // ignore the extra-wide bridge nodes and bridge edges, and allow for + // annotation boxes and labels. + let minX = Infinity; + let minY = Infinity; + let maxX = -Infinity; + let maxY = -Infinity; + _.each(nonBridgeNodeNames, nodeName => { + let nodeInfo = graph.node(nodeName); + let w = 0.5 * nodeInfo.width; + let x1 = nodeInfo.x - w - nodeInfo.inboxWidth; + let x2 = nodeInfo.x + w + nodeInfo.outboxWidth; + minX = x1 < minX ? x1 : minX; + maxX = x2 > maxX ? x2 : maxX; + let labelLength = + nodeName.length - nodeName.lastIndexOf(NAMESPACE_DELIM); + // TODO(jimbo): Account for font width rather than using a magic number. + let charWidth = 3; // 3 pixels per character. + let lw = 0.5 * labelLength * charWidth; + let lx1 = nodeInfo.x - lw; + let lx2 = nodeInfo.x + lw; + minX = lx1 < minX ? lx1 : minX; + maxX = lx2 > maxX ? lx2 : maxX; + // TODO(jimbo): Account for the height of labels above op nodes here. + let h = 0.5 * nodeInfo.outerHeight; + let y1 = nodeInfo.y - h; + let y2 = nodeInfo.y + h; + minY = y1 < minY ? y1 : minY; + maxY = y2 > maxY ? y2 : maxY; + }); + _.each(graph.edges(), edgeObj => { + let renderMetaedgeInfo = graph.edge(edgeObj); + if (renderMetaedgeInfo.structural) { + return; // Skip structural edges from min/max calculations. + } + _.each(renderMetaedgeInfo.points, + (point: { x: number, y: number }) => { + minX = point.x < minX ? point.x : minX; + maxX = point.x > maxX ? point.x : maxX; + minY = point.y < minY ? point.y : minY; + maxY = point.y > maxY ? point.y : maxY; + }); + }); + + // Shift all nodes and edge points to account for the left-padding amount, + // and the invisble bridge nodes. + _.each(graph.nodes(), nodeName => { + let nodeInfo = graph.node(nodeName); + nodeInfo.x -= minX; + nodeInfo.y -= minY; + }); + _.each(graph.edges(), edgeObj => { + _.each(graph.edge(edgeObj).points, + (point: { x: number, y: number }) => { + point.x -= minX; + point.y -= minY; + }); + }); + + return { + width: maxX - minX, + height: maxY - minY, + }; +} + +/** Layout a metanode. */ +function layoutMetanode(renderNodeInfo): void { + // First, copy params specific to meta nodes onto this render info object. + let params = PARAMS.subscene.meta; + renderNodeInfo = _.extend(renderNodeInfo, params); + + // Invoke dagre.layout() on the core graph and record the bounding box + // dimensions. + _.extend(renderNodeInfo.coreBox, + dagreLayout(renderNodeInfo.coreGraph, PARAMS.graph.meta)); + + // Calculate the position of nodes in isolatedInExtract relative to the + // top-left corner of inExtractBox (the bounding box for all inExtract nodes) + // and calculate the size of the inExtractBox. + let hasInExtract = renderNodeInfo.isolatedInExtract.length > 0; + + renderNodeInfo.inExtractBox.width = hasInExtract ? + _(renderNodeInfo.isolatedInExtract).pluck("outerWidth").max() : 0; + + renderNodeInfo.inExtractBox.height = + _.reduce(renderNodeInfo.isolatedInExtract, (height, child: any, i) => { + let yOffset = i > 0 ? params.extractYOffset : 0; + // use outerWidth/Height here to avoid overlaps between extracts + child.x = renderNodeInfo.inExtractBox.width / 2; + child.y = height + yOffset + child.outerHeight / 2; + return height + yOffset + child.outerHeight; + }, 0); + + // Calculate the position of nodes in isolatedOutExtract relative to the + // top-left corner of outExtractBox (the bounding box for all outExtract + // nodes) and calculate the size of the outExtractBox. + let hasOutExtract = renderNodeInfo.isolatedOutExtract.length > 0; + renderNodeInfo.outExtractBox.width = hasOutExtract ? + _(renderNodeInfo.isolatedOutExtract).pluck("outerWidth").max() : 0; + + renderNodeInfo.outExtractBox.height = + _.reduce(renderNodeInfo.isolatedOutExtract, (height, child: any, i) => { + let yOffset = i > 0 ? params.extractYOffset : 0; + // use outerWidth/Height here to avoid overlaps between extracts + child.x = renderNodeInfo.outExtractBox.width / 2; + child.y = height + yOffset + child.outerHeight / 2; + return height + yOffset + child.outerHeight; + }, 0); + + // Determine the whole metanode's width (from left to right). + renderNodeInfo.width = + params.paddingLeft + renderNodeInfo.coreBox.width + params.paddingRight + + (hasInExtract ? + renderNodeInfo.inExtractBox.width + params.extractXOffset : 0) + + (hasOutExtract ? + params.extractXOffset + renderNodeInfo.outExtractBox.width : 0); + + // TODO(jimbo): Remove labelHeight and instead incorporate into box sizes. + // Determine the whole metanode's height (from top to bottom). + renderNodeInfo.height = + renderNodeInfo.labelHeight + + params.paddingTop + + Math.max( + renderNodeInfo.inExtractBox.height, + renderNodeInfo.coreBox.height, + renderNodeInfo.outExtractBox.height + ) + + params.paddingBottom; +} + +/** + * Calculate layout for series node's core graph. Only called for an expanded + * series. + */ +function layoutSeriesNode(node: render.RenderGroupNodeInformation): void { + let graph = node.coreGraph; + + let params = PARAMS.subscene.series; + _.extend(node, params); + + // Layout the core. + _.extend(node.coreBox, + dagreLayout(node.coreGraph, PARAMS.graph.series)); + + _.each(graph.nodes(), nodeName => { + graph.node(nodeName).excluded = false; + }); + + // Series do not have in/outExtractBox so no need to include them here. + node.width = node.coreBox.width + params.paddingLeft + params.paddingRight; + node.height = node.coreBox.height + params.paddingTop + params.paddingBottom; +} + +/** + * Calculate layout for annotations of a given node. + * This will modify positions of the the given node and its annotations. + * + * @see tf.graph.render.Node and tf.graph.render.Annotation + * for description of each property of each render node. + * + */ + function layoutAnnotation(renderNodeInfo: render.RenderNodeInformation): void { + // If the render node is an expanded metanode, then its annotations will not + // be visible and we should skip the annotation calculations. + if (renderNodeInfo.expanded) { + _.extend(renderNodeInfo, { + inboxWidth: 0, + inboxHeight: 0, + outboxWidth: 0, + outboxHeight: 0, + outerWidth: renderNodeInfo.width, + outerHeight: renderNodeInfo.height + }); + return; + } + + let inAnnotations = renderNodeInfo.inAnnotations.list; + let outAnnotations = renderNodeInfo.outAnnotations.list; + + // Calculate size for in-annotations + _.each(inAnnotations, a => sizeAnnotation(a)); + + // Calculate size for out-annotations + _.each(outAnnotations, a => sizeAnnotation(a)); + + let params = PARAMS.annotations; + renderNodeInfo.inboxWidth = + inAnnotations.length > 0 ? + (<any>_(inAnnotations).pluck("width").max()) + + params.xOffset + params.labelWidth + params.labelOffset : + 0; + + renderNodeInfo.outboxWidth = + outAnnotations.length > 0 ? + (<any>_(outAnnotations).pluck("width").max()) + + params.xOffset + params.labelWidth + params.labelOffset : + 0; + + // Calculate annotation node position (a.dx, a.dy) + // and total height for in-annotations + // After this chunk of code: + // inboxHeight = sum of annotation heights+ (annotation.length - 1 * yOffset) + let inboxHeight = _.reduce(inAnnotations, + (height, a: any, i) => { + let yOffset = i > 0 ? params.yOffset : 0; + a.dx = -(renderNodeInfo.width + a.width) / 2 - params.xOffset; + a.dy = height + yOffset + a.height / 2; + return height + yOffset + a.height; + }, 0); + + _.each(inAnnotations, (a: any) => { + a.dy -= inboxHeight / 2; + + a.labelOffset = params.labelOffset; + }); + + // Calculate annotation node position position (a.dx, a.dy) + // and total height for out-annotations + // After this chunk of code: + // outboxHeight = sum of annotation heights + + // (annotation.length - 1 * yOffset) + let outboxHeight = _.reduce(outAnnotations, + (height, a: any, i) => { + let yOffset = i > 0 ? params.yOffset : 0; + a.dx = (renderNodeInfo.width + a.width) / 2 + params.xOffset; + a.dy = height + yOffset + a.height / 2; + return height + yOffset + a.height; + }, 0); + + _.each(outAnnotations, (a: any) => { + // adjust by (half of ) the total height + // so dy is relative to the host node's center. + a.dy -= outboxHeight / 2; + + a.labelOffset = params.labelOffset; + }); + + // Creating scales for touch point between the in-annotation edges + // and their hosts. + + let inTouchHeight = + Math.min(renderNodeInfo.height / 2 - renderNodeInfo.radius, + inboxHeight / 2); + inTouchHeight = inTouchHeight < 0 ? 0 : inTouchHeight; + + let inY = d3.scale.linear() + .domain([0, inAnnotations.length - 1]) + .range([-inTouchHeight, inTouchHeight]); + + // Calculate annotation edge position + _.each(inAnnotations, (a: any, i) => { + a.points = [ + // The annotation node end + { + dx: a.dx + a.width / 2, + dy: a.dy + }, + + // The host node end + { + dx: - renderNodeInfo.width / 2, + // only use scale if there are more than one, + // otherwise center it vertically + dy: inAnnotations.length > 1 ? inY(i) : 0 + } + ]; + }); + + // Creating scales for touch point between the out-annotation edges + // and their hosts. + let outTouchHeight = + Math.min(renderNodeInfo.height / 2 - renderNodeInfo.radius, + outboxHeight / 2); + outTouchHeight = outTouchHeight < 0 ? 0 : outTouchHeight; + let outY = d3.scale.linear() + .domain([0, outAnnotations.length - 1]) + .range([-outTouchHeight, outTouchHeight]); + + _.each(outAnnotations, (a: any, i) => { + // Add point from the border of the annotation node + a.points = [ + // The host node end + { + dx: renderNodeInfo.width / 2, + // only use scale if there are more than one, + // otherwise center it vertically + dy: outAnnotations.length > 1 ? outY(i) : 0 + }, + // The annotation node end + { + dx: a.dx - a.width / 2, + dy: a.dy + } + ]; + }); + + renderNodeInfo.outerWidth = renderNodeInfo.width + renderNodeInfo.inboxWidth + + renderNodeInfo.outboxWidth; + renderNodeInfo.outerHeight = + Math.max(renderNodeInfo.height, inboxHeight, outboxHeight); +} + +/** + * Set size of an annotation node. + */ +function sizeAnnotation(a: render.Annotation): void { + switch (a.annotationType) { + case render.AnnotationType.CONSTANT: + _.extend(a, PARAMS.constant.size); + break; + case render.AnnotationType.SHORTCUT: + if (a.node.type === NodeType.OP) { + _.extend(a, PARAMS.shortcutSize.op); + } else if (a.node.type === NodeType.META) { + _.extend(a, PARAMS.shortcutSize.meta); + } else if (a.node.type === NodeType.SERIES) { + _.extend(a, PARAMS.shortcutSize.series); + } else { + throw Error("Invalid node type: " + a.node.type); + } + break; + case render.AnnotationType.SUMMARY: + _.extend(a, PARAMS.constant.size); + break; + } +} + +} // close module diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/parser.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/parser.ts new file mode 100644 index 0000000000..b4864738a9 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/parser.ts @@ -0,0 +1,189 @@ +/// <reference path="../../../typings/tsd.d.ts" /> +/// <reference path="common.ts" /> +module tf.graph.parser { + +/** + * Parses a native js value, which can be either a string, boolean or number. + * + * @param value The value to be parsed. + */ +function parseValue(value: string): string|number|boolean { + if (value === "true") { + return true; + } + if (value === "false") { + return false; + } + let firstChar = value[0]; + if (firstChar === "\"") { + return value.substring(1, value.length - 1); + } + let num = parseFloat(value); + return isNaN(num) ? value : num; +} + +/** + * Fetches a text file and returns a promise of the result. + */ +export function readPbTxt(filepath: string): Promise<string> { + return new Promise<string>(function(resolve, reject) { + d3.text(filepath, function(error, text) { + if (error) { + reject(error); + return; + } + resolve(text); + }); + }); +} + +/** + * Fetches and parses a json file and returns a promise of the result. + */ +export function readJson(filepath: string): Promise<Object> { + return new Promise<Object>(function(resolve, reject) { + d3.json(filepath, function(error, text) { + if (error) { + reject(error); + return; + } + resolve(text); + }); + }); +} + +/** + * Reads the graph and stats file (if available), parses them and returns a + * promise of the result. + */ +export function readAndParseData(dataset: {path: string, statsPath: string}, + pbTxtContent: string, tracker: ProgressTracker): + Promise<{ nodes: TFNode[], statsJson: Object }|void> { + let graphPbTxt; + let statsJson; + return runAsyncTask("Reading graph.pbtxt", 20, () => { + return pbTxtContent || readPbTxt(dataset.path); + }, tracker) + .then(function(text) { + graphPbTxt = text; + return runAsyncTask("Reading stats.pbtxt", 20, () => { + return (dataset != null && dataset.statsPath != null) ? + readJson(dataset.statsPath) : null; + }, tracker); + }) + .then(function(json) { + statsJson = json; + return runAsyncTask("Parsing graph.pbtxt", 60, () => { + return parsePbtxt(graphPbTxt); + }, tracker); + }) + .then(function(nodes) { + return { + nodes: nodes, + statsJson: statsJson + }; + }) + .catch(function(reason) { + throw new Error("Failure parsing graph definition"); + }); +} + +/** + * Parses a proto txt file into a javascript object. + * + * @param input The string contents of the proto txt file. + * @return The parsed object. + */ +export function parsePbtxt(input: string): TFNode[] { + let output: { [name: string]: any; } = { node: [] }; + let stack = []; + let path: string[] = []; + let current: { [name: string]: any; } = output; + + function splitNameAndValueInAttribute(line: string) { + let colonIndex = line.indexOf(":"); + let name = line.substring(0, colonIndex).trim(); + let value = parseValue(line.substring(colonIndex + 2).trim()); + return { + name: name, + value: value + }; + } + + /** + * Since proto-txt doesn't explicitly say whether an attribute is repeated + * (an array) or not, we keep a hard-coded list of attributes that are known + * to be repeated. This list is used in parsing time to convert repeated + * attributes into arrays even when the attribute only shows up once in the + * object. + */ + let ARRAY_ATTRIBUTES: {[attrPath: string] : boolean} = { + "node": true, + "node.input": true, + "node.attr": true, + "node.attr.value.list.type": true, + "node.attr.value.shape.dim": true, + "node.attr.value.tensor.string_val": true, + "node.attr.value.tensor.tensor_shape.dim": true + }; + + /** + * Adds a value, given the attribute name and the host object. If the + * attribute already exists, but is not an array, it will convert it to an + * array of values. + * + * @param obj The host object that holds the attribute. + * @param name The attribute name (key). + * @param value The attribute value. + * @param path A path that identifies the attribute. Used to check if + * an attribute is an array or not. + */ + function addAttribute(obj: Object, name: string, + value: Object|string|number|boolean, path: string[]): void { + // We treat "node" specially since it is done so often. + let existingValue = obj[name]; + if (existingValue == null) { + obj[name] = path.join(".") in ARRAY_ATTRIBUTES ? [value] : value; + } else if (Array.isArray(existingValue)) { + existingValue.push(value); + } else { + obj[name] = [existingValue, value]; + } + } + + // Run through the file a line at a time. + let startPos = 0; + while (startPos < input.length) { + let endPos = input.indexOf("\n", startPos); + if (endPos === -1) { + endPos = input.length; + } + let line = input.substring(startPos, endPos); + startPos = endPos + 1; + if (!line) { + continue; + } + switch (line[line.length - 1]) { + case "{": // create new object + let name = line.substring(0, line.length - 2).trim(); + let newValue: { [name: string]: any; } = {}; + stack.push(current); + path.push(name); + addAttribute(current, name, newValue, path); + current = newValue; + break; + case "}": + current = stack.pop(); + path.pop(); + break; + default: + let x = splitNameAndValueInAttribute(line); + addAttribute(current, x.name, x.value, path.concat(x.name)); + break; + } + } + + return output["node"]; +} + +} // Close module tf.graph.parser. diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/render.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/render.ts new file mode 100644 index 0000000000..363f006fd5 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/render.ts @@ -0,0 +1,1360 @@ +/// <reference path="graph.ts" /> +/// <reference path="hierarchy.ts" /> + +/** + * 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<string, string>; + private memoryUsageScale: d3.scale.Linear<string, string>; + private computeTimeScale: d3.scale.Linear<string, string>; + // 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<string>() + .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<string, string>() + .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<string, string>() + .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 = <RenderGroupNodeInformation> 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(<GroupNode>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((<OpNode>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((<OpNode>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 = (<OpNode>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((<GroupNode> 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 = + <RenderGroupNodeInformation> 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 <RenderMetaedgeInformation> + 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 = <GroupNode>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 = <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<RenderMetaedgeInformation>; + + 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<RenderNodeInformation, any>, + 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(<RenderGroupNodeInformation>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<RenderNodeInformation, RenderMetaedgeInformation>; + /** 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<RenderNodeInformation, RenderMetaedgeInformation>( + 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<RenderNodeInformation, {}>, + 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 ((<OpNode>node).op === types[i]) { return true; } + } + } else if (node.type === NodeType.META) { + let rootOpNode = (<Metanode>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 + * <tf-graph-params>'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 diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/scene/annotation.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/annotation.ts new file mode 100644 index 0000000000..82609e8652 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/annotation.ts @@ -0,0 +1,223 @@ +/// <reference path="../graph.ts" /> +/// <reference path="../render.ts" /> +/// <reference path="scene.ts" /> +/// <reference path="edge.ts" /> + +module tf.graph.scene.annotation { + +/** + * Populate a given annotation container group + * + * <g class="{in|out}-annotations"></g> + * + * with annotation group of the following structure: + * + * <g class="annotation"> + * <g class="annotation-node"> + * <!-- + * Content here determined by Scene.node.buildGroup. + * --> + * </g> + * </g> + * + * @param container selection of the container. + * @param annotationData node.{in|out}Annotations + * @param d node to build group for. + * @param sceneBehavior polymer scene element. + * @return selection of appended objects + */ +export function buildGroup(container, annotationData: render.AnnotationList, + d: render.RenderNodeInformation, sceneBehavior) { + // Select all children and join with data. + let annotationGroups = container.selectAll(function() { + // using d3's selector function + // See https://github.com/mbostock/d3/releases/tag/v2.0.0 + // (It's not listed in the d3 wiki.) + return this.childNodes; + }) + .data(annotationData.list, d => { return d.node.name; }); + + annotationGroups.enter() + .append("g") + .attr("data-name", a => { return a.node.name; }) + .each(function(a) { + let aGroup = d3.select(this); + + // Add annotation to the index in the scene + sceneBehavior.addAnnotationGroup(a, d, aGroup); + // Append annotation edge + let edgeType = Class.Annotation.EDGE; + let metaedge = a.renderMetaedgeInfo && a.renderMetaedgeInfo.metaedge; + if (metaedge && !metaedge.numRegularEdges) { + edgeType += " " + Class.Annotation.CONTROL_EDGE; + } + // If any edges are reference edges, add the reference edge class. + if (metaedge && metaedge.numRefEdges) { + edgeType += " " + Class.Edge.REF_LINE; + } + edge.appendEdge(aGroup, a, sceneBehavior, edgeType); + + if (a.annotationType !== tf.graph.render.AnnotationType.ELLIPSIS) { + addAnnotationLabelFromNode(aGroup, a); + buildShape(aGroup, a, sceneBehavior); + } else { + addAnnotationLabel(aGroup, a.node.name, a, Class.Annotation.ELLIPSIS); + } + }); + + annotationGroups + .attr("class", a => { + return Class.Annotation.GROUP + " " + + annotationToClassName(a.annotationType) + + " " + node.nodeClass(a); + }) + .each(function(a) { + let aGroup = d3.select(this); + update(aGroup, d, a, sceneBehavior); + if (a.annotationType !== tf.graph.render.AnnotationType.ELLIPSIS) { + addInteraction(aGroup, d, sceneBehavior); + } + }); + + annotationGroups.exit() + .each(function(a) { + let aGroup = d3.select(this); + + // Remove annotation from the index in the scene + sceneBehavior.removeAnnotationGroup(a, d, aGroup); + }) + .remove(); + return annotationGroups; +}; + +/** + * Maps an annotation enum to a class name used in css rules. + */ +function annotationToClassName(annotationType: render.AnnotationType) { + return (tf.graph.render.AnnotationType[annotationType] || "") + .toLowerCase() || null; +} + +function buildShape(aGroup, a: render.Annotation, sceneBehavior) { + if (a.annotationType === tf.graph.render.AnnotationType.SUMMARY) { + let image = scene.selectOrCreateChild(aGroup, "image"); + image.attr({ + "xlink:href": sceneBehavior.resolveUrl("../../lib/svg/summary-icon.svg"), + "height": "12px", + "width": "12px", + "cursor": "pointer" + }); + } else { + let shape = node.buildShape(aGroup, a, Class.Annotation.NODE); + // add title tag to get native tooltips + scene.selectOrCreateChild(shape, "title").text(a.node.name); + } +} + +function addAnnotationLabelFromNode(aGroup, a: render.Annotation) { + let namePath = a.node.name.split("/"); + let text = namePath[namePath.length - 1]; + let shortenedText = text.length > 8 ? text.substring(0, 8) + "..." : text; + return addAnnotationLabel(aGroup, shortenedText, a, null, text); +} + +function addAnnotationLabel(aGroup, label, a, additionalClassNames, + fullLabel?) { + let classNames = Class.Annotation.LABEL; + if (additionalClassNames) { + classNames += " " + additionalClassNames; + } + let titleText = fullLabel ? fullLabel : label; + return aGroup.append("text") + .attr("class", classNames) + .attr("dy", ".35em") + .attr("text-anchor", a.isIn ? "end" : "start") + .text(label) + .append("title").text(titleText); +} + +function addInteraction(selection, d: render.RenderNodeInformation, + sceneBehavior) { + selection + .on("mouseover", a => { + sceneBehavior.fire("annotation-highlight", { + name: a.node.name, + hostName: d.node.name + }); + }) + .on("mouseout", a => { + sceneBehavior.fire("annotation-unhighlight", { + name: a.node.name, + hostName: d.node.name + }); + }) + .on("click", a => { + // Stop this event"s propagation so that it isn't also considered a + // graph-select. + (<Event>d3.event).stopPropagation(); + sceneBehavior.fire("annotation-select", { + name: a.node.name, + hostName: d.node.name + }); + }); +}; + +/** + * Adjust annotation's position. + * + * @param aGroup selection of a "g.annotation" element. + * @param d Host node data. + * @param a annotation node data. + * @param scene Polymer scene element. + */ +function update(aGroup, d: render.RenderNodeInformation, a: render.Annotation, + sceneBehavior) { + // Annotations that point to embedded nodes (constants,summary) + // don't have a render information attached so we don't stylize these. + // Also we don't stylize ellipsis annotations (the string "... and X more"). + if (a.renderNodeInfo && + a.annotationType !== tf.graph.render.AnnotationType.ELLIPSIS) { + node.stylize(aGroup, a.renderNodeInfo, sceneBehavior, + Class.Annotation.NODE); + } + + if (a.annotationType === tf.graph.render.AnnotationType.SUMMARY) { + // Update the width of the annotation to give space for the image. + a.width += 10; + } + + // label position + aGroup.select("text." + Class.Annotation.LABEL).transition().attr({ + x: d.x + a.dx + (a.isIn ? -1 : 1) * (a.width / 2 + a.labelOffset), + y: d.y + a.dy + }); + + // Some annotations (such as summary) are represented using a 12x12 image tag. + // Purposely ommited units (e.g. pixels) since the images are vector graphics. + // If there is an image, we adjust the location of the image to be vertically + // centered with the node and horizontally centered between the arrow and the + // text label. + aGroup.select("image").transition().attr({ + x: d.x + a.dx - 3, + y: d.y + a.dy - 6 + }); + + // Node position (only one of the shape selection will be non-empty.) + scene.positionEllipse(aGroup.select("." + Class.Annotation.NODE + " ellipse"), + d.x + a.dx, d.y + a.dy, a.width, a.height); + scene.positionRect(aGroup.select("." + Class.Annotation.NODE + " rect"), + d.x + a.dx, d.y + a.dy, a.width, a.height); + scene.positionRect(aGroup.select("." + Class.Annotation.NODE + " use"), + d.x + a.dx, d.y + a.dy, a.width, a.height); + + // Edge position + aGroup.select("path." + Class.Annotation.EDGE).transition().attr("d", a => { + // map relative position to absolute position + let points = a.points.map(p => { + return {x: p.dx + d.x, y: p.dy + d.y}; + }); + return edge.interpolate(points); + }); +}; + +} // close module diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/scene/edge.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/edge.ts new file mode 100644 index 0000000000..e11ec97f80 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/edge.ts @@ -0,0 +1,177 @@ +/// <reference path="../graph.ts" /> +/// <reference path="../render.ts" /> +/// <reference path="scene.ts" /> + +module tf.graph.scene.edge { + +let Scene = tf.graph.scene; // Aliased + +export function getEdgeKey(edgeObj) { + return edgeObj.v + tf.graph.EDGE_KEY_DELIM + edgeObj.w; +} + +/** + * Select or Create a "g.edges" group to a given sceneGroup + * and builds a number of "g.edge" groups inside the group. + * + * Structure Pattern: + * + * <g class="edges"> + * <g class="edge"> + * <path class="edgeline"/> + * </g> + * ... + * </g> + * + * + * @param sceneGroup container + * @param graph + * @param sceneBehavior Parent scene module. + * @return selection of the created nodeGroups + */ +export function buildGroup(sceneGroup, + graph: graphlib.Graph<tf.graph.render.RenderNodeInformation, + tf.graph.render.RenderMetaedgeInformation>, sceneBehavior) { + let edgeData = _.reduce(graph.edges(), (edges, edgeObj) => { + let edgeLabel = graph.edge(edgeObj); + edges.push({ + v: edgeObj.v, + w: edgeObj.w, + label: edgeLabel + }); + return edges; + }, []); + + let container = scene.selectOrCreateChild(sceneGroup, "g", + Class.Edge.CONTAINER); + let containerNode = container.node(); + + // Select all children and join with data. + // (Note that all children of g.edges are g.edge) + let edgeGroups = container.selectAll(function() { + // using d3's selector function + // See https://github.com/mbostock/d3/releases/tag/v2.0.0 + // (It's not listed in the d3 wiki.) + return this.childNodes; + }) + .data(edgeData, getEdgeKey); + + // Make edges a group to support rendering multiple lines for metaedge + edgeGroups.enter() + .append("g") + .attr("class", Class.Edge.GROUP) + .attr("data-edge", getEdgeKey) + .each(function(d) { + let edgeGroup = d3.select(this); + d.label.edgeGroup = edgeGroup; + // index node group for quick highlighting + sceneBehavior._edgeGroupIndex[getEdgeKey(d)] = edgeGroup; + + // If any edges are reference edges, add the reference edge class. + let extraEdgeClass = d.label.metaedge && d.label.metaedge.numRefEdges + ? Class.Edge.REF_LINE + " " + Class.Edge.LINE + : undefined; + // Add line during enter because we're assuming that type of line + // normally does not change. + appendEdge(edgeGroup, d, scene, extraEdgeClass); + }); + + edgeGroups.each(position); + edgeGroups.each(function(d) { + stylize(d3.select(this), d, sceneBehavior); + }); + + edgeGroups.exit() + .each(d => { + delete sceneBehavior._edgeGroupIndex[getEdgeKey(d)]; + }) + .remove(); + return edgeGroups; +}; + +/** + * For a given d3 selection and data object, create a path to represent the + * edge described in d.label. + * + * If d.label is defined, it will be a RenderMetaedgeInformation instance. It + * will sometimes be undefined, for example for some Annotation edges for which + * there is no underlying Metaedge in the hierarchical graph. + */ +export function appendEdge(edgeGroup, d, sceneBehavior, edgeClass?) { + edgeClass = edgeClass || Class.Edge.LINE; // set default type + + if (d.label && d.label.structural) { + edgeClass += " " + Class.Edge.STRUCTURAL; + } + + edgeGroup.append("path") + .attr("class", edgeClass); +}; + +/** + * Returns a tween interpolator for the endpoint of an edge path. + */ +function getEdgePathInterpolator(d, i, a) { + let renderMetaedgeInfo = d.label; + let adjoiningMetaedge = renderMetaedgeInfo.adjoiningMetaedge; + if (!adjoiningMetaedge) { + return d3.interpolate(a, interpolate(renderMetaedgeInfo.points)); + } + + let renderPath = this; + + // Get the adjoining path that matches the adjoining metaedge. + let adjoiningPath = + <SVGPathElement>((<HTMLElement>adjoiningMetaedge.edgeGroup.node()) + .firstChild); + + // Find the desired SVGPoint along the adjoining path, then convert those + // coordinates into the space of the renderPath using its Current + // Transformation Matrix (CTM). + let inbound = renderMetaedgeInfo.metaedge.inbound; + + return function(t) { + let adjoiningPoint = adjoiningPath + .getPointAtLength(inbound ? adjoiningPath.getTotalLength() : 0) + .matrixTransform(adjoiningPath.getCTM()) + .matrixTransform(renderPath.getCTM().inverse()); + + // Update the relevant point in the renderMetaedgeInfo's points list, then + // re-interpolate the path. + let points = renderMetaedgeInfo.points; + let index = inbound ? 0 : points.length - 1; + points[index].x = adjoiningPoint.x; + points[index].y = adjoiningPoint.y; + let dPath = interpolate(points); + return dPath; + }; +} + +export let interpolate = d3.svg.line() + .interpolate("basis") + .x((d: any) => { return d.x; }) + .y((d: any) => { return d.y; }); + +function position(d) { + d3.select(this).select("path." + Class.Edge.LINE) + .each(function(d) { + let path = d3.select(this); + path.transition().attrTween("d", getEdgePathInterpolator); + }); +}; + +/** + * For a given d3 selection and data object, mark the edge as a control + * dependency if it contains only control edges. + * + * d's label property will be a RenderMetaedgeInformation object. + */ +function stylize(edgeGroup, d, stylize) { + let a; + let metaedge = d.label.metaedge; + edgeGroup + .select("path." + Class.Edge.LINE) + .classed("control-dep", metaedge && !metaedge.numRegularEdges); +}; + +} // close module diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/scene/minimap.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/minimap.ts new file mode 100644 index 0000000000..1a34132765 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/minimap.ts @@ -0,0 +1,269 @@ +/// <reference path="../../../../typings/tsd.d.ts" /> +/// <reference path="../common.ts" /> + +module tf.scene { + +/** Show minimap when the viewpoint area is less than X% of the whole area. */ +const FRAC_VIEWPOINT_AREA: number = 0.8; + +export class Minimap { + /** The minimap container. */ + private minimap: HTMLElement; + /** The canvas used for drawing the mini version of the svg. */ + private canvas: HTMLCanvasElement; + /** A buffer canvas used for temporary drawing to avoid flickering. */ + private canvasBuffer: HTMLCanvasElement; + + /** The minimap svg used for holding the viewpoint rectangle. */ + private minimapSvg: SVGSVGElement; + /** The rectangle showing the current viewpoint. */ + private viewpoint: SVGRectElement; + /** + * The scale factor for the minimap. The factor is determined automatically + * so that the minimap doesn't violate the maximum width/height specified + * in the constructor. The minimap maintains the same aspect ratio as the + * original svg. + */ + private scaleMinimap: number; + /** The main svg element. */ + private svg: SVGSVGElement; + /** The svg group used for panning and zooming the main svg. */ + private zoomG: SVGGElement; + /** The zoom behavior of the main svg. */ + private mainZoom: d3.behavior.Zoom<any>; + /** The maximum width and height for the minimap. */ + private maxWandH: number; + /** The last translation vector used in the main svg. */ + private translate: [number, number]; + /** The last scaling factor used in the main svg. */ + private scaleMain: number; + /** The coordinates of the viewpoint rectangle. */ + private viewpointCoord: {x: number, y: number}; + /** The current size of the minimap */ + private minimapSize: {width: number, height: number}; + /** Padding (px) due to the main labels of the graph. */ + private labelPadding: number; + /** + * Constructs a new minimap. + * + * @param svg The main svg element. + * @param zoomG The svg group used for panning and zooming the main svg. + * @param mainZoom The main zoom behavior. + * @param minimap The minimap container. + * @param maxWandH The maximum width/height for the minimap. + * @param labelPadding Padding in pixels due to the main graph labels. + */ + constructor(svg: SVGSVGElement, zoomG: SVGGElement, + mainZoom: d3.behavior.Zoom<any>, minimap: HTMLElement, + maxWandH: number, labelPadding: number) { + this.svg = svg; + this.labelPadding = labelPadding; + this.zoomG = zoomG; + this.mainZoom = mainZoom; + this.maxWandH = maxWandH; + let $minimap = d3.select(minimap); + // The minimap will have 2 main components: the canvas showing the content + // and an svg showing a rectangle of the currently zoomed/panned viewpoint. + let $minimapSvg = $minimap.select("svg"); + + // Make the viewpoint rectangle draggable. + let $viewpoint = $minimapSvg.select("rect"); + let dragmove = (d) => { + this.viewpointCoord.x = (<DragEvent>d3.event).x; + this.viewpointCoord.y = (<DragEvent>d3.event).y; + this.updateViewpoint(); + }; + this.viewpointCoord = {x: 0, y: 0}; + let drag = d3.behavior.drag().origin(Object).on("drag", dragmove); + $viewpoint.datum(this.viewpointCoord).call(drag); + + // Make the minimap clickable. + $minimapSvg.on("click", () => { + if ((<Event>d3.event).defaultPrevented) { + // This click was part of a drag event, so suppress it. + return; + } + // Update the coordinates of the viewpoint. + let width = Number($viewpoint.attr("width")); + let height = Number($viewpoint.attr("height")); + let clickCoords = d3.mouse($minimapSvg.node()); + this.viewpointCoord.x = clickCoords[0] - width / 2; + this.viewpointCoord.y = clickCoords[1] - height / 2; + this.updateViewpoint(); + }); + this.viewpoint = <SVGRectElement> $viewpoint.node(); + this.minimapSvg = <SVGSVGElement> $minimapSvg.node(); + this.minimap = minimap; + this.canvas = <HTMLCanvasElement> $minimap.select("canvas.first").node(); + this.canvasBuffer = + <HTMLCanvasElement> $minimap.select("canvas.second").node(); + } + + /** + * Updates the position and the size of the viewpoint rectangle. + * It also notifies the main svg about the new panned position. + */ + private updateViewpoint(): void { + // Update the coordinates of the viewpoint rectangle. + d3.select(this.viewpoint) + .attr("x", this.viewpointCoord.x) + .attr("y", this.viewpointCoord.y); + // Update the translation vector of the main svg to reflect the + // new viewpoint. + let mainX = - this.viewpointCoord.x * this.scaleMain / this.scaleMinimap; + let mainY = - this.viewpointCoord.y * this.scaleMain / this.scaleMinimap; + let zoomEvent = this.mainZoom.translate([mainX, mainY]).event; + d3.select(this.zoomG).call(zoomEvent); + } + + /** + * Redraws the minimap. Should be called whenever the main svg + * was updated (e.g. when a node was expanded). + */ + update(): void { + let $svg = d3.select(this.svg); + // Read all the style rules in the document and embed them into the svg. + // The svg needs to be self contained, i.e. all the style rules need to be + // embedded so the canvas output matches the origin. + let stylesText = ""; + for (let k = 0; k < document.styleSheets.length; k++) { + try { + let cssRules = (<any>document.styleSheets[k]).cssRules || + (<any>document.styleSheets[k]).rules; + if (cssRules == null) { + continue; + } + for (let i = 0; i < cssRules.length; i++) { + stylesText += cssRules[i].cssText + "\n"; + } + } catch (e) { + if (e.name !== "SecurityError") { + throw e; + } + } + } + + // Temporarily add the css rules to the main svg. + let svgStyle = $svg.append("style"); + svgStyle.text(stylesText); + + // Temporarily remove the zoom/pan transform from the main svg since we + // want the minimap to show a zoomed-out and centered view. + let $zoomG = d3.select(this.zoomG); + let zoomTransform = $zoomG.attr("transform"); + $zoomG.attr("transform", null); + + // Get the size of the entire scene. + let sceneSize = this.zoomG.getBBox(); + // Since we add padding, account for that here. + sceneSize.height += this.labelPadding; + + // Temporarily assign an explicit width/height to the main svg, since + // it doesn't have one (uses flex-box), but we need it for the canvas + // to work. + $svg.attr({ + width: sceneSize.width, + height: sceneSize.height, + }); + + // Since the content inside the svg changed (e.g. a node was expanded), + // the aspect ratio have also changed. Thus, we need to update the scale + // factor of the minimap. The scale factor is determined such that both + // the width and height of the minimap are <= maximum specified w/h. + this.scaleMinimap = + this.maxWandH / Math.max(sceneSize.width, sceneSize.height); + + this.minimapSize = { + width: sceneSize.width * this.scaleMinimap, + height: sceneSize.height * this.scaleMinimap + }; + + // Update the size of the minimap's svg, the buffer canvas and the + // viewpoint rect. + d3.select(this.minimapSvg).attr(<any>this.minimapSize); + d3.select(this.canvasBuffer).attr(<any>this.minimapSize); + if (this.translate != null && this.zoom != null) { + // Update the viewpoint rectangle shape since the aspect ratio of the + // map has changed. + requestAnimationFrame(() => this.zoom()); + } + + // Serialize the main svg to a string which will be used as the rendering + // content for the canvas. + let svgXml = (new XMLSerializer()).serializeToString(this.svg); + + // Now that the svg is serialized for rendering, remove the temporarily + // assigned styles, explicit width and height and bring back the pan/zoom + // transform. + svgStyle.remove(); + $svg.attr({ + width: null, + height: null + }); + $zoomG.attr("transform", zoomTransform); + let image = new Image(); + image.onload = () => { + // Draw the svg content onto the buffer canvas. + let context = this.canvasBuffer.getContext("2d"); + context.clearRect(0, 0, this.canvasBuffer.width, + this.canvasBuffer.height); + context.drawImage(image, 0, 0, + this.minimapSize.width, this.minimapSize.height); + requestAnimationFrame(() => { + // Hide the old canvas and show the new buffer canvas. + d3.select(this.canvasBuffer).style("display", null); + d3.select(this.canvas).style("display", "none"); + // Swap the two canvases. + [this.canvas, this.canvasBuffer] = [this.canvasBuffer, this.canvas]; + }); + }; + image.src = "data:image/svg+xml;base64," + btoa(svgXml); + } + + /** + * Handles changes in zooming/panning. Should be called from the main svg + * to notify that a zoom/pan was performed and this minimap will update it's + * viewpoint rectangle. + * + * @param translate The translate vector, or none to use the last used one. + * @param scale The scaling factor, or none to use the last used one. + */ + zoom(translate?: [number, number], scale?: number): void { + // Update the new translate and scale params, only if specified. + this.translate = translate || this.translate; + this.scaleMain = scale || this.scaleMain; + // Update the location of the viewpoint rectangle. + let svgRect = this.svg.getBoundingClientRect(); + let $viewpoint = d3.select(this.viewpoint); + this.viewpointCoord.x = -this.translate[0] * this.scaleMinimap / + this.scaleMain; + this.viewpointCoord.y = -this.translate[1] * this.scaleMinimap / + this.scaleMain; + let viewpointWidth = svgRect.width * this.scaleMinimap / this.scaleMain; + let viewpointHeight = svgRect.height * this.scaleMinimap / this.scaleMain; + $viewpoint.attr({ + x: this.viewpointCoord.x, + y: this.viewpointCoord.y, + width: viewpointWidth, + height: viewpointHeight + }); + // Show/hide the minimap depending on the viewpoint area as fraction of the + // whole minimap. + let mapWidth = this.minimapSize.width; + let mapHeight = this.minimapSize.height; + let x = this.viewpointCoord.x; + let y = this.viewpointCoord.y; + let w = Math.min(Math.max(0, x + viewpointWidth), mapWidth) - + Math.min(Math.max(0, x), mapWidth); + let h = Math.min(Math.max(0, y + viewpointHeight), mapHeight) - + Math.min(Math.max(0, y), mapHeight); + let fracIntersect = (w * h) / (mapWidth * mapHeight); + if (fracIntersect < FRAC_VIEWPOINT_AREA) { + this.minimap.classList.remove("hidden"); + } else { + this.minimap.classList.add("hidden"); + } + } +} + +} // close module tf.scene diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/scene/node.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/node.ts new file mode 100644 index 0000000000..8c74b37e07 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/node.ts @@ -0,0 +1,525 @@ +/// <reference path="../graph.ts" /> +/// <reference path="scene.ts" /> +/// <reference path="annotation.ts" /> + +module tf.graph.scene.node { + +/** + * Select or Create a "g.nodes" group to a given sceneGroup + * and builds a number of "g.node" groups inside the group. + * + * Structure Pattern: + * + * <g class="nodes"> + * <g class="node"> + * <g class="in-annotations"> + * ... + * </g> + * <g class="out-annotations"> + * ... + * </g> + * <g class="nodeshape"> + * <!-- + * Content of the node shape should be for the node itself. For example a + * Metanode would have a <rect> with rounded edges, an op would have an + * <ellipse>. More complex nodes like series may contain multiple elements + * which are conditionally visible based on whether the node is expanded. + * --> + * </g> + * <text class="label">node name</text> + * <g class="subscene"> + * <!-- + * Content of the subscene (only for metanode and series node). + * + * Subscene is a svg group that contains content of the + * metanode's metagraph that is recursively generated by Scene.build(). + * + * When the graph is expanded multiple times, a subscene can contain + * nested subscenes inside. + * --> + * </g> + * </g> + * ... + * </g> + * + * + * @param sceneGroup selection of the container + * @param nodeData array of render node information to map + * @param sceneBehavior parent scene module + * @return selection of the created nodeGroups + */ +export function buildGroup(sceneGroup, + nodeData: render.RenderNodeInformation[], sceneBehavior) { + let container = scene.selectOrCreateChild(sceneGroup, "g", + Class.Node.CONTAINER); + // Select all children and join with data. + // (Note that all children of g.nodes are g.node) + let nodeGroups = container.selectAll(function() { + // using d3's selector function + // See https://github.com/mbostock/d3/releases/tag/v2.0.0 + // (It's not listed in the d3 wiki.) + return this.childNodes; // this here refers to container.node() + }) + .data(nodeData, (d: any) => { + // make sure that we don't have to swap shape type + return d.node.name + ":" + d.node.type; + }); + + // ENTER + nodeGroups.enter() + .append("g") + .attr("data-name", d => { return d.node.name; }) + .each(function(d) { + let nodeGroup = d3.select(this); + // index node group for quick stylizing + sceneBehavior.addNodeGroup(d.node.name, nodeGroup); + }); + + // UPDATE + nodeGroups + .attr("class", d => { + return Class.Node.GROUP + " " + nodeClass(d); + }) + .each(function(d) { + let nodeGroup = d3.select(this); + // add g.in-annotations (always add -- to keep layer order consistent.) + let inAnnotationBox = scene.selectOrCreateChild(nodeGroup, "g", + Class.Annotation.INBOX); + annotation.buildGroup(inAnnotationBox, d.inAnnotations, d, + sceneBehavior); + + // add g.out-annotations (always add -- to keep layer order consistent.) + let outAnnotationBox = scene.selectOrCreateChild(nodeGroup, "g", + Class.Annotation.OUTBOX); + annotation.buildGroup(outAnnotationBox, d.outAnnotations, d, + sceneBehavior); + + // label + let label = labelBuild(nodeGroup, d, sceneBehavior); + // Do not add interaction to metanode labels as they live inside the + // metanode shape which already has the same interactions. + addInteraction(label, d, sceneBehavior, d.node.type === NodeType.META); + + // build .shape below label + let shape = buildShape(nodeGroup, d, Class.Node.SHAPE, label.node()); + if (d.node.isGroupNode) { + addButton(shape, d, sceneBehavior); + } + addInteraction(shape, d, sceneBehavior); + + // build subscene on the top + subsceneBuild(nodeGroup, d, sceneBehavior); + + stylize(nodeGroup, d, sceneBehavior); + position(nodeGroup, d, sceneBehavior); + }); + + // EXIT + nodeGroups.exit() + .each(function(d) { + // remove all indices on remove + sceneBehavior.removeNodeGroup(d.node.name); + + let nodeGroup = d3.select(this); + if (d.inAnnotations.list.length > 0) { + nodeGroup.select("." + Class.Annotation.INBOX) + .selectAll("." + Class.Annotation.GROUP) + .each(a => { + sceneBehavior.removeAnnotationGroup(a, d); + }); + } + if (d.outAnnotations.list.length > 0) { + nodeGroup.select("." + Class.Annotation.OUTBOX) + .selectAll("." + Class.Annotation.GROUP) + .each(a => { + sceneBehavior.removeAnnotationGroup(a, d); + }); + } + }) + .remove(); + return nodeGroups; +}; + +/** + * Update or remove the subscene of a render group node depending on whether it + * is a expanded. If the node is not a group node, this method has no effect. + * + * @param nodeGroup selection of the container + * @param renderNodeInfo the render information for the node. + * @param sceneBehavior parent scene module + * @return Selection of the subscene group, or null if node group does not have + * a subscene. Op nodes, bridge nodes and unexpanded group nodes will + * not have a subscene. + */ +function subsceneBuild(nodeGroup, + renderNodeInfo: render.RenderGroupNodeInformation, sceneBehavior) { + if (renderNodeInfo.node.isGroupNode) { + if (renderNodeInfo.expanded) { + // Recursively build the subscene. + return scene.buildGroup(nodeGroup, renderNodeInfo, sceneBehavior, + Class.Subscene.GROUP); + } + // Clean out existing subscene if the node is not expanded. + scene.selectChild(nodeGroup, "g", Class.Subscene.GROUP).remove(); + } + return null; +}; + +/** + * Translate the subscene of the given node group + */ +function subscenePosition(nodeGroup, d: render.RenderNodeInformation) { + let x0 = d.x - d.width / 2.0 + d.paddingLeft; + let y0 = d.y - d.height / 2.0 + d.paddingTop; + + let subscene = scene.selectChild(nodeGroup, "g", Class.Subscene.GROUP); + scene.translate(subscene, x0, y0); +}; + +/** + * Add an expand/collapse button to a group node + * + * @param selection The group node selection. + * @param d Info about the node being rendered. + * @param sceneBehavior parent scene module. + */ +function addButton(selection, d: render.RenderNodeInformation, sceneBehavior) { + let group = scene.selectOrCreateChild( + selection, "g", Class.Node.BUTTON_CONTAINER); + scene.selectOrCreateChild(group, "circle", Class.Node.BUTTON_CIRCLE); + scene.selectOrCreateChild(group, "path", Class.Node.EXPAND_BUTTON).attr( + "d", "M0,-2.2 V2.2 M-2.2,0 H2.2"); + scene.selectOrCreateChild(group, "path", Class.Node.COLLAPSE_BUTTON).attr( + "d", "M-2.2,0 H2.2"); + group.on("click", d => { + // Stop this event's propagation so that it isn't also considered a + // node-select. + (<Event>d3.event).stopPropagation(); + sceneBehavior.fire("node-toggle-expand", { name: d.node.name }); + }); + scene.positionButton(group, d); +}; + +/** + * Fire node-* events when the selection is interacted. + * + * @param disableInteraction When true, have the provided selection + * ignore all pointer events. Used for text labels inside of metanodes, which + * don't need interaction as their surrounding shape has interaction, and if + * given interaction would cause conflicts with the expand/collapse button. + */ +function addInteraction(selection, d: render.RenderNodeInformation, + sceneBehavior, disableInteraction?: boolean) { + if (disableInteraction) { + selection.attr("pointer-events", "none"); + return; + } + selection.on("dblclick", d => { + sceneBehavior.fire("node-toggle-expand", { name: d.node.name }); + }) + .on("mouseover", d => { + // don't send mouseover over expanded group, + // otherwise it is causing too much glitches + if (sceneBehavior.isNodeExpanded(d)) { return; } + + sceneBehavior.fire("node-highlight", { name: d.node.name }); + }) + .on("mouseout", d => { + // don't send mouseover over expanded group, + // otherwise it is causing too much glitches + if (sceneBehavior.isNodeExpanded(d)) { return; } + + sceneBehavior.fire("node-unhighlight", { name: d.node.name }); + }) + .on("click", d => { + // Stop this event's propagation so that it isn't also considered + // a graph-select. + (<Event>d3.event).stopPropagation(); + sceneBehavior.fire("node-select", { name: d.node.name }); + }); +}; + +/** + * Append svg text for label and assign data. + * @param nodeGroup + * @param renderNodeInfo The render node information for the label. + * @param sceneBehavior parent scene module. + */ +function labelBuild(nodeGroup, renderNodeInfo: render.RenderNodeInformation, + sceneBehavior) { + let namePath = renderNodeInfo.node.name.split("/"); + let text = namePath[namePath.length - 1]; + + // Truncate long labels for unexpanded Metanodes. + let useFontScale = renderNodeInfo.node.type === NodeType.META && + !renderNodeInfo.expanded; + + let label = scene.selectOrCreateChild(nodeGroup, "text", Class.Node.LABEL); + label.attr("dy", ".35em") + .attr("text-anchor", "middle"); + if (useFontScale) { + if (text.length > sceneBehavior.maxMetanodeLabelLength) { + text = text.substr(0, sceneBehavior.maxMetanodeLabelLength - 2) + "..."; + } + let scale = getLabelFontScale(sceneBehavior); + label.attr("font-size", scale(text.length) + "px"); + } + label.text(text); + return label; +}; + +/** + * d3 scale used for sizing font of labels, used by labelBuild, + * initialized once by getLabelFontScale. + */ +let fontScale = null; +function getLabelFontScale(sceneBehavior) { + if (!fontScale) { + fontScale = d3.scale.linear() + .domain([sceneBehavior.maxMetanodeLabelLengthLargeFont, + sceneBehavior.maxMetanodeLabelLength]) + .range([sceneBehavior.maxMetanodeLabelLengthFontSize, + sceneBehavior.minMetanodeLabelLengthFontSize]).clamp(true); + } + return fontScale; +} +/** + * Set label position of a given node group + */ +function labelPosition(nodeGroup, d: render.RenderNodeInformation, + yOffset: number) { + scene.selectChild(nodeGroup, "text", Class.Node.LABEL).transition() + .attr("x", d.x) + .attr("y", d.y + yOffset); +}; + +/** + * Select or append/insert shape for a node and assign renderNode + * as the shape's data. + * + * @param nodeGroup + * @param d RenderNodeInformation + * @param nodeClass class for the element. + * @param before Reference DOM node for insertion. + * @return Selection of the shape. + */ +export function buildShape(nodeGroup, d, nodeClass: string, before?) { + // Create a group to house the underlying visual elements. + let shapeGroup = scene.selectOrCreateChild(nodeGroup, "g", nodeClass, + before); + // TODO(jimbo): DOM structure should be templated in HTML somewhere, not JS. + switch (d.node.type) { + case NodeType.OP: + scene.selectOrCreateChild(shapeGroup, "ellipse", + Class.Node.COLOR_TARGET); + break; + case NodeType.SERIES: + // Choose the correct stamp to use to represent this series. + let stampType = "annotation"; + let groupNodeInfo = <render.RenderGroupNodeInformation>d; + if (groupNodeInfo.coreGraph) { + stampType = groupNodeInfo.node.hasNonControlEdges + ? "vertical" : "horizontal"; + } + scene.selectOrCreateChild(shapeGroup, "use", Class.Node.COLOR_TARGET) + .attr("xlink:href", "#op-series-" + stampType + "-stamp"); + scene.selectOrCreateChild(shapeGroup, "rect", Class.Node.COLOR_TARGET) + .attr({ rx: d.radius, ry: d.radius }); + break; + case NodeType.BRIDGE: + scene.selectOrCreateChild(shapeGroup, "rect", Class.Node.COLOR_TARGET) + .attr({ rx: d.radius, ry: d.radius }); + break; + case NodeType.META: + scene.selectOrCreateChild(shapeGroup, "rect", Class.Node.COLOR_TARGET) + .attr({ rx: d.radius, ry: d.radius }); + break; + default: + throw Error("Unrecognized node type: " + d.node.type); + } + return shapeGroup; +}; + +export function nodeClass(d: render.RenderNodeInformation) { + switch (d.node.type) { + case NodeType.OP: + return Class.OPNODE; + case NodeType.META: + return Class.METANODE; + case NodeType.SERIES: + return Class.SERIESNODE; + case NodeType.BRIDGE: + return Class.BRIDGENODE; + case NodeType.ELLIPSIS: + return Class.ELLIPSISNODE; + }; + throw Error("Unrecognized node type: " + d.node.type); +}; + +/** Modify node and its subscene and its label's positional attributes */ +function position(nodeGroup, d: render.RenderNodeInformation, sceneBehavior) { + let shapeGroup = scene.selectChild(nodeGroup, "g", Class.Node.SHAPE); + switch (d.node.type) { + case NodeType.OP: { + // position shape + let shape = scene.selectChild(shapeGroup, "ellipse"); + scene.positionEllipse(shape, d.x, d.y, d.width, d.height); + labelPosition(nodeGroup, d, d.labelOffset); + break; + } + case NodeType.META: { + // position shape + let shape = scene.selectChild(shapeGroup, "rect"); + scene.positionRect(shape, d.x, d.y, d.width, d.height); + + if (d.expanded) { + subscenePosition(nodeGroup, d); + + // put label on top + labelPosition(nodeGroup, d, + - d.height / 2 + d.labelHeight / 2); + } else { + labelPosition(nodeGroup, d, 0); + } + break; + } + case NodeType.SERIES: { + let shape = scene.selectChild(shapeGroup, "use"); + scene.positionRect(shape, d.x, d.y, d.width, d.height); + if (d.expanded) { + subscenePosition(nodeGroup, d); + + // put label on top + labelPosition(nodeGroup, d, + - d.height / 2 + d.labelHeight / 2); + } else { + labelPosition(nodeGroup, d, d.labelOffset); + } + } + case NodeType.BRIDGE: { + // position shape + // NOTE: In reality, these will not be visible, but it helps to put them + // in the correct position for debugging purposes. + let shape = scene.selectChild(shapeGroup, "rect"); + scene.positionRect(shape, d.x, d.y, d.width, d.height); + break; + } + default: { + throw Error("Unrecognized node type: " + d.node.type); + } + } +}; + +/** Enum specifying the options to color nodes by */ +let ColorBy = { + STRUCTURE: 0, + DEVICE: 1, + COMPUTE_TIME: 2, + MEMORY: 3 +}; + +/** + * Returns the fill color for the node given its state and the "color by" + * option. + */ +function getFillForNode(sceneBehavior, colorBy, + renderInfo: render.RenderNodeInformation, isExpanded: boolean): string { + let colorParams = tf.graph.render.MetanodeColors; + switch (colorBy) { + case ColorBy.STRUCTURE: + if (renderInfo.node.type === tf.graph.NodeType.META) { + let tid = (<Metanode>renderInfo.node).templateId; + return tid === null ? colorParams.UNKNOWN : colorParams.STRUCTURE_PALETTE( + sceneBehavior.templateIndex(tid), renderInfo.expanded); + } else if (renderInfo.node.type === tf.graph.NodeType.SERIES) { + // If expanded, we're showing the background rect, which we want to + // appear gray. Otherwise we're showing a stack of ellipses which we + // want to show white. + return renderInfo.expanded ? colorParams.EXPANDED_COLOR : "white"; + } else if (renderInfo.node.type === NodeType.BRIDGE) { + return renderInfo.structural ? "#f0e" : + (<BridgeNode>renderInfo.node).inbound ? "#0ef" : "#fe0"; + } else { + // Op nodes are white. + return "white"; + } + case ColorBy.DEVICE: + if (renderInfo.deviceColors == null) { + // Return the hue for unknown device. + return colorParams.UNKNOWN; + } + let id = renderInfo.node.name; + let escapedId = tf.escapeQuerySelector(id); + let gradientDefs = d3.select("svg#svg defs #linearGradients"); + let linearGradient = + gradientDefs.select("linearGradient#" + escapedId); + // If the linear gradient is not there yet, create it. + if (linearGradient.size() === 0) { + linearGradient = gradientDefs.append("linearGradient").attr("id", id); + // Re-create the stops of the linear gradient. + linearGradient.selectAll("*").remove(); + let cumulativeProportion = 0; + // For each device, create a stop using the proportion of that device. + _.each(renderInfo.deviceColors, (d: any) => { + let color = d.color; + linearGradient.append("stop") + .attr("offset", cumulativeProportion) + .attr("stop-color", color); + linearGradient.append("stop") + .attr("offset", cumulativeProportion + d.proportion) + .attr("stop-color", color); + cumulativeProportion += d.proportion; + }); + } + return isExpanded ? colorParams.EXPANDED_COLOR : `url(#${escapedId})`; + case ColorBy.COMPUTE_TIME: + return isExpanded ? + colorParams.EXPANDED_COLOR : renderInfo.computeTimeColor || + colorParams.UNKNOWN; + case ColorBy.MEMORY: + return isExpanded ? + colorParams.EXPANDED_COLOR : renderInfo.memoryColor || + colorParams.UNKNOWN; + default: + throw new Error("Unknown case to color nodes by"); + } +} + +/** + * Modify node style by toggling class and assign attributes (only for things + * that can't be done in css). + */ +export function stylize(nodeGroup, renderInfo: render.RenderNodeInformation, + sceneBehavior, nodeClass?) { + nodeClass = nodeClass || Class.Node.SHAPE; + let isHighlighted = sceneBehavior.isNodeHighlighted(renderInfo.node.name); + let isSelected = sceneBehavior.isNodeSelected(renderInfo.node.name); + let isExtract = renderInfo.isInExtract || renderInfo.isOutExtract; + let isExpanded = renderInfo.expanded; + nodeGroup.classed("highlighted", isHighlighted); + nodeGroup.classed("selected", isSelected); + nodeGroup.classed("extract", isExtract); + nodeGroup.classed("expanded", isExpanded); + + // Main node always exists here and it will be reached before subscene, + // so d3 selection is fine here. + let node = nodeGroup.select("." + nodeClass + " ." + Class.Node.COLOR_TARGET); + let fillColor = getFillForNode(sceneBehavior, + ColorBy[sceneBehavior.colorBy.toUpperCase()], + renderInfo, isExpanded); + node.style("fill", fillColor); + + // Choose outline to be darker version of node color if the node is a single + // color and is not selected. + if (isSelected) { + node.style("stroke", null); + } else { + // If node is colored by a gradient, then use a dark gray outline. + let outlineColor = fillColor.substring(0, 3) === "url" ? + tf.graph.render.MetanodeColors.GRADIENT_OUTLINE : + d3.rgb(fillColor).darker().toString(); + node.style("stroke", outlineColor); + } +}; + +} // close module diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/scene/scene.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/scene.ts new file mode 100644 index 0000000000..2e2467f039 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/scene/scene.ts @@ -0,0 +1,409 @@ +/// <reference path="../graph.ts" /> +/// <reference path="edge.ts" /> +/// <reference path="node.ts" /> +/// <reference path="../layout.ts" /> + +module tf.graph.scene { + +/** Enums element class of objects in the scene */ +export let Class = { + Node: { + // <g> element that contains nodes. + CONTAINER: "nodes", + // <g> element that contains detail about a node. + GROUP: "node", + // <g> element that contains visual elements (like rect, ellipse). + SHAPE: "nodeshape", + // <*> element(s) under SHAPE that should receive color updates. + COLOR_TARGET: "nodecolortarget", + // <text> element showing the node's label. + LABEL: "nodelabel", + // <g> element that contains all visuals for the expand/collapse + // button for expandable group nodes. + BUTTON_CONTAINER: "buttoncontainer", + // <circle> element that surrounds expand/collapse buttons. + BUTTON_CIRCLE: "buttoncircle", + // <path> element of the expand button. + EXPAND_BUTTON: "expandbutton", + // <path> element of the collapse button. + COLLAPSE_BUTTON: "collapsebutton" + }, + Edge: { + CONTAINER: "edges", + GROUP: "edge", + LINE: "edgeline", + REF_LINE: "refline", + STRUCTURAL: "structural" + }, + Annotation: { + OUTBOX: "out-annotations", + INBOX: "in-annotations", + GROUP: "annotation", + NODE: "annotation-node", + EDGE: "annotation-edge", + CONTROL_EDGE: "annotation-control-edge", + LABEL: "annotation-label", + ELLIPSIS: "annotation-ellipsis" + }, + Scene: { + GROUP: "scene", + CORE: "core", + INEXTRACT: "in-extract", + OUTEXTRACT: "out-extract" + }, + Subscene: { + GROUP: "subscene" + }, + OPNODE: "op", + METANODE: "meta", + SERIESNODE: "series", + BRIDGENODE: "bridge", + ELLIPSISNODE: "ellipsis" +}; + +/** + * Helper method for fitting the graph in the svg view. + * + * @param svg The main svg. + * @param zoomG The svg group used for panning and zooming. + * @param d3zoom The zoom behavior. + * @param callback Called when the fitting is done. + */ +export function fit(svg, zoomG, d3zoom, callback) { + let svgRect = svg.getBoundingClientRect(); + let sceneSize = zoomG.getBBox(); + let scale = 0.9 * Math.min( + svgRect.width / sceneSize.width, + svgRect.height / sceneSize.height, + 2 + ); + let params = layout.PARAMS.graph; + let zoomEvent = d3zoom.scale(scale) + .on("zoomend.fitted", () => { + // Remove the listener for the zoomend event, + // so we don't get called at the end of regular zoom events, + // just those that fit the graph to screen. + d3zoom.on("zoomend.fitted", null); + callback(); + }) + .translate([params.padding.paddingLeft, params.padding.paddingTop]) + .event; + d3.select(zoomG).transition().duration(500).call(zoomEvent); +}; + +/** + * Helper method for panning the graph to center on the provided node, + * if the node is currently off-screen. + * + * @param nodeName The node to center the graph on + * @param svg The root SVG element for the graph + * @param zoomG The svg group used for panning and zooming. + * @param d3zoom The zoom behavior. + * @return True if the graph had to be panned to display the + * provided node. + */ +export function panToNode(nodeName: String, svg, zoomG, d3zoom): boolean { + let node: any = d3.selectAll("[data-name='" + nodeName + "']." + + Class.Node.GROUP)[0][0]; + if (!node) { + return false; + } + let translate = d3zoom.translate(); + // Check if the selected node is off-screen in either + // X or Y dimension in either direction. + let nodeBox = node.getBBox(); + let nodeCtm = node.getScreenCTM(); + let pointTL = svg.createSVGPoint(); + let pointBR = svg.createSVGPoint(); + pointTL.x = nodeBox.x; + pointTL.y = nodeBox.y; + pointBR.x = nodeBox.x + nodeBox.width; + pointBR.y = nodeBox.y + nodeBox.height; + pointTL = pointTL.matrixTransform(nodeCtm); + pointBR = pointBR.matrixTransform(nodeCtm); + let isOutsideOfBounds = (start, end, bound) => { + return end < 0 || start > bound; + }; + let svgRect = svg.getBoundingClientRect(); + if (isOutsideOfBounds(pointTL.x, pointBR.x, svgRect.width) || + isOutsideOfBounds(pointTL.y, pointBR.y, svgRect.height)) { + // Determine the amount to transform the graph in both X and Y + // dimensions in order to center the selected node. This takes into + // acount the position of the node, the size of the svg scene, the + // amount the scene has been scaled by through zooming, and any previous + // transform already performed by this logic. + let centerX = (pointTL.x + pointBR.x) / 2; + let centerY = (pointTL.y + pointBR.y) / 2; + let dx = ((svgRect.width / 2) - centerX); + let dy = ((svgRect.height / 2) - centerY); + let zoomEvent = d3zoom.translate([translate[0] + dx, translate[1] + dy]) + .event; + d3.select(zoomG).transition().duration(500).call(zoomEvent); + return true; + } + return false; +}; + +/** + * Given a container d3 selection, select a child svg element of a given tag + * and class if exists or append / insert one otherwise. If multiple children + * matches the tag and class name, returns only the first one. + * + * @param container + * @param tagName tag name. + * @param className (optional) Class name. + * @param before (optional) reference DOM node for insertion. + * @return selection of the element + */ +export function selectOrCreateChild(container, tagName: string, + className?: string, before?) { + let child = selectChild(container, tagName, className); + if (!child.empty()) { + return child; + } + let newElement = document.createElementNS("http://www.w3.org/2000/svg", + tagName); + if (className) { + newElement.classList.add(className); + } + + if (before) { // if before exists, insert + container.node().insertBefore(newElement, before); + } else { // otherwise, append + container.node().appendChild(newElement); + } + return d3.select(newElement) + // need to bind data to emulate d3_selection.append + .datum(container.datum()); +}; + +/** + * Given a container d3 selection, select a child element of a given tag and + * class. If multiple children matches the tag and class name, returns only + * the first one. + * + * @param container + * @param tagName tag name. + * @param className (optional) Class name. + * @return selection of the element, or an empty selection + */ +export function selectChild(container, tagName: string, className?: string) { + let children = container.node().childNodes; + for (let i = 0; i < children.length; i++) { + let child = children[i]; + if (child.tagName === tagName && + (!className || child.classList.contains(className)) + ) { + return d3.select(child); + } + } + return d3.select(null); +}; + +/** + * Select or create a sceneGroup and build/update its nodes and edges. + * + * Structure Pattern: + * + * <g class="scene"> + * <g class="core"> + * <g class="edges"> + * ... stuff from tf.graph.scene.edges.build ... + * </g> + * <g class="nodes"> + * ... stuff from tf.graph.scene.nodes.build ... + * </g> + * </g> + * <g class="in-extract"> + * <g class="nodes"> + * ... stuff from tf.graph.scene.nodes.build ... + * </g> + * </g> + * <g class="out-extract"> + * <g class="nodes"> + * ... stuff from tf.graph.scene.nodes.build ... + * </g> + * </g> + * </g> + * + * @param container D3 selection of the parent. + * @param renderNode render node of a metanode or series node. + * @param sceneBehavior Parent scene module. + * @param sceneClass class attribute of the scene (default="scene"). + */ +export function buildGroup(container, + renderNode: render.RenderGroupNodeInformation, + sceneBehavior, + sceneClass: string) { + sceneClass = sceneClass || Class.Scene.GROUP; + let isNewSceneGroup = selectChild(container, "g", sceneClass).empty(); + let sceneGroup = selectOrCreateChild(container, "g", sceneClass); + + // core + let coreGroup = selectOrCreateChild(sceneGroup, "g", Class.Scene.CORE); + let coreNodes = _.reduce(renderNode.coreGraph.nodes(), (nodes, name) => { + let node = renderNode.coreGraph.node(name); + if (!node.excluded) { + nodes.push(node); + } + return nodes; + }, []); + + if (renderNode.node.type === NodeType.SERIES) { + // For series, we want the first item on top, so reverse the array so + // the first item in the series becomes last item in the top, and thus + // is rendered on the top. + coreNodes.reverse(); + } + + // Create the layer of edges for this scene (paths). + edge.buildGroup(coreGroup, renderNode.coreGraph, sceneBehavior); + + // Create the layer of nodes for this scene (ellipses, rects etc). + node.buildGroup(coreGroup, coreNodes, sceneBehavior); + + // In-extract + if (renderNode.isolatedInExtract.length > 0) { + let inExtractGroup = selectOrCreateChild(sceneGroup, "g", + Class.Scene.INEXTRACT); + node.buildGroup(inExtractGroup, renderNode.isolatedInExtract, + sceneBehavior); + } else { + selectChild(sceneGroup, "g", Class.Scene.INEXTRACT).remove(); + } + + // Out-extract + if (renderNode.isolatedOutExtract.length > 0) { + let outExtractGroup = selectOrCreateChild(sceneGroup, "g", + Class.Scene.OUTEXTRACT); + node.buildGroup(outExtractGroup, renderNode.isolatedOutExtract, + sceneBehavior); + } else { + selectChild(sceneGroup, "g", Class.Scene.OUTEXTRACT).remove(); + } + + position(sceneGroup, renderNode); + + // Fade in the scene group if it didn't already exist. + if (isNewSceneGroup) { + sceneGroup.attr("opacity", 0) + .transition().attr("opacity", 1); + } + + return sceneGroup; +}; + +/** + * Given a scene's svg group, set g.in-extract, g.coreGraph, g.out-extract svg + * groups' position relative to the scene. + * + * @param sceneGroup + * @param renderNode render node of a metanode or series node. + */ +function position(sceneGroup, renderNode: render.RenderGroupNodeInformation) { + // Translate scenes down by the label height so that when showing graphs in + // expanded metanodes, the graphs are below the labels. Do not shift them + // down for series nodes as series nodes don't have labels inside of their + // bounding boxes. + let yTranslate = renderNode.node.type === NodeType.SERIES ? + 0 : layout.PARAMS.subscene.meta.labelHeight; + + // core + translate(selectChild(sceneGroup, "g", Class.Scene.CORE), + 0, yTranslate); + + // in-extract + let inExtractX = renderNode.coreBox.width === 0 ? + 0 : renderNode.coreBox.width; + let hasInExtract = renderNode.isolatedInExtract.length > 0; + if (hasInExtract) { + translate(selectChild(sceneGroup, "g", Class.Scene.INEXTRACT), + inExtractX, yTranslate); + } + + // out-extract + let hasOutExtract = renderNode.isolatedOutExtract.length > 0; + if (hasOutExtract) { + let outExtractX = inExtractX + renderNode.inExtractBox.width + + renderNode.extractXOffset; + translate(selectChild(sceneGroup, "g", Class.Scene.OUTEXTRACT), + outExtractX, yTranslate); + } +}; + +/** Adds a click listener to a group that fires a graph-select event */ +export function addGraphClickListener(graphGroup, sceneBehavior) { + d3.select(graphGroup).on("click", () => { + sceneBehavior.fire("graph-select"); + }); +}; + +/** Helper for adding transform: translate(x0, y0) */ +export function translate(selection, x0: number, y0: number) { + selection.attr("transform", "translate(" + x0 + "," + y0 + ")"); +}; + +/** + * Helper for setting position of a svg rect + * @param rect rect to set position of. + * @param cx Center x. + * @param cy Center x. + * @param width Width to set. + * @param height Height to set. + */ +export function positionRect(rect, cx: number, cy: number, width: number, + height: number) { + rect.transition().attr({ + x: cx - width / 2, + y: cy - height / 2, + width: width, + height: height + }); +}; + +/** + * Helper for setting position of a svg expand/collapse button + * @param button container group + * @param renderNode the render node of the group node to position + * the button on. + */ +export function positionButton(button, + renderNode: render.RenderNodeInformation) { + // Position the button in the top-right corner of the group node, + // with space given the draw the button inside of the corner. + let x = renderNode.x + renderNode.width / 2 - 6; + let y = renderNode.y - renderNode.height / 2 + 6; + // For unexpanded series nodes, the button has special placement due + // to the unique visuals of this group node. + if (renderNode.node.type === NodeType.SERIES && !renderNode.expanded) { + x += 10; + y -= 2; + } + let translateStr = "translate(" + x + "," + y + ")"; + button.selectAll("path").transition().attr("transform", translateStr); + button.select("circle").transition().attr({ + cx: x, + cy: y, + r: layout.PARAMS.nodeSize.meta.expandButtonRadius + }); +}; + +/** + * Helper for setting position of a svg ellipse + * @param ellipse ellipse to set position of. + * @param cx Center x. + * @param cy Center x. + * @param width Width to set. + * @param height Height to set. + */ +export function positionEllipse(ellipse, cx: number, cy: number, + width: number, height: number) { + ellipse.transition().attr({ + cx: cx, + cy: cy, + rx: width / 2, + ry: height / 2 + }); +}; + +} // close module diff --git a/tensorflow/tensorboard/components/tf-graph-common/lib/template.ts b/tensorflow/tensorboard/components/tf-graph-common/lib/template.ts new file mode 100644 index 0000000000..b5aafc55e5 --- /dev/null +++ b/tensorflow/tensorboard/components/tf-graph-common/lib/template.ts @@ -0,0 +1,282 @@ +/// <reference path="graph.ts" /> +/// <reference path="hierarchy.ts" /> + +module tf.graph.template { + +/** + * Detect repeating patterns of subgraphs. + * Assign templateId to each subgraph if it belongs to a template. + * Returns clusters of similar subgraphs . + * + * @param graph + * @param verifyTemplate whether to run the template verification algorithm + * @return a dict (template id => Array of node names) + */ +export function detect(h, verifyTemplate): {[templateId: string]: string[]} { + // In any particular subgraph, there are either + // - leaf nodes (which do not have subgraph) + // - metanode nodes - some of them have only one member (singular metanode) + // and some have multiple members (non-singular metanode) + + // First, generate a nearest neighbor hash of metanode nodes. + let nnGroups = clusterSimilarSubgraphs(h); + + // For each metanode, compare its subgraph (starting from shallower groups) + // and assign template id. + let templates = groupTemplateAndAssignId(nnGroups, verifyTemplate); + + // Sort the templates by minimum level in the graph at which they appear, + // as this leads to optimal setting of the colors of each template for + // maximum differentiation. + return _(templates).pairs() + .sortBy(function(pair) { + return pair[1].level; + }) + .map(function(pair) { + return [pair[0], pair[1].nodes]; + }) + .object().value(); +}; + +/** + * @return Unique string for a metanode based on depth, |V|, |E| and + * op type histogram. + */ + function getSignature(metanode) { + // depth=<number> |V|=<number> |E|=<number> + let props = _.map({ + "depth": metanode.depth, + "|V|": metanode.metagraph.nodes().length, + "|E|": metanode.metagraph.edges().length + }, function(v, k) { return k + "=" + v; }).join(" "); + + // optype1=count1,optype2=count2 + let ops = _.map(metanode.opHistogram, function(count, op) { + return op + "=" + count; + }).join(","); + + return props + " [ops] " + ops; +} + +/** + * Generate a nearest neighbor hash of metanodes + * based on depth, |V|, |E|, and opHistogram of their subgraph + * (excluding leaf nodes and singular metanodes). + * @param graph The graph + * @return Array of pairs of [signature, + * Object with min level of the template and an Array of tf.graph.Group] + * sort by ascending order of minimum depth at which metanode appears. + */ +function clusterSimilarSubgraphs(h: hierarchy.Hierarchy) { + /** a dict from metanode.signature() => Array of tf.graph.Groups */ + let hashDict = _(h.getNodeMap()).reduce(function(hash, node: OpNode|Metanode, name) { + if (node.type !== NodeType.META) { + return hash; + } + let levelOfMetaNode = name.split("/").length - 1; + let signature = getSignature(node); + let templateInfo = hash[signature] || + {nodes: [], level: levelOfMetaNode}; + hash[signature] = templateInfo; + templateInfo.nodes.push(node); + if (templateInfo.level > levelOfMetaNode) { + templateInfo.level = levelOfMetaNode; + } + return hash; + }, {}); + + return _(hashDict).pairs() + // filter nn metanode with only one member + .filter(function(pair) { + return pair[1].nodes.length > 1; + }) + .sortBy(function(pair) { + // sort by depth + // (all members in the same nnGroup has equal depth) + return pair[1].nodes[0].depth; + }) + .value(); +} + +function groupTemplateAndAssignId(nnGroups, verifyTemplate) { + // For each metanode, compare its subgraph (starting from shallower groups) + // and assign template id. + return _.reduce(nnGroups, function(templates, nnGroupPair) { + let signature = nnGroupPair[0], + nnGroup = nnGroupPair[1].nodes, + clusters = []; + + nnGroup.forEach(function(metanode) { + // check with each existing cluster + for (let i = 0; i < clusters.length; i++) { + let similar = !verifyTemplate || + isSimilarSubgraph( + clusters[i].metanode.metagraph, + metanode.metagraph + ); + // if similar, just add this metanode to the cluster + if (similar) { + // get template from the first one + metanode.templateId = clusters[i].metanode.templateId; + clusters[i].members.push(metanode.name); + return; + } + } + // otherwise create a new cluster with id "signature [count] " + metanode.templateId = signature + "[" + clusters.length + "]"; + clusters.push({ + metanode: metanode, + members: [metanode.name] + }); + }); + + clusters.forEach(function(c) { + templates[c.metanode.templateId] = { + level: nnGroupPair[1].level, + nodes: c.members + }; + }); + return templates; + }, {}); +} + +function sortNodes(names: string[], graph: graphlib.Graph<Metanode|OpNode, Metaedge>, + prefix: string) { + return _.sortByAll(names, + function(name) { + let node = graph.node(name); + return (<OpNode>node).op; + }, + function(name) { + let node = graph.node(name); + return (<Metanode>node).templateId; + }, + function(name) { + return graph.neighbors(name).length; + }, + function(name) { + return graph.predecessors(name).length; + }, + function(name) { + return graph.successors(name).length; + }, + function(name) { + return name.substr(prefix.length); + }); +} + +function isSimilarSubgraph(g1: graphlib.Graph<any, any>, g2: graphlib.Graph<any, any>) { + if (!tf.graph.hasSimilarDegreeSequence(g1, g2)) { + return false; + } + + // if we want to skip, just return true here. + // return true; + + // Verify sequence by running DFS + let g1prefix = g1.graph().name; + let g2prefix = g2.graph().name; + + let visited1 = {}; + let visited2 = {}; + let stack = []; + + /** + * push sources or successors into the stack + * if the visiting pattern has been similar. + */ + function stackPushIfNotDifferent(n1, n2) { + let sub1 = n1.substr(g1prefix.length), + sub2 = n2.substr(g2prefix.length); + + /* tslint:disable */ + if (visited1[sub1] ^ visited2[sub1]) { + console.warn("different visit pattern", "[" + g1prefix + "]", sub1, + "[" + g2prefix + "]", sub2); + return true; + } + /* tslint:enable */ + if (!visited1[sub1]) { // implied && !visited2[sub2] + visited1[sub1] = visited2[sub2] = true; + stack.push({n1: n1, n2: n2}); + } + + return false; + } + + // check if have same # of sources then sort and push + let sources1 = g1.sources(); + let sources2 = g2.sources(); + if (sources1.length !== sources2.length) { + /* tslint:disable */ + console.log("different source length"); + /* tslint:enable */ + return false; + } + sources1 = sortNodes(sources1, g1, g1prefix); + sources2 = sortNodes(sources2, g2, g2prefix); + + for (let i = 0; i < sources1.length; i++) { + let different = stackPushIfNotDifferent(sources1[i], sources2[i]); + if (different) { + return false; + } + } + + while (stack.length > 0) { + let cur = stack.pop(); + + // check node + let similar = isSimilarNode(g1.node(cur.n1), g2.node(cur.n2)); + if (!similar) { + return false; + } + + // check if have same # of successors then sort and push + let succ1 = g1.successors(cur.n1), succ2 = g2.successors(cur.n2); + if (succ1.length !== succ2.length) { + /* tslint:disable */ + console.log("# of successors mismatch", succ1, succ2); + /* tslint:enable */ + return false; + } + succ1 = sortNodes(succ1, g1, g1prefix); + succ2 = sortNodes(succ2, g2, g2prefix); + + for (let j = 0; j < succ1.length; j++) { + let different = stackPushIfNotDifferent(succ1[j], succ2[j]); + if (different) { + return false; + } + } + } + + return true; +} + +/** + * Returns if two nodes have identical structure. + */ + function isSimilarNode(n1: OpNode|Metanode|SeriesNode, n2: OpNode|Metanode|SeriesNode): boolean { + if (n1.type === NodeType.META) { + // compare metanode + let metanode1 = <Metanode> n1; + let metanode2 = <Metanode> n2; + return metanode1.templateId && metanode2.templateId && metanode1.templateId === metanode2.templateId; + } else if (n1.type === NodeType.OP && n2.type === NodeType.OP) { + // compare leaf node + return (<OpNode>n1).op === (<OpNode>n2).op; + } else if (n1.type === NodeType.SERIES && n2.type === NodeType.SERIES) { + // compare series node sizes and operations + // (only need to check one op as all op nodes are identical in series) + let seriesnode1 = <SeriesNode> n1; + let seriesnode2 = <SeriesNode> n2; + let seriesnode1Count = seriesnode1.metagraph.nodeCount(); + return (seriesnode1Count === seriesnode2.metagraph.nodeCount() && + (seriesnode1Count === 0 || + ((<OpNode>seriesnode1.metagraph.node(seriesnode1.metagraph.nodes()[0])).op === + (<OpNode>seriesnode2.metagraph.node(seriesnode2.metagraph.nodes()[0])).op))); + } + return false; +} +} |