| // Copyright 2020 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| /** |
| * @fileoverview Data structures for representing a directed graph. |
| */ |
| |
| /** Some aspects of the node's state, to help with node visualization. */ |
| class NodeVisualizationState { |
| constructor() { |
| /** @public {boolean} */ |
| this.selectedByFilter = false; |
| /** @public {boolean} */ |
| this.selectedByInbound = false; |
| /** @public {boolean} */ |
| this.selectedByOutbound = false; |
| /** @public {number} */ |
| this.inboundDepth = 0; |
| /** @public {number} */ |
| this.outboundDepth = 0; |
| } |
| } |
| |
| /** A node in a directed graph. */ |
| class GraphNode { |
| /** |
| * @param {string} id The unique ID for the node. |
| * @param {string} displayName The name to display when visualizing this node. |
| */ |
| constructor(id, displayName) { |
| /** @public @const {string} */ |
| this.id = id; |
| /** @public @const {string} */ |
| this.displayName = displayName; |
| |
| // Sets a mutable state to help with visualizing the node. |
| this.visualizationState = new NodeVisualizationState(); |
| |
| // This information (edges) already exists in Graph.edges. However, we |
| // duplicate it here to make BFS traversal more efficient. |
| /** @public {!Set<!GraphNode>} */ |
| this.inbound = new Set(); |
| /** @public {!Set<!GraphNode>} */ |
| this.outbound = new Set(); |
| } |
| |
| /** |
| * Resets the mutable visualization state back to its default. |
| */ |
| resetVisualizationState() { |
| this.visualizationState = new NodeVisualizationState(); |
| } |
| |
| /** |
| * Adds a node to the inbound set of this node. |
| * @param {!GraphNode} other The inbound node. |
| */ |
| addInbound(other) { |
| this.inbound.add(other); |
| } |
| |
| /** |
| * Adds a node to the outbound set of this node. |
| * @param {!GraphNode} other The outbound node. |
| */ |
| addOutbound(other) { |
| this.outbound.add(other); |
| } |
| } |
| |
| /** A node representing a Java package. */ |
| class PackageNode extends GraphNode { |
| constructor(id, displayName, classNames) { |
| super(id, displayName); |
| |
| /** @public {!Array<string>} */ |
| this.classNames = classNames; |
| } |
| } |
| |
| /** A node representing a Java class. */ |
| class ClassNode extends GraphNode { |
| constructor(id, displayName, packageName) { |
| super(id, displayName); |
| |
| /** @public {string} */ |
| this.packageName = packageName; |
| } |
| } |
| |
| /** |
| * An edge in a directed graph. |
| */ |
| class GraphEdge { |
| /** |
| * @param {string} id The unique ID for the edge. |
| * @param {!GraphNode} source The source GraphNode object. |
| * @param {!GraphNode} target The target GraphNode object. |
| */ |
| constructor(id, source, target) { |
| /** @public @const {string} */ |
| this.id = id; |
| /** @public @const {!GraphNode} */ |
| this.source = source; |
| /** @public @const {!GraphNode} */ |
| this.target = target; |
| } |
| } |
| |
| /** |
| * The graph data for d3 to visualize. |
| * |
| * @typedef {Object} D3GraphData |
| * @property {!Array<!GraphNode>} nodes The nodes to visualize. |
| * @property {!Array<!GraphEdge>} edges The edges to visualize. |
| */ |
| let D3GraphData; |
| |
| /** |
| * Generates and returns a unique edge ID from its source/target GraphNode IDs. |
| * @param {string} sourceId The ID of the source node. |
| * @param {string} targetId The ID of the target node. |
| * @return {string} The ID uniquely identifying the edge source -> target. |
| */ |
| function getEdgeIdFromNodes(sourceId, targetId) { |
| return `${sourceId} > ${targetId}`; |
| } |
| |
| /** A directed graph. */ |
| class GraphModel { |
| constructor() { |
| /** @public {!Map<string, !GraphNode>} */ |
| this.nodes = new Map(); |
| /** @public {!Map<string, !GraphEdge>} */ |
| this.edges = new Map(); |
| } |
| |
| /** |
| * Adds a GraphNode to the node set. |
| * @param {!GraphNode} node The node to add. |
| */ |
| addNodeIfNew(node) { |
| if (!this.nodes.has(node.id)) { |
| this.nodes.set(node.id, node); |
| } |
| } |
| |
| /** |
| * Retrieves a GraphNode from the node set, if it exists. |
| * @param {string} id The ID of the desired node. |
| * @return {?GraphNode} The GraphNode if it exists, otherwise null. |
| */ |
| getNodeById(id) { |
| return this.nodes.get(id) || null; |
| } |
| |
| /** |
| * Retrieves a GraphEdge from the edge set, if it exists. |
| * @param {string} id The ID of the desired edge. |
| * @return {?GraphEdge} The GraphEdge if it exists, otherwise null. |
| */ |
| getEdgeById(id) { |
| return this.edges.get(id) || null; |
| } |
| |
| /** |
| * Creates and adds an GraphEdge to the edge set. |
| * Also updates the inbound/outbound sets of the edge's nodes. |
| * @param {!GraphNode} sourceNode The node at the start of the edge. |
| * @param {!GraphNode} targetNode The node at the end of the edge. |
| */ |
| addEdgeIfNew(sourceNode, targetNode) { |
| const edgeId = getEdgeIdFromNodes(sourceNode.id, targetNode.id); |
| if (!this.edges.has(edgeId)) { |
| const edge = new GraphEdge(edgeId, sourceNode, targetNode); |
| this.edges.set(edgeId, edge); |
| sourceNode.addOutbound(targetNode); |
| targetNode.addInbound(sourceNode); |
| } |
| } |
| |
| /** |
| * Generates the lists of nodes and edges for visualization with d3. |
| * |
| * The filter has three params: includedNodes (set of nodes), inbound (num), |
| * and outbound (num). For nodes, we display `includedNodes` + the nodes |
| * reachable within `inbound` inbound edges from `includedNodes` + the nodes |
| * reachable within `outbound` outbound edges from `includedNodes`. For edges, |
| * we display edges between all nodes except for the outermost layer, where we |
| * only display the edges used to reach it from the second-outermost layer. |
| * |
| * @param {!Set<string>} includedNodeSet The nodes included in the filter. |
| * @param {number} inboundDepth The maximum inbound distance. |
| * @param {number} outboundDepth The maximum outbound distance. |
| * @return {!D3GraphData} The nodes and edges to visualize. |
| */ |
| getDataForD3(includedNodeSet, inboundDepth, outboundDepth) { |
| // These will be updated throughout the function and returned at the end. |
| const /** !Set<!GraphNode> */ resultNodeSet = new Set(); |
| const /** !Set<!GraphNode> */ resultEdgeSet = new Set(); |
| |
| for (const node of this.nodes.values()) { |
| node.resetVisualizationState(); |
| } |
| |
| // Initialize the inbound and outbound BFS by setting the "seen" collection |
| // to the filter nodes. We maintain both a Set and array for efficiency. |
| const /** !Set<string> */ inboundSeenNodes = new Set(includedNodeSet); |
| const /** !Set<string> */ outboundSeenNodes = new Set(includedNodeSet); |
| const /** !Array<!GraphNode> */ inboundNodeQueue = []; |
| const /** !Array<!GraphNode> */ outboundNodeQueue = []; |
| for (const nodeName of includedNodeSet) { |
| const node = this.nodes.get(nodeName); |
| if (node !== undefined) { |
| node.visualizationState.selectedByFilter = true; |
| inboundNodeQueue.push(node); |
| outboundNodeQueue.push(node); |
| resultNodeSet.add(node); |
| } |
| } |
| |
| /** |
| * Runs BFS and updates the result (resultNodeSet, resultEdgeSet). |
| * @param {boolean} inboundTraversal Whether inbound edges should be used to |
| * traverse. If false, outbound edges are used. |
| * @param {!Set<string>} seenNodes The IDs of nodes already visited in the |
| * BFS. Will be modified. |
| * @param {!Array<!GraphNode>} nodeQueue The queue used in BFS. Will be |
| * modified. |
| * @param {number} maxDepth The depth of the traversal. |
| */ |
| const updateResultBFS = ( |
| inboundTraversal, seenNodes, nodeQueue, maxDepth) => { |
| while (nodeQueue.length > 0) { |
| // The performance on the repeated `shift()`s is not as bad as it might |
| // seem, since we only have ~500 nodes for the package graph. |
| const curNode = nodeQueue.shift(); |
| const curDepth = inboundTraversal ? |
| curNode.visualizationState.inboundDepth : |
| curNode.visualizationState.outboundDepth; |
| if (curDepth < maxDepth) { |
| const otherNodes = inboundTraversal ? |
| curNode.inbound : curNode.outbound; |
| for (const otherNode of otherNodes) { |
| if (!seenNodes.has(otherNode.id)) { |
| if (inboundTraversal) { |
| otherNode.visualizationState.selectedByInbound = true; |
| otherNode.visualizationState.inboundDepth = curDepth + 1; |
| } else { |
| otherNode.visualizationState.selectedByOutbound = true; |
| otherNode.visualizationState.outboundDepth = curDepth + 1; |
| } |
| nodeQueue.push(otherNode); |
| seenNodes.add(otherNode.id); |
| resultNodeSet.add(otherNode); |
| } |
| const edgeTraversedId = inboundTraversal ? |
| getEdgeIdFromNodes(otherNode.id, curNode.id) : |
| getEdgeIdFromNodes(curNode.id, otherNode.id); |
| resultEdgeSet.add(this.getEdgeById(edgeTraversedId)); |
| } |
| } |
| } |
| }; |
| |
| updateResultBFS(/* inboundTraversal */ true, inboundSeenNodes, |
| inboundNodeQueue, inboundDepth); |
| updateResultBFS(/* inboundTraversal */ false, outboundSeenNodes, |
| outboundNodeQueue, outboundDepth); |
| |
| // Special case: If inbound and outbound are both 0, both BFS will be a |
| // no-op and the edges between filtered nodes will not be included. In this |
| // case, we include those edges manually. |
| if (inboundDepth === 0 && outboundDepth === 0) { |
| for (const filterNode of resultNodeSet) { |
| for (const otherNode of filterNode.inbound) { |
| if (resultNodeSet.has(otherNode)) { |
| resultEdgeSet.add(this.getEdgeById( |
| getEdgeIdFromNodes(otherNode.id, filterNode.id))); |
| } |
| } |
| for (const otherNode of filterNode.outbound) { |
| if (resultNodeSet.has(otherNode)) { |
| resultEdgeSet.add(this.getEdgeById( |
| getEdgeIdFromNodes(filterNode.id, otherNode.id))); |
| } |
| } |
| } |
| } |
| |
| return { |
| nodes: [...resultNodeSet], |
| edges: [...resultEdgeSet], |
| }; |
| } |
| } |
| |
| export { |
| GraphNode, |
| PackageNode, |
| ClassNode, |
| GraphEdge, |
| GraphModel, |
| D3GraphData, |
| }; |