graph-data-structure

What is graph-data-structure?

The graph-data-structure npm package provides a simple and efficient way to create and manipulate graph data structures in JavaScript. It supports various graph operations such as adding nodes and edges, finding paths, and detecting cycles.

What are graph-data-structure's main functionalities?

Add Nodes and Edges

This feature allows you to add nodes and edges to the graph. The code sample demonstrates how to create a graph, add nodes 'A' and 'B', and then add an edge from 'A' to 'B'.

const Graph = require('graph-data-structure');
const graph = Graph();
graph.addNode('A');
graph.addNode('B');
graph.addEdge('A', 'B');
console.log(graph.serialize());

Find Paths

This feature allows you to find paths between nodes in the graph. The code sample demonstrates how to find a path from node 'A' to node 'C' through node 'B'.

const Graph = require('graph-data-structure');
const graph = Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
const path = graph.path('A', 'C');
console.log(path);

Detect Cycles

This feature allows you to detect cycles in the graph. The code sample demonstrates how to detect a cycle in a graph where nodes 'A', 'B', and 'C' form a cycle.

const Graph = require('graph-data-structure');
const graph = Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'A');
const hasCycle = graph.hasCycle();
console.log(hasCycle);

Other packages similar to graph-data-structure

graphlib

Graphlib is a library for creating and manipulating directed graphs in JavaScript. It offers a rich set of features including graph serialization, pathfinding, and cycle detection. Compared to graph-data-structure, graphlib provides more advanced functionalities and is suitable for more complex graph operations.

cytoscape

Cytoscape is a graph theory library for visualizing and analyzing graphs. It supports a wide range of graph operations and provides extensive visualization capabilities. While graph-data-structure focuses on basic graph operations, Cytoscape is more geared towards visualization and complex graph analysis.

d3-graphviz

d3-graphviz is a library that integrates Graphviz with D3.js to create interactive graph visualizations. It is particularly useful for rendering graphs and visualizing their structure. Unlike graph-data-structure, which is more about graph manipulation, d3-graphviz excels in graph visualization.

README

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

var Graph = require("graph-data-structure");

Examples

ABC

To create a graph instance, invoke Graph as a constructor function.

var graph = Graph();

Add some nodes and edges with addNode and addEdge.

graph.addNode("a");
graph.addNode("b");
graph.addEdge("a", "b");

Nodes are added implicitly when edges are added.

graph.addEdge("b", "c");

Now we have the following graph.

Topological sorting can be done by invoking topologicalSort like this.

graph.topologicalSort(); // 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).

var 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(graph.topologicalSort());

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

Creating a Graph

# Graph([serialized])

Constructs an instance of the graph data structure.

The optional argument serialized is a serialized graph that may have been generated by serialize. If serialized is present, it is deserialized by invoking deserialize.

Adding and Removing Nodes

# graph.addNode(node)

Adds a node to the graph. Returns graph to support method chaining. The argument node is a string identifier that uniquely identifies the node within this graph instance. If a node with the same identifier 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 identifier for the node to remove. This function also removes all edges connected to the specified node, both incoming and outgoing.

Adding and Removing Edges

# 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 string identifiers for nodes. 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 string identifiers for nodes. 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.

Working with Edge Weights

# graph.setEdgeWeight(u, v, weight)

Sets the weight (a number) of the edge from node u to node v.

# graph.getEdgeWeight(u, v, weight)

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

# graph.nodes()

List all nodes in the graph. Returns an array of node identifier strings.

# graph.adjacent(node)

Gets the adjacent node list for the specified node. The argument node is a string identifier for a node. Returns an array of node identifier strings.

The "adjacent node list" is the Array of nodes for which there is an incoming edge from the given node. In other words, for all edges (u -> v) where u is the specified node, all values for v are in the adjacent node list.

# graph.indegree(node)

Computes the indegree (number of incoming edges) for the specified node.

# graph.outdegree(node)

Computes the outdegree (number of outgoing edges) for the specified node.

Serialization

# graph.serialize()

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

• nodes An array of objects, each with an id property whose value is a node identifier string.
• links An array of objects representing edges, each with the following properties.
  • source The node identifier string of the source node (u).
  • target The node identifier string 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.

var graph = Graph();
graph.addEdge("a", "b");
graph.addEdge("b", "c");
var serialized = graph.serialize();

The following will be the value of serialized.

{
  "nodes": [{ "id": "a" }, { "id": "b" }, { "id": "c" }],
  "links": [
    { "source": "a", "target": "b", "weight": 1 },
    { "source": "b", "target": "c", "weight": 1 }
  ]
}

This representation conforms to the convention of graph representation when working with D3.js force layouts. See also d3.simulation.nodes and d3.forceLinks.

# graph.deserialize(serialized)

Deserializes the given serialized graph. Returns graph to support method chaining. The argument serialized is a graph representation with the structure described in serialize. This function iterates over the serialized graph and adds the nodes and links it represents by invoking addNode and addEdge. The output from serialize can be used as the input to deserialize.

Graph Algorithms

# graph.depthFirstSearch([sourceNodes][, includesourcenodes][, errorOnCycle])

Performs Depth-first Search. Returns an array of node identifier strings. The returned array includes nodes visited by the algorithm in the order in which they were visited. Implementation inspired by pseudocode from Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604.

Arguments:

• sourceNodes (optional) - An array of node identifier strings. This specifies the subset of nodes to use as the sources of the depth-first search. If sourceNodes is not specified, all nodes in the graph are used as source nodes.
• includeSourceNodes (optional) - A boolean specifying whether or not to include the source nodes in the returned array. If includeSourceNodes is not specified, it is treated as true (all source nodes are included in the returned array).
• errorOnCycle (optional) - A boolean indicating that a CycleError should be thrown whenever a cycle is first encountered. Defaults to false.

# graph.hasCycle()

Checks if the graph has any cycles. Returns true if it does and false otherwise.

# graph.lowestCommonAncestors([node1][, node2])

Performs search of Lowest common ancestors. Returns an array of node identifier strings.

Arguments:

• node1 (required) - First node.
• node2 (required) - Second node.

# graph.topologicalSort([sourceNodes][, includesourcenodes])

Performs 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. Amazingly, this comes from simply reversing the result from depth first search. Inspired by by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613.

See depthFirstSearch for documentation of the arguments sourceNodes and includeSourceNodes.

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

# graph.shortestPath(sourceNode, destinationNode)

Performs Dijkstras Algorithm. Returns an array of node identifier strings. The returned array includes the nodes of the shortest path from source to destination node. The returned array also contains a weight property, which is the total weight over all edges in the path. Inspired by by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 658.