Start your graph theory website with WebSharper
Graph theory is lovely. I’ve always loved graphs and sets, but would have never thought that it’d make a good website. Cytoscape.js and WebSharper proved me wrong!
In a previous story of mine I’ve talked about it and its WebSharper bind, you can read it here:
Sometimes we just want to show our data in a nicely rendered graph on our website. If we have enough data, everything…medium.com
That story is just the basics of this wonderful extension. Today we’ll create a more complex, yet more beautiful little graph website.
Graphs about people’s relationships are always interesting. Let’s see something like the “Erdős number” implemented as a graph. What’s the point of this? We can have people as nodes and edges as relationships. If we connect every person with another one by some rule, we’ll get a nice graph. On this graph we can do graph algorithms, for example: A Star to find the shortest path between two people.
Just to keep it simple I will use random names and random relationships in our little example, but you could (it’s a fun project) implement the whole Erdős number problem in this example.
Setting up the project
All we need is a WebSharper Single Page Application for this little project. Create it and get
WebSharper.Cytoscape ) from NuGet!
If you’ve read my stories (if not, this one is a perfect start) as usual we’re going to start with the html file. We really don’t need much just a single
div with and
id and a stlye tag with a height. Let’s call our
<div id="main" style="height:90vh;"></div>
With this we’re finished with the html file. Let’s move onto our
Before coding, let’s think. What do we need?
- A list of people
- A list of people’s relationships
- Setting up the graph
- A function for our A Star algorithm
A list of people
A list of people is easy. As I said I’m going to use random names, but you could use any list of names you want:
You could use any representation you’d like to use, but I’m using Lists. This is just a personal preference.
A list of people’s relationships
We have many ways to do this. I thought we could use a list with pairs:
Person, List of people
In the second list we could have the people our person has some kind of relation with.
Let’s see the code for it:
Setting up the graph
Before we could do that, we need a list of nodes and edges from our lists.
Creating nodes are easy, we can just map the node constructor to our
people list like this:
Every node will have the person’s name as an
id . We will need this during the A Star.
This might seem a little bit more complicated, but it’s not! All we have to do is to map our constructor twice! Let’s see the code for it:
First we get our pairs, then we map the edge constructor to our list of relations. Doing this will result a list in a list, but we can solve that with a simple
List.Concat . Our edges have three properties:
- id: Concatenation of the two people names (this will be always unique since we don’t have parallel edges)
- source: The person
- Target: The people from the list paired to the person
Only one thing is left: Creating a single array of the node and edge lists. We have the
List.Append function to do this. But our graph will need an Array so we’ll have to call
As we’ve seen in the basics, we’ll need four things:
- A container for our graph
- A set of elements
- The style of the graph
- A layout
The container is simple, we just get the DOM element for our created “main”
JS.Document.GetElementById "main" .
The elements we’ve just finished.
For the style I am going to use the same settings as for our basic example with one difference: Now we need a
:selected selector to make our A Star path visible.
In my example the
circle layout worked the best, but do experiment with the layouts to found the one you like!
Let’s see our complete graph’s code:
A function for our A Star algorithm
We have many ways to do this. I’ve found the bast way to do this is by right clicking on the nodes we want to connect.
Luckily Cytoscape already has the A Start algorithm implemented, so all we have to do is write the right click event handler. To do this we have to create some reactive variables with
Var.Create . We’re going to use two for the nodes’ id and one to know if we’re at the first or second node we want to select.
Let’s work on our event handler. This function has a
Dom.Event parameter and we’ll use its
Target and that’s
id property. What does this function have to do? Check if we’re at the first or second node, save the node’s id and if we’re on the second node, do the A Star algorithm and select the path. (Of course we will have to deselect the previous path.) Here’s the code:
AlgorithmOptions for the
Goal we have to use Union2Of2 since we are giving the function a selector string and not a Node object.
At the end all we have to do is to bind our
changeAStar function to the
ctxtap event on every
node . (
ctxtap is our right click and two finger tap event.)
I have also locked the nodes so I wouldn’t accidentally move the nodes around while selecting, but you could remove that, it might be fun to play around with it.
With this we have finished our graph, the code is ready to run!
If you want to play around with the code you can do it from your browser! Try out the code we wrote in Try WbSharper following this link:
Be sure to leave a 💚, it helps me know what stories you want to read, and leave a comment if you have any question! Hope you had fun reading the post and found your love for F# and for WebSharper.