graph-data-structure

graph-data-structure

A graph data structure with topological sort algorithm.

Usage

If you are using NPM, install the library by running

npm install graph-data-structure

Require it in your code like this.

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

Create a graph instance.

var graph = Graph();

Add some nodes and edges.

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

Nodes are added implicitly when edges are added.

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

Topological sort can be invoked like this.

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

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

var graph = Graph();

// Shoes depend on socks.
// Socks need to be put on before shoes.
graph.addEdge("socks", "shoes");

graph.addEdge("shirt", "belt");
graph.addEdge("shirt", "tie");
graph.addEdge("tie", "jacket");
graph.addEdge("belt", "jacket");
graph.addEdge("pants", "shoes");
graph.addEdge("underpants", "pants");
graph.addEdge("pants", "belt");

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

For more detailed example code that shows more methods, have a look at the tests.

API Reference

Methods on graphs include:

• addNode(node) Adds a node to the graph, accepts a string node identifier. If node was already added, this function does nothing.
• removeNode(node) Removes a node from the graph. Also removes incoming and outgoing edges.
• nodes() List all nodes in the graph.
• adjacent(node) Gets the adjacent node list for the given node. This is the set of nodes for which there is an incoming edge from the given node.
• addEdge(u, v) Adds an edge from node u to node v. Implicitly adds the nodes if they were not already added.
• removeEdge(u, v) Removes the edge from node u to node v. Does not remove the nodes. Does nothing if the edge does not exist.
• depthFirstSearch(sourceNodes, includeSourceNodes) Depth First Search algorithm, inspired by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604. This variant includes an additional option includeSourceNodes to specify whether to include or exclude the source nodes from the result (true by default). If sourceNodes is not specified, all nodes in the graph are used as source nodes.
• topologicalSort(sourceNodes, includeSourceNodes) The topological sort algorithm yields a list of visited nodes such that for each visited edge (u, v), u comes before v in the list. Amazingly, this comes from just reversing the result from depth first search. Inspired by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613. This variant includes an additional option includeSourceNodes to specify whether to include or exclude the source nodes from the result (true by default). If sourceNodes is not specified, all nodes in the graph are used as source nodes.

Similar packages

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.