quick-dijkstra implements the Dijkstra's algorithm as a native C++ library for NodeJS, and as a WebAssembly library for the browsers. Speed tests indicate that the native NodeJS library is approximately 10x faster than the js-graph-algorithms Dijkstra implementation written in pure Javascript. The native NodeJS library is distributed as NPM package @streamr/quick-dijkstra, and the WebAssembly version as @streamr/quick-dijkstra-wasm. Both versions are build from the same codebase (https://github.com/streamr-dev/quick-dijkstra)
The native library gets compiled automatically with npm install
npm install @streamr/quick-dijkstra
const QuickDijkstra = require('@streamr/quick-dijkstra');
let result = QuickDijkstra.calculateShortestPaths([ [0,1,1], [1,2,1], [2,3,1], [3,4,1] ] );
console.log(JSON.stringify(result));
import * as QuickDijkstra from '@streamr/quick-dijkstra';
let result = QuickDijkstra.calculateShortestPaths([ [2,3,1], [0,2,3], [2,1,4] ]);
console.log(JSON.stringify(result));
See the examples/native for a complete example of using the native NodeJS library.
npm test
Runs a speed test against a pure JS Dijkstra implementation of js-graph-algorithms.
npm run speedtest
npm install @streamr/quick-dijkstra-wasm
Pre-compiled WebAssembly files are provided in the NPM package, so compiling the webassembly library is not strictly necessary.
If you wish to compile the webassembly files, first download and install the Emscripten toolkit
Then you can compile the webassembly library by issuing the commands
git clone https://github.com/streamr-dev/quick-dijkstra
cd quick-dijkstra
npm install
npm run npm run wasm-compile
npm run wasm-speedtest
<script src="dijkstraengine.js"></script>
<script src="quickdijkstra-wasm.js"></script>
...
<script>
QuickDijkstraWasm.calculateShortestPaths([ [2,3,1], [0,2,3], [2,1,4] ], ret =>
{
console.log(ret);
}
</script>
See the complete example at examples/wasm/javascript-web
Installation
npm install @streamr/quick-dijkstra-wasm
A project created with create-react-app uses webpack under the hood, and the webpack config needs to be made editable in order to be able to use quick-dijkstra-wasm. This can be achieved with the react-app-rewired package.
Install react-app-rewired and required webpack plugins:
npm i -D react-app-rewired
npm i -D [email protected]
npm i -D write-file-webpack-plugin
npm i -D [email protected]
The react-app-revired uses the file config-overrides.js in the root directory of the project for modifying the webpack config. Create config-overrides.js in the root directory of the project with the following content:
const CopyWebpackPlugin = require('copy-webpack-plugin');
const WriteFilePlugin = require('write-file-webpack-plugin');
module.exports = function override(config, env) {
if (!config.plugins) {
config.plugins = [];
}
config.module.rules[0] = { parser: { requireEnsure: true } };
console.log(config.module.rules);
config.plugins.push(new CopyWebpackPlugin({patterns: [{from: 'node_modules/\@streamr/quick-dijkstra-wasm/dijkstraengine.wasm', to: 'static/js'}]}));
config.plugins.push(new WriteFilePlugin());
config.module.rules.push( {
test: /dijkstraengine\.js$/,
loader: "exports-loader",
options: {
exports: "Module",
}
});
config.module.rules.push( {
test: /dijkstraengine\.wasm$/,
loader: "file-loader",
options: {
publicPath: "build/static/js"
}
});
config.output.futureEmitAssets=false;
return config;
}
Edit package.json to use react-app-rewired instead of react-scripts or react-scripts-ts:
// package.json
"scripts": {
- "start":"react-scripts-ts start",
+ "start": "react-app-rewired start --scripts-version react-scripts-ts",
- "build" "react-scripts-ts build",
+ "build": "react-app-rewired build --scripts-version react-scripts-ts",
- "test": "react-scripts-ts test --env=jsdom",
+ "test": "react-app-rewired test --env=jsdom --scripts-version react-scripts-ts",
"eject": "react-scripts-ts eject"
}
See the complete example at examples/wasm/typescript-react
The folder examples/wasm contains complete examples of using the WebAssembly library in various environments:
- javascript-node is an example of using the WebAssembly library on NodeJS with JavaScript
- typescript-node is an example of using the WebAssembly library on NodeJS with TypeScript
- javascript-web is an example of using the WebAssembly library imported using the script tag on web
- typescript-webpack is an example of using the WebAssembly library in a TypeScript project with webpack
- typescript-react is an example of using the WebAssembly library in a React TypeScript project generated using create-react-app
The most complete example is the typescript-webpackit, as it includes an example of converting a network graph into the format required by the library. Pay attention to the webpack.config.js file; custom rules are neede in order to use the WebAssembly library in a WebPack project. Also note that the .wasm file needs to be served by the web server from the same folder together with the bundled JavaScript file.
The C++ algorithm was inspired by the GeeksforGeeks tutorial by Shubham Agrawal https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl and the Dijkstra's implementation posted by Michal Forišek at https://www.quora.com/What-is-the-most-simple-efficient-C++-code-for-Dijkstras-shortest-path-algorithm