This is a package containing multiple datastructures and some graph algorithms written in typescript with no dependencies usable with commonjs, esm and in the browser. Also some other handy utility function are contained in this package.

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>
  </body>
</html>

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>include npm package as ES-module</title>
  </head>
  <body>
    <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
- Density of the graph
order(): number
size(): number
isCyclic(): boolean
isAcyclic(): boolean
isTree(): boolean
isForest(): boolean
isDirected(): boolean
isConnected(): boolean
isConnectedFrom(v: V): boolean
isStronglyConnectedFrom(v: V): boolean
isMixed(): boolean
isDense(): boolean
isSparse(): boolean

Algorithms

depthFirstSearch(startVertex: V)
breadthFirstSearch(startVertex: V)
shortestPath(from: V, to: V)
kShortestPaths(from: V, to: V, k: number)
minimalSpanningTree()
topologicalSorting()
parallelTopologicalSorting()
connectedComponents()
strongConnectedComponents()
checkForCycles()
checkForNegativeCycles()
inferCycles()

Utility functions

createEdge(from: V, to: V, title?: string, directed?: boolean, weight?: number): E
addEdge(e: E): boolean
removeEdge(e: E): boolean
createVertex(title?: string, point?: Point, object?: any): V
addVertex(v: V): boolean
removeVertex(v: V): boolean
c(from: V, to: V): number

Lists

All lists implement the interface IList:

export interface IList<E> extends ICollection<E>, ISortable<E> {
  comparator: Comparator<E>
  add(e: E): void
  addAll(c: Iterable<E>): void
  get(index: number): E
  set(index: number, e: E | null): boolean
  slice(startIndex: number, endIndex: number): IList<E>
  slice2(startIndex: number, endIndex: number): IList<E>
  splice(startIndex: number, deleteCount: number): IList<E>
  map<V>(fn: (e: E) => V): IList<V>
  filter(predicate: (e: E) => boolean): IList<E>
  remove(index: number): E
  includes(e: E): boolean
  equals(l: IList<E>): boolean
  indexOf(e: E): number
  reverseIterator(): Generator<E>
}

The interface ICollection adds the following to the lists:

export interface ICollection<E> extends Iterable<E> {
  size: number
  isEmpty(): boolean
  clear(): void
}

and further, Iterable adds:

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

and ISortable adds:

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

There are 2 sorting algorithmen's provided with the implementation. One quicksort, and one heapsort variante using a fibonacci heap.

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 list = 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)

const dequeue = new Dequeue<number>()

Stacks

Stacks have the following interface:

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

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

One of the quickest ways of sorting a collection is the quicksort. Additionally to this sorting algorithm a heapsort variant is provided by this package, using a FibonacciHeap for sorting.

Quicksort

The quicksort has the following function signature:

quicksort<V>(A: IList<V>, comparator: Comparator<V>): IList<V>

Heapsort

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

heapSort<V>(A: IList<V>, comparator: Comparator<V>): FibonnaciHeap<V>

@avensio/shared

Graph

Graph Properties

Algorithms

Utility functions

Lists

List

LinkedList

DoublyLinkedList

CyclicLinkedList

Queues

Queue

LinkedQueue

PriorityQueue

Dequeue

Stacks

Stack

LinkedStack

Heap

Sorting

Quicksort

Heapsort

Readme

Keywords

Package Sidebar

Install

Repository

Homepage

Weekly Downloads

Version

License

Unpacked Size

Total Files

Last publish

Collaborators

@avensio/shared

Graph

Graph Properties

Algorithms

Utility functions

Lists

List

LinkedList

DoublyLinkedList

CyclicLinkedList

Queues

Queue

LinkedQueue

PriorityQueue

Dequeue

Stacks

Stack

LinkedStack

Heap

Sorting

Quicksort

Heapsort

Readme

Keywords

Package Sidebar

Install

Repository

Homepage

DownloadsWeekly Downloads

Version

License

Unpacked Size

Total Files

Last publish

Collaborators

Weekly Downloads