1/* 2 * Copyright (c) 2024-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 */ 15 16import { Kind, NodeID, GraphTraits } from './GraphTraits'; 17 18export { Kind, NodeID }; 19export abstract class BaseEdge { 20 private src: BaseNode; 21 private dst: BaseNode; 22 protected kind: Kind; 23 24 constructor(s: BaseNode, d: BaseNode, k: Kind) { 25 this.src = s; 26 this.dst = d; 27 this.kind = k; 28 } 29 30 public getSrcID(): NodeID { 31 return this.src.getID(); 32 } 33 34 public getDstID(): NodeID { 35 return this.dst.getID(); 36 } 37 38 public getSrcNode(): BaseNode { 39 return this.src; 40 } 41 42 public getDstNode(): BaseNode { 43 return this.dst; 44 } 45 46 public getKind(): Kind { 47 return this.kind; 48 } 49 50 public setKind(kind: Kind): void { 51 this.kind = kind; 52 } 53 54 public getEndPoints(): { src: NodeID; dst: NodeID } { 55 return { 56 src: this.src.getID(), 57 dst: this.dst.getID(), 58 }; 59 } 60 61 public getDotAttr(): string { 62 return 'color=black'; 63 } 64} 65 66export abstract class BaseNode { 67 private id: NodeID; 68 protected kind: Kind; 69 private inEdges: Set<BaseEdge> = new Set(); 70 private outEdges: Set<BaseEdge> = new Set(); 71 72 constructor(id: NodeID, k: Kind) { 73 this.id = id; 74 this.kind = k; 75 } 76 77 public getID(): NodeID { 78 return this.id; 79 } 80 81 public getKind(): Kind { 82 return this.kind; 83 } 84 85 public setKind(kind: Kind): void { 86 this.kind = kind; 87 } 88 89 public hasIncomingEdges(): boolean { 90 return this.inEdges.size !== 0; 91 } 92 93 public hasOutgoingEdges(): boolean { 94 return this.outEdges.size === 0; 95 } 96 97 public hasIncomingEdge(e: BaseEdge): boolean { 98 return this.inEdges.has(e); 99 } 100 101 public hasOutgoingEdge(e: BaseEdge): boolean { 102 return this.outEdges.has(e); 103 } 104 105 public addIncomingEdge(e: BaseEdge): void { 106 this.inEdges.add(e); 107 } 108 109 public addOutgoingEdge(e: BaseEdge): void { 110 this.outEdges.add(e); 111 } 112 113 public removeIncomingEdge(e: BaseEdge): boolean { 114 return this.inEdges.delete(e); 115 } 116 117 public removeOutgoingEdge(e: BaseEdge): boolean { 118 return this.outEdges.delete(e); 119 } 120 121 public getIncomingEdge(): Set<BaseEdge> { 122 return this.inEdges; 123 } 124 125 public getOutgoingEdges(): Set<BaseEdge> { 126 return this.outEdges; 127 } 128 129 public getDotAttr(): string { 130 return 'shape=box'; 131 } 132 133 public abstract getDotLabel(): string; 134} 135 136export abstract class BaseExplicitGraph implements GraphTraits<BaseNode> { 137 protected edgeNum: number = 0; 138 protected nodeNum: number = 0; 139 protected idToNodeMap: Map<NodeID, BaseNode>; 140 protected edgeMarkSet: Set<string>; 141 142 constructor() { 143 this.idToNodeMap = new Map(); 144 this.edgeMarkSet = new Set(); 145 } 146 147 public getNodeNum(): number { 148 return this.nodeNum; 149 } 150 151 public nodesItor(): IterableIterator<BaseNode> { 152 return this.idToNodeMap.values(); 153 } 154 155 public addNode(n: BaseNode): void { 156 this.idToNodeMap.set(n.getID(), n); 157 this.nodeNum++; 158 } 159 160 public getNode(id: NodeID): BaseNode | undefined { 161 if (!this.idToNodeMap.has(id)) { 162 throw new Error(`Can find Node # ${id}`); 163 } 164 165 return this.idToNodeMap.get(id); 166 } 167 168 public hasNode(id: NodeID): boolean { 169 return this.idToNodeMap.has(id); 170 } 171 172 public removeNode(id: NodeID): boolean { 173 if (this.idToNodeMap.delete(id)) { 174 this.nodeNum--; 175 return true; 176 } 177 return false; 178 } 179 180 public hasEdge(src: BaseNode, dst: BaseNode): boolean { 181 for (let e of src.getOutgoingEdges()) { 182 if (e.getDstNode() === dst) { 183 return true; 184 } 185 } 186 187 return false; 188 } 189 190 public ifEdgeExisting(edge: BaseEdge): boolean { 191 let edgeMark: string = `${edge.getSrcID()}-${edge.getDstID()}:${edge.getKind()}`; 192 if (this.edgeMarkSet.has(edgeMark)) { 193 return true; 194 } 195 196 this.edgeMarkSet.add(edgeMark); 197 return false; 198 } 199 200 public getNodesIter(): IterableIterator<BaseNode> { 201 return this.idToNodeMap.values(); 202 } 203 204 public abstract getGraphName(): string; 205} 206