Tuesday, September 12, 2017 Eric Richards

Drawing State Machine Diagrams with Microsoft Automatic Graph Layout

C# MSAGL

TLDR; the Microsoft Automatic Graph Layout library is pretty slick at automatically generating state transition diagrams.

One of the products that I work on for my day job is an instant message-based call center/helpdesk application. It's a pretty complicated beast, but at the heart of it, what it does is:

Allow users to contact a central endpoint.
Process the incoming request
Route the request to a member of a predefined group that can assist the end-user
Broker the conversation between the end-user and the helpdesk/call center agent.
Perform post-processing on the chat session once it has ended.

Internally, each incoming chat session uses a state machine to keep track of the session and its progression through the workflow. For each stage in the pipeline, we've got a State class that handles operations during that particular stage. There is also a table in our state machine which determines what the valid transitions between the states are, so that we can easily assert that the session is following the expected workflow.

This state machine started out fairly simple, with just a few states, but as always happens, we began to accrete features, and so more and more stages were added into the pipeline, and the complexity and number of state transitions grew. The state machine definition that originated as a hastily drawn scrawling on a sheet of printer paper blossomed into a Visio diagram, then eventually wilted into irrelevance as more and more states were added and documentation efforts fell behind. Like most manual processes, it became a pain point, and was neglected.

Things came to a head recently when it was discovered that a state transition had been added as a code path in certain situations, but the state machine transition table had not been updated accordingly, and so it was possible for chats to attempt to make a transition that the state machine would reject as invalid, leaving the chat session in limbo. Not ideal. Ideally, we'd have caught this in some way with compile or build-time static analysis, but getting that implemented is going to have to be an exercise for the future. Failing that, exhaustive unit-tests validating the state transition rules was the easier task, but ran into the difficulty that the hand-written design documentation had fallen out of date, which necessitated a tedious and time-consuming search through the code base to trace out the logic. Once that was complete, there remained the task of updating the Visio docs... which is less than fun to do by hand.

Earlier that week, I had run across a link to the Microsoft Automatic Graph Layout library, a nifty open-source project that makes it stupidly easy to define a graph and then either display it in a Windows Form or render to an image file. While it may not be quite as nice looking as a hand-crafted Visio doc, it's not too unattractive, and better, can be completely automated. So we can just pipe our state transition definitions into it from the source code, and right out comes a legible diagram. We can even run it as a post-build step in our build to automatically keep the documentation up-to-date. Hooray!

State Data

Each state in our state machine is implemented as a class that encapsulates the logic and lifecycle events for that particular stage of the chat conversation. For convenience, each state is tagged with a constant enum value indicating its name/type, which is called SessionState:

public enum SessionState {
    RoutingTagMenu = -4,
    PreChatLookup = -3,
    PreWaiting = -2,
    Waiting = -1,
    Connected = 0,
    Dropped = 1,
    TimedOut = 2,
    RolledOver = 3,
    Completed = 4,
    Disconnected = 5,
    QueueUnavailable = 6,
    Deflected = 7,
    PostConnected = 8,        
}

Our state machine class has a predefined lookup table that maps each state to the states that it is valid to transition into from that state:

public class SessionStateMachine {
    private static readonly Dictionary<SessionState, HashSet<SessionState>> AllowedTransitions = new Dictionary<SessionState, HashSet<SessionState>> {
        { SessionState.RoutingTagMenu, new HashSet<SessionState> {SessionState.PreChatLookup, SessionState.Disconnected, SessionState.Dropped} },
        {SessionState.PreChatLookup, new HashSet<SessionState> {SessionState.PreWaiting, SessionState.Disconnected, SessionState.Dropped, SessionState.Completed} },
        {SessionState.PreWaiting, new HashSet<SessionState> {SessionState.Waiting, SessionState.Disconnected, SessionState.Dropped, SessionState.Deflected} },
        {SessionState.Waiting, new HashSet<SessionState> {SessionState.Connected, SessionState.Disconnected, SessionState.Dropped, SessionState.TimedOut, SessionState.QueueUnavailable } },
        {SessionState.Connected, new HashSet<SessionState> { SessionState.Completed, SessionState.Disconnected, SessionState.Waiting} },
        {SessionState.Completed, new HashSet<SessionState> {SessionState.PostConnected} },
        {SessionState.Disconnected, new HashSet<SessionState> { SessionState.PostConnected} },
        {SessionState.Dropped, new HashSet<SessionState> {SessionState.PostConnected} },
        {SessionState.TimedOut, new HashSet<SessionState> {SessionState.RolledOver,SessionState.PostConnected } },
        {SessionState.RolledOver, new HashSet<SessionState> {SessionState.PostConnected } },
        {SessionState.QueueUnavailable, new HashSet<SessionState> {SessionState.RolledOver, SessionState.PostConnected } },
        {SessionState.Deflected, new HashSet<SessionState> {SessionState.PostConnected } },
        {SessionState.PostConnected, new HashSet<SessionState>() }
    };

    public static IReadOnlyDictionary<SessionState, IReadOnlyCollection<SessionState>> Transitions {
        get {
            return new ReadOnlyDictionary<SessionState, IReadOnlyCollection<SessionState>>(
                AllowedTransitions.ToDictionary(
                    kv => kv.Key,
                    kv => (IReadOnlyCollection<SessionState>)kv.Value.ToList()
                )
            );
        }
    }
    // other details omitted...
}

These transitions are exposed with a readonly collection publicly, just to make doubly sure that they can't be monkeyed with.

Automatically Creating a State Diagram

The MSAGL library makes it incredibly easy to generate a state transition diagram from this definition - the basic driver program shown in the screenshot above is less lines of code than the preceding definitions. In it's entirety:

using System;
using System.Windows.Forms;
using Microsoft.Msagl.Drawing;
using Microsoft.Msagl.GraphViewerGdi;

namespace DrawStateMap {
    
    class Program {
        [STAThread]
        static void Main(string[] args) {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);

            var form = new Form(){Text = "Session State Machine States"};
            // Create the WinForms control for displaying the graph
            var viewer = new GViewer();
            // disable editing the graph in the control
            viewer.LayoutEditingEnabled = false;
            // Create the graph, setting the title
            var graph = new Graph("Session State Machine");
            
            // loop over the state transition definition
            foreach (var state in SessionStateMachine.Transitions) {
                foreach (var nextState in state.Value) {
                    // add an edge between each state that is connected
                    // MSAGL automatically adds any new nodes, and draws the edges as directed arrows
                    graph.AddEdge(state.Key.ToString(), nextState.ToString());
                }
            }
            // Assign the graph to the viewer
            viewer.Graph = graph;
            // Enables saving the rendered graph as an image
            viewer.SaveAsImageEnabled = true;
            // disable layout while adding the viewer control, to prevent weird graphical glitches as it does its layout
            form.SuspendLayout();
            // Make the viewer fill the whole form, and add it to the form
            viewer.Dock = DockStyle.Fill;
            form.Controls.Add(viewer);
            // resume laying out the form
            form.ResumeLayout();
            // launch the form
            Application.Run(form);

        }
    }
}

Make sure that you have added these NuGet packages:

Microsoft.Msagl 1.0.2
Microsoft.Msagl.Drawing 1.0.2
Microsoft.Msagl.GraphViewerGDI 1.0.2

And you should be good to go.

Instead of showing the graph in a form, it is equally simple to render the graph directly to an image:

using (var bitmap = new Bitmap((int)graph.Width, (int)graph.Height )){
    var renderer = new GraphRenderer(graph);
    renderer.Render(bitmap);
    bitmap.Save("graph.png");
}

There is a ton more that you could do to extend this further, and produce prettier diagrams; this is just scratching the surface. But altogether, this has already been a win for me - start to finish, figuring out how MSAGL works and generating this simple driver example took less time than the last time I had to hand-edit our original Visio diagram. And now I can just rerun the program to regenerate the documentation when the state machine changes in the future.