简单DAG生成算法的一个性质

核心提示： C#代码class DotGenerator { HashSet<Expression> _seenNodes; TextWriter _writer; IEnumerator<string> _nameMaker; Dictionary<Expres

C#代码　　

class DotGenerator {
  HashSet<Expression> _seenNodes;
  TextWriter _writer;
  IEnumerator<string> _nameMaker;
  Dictionary<Expression, string> _nameMap;
  
  public DotGenerator( ) {
    _seenNodes = new HashSet<Expression>(
      IdentityComparer<Expression>.Instance );
    _nameMap = new Dictionary<Expression, string>(
      IdentityComparer<Expression>.Instance );
  }
  
  public string Generate( Expression root ) {
    _nameMaker = GetNameMaker( ).GetEnumerator( );
    _writer = new StringWriter( );
    _writer.WriteLine( "digraph {" );
    _writer.WriteLine( "  node [fontsize=12, font=Courier, shape=plaintext]" );
    GenerateCore( root );
    _writer.WriteLine( "}" );
    var dot = _writer.ToString( );
    
    _seenNodes.Clear( );
    _nameMap.Clear( );
    _nameMaker = null;
    _writer = null;
    return dot;
  }
  
  // depth-first traverse
  void GenerateCore( Expression expr ) {
    DeclareNode( expr );
    _seenNodes.Add( expr );
    switch ( expr.NodeKind ) {
    case NodeKind.Add:
      var addExpr = expr as BinaryExpression;
      var left = addExpr.Left;
      var right = addExpr.Right;
     
      if ( !_seenNodes.Contains( left ) ) {
        GenerateCore( left );
      }
      if ( !_seenNodes.Contains( right ) ) {
        GenerateCore( right );
      }
      _writer.WriteLine( "  {0} -> {1}",
        _nameMap[ expr ], _nameMap[ left ] );
      _writer.WriteLine( "  {0} -> {1}",
        _nameMap[ expr ], _nameMap[ right ] );
      
      break;
    case NodeKind.Id:
      // DO NOTHING
      break;
    }
  }
  

  void DeclareNode( Expression expr ) {
    if ( !_nameMap.ContainsKey( expr ) ) {
      _nameMaker.MoveNext( );
      var name = _nameMaker.Current;
      _nameMap.Add( expr, name );
      switch ( expr.NodeKind ) {
      case NodeKind.Add:
        _writer.WriteLine( "  {0} [label="+"]", name );
        break;
      case NodeKind.Id:
        var idExpr = expr as IdExpression;
        _writer.WriteLine( "  {0} [label="{1}"]", name, idExpr.IdString );
        break;
      }
    }
  }
  
  IEnumerable<string> GetNameMaker( ) {
    for ( var count = 0; ; ++count ) {
      yield return string.Format( "node_{0}", count.ToString( ) );
    }
  }
  
  class IdentityComparer<T> : EqualityComparer<T> {
    static IdentityComparer<T> _instance;
    
    static IdentityComparer( ) {
      _instance = new IdentityComparer<T>( );
    }
    
    public static IdentityComparer<T> Instance {
      get { return _instance; }
    }
    
    public override bool Equals( T first, T second ) {
      return object.ReferenceEquals( first, second );
    }
    
    public override int GetHashCode( T obj ) {
      return obj.GetHashCode( );
    }
  }
}

	 
	 
	
上一页  1 2 3 4 5 6 7 8 9  下一页