# AdjacencyList The `AdjacencyList` in Atlaspack is a complex implementation of an otherwise [straightforward data structure](https://en.wikipedia.org/wiki/Adjacency_list). The core ideas behind the `AdjacencyList` are: - Any two **nodes** that are connected by an **edge** are said to be _adjacent_ - For _any_ node in the graph, every _adjacent node_ should be discoverable in _linear time_. Conceptually, this is achieved by associating each edge that is added _to or from_ a node with a previous edge that was added to or from that node. Where Atlaspack's `AdjacencyList` gets complex is in its _data layer_, which is designed for: - shared access in a multithreaded runtime - fast serialization and deserialization ## A list of lists The simplest way of thinking about `AdjacencyList` is as a _list of lists_. The primary list contains (conceptually) _node_ structs (ordered by numeric id), with each field on the struct pointing to _doubly linked lists_ of (again, conceptual) _edge_ structs that also connect to or from the same node (ordered by insertion). This looks something like: ```js // NOTE: Not a real type, just an illustration! type AdjacencyList<{ id: NodeId, incoming?: EdgeList, incomingReverse?: EdgeList, outgoing?: EdgeList, outgoingReverse?: EdgeList, }> type EdgeList<{ from: NodeId, to: NodeId, }> ```
So, given a graph like:you can imagine doubly linked lists like:
```mermaid graph TD; 0 --> |a| 1 0 --> |b| 2 1 --> |c| 2 ``` ```mermaid graph LR subgraph 0[Node 0] direction LR 0o([outgoing]) --- 0oa[[a]] <--> 0ob[[b]] --- 0or([outgoingReverse]) end subgraph 1[Node 1] direction LR 1i([incoming]) --- 1ia[[a]] --- 1ir([incomingReverse]) 1o([outgoing]) --- 1oc[[c]] --- 1or([outgoingReverse]) end subgraph 2[Node 2] direction LR 2i([incoming]) --- 2ib[[b]] <--> 2ic[[c]] --- 2ir([incomingReverse]) end ``` This makes traversal of every edge of the graph _from any node_ a straightforward process of following the links.
## SharedTypeMap Under the hood, things are less straightforward. Since Atlaspack is multi-threaded, its implementation of `AdjacencyList` features another core idea: - The data stored in the `AdjacencyList` should be accessible from multiple threads with _no overhead_ Here, _overhead_ refers to the serialization costs that add up in multi-threading scenarios. To accommodate this, `AdjacencyList` features a custom data structure called the `SharedTypeMap`: - **Shared** because it is a [`Uint32Array`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Uint32Array) backed by a [`SharedArrayBuffer`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/SharedArrayBuffer) - **Type** because each item has a `TYPE` field - **Map** because it is an implementation of a [hash map](https://en.wikipedia.org/wiki/Hash_table), using a [coalesced hashing](https://en.wikipedia.org/wiki/Coalesced_hashing) strategy This means that data being added to `SharedTypeMap` gets a pass through a hash function to produce stable key for storing and retrieving that data. ### Why _Type_, though? Two nodes in a Atlaspack graph may be related to in each other in more than one way. In order to represent multiple relationships between the same two nodes, each _edge_ that connects the nodes has a _type_. Thus, when storing data about connections between adjacent nodes, `AdjacencyList` uses the _type_ as part of the identifying information. ### Uint32Array partitions As mentioned above, to deal with collisions, `SharedTypeMap` employs a version of a coalesced hashing strategy. In this version: - A contiguous array of memory is maintained for storing the data - A portion of the array is designated as the hash table - The rest of the array is the addressable space, which is where values are stored - the hash table stores pointers into the addressable space The `SharedTypeMap` is partitioned into 3 subarrays: ```mermaid graph LR header ~~~ hashtable ~~~ items subgraph header direction LR 0[0: CAPACITY] ~~~ 1[1: COUNT] end subgraph hashtable[hash table] direction LR 2[2: hash 0] ~~~ 3[3: hash 1] ~~~ 4[4: hash 2] end subgraph items[addressable space] direction LR item1 ~~~ item2 ~~~ item3 ~~~ item4 subgraph item1[item 1] direction LR 5([5: NEXT]) ~~~ 6[6: TYPE] end subgraph item2[item 2] direction LR 7([7: NEXT]) ~~~ 8[8: TYPE] end subgraph item3[item 3] direction LR 9([9: NEXT]) ~~~ 10[10: TYPE] end subgraph item4[item 4] direction LR 11([11: NEXT]) ~~~ 12[12: TYPE] end end ``` - The _header_ partition stores metadata: - `CAPACITY`: the total number of items that can fit in the array. This is always equal to the length of the _hash table_. - `COUNT`: the number of items that are currently in the _addressable space_ partition. - The _hash table_ partition stores _addresses_, which are pointers into the _addressable space_ partition - each index represents the head of a linked list known as a _bucket_ - The _addressable space_ partition stores contiguous slices of _item data_: - `NEXT`: the _address_ of the next item with the same hash as this item; this is a _link_ in the hash _bucket_. - `TYPE`: the item's type Note that the fields described above are _inherited_ by `NodeTypeMap` and `EdgeTypeMap`. They both extend this base set with fields of their own. When there is a hash collision, the previous value is augmented with a link to the address of the colliding value. These linked lists of values that have hash collisions are known as _buckets_. ## Hash buckets: another list of lists Though `SharedTypeMap` stores data in a _hash table_, it presents an API that is more like a _linked list_. Instead of adding an item to the `SharedTypeMap` through something like an `add` method, `SharedTypeMap` has a method called `link`: ```js link(hash: THash, item: TAddress, type: TItemType): void; ``` This method pairs with `getNextAddress`: ```js getNextAddress(): TAddress ``` This is because `SharedTypeMap` is really a _base class_ implementation; its subclasses (See [NodeTypeMap](#nodetypemap) and [EdgeTypeMap](#edgetypemap)) extend this API with more map-like `add` methods. As `link` implies, each index in the hash table can be thought of as the head of a _linked list_. When an item is added to a `SharedTypeMap` (or rather, to one of its subclasses), the `getNextAddress` method is invoked to find the next location in the _addressable space_ that is unoccupied. The next address is always computed in constant time by adding the current item count (multiplied by the item size) to the offset of the first addressable space. This has the effect of storing items in the addressable space _in insertion order_. For example, here we see that hash `0` has 1 collision:
given an insertion order:imagine a list like:
``` // map.link(hash, address, type) map.link(0, map.getNextAddress(), 1) map.link(1, map.getNextAddress(), 2) map.link(2, map.getNextAddress(), 3) map.link(0, map.getNextAddress(), 1) ``` ```mermaid graph LR 2[2: hash 0] -- head --> 5([5: NEXT]) -- next --> 11([11: NEXT]) 3[3: hash 1] -- head --> 7([7: NEXT]) 4[4: hash 2] -- head --> 9([9: NEXT]) ```
Or, as raw `Uint32Array` data: | label | CAPACITY | COUNT | # | # | # | NEXT | TYPE | NEXT | TYPE | NEXT | TYPE | NEXT | TYPE | | ----- | -------- | ----- | --- | --- | --- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | value | 4 | 4 | 5 | 7 | 9 | 11 | 1 | 0 | 2 | 0 | 3 | 0 | 1 | Notice that, thanks to `getNextAddress()`, the items are stored in _insertion order_, not by type or hash! Also notice that the hashes we used to `link` are mapped to indices in the hash table (the `#` above), and that the values stored at those indices are the _addresses_ returned by `getNextAddress`. You may have also noticed that our last `link` has a _collision_ with our first `link` (they both use hash `0`). In that case, the `address` for our last `link` is stored in the `NEXT` field of the item at the `address` that is currently stored for hash `0`: ```mermaid graph LR hash0[hash 0] -- HEADER_SIZE + 0 --> index2[2] hash1[hash 1] -- HEADER_SIZE + 1 --> index3[3] hash2[hash 2] -- HEADER_SIZE + 2 --> index4[4] index2[2] -- head --> address5[5] -- next --> address11[11] index3[3] -- head --> address7[7] index4[4] -- head --> address9[9] ``` ## How AdjacencyList uses SharedTypeMap As mentioned above, `SharedTypeMap` is a _base implementation_; it isn't used directly. `AdjacencyList` uses two subclasses of `SharedTypeMap`: - `NodeTypeMap`, which is referred to internally as `nodes` - `EdgeTypeMap`, which is referred to internally as `edges` The business of `AdjacencyList` is therefore interacting with these two maps when: - **adding** edges by _linking_ records in `nodes` with records in `edges` - **deleting** edges by _unlinking_ records in `nodes` from records in `edges` - **resizing** either map when they run low on space - **traversing** edges by following the links from records in `nodes` to records in `edges` (and back) ## EdgeTypeMap The `EdgeTypeMap` extends `SharedTypeMap` with API for: - **adding** edges - **deleting** edges - **linking** adjacent edges - **unlinking** adjacent edges ### Edge hashes Edges are identified by a hash of their `to`, `from`, and `type` values. For any given set of these values, the hash function deterministically produces a number that that fits within the **current capacity** of the `EdgeTypeMap`. That hash number is then the index in the hash table where the _head_ of the linked list of edges with this hash is stored. See [Hash buckets: another list of lists](#hash-buckets-another-list-of-lists) for more. ### Edge records The `EdgeTypeMap` records can be thought of as the links in the linked lists of edges connected to or from a given node. As described in [Node records](#node-records), There is a linked list _per edge type_, and also _per direction_:
given a graph like:imagine lists like:
```mermaid graph TD; 0 --> |1| 1 0 --> |2| 1 1 --> |1| 2 0 --> |2| 2 1 --> |2| 2 ``` ```mermaid graph LR subgraph e4[edge 4] direction LR e4n1[1] -- 2 --> e4n2[2] end subgraph e3[edge 3] direction LR e3n1[1] -- 1 --> e3n2[2] end subgraph e2[edge 2] direction LR e2n0[0] -- 2 --> e2n2[2] end subgraph e1[edge 1] direction LR e1n0[0] -- 2 --> e1n1[1] end subgraph e0[edge 0] direction LR e0n0[0] -- 1 --> e0n1[1] end e1 -- next out --> e2 -- prev out --> e1 e2 -- next in --> e4 -- prev in --> e2 ``` Because edge records are only created once per unique pair of node ids and edge type, and deleted edges do not get reclaimed (without a resize and rehash of every edge, see [Resizing the `EdgeTypeMap`](#resizing-the-edgetypemap)), the maximum number of edge records that will be stored is `d + n * n * e`, where `n` is the number of nodes and `e` is the number of _unique_ edge types, and `d` is the number of deleted edges.
### Edge fields Edge records occupy **32 bytes** of contiguous space, labelled as the following **`uint32` (4 byte)** fields: - `NEXT`: The next edge record with the same hash - `TYPE`: The edge type - `FROM`: The id of the originating node - `TO`: The id of the terminating node - `NEXT_IN`: The address of the next incoming edge of the same type to the same terminating node - `PREV_IN`: The address of the previous incoming edge of the same type to the same terminating node - `NEXT_OUT`: The address of the next outgoing edge of the same type from the same originating node - `PREV_OUT`: The address of the previous outgoing edge of the same type from the same originating node #### Sizing the EdgeTypeMap The capacity of `EdgeTypeMap` is always _at least_ the total number of edges in the graph. Note that between any two nodes, there my only be one edge per unique edge type. Recalling that the `Uint32Array` is partitioned into 3 subarrays: | header | hash table | addressable space | | ------ | ---------- | ----------------- | Given a capacity of `c`: - The first 3 values in the `Uint32Array` are the header: `HEADER_SIZE = 3` - The hash table is always equal to the capacity: `c` - The addressable space is equal to the capacity times the item size: `IITEM_SIZE * c` - The item size is equal to the number of fields on an edge record: `ITEM_SIZE = 8` The size of the `Uint32Array` is therefore `3 + 9c`. #### Resizing the EdgeTypeMap The `EdgeTypeMap` is resized on demand in `addEdge`. There are two scenarios in which the `EdgeTypeMap` is resized: - if there is not enough capacity in the addressable space to accommodate an additional edge - if there are enough deletes that the capacity can be reduced and still fit the number of edges plus an additional edge. In the first case, the capacity must increase. This is accomplished by computing a next capacity from the current capacity. The next capacity follows a linear progression, starting from the `maxGrowFactor (defaulting to 8)`, and scaled inversely linearly the `minGrowFactor (defaulting to 2)` from capacity 0 to `peakCapacity`. Roughly the following formula: ```js maxGrowFactor + (minGrowFactor - maxGrowFactor) * (capacity / peakCapacity); ``` Once the `capacity` exceeds `peakCapacity`, the capacity grows by the `minGrowFactor`. In the second case, the capacity can decrease. This is accomplished by _halving_ the capacity. In both cases, after computing the next capacity, a new `EdgeTypeMap` is created with that new capacity along with a new `NodeTypeMap` that retains its current capacity. Every edge in the current `EdgeTypeMap` is then _rehashed_ and _relinked_ into the new maps. ## NodeTypeMap The `NodeTypeMap` extends `SharedTypeMap` with API for: - **adding** nodes - **linking** nodes to edges - **unlinking** nodes from edges ### Node records The `NodeTypeMap` records can be thought of as the heads of linked lists of edges connected to or from a given node. There is a linked list _per edge type_, and also _per direction_:
given a graph like:imagine lists like:
```mermaid graph TD; 0 --> |1| 1 0 --> |2| 1 1 --> |1| 2 0 --> |2| 2 ``` ```mermaid graph LR subgraph n0[node 0] et1(edge type 1) et2(edge type 2) end subgraph edges subgraph e0[edge 0] direction LR e0n0[0] -- 1 --> e0n1[1] end subgraph e1[edge 1] direction LR e1n0[0] -- 2 --> e1n1[1] end subgraph e2[edge 2] direction LR e2n0[0] -- 2 --> e2n2[2] end end et1 -- first out --> e0 et1 -- last out --> e0 et2 -- first out --> e1 et2 -- last out --> e1 e1 -- next out --> e2 e2 -- prev out --> e1 ``` ```mermaid graph LR subgraph n1[node 1] et1(edge type 1) et2(edge type 2) end subgraph edges subgraph e0[edge 0] direction LR e0n0[0] -- 1 --> e0n1[1] end subgraph e1[edge 1] direction LR e1n0[0] -- 2 --> e1n1[1] end subgraph e3[edge 3] direction LR e3n1[1] -- 1 --> e3n2[2] end end et1 -- first in --> e0 et1 -- last in --> e0 et1 -- first out --> e3 et1 -- last out --> e3 et2 -- first in --> e1 et2 -- last in --> e1 ``` ```mermaid graph LR subgraph n2[node 2] et1(edge type 1) et2(edge type 2) end subgraph edges subgraph e2[edge 2] direction LR e2n0[0] -- 2 --> e2n2[2] end subgraph e3[edge 3] direction LR e3n1[1] -- 1 --> e3n2[2] end end et1 -- first in --> e3 et1 -- last in --> e3 et2 -- first in --> e2 et2 -- last in --> e2 ``` Because node records are only created once per unique node id and edge type, the maximum number of node records that will be stored is `n * e`, where `n` is the number of nodes (the count of _node ids_ issued) and `e` is the number of _unique_ edge types in the graph.
### Node fields Node records occupy **24 bytes** of contiguous space, labelled as the following **`uint32` (4 byte)** fields: - `NEXT`: The next node record with the same node id, but a different `TYPE` - `TYPE`: The edge type for edges linked to or from the node via this record - `FIRST_IN`: The address in `EdgeTypeMap` of the first edge of this type **to** this node - `FIRST_OUT`: The address in `EdgeTypeMap `of the first edge of this type **from** this node - `LAST_IN`: The address in `EdgeTypeMap` of the last edge of this type **to** this node - `LAST_OUT`: The address in `EdgeTypeMap` of the last edge of this type **from** this node #### Sizing the NodeTypeMap As implied above, adding a node to `AdjacencyList` does not actually increment the count of nodes in the `NodeTypeMap`, it only increments the `nodeId`. This means that the number of nodes in the graph is _not the same as_ the number of node records in the `AdjacencyList`. However, the capacity of `NodeTypeMap` is always _at least_ the larger of the total number of node ids issued (`nextId`) or the number of node records in the map (`count`). The reasons that the capacity must consider both `nextId` and `count` are: - when a node is connected to an edge, the node id is used as the hash in the `NodeTypeMap`, so the hash table must have _at least_ enough capacity to fit the highest node id. - when a node is connected to edges of more than one unique type, the additional types require additional node records, which increase the `count` and may require additional addressable space (e.g., if most nodes are already connected). Recalling that the `Uint32Array` is partitioned into 3 subarrays: | header | hash table | addressable space | | ------ | ---------- | ----------------- | Given a capacity of `c`: - The first 3 values in the `Uint32Array` are the header: `HEADER_SIZE = 3` - `NEXT` and - `TYPE` have the same meaning as in `SharedTypeMap` - `NEXT_ID` tracks the number of unique node ids issued by `addNode` - The hash table is always equal to the capacity: `c` - The addressable space is equal to the capacity times the item size: `IITEM_SIZE * c` - The item size is equal to the number of fields on a node record: `ITEM_SIZE = 6` - these are the 6 fields describe in [Node fields](#node-fields) The size of the `Uint32Array` is therefore `3 + 7c`. #### Resizing the NodeTypeMap There are two scenarios in which the `NodeTypeMap` is resized: - in `addNode`, if there is not enough capacity in the hash table to accommodate the number of nodes implied by the next node id. - in `addEdge`, if the edge being added is the first of its type for either node, _and_ there is not enough capacity in the addressable space to accommodate the additional count of node records required. In either case, the resizing is accomplished by creating a new `NodeTypeMap` with double the capacity of the current one, and then copying the data in the hash table and addressable space directly into the new map. To account for the increase in the size of the hash table (remember that the size of the hash table is always equal to the capacity), all pointers into the addressable space are adjusted by the delta between the old map capacity and the new capacity, e.g., if the old capacity was 4, and now it's 8, all of the internal addresses would be shifted by 4. This works because the node ids are sequential and immutable, so no rehashing is necessary. The internal addresses can all be safely incremented by the capacity delta, while the addresses to edges, which point to the `EdgeTypMap`, don't need to change at all (as its size hasn't changed). ## What AdjacencyList really looks like
given a graph like:AdjacencyList looks like:
```mermaid graph TD; 0 --> |1| 1 0 --> |2| 1 1 --> |1| 2 0 --> |2| 2 ``` AdjacencyList looks like: ```mermaid graph LR subgraph nodes subgraph n0[node 0] na17[(type 1)] na29[(type 2)] na17 -- next --> na29 end subgraph n1[node 1] na11[(type 1)] na23[(type 2)] na11 -- next --> na23 end subgraph n2[node 2] na35[(type 2)] na41[(type 1)] na35 -- next --> na41 end end subgraph edges subgraph e0[hash 0] ea7[(type 1)] end subgraph e1[hash 1] ea15[(type 2)] end subgraph e2[hash 2] ea31[(type 1)] end subgraph e3[hash 3] ea23[(type 2)] end ea15 -- next out --> ea23 ea23 -- prev out --> ea15 end ea7 -- from --> n0 ea7 -- to --> n1 ea15 -- from --> n0 ea15 -- to --> n1 ea23 -- from --> n0 ea23 -- to --> n2 ea31 -- from --> n1 ea31 -- to --> n2 na11 -- first in --> ea7 na11 -- first out --> ea31 na11 -- last in --> ea7 na11 -- last out --> ea31 na17 -- first out --> ea7 na17 -- last out --> ea7 na23 -- first in --> ea15 na23 -- last in --> ea15 na29 -- first out --> ea15 na29 -- last out --> ea23 na35 -- first in --> ea23 na35 -- last in --> ea23 na41 -- first out --> ea31 na41 -- last out --> ea31 ``` Or, as raw `Uint32Array` data: ``` nodes: header hash table addressable space 0 1 2 3 4 5 6 7 8 9 10 11 [ 23 1 7 31 7 31 ] 8 6 3 17 11 35 0 0 0 0 0 17 [ 29 1 0 7 0 7 ] 23 [ 0 2 15 0 15 0 ] 29 [ 0 2 0 15 0 23 ] 35 [ 41 2 23 0 23 0 ] 41 [ 0 1 31 0 31 0 ] 47 [ 0 0 0 0 0 0 ] 53 [ 0 0 0 0 0 0 ] edges: header hash table addressable space 0 1 2 3 4 5 6 7 [ 0 1 0 1 0 0 0 0 ] 4 4 0 15 7 31 23 15 [ 0 2 0 1 0 0 23 0 ] 23 [ 0 2 0 2 0 0 0 15 ] 31 [ 0 1 1 2 0 0 0 0 ] ```