Force-Directed Graph Layout in WebSharper

Force-Directed Graph Layout in WebSharper

In this tutorial I demonstrate how to build an interactive force-directed graph visualization running in the browser. Instead of coding directly in JavaScript and HTML5, I take advantage of F#, WebSharper, and Raphael. This technology combo makes it pleasantly simple to navigate the available API. It also reduces mistakes by checking types and units of measure, making the job both easy and fun. Dive in to learn how to make the most out of F# and WebSharper for portable interactive vector graphics in the browser.

Setting Up

To follow the code in the tutorial you will need Microsoft Visual Studio ™ and the latest WebSharper. You will also need WebSharper bindings for Raphael, available in the downloads section.

The complete source code is available in the force-graph repository. You are also welcome to try it out live.

Drawing with Raphael

To quickly get started doing vector graphics, create a new WebSharper project in Visual Studio, choose the "WebSharper 2.4 HTML Application (Sitelets)" template: this template generates the simplest standalone static (HTML, JS, CSS) web apps.

Adding a reference to IntelliFactory.WebSharper.Raphael.dll makes the Raphael library available for use in F#. Let us write a simple test program:

module RaphaelTest =
 open IntelliFactory.WebSharper
 open IntelliFactory.WebSharper.Raphael
 open IntelliFactory.WebSharper.Html

[<JavaScript>] let DrawFigures () = Div [] |>! OnAfterRender (fun canvas -> let r = Raphael(canvas.Dom, 640., 480.) let circle = r.Circle(100., 100., 25.) .Fill("#ff0000") .Opacity(0.4) let triangle = let path = Path() .Absolute .MoveTo(100., 100.) .LineTo(150., 125.) .LineTo(50., 25.) .ClosePath() r.Path(path) .Fill("#00cc00") .Opacity(0.25) circle.Click(fun () -> circle.Opacity(1. - circle.Opacity()) |> ignore) |> ignore triangle.Click(fun () -> triangle.Opacity(1. - triangle.Opacity()) |> ignore) |> ignore ())

Copy this code to your project and run it from a control, for example by setting the body of MyControl type present in the template to the output of the DrawFigures like this:

override this.Body = RaphaelTest.DrawFigures() :> _

Build the project and you will now be able to see the control running on Page 2 and responding to clicks.

Figure 1

Raphael provides a fluent drawing API implemented with the browser SVG support. This approach to visualization is especially suited for vector graphics with a small (under 10000) number of objects, and is compatible with the browser notion of mouse events. The HTML5 Canvas element provides the alternative pixel-based graphics system, but it is out of the scope of this tutorial.

WebSharper bindings to Raphael expose its API in a typed manner, and also add some helper functionality such as the path builder. Try exploring the code in your IDE, relying on code completion and type hints. Building simple graphics and animations can be a lot of fun.

Modeling the Physics

Let us now move on to the force-directed graph layout problem. A basic algorithm for force-directed graph layout builds on two laws of physics: Hooke's law and Coulomb's law. Graph nodes are imagined as points with identical electric charges repulsing each other according to Coulomb's law. Edges become springs that generate a force when compressed or stretched from their optimal length, with Hooke's law describing the force.

The important thing about the laws is that the electric charge repulsion force quadratically decreases with distance, and the spring force is proportional to the displacement from the optimal spring length. The multipliers in the equations are not important and can be picked to produce the desired smoothness.

It would be nice to code the vector form of the laws directly in F#. However, JavaScript execution environment does not support structs. The direct encoding that would model positions and speeds as two-element objects would be allocating O(N2) objects on the heap on every cycle. This is not a very good idea for performance reasons. You can, however, easily model multi-dimensional arrays. I therefore use a simple State object encapsulating such an array to represent the state of our physics system, encoding positions and speeds of N nodes in two dimensions.

One nice feature of F# that is available and relevant to our simulation is units of measure. In F#, you can declare SI units and type-check your float equations for physics compatibility. For example, we can define meters, seconds and Newtons:

[<Measure>] type m
[<Measure>] type s
[<Measure>] type N = m / s ^ 2
 

Without further ado, here is the physics model (Physics.fs), with some arbitrary coefficients that seem to work well. The function describes the update of the state over a time delta dT:

[<JavaScript>]
let Update (g: Graph) (dT: float<s>) (s: State) : State =
 // Euclidian distance between two points.
 let distance (p1x: float<m>) (p1y: float<m>)
              (p2x: float<m>) (p2y: float<m>) : float<m> =
     let dx = p2x - p1x
     let dy = p2y - p1y
     sqrt (dx * dx + dy * dy)
 let kAttr = 0.05<N/m> // Hooke attraction factor
 let kRep = 0.0005<N*m^2> // Coulomb repulsion factor
 let dOpt = 0.1<m> // Optimal distance (spring length at rest)
 let dMin = 0.01<m> // Minimal distance between nodes
 let damping = 0.9 // Friction factor
 let sN = s.Copy()
 for i in 0 .. s.Count - 1 do
     // Cumulative force vector acting on the i-th node.
     let mutable fx = 0.<N>
     let mutable fy = 0.<N>
     // Position of i-th node
     let xi = s.Px i
     let yi = s.Py i
     for j in 0 .. s.Count - 1 do
         // Position of j-th node
         let xj = s.Px j
         let yj = s.Py j
         // Distance between (i, j) nodes.
         let dist = max dMin (distance xi yi xj yj)
         // Normalized direction vector |dir| = 1.
         let xDir = (xj - xi) / dist
         let yDir = (yj - yi) / dist
         // Hooke attraction
         if g.IsConnected(i, j) then
             let delta = dist - dOpt
             fx <- fx + kAttr * delta * xDir
             fy <- fy + kAttr * delta * yDir
         // Coulomb repulsion
         if i <> j then
             fx <- fx - kRep * xDir / (dist * dist)
             fy <- fy - kRep * yDir / (dist * dist)
     let vx = s.Vx(i)
     let vy = s.Vy(i)
     sN.Set(i,
         xi + vx * dT,
         yi + vy * dT,
         damping * (vx + fx * dT),
         damping * (vy + fy * dT))
 sN
 

Grabbing Some Data

Looking for a manageably small graph, I found Les Miserables data, the coappearance network of characters in the novel Les Miserables (appearing in D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, Reading, MA (1993)). I then adapted it for use in the browser by a simple F# script.

Connecting the Dots

To visualize the graph, I draw nodes as circles and edges as lines. On every update, then apply Raphael transforms to move the circles and lines to their new positions. Using transforms has proven to be more efficient than redrawing from scratch (code from Graphs.fs):

[<JavaScript>]
let updateNode (circle: Raphael.Element) (x: float) (y: float) =
 circle.Cx(x).Cy(y).ToFront()
 |> ignore

[<JavaScript>] let updateEdge (line: Raphael.Element) (x1: float) (y1: float) (x2: float) (y2: float) = let dx = x2 - x1 let dy = y2 - y1 let angle = Math.Atan2(dy, dx) / Math.PI * 180. let dist = sqrt (dx * dx + dy * dy) let transform = Raphael.Transform().Absolute .Scale(dist, dist, 0., 0.) .Translate(x1, y1) .Rotate(angle, x1, y1) line.ClearTransform().Transform(transform) |> ignore

The remaining parts of the code are fairly straightforward. I hook up the dataset to the application via JSON. Initial velocities are set to zero, and node positions are assigned randomly - the rest is done by the physics model. Updates are done in an async loop. The initialization and update code looks like this (also from Graphs.fs):

 let redraw (lastTime, lastState: Physics.State) =
     let cT = currentTime ()
     let dT = cT - lastTime
     let st = Physics.Update g dT lastState
     for i in 0 .. nodes.Length - 1 do
         let node = nodes.[i]
         for j in 0 .. node.edges.Length - 1 do
             let edge = node.edges.[j]
             edge.redraw st
         node.redraw st
     (cT, st)
 let rec loop (cT, st) : Async<unit> =
     async {
         do! Async.Sleep 1
         return! loop (redraw (cT, st))
     }
 let initialState =
     let s = Physics.State(nodes.Length)
     let r () =
         2.<m> * random () - 1.<m>
     for i in 0 .. nodes.Length - 1 do
         s.Set(i, r (), r (), 0.<m/s>, 0.<m/s>)
     s
 Async.Start (loop (currentTime (), initialState))
 

You are welcome to explore and experiment with the complete code.

Summary

In this tutorial you have learned how to do interactive vector graphics in the browser. Using Raphael via WebSharper and F# simplified the job by letting you code faster with code completion, make fewer mistakes with type checking, and focus on the problem at hand. You have seen both the basics of doing interactive graphics and a slightly more involved example of doing force-directed graph layout.

You might also like...

Comments

About the author

Anton Tayanovskyy

Anton Tayanovskyy United States

F# developer for IntelliFactory - currently working on WebSharper.

Interested in writing for us? Find out more.

Contribute

Why not write for us? Or you could submit an event or a user group in your area. Alternatively just tell us what you think!

Our tools

We've got automatic conversion tools to convert C# to VB.NET, VB.NET to C#. Also you can compress javascript and compress css and generate sql connection strings.

“We better hurry up and start coding, there are going to be a lot of bugs to fix.”