oct. 31

## How to render a finite state machine graph in ASP.NET ?

Currently I'm working with finite state machine and I was searching for an easy way of rendering them. I have found the free tool Graphviz and I was wondering how we could use it to render a graph in an ASP.NET environment.

# Prerequisites : the tool

For the sake of this example, I will use Graphviz. This is a C++ set of tool that can be used to render many types of graphes. Very interesting and it can be questionnable in command line.

Graphviz works from a "dot file" : a text file that represent the graph vertices and edges.

To be able to generate this dot file, I will use Quickgraph. This is a free .NET library create by Jonathan Halleux. It can be used for creating and manipulating graphs, as for doing calculation on graphes (shortest path, ...). For the rendering, it can be used with MSAGL (Microsoft Automatic Graph Layout - ex Microsoft GLEE). As this tool is NOT free, I will combine the two tool to achieve this work.

# Generating the graph

• Let's create a website and add a new Generic Handler
• Right-clic on the website
• Choose Web and then Generic Handler
• Name it GraphGeneratorAndRenderer
• Add a reference to QuickGraph.dll and QuickGraph.Graphviz.dll
• Modify your handler as follow:
using System.Web;

using QuickGraph;



//To ease the writing of our graph, we can use type aliases

using TEdge = QuickGraph.TaggedEdge<string, string>;

using TVertex = System.String;



namespace WebApplication1

{

   public class GraphGeneratorAndRenderer : IHttpHandler

   {

      private AdjacencyGraph<TVertex, TEdge> CreateGraph()

      {

         AdjacencyGraph<TVertex, TEdge> graph = new AdjacencyGraph<TVertex, TEdge>();



         //1. Let's declare our vertices (ie our states)

         TVertex init = "Initial State";

         TVertex cancelled = "Cancelled";

         TVertex deleted = "Deleted";

         TVertex scheduled = "Scheduled";

         TVertex expected = "Expected";



         //2. Let's add them to our graph

         graph.AddVertex(init);

         graph.AddVertex(cancelled);

         graph.AddVertex(deleted);

         graph.AddVertex(scheduled);

         graph.AddVertex(expected);



         //3. Let's add the edges between our states

         graph.AddEdge(new TEdge(init, deleted, "Delete"));

         graph.AddEdge(new TEdge(init, scheduled, "Reception of a schedule"));

         graph.AddEdge(new TEdge(scheduled, cancelled, "CNL message"));

         graph.AddEdge(new TEdge(scheduled, expected, "Reception of Flight plan"));

         graph.AddEdge(new TEdge(expected, cancelled, "CNL message"));

         graph.AddEdge(new TEdge(scheduled, init, "Reinitialization"));

         graph.AddEdge(new TEdge(expected, init, "Reinitialization"));



         return graph;

      }



      public void ProcessRequest(HttpContext context)

      {

      }



      public bool IsReusable

      {

         get { return false; }

      }

   }

}


# Transforming the graph to a dot file

More precisely we do not want to generate a file, but we want to have the dot structure, so we can use it in the future.

Quickgraph expose a GraphvizAlgorithm that will be responsible of the generation of the graph into a dot structure and it will transfer this to a IDotEngine that can be used for extra processing. By default, Quickgraph expose a FileDotEngine that will generate a file containing the dot structure. As this is not satisfying for us, we'll create our own dot engine.

You should of course create the dot engine in a separate file and DLL but for the sake and quickiness of this example, let's put them all together !

Update your generic handler file to add a new class definition :

using QuickGraph.Graphviz;

using QuickGraph.Graphviz.Dot;



public class BitmapGeneratorDotEngine : IDotEngine

{

   #region IDotEngine Members



   public string Run(GraphvizImageType imageType, string dot, string outputFileName)

   {

      return "We should return something here !";

   }



   #endregion

}


and let's add a method to our generic handler and complete the ProcessRequest method.

public class GraphGeneratorAndRenderer : IHttpHandler

{

   private string GenerateBitmap(AdjacencyGraph<TVertex, TEdge> graph)

   {

      GraphvizAlgorithm<TVertex, TEdge> algo = new GraphvizAlgorithm<TVertex, TEdge>(graph);

      string output = algo.Generate(new BitmapGeneratorDotEngine(), "ignored");

      return output;

   }



   public void ProcessRequest(HttpContext context)

   {

      AdjacencyGraph<TVertex, TEdge> graph = CreateGraph();

      string bitmap = GenerateBitmap(graph);

   }



   //Other implementation remains unchanged

}


Let's now check the dot structure:

• Right-Clic on the website and choose Properties
• Choose Web
• For the Start Action, set Specific Page, and give the name of your handler : GraphGeneratorAndRenderer.ashx
• Add a breakpoint in the Run method of you dot engine and press F5

We so have our finite state machine graph rendered in the following dot structure :

digraph G

{

0 [];

1 [];

2 [];

3 [];

4 [];

0 -> 2 [];

0 -> 3 [];

3 -> 1 [];

3 -> 4 [];

3 -> 0 [];

4 -> 1 [];

4 -> 0 [];

}


# Customize the dot structure

It's correct, but we would like to add some labels. Let's simply modify our GraphvizAlgorithm as follows:

private string GenerateBitmap(AdjacencyGraph<TVertex, TEdge> graph)

{

   GraphvizAlgorithm<TVertex, TEdge> algo = new GraphvizAlgorithm<TVertex, TEdge>(graph);

   algo.FormatEdge += delegate(object sender, FormatEdgeEventArgs<TVertex, TEdge> e)

   {

      e.EdgeFormatter.Label.Value = e.Edge.Tag;

   };

   algo.FormatVertex += delegate(object sender, FormatVertexEventArgs<TVertex> e)

   {

      e.VertexFormatter.Label = e.Vertex;

   };

   string output = algo.Generate(new BitmapGeneratorDotEngine(), "ignored");

   return output;

}


If we debug again, we'll have the following dot structure : much better.

digraph G

{

0 [label="Initial State"];

1 [label="Cancelled"];

2 [label="Deleted"];

3 [label="Scheduled"];

4 [label="Expected"];

0 -> 2 [ label="Delete"];

0 -> 3 [ label="Reception of a schedule"];

3 -> 1 [ label="CNL message"];

3 -> 4 [ label="Reception of Flight plan"];

3 -> 0 [ label="Reinitialization"];

4 -> 1 [ label="CNL message"];

4 -> 0 [ label="Reinitialization"];

}


# Convert the dot structure to a bitmap

Let's now go back to the dot engine to improve it in order to generate a bitmap instead. To do so, we'll use the tool dot.exe from Graphviz to do the conversion for us. You will also note that as we do not generate any output file, we do not use the parameter "outputFileName".

public string Run(GraphvizImageType imageType, string dot, string outputFileName)

{

   using ( Process process = new Process() )

   {

      //We'll launch dot.exe in command line

      process.StartInfo.FileName = @"C:\Program Files\Graphviz 2.21\bin\dot.exe";

      //Let's give the type we want to generate to, and a charset

      //to support accent

      process.StartInfo.Arguments = string.Format("-T{0} -Gcharset=latin1", imageType.ToString());

      //We'll receive the bitmap thru the standard output stream

      process.StartInfo.RedirectStandardOutput = true;

      //We'll need to give the dot structure in the standard input stream

      process.StartInfo.RedirectStandardInput = true;

      process.StartInfo.UseShellExecute = false;

      process.Start();

      //Let's sent the dot structure and close the stream to send the data and tell

      //we won't give any more

      process.StandardInput.Write(dot);

      process.StandardInput.Close();

      //Wait the process is finished and get back the image (binary format)

      process.WaitForExit(1000);

      return process.StandardOutput.ReadToEnd();

   }

}


# Render the bitmap

What we'll want to do now is to generate an HTML image from this binary bitmap. To do so, we'll use our HTTP Handler as an image source.

• Add a new webform to the website and call it GraphRenderer.aspx
• Add an image on the aspx page and set the URL to the HTTP Handler
<body>

    <form id="form1" runat="server">

    <div>

      <asp:Image runat="server" ID="imgGraph" ImageUrl="~/GraphGeneratorAndRenderer.ashx" />

    </div>

    </form>

</body>


We can now update our HttpHandler to render the image:

public void ProcessRequest(HttpContext context)

{

   AdjacencyGraph<TVertex, TEdge> graph = CreateGraph();

   string binaryBitmap = GenerateBitmap(graph);



   //Save the bitmap to the response stream

   Stream stream = context.Response.OutputStream;

   using ( StreamWriter sw = new StreamWriter(stream, Encoding.Default) )

      sw.Write(binaryBitmap);

}


# What to know ?

There are several things to know / drawback about his solution. As you may have seen, we have specified a timeout in the WaitForExit method. Indeed, there is a bug in the Graphviz tool that may freeze when generating some "large" graphs. And the graph we took in example is falling into this category. Giving a timeout gives us the opportunity to get the hand on the tool after 1 second. This value is arbitrary and we consider this is enough for the tool to generate the graph.

So the generation will take 1 second after what we should get the gif, even if we abort the process.

Is there any way to avoid this ugly trick ?

## Generating files

The first solution is to use graphviz to generate output file. To do so, we can just add some command parameters : "-o"c:\temp\MyTempFile.gif"".

This solution is less elegant in my view as it involves some folder security (giving ASPNET / IIS_WPG the right of writing) and cleaning (you should clear this temp folder after a while).

## Reading the standard output asynchronously

Another solution is to read the standard output asynchronously. For a reason I cannot explain, when doing so, no error / freeze can be encountered.

We have two solutions to do that : we can work high-level using the Process methods to do asynchronous reading : BeginOutputReadLine and OutputDataReceived. This will not work. Indeed in the OutputDataReceived's event handler, when accessing the e.Data property to get a line of data, we won't get any line ending (\r, \n or \r\n). This highly critical as each line of a gif image will be ended either by \r or by \n. Changing one of this delimiter will produce an unreadable image !

So how can we achieve that ? Going a bit lower level and accessing directly the underlying stream to read it asynchronously. And this will work like a charm ! Let's see some code to see how to get it work :

public class BitmapGeneratorDotEngine : IDotEngine

{

   private Stream standardOutput;

   private MemoryStream memoryStream = new MemoryStream();

   private byte[] buffer = new byte[4096];



   public string Run(GraphvizImageType imageType, string dot, string outputFileName)

   {

      using ( Process process = new Process() )

      {

         //We'll launch dot.exe in command line

         process.StartInfo.FileName = @"C:\Program Files\Graphviz 2.21\bin\dot.exe";

         //Let's give the type we want to generate to, and a charset

         //to support accent

         process.StartInfo.Arguments = "-Tgif -Gcharset=latin1";

         process.StartInfo.WindowStyle = ProcessWindowStyle.Minimized;



         //We'll receive the bitmap thru the standard output stream

         process.StartInfo.RedirectStandardOutput = true;

         //We'll need to give the dot structure in the standard input stream

         process.StartInfo.RedirectStandardInput = true;

         process.StartInfo.UseShellExecute = false;

         process.Start();

         standardOutput = process.StandardOutput.BaseStream;

         standardOutput.BeginRead(buffer, 0, buffer.Length, StandardOutputReadCallback, null);

         //Let's sent the dot structure and close the stream to send the data and tell

         //we won't give any more

         process.StandardInput.Write(dot);

         process.StandardInput.Close();

         //Wait the process is finished and get back the image (binary format)

         process.WaitForExit();

         return Encoding.Default.GetString(memoryStream.ToArray());

      }

   }



   private void StandardOutputReadCallback(IAsyncResult result)

   {

      int numberOfBytesRead = standardOutput.EndRead(result);

      memoryStream.Write(buffer, 0, numberOfBytesRead);



      // Read next bytes.

      standardOutput.BeginRead(buffer, 0, buffer.Length, StandardOutputReadCallback, null);

   }

}


We will store the standard output base stream and use the BeginRead method on it to start getting the output. Each time we'll receive an output - via the read callback - we'll put temporarily the data in a buffer, and then write them in a stream. The read callback will call himself recursively until the process exit.

Tags: | |

Commentaires

Posted on mercredi, 17 décembre 2008 07:23

i will give it a try based on the step given above.

Posted on mercredi, 17 décembre 2008 09:19

Do not hesitate letting a comment in case of problem. We have it running in production right now.

Posted on mercredi, 29 avril 2009 16:40

I am a beginner with C#.NET and I recently used the .NET IDE. And in my work, I must implement a program that generates the graph associated to an assembly of components. I find that these tools are interesting (Quickgraph and Graphviz) and this tutorial is very important and usefull. But, I asked how to configure the.NET IDE library to support Quickgraph to work with.

I would be delighted to help. Thank you!

Posted on dimanche, 17 mai 2009 15:31

Makes me think of a reference graph or something like that. Am I correct ?
If it is the case, you should have a look to Reflector.NET's addins or to NDepend that already do that  out of the box.

Posted on jeudi, 10 décembre 2009 23:04

Hello Pierre Emmanuel, I always have been interested in graph drawing by the busines I work which deals with electrical harness drawing. Your blog is very (^n) interesting. How to transform the code for WinForms?
I thank you very much for sharing knowledge
I am always wowwww gaga in front of people who take time to share knowledge

Posted on vendredi, 11 décembre 2009 10:57

Hello Hichem,

I have never port the code for winforms but I guess there should not be so much difference.
With this code, you receive a string containing the bitmap content. As a consequence, you can just write it to a bitmap object.

In your case, I would be trying to add a container on my winform (like a panel or something) and to get a Graphics object from it. Then I would simply try to use the "DrawBitmap" methods on it. Just like that, I don't remember if you can pass a string directly or if you will need to give a stream object but anyway you could use a StringReader to make.

Just let me know if you succeed to make it work with this clues. Otherwise, I will make a try

Posted on jeudi, 17 décembre 2009 11:14

I have a problem with the image. When I add few vertexes and run the page I get half (image or) graph. Is it image format problem or I need to set size on the image, and if...where can set the maximum image size of the graph.

Thanks.

Posted on vendredi, 18 décembre 2009 13:28

Ohhh that's a very strange problem.
If you run directly the dot tools (outside of the WebApp) giving him your dot structure, does it work correctly ?

Posted on mardi, 12 janvier 2010 10:05

You need to make cnahge on the code in Run():

process.StandardInput.Close();
//Wait the process is finished and get back the image (binary format)
process.WaitForExit(1000);

with

process.WaitForExit(1000);
process.StandardInput.Close();
process.Close();

Otherwise you will get half image of graph.

Posted on mercredi, 3 février 2010 11:17

Thanks for the sample, it's exactly what I was looking for. I'd concur with Gjorgi though, the Run() method should be tweaked a bit to avoid incomplete images. In addition to that, the code will be trapped in an infinite loop in StandardoutputReadCallback if something goes wrong. Following is how I fixed it:

public string Run(GraphvizImageType imageType, string dot, string outputFileName) {
....
process.StandardInput.Close();
process.WaitForExit();
}
...

&nbsp;&nbsp;&nbsp;else {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;standardOutput.Close(); // Nothing left to be read, terminate the async
&nbsp;&nbsp;&nbsp;}
}

I'd also honor outputFileName and try to write out the bits as well.

Posted on mercredi, 3 février 2010 11:23

Trying one more time w/o nbsp;, got fooled by "Live preview"...

public string Run(GraphvizImageType imageType, string dot, string outputFileName) {
....
process.StandardInput.Close();
process.WaitForExit();
}
...
}

}
else {
standardOutput.Close(); // Nothing left to be read, terminate the async
}
}

Posted on jeudi, 11 février 2010 13:02

Hi Pierre-Emmanuel Dautreppe
Thank you for this Exemple of using QuickGraph, But when I tried to implement this exemple I have some problemes
first of all, QuickGraph.NamedEdge<string> not accepted
seconde i don't know what i should to write in run methode

I tried to modifiy this code but also I' haven't any result

this is my code

using System.Web;
using QuickGraph;
using QuickGraph.Algorithms;
using QuickGraph.Graphviz;
using QuickGraph.Graphviz.Dot;

//To ease the writing of our graph, we can use type aliases
//using TEdge = QuickGraph.Edge<string>;
using TVertex = System.String;
using System.Diagnostics;
using System.IO;
using System.Text;

namespace WebApplication1
{

public class GraphGeneratorAndRenderer : IHttpHandler
{
{

//1. Let's declare our vertices (ie our states)
TVertex init = "Initial State";
TVertex cancelled = "Cancelled";
TVertex deleted = "Deleted";
TVertex scheduled = "Scheduled";
TVertex expected = "Expected";

//2. Let's add them to our graph

//3. Let's add the edges between our states

Edge<string> i_c = new Edge<string>(init, cancelled);
Edge<string> i_s = new Edge<string>(init, scheduled);
Edge<string> d_c = new Edge<string>(deleted, scheduled);
Edge<string> e_c = new Edge<string>(expected, init);

return graph;
}

public bool IsReusable
{
get { return false; }
}

{
GraphvizAlgorithm<TVertex, Edge<string>> algo = new GraphvizAlgorithm<TVertex, Edge<string>>(graph);
algo.FormatEdge += delegate(object sender, FormatEdgeEventArgs<TVertex, Edge<string>> e)
{
e.EdgeFormatter.Label.Value = e.Edge.ToString();
};
algo.FormatVertex += delegate(object sender, FormatVertexEventArgs<TVertex> e)
{
e.VertexFormatter.Label = e.Vertex;
};
string output = algo.Generate(new BitmapGeneratorDotEngine(), "ignored");
return output;
}

public void ProcessRequest(HttpContext context)
{
string bitmap = GenerateBitmap(graph);
}        //Other implementation remains unchanged
}

public class BitmapGeneratorDotEngine : IDotEngine
{
#region IDotEngine Members

public string Run(GraphvizImageType imageType, string dot, string outputFileName)
{   return outputFileName;
}

#endregion
}
}

Pending a response, please accept Sir, the assurances of my most respectful greetings.

Posted on vendredi, 12 février 2010 09:29

Hello Achraf,

yes indeed you are right, in the latest version of the library, the class NamedEdge has been removed.
I have updated the code above to use the Quickgraph.TaggedEdge<string, string> class.

Note that doing this, you should also correct the GenerateBitmap method to use the "e.Edge.Tag" instead of "e.Edge.Name".

For the "Run" method, you will see full code in the post.

Posted on vendredi, 12 novembre 2010 14:31

Help.
I keep getting this error:

Error  1  Could not load file or assembly 'QuickGraph.Contracts, Version=3.3.50603.0, Culture=neutral, PublicKeyToken=f3fb40175eec2af3' or one of its dependencies. Strong name signature could not be verified.  The assembly may have been tampered with, or it was delay signed but not fully signed with the correct private key. (Exception from HRESULT: 0x80131045)

Posted on mardi, 19 juillet 2011 05:15

Thanks for the great tutorial. But when i build the code, i getting this error :

The type or namespace name 'TEdge' could not be found (are you missing a using directive or an assembly reference?)  E:\MY EXERCISE\WebApplication2\WebApplication2\GraphGeneratorAndRenderer.ashx.cs  23  63  WebApplication2

Posted on mardi, 19 juillet 2011 07:31

i have many error in code...could you give me your complete source code. thank you very much

Posted on mardi, 19 juillet 2011 08:41

XML Parsing Error: no element found
Location: http://localhost:4904/GraphGeneratorAndRenderer.ashx
Line Number 1, Column 1:

Posted on mardi, 19 juillet 2011 11:29

thanks for the tutorial, sir. but, I've been following in accordance with the steps you give, but when in debug, does not give results, only a blank page. Could you help me? Thanks

Posted on samedi, 13 avril 2013 00:02

Pingback from blogosfera.co.uk

How to draw a colored graph in C# | BlogoSfera

Posted on jeudi, 18 juillet 2013 03:37

I don't even know how I ended up here, but I thought this post was good. I do not know who you are but definitely you're going to a famous blogger if you aren't already ;) Cheers!

Feel free to surf to my page ::  www - http://www.michael-friedrichs.de/node/47383

Posted on dimanche, 18 août 2013 08:10

Here is my weblog -  window cleaning - www.fizzlive.com/member/387592/blog/view/576486

Posted on mardi, 20 août 2013 14:50

Hello There. I found your blog using msn. This is an extremely well written article. I will be sure to bookmark it and return to read more of your useful info. Thanks for the post. I'll certainly return.

Feel free to surf to my web-site ...  best small business - http://mycashtown.com/

Posted on samedi, 7 septembre 2013 12:55

I got this web site from my friend who told me on the topic of this web site and at the moment this time I am visiting this web site and reading very informative posts here.

my web page ...  Proactol reviews - ariginalfitness.com/.../

Posted on vendredi, 20 septembre 2013 07:03

lighting and entertainment. I've a weblog of my 'reading.' Continued me updated!

Take a look at my web-site ...  car insurance Information - www.loveconnections.ca/.../Guidance-On-How-To-Get-Very-Good-Automobile

Posted on vendredi, 20 septembre 2013 14:16

Wow, amazing weblog structure! How long have you ever been running a blog for? you make blogging look easy. The full look of your site is magnificent, let alone the content!

Here is my blog ...  nanny cam - co2gerechtigkeit.de/index.php?title=BenutzeratHellyer

Posted on mardi, 15 octobre 2013 07:28

Also visit my page ...  raniahot webcam - http://www.chat-play.com/raniahot.shtml

Posted on samedi, 2 novembre 2013 05:24

certainly like your web site but you have to check the spelling on several of your posts. Several of them are rife with spelling issues and I find it very bothersome to tell the truth nevertheless I�ll definitely come back again.

Look at my blog post;  wilmington nc - http://wordwrightweb.com/

Posted on lundi, 4 novembre 2013 03:37

I blog frequently and I truly appreciate your content. The article has really peaked my interest. I'm going to book mark your website and keep checking for new information about once a week. I subscribed to your RSS feed too.

Here is my page:  Mighty Raspberry Ketone Diet - proterritorios.net/.../index.php

Posted on jeudi, 5 décembre 2013 19:02

Hi there to all, how is all, I think every one is getting more from this site, and your views are pleasant in favor of new visitors.

My blog post ...  art for sale - http://artgalleryonline.webs.com/

Posted on samedi, 7 décembre 2013 14:06

REVIEW BELLA NAIL DESIGN CHEAP SHIT COUNTERFIT BRAND !!!! STAY AWAY FROM THIS FAKE !!

Stop by my homepage ...  REVIEW BELLA NAIL DESIGN BND CHEAP SHIT COUNTERFIT BRAND !!!! STAY AWAY FROM THIS FAKE !! - http://bellanaildesign.com.au

Posted on samedi, 21 décembre 2013 04:36

Hello, i think that i noticed you visited my weblog so i came to go back the favor?.I'm trying to in finding things to enhance my site!I assume its good enough to use some of your ideas!!

Also visit my web-site -  old navy coupon - www.unreal.fr/.../profile.php

Posted on mercredi, 25 décembre 2013 19:51

I delight in, lead to I discovered just what I used to be having a look for. You've ended my 4 day long hunt! God Bless you man. Have a great day. Bye

My weblog:  home depot promo code 2013 - www.sbwire.com/.../...sed-december-2013-413233.htm

Posted on mercredi, 25 décembre 2013 21:45

Thank you for some other magnificent post. Where else could anyone get that kind of info in such an ideal way of writing? I've a presentation next week, and I am on the look for such info.

My website;  how to get your ex boyfriend back - http://vimeo.com/69285875

Posted on jeudi, 26 décembre 2013 02:34

My brother suggested I would possibly like this website. He used to be totally right. This publish actually made my day. You can not imagine just how so much time I had spent for this info! Thank you!

Have a look at my site ::  what to say to get your ex back - http://www.youtube.com/watch?v=MC1v-0sviJU

Posted on vendredi, 27 décembre 2013 04:07

It's a shame you don't have a donate button! I'd without a doubt donate to this excellent blog! I guess for now i'll settle for bookmarking and adding your RSS feed to my Google account. I look forward to brand new updates and will talk about this blog with my Facebook group. Talk soon!

Here is my web blog -  testerone - myfnf.com/.../alpha-genix-review

Posted on mercredi, 1 janvier 2014 17:18

When I initially commented I seem to have clicked the -Notify me when new comments are added- checkbox and now each time a comment is added I recieve four emails with the same comment. Is there a means you can remove me from that service? Cheers!

Feel free to visit my weblog  advance auto parts coupon - delray.patch.com/.../2014-advanced-auto-parts-coupons-and-promo-codes

Posted on mercredi, 8 janvier 2014 18:16

Having read this I believed it was extremely enlightening. I appreciate you taking the time and effort to put this informative article together. I once again find myself personally spending way too much time both reading and commenting. But so what, it was still worth it!

my page ...  Inn in Bangkok Important - www.hotel-discount.com/destination-spa-resort/

Ajouter un commentaire

• Commentaire
• Aperçu immédiat