typescript-graph
This library provides some basic graph data structures and algorithms.
Full docs are availible here.
It supports undirected graphs, directed graphs and directed acyclic graphs (including inforcing acyclicality). It does not support weighted graphs at this time.
The graphs created with this library can have nodes of any type, however at present it does not support attaching metadata to edges.
The most useful functionality is the ability to compute cyclicality and topological sort order on [[DirectedAcyclicGraph
]]s. This can be used for determining things like task order or tracing dependencies.
Installing & Basic Usage
npm install 'typescript-graph'
import { Graph } from 'typescript-graph'
type NodeType = { name: string, count: number, metadata: { [string: string]: string } }
const graph = new Graph<NodeType>((n: NodeType) => n.name)
const node1 = graph.insert({name: 'node1', count: 45, metadata: {color: 'green'}})
const node2 = graph.insert({name: 'node2', count: 5, metadata: {color: 'red', style: 'normal'}})
const node3 = graph.insert({name: 'node3', count: 15, metadata: {color: 'blue', size: 'large'}})
graph.addEdge(node1, node2)
graph.addEdge(node2, node3)
const node: NodeType = graph.getNode(node2);
Examples
Creating a directed graph and detecting cycles.
import { DirectedGraph, DirectedAcyclicGraph } from 'typescript-graph'
type NodeType = { name: string, count: number }
const graph = new DirectedGraph<NodeType>((n: NodeType) => n.name)
const node1 = graph.insert({name: 'node1', count: 45})
const node2 = graph.insert({name: 'node2', count: 5})
const node3 = graph.insert({name: 'node3', count: 15})
console.log(graph.isAcyclic())
graph.addEdge(node1, node2)
graph.addEdge(node2, node3)
console.log(graph.isAcyclic())
const dag = DirectedAcyclicGraph.fromDirectedGraph(graph)
dag.addEdge(node3, node1)
graph.addEdge(node3, node1)
console.log(graph.isAcyclic())
DirectedAcyclicGraph.fromDirectedGraph(graph)
Creating a directed acyclic graph and getting the nodes in topological order
import { DirectedAcyclicGraph } from 'typescript-graph'
type NodeType = { name: string }
const graph = new DirectedAcyclicGraph<NodeType>((n: NodeType) => n.name)
const node1 = graph.insert({name: 'node1'})
const node2 = graph.insert({name: 'node2'})
const node3 = graph.insert({name: 'node3'})
const node4 = graph.insert({name: 'node4'})
const node5 = graph.insert({name: 'node5'})
graph.addEdge(node1, node2)
graph.addEdge(node2, node4)
graph.addEdge(node1, node3)
graph.addEdge(node3, node5)
graph.addEdge(node5, node4)
graph.topologicallySortedNodes()
License
MIT License
Author
Max Walker (max@maxwalker.me)