F#: Graphing with GLEE

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:

MS GLEE Sample

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:

1. Converting the graph to a format used by GLEE
2. 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.

Example

References

• My earlier post with the Graph data structure code: http://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]

About these ads