A TypeScript library for graph data structures.
The data structures available include:
- Graph
- A graph containing an array of nodes and an array of edges. Each edge is a pair of indices. Each edge index is the index of its nodes in the nodes array.
- GraphNode
- A node in a graph. It has a data property and neighbors property. The data property has the data associated with a node. The neighbors are the nodes it is connected to.
- TreeNode
-
A node in a tree. It is an extension of the
GraphNode. It has a parent property, which maybe a node ornull. It also has achildrenproperty which has the children of the node. - ChainNode
-
A node in a chain (doubly-linked list). It has
previousandnextproperties, which maybe a node ornull. - ListNode
-
A node in a list (singly-linked list). It has a
nextproperty which maybe a node ornull.
The nodes support the following traversal algorithms:
- breadth-first
- Level-order traversal.
- depth-first
-
- post-order
- pre-order
npm install @mishieck/graph-jsbun install @mishieck/graph-jsimport { GraphNode, Traversal } from "@mishieck/graph-js";
const root = new GraphNode({ data: 1, neighbors: [] });
const childLeft = new GraphNode({ data: 2, neighbors: [] });
const childRight = new GraphNode({ data: 3, neighbors: [] });
const grandChildLeftLeft = new GraphNode({ data: 4, neighbors: [] });
const grandChildLeftRight = new GraphNode({ data: 5, neighbors: [] });
const grandChildRightLeft = new GraphNode({ data: 6, neighbors: [] });
const grandChildRightRight = new GraphNode({ data: 7, neighbors: [] });
childLeft.neighbors = [grandChildLeftLeft, grandChildLeftRight];
childRight.neighbors = [grandChildRightLeft, grandChildRightRight];
root.neighbors = [childLeft, childRight];
let data = [...root.traverse(Traversal.LevelOrder)].map(({ data }) => data);
console.log(data); // [1, 2, 3, 4, 5, 6, 7]
data = [...root.traverse(Traversal.PostOrder)].map(({ data }) => data);
console.log(data); // [4, 5, 2, 6, 7, 3, 1]
data = [...root.traverse(Traversal.PreOrder)].map(({ data }) => data);
console.log(data); // [1, 2, 4, 5, 3, 6, 7]