jriecken / dependency-graph Goto Github PK

Hi,

I have the typescript compiler reported /lib/index.d.ts(33,31): error TS7006: Parameter 'T' implicitly has an 'any' type.

Looks like there is typo under the file lib/index.d.ts

/**
     * set the data for an existing node (will throw an Error if the node does not exist)
     * @param {string} name
     * @param data
     */
    setNodeData(name: string, T): void;

Should be like below?

/**
     * set the data for an existing node (will throw an Error if the node does not exist)
     * @param {string} name
     * @param data
     */
    setNodeData(name: string, data?: T): void;

I am new to typescript, maybe I haven't got my tsconfig.json setup properly..

It would be nice if a complete copy of the dependency graph was listed that caused the error (e.g. if a indirectly depends on a then this might be a -> c -> d -> b -> a).

I would like to print all my dependencies a la npm ls.

• Function to return string of formatted tree.
• Expose the DFS function with a callback to perform an action on each visited node, such that the user can print out the tree themeselves.

Having level dependency level would be really to have:

• numberOfLevel() to expose how many level of dependency there are (3 levels if a -> b -> c, or 2 levels if a , b -> c)
• showLevel(level) to expose all the node at that dependency level (showLevel(2) = b if a -> b -> c)

The inspiration for this request is to be able to update 1 level of dependency at a time. This is useful for representing nested calculations. This is one way to do it and not necessarily the best, please let me know if there are better ways.

As in title. Say I have a node that's in the "middle" -- it has some dependents and some dependencies. I want to remove this node and all of its dependent nodes (and all of their dependent nodes) from the dependency graph.

I have a semi-hacky solution that does this, but it'd be nice if dependency-graph had a function to do it.

I love this library! I was really happy to search for a specific problem on npm and then find the solution.

I'm mostly using it for the overallOrder() method, to get the proper order to execute a series of tasks in order to satisfy dependencies.

I'm now wondering if there's a way to get an order output based on a single node. Let's say I have a simple dependency graph like this:

• three depends on two
• two depends on one
• one is just there

So if you call overallOrder(), you'd get ['one', 'two', 'three']. What I'd also like to do is calculate an order given a single node as a baseline. So the order based just on two would be ['two', 'three']. Obviously two is first because it's the baseline, and then its dependents are positioned after. The order based on three would just be ['three'] because the node three has no dependents.

I don't see anything in the existing API that could accomplish this, so I'm wondering if you can think of a workaround. Unless I'm missing something! Thanks for your time :)

I have the requirement to save the graph and later restoring it from storage.

I'm saving the properties:

• nodes
• outgoingEdges
• incomingEdges
• circular

from the Graph instance and when I restore from storage I just create a Dependency-Graph instance and set those properties back.

A quick browse through the code seems to indicate this is safe to do this. Can someone confirm if they did this in the past and it's safe? should some extra state from the instance be saved?

First, I ❤️ dependency-graph and thank you so much for making it. 👍 x 💯

I've got a use-case where I need to create a copy/clone of an existing graph. It'd be really handy to that built-in so I'm not accessing private-ish properties on the graph to manually create clones of them. Thoughts?

example code speaks better than words

var DepGraph = require('dependency-graph').DepGraph;

// some arbitrary modules with dependencies
var mods = [
    {name: 'a', deps: []},
    {name: 'b', deps: ['a', 'd']},
    {name: 'c', deps: ['a', 'b']},
    {name: 'd', deps: ['c']}
];

// Helper functions

function _addNode(mod){
  depGraph.addNode(mod.name);
}

function _addEdge(mod){
    function _reallyAddEdge(dep){
      console.log(mod.name + ' -> ' + dep);
      depGraph.addDependency(mod.name, dep);
    }
    mod.deps.forEach(_reallyAddEdge);
}

mods.forEach(_addNode);
mods.forEach(_addEdge);

//this really should explode... but doesn't
console.log(depGraph.overallOrder())
//[ 'a' ]

//this does however cause it to explode
console.log(depGraph.dependantsOf('b'))
/Users/sandfox/code/bizzby/bizzby/node_modules/dependency-graph/lib/dep_graph.js:26
        throw new Error('Dependency Cycle Found: ' + currentPath.join(' -> '))
              ^
Error: Dependency Cycle Found: b -> c -> d -> b
    at /Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:26:15
    at Array.forEach (native)
    at DFS (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:21:17)
    at /Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:23:9
    at Array.forEach (native)
    at DFS (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:21:17)
    at /Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:23:9
    at Array.forEach (native)
    at DFS (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:21:17)
    at Object.DepGraph.dependantsOf (/Users/sandfox/code/xx/node_modules/dependency-graph/lib/dep_graph.js:147:7)

I think that should be enough but let me know if it's not clear or doesn't make any sense.

EDIT----

Think I have found the/a problem..

TL;DR

the overallOrder function checks every node to find one that is not a dependency of another node, and when that fails just checks the first node to find it's dependencies, even though the first node maybe a leaf (based upon on outgoingEdges)

so, in overallOrder it tries to find a node to start from by checking for a node with 0 incomingEdges (things that are immediately dependent on that node).
but every node in my example is a dependency (which means it's cyclic), so the code realises it can't find a starting point and so to find the cyclic dependency it just takes the first node and tries search through it's outgoingEdges (things it is immediately dependent on) and find the cycle that way. This is all groovy and everything unless your first node isn't in the middle of the cycle and is just a leaf node.

I think I can add a small fix to make sure that at least an error gets thrown when trying to render overall order.

Hi there,

I have a feature request. I was wondering if the library could be extended to enable the user to add a node with data

From what I can tell this would require 3 changes:

• the addNode method needs a 2nd parameter for the data (first parameter would be the node name and second parameter the data)
• a new method getData will be needed to get the data of a node by node name
• the hasNode method would need changes to be able to cope with falsy data (0, '', false, undefined, null)

Backwards compatibility should not be an issue if we keep the existing behavior when the addNode method gets undefined data. Only issue with this would be that a user will not be able to set undefined as data for a node.

In case you are interested in this functionality, I would gladly prepare a pull request.

Cheers
Nikolas

I just spent a heap of time tracking down a bug related to this.

If you add a node that already exists, all its edges will be reset to empty arrays which will probably always break something.

Hi,

Thanks for the awesome library!

I'd like to be able to check the type of errors being thrown from dependency-graph. For example, error instanceof DependencyCycleError (or something similar).

Would you accept a PR for custom error types? If so, what Node.js versions should I target, or can I assume ES6+?

Hello,

In my use case I construct a graph to validate a user input. When the input changes I modify the graph accordingly. One of the validations is to check for cycles in the graph.

My current solutions is:

function checkCycle() {
    this.graph.circular = false;
    let res = null;
    try {
        this.graph.overallOrder();
    } catch(e) {
        res = e.message;
    }
    this.graph.circular = true;
    return res;
}

But I this is bad in multiple ways.

1. First of all it modifies the internal circular property temporary. (not exposed to Typescript)
2. It does unnecessary work, since the result of overallOrder() is not used.
3. Relying on exceptions is not clean code.
4. This might suppress other errors.

In my opinion checking for cycles is a general use case and it would be nice if the library can expose it as a function.

Similar to overallOrder, but just for a single dependency.

Use case: When used as an event trigger to run before and after hooks (which have interdependencies).

When the circular property was added to allow cycles (by #21) , clone was not updated to also copy the property to the new DepGraph instance.

Is there a version of this I can use for webapps in the browser?

I have a library that is currently building a dependency graph for package.jsons and its dependencies. It works... alright for now. I was looking into your library but it doesn't seem to sort by most depended on, as overallOrder seems like the order in which nodes were added? Is a sort possible?

Are there any suggestions on how to implement these two helpers?

const graph = new DepGraph() // adding nodes a, b, c, d, etc

const serializedGraph: Record<string, unknown> = serialize(graph) // unknown could be a specific type

const insertedRow = database.insert({ serializedGraph }) // putting serialized graph into a database using something like prisma or sequelize

const const deserializedGraph: DepGraph<T> = deserialize(insertedRow.serializedGraph) // T could be a specific type as well

Great library!

Types for DepGraph constructor are incorrect.

Here the opts argument is required.

Here it is optional.

Currently there is the list of nodes in an error message for the Dependency Cycle error.

It would be great if this could be added as a cycleNodes property to the error itself.

There should be methods to get a node's immediate dependencies or dependents; both of these currently return the full chain (optionally without the last leaf). This makes it hard to walk the graph, step by step.

I'll use it in my TypeORM library to build a dependency tree in which entities will be persisted.

Request

It would be ideal to extend the overallOrder to support returning only the 'entry' nodes.

Example

var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');

graph.addDependency('a', 'b');
graph.addDependency('b', 'c');

graph.entryNodes(); // => ['a']

Underlying problem

Since DepGraph uses an Object, and not a Map, to store nodes, outgoingEdges, and incomingEdges , it mishandles nodes with specific names.

Two examples of how Objects can cause bugs:

Object.keys({__proto__:"hey"}) // []

const obj = {};
if(obj["constructor"]) console.log("key 'constructor' is in obj") // key 'constructor' is in obj

Concrete bugs

Two corresponding examples of bugs in dependency-graph:

var DepGraph = require('dependency-graph').DepGraph;
 
var graph = new DepGraph();
graph.addNode("a");
graph.addNode('__proto__');
graph.addDependency("a","__proto__") // error: node does not exist: __proto__

var DepGraph = require('dependency-graph').DepGraph;
var graph = new DepGraph();
graph.addNode("a");
graph.addNode("constructor");
graph.overallOrder() // ["a"] (notice "constructor" is missing)]

Fix

These bugs can be solved by replacing this.nodes, this.incomingEdges, and this.outgoingEdges with Maps.

For example:
this.nodes = {}; maps to this.nodes = new Map,
this.nodes.hasOwnProperty(node) maps to this.nodes.has(node).
this.nodes[node] = node maps to this.nodes.set(node,node).

I have a graph with cycle on the root node as shown below:
1 --> 2 --> 3 --> 1
Now when I try to print the order of graph (graph.overallOrder()), this returns empty.

But it works fine with below scenario
0 -->1 --> 2 --> 3 --> 1

Here is the code:

const GRAPH = require('dependency-graph').DepGraph;

// Working
let a = new GRAPH({ circular: true });

a.addNode(0);
a.addNode(1);
a.addNode(2);
a.addNode(3);
a.addDependency(0,1);
a.addDependency(1,2);
a.addDependency(2,3);
a.addDependency(3,1);

console.log(a.overallOrder()); // returns correct order

/*
**************************
*/

// Not working
let a = new GRAPH({ circular: true });

a.addNode(1);
a.addNode(2);
a.addNode(3);
a.addDependency(1,2);
a.addDependency(2,3);
a.addDependency(3,1);

console.log(a.overallOrder()); // returns empty array