@seriouscoderone/toposort
v2.1.2
Published
Topological sort of directed ascyclic graphs (like dependecy lists)
Downloads
762
Maintainers
Readme
@qiwi/toposort
Fork of toposort with updated dependencies and some new features
Why?
Toposort is wonderful, but we also need to know which parts of graph can be handled in parallel mode.
You can simultaneously handle unconnected parts (components in graph theory) of a graph.
Also, you can analyze dependencies and dependants of graph nodes to find independent nodes to parallelize their processing.
So, toposortExtra returns maps of dependencies and dependants and a list of graph components.
Installation
yarn add @qiwi/toposort
npm i @qiwi/toposort
Usage
toposortExtra({ nodes, edges, throwOnCycle })
Returns an array of the graph components
The graph above is used in the code below.
import { toposortExtra } from '@qiwi/toposort'
const res = toposortExtra({ edges: [[1, 3], [1, 2], [2, 4], [2, 5], [6, 7], [6, 8], [9, 8]] }) // see diagramm above
console.log(res)
/*
{
sources: [1, 6, 9], // nodes which do not have incoming edges, e.g. dependencies/parents
prev: new Map([ // map of dependencies
[1, []],
[3, [1]],
[2, [1]],
[4, [2]],
[5, [2]],
[6, []],
[7, [6]],
[8, [6, 9]],
[9, []],
]),
next: new Map([ // map of dependants
[1, [2, 3]],
[3, []],
[2, [4, 5]],
[4, []],
[5, []],
[6, [7, 8]],
[7, []],
[8, []],
[9, [8]],
]),
graphs: [ // list of graph components (unconnected parts)
{
nodes: [1, 2, 3, 4, 5], // list of component nodes
sources: [1] // list of component start nodes
},
{
nodes: [6, 7, 8, 9],
sources: [6, 9]
}
]
}
*/
The same result, but also checks edge nodes to be in the nodes
list
const res = toposortExtra({
nodes: [1, 2, 3, 4, 5, 6, 7, 8, 9],
edges: [[1, 3], [1, 2], [2, 4], [2, 5], [6, 7], [6, 8], [9, 8]]
})
console.log(res) // the same result
const res = toposortExtra({
nodes: [1, 2, 3, 4, 6, 7, 8, 9],
edges: [[1, 3], [1, 2], [2, 4], [2, 5], [6, 7], [6, 8], [9, 8]]
}) // Uncaught Error: Unknown node. There is an unknown node in the supplied edges.
You can also check the graph to be acyclic
toposortExtra({
edges: [[1, 2], [2, 3], [3, 1]],
throwOnCycle: true
}) // Uncaught Error: Cyclic dependency, node was:1
toposort(edges)
Marcelklehr's original toposort
import toposort from '@qiwi/toposort'
console.log(toposort([
[ '3', '2' ],
[ '2', '1' ],
[ '6', '5' ],
[ '5', '2' ],
[ '5', '4' ]
]
)) // [ '3', '6', '5', '2', '1', '4' ]
array(nodes, edges)
Marcelklehr's original toposort.array.
Checks edge nodes for presence in the nodes array
import { array } from '@qiwi/toposort'
console.log(array(
['1', '2', '3', '4', '5', '6'],
[
[ '3', '2' ],
[ '2', '1' ],
[ '6', '5' ],
[ '5', '2' ],
[ '5', '4' ]
]
)) // [ '3', '6', '5', '2', '1', '4' ]