How to use the graphlib.alg function in graphlib

To help you get started, we’ve selected a few graphlib examples, based on popular ways it is used in public projects.

Secure your code as it's written. Use Snyk Code to scan source code in minutes - no build needed - and fix issues immediately.

github pattern-lab / patternlab-node / core / lib / pattern_graph.js View on Github external
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);
  },
github teambit / bit / src / scope / graph / components-graph.ts View on Github external
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}`);
github teambit / bit / src / scope / component-ops / export-scope-components.ts View on Github external
}
      // 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;
  }
github serverless / components / src / utils / dag / detectCircularDeps.js View on Github external
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
}
github tylingsoft / dagre-layout / lib / order / sortLayer.js View on Github external
"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();
github tylingsoft / dagre-layout / lib / rank.js View on Github external
"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);
github ezolenko / rollup-plugin-typescript2 / dist / rollup-plugin-typescript2.cjs.js View on Github external
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 () {
github mcclure / dts2nim / src / dts2nim.ts View on Github external
function tarjanResults(graph) {
	return graphlib.alg.tarjan(graph)
		.map( scc => scc.map( id => graph.node(id) ) )
}