Secure your code as it's written. Use Snyk Code to scan source code in minutes - no build needed - and fix issues immediately.
if (!compileGraph.hasNode(name)) {
compileGraph.setNode(name);
}
}
if (!compileGraph.hasNode(toName)) {
compileGraph.setNode(toName);
}
// reverse!
compileGraph.setEdge({v:toName, w:fromName});
});
});
// Apply topological sorting, Start at the leafs of the graphs (e.g. atoms) and go further
// up in the hierarchy
const o = graphlib.alg.topsort(compileGraph);
return this.nodes2patterns(o);
},
export function topologicalSortComponentDependencies(componentWithDependencies: ComponentWithDependencies): void {
const { graphDeps } = buildComponentsGraph([
componentWithDependencies.component,
...componentWithDependencies.allDependencies
]);
const componentId = componentWithDependencies.component.id.toString();
let sortedComponents;
if (!graphLib.alg.isAcyclic(graphDeps)) {
const circle = graphLib.alg.findCycles(graphDeps);
throw new GeneralError(
`unable to topological sort dependencies of ${componentId}, it has the following cyclic dependencies\n${circle}`
);
}
try {
sortedComponents = graphLib.alg.topsort(graphDeps);
const sortedComponentsIds = sortedComponents.map(s => graphDeps.node(s));
const sortedDependenciesIds = R.tail(sortedComponentsIds); // the first one is the component itself
const dependencies = sortedDependenciesIds.map(depId => {
const matchDependency = componentWithDependencies.dependencies.find(dependency => dependency.id.isEqual(depId));
if (!matchDependency) throw new Error(`topologicalSortComponentDependencies, ${depId.toString()} is missing`);
return matchDependency;
});
componentWithDependencies.dependencies = dependencies;
} catch (err) {
throw new GeneralError(`unable to topological sort dependencies of ${componentId}. Original error: ${err.message}`);
}
// there are circles but they are all from the same scope, add them to groupedArraySorted
// first, then, remove from the graph, so it will be possible to execute topsort
cycles.forEach(cycle => {
cycle.forEach(node => {
const id = graph.node(node);
addToGroupedSorted(id);
graph.removeNode(node);
});
});
}
// @todo: optimize in case each one of the ids has all its dependencies from the same scope,
// return groupedArrayFormat
let sortedComponents;
try {
sortedComponents = graphLib.alg.topsort(graph);
} catch (err) {
// should never arrive here, it's just a precaution, as topsort doesn't fail nicely
logger.error(err);
throw new Error(`fatal: graphlib was unable to topsort the components. circles: ${cycles}`);
}
const sortedComponentsIds = sortedComponents.map(s => graph.node(s)).reverse();
sortedComponentsIds.forEach(id => addToGroupedSorted(id));
return groupedArraySorted;
}
function detectCircularDeps(graph) {
const isAcyclic = graphlib.alg.isAcyclic(graph)
if (not(isAcyclic)) {
const cycles = graphlib.alg.findCycles(graph)
let msg = ['Your serverless.yml file has circular dependencies:']
forEachIndexed((cycle, index) => {
let fromAToB = cycle.join(' --> ')
fromAToB = `${(index += 1)}. ${fromAToB}`
const fromBToA = cycle.reverse().join(' <-- ')
const padLength = fromAToB.length + 4
msg.push(fromAToB.padStart(padLength))
msg.push(fromBToA.padStart(padLength))
}, cycles)
msg = msg.join('\n')
throw new Error(msg)
}
return graph
}
"use strict";
var util = require("../util"),
Digraph = require("graphlib").Digraph,
topsort = require("graphlib").alg.topsort,
nodesFromList = require("graphlib").filter.nodesFromList;
module.exports = sortLayer;
function sortLayer(g, cg, weights) {
weights = adjustWeights(g, weights);
var result = sortLayerSubgraph(g, null, cg, weights);
result.list.forEach(function(u, i) {
g.node(u).order = i;
});
return result.constraintGraph;
}
function sortLayerSubgraph(g, sg, cg, weights) {
cg = cg ? cg.filterNodes(nodesFromList(g.children(sg))) : new Digraph();
"use strict";
var util = require("./util"),
acyclic = require("./rank/acyclic"),
initRank = require("./rank/initRank"),
feasibleTree = require("./rank/feasibleTree"),
constraints = require("./rank/constraints"),
simplex = require("./rank/simplex"),
components = require("graphlib").alg.components,
filter = require("graphlib").filter;
exports.run = run;
exports.restoreEdges = restoreEdges;
/*
* Heuristic function that assigns a rank to each node of the input graph with
* the intent of minimizing edge lengths, while respecting the `minLen`
* attribute of incident edges.
*
* Prerequisites:
*
* * Each edge in the input graph must have an assigned "minLen" attribute
*/
function run(g, useSimplex) {
expandSelfLoops(g);
TsCache.prototype.walkTree = function (cb) {
var acyclic = graphlib.alg.isAcyclic(this.dependencyTree);
if (acyclic) {
_.each(graphlib.alg.topsort(this.dependencyTree), function (id) { return cb(id); });
return;
}
this.context.info(safe.yellow("import tree has cycles"));
_.each(this.dependencyTree.nodes(), function (id) { return cb(id); });
};
TsCache.prototype.done = function () {
function tarjanResults(graph) {
return graphlib.alg.tarjan(graph)
.map( scc => scc.map( id => graph.node(id) ) )
}