Click here to Skip to main content
15,896,269 members
Articles / Programming Languages / C#

Generic DFA State Machine for .NET

Rate me:
Please Sign up or sign in to vote.
4.75/5 (42 votes)
21 May 2003BSD6 min read 224.9K   3.6K   75  
Seemless NFA to DFA transfers with GraphViz graphing integration
using System;
using leppie.FA;
using leppie.FA.Support;
using System.IO;
using System.Collections;
using leppie;
using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Reflection;

namespace leppie 
{
   /*
   [Guid("32E2F4DA-1BEA-47ea-88F9-C5DAF691C94A")]
   public interface IProfilerCallback
   {
   }
*/
   class Test 
   {
      static string cml;

      static void Main(string[] args)
      {
         cml = String.Join(" ", args);
         DoCharDemo();
         DoStringDemo();
         DoIpDemo();
         DoTypeDemo();
         //StressTest();
         //Debugger.Break();
      }

      static void DoCharDemo()
      {
         CharState root = new CharState();
         StreamReader reader = File.OpenText("chars.txt");
         while (reader.Peek() > -1)
            root.Add(reader.ReadLine().ToCharArray());
         reader.Close();

         //GDI.Render(root);
         GraphAttributes at = GraphAttributes.Default;
         //at.Size = new System.Drawing.SizeF(12, 8);
         //at.Ratio = GraphRatio.filled;
         string filename = "chars";
         TextWriter writer = File.CreateText(filename + ".dot");
         GraphViz.Generate(root, writer, at);
         writer.Close();
         RunDot(filename, "ps");
      }

      static void DoStringDemo()
      {
         StringState root = new StringState();
         StreamReader reader = File.OpenText("strings.txt");
         while (reader.Peek() > -1)
            root.Add(reader.ReadLine().Split(' '));
         reader.Close();
         string filename = "strings";
         TextWriter writer = File.CreateText(filename + ".dot");
         GraphViz.Generate(root, writer);
         writer.Close();
         RunDot(filename, "ps");
      }

      static void DoIpDemo()
      {
         StringState root = new StringState();
         StreamReader reader = File.OpenText("ip.txt");
         while (reader.Peek() > -1)
         {
            string[] ip = reader.ReadLine().Split('|');
            ip[ip.Length - 1] = null;
            root.Add(ip);
         }
         reader.Close();
         string filename = "ip";
         GraphAttributes ga = GraphAttributes.Default;
         //ga.Vertical = true;
         ga.NodeSeperation = 0.2;
         ga.RankSeperation = 0.2;
         
         ga.Concentrate = true;

         TextWriter writer = File.CreateText(filename + ".dot");
         GraphViz.Generate(root, writer, ga);
         writer.Close();
         RunDot(filename, "ps");
      }

      static void DoTypeDemo()
      {
         TypeState root = new TypeState();
         Type[] types = Assembly.GetAssembly(typeof(AtomicState)).GetTypes();

         foreach (Type type in types)
         {
            ArrayList arr = new ArrayList();
            Type etype = type;
            do 
            {
               arr.Insert(0, etype);
               etype = etype.BaseType;
            }
            while (etype != null);

            root.Add( (Type[]) arr.ToArray(typeof(Type)));
         }
   
         string filename = "types";
         TextWriter writer = File.CreateText(filename + ".dot");
         GraphViz.Generate(root, writer);
         writer.Close();
         RunDot(filename, "ps");
      }

      static void RunDot(string filename, string format)
      {
         //try 
         //{
         /////////DO NOT USE JPG//////////////////
            format = "ps";
            GraphVizdotNet.Dot.Exec( String.Format("-T{1} {0}.dot -o {0}.{1}", 
               filename, format));
            //Process.Start("dot", String.Format("-T{1} {0}.dot -o {0}.{1}", 
            //   filename, format));
         //}
         //catch{}
      }

      static void StressTest()
      {
         HiPerfTimer t = new HiPerfTimer();
         CharState root = new CharState();
         System.Windows.Forms.OpenFileDialog ofd = 
            new System.Windows.Forms.OpenFileDialog();
         ofd.Title = "Select a big word list";
         if ( ofd.ShowDialog() != System.Windows.Forms.DialogResult.OK)
            return;
         StreamReader reader = File.OpenText(ofd.FileName);
         ofd.Dispose();
         string entry;
         t.Start();
         while ((entry = reader.ReadLine()) != null)
            root.Add(entry.ToCharArray());
         t.Stop();
         reader.Close();
         Console.WriteLine("Loaded {0} words in {1:F3}ms with {2} states. avg/state: {3:F6}ms", 
            root.AcceptStateCount, t.Duration, root.TotalStateCount, 
            t.Duration/root.TotalStateCount);

         string filename = "bigtest";
         TextWriter writer = File.CreateText(filename + ".dot");
         t.Start();
         GraphViz.Generate(root, writer);
         t.Stop();
         writer.Close();
         Console.WriteLine("Generated graph in {0:F3}ms", 
            t.Duration);
//*/
         t.Start();
         char[][] res = root.AcceptStates(null);
         t.Stop();
         int i = res.Length;
         int j = i;
         Console.WriteLine("Extracted {0} words in {1:F3}ms. avg/word: {2:F6}ms", 
            i, t.Duration, t.Duration/i);
         Random r = new Random();
         t.Start();
         while (j-- > 0)
            root.Accepts(res[r.Next(i)]);
         t.Stop();
         Console.WriteLine("Looked up {0} random entries from {0} entries\n" 
            + "Total time: {1:F3}ms Avg: {2:F6}ms Lookup per sec: {3:F0}", 
            i, t.Duration, t.Duration/i, 1000/(t.Duration/i));
      }
   }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The BSD License


Written By
Software Developer
South Africa South Africa
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions