-
Notifications
You must be signed in to change notification settings - Fork 167
/
adjacency-list.ts
64 lines (55 loc) · 1.58 KB
/
adjacency-list.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
* @file Adjacency List
* @author Alexander Rose <alexander.rose@weirdbyte.de>
* @private
*/
export interface Edges {
nodeArray1: ArrayLike<number>
nodeArray2: ArrayLike<number>
edgeCount: number
nodeCount: number
}
export interface AdjacencyList {
/* number of edges for each node */
countArray: Uint8Array
/* offset into indexArray for each node */
offsetArray: Int32Array
/* edge indices, grouped by nodes */
indexArray: Int32Array
}
export function createAdjacencyList (edges: Edges): AdjacencyList {
const { edgeCount, nodeCount, nodeArray1, nodeArray2 } = edges
const countArray = new Uint8Array(nodeCount)
const offsetArray = new Int32Array(nodeCount)
// count edges per node
for (let i = 0; i < edgeCount; ++i) {
countArray[ nodeArray1[ i ] ] += 1
countArray[ nodeArray2[ i ] ] += 1
}
// get offsets to node edges
for (let i = 1; i < nodeCount; ++i) {
offsetArray[ i ] += offsetArray[ i - 1 ] + countArray[ i - 1 ]
}
// prepare index array
const bondCount2 = edgeCount * 2
const indexArray = new Int32Array(bondCount2)
for (let j = 0; j < bondCount2; ++j) {
indexArray[ j ] = -1
}
// build index array
for (let i = 0; i < edgeCount; ++i) {
const idx1 = nodeArray1[ i ]
const idx2 = nodeArray2[ i ]
let j1 = offsetArray[ idx1 ]
while (indexArray[ j1 ] !== -1 && j1 < bondCount2) {
j1 += 1
}
indexArray[ j1 ] = i
let j2 = offsetArray[ idx2 ]
while (indexArray[ j2 ] !== -1 && j2 < bondCount2) {
j2 += 1
}
indexArray[ j2 ] = i
}
return { countArray, offsetArray, indexArray }
}