# graph-data-structure

A [graph data structure](<https://en.wikipedia.org/wiki/Graph_(abstract_data_type)>) with [topological sort](https://en.wikipedia.org/wiki/Topological_sorting).

This library provides a minimalist implementation of a directed graph data structure. Nodes are represented by unique strings or any other object. Internally, an [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list) is used to represent nodes and edges.

The primary use case for this library is in implementing [dataflow programming](https://en.wikipedia.org/wiki/Dataflow_programming) or [reactive programming](https://en.wikipedia.org/wiki/Reactive_programming). The key algorithm necessary for these is topological sorting, to get an ordering of nodes such that for each edge (**u** -> **v**), **u** comes before **v** in the sorted order. The topological sorting algorithm exposed here has modifications useful for computing the order in which functions in a data flow graph should be executed, namely specifying source nodes for propagation and specifying to exclude the source nodes themselves from the result.

**Table of Contents**

- [Installing](#installing)
- [Examples](#examples)
  - [ABC](#abc)
  - [Getting Dressed](#getting-dressed)
- [API Reference](#api-reference)

## Installing

This library is distributed only via [NPM](npmjs.com). Install by running

`npm install graph-data-structure`

Require it in your code like this.

```javascript
import {
  Graph,
  serializeGraph,
  deserializeGraph,
  topologicalSort,
  shortestPath,
} from 'graph-data-structure';
```

## Examples

### ABC

Start by creating a new **[Graph](#graph)** object.

```javascript
var graph = new Graph();
```

Add some nodes and edges with **[addNode](#add-node)** and **[addEdge](#add-edge)**.

```javascript
graph.addNode('a');
graph.addNode('b');
graph.addEdge('a', 'b');
```

Nodes are added implicitly when edges are added.

```javascript
graph.addEdge('b', 'c');
```

Now we have the following graph. <img src="https://cloud.githubusercontent.com/assets/68416/15385597/44a10522-1dc0-11e6-9054-2150f851db46.png">

[Topological sorting](https://en.wikipedia.org/wiki/Topological_sorting) can be done by invoking the standalone function **[topologicalSort](#topological-sort)** like this.

```javascript
topologicalSort(graph); // Returns ["a", "b", "c"]
```

### Getting Dressed

Here's an example of topological sort with getting dressed (from Cormen et al. "Introduction to Algorithms" page 550).

<p align="center">
  <img src="https://cloud.githubusercontent.com/assets/68416/15385742/36f76410-1dc1-11e6-9fac-a8e41379c795.png">
</p>

```javascript
const graph = new Graph();
graph
  .addEdge('socks', 'shoes')
  .addEdge('shirt', 'belt')
  .addEdge('shirt', 'tie')
  .addEdge('tie', 'jacket')
  .addEdge('belt', 'jacket')
  .addEdge('pants', 'shoes')
  .addEdge('underpants', 'pants')
  .addEdge('pants', 'belt');

// prints [ "underpants", "pants", "shirt", "tie", "belt", "jacket", "socks", "shoes" ]
console.log(topologicalSort(graph));
```

For more detailed example code that shows more methods, have a look at the [tests](https://github.com/datavis-tech/graph-data-structure/blob/master/test.js).

## API Reference

- [Creating a Graph](#creating-a-graph)
- [Adding and Removing Nodes](#adding-and-removing-nodes)
- [Adding and Removing Edges](#adding-and-removing-edges)
- [Querying the Graph](#querying-the-graph)
- [Serialization](#serialization)
- [Graph Algorithms](#graph-algorithms)

### Creating a Graph

<a name="graph" href="#graph">#</a> <b>Graph</b>([<i>serialized</i>])

Constructs an instance of the graph data structure.

The optional argument _serialized_ is a serialized graph that may have been generated by **[serializeGraph](#serializeGraph)**. If _serialized_ is present, it is deserialized by invoking **[deserializeGraph(mySerializedObject)](#deserializeGraph)**.

### Adding and Removing Nodes

<a name="add-node" href="#add-node">#</a> <i>graph</i>.<b>addNode</b>(<i>node</i>)

Adds a node to the graph. Returns _graph_ to support method chaining. If the given _node_ was already added to the graph, this function does nothing.

<a name="remove-node" href="#remove-node">#</a> <i>graph</i>.<b>removeNode</b>(<i>node</i>)

Removes the specified node. Returns _graph_ to support method chaining. The argument _node_ is a string or object identifier for the node to remove. This function also removes all edges connected to the specified node, both incoming and outgoing.

**Note:** You have to remove them using the exact same reference as when they were created. One can use getNode() to retrieve such reference.

### Adding and Removing Edges

<a name="add-edge" href="#add-edge">#</a> <i>graph</i>.<b>addEdge</b>(<i>u</i>, <i>v</i>[,<i>weight</i>])

Adds an edge from node _u_ to node _v_. Returns _graph_ to support method chaining. The arguments _u_ and _v_ are node references (either objects or strings). This function also adds _u_ and _v_ as nodes if they were not already added.

The last argument _weight_ (optional) specifies the weight of this edge.

<a name="remove-edge" href="#remove-edge">#</a> <i>graph</i>.<b>removeEdge</b>(<i>u</i>, <i>v</i>)

Removes the edge from node _u_ to node _v_. Returns _graph_ to support method chaining. The arguments _u_ and _v_ are node references. This function does not remove the nodes _u_ and _v_. Does nothing if the edge does not exist.

<a name="has-edge" href="#has-edge">#</a> <i>graph</i>.<b>hasEdge</b>(<i>u</i>, <i>v</i>)

Returns `true` if there exists an edge from node _u_ to node _v_. Returns `false` otherwise.

### Working with Edge Weights

<a name="set-edge-weight" href="#set-edge-weight">#</a> <i>graph</i>.<b>setEdgeWeight</b>(<i>u</i>, <i>v</i>, <i>weight</i>)

Sets the _weight_ (a number) of the edge from node _u_ to node _v_.

<a name="get-edge-weight" href="#get-edge-weight">#</a> <i>graph</i>.<b>getEdgeWeight</b>(<i>u</i>, <i>v</i>)

Gets the _weight_ of the edge from node _u_ to node _v_. If no weight was previously set on this edge, then the value 1 is returned.

### Querying the Graph

<a name="adjacent" href="#adjacent">#</a> <i>graph</i>.<b>adjacent</b>(<i>node</i>)

Gets the adjacent node list for the specified node. The argument _node_ is a node reference (object or string). Returns a `Set` of adjacent node references or `undefined` if the node is not found.

### Serialization

<a name="serializeGraph" href="#serializeGraph">#</a> <b>serializeGraph</b>(<i>graph</i>)

Serializes the graph. Returns an object with the following properties.

- `nodes` An array of objects, each representing a node reference.
- `links` An array of objects representing edges, each with the following properties.
  - `source` The node reference of the source node (**u**).
  - `target` The node reference of the target node (**v**).
  - `weight` The weight of the edge between the source and target nodes.

Here's example code for serializing a graph.

```javascript
var graph = new Graph();
graph.addEdge('a', 'b');
graph.addEdge('b', 'c');
var serialized = serializeGraph(graph);
```

<a name="deserializeGraph" href="#deserializeGraph">#</a> <b>deserializeGraph</b>(<i>serialized</i>)

Deserializes the given serialized graph. Returns a new _graph_. The argument _serialized_ is a graph representation with the structure described in **[serializeGraph](#serializeGraph)**.

### Graph Algorithms

<a name="topological-sort" href="#topological-sort">#</a> <b>topologicalSort</b>(<i>graph</i>)

Performs [Topological Sort](

https://en.wikipedia.org/wiki/Topological_sorting). Returns an array of node identifier strings. The returned array includes nodes in topologically sorted order. This means that for each visited edge (**u** -> **v**), **u** comes before **v** in the topologically sorted order.

Note: this function raises a `CycleError` when the input is not a DAG.

<a name="shortest-path" href="#shortest-path">#</a> <b>shortestPath</b>(<i>graph</i>, <i>sourceNode</i>, <i>destinationNode</i>)

Performs [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). Returns an object with two properties: `nodes`, an array of node references representing the path, and `weight`, the total weight of the path.

```javascript
var result = shortestPath(graph, 'a', 'c');
console.log(result.nodes); // Prints the array of nodes in the shortest path
console.log(result.weight); // Prints the total weight of the path
```

<a name="shortest-path" href="#shortest-path">#</a> <b>shortestPath</b>(<i>graph</i>, <i>sourceNode</i>, <i>destinationNode</i>, <i>nextWeightFn</i>)

Calculates the weight based on the custom function.

```javascript
import type { NextWeightFnParams } from '../../types.js';
function multiplyWeightFunction(wp: NextWeightFnParams): number {
    if (wp.currentPathWeight === undefined) {
        return wp.edgeWeight;
    }
    return wp.edgeWeight * wp.currentPathWeight;
}
var result = shortestPath(graph, 'a', 'c', multiplyWeightFunction);
console.log(result.nodes); // Prints the array of nodes in the shortest path
console.log(result.weight); // Prints the total weight of the path
```

<p align="center">
  <a href="https://datavis.tech/">
    <img src="https://cloud.githubusercontent.com/assets/68416/15298394/a7a0a66a-1bbc-11e6-9636-367bed9165fc.png">
  </a>
</p>
```