@graphty/algorithms

Graph algorithms for the browser and Node, in TypeScript: traversal, shortest paths, centrality, community detection, clustering, flow, matching and link prediction. Every algorithm runs over a frozen graph snapshot from @graphty/graph-format -- compact typed arrays in compressed sparse row form -- and returns typed arrays indexed by node, so it runs on graphs of millions of edges without an object per node.

Installation

npm install @graphty/algorithms @graphty/graph-format

Quick Start

Build a snapshot with GraphBuilder, run an algorithm on it, and read the result. Results are typed arrays indexed by node; graph.ids maps between your node ids and the indices, and the helpers below do it for you.

import { GraphBuilder } from "@graphty/graph-format";
import { betweennessCentrality, dijkstra, groupsById, louvain, pathIds, scoresById } from "@graphty/algorithms";

const builder = new GraphBuilder({ directed: false });
builder.addEdge("alice", "bob", 1);
builder.addEdge("bob", "carol", 2);
builder.addEdge("alice", "carol", 4);
builder.addEdge("carol", "dave", 1);
const graph = builder.freeze();

// Shortest paths from one node: distances and the path to any other. A node is its index or { id }.
const paths = dijkstra(graph, { id: "alice" });
console.log(paths.dist[graph.ids.requireIndex("dave")]); // 4
console.log(pathIds(paths.pathTo({ id: "dave" }), graph)); // ["alice", "bob", "carol", "dave"]

// A score per node, keyed by id
const betweenness = scoresById(betweennessCentrality(graph), graph);
console.log(betweenness.get("carol")); // 2

// A partition, as groups of ids
const communities = groupsById(louvain(graph), graph);
console.log(communities.length > 0); // true

Every function takes the snapshot first and an options object last; a required input such as a source node sits between them (dijkstra(graph, source, options?)). Wherever a function takes a node it accepts its index or { id } (the id form is explicit because ids can be numbers), and wherever it takes a set of nodes (sampled sources, candidates, matching sides) it accepts a NodeSet: an array of indices, { mask } or { ids }. Matching's left and right still read a bare Uint32Array as a node mask, as they always have. The guide covers each family with runnable examples.

Algorithms

| Family | Functions | | ------------------------ | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | Traversal | breadthFirstSearch, directionOptimizedBfs, depthFirstSearch, topologicalSort, hasCycle, isBipartite | | Components | connectedComponents, weaklyConnectedComponents, stronglyConnectedComponents, condensation | | Shortest paths | dijkstra, bellmanFord, bidirectionalDijkstra, astar, allPairsShortestPath | | Spanning trees | kruskalMST, primMST | | Centrality | degrees, degreeCentrality, betweennessCentrality, edgeBetweennessCentrality, closenessCentrality, nodeClosenessCentrality, eigenvectorCentrality, katzCentrality, hits, pageRank, personalizedPageRank, DeltaPageRank, PriorityDeltaPageRank | | Community detection | louvain, leiden, girvanNewman, labelPropagation, labelPropagationSynchronous, labelPropagationSemiSupervised, modularity | | Clustering | kCoreDecomposition, hierarchicalClustering, markovClustering, spectralClustering, teraHAC, syncClustering, grsbm | | Flow and cuts | maxFlow, minSTCut, stoerWagner, kargerMinCut, bipartiteFlowNetwork | | Matching and isomorphism | maximumBipartiteMatching, greedyBipartiteMatching, isGraphIsomorphic, findAllIsomorphisms | | Link prediction | commonNeighborsScore, commonNeighborsPrediction, commonNeighborsForPairs, getTopCandidatesForNode, evaluateCommonNeighbors, adamicAdarScore, adamicAdarPrediction, adamicAdarForPairs, getTopAdamicAdarCandidatesForNode, evaluateAdamicAdar, compareAdamicAdarWithCommonNeighbors |

The catalog

ALGORITHMS describes every algorithm above except the two DeltaPageRank classes, keyed by export name, so an integration can register them all without keeping its own table. Each entry's fn is called as fn(graph, ...inputs, options).

import { ALGORITHMS } from "@graphty/algorithms";

const dijkstra = ALGORITHMS.dijkstra;
console.log(dijkstra.direction, dijkstra.weights); // any always
console.log(dijkstra.inputs.map((i) => `${i.name}: ${i.kind}`).join(", ")); // source: node
console.log(dijkstra.result, dijkstra.values.join(", ")); // shortest-paths dist, predArc
console.log(dijkstra.dispatch, dijkstra.accelerator); // sssp sssp

const undirectedOnly = Object.values(ALGORITHMS).filter((a) => a.direction === "undirected");
console.log(undirectedOnly.map((a) => a.name).join(", ")); // connectedComponents, kCoreDecomposition, louvain, leiden, girvanNewman, primMST

• direction: "any", "directed" or "undirected"; an algorithm throws on the other kind of graph.
• weights: "never", "always", "by-default" (read unless weighted: false) or "on-request" (read only with weighted: true).
• inputs: the positional arguments between the graph and the options, each a name and a kind ("node", "node-values", "node-labels", "seed-labels", "node-pairs", "heuristic", "graph").
• requiredOptions: options with no default, such as spectralClustering's k.
• result and values: what it returns, and the paths of its per-node (or per-edge) arrays.
• dispatch and accelerator: the accelerated(acc) method that runs it, and the AlgorithmAccelerator method that can take it over (null when it always runs on the CPU).

A test runs every algorithm to check its entry, so the catalog changes when an algorithm does.

GPU Acceleration

accelerated(accelerator) runs the same algorithms through an accelerator such as @graphty/webgpu-graph-algorithms where it implements them, and on the CPU otherwise: await accelerated(gpu).pageRank(graph). Without an accelerator (accelerated(null)) every call runs on the CPU. An accelerator's failure is thrown, never quietly retried on the CPU.

Errors

Every error an algorithm throws on purpose carries a stable code (the AlgorithmErrorCode type lists them), so a caller can react to the case without matching message text:

import { GraphBuilder } from "@graphty/graph-format";
import { connectedComponents, weaklyConnectedComponents } from "@graphty/algorithms";

const builder = new GraphBuilder({ directed: true });
builder.addEdge("a", "b");
const graph = builder.freeze();

try {
    connectedComponents(graph);
} catch (error) {
    // E_NEEDS_UNDIRECTED: the directed graph needs the weakly connected variant
    const code = (error as { code?: string }).code;
    console.log(code); // E_NEEDS_UNDIRECTED
    console.log(weaklyConnectedComponents(graph).count); // 1
}

E_NEEDS_UNDIRECTED and E_NEEDS_DIRECTED (the wrong kind of graph), E_BAD_OPTION, E_BAD_NODE (a node index out of range) and E_BAD_WEIGHT cover most of them.

Upgrading From 2.x

algorithms 3.0.0 removed the id-keyed API of 2.x: the Graph class, the functions that took it and returned Maps keyed by node id, and the CSRGraph helpers. The snapshot functions that 2.x offered as indexed.<name> are the top-level exports now, and indexed stays as a deprecated alias until 4.0. The migration guide gives the replacement for every 2.x function and lists the results that changed.

Documentation

• Guide -- every algorithm family, with runnable examples
• API reference
• Storybook -- an interactive demo of each algorithm

Development

The package lives in graphty-monorepo under algorithms/.

pnpm install              # from the monorepo root
cd algorithms
npm run build             # compile to dist/
npm run test:run          # the default test project
npm run test:browser      # the browser test project (Playwright)
npm run lint              # ESLint and the type checks, the compile-only export tests included
npm run benchmark:quick   # time every algorithm over generated graphs

Contributions are welcome as issues or pull requests on GitHub. Commits follow Conventional Commits.

License

MIT (c) Adam Powers

Related Projects

• @graphty/graph-format - The graph snapshot every algorithm takes
• @graphty/layout - Graph layout algorithms
• @graphty/graphty-element - 3D graph visualization web component