toposort - npm Package Compare versions

Comparing version 0.2.9 to 0.2.10

component.json

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

index.js


		module.exports = toposort;

		/**
		* Topological sorting function
		*
		*
		* @param {Array} edges
		@@ -11,12 +9,21 @@ * @returns {Array}

		function toposort(edges) {
		var nodes = uniqueNodes(edges)
		, index = nodes.length
		, sorted = new Array(index)
		module.exports = exports = function(edges){
		return toposort(uniqueNodes(edges), edges)
		}

		while (index) visit(nodes[0], [])
		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, predecessors) {
		function visit(node, i, predecessors) {
		if(predecessors.indexOf(node) >= 0) {
		@@ -26,21 +33,18 @@ throw new Error('Cyclic dependency: '+JSON.stringify(node))

		var i = nodes.indexOf(node)

		// already visited
		if (i < 0) return;
		if (visited[i]) return;
		visited[i] = true

		nodes.splice(i, 1)

		// outgoing edges
		var out = edges.filter(function(edge){
		var outgoing = edges.filter(function(edge){
		return edge[0] === node
		})
		if (i = out.length) {
		if (i = outgoing.length) {
		var preds = predecessors.concat(node)
		do {
		visit(out[--i][1], preds)
		var child = outgoing[--i][1]
		visit(child, nodes.indexOf(child), preds)
		} while (i)
		}

		sorted[--index] = node

		sorted[--cursor] = node
		}
		@@ -47,0 +51,0 @@ }

package.json

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

README.md

		@@ -78,2 +78,9 @@ # Toposort

		### toposort.array(nodes, edges)

		+ nodes {Array} An array of nodes
		+ edges {Array} As with `toposort`. Edges doesn't necessarily need to contain all the items in `nodes`. However, the ordering of the items you don't mention will be undefined.

		Returns: {Array} as per `toposort`

		## Tests
		@@ -80,0 +87,0 @@

test.js

		@@ -80,2 +80,23 @@ var vows = require('vows')
		}
		, 'toposort.array':
		{ topic: function() {
		return toposort.array(['d', 'c', 'a', 'b'], [['a','b'],['b','c']])
		}
		, 'should handle imcomplete edges': function(er, result){
		var i = result.indexOf('d')
		assert(i >= 0)
		result.splice(i, 1)
		assert.deepEqual(result, ['a', 'b', 'c'])
		}
		}
		, 'toposort.array mutation':
		{ topic: function() {
		var array = ['d', 'c', 'a', 'b']
		toposort.array(array, [['a','b'],['b','c']])
		return array
		}
		, 'should not mutate its arguments': function(er, result){
		assert.deepEqual(result, ['d', 'c', 'a', 'b'])
		}
		}
		})
		@@ -82,0 +103,0 @@ .run(null, function() {

New alerts