graph-builder

Graph Builder

A graph builder library for modeling, and traversing abstract graph structures.

This is a (incomplete) port of the guava graph library.

The main entry point for building the graph are the GraphBuilder for building a MutableGraph and ValueGraphBuilder for building a MutableValueGraph.

Graph Traversal

There is also a traverser which can perform different types of traversal of any graphs/trees (that implement SuccessorFunction, which all the Graphs created by the GraphBuilder do).

Examples

Creating a Graph

Create an undirected Mutablegraph:

• Inherits from Graph
• And BaseGraph

const { GraphBuilder } = require('graph-builder');

const graph = GraphBuilder.undirected().allowsSelfLoops(true).build();

Add some nodes:

graph.addNode("bread");

Add some edges (silently adds nodes too):

graph.putEdge("bread", "bread");
graph.putEdge("chocolate", "peanut butter");
graph.putEdge("peanut butter", "jelly");

Remove an edge:

graph.removeEdge("chocolate", "peanut butter");

Reading From the Graph

Everything returned is iterable.

Get connected nodes:

for (const n of graph.adjacentNodes("peanut butter")) {
  console.log(n);
}
// prints:
//   chocolate
//   jelly

Get all the edges:

for (const e of graph.edges()) {
  console.log(e.nodeU, ' => ', e.nodeV);
}
// prints:
//   bread  =>  bread
//   peanut butter  =>  chocolate
//   jelly  =>  peanut butter

Get all edges connected to "peanut butter":

for (const e of graph.incidentEdges("peanut butter")) {
  console.log(e.nodeU, ' => ', e.nodeV);
}
// prints:
//   chocolate  =>  peanut butter
//   jelly  =>  peanut butter

Get all the successors/predecessors of "peanut butter" (in an undirected graph, these are the same):

for (const n of graph.successors("peanut butter")) {
  console.log(n);
}
// prints:
//   chocolate
//   jelly
for (const n of graph.predecessors("peanut butter")) {
  console.log(n);
}
// prints:
//   chocolate
//   jelly

Or for a directed graph:

const graph = GraphBuilder.directed().allowsSelfLoops(true).build();
graph.putEdge("bread", "bread");
graph.putEdge("chocolate", "peanut butter");
graph.putEdge("peanut butter", "jelly");
for (const n of graph.successors("peanut butter")) {
  console.log(n);
}
// prints:
//   jelly
for (const n of graph.predecessors("peanut butter")) {
  console.log(n);
}
// prints:
//   chocolate

Traversing the Graph

The traversers return iterators.

Traverse a graph that looks like this (numbered breadth first):

 1     2
 | \   |
 3  4--5
 |
 6

const { GraphBuilder, Traversers } = require('graph-builder');
const graph = GraphBuilder.directed().allowsSelfLoops(true).build();
graph.putEdge(1, 3);
graph.putEdge(1, 4);
graph.putEdge(2, 5);
graph.putEdge(4, 5);
graph.putEdge(3, 6);

Iterate breadth first:

const nodeIterator = Traversers.forGraph(graph).breadthFirst(1, 2); // starting from root nodes, 1 & 2
console.log(Array.from(nodeIterator).join(', '));
// prints: 1, 2, 3, 4, 5, 6,

Iterate depth first preorder:

const nodeIterator = Traversers.forGraph(graph).depthFirstPreOrder(1, 2); // starting from root nodes, 1 & 2
console.log(Array.from(nodeIterator).join(', '));
// prints: 1, 3, 6, 4, 5, 2

Iterate depth first postorder:

const nodeIterator = Traversers.forGraph(graph).depthFirstPostOrder(1, 2); // starting from root nodes, 1 & 2
console.log(Array.from(nodeIterator).join(', '));
// prints: 6, 3, 5, 4, 1, 2

More

See the full API documentation for usage.

Full typescript typings are also provided.