graph-data-structure

A graph data structure>) with topological sort.

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 is used to represent nodes and edges.

The primary use case for this library is in implementing dataflow programming or 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
- Examples
- ABC
- Getting Dressed
- API Reference

Installing

This library is distributed only via NPM. 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

$3

Start by creating a new Graph object.

`javascript
var graph = new Graph();
`

Add some nodes and edges with addNode and addEdge.

`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.

Topological sorting can be done by invoking the standalone function topologicalSort like this.

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

$3

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





`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.

API Reference

- Creating a Graph
- Adding and Removing Nodes
- Adding and Removing Edges
- Querying the Graph
- Serialization
- Graph Algorithms

$3

# Graph([serialized])

Constructs an instance of the graph data structure.

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

$3

# graph.addNode(node)

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.

# graph.removeNode(node)

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.

$3

# graph.addEdge(u, v[,weight])

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.

# graph.removeEdge(u, v)

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.

# graph.hasEdge(u, v)

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

$3

# graph.setEdgeWeight(u, v, weight)

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

# graph.getEdgeWeight(u, v)

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.

$3

# graph.adjacent(node)

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.

$3

# serializeGraph(graph)

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);
`

# deserializeGraph(serialized)

Deserializes the given serialized graph. Returns a new _graph_. The argument _serialized_ is a graph representation with the structure described in serializeGraph.

$3

# topologicalSort(graph)

Performs https://en.wikipedia.org/wiki/Topological_sorting" class="text-primary hover:underline" target="_blank" rel="noopener noreferrer">Topological Sort. 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.

# shortestPath(graph, sourceNode, destinationNode)

Performs Dijkstra's 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
`

# shortestPath(graph, sourceNode, destinationNode, nextWeightFn)

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
`








``