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
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.
density(): number- Density of the graph
order(): numbersize(): numberisCyclic(): booleanisAcyclic(): booleanisTree(): booleanisForest(): booleanisDirected(): booleanisConnected(): booleanisConnectedFrom(v: V): booleanisStronglyConnectedFrom(v: V): booleanisMixed(): booleanisDense(): booleanisSparse(): boolean
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()
createEdge(from: V, to: V, title?: string, directed?: boolean, weight?: number): EaddEdge(e: E): booleanremoveEdge(e: E): booleancreateVertex(title?: string, point?: Point, object?: any): VaddVertex(v: V): booleanremoveVertex(v: V): booleanc(from: V, to: V): number
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 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])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>()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>()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 are implementing the interface IQueue and extends ICollection:
export interface IQueue<E> extends ICollection<E> {
enqueue(e: E): void
dequeue(): E
head(): E
}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>()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>()The priority queue uses the fibonacci heap implementation to store the elements.
const queue = new PriorityQueue<number>()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 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>
}Like the list and queue, also the stack has a reference implementation with native arrays for benchmarking.
const stack = new Stack<number>()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>()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>
}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.
The quicksort has the following function signature:
quicksort<V>(A: IList<V>, comparator: Comparator<V>): IList<V>Sorting a list using a FibonnaciHeap has the following function signature:
heapSort<V>(A: IList<V>, comparator: Comparator<V>): FibonnaciHeap<V>