Following on from my last post about modelling graphs as data structures in F#, in this post I show how to use Microsoft’s graphing tool GLEE to plot the graph.

The previous post is here: F#: A Data Structure For Modelling Directional Graphs.

**Introducing GLEE**

GLEE is an early version of Microsoft Automatic Graph Layout (MSAGL) pioneered by Microsoft Research. GLEE is free to download and use for non-commercial purposes (read the full licence agreement!); MSAGL is a fully supported and paid product. You can find out more about GLEE and MSAGL here at the Microsoft Research site here: http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/default.aspx.

This is a sample screenshot produced using GLEE:

**Using GLEE with F#**

Firstly, you must install GLEE. The defaults cause GLEE to be installed in C:\Program Files\Microsoft Research\GLEE. Next, you need to add the following assemblies to your F# project:

- System.Windows.Forms
- System.Drawing
- Microsoft.GLEE
- Microsoft.GLEE.Drawing
- Microsoft.Glee.GraphViewerGDI

There are two parts to the process of using GLEE with the F# graph structure that I introduced in the previous post:

- Converting the graph to a format used by GLEE
- Displaying the graph using the GLEE controls

An alternative for new projects is to use the GLEE data structures to represent the graph in the first place.

**Converting the graph to a format used by GLEE**

The data structure I introduced previously uses an adjacency list approach. One drawback of this approach is that a vertex’s adjacency list may refer to another vertex later in the list of vertices. This makes it difficult to translate to a GLEE graph in a single pass of the data structure. For simplicity, the approach I will use requires two passes of the data structure, the first to find all the vertices and the second to add all the edges.

To contain the new methods, I have added another module to the project: GleeGraph.fsi and GleeGraph.fs:

**GleeGraph.fsi**

This file extends the existing Graph module with support for GLEE:

#light open Graph open Microsoft.Glee.Drawing module Graph = type NodeAdapter<'V,'E> = Vertex<'V,'E> -> Node -> unit type EdgeAdapter<'E> = EdgeData<'E> -> Edge -> unit val toGlee<'V,'E> : string -> NodeAdapter<'V,'E> -> EdgeAdapter<'E> -> Graph<'V,'E> -> Graph val graphForm : string -> NodeAdapter<'V,'E> -> EdgeAdapter<'E> -> Graph<'V,'E> -> System.Windows.Forms.Form

The NodeAdapter and EdgeAdapter functions allow the calling context to adapt the display of nodes and edges as they are created, possibly using information stored in the graph to change the appearance of the graph. The toGlee function converts a Graph to a GLEE graph. Note that the ambiguity of type names is solved by the fact that the Graph type I created is generic. However, this is still unfortunate! Remember, Graph<_,_>, Vertex<_,_>, VertexData<_>, Adjacency<_>, EdgeData<_> are types from the F# graph data structure and Graph, Node and Edge are part of GLEE.

**GleeGraph.fs**

This file contains the actual implementation details:

#light open Graph open Microsoft.Glee.Drawing open System.Windows.Forms module Graph = type NodeAdapter<'V,'E> = Vertex<'V,'E> -> Node -> unit type EdgeAdapter<'E> = EdgeData<'E> -> Edge -> unit (* function to create an empty GLEE graph *) let newGlee = fun name -> new Microsoft.Glee.Drawing.Graph(name) (* add a GLEE node to the graph *) let newNode = fun (id:string) -> fun (nodeAdapter:Node->unit) -> fun (g:Microsoft.Glee.Drawing.Graph) -> let n = g.AddNode(id) nodeAdapter n (* add a GLEE edge to the graph *) let newEdge = fun (v1:string) -> fun (v2:string) -> fun (edgeAdapter:Edge->unit) -> fun (g:Microsoft.Glee.Drawing.Graph) -> let e = g.AddEdge(v1, v2) edgeAdapter e (* create a GLEE representation of a Graph<_,_> *) let toGlee<'V,'E> name (nodeAdapter:NodeAdapter<'V,'E>) (edgeAdapter:EdgeAdapter<'E>) (g:Graph<'V,'E>) = let x = newGlee name let l = snd g let processNode y = x |> newNode ((y |> vertexId).ToString()) (nodeAdapter y) let processEdge start (y:EdgeData<_>) : unit = match y with | (a,b,c,d) -> x |> newEdge (start.ToString()) (c.ToString()) (edgeAdapter y) l |> List.rev |> List.iter processNode; l |> List.rev |> List.iter ( fun z -> (snd z) |> List.rev |> List.iter (processEdge (fst z |> fst))); x (* Create a Windows Form to display a GLEE graph *) let graphForm name (nodeAdapter:NodeAdapter<'V,'E>) (edgeAdapter:EdgeAdapter<'E>) (g:Graph<'V,'E>) = let frm = new System.Windows.Forms.Form() frm.Text <- name let gc = new Microsoft.Glee.GraphViewerGdi.GViewer() gc.Graph <- toGlee name nodeAdapter edgeAdapter g gc.Dock <- System.Windows.Forms.DockStyle.Fill; frm.Controls.Add gc frm

The lists are reversed in the toGlee function because when the Graph<_,_> is created, the new vertices and edges are placed at the front of the list. This may make a difference for the plotting of some graphs but GLEE appears to layout the graph as it considers best.

**Program.fs**

You can use the following code to see a complete process:

#light open System.Windows.Forms open Microsoft.Glee.Drawing open Graph open GleeGraph let nodeAdapter (v:Vertex<_,_>) (n:Microsoft.Glee.Drawing.Node) = n.Attr.Shape <- Shape.Box n.Attr.Color <- Color.Blue let edgeAdapter (ed:EdgeData<_>) (e:Microsoft.Glee.Drawing.Edge) = e.Attr.Color <- Color.Red Graph.empty |> Graph.addVertex "vertex1" |> (fun (v1,g) -> (Graph.addVertex "vertex2" g) |> (fun (v2,g) -> (Graph.addEdge 0 v1 v2 "edge1" g))) |> snd |> Graph.graphForm "example" nodeAdapter edgeAdapter |> System.Windows.Forms.Application.Run

You should see output similar to the following. You should see one main difference in that the vertex numbers should differ. That is because I changed my Graph code to number edges and vertices separately. I will provide the code in the next post when I show how to produce a non-deterministic finite state machine from the regular expression syntax previously parsed.

**References**

- My earlier post with the Graph data structure code: https://stevehorsfield.wordpress.com/2009/07/27/f-a-data-structure-for-modelling-directional-graphs/
- Microsoft Automatic Graph Layout (MSAGL) and GLEE: http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/default.aspx
- QuickGraph for .NET: http://quickgraph.codeplex.com/Wiki/View.aspx?title=Home [this project led me to GLEE but I have not used it directly]

Pingback: F#: Compiling a Regular Expression Syntax « Steve Horsfield

Pingback: F#: A Complete Regular Expression Processor « Steve Horsfield

Pingback: Microsoft GLEE and AGL resources « Steve Horsfield