CtrlK
BlogDocsLog inGet started
Tessl Logo

tessl/npm-graphlib

A directed and undirected multi-graph library with comprehensive graph algorithms

—

Pending
Quality

Pending

Does it follow best practices?

Impact

Pending

No eval scenarios have been run

SecuritybySnyk

Pending

The risk profile of this skill

Overview
Eval results
Files

algorithms.mddocs/

Graph Algorithms

Comprehensive suite of graph algorithms including shortest paths, traversal methods, cycle detection, topological sorting, and strongly connected components analysis.

Capabilities

Shortest Path Algorithms

Dijkstra's Algorithm

Single-source shortest paths algorithm supporting custom weight and edge functions.

/**
 * Computes shortest paths from source node to all reachable nodes
 * @param g - Graph instance
 * @param source - Starting node ID
 * @param weightFn - Optional function to get edge weight (default: constant 1)
 * @param edgeFn - Optional function to get edges (default: outEdges for directed, nodeEdges for undirected)
 * @returns Object mapping node IDs to {distance: number, predecessor?: string}
 * @throws Error if negative edge weights are encountered
 */
function dijkstra(
  g: Graph, 
  source: string, 
  weightFn?: (edge: EdgeObj) => number,
  edgeFn?: (v: string) => EdgeObj[]
): DijkstraResult;

interface DijkstraResult {
  [nodeId: string]: {
    distance: number;
    predecessor?: string;
  };
}

Usage Examples:

import { Graph, alg } from "graphlib";

const g = new Graph();
g.setEdge("a", "b", { weight: 4 });
g.setEdge("a", "c", { weight: 2 });
g.setEdge("b", "c", { weight: 1 });
g.setEdge("c", "d", { weight: 5 });

// Use edge weights
const paths = alg.dijkstra(g, "a", (edge) => g.edge(edge).weight);
console.log(paths.d.distance); // 8 (a->c->d)
console.log(paths.d.predecessor); // "c"

// Uniform weights (default)
const uniformPaths = alg.dijkstra(g, "a");
console.log(uniformPaths.d.distance); // 3 (a->c->d)

Dijkstra All-Pairs

All-pairs shortest paths using Dijkstra's algorithm for each source node.

/**
 * Computes shortest paths between all pairs of nodes using Dijkstra
 * @param g - Graph instance
 * @param weightFn - Optional function to get edge weight
 * @param edgeFn - Optional function to get edges
 * @returns Nested object: {sourceId: {targetId: {distance, predecessor}}}
 */
function dijkstraAll(
  g: Graph,
  weightFn?: (edge: EdgeObj) => number,
  edgeFn?: (v: string) => EdgeObj[]
): AllPairsResult;

interface AllPairsResult {
  [sourceId: string]: DijkstraResult;
}

Floyd-Warshall Algorithm

All-pairs shortest paths algorithm with O(V³) complexity, handles negative weights.

/**
 * Computes shortest paths between all pairs using Floyd-Warshall algorithm
 * @param g - Graph instance
 * @param weightFn - Optional function to get edge weight
 * @param edgeFn - Optional function to get edges
 * @returns Nested object: {sourceId: {targetId: {distance, predecessor}}}
 */
function floydWarshall(
  g: Graph,
  weightFn?: (edge: EdgeObj) => number,
  edgeFn?: (v: string) => EdgeObj[]
): AllPairsResult;

Usage Examples:

// Graph with negative weights
const g = new Graph();
g.setEdge("a", "b", { weight: -2 });
g.setEdge("b", "c", { weight: 3 });
g.setEdge("a", "c", { weight: 4 });

const allPaths = alg.floydWarshall(g, (edge) => g.edge(edge).weight);
console.log(allPaths.a.c.distance); // 1 (via b)
console.log(allPaths.a.c.predecessor); // "b"

Traversal Algorithms

Depth-First Search

Configurable depth-first search with preorder and postorder options.

/**
 * Performs depth-first search traversal
 * @param g - Graph instance
 * @param vs - Starting node(s) (string or array of strings)
 * @param order - "pre" for preorder, "post" for postorder
 * @returns Array of node IDs in traversal order
 * @throws Error if starting node doesn't exist
 */
function dfs(g: Graph, vs: string | string[], order: "pre" | "post"): string[];

/**
 * Preorder DFS traversal (visits node before children)
 * @param g - Graph instance
 * @param vs - Starting node(s)
 */
function preorder(g: Graph, vs: string | string[]): string[];

/**
 * Postorder DFS traversal (visits node after children)
 * @param g - Graph instance
 * @param vs - Starting node(s)
 */
function postorder(g: Graph, vs: string | string[]): string[];

Usage Examples:

const g = new Graph();
g.setPath(["a", "b", "c"]);
g.setEdge("a", "d");
g.setEdge("d", "e");

console.log(alg.preorder(g, "a"));  // ["a", "b", "c", "d", "e"]
console.log(alg.postorder(g, "a")); // ["c", "b", "e", "d", "a"]

// Multiple starting points
console.log(alg.dfs(g, ["a", "f"], "pre")); // Includes disconnected nodes

Topological Sorting

Topological ordering of directed acyclic graphs.

/**
 * Returns topological ordering of the graph
 * @param g - Graph instance (must be directed)
 * @returns Array of node IDs in topological order
 * @throws CycleException if graph contains cycles
 */
function topsort(g: Graph): string[];

/**
 * Exception thrown when topological sort encounters cycles
 */
class CycleException extends Error {
  constructor();
}

Usage Examples:

// Task dependency graph
const tasks = new Graph();
tasks.setEdge("design", "implement");
tasks.setEdge("implement", "test");
tasks.setEdge("design", "docs");

try {
  const order = alg.topsort(tasks);
  console.log(order); // ["design", "implement", "docs", "test"] (or valid variant)
} catch (e) {
  if (e instanceof alg.topsort.CycleException) {
    console.log("Cannot sort: graph has cycles");
  }
}

Cycle Detection

Methods for detecting and analyzing cycles in graphs.

/**
 * Returns true if graph has no cycles
 * @param g - Graph instance
 */
function isAcyclic(g: Graph): boolean;

/**
 * Returns all cycles in the graph
 * @param g - Graph instance
 * @returns Array of cycles, each cycle is an array of node IDs
 */
function findCycles(g: Graph): string[][];

Usage Examples:

const g = new Graph();
g.setPath(["a", "b", "c"]);
g.setEdge("c", "a"); // Creates cycle

console.log(alg.isAcyclic(g)); // false
console.log(alg.findCycles(g)); // [["a", "b", "c"]]

// Remove cycle-creating edge
g.removeEdge("c", "a");
console.log(alg.isAcyclic(g)); // true

Strongly Connected Components

Analysis of strongly connected components in directed graphs.

/**
 * Returns strongly connected components using Tarjan's algorithm
 * @param g - Graph instance
 * @returns Array of components, each component is an array of node IDs
 */
function tarjan(g: Graph): string[][];

/**
 * Returns strongly connected components (alias for tarjan)
 * @param g - Graph instance
 * @returns Array of components
 */
function components(g: Graph): string[][];

Usage Examples:

const g = new Graph();
// Create graph with SCCs
g.setEdge("a", "b");
g.setEdge("b", "c");
g.setEdge("c", "a"); // SCC: {a, b, c}
g.setEdge("c", "d");
g.setEdge("d", "e");
g.setEdge("e", "d"); // SCC: {d, e}

const sccs = alg.tarjan(g);
console.log(sccs); // [["a", "b", "c"], ["d", "e"]]

Minimum Spanning Tree

Minimum spanning tree algorithms for weighted graphs.

/**
 * Computes minimum spanning tree using Prim's algorithm
 * @param g - Graph instance (must be connected for meaningful result)
 * @param weightFn - Required function to get edge weights
 * @returns New Graph instance containing MST edges
 * @throws Error if graph is not connected
 */
function prim(g: Graph, weightFn: (edge: EdgeObj) => number): Graph;

Usage Examples:

const g = new Graph({ directed: false }); // Undirected for MST
g.setEdge("a", "b", { weight: 4 });
g.setEdge("a", "c", { weight: 2 });
g.setEdge("b", "c", { weight: 1 });
g.setEdge("b", "d", { weight: 5 });
g.setEdge("c", "d", { weight: 8 });
g.setEdge("c", "e", { weight: 10 });
g.setEdge("d", "e", { weight: 2 });

const mst = alg.prim(g, (edge) => g.edge(edge).weight);
console.log(mst.edges().length); // 4 (n-1 edges for n nodes)

// Calculate total MST weight
let totalWeight = 0;
mst.edges().forEach(edge => {
  totalWeight += g.edge(edge).weight;
});
console.log(totalWeight); // Minimum possible total weight

Algorithm Configuration

Weight Functions

Most algorithms accept an optional weightFn parameter:

// Use edge labels as weights
const weightFn = (edge) => g.edge(edge);

// Use specific property as weight
const weightFn = (edge) => g.edge(edge).distance;

// Constant weight (default behavior)
const weightFn = (edge) => 1;

// Dynamic weight calculation
const weightFn = (edge) => {
  const edgeData = g.edge(edge);
  return edgeData.distance * edgeData.difficulty;
};

Edge Functions

Some algorithms accept an optional edgeFn parameter to customize edge traversal:

// Default behaviors:
// - Directed graphs: outEdges (follow edge direction)
// - Undirected graphs: nodeEdges (all connected edges)

// Custom edge function for reverse traversal
const reverseEdgeFn = (v) => g.inEdges(v);

// Filtered edge function
const filteredEdgeFn = (v) => {
  return g.outEdges(v).filter(edge => {
    const edgeData = g.edge(edge);
    return edgeData.enabled !== false;
  });
};

Performance Characteristics

Time Complexities

  • Dijkstra: O((V + E) log V) using binary heap
  • Dijkstra All: O(V × (V + E) log V)
  • Floyd-Warshall: O(V³)
  • DFS/Traversal: O(V + E)
  • Topological Sort: O(V + E)
  • Tarjan SCC: O(V + E)
  • Prim MST: O((V + E) log V)

Space Complexities

  • Dijkstra: O(V) for distance/predecessor tracking
  • Floyd-Warshall: O(V²) for all-pairs matrix
  • DFS: O(V) for visited tracking and recursion stack
  • Prim: O(V) for priority queue and MST tracking

Error Handling

Common algorithm errors and exceptions:

  • Error: "dijkstra does not allow negative edge weights" - Negative weights in Dijkstra algorithm
  • Error: "Input graph is not connected" - Prim's algorithm on disconnected graph
  • Error: "Graph does not have node: X" - Algorithm called with non-existent starting node
  • CycleException: Thrown by topsort when graph contains cycles (not a standard Error)

Advanced Usage Patterns

Custom Weight Functions

// Time-based weights
const timeWeightFn = (edge) => {
  const edgeData = g.edge(edge);
  const currentHour = new Date().getHours();
  return edgeData.baseTime * (edgeData.trafficMultiplier[currentHour] || 1);
};

// Multi-criteria weights
const multiCriteriaFn = (edge) => {
  const data = g.edge(edge);
  return data.distance * 0.6 + data.cost * 0.4;
};

Algorithm Chaining

// Find shortest paths in acyclic subgraph
if (alg.isAcyclic(g)) {
  const topOrder = alg.topsort(g);
  const paths = alg.dijkstra(g, topOrder[0]);
} else {
  // Handle cyclic graph differently
  const cycles = alg.findCycles(g);
  console.log("Graph has cycles:", cycles);
}

docs

algorithms.md

graph.md

index.md

json.md

tile.json