Wasm Builders

Cover image for Dijkstra's Algorithm + Web Assembly
Jennifer
Jennifer

Posted on

Dijkstra's Algorithm + Web Assembly

Yea, I know what you are thinking ? why the heck am I so bent on shipping my C++ code to the web, well just for the fun of it 🙂

Alright Alright, let me start from the very beginning 😁. Sometime in mid 2020 at the heat of the pandemic, I was at home and bored, so I decided to implement data structures and algorithm in C++, started with Bellman-ford algorithm to sorting algorithms then Dijkstra, but I wasn't satisfied, I wanted real life applications so I decided to take the Dijkstra's algorithm to the web using data gotten from mileage charts.
the mileage chart data was a csv file that looks like this

mileage chart
I wrote the Dijkstra's algorithm in C++ using cmake, it worked quite well, takes two strings as input and displays the shortest distance with paths to follow, you can see code here
A brief summary of steps I took to achieve this:

  • Read the csv file and convert it to a 2D table

  • convert the table to adjacency list

  • implement Dijkstra's algorithm on the adjacency list
    The only problem I had was the fact that it was a command line application as shown

command line image

I wanted to ship it off to the web so bad, so I started researching for solutions
I came across restbed, but I wasn't satisfied with the results and restbed was soo confusing, I even tried converting it to a dll, and using the dll in the JavaScript frontend but that didn't work out either, because I obviously didn't know what I was doing 🤣

stop doing this
So fast forward to sometime in October 2021, I applied for Outreachy internship, during the contribution phase while trying to contribute to the Enarx project, I got introduced to web assembly, and I was like heck yea, this is what I need to complete my long lost Dijkstra's algorithm project !!

Okay... so how do we go about it ??, first was to setup my environment variable.

To compile C/C++ code to WebAssembly, I need a toolchain. This tool will be responsible for translating the code into WebAssembly format. To do that, I installed the Emscripten toolchain. It is an open-source project that can compile any portable C/C++ code into WebAssembly.

cd ~/
git clone https://github.com/emscripten-core/emsdk.git
cd emsdk
emsdk install latest
emsdk activate latest
Enter fullscreen mode Exit fullscreen mode

Add variables to PATH:

emsdk_env.bat             (windows)

source ./emsdk_env.sh      (unix)
Enter fullscreen mode Exit fullscreen mode

The updates that this makes to environment variables isn't persistent; it will need to be run again with the next reboot.

I created a build.sh file to make building easy for me

rm build/ -rf
mkdir build
cd build
em++ ../src/Dijkstra.cpp -g -std=c++1z -s WASM=1 -s 
EXCEPTION_CATCHING_ALLOWED=[..] -o index.js || exit 1
Enter fullscreen mode Exit fullscreen mode

and serve.sh

emrun --port 8080 web/
Enter fullscreen mode Exit fullscreen mode

This will create three files: index.js, index.wasm and index.html.
index.wasm - the compiled version of your program

index.html - an HTML page for hosting your WebAssembly

index.js - JavaScript for loading your WebAssembly into the page

But note that index.html would not be recreated each time I rebuild.
Now, open the browser and access http://localhost:8080

The input will be gotten from the user from the front end (index.html) using Autocomplete function. see here
Embind was used to bind the C++ function to JavaScript and displayed for user as shown

Output Image

And Yes 😄, I finally shipped my Dijkstra's algorithm to the web, you can see full code on github

Image gif

Discussion (1)

Collapse
cohix profile image
Connor Hicks

This is so great! Thanks for sharing.