About this package

A lightweight and dependency-free collection of essential data structures and graph algorithms, written entirely in TypeScript. This library supports CommonJS, ESM, and browser environments, and includes utility functions for practical, everyday tasks in modern development.

Historical Background

The organization and structuring of data has deep roots, reaching far beyond the digital age. In the 19th century, mathematics introduced formal constructs such as matrices and polynomials. In 1837, Charles Babbage conceptualized tabular memory in his design of the Analytical Engine, followed by George Boole in 1854, who laid the foundations of Boolean logic. Herman Hollerith introduced punched cards for structured data input in 1890.

Theoretical computing advanced significantly in the 20th century:
In 1936, Alan Turing proposed the Turing machine, a model based on an infinite tape, which inspired later abstractions such as arrays, buffers, and queues. Around the same time, Alonzo Church developed the lambda calculus, laying the foundation for functional programming — which in turn influenced Konrad Zuse, who in the 1940s designed the Plankalkül, the first high-level language to define typed data structures and formal operations.

This library embraces these historical concepts and translates them into a clean, type-safe, and modern TypeScript implementation suitable for a wide range of applications.

Interactive Graph Visualization

For visual experimentation and algorithm demos, we recommend using GraphOnline, a free and intuitive tool that allows you to:

Draw directed and undirected graphs
Assign weights and labels to edges
Run built-in algorithms like DFS, BFS, Dijkstra, and Floyd-Warshall
Visualize traversal steps and shortest paths interactively

This external tool complements the core features of the library, making it easier to prototype and test graph-based logic.

Whether you're working on academic projects, interview preparation, or production-level applications, this library offers a solid foundation rooted in theory and optimized for practical use.

Here are two examples of using the package directly in the browser:

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>include npm package as IIFE</title>
    <script src="https://unpkg.com/@avensio/shared"></script>
  </head>
  <body>

    <script>
      const a = new Vertex('A')
      const b = new Vertex('B')
      const g = new Graph()
      g.addVertex(a)
      g.addVertex(b)
      g.addEdge(new Edge(a, b))
      console.debug(g)
    </script>

    <script type="module">
      import { Vertex, Edge, Graph } from 'https://unpkg.com/@avensio/shared@latest/dist/shared.es.js'
    </script>

  </body>
</html>

otherwise install it with npm/pnpm: npm install @avensio/shared and use the classes by importing them:

import { Vertex, Edge, Graph } from '@avensio/shared'

The test coverage is about 90% and benchmarks for list, queue and stack tests are included.

A bulk of algorithms have asymptotic behavior described with the upper and the lower bound (time complexity).

All datastructures (except Graph, Vertex, Edge) can be passed an Iterable as constructor argument to initialize with.

Graph
1.1 GraphProperties
1.2 Algorithms
1.3 Utility Functions
Lists
2.1 List
2.2 LinkedList
2.2.1 DoublyLinkedList
2.2.2 CyclicLinkedList
Queues
3.1 Queue
3.2 LinkedQueue
3.3 PriorityQueue
3.4 Dequeue
Stacks
4.1 Stack
4.2 LinkedStack
Heap
Sorting
6.1 Quicksort
6.2 Heapsort

Graph

To use the Graph provided by this package some GraphProperties can be passed to the Graph constructor as first argument, as second a comparator can be passed.

The comparator is needed for some algorithms to function properly and must return all Ordering's (-1 for LessThan, 0 for EQual and 1 for GreaterThan).

A minimal example of using the graph is as follows:

import { Graph } from '@avensio/shared'

const graph = new Graph()

If a custom Graph with custom Vertex and Edge classes is needed, the Graph can extend AGraph like so:

class CustomVertex extends Vertex {
  additionalVertexProp = 'prop'
}

class CustomEdge extends Edge {
  additionalEdgeProp = 'prop'
}

class Graph extends AGraph<CustomVertex, CustomEdge> {
  constructor(props: GraphProperties = {}, comparator?: Comparator<CustomVertex>)) {
    const _cmp = (v1: IVertex, v2: IVertex) => (v1.uuid === v2.uuid ?
      Ordering.EQ
      : v1.outdeg() < v2.outdeg() ?
        Ordering.LT
        : Ordering.GT)
    super(props, (comparator || _cmp), CustomVertex, CustomEdge)
  }
}

A custom comparator can be provided for CustomVertex or a default one (_cmp) could be used.

Graph Properties

density(): number
- Calculates the density of the graph. Density is the ratio of the number of actual edges to the maximum possible number of edges. A value close to 1 indicates a dense graph; a value close to 0 indicates a sparse graph.
order(): number
- Returns the number of vertices (nodes) in the graph.
size(): number
- Returns the number of edges in the graph.
isCyclic(): boolean
- Checks whether the graph contains at least one cycle (i.e., a path that starts and ends at the same node).
isAcyclic(): boolean
- Checks whether the graph is acyclic (i.e., contains no cycles).
isTree(): boolean
- Checks whether the graph is a tree, meaning it is connected and acyclic.
isForest(): boolean
- Checks whether the graph is a forest, meaning it consists of a collection of disjoint trees.
isDirected(): boolean
- Returns whether the graph is directed (i.e., edges have a direction).
isConnected(): boolean
- Checks whether the directed or undirected graph is connected, meaning there is a path between any two nodes.
isStronglyConnected(): boolean
- Checks if there is a path from v to every other node and a path from every other node back to v (strong connectivity).
isMixed(): boolean
- Returns whether the graph has both directed and undirected edges (mixed graph).
isDense(): boolean
- Checks whether the graph is considered dense based on a defined density threshold (density >= threshold).
isSparse(): boolean
- Checks whether the graph is considered sparse, meaning it has relatively few edges compared to the number of possible edges (density < threshold).

Algorithms

depthFirstSearch(startVertex: V)
- Performs a depth-first traversal starting from startVertex. Explores as far as possible along each branch before backtracking.
breadthFirstSearch(startVertex: V)
- Performs a breadth-first traversal starting from startVertex. Visits all neighboring vertices before moving to the next level.
shortestPath(from: V, to: V)
- Computes the shortest path between from and to using a modified More-Bellman-Ford's algorithm. Returns the path as a list of vertices.
kShortestPaths(from: V, to: V, k: number)
- Finds the k shortest simple paths between from and to using a variation of Yen's algorithm. Returns a list of paths sorted by total cost.
minimalSpanningTree()
- Constructs a minimal spanning tree of the graph using Kruskal's algorithm (if undirected) or returns a minimum branching (if directed).
topologicalSorting()
- Performs a topological sort on the graph. Assumes the graph is a Directed Acyclic Graph (DAG) and returns an ordering of vertices.
parallelTopologicalSorting()
- Computes a layered topological sort, grouping vertices into levels based on dependencies. Useful for parallel execution scheduling.
connectedComponents()
- Identifies all connected components of the graph (for undirected graphs) and returns them as a list of graphs.
strongConnectedComponents()
- Finds all strongly connected components in a directed graph.
checkForCycles()
- Checks if the graph contains any cycles (works for both directed and undirected graphs).
checkForNegativeCycles()
- Checks if the graph contains negative weight cycles (applicable for weighted directed graphs; uses Bellman-Ford approach).
inferCycles()
- Identifies and returns all detected cycles within the graph. May return multiple cycles if the graph is highly interconnected.

Utility functions

createEdge(from: V, to: V, title?: string, directed?: boolean, weight?: number): E
Creates a new edge between two vertices, optionally specifying a title, direction, and weight.
addEdge(e: E): boolean
Adds an edge to the graph if it does not already exist; returns true if successful, false if the edge is already contained.
removeEdge(e: E): boolean
Removes an edge from the graph; returns true if the edge was found and removed, false otherwise.
createVertex(title?: string, point?: Point, object?: any): V
Creates a new vertex with an optional title, a position (Point), and any additional associated data (object).
addVertex(v: V): boolean
Adds a vertex to the graph if it does not already exist; returns true if successful, false if the vertex is already contained.
removeVertex(v: V): boolean
Removes a vertex (and all connected edges) from the graph; returns true if the vertex was found and removed, false otherwise.
c(from: V, to: V): number
Returns the cost (i.e., weight) of traveling from one vertex to another.
If no direct edge exists, typically returns Infinity or a sentinel value.

Lists

All lists implement the interface IList:

interface IList<E> extends ICollection<E>, IListFunctions<E> {
  comparator: Comparator<E>
  addAll(c: Iterable<E>): void
  get(index: number): E
  set(index: number, e: E | null): boolean
  remove(index: number): E
  equals(l: IList<E>): boolean
  indexOf(e: E): number
  includes(e: E): boolean
  reverseIterator(): Generator<E>
}

The interface ICollection adds the following to the lists:

interface ICollection<E> extends ISortable<E>, Iterable<E>, IReverseIterable<E> {
  add(e: E): void
  size: number
  isEmpty(): boolean
  clear(): void
}

and further, Iterable adds:

interface Iterable<T> {
    [Symbol.iterator](): Iterator<T>;
}

ISortable adds:

export interface ISortable<V> {
  sort(cmp?: Comparator<V>): void
}

IReverseIterable adds:

interface IReverseIterable<E> {
  reverseIterator(): Generator<E>
}

and IListFunctions adds some common functions:

interface IListFunctions<E> {
  map<V>(fn: (e: E) => V): IList<V>
  reduce<V>(fn: (accumulator: V, element: E) => V, initialValue?: V): V
  filter(predicate: (e: E) => boolean): IList<E>
  every(predicate: (e: E) => boolean): boolean
  some(predicate: (e: E) => boolean): boolean
  slice(startIndex: number, endIndex: number): IList<E>
  slice2(startIndex: number, endIndex: number): IList<E>
  splice(startIndex: number, deleteCount: number): IList<E>
}

List

List implementation using the native array as data structure to have a reference when benchmarking some list methods.

const list = new List<number>()
const list2 = new List<number>([1,2,3])

LinkedList

A linked list consists of nodes, each with a pointer to the next node.

Additionally, to the interfaces in IList, LinkedLists also implement the following properties and functions:

export interface ILinkedList<E> extends IList<E> {
  first: Node<E>
  last: Node<E>
  getNode(index: number): Node<E>
  addFirst(e: E): void
  addLast(e: E): void
  getFirst(): E
  getLast(): E
  removeFirst(): E
  removeLast(): E
}

const list = new LinkedList<number>()

DoublyLinkedList

Linked lists hava one pointer to the next node, but that's it. No other pointers. Doubly linked lists have these second pointer to the previous element.

const list = new DoublyLinkedList<number>()

CyclicLinkedList

Doubly linked lists have 2 pointers: the first to the next, and the second to the previous element. But these kind of list is ending at the first and last elements. The doubly linked list kind of lists has no previous pointer at the first element and no next pointer at the last element.

With this cyclic linked lists there is a new kind of list with exactly these 2 pointers. So a cyclic linked list is named this way, since the first element now points to the last and the last to the first element, so the list is now cyclic.

const list = new CyclicLinkedList<number>()

Queues

Queues are implementing the interface IQueue and extends ICollection:

export interface IQueue<E> extends ICollection<E> {
  enqueue(e: E): void
  dequeue(): E
  head(): E
}

Queue

Queues have a head (f.e. the first one in the queue) and a tail (where the new ones will enqueue).

Like the list, also the queue have an implementation using a native array as backing data structure for benchmarking.

const queue = new Queue<number>()

LinkedQueue

A linked queue has like a linked list 2 pointers with different names. With queues the pointers are head and tail, instead of first and last.

const queue = new LinkedQueue<number>()

PriorityQueue

The priority queue uses the fibonacci heap implementation to store the elements.

const queue = new PriorityQueue<number>()

Dequeue

A Dequeue merge a Stack and a Queue, so both type of functions are usable (enqueue, dequeue, push, pop, head, top)

export interface IDequeue<E> extends IQueue<E>, IStack<E> { }

const dequeue = new Dequeue<number>()

Stacks

Stacks have the following interface:

export interface IStack<E> extends ICollection<E> {
  comparator: Comparator<E>
  push(e: E): void
  pop(): E
  top(): E
  contains(e: E): boolean
}

Stack

Like the list and queue, also the stack has a reference implementation with native arrays for benchmarking.

const stack = new Stack<number>()

LinkedStack

The linked stack is an implementation with 1 pointer to the top of the stack. Each node knows the previous one in the stack.

const stack = new LinkedStack<number>()

Heap

This package provides a tested fibonacci heap implementation.

The fibonacci heap has the following interface:

export interface IFibonacciHeap<E> extends ICollection<E> {
  rootList: HeapNode<E>
  minNode: HeapNode<E>
  insert(element: E): HeapNode<E>
  delete(node: HeapNode<E>): HeapNode<E>
  decreaseKey(node: HeapNode<E>, newValue: E): void
  minimum(): HeapNode<E>
  extractMin(): HeapNode<E>
  union(heap: IFibonacciHeap<E>): void
  extractNeighbours(node: HeapNode<E>, includeSelf?: boolean): CyclicDoublyLinkedList<HeapNode<E>>
  extractChildren(node: HeapNode<E>): CyclicDoublyLinkedList<HeapNode<E>>
}

const heap = new FibonacciHeap<number>()

and a heap node looks like:

export type HeapNode<E> = {
  value: E
  degree: number
  marked: boolean
  left: HeapNode<E>
  right: HeapNode<E>
  parent?: HeapNode<E>
  child?: HeapNode<E>
}

Sorting

There are 2 sorting algorithmen's provided with the implementation. One quicksort, and one heapsort variant using a fibonacci heap. The heapsort can be run on Iterables and the quicksort on ICollection.

Quicksort

The quicksort algorithm has the following function signature and returns a sorted collection, which creation must be passed as factory function (third parameter):

function quicksort<V>(
        collection: ICollection<V>,
        comparator: Comparator<V>,
        factory: () => ICollection<V>
): ICollection<V> {}

A comparator like the following (for numbers) must be specified for sorting the collection:

function numberComparatorASC(n1: number, n2: number) {
  if (n1 === n2) return Ordering.EQ // 0
  if (n1 < n2) return Ordering.LT // -1

  return Ordering.GT // 1
}

It's also possible to pass a comparator which returns bigger numbers.

Heapsort

Sorting a list using a FibonacciHeap has the following function signature:

function heapSort<V>(A: Iterable<V>, comparator: Comparator<V>): FibonacciHeap<V> {}

Package detail

@avensio/shared

readme