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

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(N^{2}) 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.

## Comments