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:

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 Zafir.Cytoscape (or WebSharper.Cytoscape ) from NuGet!

Index.html

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 “main”:

<div id="main" style="height:90vh;"></div>

With this we’re finished with the html file. Let’s move onto our Client.fs !

Client.fs

Before coding, let’s think. What do we need?

  1. A list of people
  2. A list of people’s relationships
  3. Setting up the graph
  4. 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.

Nodes
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.

Edges
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

Elements
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 List.toArray too:

The graph
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” div with 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:

In our AlgorithmOptions for the Root and 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.

Result

With this we have finished our graph, the code is ready to run!

The result graph

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.