# typescript-graph

This library provides some basic graph data structures and algorithms.

## Stats

StarsIssuesVersionUpdatedCreatedSize
typescript-graph
1320.3.02 months ago2 years ago

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'

// Identify the node type to be used with the graph
type NodeType = { name: string, count: number, metadata: { [string: string]: string } }
// Define a custom identity function with which to identify nodes
const graph = new Graph<NodeType>((n: NodeType) => n.name)

// Insert nodes into the graph
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'}})

// Add edges between the nodes we created.

// Get a node
const node: NodeType = graph.getNode(node2);``````

## Examples

### Creating a directed graph and detecting cycles.

``````import { DirectedGraph, DirectedAcyclicGraph } from 'typescript-graph'

// Create the graph
type NodeType = { name: string, count: number }
const graph = new DirectedGraph<NodeType>((n: NodeType) => n.name)

// Insert nodes into the graph
const node1 = graph.insert({name: 'node1', count: 45})
const node2 = graph.insert({name: 'node2', count: 5})
const node3 = graph.insert({name: 'node3', count: 15})

// Check for cycles
console.log(graph.isAcyclic()) // true

// Add edges between the nodes we created.

// Check for cycles again
console.log(graph.isAcyclic()) // still true

// Converts the graph into one that enforces acyclicality
const dag = DirectedAcyclicGraph.fromDirectedGraph(graph)

// Try to add an edge that will cause an cycle
dag.addEdge(node3, node1) // throws an exception

// You can add the edge that would cause a cycle on the preview graph

// Check for cycles again
console.log(graph.isAcyclic()) // now false

DirectedAcyclicGraph.fromDirectedGraph(graph) // now throws an exception because graph is not acyclic``````

### Creating a directed acyclic graph and getting the nodes in topological order

``````import { DirectedAcyclicGraph } from 'typescript-graph'

// Create the graph
type NodeType = { name: string }
const graph = new DirectedAcyclicGraph<NodeType>((n: NodeType) => n.name)

// Insert nodes into the graph
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'})