graph-data-structure - npm Package Compare versions

Comparing version 0.5.0 to 0.6.0

index.js

 // A graph data structure with depth-first search and topological sort.
-module.exports = function Graph(){
+module.exports = function Graph(serialized){
   
@@ -9,2 +9,7 @@ // The adjacency list of the graph.
 
+  // If a serialized graph was passed into the constructor, deserialize it.
+  if(serialized){
+    deserialize(serialized);
+  }
+
   // Adds a node to the graph.
@@ -120,2 +125,36 @@ // If node was already added, this function does nothing.
   }
+
+  // Serializes the graph.
+  function serialize(){
+    var serialized = {
+      nodes: nodes(),
+      links: []
+    };
+
+    var indices = {};
+    serialized.nodes.forEach(function (node, i){
+      indices[node] = i;
+    });
+
+    serialized.nodes.forEach(function (u, i){
+      adjacent(u).forEach(function (v){
+        serialized.links.push({
+          source: i,
+          target: indices[v]
+        });
+      });
+    });
+
+    return serialized;
+  }
+
+  // Deserializes the given serialized graph.
+  function deserialize(serialized){
+    serialized.nodes.forEach(addNode);
+    serialized.links.forEach(function (link){
+      var u = serialized.nodes[link.source];
+      var v = serialized.nodes[link.target];
+      addEdge(u, v);
+    });
+  }
   
@@ -130,4 +169,6 @@ return {
     depthFirstSearch: depthFirstSearch,
-    topologicalSort: topologicalSort
+    topologicalSort: topologicalSort,
+    serialize: serialize,
+    deserialize: deserialize
   };
 }

package.json

 {
   "name": "graph-data-structure",
-  "version": "0.5.0",
+  "version": "0.6.0",
   "description": "A graph data structure with topological sort.",
@@ -11,3 +11,3 @@ "main": "index.js",
     "type": "git",
-    "url": "git+https://github.com/curran/graph-data-structure.git"
+    "url": "git+https://github.com/datavis-tech/graph-data-structure.git"
   },
@@ -23,5 +23,5 @@ "keywords": [
   "bugs": {
-    "url": "https://github.com/curran/graph-data-structure/issues"
+    "url": "https://github.com/datavis-tech/graph-data-structure/issues"
   },
-  "homepage": "https://github.com/curran/graph-data-structure#readme",
+  "homepage": "https://github.com/datavis-tech/graph-data-structure#readme",
   "devDependencies": {
@@ -28,0 +28,0 @@ "mocha": "^2.4.5"

README.md

@@ -1,28 +0,19 @@
-# graph-data-structure
+# graph-data-structure 
 
-A graph data structure with topological sort algorithm.
+A [graph data structure](https://en.wikipedia.org/wiki/Graph_(abstract_data_type)) with [topological sort](https://en.wikipedia.org/wiki/Topological_sorting).
 
-[![NPM](https://nodei.co/npm/graph-data-structure.png)](https://nodei.co/npm/graph-data-structure/)
+[![NPM](https://nodei.co/npm/graph-data-structure.png)](https://npmjs.org/package/graph-data-structure)
+[![NPM](https://nodei.co/npm-dl/graph-data-structure.png?months=3)](https://npmjs.org/package/graph-data-structure) [![Build Status](https://travis-ci.org/datavis-tech/graph-data-structure.svg?branch=master)](https://travis-ci.org/curran/reactive-property)
 
-[![Build Status](https://travis-ci.org/curran/graph-data-structure.svg?branch=master)](https://travis-ci.org/curran/graph-data-structure)
+This library provides a minimalist implementation of a directed graph data structure. Nodes are represented by unique strings. Internally, an [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list) is used to represent nodes and edges.
 
-# Usage
+The primary use case for this library is in implementing [dataflow programming](https://en.wikipedia.org/wiki/Dataflow_programming) or [reactive programming](https://en.wikipedia.org/wiki/Reactive_programming). The key algorithm necessary for these is topological sorting, to get an ordering of nodes such that for each edge (**u** -> **v**), **u** comes before **v** in the sorted order. The topological sorting algorithm exposed here has modifications useful for computing the order in which functions in a data flow graph should be executed, namely specifying source nodes for propagation and specifying to exclude the source nodes themselves from the result.
 
-If you are using NPM, install the library by running
+To create a graph instance, invoke **[Graph](#graph)** as a constructor function.
 
-`npm install graph-data-structure`
-
-Require it in your code like this.
-
 ```javascript
-var Graph = require("graph-data-structure");
-```
-
-Create a graph instance.
-
-```javascript
 var graph = Graph();
 ```
 
-Add some nodes and edges.
+Add some nodes and edges with **[addNode](#add-node)** and **[addEdge](#add-edge)**.
 
@@ -41,3 +32,3 @@ ```javascript
 
-[Topological sort](https://en.wikipedia.org/wiki/Topological_sorting) can be invoked like this.
+[Topological sorting](https://en.wikipedia.org/wiki/Topological_sorting) can be done by invoking **[topologicalSort](#topological-sort)** like this.
 
@@ -65,18 +56,125 @@ ```
 
-console.log(graph.topologicalSort()); // prints [ "underpants", "pants", "shirt", "tie", "belt", "jacket", "socks", "shoes" ]
+// prints [ "underpants", "pants", "shirt", "tie", "belt", "jacket", "socks", "shoes" ]
+console.log(graph.topologicalSort());
 ```
 
-For more detailed example code that shows more methods, have a look at the [tests](https://github.com/curran/graph-data-structure/blob/master/test.js).
+For more detailed example code that shows more methods, have a look at the [tests](https://github.com/datavis-tech/graph-data-structure/blob/master/test.js).
 
+# Installation
+
+This library is distributed only via [NPM](npmjs.com). Install by running
+
+`npm install graph-data-structure`
+
+Require it in your code like this.
+
+```javascript
+var Graph = require("graph-data-structure");
+```
+
 # API Reference
 
-Methods on graphs include:
+* [Creating a Graph](#creating-a-graph)
+* [Adding and Removing Nodes](#adding-and-removing-nodes)
+* [Adding and Removing Edges](#adding-and-removing-edges)
+* [Querying the Graph](#querying-the-graph)
+* [Graph Algorithms](#graph-algorithms)
 
-* `addNode(node)` Adds a node to the graph, accepts a string node identifier. If node was already added, this function does nothing.
-* `removeNode(node)` Removes a node from the graph. Also removes incoming and outgoing edges.
-* `nodes()` List all nodes in the graph.
-* `adjacent(node)` Gets the adjacent node list for the given node. This is the set of nodes for which there is an incoming edge from the given node.
-* `addEdge(u, v)` Adds an edge from node u to node v. Implicitly adds the nodes if they were not already added.
-* `removeEdge(u, v)` Removes the edge from node u to node v. Does not remove the nodes. Does nothing if the edge does not exist.
-* `depthFirstSearch(sourceNodes, includeSourceNodes)` Depth First Search algorithm, inspired by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604. This variant includes an additional option `includeSourceNodes` to specify whether to include or exclude the source nodes from the result (true by default). If `sourceNodes` is not specified, all nodes in the graph are used as source nodes.
-* `topologicalSort(sourceNodes, includeSourceNodes)` The topological sort algorithm yields a list of visited nodes such that for each visited edge (u, v), u comes before v in the list. Amazingly, this comes from just reversing the result from depth first search. Inspired by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613. This variant includes an additional option `includeSourceNodes` to specify whether to include or exclude the source nodes from the result (true by default). If `sourceNodes` is not specified, all nodes in the graph are used as source nodes.
+### Creating a Graph
+
+<a name="graph" href="#graph">#</a> <b>Graph</b>([<i>serialized</i>])
+
+Constructs an instance of the graph data structure.
+
+The optional argument *serialized* is a serialized graph that may have been generated by **[serialize](#serialize)**. If *serialized* is present, it is deserialized by invoking **[deserialize](#deserialize)**.
+
+### Adding and Removing Nodes
+
+<a name="add-node" href="#add-node">#</a> <i>graph</i>.<b>addNode</b>(<i>node</i>)
+
+Adds a node to the graph. The argument *node* is a string identifier that uniquely identifies the node within this graph instance. If a node with the same identifier was already added to the graph, this function does nothing.
+
+<a name="remove-node" href="#remove-node">#</a> <i>graph</i>.<b>removeNode</b>(<i>node</i>)
+
+Removes the specified node. The argument *node* is a string identifier for the node to remove. This function also removes all edges connected to the specified node, both incoming and outgoing.
+
+### Adding and Removing Edges
+
+<a name="add-edge" href="#add-edge">#</a> <i>graph</i>.<b>addEdge</b>(<i>u</i>, <i>v</i>)
+
+Adds an edge from node *u* to node *v*. The arguments *u* and *v* are string identifiers for nodes. This function also adds *u* and *v* as nodes if they were not already added.
+
+<a name="remove-edge" href="#remove-edge">#</a> <i>graph</i>.<b>removeEdge</b>(<i>u</i>, <i>v</i>)
+
+Removes the edge from node *u* to node *v*. The arguments *u* and *v* are string identifiers for nodes. This function does not remove the nodes *u* and *v*. Does nothing if the edge does not exist.
+
+### Querying the Graph
+
+<a name="nodes" href="#nodes">#</a> <i>graph</i>.<b>nodes</b>()
+
+List all nodes in the graph. Returns an array of node identifier strings.
+
+<a name="adjacent" href="#adjacent">#</a> <i>graph</i>.<b>adjacent</b>(<i>node</i>)
+
+Gets the adjacent node list for the specified node. The argument *node* is a string identifier for a node. Returns an array of node identifier strings.
+
+The "adjacent node list" is the set of nodes for which there is an incoming edge from the given node. In other words, for all edges (**u** -> **v**) where **u** is the specified node, all values for **v** are in the adjacent node list. 
+
+<a name="serialize" href="#serialize">#</a> <i>graph</i>.<b>serialize</b>()
+
+Serializes the graph. Returns an object with the following properties.
+
+ * `nodes` An array of node identifier strings.
+ * `links` An array of edge objects with the following properties.
+   * `source` An integer, the index of the source node (**u**) in the `nodes` array.
+   * `target` An integer, the index of the target node (**v**) in the `nodes` array.
+
+Here's example code for serializing a graph.
+
+```javascript
+var graph = Graph();
+graph.addEdge("a", "b");
+graph.addEdge("b", "c");
+var serialized = graph.serialize();
+```
+
+The following will be the value of `serialized`.
+
+```json
+ {
+    "nodes": ["a", "b", "c"],
+    "links": [
+      { "source": 0, "target": 1 },
+      { "source": 1, "target": 2 }
+    ]
+  }
+```
+
+This representation conforms to the convention of graph representation when working with D3.js force layouts. See also [d3.simulation.nodes](https://github.com/d3/d3-force#simulation_nodes) and [d3.forceLinks](https://github.com/d3/d3-force#links).
+
+<a name="deserialize" href="#deserialize">#</a> <i>graph</i>.<b>deserialize</b>(<i>serialized</i>)
+
+Deserializes the given serialized graph. The argument *serialized* is a graph representation with the structure described in **[serialize](#serialize)**. This function iterates over the serialized graph and adds the nodes and links it represents by invoking **[addNode](#add-node)** and **[addEdge](#add-edge)**.
+
+### Graph Algorithms
+
+<a name="dfs" href="#dfs">#</a> <i>graph</i>.<b>depthFirstSearch</b>([<i>sourceNodes</i>][, <i>includeSourceNodes</i>])
+
+Performs [Depth-first Search](https://en.wikipedia.org/wiki/Depth-first_search). Returns an array of node identifier strings. The returned array includes nodes visited by the algorithm in the order in which they were visited. Implementation inspired by pseudocode from Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604.
+
+Arguments:
+
+ * *sourceNodes* (optional) - An array of node identifier strings. This specifies the subset of nodes to use as the sources of the depth-first search. If *sourceNodes* is not specified, all **[nodes](#nodes)** in the graph are used as source nodes.
+ * *includeSourceNodes* (optional) - A boolean specifying whether or not to include the source nodes in the returned array. If *includeSourceNodes* is not specified, it is treated as `true` (all source nodes are included in the returned array).
+
+<a name="topological-sort" href="#topological-sort">#</a> <i>graph</i>.<b>topologicalSort</b>([<i>sourceNodes</i>][, <i>includeSourceNodes</i>])
+
+Performs [Topological Sort](https://en.wikipedia.org/wiki/Topological_sorting). Returns an array of node identifier strings. The returned array includes nodes in topologically sorted order. This means that for each visited edge (**u** -> **v**), **u** comes before **v** in the topologically sorted order. Amazingly, this comes from simply reversing the result from depth first search. Inspired by by Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613.
+
+See **[depthFirstSearch](#dfs)** for documentation of the arguments *sourceNodes* and *includeSourceNodes*.
+
+<p align="center">
+  <a href="https://datavis.tech/">
+    <img src="https://cloud.githubusercontent.com/assets/68416/15298394/a7a0a66a-1bbc-11e6-9636-367bed9165fc.png">
+  </a>
+</p>

test.js

@@ -192,2 +192,104 @@
   });
+
+  describe("Serialization", function() {
+
+    it("Should serialize a graph.", function (){
+      var graph = Graph();
+
+      graph.addEdge("a", "b");
+      graph.addEdge("b", "c");
+
+      var serialized = graph.serialize();
+
+      assert.equal(serialized.nodes.length, 3);
+      assert.equal(serialized.links.length, 2);
+
+      assert.equal(serialized.nodes[0], "a");
+      assert.equal(serialized.nodes[1], "b");
+      assert.equal(serialized.nodes[2], "c");
+
+      assert.equal(serialized.links[0].source, 0);
+      assert.equal(serialized.links[0].target, 1);
+      assert.equal(serialized.links[1].source, 1);
+      assert.equal(serialized.links[1].target, 2);
+
+    });
+
+    it("Should deserialize a graph.", function (){
+
+      var graph = Graph();
+      
+      var serialized = {
+        "nodes": [
+          "a",
+          "b",
+          "c"
+        ],
+        "links": [
+          {
+            "source": 0,
+            "target": 1
+          },
+          {
+            "source": 1,
+            "target": 2
+          }
+        ]
+      };
+
+      graph.deserialize(serialized);
+      var reserialized = graph.serialize();
+
+      assert.equal(reserialized.nodes.length, 3);
+      assert.equal(reserialized.links.length, 2);
+
+      assert.equal(reserialized.nodes[0], "a");
+      assert.equal(reserialized.nodes[1], "b");
+      assert.equal(reserialized.nodes[2], "c");
+
+      assert.equal(reserialized.links[0].source, 0);
+      assert.equal(reserialized.links[0].target, 1);
+      assert.equal(reserialized.links[1].source, 1);
+      assert.equal(reserialized.links[1].target, 2);
+
+    });
+
+    it("Should deserialize a graph passed to constructor.", function (){
+      
+      var serialized = {
+        "nodes": [
+          "a",
+          "b",
+          "c"
+        ],
+        "links": [
+          {
+            "source": 0,
+            "target": 1
+          },
+          {
+            "source": 1,
+            "target": 2
+          }
+        ]
+      };
+
+      var graph = Graph(serialized);
+
+      var reserialized = graph.serialize();
+
+      assert.equal(reserialized.nodes.length, 3);
+      assert.equal(reserialized.links.length, 2);
+
+      assert.equal(reserialized.nodes[0], "a");
+      assert.equal(reserialized.nodes[1], "b");
+      assert.equal(reserialized.nodes[2], "c");
+
+      assert.equal(reserialized.links[0].source, 0);
+      assert.equal(reserialized.links[0].target, 1);
+      assert.equal(reserialized.links[1].source, 1);
+      assert.equal(reserialized.links[1].target, 2);
+
+    });
+  });
 });
@@ -194,0 +296,0 @@

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

23812

increased by60.31%

Lines of code

392

increased by40.5%

Number of lines in readme file

179

increased by120.99%

No dependency changes