toposort
Advanced tools
Package description
The toposort npm package is used for sorting directed acyclic graphs (DAG) into a topological order. It is useful for tasks where dependencies need to be resolved in a specific sequence, such as task scheduling, resolving package dependencies, or processing data with dependencies.
Topological sorting
This feature allows you to sort a list of edges representing dependencies into a topological order. The edges are pairs where the first element depends on the second one.
const toposort = require('toposort');
const edges = [
['task1', 'task2'],
['task2', 'task3'],
['task3', 'task4']
];
const sorted = toposort(edges);
console.log(sorted); // ['task1', 'task2', 'task3', 'task4']Dagre is a JavaScript library that lays out directed graphs on the client-side. While toposort focuses on sorting nodes in a topological order, dagre provides the additional functionality of graph layout for visualization purposes.
Graphlib is a library that provides data structures for undirected and directed multi-graphs along with algorithms to use with them. It includes topological sorting as well as other algorithms like shortest path. It is more comprehensive than toposort, which is specialized for topological sorting.
Dependency-graph is a simple dependency graph library that can be used to handle and sort dependencies. It offers a higher-level API compared to toposort, allowing for the addition of nodes and dependencies in a more object-oriented manner.
Readme
Sort directed acyclic graphs
npm install toposort or component install marcelklehr/toposort
then in your code:
toposort = require('toposort')
We want to sort the following graph.
// First, we define our edges.
var graph = [
['put on your shoes', 'tie your shoes']
, ['put on your shirt', 'put on your jacket']
, ['put on your shorts', 'put on your jacket']
, ['put on your shorts', 'put on your shoes']
]
// Now, sort the vertices topologically, to reveal a legal execution order.
toposort(graph)
// [ 'put on your shirt'
// , 'put on your shorts'
// , 'put on your jacket'
// , 'put on your shoes'
// , 'tie your shoes' ]
(Note that there is no defined order for graph parts that are not connected -- you could also put on your jacket after having tied your shoes...)
It is usually more convenient to specify dependencies instead of "sequences".
// This time, edges represent dependencies.
var graph = [
['tie your shoes', 'put on your shoes']
, ['put on your jacket', 'put on your shirt']
, ['put on your shoes', 'put on your shorts']
, ['put on your jacket', 'put on your shorts']
]
toposort(graph)
// [ 'tie your shoes'
// , 'put on your shoes'
// , 'put on your jacket'
// , 'put on your shirt'
// , 'put on your shorts' ]
// Now, reversing the list will reveal a legal execution order.
toposort(graph).reverse()
// [ 'put on your shorts'
// , 'put on your shirt'
// , 'put on your jacket'
// , 'put on your shoes'
// , 'tie your shoes' ]
[node1, node2] (vertices needn't be strings but can be of any type).Returns: {Array} a list of vertices, sorted from "start" to "end"
Throws an error if there are any cycles in the graph.
nodes here.This is a convenience method that allows you to define nodes that may or may not be connected to any other nodes. The ordering of unconnected nodes is not defined.
Returns: {Array} a list of vertices, sorted from "start" to "end"
Throws an error if there are any cycles in the graph.
Run the tests with node test.js.
MIT License
FAQs
Topological sort of directed ascyclic graphs (like dependecy lists)
The npm package toposort receives a total of 4,994,875 weekly downloads. As such, toposort popularity was classified as popular.
We found that toposort demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
UnitedHealth Group disclosed that the ransomware attack on Change Healthcare compromised protected health information for millions in the U.S., with estimated costs to the company expected to reach $1 billion.
Security News
GitHub is susceptible to a CDN flaw that allows attackers to host malware on any public repository.
Security News
At Node Congress, Socket CEO Feross Aboukhadijeh uncovers the darker aspects of open source, where applications that rely heavily on third-party dependencies can be exploited in supply chain attacks.