1/* 2 * Copyright (c) 2025 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15import { NodeID, GraphTraits } from './GraphTraits'; 16 17export { NodeID }; 18 19/** 20 * BaseImplicitGraph is an abstract class that represents an implicit graph. 21 * An implicit graph is a graph representation where node and edge information is implicitly stored using maps. 22 * This class implements the GraphTraits<Node> interface and provides basic graph operations. 23 */ 24export abstract class BaseImplicitGraph<Node> implements GraphTraits<Node> { 25 /** 26 * idToNodeMap is an optional map that maps node IDs (NodeID) to node objects (Node). 27 * If not initialized, calling related methods will throw an error. 28 */ 29 protected idToNodeMap?: Map<NodeID, Node>; 30 31 /** 32 * nodeToIdMap is a map that maps node objects (Node) to node IDs (NodeID). 33 * This map must be initialized in the subclass. 34 */ 35 protected nodeToIdMap!: Map<Node, NodeID>; 36 37 /** 38 * succMap is a map that stores the successors of each node. 39 * The key is a node ID (NodeID), and the value is an array of successor node IDs. 40 */ 41 succMap!: Map<NodeID, NodeID[]>; 42 43 /** 44 * predMap is a map that stores the predecessors of each node. 45 * The key is a node ID (NodeID), and the value is an array of predecessor node IDs. 46 */ 47 predMap!: Map<NodeID, NodeID[]>; 48 49 constructor() {} 50 51 /** 52 * Gets the number of nodes in the graph. 53 * @returns The number of nodes in the graph. 54 */ 55 public getNodeNum(): number { 56 return this.nodeToIdMap.size; 57 } 58 59 /** 60 * Returns an iterator for all nodes in the graph. 61 * @returns An iterator for traversing all nodes in the graph. 62 */ 63 public nodesItor(): IterableIterator<Node> { 64 return this.nodeToIdMap.keys(); 65 } 66 67 /** 68 * Gets the node object corresponding to a given node ID. 69 * @param id The node ID. 70 * @returns The corresponding node object. 71 * @throws Throws an error if idToNodeMap is not initialized or if the node is not found. 72 */ 73 public getNode(id: NodeID): Node { 74 if (!this.idToNodeMap) { 75 throw new Error(`initialize this.idToNodeMap first`); 76 } 77 78 if (!this.idToNodeMap.has(id)) { 79 throw new Error(`Can find Node # ${id}`); 80 } 81 82 return this.idToNodeMap.get(id)!; 83 } 84 85 public getNodeID(s: Node): NodeID { 86 if (!this.nodeToIdMap.has(s)) { 87 throw new Error(`Can find Node # ${s}`); 88 } 89 90 return this.nodeToIdMap.get(s)!; 91 } 92 93 /** 94 * Checks whether the graph contains a specific node ID. 95 * @param id The node ID. 96 * @returns Returns true if the node ID exists in the graph; otherwise, returns false. 97 * @throws Throws an error if idToNodeMap is not initialized. 98 */ 99 public hasNode(id: NodeID): boolean { 100 if (!this.idToNodeMap) { 101 throw new Error(`initialize this.idToNodeMap first`); 102 } 103 104 return this.idToNodeMap.has(id); 105 } 106 107 /** 108 * Gets the list of successor node IDs for a given node. 109 * @param id The node ID. 110 * @returns An array of successor node IDs. Returns an empty array if no successors are found. 111 */ 112 public succ(id: NodeID): NodeID[] { 113 return this.succMap.get(id) ?? []; 114 } 115 116 /** 117 * Gets the list of predecessor node IDs for a given node. 118 * @param id The node ID. 119 * @returns An array of predecessor node IDs. Returns an empty array if no predecessors are found. 120 */ 121 public pred(id: NodeID): NodeID[] { 122 return this.predMap.get(id) ?? []; 123 } 124 125 /** 126 * Gets the nodeToIdMap, which maps node objects to node IDs. 127 * @returns The nodeToIdMap. 128 */ 129 public getNodeToIdMap(): Map<Node, NodeID> { 130 return this.nodeToIdMap; 131 } 132 133 /** 134 * Abstract method to get the name of the graph. 135 * Subclasses must implement this method. 136 * @returns The name of the graph. 137 */ 138 public abstract getGraphName(): string; 139} 140