Sort by most dependend on?

[milesj]

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?

[jriecken]

The overallOrder method performs a Topological Sort on the graph. It will give a valid sequence where all nodes that depend on another node appear after that node (there may be many such valid sequences, but this will return one of them).

As an example, given a set of items of clothing and their dependencies to get dressed:

Socks     Underwear             
     |        |    -\            
     |        |      -\          
     |        |        --        
     |      Jeans      Shirt     
     |      /-  \          |     
     |    /-     -\        |     
     |  --         -       |     
    Shoes         Belt     |     
                     -\    |     
                       -\  |     
                         --|     
                        Jacket    

(e.g. in order to put on my shoes I need to have my socks and jeans on, but in order to put my jeans on I need my underwear on, etc.)

One valid output from overallOrder could be:

Socks, Underwear, Shirt, Jeans, Belt, Jacket, Shoes or Underwear, Jeans, Shirt, Belt, Jacket, Socks, Shoes

In each case, every item appears after all of the items it relies on to be complete before it.

[milesj]

Yeah that makes sense, I'm just a bit confused by my initial testing. I was expecting it to order by most depended on. For example, here's the console log of the graph instance.

{ nodes: 
         { '@scope/primary': { name: '@scope/primary', version: '0.0.0', workspace: [Object] },
           '@scope/foo': 
            { name: '@scope/foo',
              version: '0.0.0',
              workspace: [Object],
              peerDependencies: [Object] },
           '@scope/bar': { name: '@scope/bar', version: '0.0.0', workspace: [Object] },
           '@scope/baz': { name: '@scope/baz', version: '0.0.0', workspace: [Object] },
           '@scope/qux': { name: '@scope/qux', version: '0.0.0', workspace: [Object] } },
        outgoingEdges: 
         { '@scope/primary': [],
           '@scope/foo': [ '@scope/bar' ],
           '@scope/bar': [],
           '@scope/baz': [],
           '@scope/qux': [] },
        incomingEdges: 
         { '@scope/primary': [],
           '@scope/foo': [],
           '@scope/bar': [ '@scope/foo' ],
           '@scope/baz': [],
           '@scope/qux': [] },
        circular: true }

Notice that @scope/foo depends on @scope/bar, but overallOrder returns: [ '@scope/primary', '@scope/bar', '@scope/foo', '@scope/baz', '@scope/qux' ]. I would expect @scope/bar to be before @scope/primary, but if that's not the case, then this library won't achieve what I need.

[jriecken]

Ah, I think I understand now.

In your example there's only one dependency, so the only constraint it puts on the output is that @scope/bar comes before @scope/foo . Since @scope/primary doesn't depend on anything (and nothing depends on it) it can validly show up in any position in the list (it would be like adding a sing a song step to the getting dressed example).

It would definitely be much less efficient for larger graphs (O(n^2) instead of O(n)) but I think this would do what you want:

• For each node, compute graph.dependantsOf(node).length
• Sort the list of nodes by the number of dependant nodes.

Given that a node that depends on another node will have 1 less dependant than that other node, sorting it this way should still be a valid topological sort.

E.g.

const g = new DepGraph()
g.addNode('primary')
g.addNode('foo')
g.addNode('bar')
g.addNode('baz')
g.addNode('qux')
g.addDependency('foo', 'bar')

Object.keys(g.nodes).
  map(n => [n, g.dependantsOf(n).length]).
  sort(([,l1],[,l2]) => l2 - l1).map(([v,])=>v)

// ['bar', 'primary', 'foo', 'baz', 'qux']

[milesj]

I'll give that a try, thank you!