toposort - npm Package Compare versions

Comparing version 0.2.8 to 0.2.9

component.json

@@ -6,3 +6,3 @@ {
   "description": "Topological sort of directed ascyclic graphs (like dependecy lists)",
-  "version": "0.2.8",
+  "version": "0.2.9",
   "keywords": [
@@ -9,0 +9,0 @@ "topological",

index.js

@@ -1,25 +0,1 @@
-/*!
- * Toposort - Topological sorting for node.js
- * Copyright (c) 2012 by Marcel Klehr <[e-mail]>
- *
- * MIT LICENSE
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- * 
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- * 
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
- * THE SOFTWARE.
- */
 
@@ -30,47 +6,51 @@ module.exports = toposort;
  * Topological sorting function
- * @param edges {Array} An array of edges like [node1, node2]
- * @returns {Array} a list of nodes, sorted by their dependency (following edge direction as descendancy)
+ * 
+ * @param {Array} edges
+ * @returns {Array}
  */
+
 function toposort(edges) {
-   var nodes = [] // a list of id=>node
-     , sorted = [] // sorted list of ids
+   var nodes = uniqueNodes(edges)
+     , index = nodes.length
+     , sorted = new Array(index)
 
-  // list all nodes by id
-  edges.forEach(function(edge) {
-    edge.forEach(function insertNode (n) {
-      if(nodes.indexOf(n) >= 0) return;
-      nodes.push(n)
-    })
-  })
+  while (index) visit(nodes[0], [])
 
-  while (nodes.length > 0)
-    visit(nodes[0], null, edges, nodes, sorted)
+  return sorted
 
-  return sorted;
-}
+  function visit(node, predecessors) {
+    if(predecessors.indexOf(node) >= 0) {
+      throw new Error('Cyclic dependency: '+JSON.stringify(node))
+    }
 
-function visit(node, predecessors, edges, nodes, sorted) {
-  if (!predecessors) predecessors = []
-  else // The node is a dependency of itself?! I'd say, we're free to throw
-  if(predecessors.indexOf(node) >= 0)
-   throw new Error('Cyclic dependency! The following node is a dependency of itself: '+JSON.stringify(node))
+    var i = nodes.indexOf(node)
+    
+    // already visited
+    if (i < 0) return;
 
-  // if it's not in nodes[] anymore, we've already had this node
-  if (nodes.indexOf(node) < 0) return;
-  
-  // remove this node from nodes[]
-  nodes.splice(nodes.indexOf(node), 1)
+    nodes.splice(i, 1)
 
-  var predsCopy = predecessors.map(function(n) {return n})
-  predsCopy.push(node)
-  
-  edges
-   .filter(function(e) { return e[0] === node })
-   .forEach(function(e) {
-     // visit all dependencies of this node
-     // and provide them with a *copy* of their predecessors (including *this* node)
-     visit(e[1], predsCopy, edges, nodes, sorted)
-   })
+    // outgoing edges
+    var out = edges.filter(function(edge){
+      return edge[0] === node
+    })
+    if (i = out.length) {
+      var preds = predecessors.concat(node)
+      do {
+        visit(out[--i][1], preds)
+      } while (i)
+    }
+    
+    sorted[--index] = node
+  }
+}
 
-  sorted.unshift(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
 }

package.json

 {
   "name": "toposort",
-  "version": "0.2.8",
+  "version": "0.2.9",
   "description": "Topological sort of directed ascyclic graphs (like dependecy lists)",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -1,72 +0,68 @@
-# Sorting directed acyclic graphs
+# Toposort
+
+Sort directed acyclic graphs
+
 [![Build Status](https://travis-ci.org/marcelklehr/toposort.png)](https://travis-ci.org/marcelklehr/toposort)
 
 ## Installation
-`npm install toposort` or `component install toposort`
 
+`npm install toposort` or `component install marcelklehr/toposort`  
+
+then in your code:
+
+```js
+toposort = require('toposort')
+```
+
 ## Example
-Let's say, you have a list of plugins or tasks, which depend on each other (`depends` defines plugins or tasks that should be executed before the plugin that declares the directive):
 
+Let's say you are compiling a project consisting of 5 modules. You know there are some dependencies between them so you want to figure a safe execution order to run them in. Lets assume we have tool which spits out dependency data for us:
+
 ```
-var plugins =
-[ {name: "foo", depends: ['bar']}
-, {name: "bar", depends: ["ron"]}
-, {name: "john", depends: ["bar"]}
-, {name: "tom", depends: ["john"]}
-, {name: "ron", depends: []}
+var project = [
+  {name: "foo", depends: ['bar']},
+  {name: "bar", depends: ["ron"]},
+  {name: "john", depends: ["bar"]},
+  {name: "tom", depends: ["john"]},
+  {name: "ron", depends: []}
 ]
 ```
 
-A quick analysis, will result in the following dependency tree:
+Which if visualized in a graph:
 
-```
-tom
- |
-john  foo
- |     |
- - - - - 
-    |
-   bar
-    |
-   ron
-```
+![graph](out.png)
 
-and thus the following execution flow:
+reveals two safe execution orders:
 
-```
-   ron
-    |
-   bar
- - - - - 
- |     |
-john  foo
- |
-tom
-```
++ `ron -> bar -> foo -> john -> tom`
++ `ron -> bar -> john -> tom -> foo`
 
-Let's try this with `toposort`:
+Let's see if we can get `toposort` to figure that out for us. First though we need to translate the dependency information into something it can understand. The way `toposort` understands relationships is with edges. An "edge" is a 2 item `Array` where the first item is the subject and the 2nd item is the target.  
 
+With edges our data looks like this: 
+
 ```js
-toposort = require('toposort')
-
-var plugins =
-[ ["foo", 'bar']
-, ["bar", "ron"]
-, ["john", "bar"]
-, ["tom", "john"]
+var modules = [
+  ["foo", "bar"],
+  ["bar", "ron"],
+  ["john", "bar"],
+  ["tom", "john"]
 ]
+```
 
-// this will sort our plugins by dependecy
-var results = toposort(plugins)
+Running it through `toposort` we get:
 
-// now, we reverse the results to get the resulting execution flow, as above
-results.reverse()
+```js
+var results = toposort(modules)
 
 console.dir(results)
-/*
-Output:
+// => [ 'tom', 'john', 'foo', 'bar', 'ron' ]
+```
+So `toposort` prefered the first path through the graph. Since it was the first it encountered.
 
-[ 'ron', 'bar', 'foo', 'john', 'tom' ]
+Now, we to get the best execution order, we can just reverse the returned array:
 
-*/
+```js
+console.dir(results.reverse())
+// => [ 'ron', 'bar', 'foo', 'john', 'tom' ]
 ```
@@ -77,10 +73,13 @@
 ### toposort(edges)
- * edges {Array} An array of directed vertices like `[node1, node2]` (where `node1` depends on `node2`) -- these needn't be strings but can be any of any type
 
-Returns: {Array} a list of nodes, sorted by their dependency (following edge direction as descendancy)
++ edges {Array} An array of directed vertices like `[node1, node2]` (where `node1` depends on `node2`) -- these needn't be strings but can be of any type
 
+Returns: {Array} a list of nodes, sorted from least dependencies to most
+
 ## Tests
+
 Run the tests with `node test.js`.
 
 ## Legal
+
 MIT License

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

21103

increased by170.9%

Number of package files

10

increased by25%

Worsened metrics

Lines of code

147

decreased by-12.5%

Number of lines in readme file

84

decreased by-1.18%

No dependency changes