import { _ } from '@kitmi/utils';
/**
* @class
*/
class TopoSort {
/**
* Map of nodes to a set of nodes as dependents, <string, Set.<string>>
* @member {object}
*/
mapOfDependents = {};
/** -
* Map of nodes to a set of nodes as dependencies, <string, Set.<string>>
* @member {object}
*/
mapOfDependencies = {};
/**
* Add edges(or one edge, if values is non-array).
* @param {string} dependency - Incoming node (dependency)
* @param {string|array} dependents - Outgoing node or nodes
*/
add(dependency, newDependents) {
// cast to array
newDependents = Array.isArray(newDependents) ? newDependents : newDependents == null ? [] : [newDependents];
// get the existing dependents
const dependents = this.mapOfDependents[dependency];
newDependents.forEach((dependent) => {
// get the existing dependencies
const dependencies = this.mapOfDependencies[dependent];
if (!dependencies) {
// new set of dependencies
this.mapOfDependencies[dependent] = new Set([dependency]);
} else {
dependencies.add(dependency);
}
if (dependents) {
dependents.add(dependent);
}
});
if (!dependents) {
// new set of dependents
this.mapOfDependents[dependency] = new Set(newDependents);
}
}
depends(node, dependencies) {
// cast to array
dependencies = Array.isArray(dependencies) ? dependencies : dependencies == null ? [] : [dependencies];
// get the existing dependencies
const _dependencies = this.mapOfDependencies[node];
if (!_dependencies) {
// new set of dependencies
this.mapOfDependencies[node] = new Set(dependencies);
} else {
dependencies.forEach((dependency) => {
_dependencies.add(dependency);
});
}
// get the existing dependents
dependencies.forEach((dependency) => {
const dependents = this.mapOfDependents[dependency];
if (dependents) {
dependents.add(node);
} else {
// new set of dependents
this.mapOfDependents[dependency] = new Set([node]);
}
});
// Ensure node is in mapOfDependents with an empty set if it has no dependents
if (!this.mapOfDependents[node]) {
this.mapOfDependents[node] = new Set();
}
}
hasDependency(node) {
return (this.mapOfDependencies[node] && this.mapOfDependencies[node].size > 0) || false;
}
hasDependent(node) {
return (this.mapOfDependents[node] && this.mapOfDependents[node].size > 0) || false;
}
/**
* Sort the graph. Circular graph throw an error with the circular nodes info.
* Implementation of http://en.wikipedia.org/wiki/Topological_sorting#Algorithms
* Reference: http://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf
* @return {Array} Sorted list
*/
sort() {
// The list contains the final sorted nodes.
const l = [];
// Find all the initial 0 incoming edge nodes. If not found, this is a circular graph, cannot be sorted.
const nodesWithDependents = Object.keys(this.mapOfDependents);
const nodesWithDependencies = Object.keys(this.mapOfDependencies);
const initialNodes = new Set(nodesWithDependents);
nodesWithDependencies.forEach((nodeHasDependency) => initialNodes.delete(nodeHasDependency));
// Add nodes with no dependencies to initialNodes
nodesWithDependencies.forEach((node) => {
if (this.mapOfDependencies[node].size === 0) {
initialNodes.add(node);
}
});
// List of nodes with no unsorted dependencies
const s = [...initialNodes];
const allNodes = new Set(nodesWithDependents.concat(nodesWithDependencies));
// number of unsorted nodes. If it is not zero at the end, this graph is a circular graph and cannot be sorted.
let unsorted = allNodes.size;
if (s.length === 0 && (nodesWithDependencies.length === 0 || nodesWithDependents.length === 0)) {
// only 1 node in the graph, no need to sort.
return Array.from(allNodes);
}
const numWithDependencies = _.mapValues(this.mapOfDependencies, (node) => node.size);
while (s.length !== 0) {
const n = s.shift();
l.push(n);
// decrease unsorted count, node n has been sorted.
--unsorted;
// n node might have no dependency, so have to check it.
const dependentsOfN = this.mapOfDependents[n];
if (dependentsOfN) {
// decease n's adjacent nodes' incoming edges count. If any of them has 0 incoming edges, push them into s get them ready for detaching from the graph.
for (const dependentOfN of dependentsOfN) {
if (--numWithDependencies[dependentOfN] === 0) {
// no unsorted dependencies
s.push(dependentOfN);
}
}
}
}
// If there are unsorted nodes left, this graph is a circular graph and cannot be sorted.
// At least 1 circular dependency exist in the nodes with non-zero incoming edges.
if (unsorted !== 0) {
const circular = [];
for (const node in numWithDependencies) {
if (numWithDependencies[node] !== 0) {
circular.push(node);
}
}
throw new Error(
'At least 1 circular dependency in nodes: \n\n' + circular.join('\n') + '\n\nGraph cannot be sorted!'
);
}
return l;
}
}
export default TopoSort;