dependency_analysis/js/src/graph_model.js - chromium/src/tools/android - Git at Google

 // 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,
 };
	// 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,
	};