!@thi.ng/adjacency

!npm downloads

> [!NOTE]
> This is one of 214 standalone projects, maintained as part
> of the @thi.ng/umbrella monorepo
> and anti-framework.
>
> 🚀 Please help me to work full-time on these projects by sponsoring me on
> GitHub. Thank you! ❤️

- About
- Graph implementations
- Traversals
- Status
- Related packages
- Installation
- Dependencies
- Usage examples
- API
- Basic usage
- Authors
- License

About

Sparse & bitwise adjacency matrices, lists and selected traversal algorithms for directed & undirected graphs.

> [!IMPORTANT]
> In July 2024 this package was restructured and split-up to extract some
> features into smaller more focused packages:
>
> - @thi.ng/disjoint-set

$3

The following types all implement the IGraph
interface and
support both directed & undirected graphs:

- AdjacencyBitMatrix (bit matrix based)
- AdjacencyMatrix (sparse matrix based)
- AdjacencyList

$3

- Breadth-First Search
- Depth-First Search
- Floyd-Warshall (global shortest paths search)
- Minimum Spanning Tree

Status

STABLE - used in production

Search or submit any issues for this package

Related packages

- @thi.ng/dgraph - Type-agnostic directed acyclic graph (DAG) & graph operations

Installation

``bash
yarn add @thi.ng/adjacency
`

ESM import:

`ts
import * as adj from "@thi.ng/adjacency";
`

Browser ESM import:

`html

`

JSDelivr documentation

For Node.js REPL:

`js
const adj = await import("@thi.ng/adjacency");
`

Package sizes (brotli'd, pre-treeshake): ESM: 2.53 KB

Dependencies

- @thi.ng/api
- @thi.ng/arrays
- @thi.ng/bitfield
- @thi.ng/dcons
- @thi.ng/disjoint-set
- @thi.ng/errors
- @thi.ng/sparse

Note: @thi.ng/api is in _most_ cases a type-only import (not used at runtime)

Usage examples

One project in this repo's
/examples
directory is using this package:

| Screenshot | Description | Live demo | Source |
|:------------------------------------------------------------------------------------------------------------------------|:---------------------------------------------------------------------------------|:-------------------------------------------------------|:------------------------------------------------------------------------------------|
| | Poisson-disk shape-aware sampling, Voronoi & Minimum Spanning Tree visualization | Demo | Source |

API

Generated API docs

TODO

$3

`ts tangle:export/readme.ts
import { defAdjBitMatrix, type Edge } from "@thi.ng/adjacency";

// relationships
const rels = {
a: ["b", "c"],
b: ["d"],
c: ["d", "e"],
e: ["a", "d", "b"],
};

// form set of unique node IDs
const nodeIDs = [
...new Set(Object.entries(rels).flatMap(([id, rels]) => [id, ...rels])),
];

// the current adjacency matrix impls only support numeric node IDs
// therefore, we first map node names to numeric IDs
const index = new Map(nodeIDs.map((id, i) => [id, i]));

// transform relationships into sequence of edges (aka [from,to] tuples)
const edges = Object.entries(rels).flatMap(([id, rels]) =>
rels.map((x) => [index.get(id), index.get(x)])
);

// build adjacency matrix, treat as undirected graph
// edges can also be added/removed later
const graph = defAdjBitMatrix(nodeIDs.length, edges, true);

// graph queries
console.log("edges:", graph.numEdges(), "verts:", graph.numVertices());
// edges: 8 verts: 5

// check if vertex/node is present in graph
// (this is implementation specific and for the bitmatrix backed version here
// only true if the vertex has at least 1 edge...)
console.log(graph.hasVertex(index.get("d")!));
// true

// are a and d connected?
console.log(graph.hasEdge(index.get("a")!, index.get("d")!));
// false

// number of connected nodes for a
// (in directed graphs, there's also possibility to distinguish between in/out/inout)
console.log(graph.degree(index.get("a")!));
// 3

// neighbors of a (with reverse lookup of node names)
console.log(graph.neighbors(index.get("a")!).map((x) => nodeIDs[x]));
// [ 'b', 'c', 'e' ]

// serialize to GraphViz DOT format (see result visualization below)
console.log(graph.toDot(nodeIDs));
// graph g {
// "d"--"e";
// "c"--"d";
// "c"--"e";
// "b"--"d";
// "b"--"e";
// "a"--"b";
// "a"--"c";
// "a"--"e";
// }

// resize to new capacity & add add/remove vertices/edges
graph.resize(10);

graph.addEdge(4, 5);
graph.removeEdge(0, 1);
`

GraphViz visualization of the above example graph:

!example graph

Authors

- Karsten Schmidt (Main author)
- Igor Loskutov

If this project contributes to an academic publication, please cite it as:

`bibtex
@misc{thing-adjacency,
title = "@thi.ng/adjacency",
author = "Karsten Schmidt and others",
note = "https://thi.ng/adjacency",
year = 2018
}
``

License

© 2018 - 2026 Karsten Schmidt // Apache License 2.0