1 files changed, 715 insertions, 0 deletions
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