@graphty/algorithms

v1.2.0

Published

4 months ago

Graph algorithms library for browser environments implemented in TypeScript

0High
0Medium
0Low

graph algorithms typescript browser graph-theory network-analysis centrality community-detection shortest-path graph-traversal

@graphty/algorithms

A comprehensive TypeScript graph algorithms library with 100+ algorithms optimized for browser environments and visualization applications.

Features

TypeScript-first: Full type safety with comprehensive type definitions
Browser-optimized: Designed to run efficiently in web browsers
Modular: Import only the algorithms you need
Comprehensive: 100+ graph algorithms including traversal, shortest paths, centrality, clustering, flow, matching, link prediction, and more
Well-tested: Extensive test suite with high coverage
Standards-compliant: Follows conventional commits and semantic versioning

Installation

npm install @graphty/algorithms

Quick Start

import { Graph, breadthFirstSearch, dijkstra } from '@graphty/algorithms';

// Create a new graph
const graph = new Graph();

// Add nodes and edges
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addEdge('A', 'B', 1); // source, target, weight
graph.addEdge('B', 'C', 2);

// Basic graph operations
console.log(graph.nodeCount); // 3
console.log(graph.totalEdgeCount); // 2
console.log(graph.hasEdge('A', 'B')); // true

// Run algorithms
const traversal = breadthFirstSearch(graph, 'A');
console.log(traversal.order); // ['A', 'B', 'C']

const shortestPaths = dijkstra(graph, 'A');
// Get distance to C
const pathToC = shortestPaths.get('C');
console.log(pathToC?.distance); // 3

API Reference

Graph Class

The core data structure for representing graphs.

class Graph {
  constructor(config?: Partial<GraphConfig>)
}

Configuration Options

interface GraphConfig {
  directed: boolean;         // Default: false
  allowSelfLoops: boolean;   // Default: false
  allowParallelEdges: boolean; // Default: false
}

Node Operations

// Add a node with optional data
graph.addNode(id: NodeId, data?: Record<string, unknown>): void

// Remove a node and all its edges
graph.removeNode(id: NodeId): boolean

// Check if a node exists
graph.hasNode(id: NodeId): boolean

// Get node details
graph.getNode(id: NodeId): Node | undefined

// Get all nodes
graph.nodes(): IterableIterator<Node>

Edge Operations

// Add an edge with optional weight and data
graph.addEdge(
  source: NodeId, 
  target: NodeId, 
  weight?: number, 
  data?: Record<string, unknown>
): void

// Remove an edge
graph.removeEdge(source: NodeId, target: NodeId): boolean

// Check if an edge exists
graph.hasEdge(source: NodeId, target: NodeId): boolean

// Get edge details
graph.getEdge(source: NodeId, target: NodeId): Edge | undefined

// Get all edges
graph.edges(): IterableIterator<Edge>

Graph Properties

// Number of nodes
graph.nodeCount: number

// Total number of edges (counts both directions for undirected)
graph.totalEdgeCount: number

// Number of unique edges
graph.uniqueEdgeCount: number

// Check if graph is directed
graph.isDirected: boolean

Degree Operations

// Total degree (in + out for directed)
graph.degree(nodeId: NodeId): number

// In-degree (directed graphs only)
graph.inDegree(nodeId: NodeId): number

// Out-degree
graph.outDegree(nodeId: NodeId): number

Neighbor Operations

// Get neighboring nodes
graph.neighbors(nodeId: NodeId): IterableIterator<NodeId>

// Get incoming neighbors (directed graphs)
graph.inNeighbors(nodeId: NodeId): IterableIterator<NodeId>

// Get outgoing neighbors
graph.outNeighbors(nodeId: NodeId): IterableIterator<NodeId>

Utility Methods

// Create a deep copy
graph.clone(): Graph

// Clear all nodes and edges
graph.clear(): void

Traversal Algorithms

Breadth-First Search (BFS)

import { breadthFirstSearch, shortestPathBFS, singleSourceShortestPathBFS, isBipartite } from '@graphty/algorithms';

// Basic BFS traversal
const result = breadthFirstSearch(graph, startNode, {
  maxDepth?: number,     // Optional: limit traversal depth
  visitCallback?: (node: NodeId, depth: number) => void
});
// Returns: TraversalResult { visited: Set<NodeId>, order: NodeId[], tree?: Map<NodeId, NodeId> }

// Find shortest path between two nodes (unweighted)
const path = shortestPathBFS(graph, source, target);
// Returns: NodeId[] | null

// Find all shortest paths from a source
const paths = singleSourceShortestPathBFS(graph, source);
// Returns: Map<NodeId, NodeId[]>

// Check if graph is bipartite
const bipartite = isBipartite(graph);
// Returns: { isBipartite: boolean, coloring?: Map<NodeId, number> }

Depth-First Search (DFS)

import { depthFirstSearch, topologicalSort, hasCycleDFS, findStronglyConnectedComponents } from '@graphty/algorithms';

// Basic DFS traversal
const result = depthFirstSearch(graph, startNode, {
  previsitCallback?: (node: NodeId) => void,
  postvisitCallback?: (node: NodeId) => void
});
// Returns: TraversalResult

// Topological sort (for DAGs)
const sorted = topologicalSort(graph);
// Returns: NodeId[] | null (null if cycle detected)

// Cycle detection
const hasCycle = hasCycleDFS(graph);
// Returns: boolean

// Find strongly connected components using DFS
const sccs = findStronglyConnectedComponents(graph);
// Returns: NodeId[][]

Shortest Path Algorithms

Dijkstra's Algorithm

import { dijkstra, dijkstraPath, singleSourceShortestPath, allPairsShortestPath } from '@graphty/algorithms';

// Single-source shortest paths
const result = dijkstra(graph, source, {
  target?: NodeId        // Optional: stop when target is reached
});
// Returns: Map<NodeId, ShortestPathResult>
// ShortestPathResult = { distance: number, path: NodeId[], predecessor: Map<NodeId, NodeId | null> }

// Get specific path
const path = dijkstraPath(graph, source, target);
// Returns: ShortestPathResult | null

// All shortest paths from source
const paths = singleSourceShortestPath(graph, source);
// Returns: Map<NodeId, ShortestPathResult>

// All pairs shortest paths
const allPairs = allPairsShortestPath(graph);
// Returns: Map<NodeId, Map<NodeId, ShortestPathResult>>

Bellman-Ford Algorithm

import { bellmanFord, bellmanFordPath, hasNegativeCycle } from '@graphty/algorithms';

// Single-source shortest paths (handles negative weights)
const result = bellmanFord(graph, source);
// Returns: BellmanFordResult { 
//   distances: Map<NodeId, number>, 
//   predecessors: Map<NodeId, NodeId | null>,
//   hasNegativeCycle: boolean,
//   negativeCycleNodes?: Set<NodeId>
// }

// Get specific path
const path = bellmanFordPath(graph, source, target);
// Returns: ShortestPathResult | null

// Check for negative cycles
const result = hasNegativeCycle(graph);
// Returns: BellmanFordResult with hasNegativeCycle boolean

Floyd-Warshall Algorithm

import { floydWarshall, floydWarshallPath, transitiveClosure } from '@graphty/algorithms';

// All pairs shortest paths
const result = floydWarshall(graph);
// Returns: { distances: Map<NodeId, Map<NodeId, number>>, next: Map<NodeId, Map<NodeId, NodeId | null>> }

// Get specific path between any pair
const path = floydWarshallPath(result, source, target);
// Returns: NodeId[] | null

// Compute transitive closure
const closure = transitiveClosure(graph);
// Returns: Map<NodeId, Set<NodeId>>

Centrality Algorithms

Degree Centrality

import { degreeCentrality, nodeDegreeCentrality } from '@graphty/algorithms';

// Calculate for all nodes
const centralities = degreeCentrality(graph, {
  normalized?: boolean,   // Default: false
  weight?: string        // Optional: edge property for weighted degree
});
// Returns: CentralityResult (Record<string, number>)

// Calculate for single node
const centrality = nodeDegreeCentrality(graph, nodeId, { normalized?: boolean });
// Returns: number

Betweenness Centrality

import { betweennessCentrality, nodeBetweennessCentrality, edgeBetweennessCentrality } from '@graphty/algorithms';

// Node betweenness for all nodes
const centralities = betweennessCentrality(graph, {
  normalized?: boolean,   // Default: false
  weight?: string,       // Optional: use weighted shortest paths
  endpoints?: boolean    // Default: false, include endpoints in paths
});
// Returns: CentralityResult (Record<string, number>)

// Single node betweenness
const centrality = nodeBetweennessCentrality(graph, nodeId, options);
// Returns: number

// Edge betweenness
const edgeCentralities = edgeBetweennessCentrality(graph, options);
// Returns: Map<string, number> (edge ID to centrality)

Closeness Centrality

import { closenessCentrality, nodeClosenessCentrality, weightedClosenessCentrality } from '@graphty/algorithms';

// Closeness for all nodes
const centralities = closenessCentrality(graph, {
  normalized?: boolean    // Default: false
});
// Returns: CentralityResult (Record<string, number>)

// Single node closeness
const centrality = nodeClosenessCentrality(graph, nodeId, { normalized?: boolean });
// Returns: number

// Weighted closeness
const centralities = weightedClosenessCentrality(graph, {
  normalized?: boolean,
  weight?: string        // Edge property for weights
});
// Returns: CentralityResult (Record<string, number>)

PageRank

import { pageRank, personalizedPageRank, topPageRankNodes } from '@graphty/algorithms';

// Standard PageRank
const result = pageRank(graph, {
  dampingFactor?: number,    // Default: 0.85
  maxIterations?: number,    // Default: 100
  tolerance?: number,        // Default: 1e-6
  initialRanks?: Record<string, number>,
  personalization?: Record<string, number>
});
// Returns: { ranks: Record<string, number>, iterations: number, converged: boolean }

// Personalized PageRank (with bias)
const ranks = personalizedPageRank(graph, personalization, options);
// personalization: Map<NodeId, number> - restart probabilities
// Returns: CentralityResult (Record<string, number>)

// Get top N nodes by PageRank
const topNodes = topPageRankNodes(graph, n, options);
// Returns: Array<{ node: NodeId, rank: number }>

Eigenvector Centrality

import { eigenvectorCentrality, nodeEigenvectorCentrality } from '@graphty/algorithms';

// Calculate eigenvector centrality for all nodes
const centralities = eigenvectorCentrality(graph, {
  maxIterations?: number,    // Default: 100
  tolerance?: number         // Default: 1e-6
});
// Returns: CentralityResult (Record<string, number>)

// Single node eigenvector centrality
const centrality = nodeEigenvectorCentrality(graph, nodeId, options);
// Returns: number

Katz Centrality

import { katzCentrality, nodeKatzCentrality } from '@graphty/algorithms';

// Calculate Katz centrality for all nodes
const centralities = katzCentrality(graph, {
  alpha?: number,           // Attenuation factor (default: 0.1)
  beta?: number,            // Weight for direct connections (default: 1.0)
  maxIterations?: number,   // Default: 100
  tolerance?: number,       // Default: 1e-6
  normalized?: boolean      // Default: true
});
// Returns: CentralityResult (Record<string, number>)

// Single node Katz centrality
const centrality = nodeKatzCentrality(graph, nodeId, options);
// Returns: number

HITS Algorithm

import { hits, nodeHITS } from '@graphty/algorithms';

// Calculate hub and authority scores
const result = hits(graph, {
  maxIterations?: number,   // Default: 100
  tolerance?: number        // Default: 1e-6
});
// Returns: HITSResult { hubs: CentralityResult, authorities: CentralityResult }

// Single node HITS scores
const scores = nodeHITS(graph, nodeId, options);
// Returns: { hub: number, authority: number }

Connected Components

Basic Component Operations

import { 
  connectedComponents, 
  isConnected, 
  numberOfConnectedComponents,
  largestConnectedComponent,
  getConnectedComponent 
} from '@graphty/algorithms';

// Find all components
const components = connectedComponents(graph);
// Returns: NodeId[][] (array of component arrays)

// Check if graph is connected
const connected = isConnected(graph);
// Returns: boolean

// Count components
const count = numberOfConnectedComponents(graph);
// Returns: number

// Get largest component
const largest = largestConnectedComponent(graph);
// Returns: NodeId[]

// Get component containing a specific node
const component = getConnectedComponent(graph, nodeId);
// Returns: Set<NodeId>

Strongly Connected Components

import { 
  stronglyConnectedComponents,
  findStronglyConnectedComponents,
  isStronglyConnected,
  condensationGraph 
} from '@graphty/algorithms';

// Find SCCs using Tarjan's algorithm
const sccs = stronglyConnectedComponents(graph);
// Returns: ComponentResult

// Alternative: using DFS
const sccs = findStronglyConnectedComponents(graph);
// Returns: NodeId[][]

// Check if directed graph is strongly connected
const stronglyConnected = isStronglyConnected(graph);
// Returns: boolean

// Create condensation graph (DAG of SCCs)
const condensation = condensationGraph(graph);
// Returns: { graph: Graph, componentMap: Map<NodeId, number> }

// Alternative DFS-based connected components
const components = connectedComponentsDFS(graph);
// Returns: ComponentResult

Weakly Connected Components

import { weaklyConnectedComponents, isWeaklyConnected } from '@graphty/algorithms';

// Find WCCs (ignoring edge direction)
const wccs = weaklyConnectedComponents(graph);
// Returns: ComponentResult

// Check if directed graph is weakly connected
const weaklyConnected = isWeaklyConnected(graph);
// Returns: boolean

Data Structures

Priority Queue

Min-heap implementation used internally by algorithms.

import { PriorityQueue } from '@graphty/algorithms';

const pq = new PriorityQueue<T>((a, b) => a.priority - b.priority);

pq.enqueue(item);
pq.dequeue();
pq.peek();
pq.isEmpty();
pq.size;
pq.clear();

Union-Find (Disjoint Set)

Efficient data structure for tracking connected components.

import { UnionFind } from '@graphty/algorithms';

const uf = new UnionFind<T>();

uf.makeSet(item);
uf.find(item);
uf.union(item1, item2);
uf.connected(item1, item2);
uf.getSetSize(item);
uf.numberOfSets;

Minimum Spanning Tree Algorithms

Kruskal's Algorithm

import { kruskalMST, minimumSpanningTree } from '@graphty/algorithms';

// Find MST using Kruskal's algorithm
const mst = kruskalMST(graph);
// Returns: { edges: Edge[], weight: number }

// Alternative alias
const mst = minimumSpanningTree(graph);

Prim's Algorithm

import { primMST } from '@graphty/algorithms';

// Find MST using Prim's algorithm
const mst = primMST(graph, startNode?);
// Returns: { edges: Edge[], weight: number }

Community Detection Algorithms

Louvain Method

import { louvain } from '@graphty/algorithms';

// Detect communities using Louvain method
const communities = louvain(graph, {
  resolution?: number,      // Default: 1.0
  randomSeed?: number
});
// Returns: { communities: Map<NodeId, number>, modularity: number }

Leiden Algorithm

import { leiden } from '@graphty/algorithms';

// Improved community detection
const communities = leiden(graph, {
  resolution?: number,      // Default: 1.0
  iterations?: number,      // Default: 10
  randomSeed?: number
});
// Returns: { communities: Map<NodeId, number>, modularity: number }

Label Propagation

import { labelPropagation, labelPropagationAsync, labelPropagationSemiSupervised } from '@graphty/algorithms';

// Basic label propagation
const labels = labelPropagation(graph, {
  maxIterations?: number    // Default: 100
});
// Returns: Map<NodeId, number>

// Asynchronous version
const labels = labelPropagationAsync(graph, options);

// Semi-supervised with seed communities
const labels = labelPropagationSemiSupervised(graph, seedLabels, options);

Girvan-Newman Algorithm

import { girvanNewman } from '@graphty/algorithms';

// Edge betweenness based community detection
const dendrogram = girvanNewman(graph, {
  targetCommunities?: number  // Stop at this many communities
});
// Returns: { levels: Array<{ modularity: number, communities: NodeId[][] }> }

Pathfinding Algorithms

A* Algorithm

import { astar, astarWithDetails, heuristics } from '@graphty/algorithms';

// A* pathfinding with heuristic
const path = astar(graph, start, goal, {
  heuristic: heuristics.euclidean,  // or manhattan, chebyshev, zero
  weight?: (edge: Edge) => number
});
// Returns: { path: NodeId[], cost: number } | null

// A* with search details
const result = astarWithDetails(graph, start, goal, options);
// Returns: { path: NodeId[], cost: number, explored: Set<NodeId>, parent: Map<NodeId, NodeId> } | null

Flow Algorithms

Maximum Flow

import { fordFulkerson, edmondsKarp } from '@graphty/algorithms';

// Ford-Fulkerson using DFS
const flow = fordFulkerson(graph, source, sink, {
  capacityKey?: string      // Edge property for capacity
});
// Returns: { maxFlow: number, flowGraph: Map<NodeId, Map<NodeId, number>> }

// Edmonds-Karp using BFS (better complexity)
const flow = edmondsKarp(graph, source, sink, options);

// Create bipartite flow network
const flowNetwork = createBipartiteFlowNetwork(leftNodes, rightNodes, edges, capacities?);
// Returns: FlowNetwork

Minimum Cut

import { minSTCut, stoerWagner, kargerMinCut } from '@graphty/algorithms';

// Min s-t cut using max flow
const cut = minSTCut(graph, source, sink);
// Returns: { cutValue: number, sourcePartition: Set<NodeId>, sinkPartition: Set<NodeId> }

// Global minimum cut (Stoer-Wagner)
const cut = stoerWagner(graph);
// Returns: { cutValue: number, partition1: Set<NodeId>, partition2: Set<NodeId> }

// Randomized min cut (Karger)
const cut = kargerMinCut(graph, iterations?);
// Returns: { cutValue: number, partition1: Set<NodeId>, partition2: Set<NodeId> }

Clustering Algorithms

Hierarchical Clustering

import { hierarchicalClustering, cutDendrogram, cutDendrogramKClusters } from '@graphty/algorithms';

// Agglomerative clustering
const result = hierarchicalClustering(graph, linkage);
// graph: Map<NodeId, Set<NodeId>>
// linkage: 'single' | 'complete' | 'average' | 'ward' (default: 'single')
// Returns: HierarchicalClusteringResult { root: ClusterNode, dendrogram: ClusterNode[], clusters: Map<number, Set<NodeId>[]> }

// Cut at specific height
const clusters = cutDendrogram(result.root, height);
// Returns: Set<NodeId>[]

// Get exactly k clusters
const clusters = cutDendrogramKClusters(result.root, k);
// Returns: Set<NodeId>[]

K-Core Decomposition

import { kCoreDecomposition, getKCore, kTruss, degeneracyOrdering } from '@graphty/algorithms';

// Find all k-cores
const result = kCoreDecomposition(graph);
// graph: Map<NodeId, Set<NodeId>>
// Returns: KCoreResult { cores: Map<number, Set<NodeId>>, coreness: Map<NodeId, number>, maxCore: number }

// Extract specific k-core subgraph
const kCore = getKCore(graph, k);
// Returns: Set<NodeId>

// Find k-truss (triangular cores)
const truss = kTruss(graph, k);
// Returns: Set<string> (edge strings)

// Degeneracy ordering
const ordering = degeneracyOrdering(graph);
// Returns: NodeId[]

Spectral Clustering

import { spectralClustering } from '@graphty/algorithms';

// Spectral clustering using graph Laplacian
const result = spectralClustering(graph, {
  k: number,                // Number of clusters
  laplacianType?: 'unnormalized' | 'normalized' | 'randomWalk',  // Default: 'normalized'
  maxIterations?: number,   // Default: 100
  tolerance?: number        // Default: 1e-4
});
// Returns: SpectralClusteringResult { communities: NodeId[][], clusterAssignments: Map<NodeId, number> }

Markov Clustering (MCL)

import { markovClustering } from '@graphty/algorithms';

// MCL algorithm for network clustering
const result = markovClustering(graph, {
  expansion?: number,       // Expansion parameter (default: 2)
  inflation?: number,       // Inflation parameter (default: 2)
  maxIterations?: number,   // Default: 100
  tolerance?: number        // Default: 1e-6
});
// Returns: MCLResult { communities: NodeId[][], attractors: Set<NodeId>, iterations: number, converged: boolean }

Matching Algorithms

Bipartite Matching

import { maximumBipartiteMatching, greedyBipartiteMatching, bipartitePartition } from '@graphty/algorithms';

// Maximum bipartite matching (Hungarian algorithm)
const matching = maximumBipartiteMatching(graph, {
  leftNodes?: Set<NodeId>,   // Optional: specify left partition
  rightNodes?: Set<NodeId>,  // Optional: specify right partition
});
// Returns: BipartiteMatchingResult { matching: Map<NodeId, NodeId>, size: number }

// Greedy bipartite matching (faster, approximate)
const matching = greedyBipartiteMatching(graph, options);

// Partition graph into bipartite sets
const partition = bipartitePartition(graph);
// Returns: { left: Set<NodeId>, right: Set<NodeId> } | null

Graph Isomorphism

import { isGraphIsomorphic, findAllIsomorphisms } from '@graphty/algorithms';

// Check if two graphs are isomorphic
const result = isGraphIsomorphic(graph1, graph2, {
  nodeMatch?: (node1: NodeId, node2: NodeId, g1: Graph, g2: Graph) => boolean,
  edgeMatch?: (edge1: [NodeId, NodeId], edge2: [NodeId, NodeId], g1: Graph, g2: Graph) => boolean,
  findAllMappings?: boolean     // Find all possible isomorphisms
});
// Returns: IsomorphismResult { isIsomorphic: boolean, mapping?: Map<NodeId, NodeId> }

// Find all isomorphism mappings
const mappings = findAllIsomorphisms(graph1, graph2, options);
// Returns: Array<Map<NodeId, NodeId>>

Link Prediction Algorithms

Common Neighbors

import { commonNeighborsScore, commonNeighborsPrediction, commonNeighborsForPairs } from '@graphty/algorithms';

// Score for a specific pair
const score = commonNeighborsScore(graph, node1, node2);
// Returns: number

// Predict links for all non-connected pairs
const predictions = commonNeighborsPrediction(graph, {
  directed?: boolean,        // Consider direction
  includeExisting?: boolean, // Include existing edges
  topK?: number             // Return only top K predictions
});
// Returns: LinkPredictionScore[]

// Score multiple specific pairs
const scores = commonNeighborsForPairs(graph, pairs, options);
// Returns: LinkPredictionScore[]

// Evaluate prediction performance
const evaluation = evaluateCommonNeighbors(graph, testEdges);
// Returns: { precision, recall, f1Score }

// Get top candidates for a node
const candidates = getTopCandidatesForNode(graph, nodeId, { topK?: number });
// Returns: LinkPredictionScore[]

Adamic-Adar Index

import { adamicAdarScore, adamicAdarPrediction, adamicAdarForPairs } from '@graphty/algorithms';

// Adamic-Adar score for a pair (weighted by neighbor degrees)
const score = adamicAdarScore(graph, node1, node2);
// Returns: number

// Predict links using Adamic-Adar
const predictions = adamicAdarPrediction(graph, {
  directed?: boolean,
  includeExisting?: boolean,
  topK?: number
});
// Returns: LinkPredictionScore[]

// Score multiple pairs
const scores = adamicAdarForPairs(graph, pairs, options);
// Returns: LinkPredictionScore[]

// Compare Adamic-Adar with Common Neighbors
const comparison = compareAdamicAdarWithCommonNeighbors(graph, pairs);
// Returns: Array<{ source, target, adamicAdar, commonNeighbors }>

// Evaluate prediction performance
const evaluation = evaluateAdamicAdar(graph, testEdges);
// Returns: { precision, recall, f1Score }

// Get top candidates for a node
const candidates = getTopAdamicAdarCandidatesForNode(graph, nodeId, { topK?: number });
// Returns: LinkPredictionScore[]

Research Algorithms (2023-2025)

Cutting-edge graph algorithms based on recent research.

SynC - Synergistic Deep Graph Clustering

import { syncClustering } from '@graphty/algorithms';

// Deep learning based clustering
const result = syncClustering(graph, {
  k: number,                  // Number of clusters
  maxIterations?: number,     // Default: 100
  learningRate?: number,      // Default: 0.01
  hiddenDim?: number,         // Default: 64
  randomSeed?: number
});
// Returns: SynCResult { 
//   communities: NodeId[][], 
//   clusterAssignments: Map<NodeId, number>,
//   embeddings: Map<NodeId, number[]>,
//   iterations: number,
//   converged: boolean
// }

TeraHAC - Scalable Hierarchical Agglomerative Clustering

import { teraHAC } from '@graphty/algorithms';

// Scalable hierarchical clustering
const result = teraHAC(graph, {
  linkage?: 'single' | 'complete' | 'average',  // Default: 'average'
  k?: number,                   // Target number of clusters
  threshold?: number,           // Distance threshold for merging
  sampleSize?: number,          // Default: 1000
  randomSeed?: number
});
// Returns: TeraHACResult {
//   root: TeraHACClusterNode,
//   dendrogram: TeraHACClusterNode[],
//   clusters: NodeId[][],
//   mergeDistances: number[]
// }

GRSBM - Greedy Recursive Spectral Bisection with Modularity

import { grsbm } from '@graphty/algorithms';

// Explainable community detection
const result = grsbm(graph, {
  minClusterSize?: number,      // Default: 5
  maxDepth?: number,            // Default: 10
  modularityThreshold?: number, // Default: 0.1
  explainClusters?: boolean     // Default: true
});
// Returns: GRSBMResult {
//   clusters: GRSBMCluster[],   // Each cluster has id, nodes, modularity, explanation
//   hierarchy: Map<number, number[]>,
//   totalModularity: number
// }

Algorithm Categories Summary

Available Algorithms by Category:

Traversal: BFS, DFS, Topological Sort, Cycle Detection, Bipartite Check
Shortest Path: Dijkstra, Bellman-Ford, Floyd-Warshall, A*
Centrality: Degree, Betweenness, Closeness, PageRank, Eigenvector, Katz, HITS
Components: Connected, Strongly Connected, Weakly Connected, Condensation Graph
Community Detection: Louvain, Leiden, Label Propagation, Girvan-Newman
Clustering: Hierarchical, K-Core, Spectral, Markov (MCL)
Minimum Spanning Tree: Kruskal, Prim
Network Flow: Ford-Fulkerson, Edmonds-Karp, Min-Cut (Stoer-Wagner, Karger)
Matching: Bipartite Matching, Graph Isomorphism
Link Prediction: Common Neighbors, Adamic-Adar
Research Algorithms: SynC, TeraHAC, GRSBM

Examples

The library includes comprehensive examples demonstrating each algorithm. Find them in the examples directory:

Basic Algorithms

BFS Traversal - Breadth-first search and shortest paths
DFS Traversal - Depth-first search and applications
Dijkstra's Algorithm - Weighted shortest paths
Bellman-Ford - Shortest paths with negative weights
Floyd-Warshall - All pairs shortest paths

Centrality Measures

Degree Centrality - Node importance by connections
Betweenness Centrality - Bridge nodes
Closeness Centrality - Central nodes
PageRank - Node ranking algorithm
Eigenvector Centrality - Influence from important nodes
Katz Centrality - Weighted path counting
HITS Algorithm - Hub and authority scores

Graph Structure

Connected Components - Find graph components
Kruskal's MST - Minimum spanning tree
Prim's MST - Alternative MST algorithm

Community Detection

Louvain Method - Modularity-based communities
Leiden Algorithm - Improved Louvain
Label Propagation - Fast community detection
Girvan-Newman - Hierarchical communities

Clustering

Hierarchical Clustering - Graph clustering
K-Core Decomposition - Core analysis
Spectral Clustering - Eigenvalue-based clustering
MCL Clustering - Markov clustering

Matching

Bipartite Matching - Job assignment, dating apps
Graph Isomorphism - Structural equivalence

Link Prediction

Common Neighbors - Friend suggestions
Adamic-Adar - Weighted predictions

Advanced Algorithms

A* Pathfinding - Heuristic pathfinding
Flow Algorithms - Maximum flow and applications
Ford-Fulkerson Flow - Maximum flow implementation
Minimum Cut - Graph partitioning

Research Algorithms

SynC Clustering - Deep learning based clustering
TeraHAC - Scalable hierarchical clustering
GRSBM - Explainable community detection

Advanced Usage Examples

Working with Weighted Graphs

const graph = new Graph();

// Add weighted edges
graph.addEdge('A', 'B', 5);
graph.addEdge('B', 'C', 3);
graph.addEdge('A', 'C', 10);

// Find shortest path considering weights
const result = dijkstra(graph, 'A');
const pathToC = dijkstraPath(graph, 'A', 'C');
console.log(pathToC); // { path: ['A', 'B', 'C'], distance: 8 }

Directed Graphs

const directedGraph = new Graph({ directed: true });

directedGraph.addEdge('A', 'B');
directedGraph.addEdge('B', 'C');
directedGraph.addEdge('C', 'A');

// Check for cycles
console.log(hasCycleDFS(directedGraph)); // true

// Find strongly connected components
const sccs = stronglyConnectedComponents(directedGraph);
console.log(sccs.components); // [['A', 'B', 'C']]

Network Analysis

// Identify important nodes
const graph = createSocialNetwork(); // Your graph

// Find influencers (high PageRank)
const influencers = topPageRankNodes(graph, 10);

// Find bridges (high betweenness)
const bridgers = Array.from(betweennessCentrality(graph).entries())
  .sort((a, b) => b[1] - a[1])
  .slice(0, 10);

// Find communities (connected components)
const communities = connectedComponents(graph);
console.log(`Found ${communities.components.length} communities`);

Custom Edge Properties

const graph = new Graph();

// Add edges with custom data
graph.addEdge('A', 'B', 1, { 
  type: 'road', 
  distance: 100, 
  traffic: 'heavy' 
});

// Use custom weight in algorithms
const result = dijkstra(graph, 'A', { 
  weightKey: 'distance' // Use 'distance' property as weight
});

Graph Visualization Preparation

// Prepare data for visualization
const graph = loadGraph();

// Calculate layout metrics
const centralities = degreeCentrality(graph, { normalized: true });
const ranks = pageRank(graph);

// Export for visualization
const nodes = Array.from(graph.nodes()).map(node => ({
  id: node.id,
  data: node.data,
  size: centralities.get(node.id) || 0,
  importance: ranks.get(node.id) || 0
}));

const edges = Array.from(graph.edges()).map(edge => ({
  source: edge.source,
  target: edge.target,
  weight: edge.weight || 1,
  data: edge.data
}));

Type Definitions

Core Types

type NodeId = string | number;

interface Node {
  id: NodeId;
  data?: Record<string, unknown>;
}

interface Edge {
  source: NodeId;
  target: NodeId;
  weight?: number;
  id?: string;
  data?: Record<string, unknown>;
}

Algorithm Result Types

interface TraversalResult {
  visited: Set<NodeId>;
  order: NodeId[];
  tree?: Map<NodeId, NodeId>;
}

interface ShortestPathResult {
  path: NodeId[];
  distance: number;
  predecessor: NodeId | null;
}

interface BellmanFordResult {
  distances: Map<NodeId, number>;
  predecessors: Map<NodeId, NodeId | null>;
  hasNegativeCycle: boolean;
  negativeCycleNodes?: Set<NodeId>;
}

type CentralityResult = Record<string, number>;

interface PageRankResult {
  ranks: Record<string, number>;
  iterations: number;
  converged: boolean;
}

interface CommunityResult {
  communities: Map<NodeId, number>;
  modularity: number;
}

interface ComponentResult {
  components: NodeId[][];
  componentMap: Map<NodeId, number>;
}

interface HITSResult {
  hubs: CentralityResult;
  authorities: CentralityResult;
}

interface SpectralClusteringResult {
  communities: NodeId[][];
  clusterAssignments: Map<NodeId, number>;
}

interface MCLResult {
  communities: NodeId[][];
  attractors: Set<NodeId>;
  iterations: number;
  converged: boolean;
}

interface BipartiteMatchingResult {
  matching: Map<NodeId, NodeId>;
  size: number;
}

interface LinkPredictionScore {
  source: NodeId;
  target: NodeId;
  score: number;
}

interface HierarchicalClusteringResult<T> {
  root: ClusterNode<T>;
  dendrogram: ClusterNode<T>[];
  clusters: Map<number, Set<T>[]>;
}

interface KCoreResult<T> {
  cores: Map<number, Set<T>>;
  coreness: Map<T, number>;
  maxCore: number;
}

interface IsomorphismResult {
  isIsomorphic: boolean;
  mapping?: Map<NodeId, NodeId>;
}

interface SynCResult {
  communities: NodeId[][];
  clusterAssignments: Map<NodeId, number>;
  embeddings: Map<NodeId, number[]>;
  iterations: number;
  converged: boolean;
}

interface TeraHACResult {
  root: TeraHACClusterNode;
  dendrogram: TeraHACClusterNode[];
  clusters: NodeId[][];
  mergeDistances: number[];
}

interface GRSBMResult {
  clusters: GRSBMCluster[];
  hierarchy: Map<number, number[]>;
  totalModularity: number;
}

Performance Considerations

Graph Representation: Uses adjacency lists for O(1) neighbor access
Algorithm Complexity:
- BFS/DFS: O(V + E)
- Dijkstra: O((V + E) log V) with binary heap
- Bellman-Ford: O(VE)
- Floyd-Warshall: O(V³)
- PageRank: O(k(V + E)) where k is iterations
- Connected Components: O(V + E)
- Kruskal's MST: O(E log E)
- Prim's MST: O((V + E) log V)
- A*: O((V + E) log V) - depends on heuristic quality
- Ford-Fulkerson: O(E * f) where f is max flow
- Edmonds-Karp: O(VE²)
- Louvain/Leiden: O(n log n) average case
- Hierarchical Clustering: O(n² log n)
- SynC: O(kni) where k is clusters, n is nodes, i is iterations
- TeraHAC: O(n log n) with sampling
- GRSBM: O(m log n) where m is edges
Memory Usage: O(V + E) for graph storage
Browser Optimization: Algorithms use iterative approaches where possible to avoid stack overflow

Development

Prerequisites

Node.js 18+
npm 9+

Setup

# Clone the repository
git clone https://github.com/graphty-org/algorithms.git
cd algorithms

# Install dependencies
npm install

# Set up git hooks
npm run prepare

Scripts

# Development
npm run dev          # Watch mode compilation
npm run build        # Build the library
npm run typecheck    # Type checking

# Testing
npm run test         # Run tests in watch mode
npm run test:run     # Run tests once
npm run test:coverage # Generate coverage report
npm run test:browser # Run browser tests

# Code Quality
npm run lint         # Run ESLint
npm run lint:fix     # Fix ESLint issues
npm run lint:pkg     # Check for unused dependencies

# Git
npm run commit       # Conventional commit helper

# HTML Examples
npm run examples:html # Run interactive HTML examples
npm run build:gh-pages # Build for GitHub Pages deployment

Development Server

The project includes interactive HTML examples demonstrating each algorithm. To run them locally:

Copy the environment configuration:
```
cp .env.example .env
```

Configure the server (optional): Edit .env to set your preferred host and port:

# Server host (defaults to true for network exposure)
HOST=localhost       # For local-only access
# HOST=0.0.0.0       # For network access
# HOST=my.server.com # Custom domain

# Server port (defaults to 9000)
PORT=9000           # Must be between 9000-9099

Start the development server:
```
npm run examples:html
```
Open your browser to http://localhost:9000 (or your configured host/port)

The HTML examples provide:

Interactive visualizations for each algorithm
Step-by-step execution with play/pause controls
Multiple graph types for testing
Real-time parameter adjustment
Educational information about complexity and use cases
Mobile debugging console (Eruda) for testing on mobile devices

Project Structure

src/
├── core/              # Core graph data structures
├── algorithms/        # Algorithm implementations
│   ├── traversal/     # BFS, DFS
│   ├── shortest-path/ # Dijkstra, Bellman-Ford
│   ├── centrality/    # Degree, Betweenness, PageRank
│   └── components/    # Connected components
├── data-structures/   # Supporting data structures
├── types/            # TypeScript type definitions
└── utils/            # Utility functions

examples/
├── html/             # Interactive HTML examples
│   ├── shared/       # Shared utilities and styles
│   └── algorithms/   # Algorithm-specific examples

test/
├── unit/             # Unit tests
├── browser/          # Browser-specific tests
└── helpers/          # Test utilities

Contributing

We welcome contributions! Please see our Contributing Guide for details.

Commit Convention

This project uses Conventional Commits:

feat(scope): add new algorithm
fix(scope): resolve edge case in traversal
docs(scope): update API documentation
test(scope): add coverage for centrality measures

License

Related Projects

@graphty/layout - Graph layout algorithms
@graphty/graphty-element - 3D graph visualization web component

Published

Vulnerabilities

Links

Maintainers

Keywords

Readme

@graphty/algorithms

Features

Installation

Quick Start

API Reference

Graph Class

Configuration Options

Node Operations

Edge Operations

Graph Properties

Degree Operations

Neighbor Operations

Utility Methods

Traversal Algorithms

Breadth-First Search (BFS)

Depth-First Search (DFS)

Shortest Path Algorithms

Dijkstra's Algorithm

Bellman-Ford Algorithm

Floyd-Warshall Algorithm

Centrality Algorithms

Degree Centrality

Betweenness Centrality

Closeness Centrality

PageRank

Eigenvector Centrality

Katz Centrality

HITS Algorithm

Connected Components

Basic Component Operations

Strongly Connected Components

Weakly Connected Components

Data Structures

Priority Queue

Union-Find (Disjoint Set)

Minimum Spanning Tree Algorithms

Kruskal's Algorithm

Prim's Algorithm

Community Detection Algorithms

Louvain Method

Leiden Algorithm

Label Propagation

Girvan-Newman Algorithm

Pathfinding Algorithms

A* Algorithm

Flow Algorithms

Maximum Flow

Minimum Cut

Clustering Algorithms

Hierarchical Clustering

K-Core Decomposition

Spectral Clustering

Markov Clustering (MCL)

Matching Algorithms

Bipartite Matching

Graph Isomorphism

Link Prediction Algorithms

Common Neighbors

Adamic-Adar Index

Research Algorithms (2023-2025)

SynC - Synergistic Deep Graph Clustering

TeraHAC - Scalable Hierarchical Agglomerative Clustering

GRSBM - Greedy Recursive Spectral Bisection with Modularity

Algorithm Categories Summary

Available Algorithms by Category:

Examples

Basic Algorithms

Centrality Measures

Graph Structure

Community Detection

Clustering

Matching

Link Prediction

Advanced Algorithms