1import type * as Graph from "../Graph.ts"
2import { isTransforming, toImpl } from "./graph.ts"
3
4/** @internal */
5export interface Adjacency {
6 // Neighbors of compact node i occupy [rowOffsets[i], rowOffsets[i + 1]).
7 readonly rowOffsets: Uint32Array
8 // Values are compact node indices rather than public node ids.
9 readonly columnIndices: Uint32Array
10}
11
12/** @internal */
13export interface AdjacencyWithEdges extends Adjacency {
14 // Parallel to columnIndices and points into the compact edge domain.
15 readonly edgeIndices: Uint32Array
16}
17
18/** @internal */
19export interface Adjacencies {
20 readonly primary: Adjacency
21 // Present only when directed edges must be traversed without regard to direction.
22 readonly secondary: Adjacency | undefined
23}
24
25/** @internal */
26export interface EdgeEndpoints {
27 // Both arrays are parallel to compact edge data and contain compact node indices.
28 readonly sources: Uint32Array
29 readonly targets: Uint32Array
30}
31
32/** @internal */
33export interface Csr {
34 readonly type: Graph.Kind
35 // Retained as the source for projections that are materialized only when an algorithm needs them.
36 readonly graph: Graph.Graph<any, any, any> | Graph.MutableGraph<any, any, any>
37 // Parallel arrays define the compact node domain: their position is the index stored in CSR columns.
38 readonly nodeIds: Array<Graph.NodeIndex>
39 readonly nodeData: Array<any>
40 // Dense public ids already equal their compact positions, so they do not need a reverse lookup map.
41 readonly indexByNodeId: Map<Graph.NodeIndex, number> | undefined
42 // Adjacency and edge projections stay lazy because most algorithms need only one of them.
43 outgoingCsr: Adjacency | undefined
44 incomingCsr: Adjacency | undefined
45 outgoingEdgeCsr: AdjacencyWithEdges | undefined
46 // Edge data and endpoints share this insertion-order compact edge domain.
47 edgesByIndex: Array<Graph.Edge<any>> | undefined
48 edgeIdsByIndex: Array<Graph.EdgeIndex> | undefined
49 compactEdgeEndpoints: EdgeEndpoints | undefined
50 // Null marks the dense id fast path; undefined means the edge domain has not been inspected yet.
51 indexByEdgeId: Map<Graph.EdgeIndex, number> | null | undefined
52}
53
54const cache = new WeakMap<Graph.Graph<any, any, any> | Graph.MutableGraph<any, any, any>, Csr>()
55
56/** @internal */
57export const getNodeIndex = (csr: Csr, nodeId: Graph.NodeIndex): number | undefined =>
58 csr.indexByNodeId === undefined
59 ? Number.isInteger(nodeId) && nodeId >= 0 && nodeId < csr.nodeIds.length ? nodeId : undefined
60 : csr.indexByNodeId.get(nodeId)
61
62/** @internal */
63const materializeEdges = (csr: Csr): void => {
64 if (csr.edgesByIndex !== undefined) {
65 return
66 }
67 const graphEdges = toImpl(csr.graph).edges
68 const edgeIds = new Array<Graph.EdgeIndex>(graphEdges.size)
69 const edges = new Array<Graph.Edge<any>>(graphEdges.size)
70 let index = 0
71 for (const [edgeId, edge] of graphEdges) {
72 edgeIds[index] = edgeId
73 edges[index++] = edge
74 }
75 csr.edgeIdsByIndex = edgeIds
76 csr.edgesByIndex = edges
77}
78
79/** @internal */
80export const getEdges = (csr: Csr): Array<Graph.Edge<any>> => {
81 materializeEdges(csr)
82 return csr.edgesByIndex!
83}
84
85/** @internal */
86export const getEdgeIds = (csr: Csr): Array<Graph.EdgeIndex> => {
87 materializeEdges(csr)
88 return csr.edgeIdsByIndex!
89}
90
91const makeAdjacency = (csr: Csr, incoming: boolean): Adjacency => {
92 const impl = toImpl(csr.graph)
93 const adjacencyMap = incoming ? impl.reverseAdjacency : impl.adjacency
94 // The first pass allocates exact row ranges; the second preserves canonical adjacency order within each row.
95 const rowOffsets = new Uint32Array(csr.nodeIds.length + 1)
96 for (let i = 0; i < csr.nodeIds.length; i++) {
97 rowOffsets[i + 1] = rowOffsets[i] + (adjacencyMap.get(csr.nodeIds[i])?.length ?? 0)
98 }
99
100 const columnIndices = new Uint32Array(rowOffsets[csr.nodeIds.length])
101 for (let i = 0; i < csr.nodeIds.length; i++) {
102 const nodeId = csr.nodeIds[i]
103 const adjacency = adjacencyMap.get(nodeId)
104 if (adjacency === undefined) {
105 continue
106 }
107
108 let offset = rowOffsets[i]
109 for (let j = 0; j < adjacency.length; j++) {
110 const edge = impl.edges.get(adjacency[j])!
111 const neighbor = csr.type === "undirected"
112 ? edge.source === nodeId ? edge.target : edge.source
113 : incoming
114 ? edge.source
115 : edge.target
116 columnIndices[offset++] = csr.indexByNodeId === undefined ? neighbor : csr.indexByNodeId.get(neighbor)!
117 }
118 }
119 return { rowOffsets, columnIndices }
120}
121
122/** @internal */
123export const getOutgoing = (csr: Csr): Adjacency => {
124 return csr.outgoingCsr ?? (csr.outgoingCsr = makeAdjacency(csr, false))
125}
126
127/** @internal */
128export const getIncoming = (csr: Csr): Adjacency => {
129 return csr.incomingCsr ?? (csr.incomingCsr = makeAdjacency(csr, true))
130}
131
132/** @internal */
133export const getOutgoingWithEdges = (csr: Csr): AdjacencyWithEdges => {
134 if (csr.outgoingEdgeCsr !== undefined) {
135 return csr.outgoingEdgeCsr
136 }
137
138 const impl = toImpl(csr.graph)
139 if (csr.indexByEdgeId === undefined) {
140 // Avoid a map lookup per adjacency entry when edge ids already match insertion-order positions.
141 let compactEdgeIds = true
142 let position = 0
143 for (const edgeId of impl.edges.keys()) {
144 if (edgeId !== position++) {
145 compactEdgeIds = false
146 break
147 }
148 }
149 if (compactEdgeIds) {
150 csr.indexByEdgeId = null
151 } else {
152 csr.indexByEdgeId = new Map()
153 position = 0
154 for (const edgeId of impl.edges.keys()) {
155 csr.indexByEdgeId.set(edgeId, position++)
156 }
157 }
158 }
159
160 const outgoing = getOutgoing(csr)
161 // Each slot identifies the edge responsible for the neighbor in the matching columnIndices slot.
162 const edgeIndices = new Uint32Array(outgoing.columnIndices.length)
163 let position = 0
164 for (const nodeId of csr.nodeIds) {
165 const adjacency = impl.adjacency.get(nodeId)
166 if (adjacency === undefined) {
167 continue
168 }
169
170 for (const edgeId of adjacency) {
171 edgeIndices[position++] = csr.indexByEdgeId === null ? edgeId : csr.indexByEdgeId.get(edgeId)!
172 }
173 }
174
175 return csr.outgoingEdgeCsr = { ...outgoing, edgeIndices }
176}
177
178/** @internal */
179export const getAdjacencies = (
180 csr: Csr,
181 direction: Graph.TraversalDirection
182): Adjacencies => {
183 if (csr.type === "directed" && direction === "incoming") {
184 return { primary: getIncoming(csr), secondary: undefined }
185 }
186
187 if (csr.type === "directed" && direction === "undirected") {
188 // A directed graph needs both matrices to ignore direction; undirected rows already contain both endpoints.
189 return { primary: getOutgoing(csr), secondary: getIncoming(csr) }
190 }
191
192 return { primary: getOutgoing(csr), secondary: undefined }
193}
194
195/** @internal */
196export const getEdgeEndpoints = (csr: Csr): EdgeEndpoints => {
197 if (csr.compactEdgeEndpoints !== undefined) {
198 return csr.compactEdgeEndpoints
199 }
200
201 const edges = getEdges(csr)
202 const sources = new Uint32Array(edges.length)
203 const targets = new Uint32Array(edges.length)
204 for (let i = 0; i < edges.length; i++) {
205 sources[i] = csr.indexByNodeId === undefined ? edges[i].source : csr.indexByNodeId.get(edges[i].source)!
206 targets[i] = csr.indexByNodeId === undefined ? edges[i].target : csr.indexByNodeId.get(edges[i].target)!
207 }
208
209 return csr.compactEdgeEndpoints = { sources, targets }
210}
211
212/** @internal */
213export const peek = <N, E, T extends Graph.Kind>(
214 graph: Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T>
215): Csr | undefined => cache.get(graph)
216
217/** @internal */
218export const invalidate = <N, E, T extends Graph.Kind>(
219 graph: Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T>
220): void => {
221 // Existing iterators retain their Csr object; only subsequent lookups rebuild from the mutated graph.
222 cache.delete(graph)
223}
224
225/** @internal */
226export const get = <N, E, T extends Graph.Kind>(
227 graph: Graph.Graph<N, E, T> | Graph.MutableGraph<N, E, T>
228): Csr => {
229 const cacheEnabled = !isTransforming(graph)
230 if (cacheEnabled) {
231 const cached = cache.get(graph)
232 if (cached !== undefined) {
233 return cached
234 }
235 }
236
237 // Node ids and data are captured together so an iterator never consults mutable maps after it starts.
238 const impl = toImpl(graph)
239 const nodeIds = new Array<Graph.NodeIndex>(impl.nodes.size)
240 const nodeData = new Array<any>(impl.nodes.size)
241 let compactNodeIds = true
242 let nodePosition = 0
243 for (const [nodeId, data] of impl.nodes) {
244 nodeIds[nodePosition] = nodeId
245 nodeData[nodePosition] = data
246 if (nodeId !== nodePosition) {
247 compactNodeIds = false
248 }
249 nodePosition++
250 }
251
252 const indexByNodeId = compactNodeIds ? undefined : new Map<Graph.NodeIndex, number>()
253 if (indexByNodeId !== undefined) {
254 for (let i = 0; i < nodeIds.length; i++) {
255 indexByNodeId.set(nodeIds[i], i)
256 }
257 }
258
259 const result: Csr = {
260 type: impl.type,
261 graph,
262 nodeIds,
263 nodeData,
264 indexByNodeId,
265 outgoingCsr: undefined,
266 incomingCsr: undefined,
267 outgoingEdgeCsr: undefined,
268 edgesByIndex: undefined,
269 edgeIdsByIndex: undefined,
270 compactEdgeEndpoints: undefined,
271 indexByEdgeId: undefined
272 }
273
274 if (cacheEnabled) {
275 cache.set(graph, result)
276 }
277
278 return result
279}