graph-data-structure - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

index.js

@@ -73,3 +73,3 @@ // A graph data structure with depth-first search and topological sort.
   // This variant excludes the source nodes from the result.
-  function depthFirstSearch(sourceNodes){
+  function depthFirstSearch(sourceNodes, includeSourceNodes){
 
@@ -87,5 +87,9 @@ var visited = {};
 
-    sourceNodes.forEach(function (node){
-      adjacent(node).forEach(DFSVisit);
-    });
+    if(includeSourceNodes){
+      sourceNodes.forEach(DFSVisit);
+    } else {
+      sourceNodes.forEach(function (node){
+        adjacent(node).forEach(DFSVisit);
+      });
+    }
 
@@ -99,4 +103,4 @@ return nodes;
   // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613
-  function topologicalSort(sourceNodes){
-    return depthFirstSearch(sourceNodes).reverse();
+  function topologicalSort(sourceNodes, includeSourceNodes){
+    return depthFirstSearch(sourceNodes, includeSourceNodes).reverse();
   }
@@ -103,0 +107,0 @@

package.json

 {
   "name": "graph-data-structure",
-  "version": "0.1.0",
+  "version": "0.2.0",
   "description": "A graph data structure with topological sort.",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -1,2 +0,45 @@
-# graph-data-structure
-A graph data structure with topological sort.
+# graph-data-structure [![Build Status](https://travis-ci.org/curran/graph-data-structure.svg?branch=master)](https://travis-ci.org/curran/graph-data-structure)
+
+A graph data structure with topological sort algorithm.
+
+[![NPM](https://nodei.co/npm/graph-data-structure.png)](https://nodei.co/npm/graph-data-structure/)
+
+# Usage
+
+Install the library by running
+
+`npm install graph-data-structure`
+
+Require it in your code like this.
+
+```javascript
+var Graph = require("graph-data-structure");
+```
+
+Create a graph.
+
+```javascript
+var graph = Graph();
+```
+
+Add some nodes and edges.
+
+```javascript
+graph.addNode("a");
+graph.addNode("b");
+graph.addEdge("a", "b");
+```
+
+Nodes are added implicitly when edges are added.
+
+```javascript
+graph.addEdge("b", "c");
+```
+
+[Topological sort](https://en.wikipedia.org/wiki/Topological_sorting) can be invoked with an array source nodes (which are excluded from the result).
+
+```
+graph.topologicalSort(["a"]); // Returns ["b", "c"]
+```
+
+For more detailed example code, have a look at the [tests](https://github.com/curran/graph-data-structure/blob/master/test.js).

test.js

@@ -118,2 +118,46 @@
 
+    // This example is from Cormen et al. "Introduction to Algorithms" page 550
+    it("Should compute topological sort relatable case.", function (){
+
+      var graph = Graph();
+
+      // Shoes depend on socks.
+      // Socks need to be put on before shoes.
+      graph.addEdge("socks", "shoes");
+
+      // Shoes depend on pants.
+      // Pants need to be put on before shoes.
+      graph.addEdge("pants", "shoes");
+
+      // Pants depend on underpants.
+      graph.addEdge("underpants", "pants");
+
+      // Belt depends on pants.
+      graph.addEdge("pants", "belt");
+
+      // Belt depends on shirt.
+      graph.addEdge("shirt", "belt");
+
+      // Tie depends on shirt.
+      graph.addEdge("shirt", "tie");
+
+      // Jacket depends on tie.
+      graph.addEdge("tie", "jacket");
+
+      // Jacket depends on belt.
+      graph.addEdge("belt", "jacket");
+
+      var sorted = graph.topologicalSort(graph.nodes(), true);
+
+      assert.equal(sorted.length, 8);
+
+      assert(comesBefore(sorted, "pants", "shoes"));
+      assert(comesBefore(sorted, "underpants", "pants"));
+      assert(comesBefore(sorted, "underpants", "shoes"));
+      assert(comesBefore(sorted, "shirt", "jacket"));
+      assert(comesBefore(sorted, "shirt", "belt"));
+      assert(comesBefore(sorted, "belt", "jacket"));
+
+    });
+
   });
@@ -120,0 +164,0 @@

No alert changes

Improved metrics

Total package byte prevSize

11637

increased by27.56%

Number of package files

7

increased by16.67%

Lines of code

253

increased by15.53%

Number of lines in readme file

46

increased by1433.33%

No dependency changes