'a'

mh-two-thousand-and-two

2024-04-12 44d2c92345cd156a59fc327b3060292a282d2893

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
/**
 * Topological sorting function
 *
 * @param {Array} edges
 * @returns {Array}
 */
 
module.exports = function(edges){
  return toposort(uniqueNodes(edges), edges)
}
 
module.exports.array = toposort
 
function toposort(nodes, edges) {
  var cursor = nodes.length
    , sorted = new Array(cursor)
    , visited = {}
    , i = cursor
 
  while (i--) {
    if (!visited[i]) visit(nodes[i], i, [])
  }
 
  return sorted
 
  function visit(node, i, predecessors) {
    if(predecessors.indexOf(node) >= 0) {
      var nodeRep 
      try {
        nodeRep = ", node was:" + JSON.stringify(node)
      } catch(e) {
        nodeRep = ""
      }
      throw new Error('Cyclic dependency' + nodeRep)
    }
 
    if (!~nodes.indexOf(node)) {
      throw new Error('Found unknown node. Make sure to provided all involved nodes. Unknown node: '+JSON.stringify(node))
    }
 
    if (visited[i]) return;
    visited[i] = true
 
    // outgoing edges
    var outgoing = edges.filter(function(edge){
      return edge[0] === node
    })
    if (i = outgoing.length) {
      var preds = predecessors.concat(node)
      do {
        var child = outgoing[--i][1]
        visit(child, nodes.indexOf(child), preds)
      } while (i)
    }
 
    sorted[--cursor] = node
  }
}
 
function uniqueNodes(arr){
  var res = []
  for (var i = 0, len = arr.length; i < len; i++) {
    var edge = arr[i]
    if (res.indexOf(edge[0]) < 0) res.push(edge[0])
    if (res.indexOf(edge[1]) < 0) res.push(edge[1])
  }
  return res
}