JSNetworkX

JSNetworkX allows you to build, process and analyze graphs in JavaScript. It can be used together with D3.js in the browser to create interactive graph visualizations.

It is a port of NetworkX (v1.6), a popular graph library for Python, to JavaScript. Extensive information can be found on:

• the website
• the API documentation
• the wiki

Install

Node.js

Install from npm:

npm install jsnetworkx

Browser

Download jsnetworkx.js and include it in your page with

<script src="/path/to/jsnetworkx.js"></script>

This will create the global variable jsnx, with which all functions can be accessed.

Usage

JSNetworkX consists of multiple parts which work closely together:

• Graph classes (Graph, DiGraph, MultiGraph and MultiDiGraph) to model the data
• Graph generators for common graphs
• Various graph algorithms
• Graph visualization (in the browser)

Most classes and functions are available on the root object (jsnx in browsers, require('jsnetworkx') in Node).

Information about which algorithms are available and the API of the classes, can be found in the auto-generated API documentation.

Example

// var jsnx = require('jsnetworkx'); // in Node

// a tree of height 4 with fan-out 2
var G = jsnx.balancedTree(2, 4);

// Compute the shortest path between node 2 and 7
var path = jsnx.bidirectionalShortestPath(G, 2, 7);
// [ 2, 0, 1, 3, 7 ]

// or asynchronously
jsnx.genBidirectionalShortestPath(G, 2, 7).then(function(path) {
  // path = [ 2, 0, 1, 3, 7 ]
});

More examples can be found on the website.

Asynchronous computation

All the algorithms are implemented in a synchronous fashion (for now at least). However, many algorithms are also available as asynchronous version. Their names are gen<SyncFunctionName> (see example above) and they return a Promise.

This is achieved in browsers by creating a WebWorker. The WebWorker has to be passed the path to the jsnetworkx.js file. You have to set the path explicitly if the file is not located at the root:

jsnx.workerPath = '/path/to/jsnetworkx.js';

In Node, a subprocess will be spawned (no setup is required).

Caveat: In both cases the input data has to be serialized before it can be sent to the worker or subprocess. However, not every value can be serialized, in which case JSNetworkX will use the synchronous version instead. If you encounter a situation where a value is not serialized, but it should be serializable, please file an issue.

Iterables

Many methods return generators or Maps. In an ES2015 environment, these can be easily consumed with a for/of loop or Array.from.

If those are not available to you, JSNetworkX provides two helper methods for iterating iterables and converting them to arrays: jsnx.forEach and jsnx.toArray

How to contribute

You can contribute by:

• Porting code from Python
• Improving the documentation/website

If you plan on converting/porting a specific part, please create an issue beforehand.

Build JSNetworkX

JSNetworkX is written in ES2015 (ES6) and Babel is used to convert it to ES5. For the browser, all modules are bundled together with browserify.

To build JSNetworkX, all dependencies have to be installed via

npm install

Build for the browser

npm run build:browser

creates jsnetworkx.js, a minified version for production.

npm run build:browser:dev
npm run watch:browser

Creates jsnetworkx-dev.js, an unminified version with inline source maps for development. The second version automatically rebuilds the file on change.

Build for Node

npm run build:node

Transforms all modules to ES5 and saves them inside the node/ directory.

npm run build:node:dev

Same as above but with inline source maps. These modules are also used to tun the unit tests.

npm run watch:node

Incrementally transform modules when files change.

Create and run tests

Tests are stored in the respective __tests__ directories and have to follow the naming convention <testname>-test.js. The tests can be run with

npm test
# or
npm run test:fast # if you also run `npm run watch:node`

This will run all tests by default. To consider only those files whose path matches a specific string, pass the -g option:

# Runs all digraph tests but no graph tests
npm run test:fast -- -g digraph

The difference between npm test and npm run test:fast is that the former will always transplile all files from ES6 to ES5 first. This is slow and annoying during development. Therefore you can use

npm run watch:node

to automatically convert only the changed file and run npm run test:fast to quickly test them.

Ideally, every module has corresponding unit test. If you port a module from NetworkX, make sure to implement the same tests.

Run coverage

We use istanbul to generate a coverage report. We are not enforcing any coverage yet, but there should not be a regression. The report can be created via

npm run cover

and written to coverage/.

Changlog

v0.3.4

New

API/Algorithms

Binary graph operators:

• union / genUnion
• disjointUnion / genDisjointUnion
• intersection / genIntersection
• difference / genDifference
• symmetricDifference / genSymmetricDifference
• compose / genCompose

Fixed

• Issue with zoom on double click since d3 v3.5.5 (#51)

v0.3.3

Changes

It is now possible to require individual modules and still get the benefits of async code execution through workers.

Example:

var completeGraph = require('jsnetworkx/node/generators/classic').completeGraph;
var cluster = require('jsnetworkx/node/algorithms/cluster');
var WorkerSettings = require('jsnetworkx/node/WorkerSettings');
var initializeBrowserWorker = require('jsnetworkx/node/initializeBrowserWorker');

global.genClustering = cluster.genClustering;
global.completeGraph = completeGraph;
WorkerSettings.methodLookupFunction = function(name) {
  return cluster[name];
};
initializeBrowserWorker();

This is a custom module which only exposes completeGraph and genClustering.

WorkerSettings.methodLookupFunction

This function is used by the worker (and delegateToSync!) to resolve the method name the worker receives, to the actual function. E.g. the prebuilt version of JSNetworkX uses name => jsnx[name].

initializeBrowserWorker

This function tests whether we are in a worker environment and if yes, sets up the event handlers and takes care of (de)serializing the data. This function should be called in the worker script.

Given the example above, the custom bundle could be created with

JSNETWORKX_BUNDLE='bundle.js' browserify test.js > bundle.js

v0.3.2

New

API/Algorithms

• eigenvectorCentrality (genEigenvectorCentrality)

v0.3.1

New

API/Algorithms

Weighted and generic shortest path algorithms. The "generic" functions provide a single interface for weighted and unweighted algorithms.

• allPairsDijkstraPath
• allPairsDijkstraPathLength
• dijkstraPath
• dijkstraPathLength
• singleSourceDijkstra
• singleSourceDijkstraPath
• singleSourceDijkstraPathLength
• shortestPath
• shortestPathLength
• hasPath

including async (gen*) versions.

v0.3.0

New

API

• Many algorithms are now available as asynchronous methods. E.g. clustering is available as genClustering. Those methods return a Promise and will delegate to a web worker in browsers. In Node.js, a new process will be spawned.
  Note that in both cases the data has to be serialized, which happens synchronously and may also take some time, depending on the size of the graph.

Drawing

• New drawing option stickyDrag. If set to true, the dragged node will keep its new position after dragging and is not subject to the force layout. D3 example.

Changes

API

• Moved from underscore_method_names to camelCaseMethodNames.
• makeSmallUndirectedGraph and makeSmallGraph now accept an object of the form {type, name, n, list} as first argument instead of an array [type, name, n, list].
• Objects are not considered as "NodeContainers" anymore. Previously, any function that accepted a list of nodes also accepted an object of the form {n1: ..., n2: ..., ...} and n1, n2, ... would have been treated as nodes. Instead, any object that implements the ES6 iterator protocol can be used. This includes (by default) arrays and generator functions.
• Graph classes cannot be instantiated without new anymore. I.e. you have to use var G = new jsnx.Graph(); instead of var G = jsnx.Graph();. That's because ES6 classes cannot be called without new.
• The utility methods cumulative_sum, generate_unique_node and is_list_of_ints have been removed, since there was no need for them.

Algorithms

• balancedTree doesn't set the height to 2 anymore if the branching factor is 1. So balancedTree(1, 4) is equivalent to pathGraph(4).

Drawing

• Like with method names, drawing options are camelCase now instead of under_score.

Fixed

Drawing

• Fixed dragging (canvas doesn't pan while node is dragged).