A quick note on writing up algorithms

I've been very casual so far about presenting algorithms that I've developed. I've been offering a casual description and some pseudocode or relaxed source code - little or no formality, no analysis. I'm just about to do the same thing for rest of this page.

I've developed a rather detailed format for presenting algorithms and will, someday, begin to use it for presenting my algorithms. This way is faster and I'm using it to get my blog going for now. I'll revisit all algorithms as time permits, write them up formally and consistently, and collect them off of the Research page.

The Algorithms of the Constraint Calculus

          First in thread      Previous in thread      Next in thread

I discussed the Constraint Calculus in a June 5, 2008 post but didn't provide any algorithms in that discussion. Here they are in a rather casual C++ (I stole the foreach and properties from C#, and use 'Append' and 'RemoveAll' for clarity).

An application of the Constraint Calculus

BooleanExpression  expression("ExpressionFile.txt");

expression.BuildTree();
expression.PropagateTruthValue( true );
expression.GatherJunctors();
expression.TransformTreeIntoGraph();
expression.FullyTraverseGraph();

foreach ( ConstraintSet consistentSelectionSet in expression.ModelGenerators() )
{
    cout << consistentSelectionSet << endl;
}

The Build Tree Algorithm

void
BooleanExpression::
BuildTree()
{
    Node *   currentNode;
    Node *   newNode;
    Node *   tempNode;
    char     token;

    while ( ( token = ReadToken() ) != EndOfExpression )
    {
        switch ( NodeType( token ) )
        {
            case  BeginningOfExpression :

                    _root = new Node( Root );
                    currentNode = _root;
                    break;

            case  LeftParenthesis :

                    newNode = newNode ( Group );
                    LinkNodes( currentNode, newNode );
                    currentNode = newNode;
                    break;

            case  RightParenthesis :

                    while ( currentNode->Type != Group )
                    {
                        currentNode = currentNode->Parent;
                    }

                    tempNode = currentNode->Parent;
                    RemoveNode( currentNode );
                    currentNode = tempNode;
                    break;

            case  Not :

                    newNode = new Node( Not );
                    LinkNodes( currentNode, newNode );
                    currentNode = newNode;
                    break;

            case  And :
                  Or :

                    newNode = new Node( NodeType( token ) );

                    while ( newNode->Type <= currentNode->Type )
                    {
                        currentNode = currentNode->Parent;
                    }

                    tempNode = currentNode->RightChild;
                    LinkNodes( currentNode, newNode );
                    LinkNodes( newNode, tempNode );
                    currentNode = newNode;
                    break;

            case  Literal :

                    newNode = new Node( Literal );
                    newNode->Identifier = ReadUnsigned();
                    LinkNodes( currentNode, newNode );
                    currentNode = newNode;
                    break;
        }
    }
}

//  Establishes the proper parent/child linkages between two nodes

void
BooleanExpression::
LinkNodes( Node *   parentNode,
           Node *   childNode )
{
    switch ( parentNode->Type )
    {
        case  Root :
        case  Group :
        case  Not :

                parentNode->RightChild = childNode;
                break;

        case  And :
        case  Or :

                if ( parentNode->LeftChild == NULL )
                {
                    parentNode->LeftChild = childNode;
                }
                else
                {
                    parentNode->RightChild = childNode;
                }
    }

    childNode->Parent = parentNode;
}

//  Removes a node from a binary expression tree, 
//  linking its parent and its right child

void
BooleanExpression::
RemoveNode( Node *   currentNode )
{
    Node *   childNode   =  currentNode->RightChild;
    Node *   parentNode  =  currentNode->Parent;

    if ( parentNode->LeftChild == currentNode )
    {
        parentNode->LeftChild = childNode;
    }
    else
    {
        parentNode->RightChild = = childNode;
    }

    childNode->Parent = parentNode;
    delete currentNode;
}

The Propagate Truth Value Algorithm

void
BooleanExpression::
PropagateTruthValue( bool   targetTruthValue )
{
    _root = PropagateTruthValue( _root, targetTruthValue );
}

Node *
BooleanExpression::
PropagateTruthValue( Node *   currentNode,
                     bool     truthValue )
{
    switch ( currentNode->Type )
    {
        case  Root :

            currentNode->RightChild = 
                PropagateTruthValue( currentNode->RightChild, truthValue );

            return currentNode;

        case  Not :

            {
                Node *   tempNode;

                tempNode = PropagateTruthValue( currentNode->RightChild, 
                                                ! truthValue );
                delete currentNode;

                return tempNode;
            }
                
        case  And :
        case  Or :

            if ( truthValue == false )
            {
                currentNode->Type = ( currentNode->Type == And ) ? Or : And;
            }

            currentNode->LeftChild = 
                PropagateTruthValue( currentNode->LeftChild, truthValue );

            currentNode->RightChild = 
                PropagateTruthValue( currentNode->RightChild, truthValue );

            return currentNode;

        case  Literal :

            currentNode->TruthValue = truthValue;

            return currentNode;
    }
}

The Gather Junctors Algorithm

void
BooleanExpression::
GatherJunctors()
{
    GatherJunctors( _root, NULL );
}

void
BooleanExpression::
GatherJunctors( Node *   currentNode,
                Node *   centerNode )
{
    switch ( currentNode->Type )
    {
        case  Root :

            currentNode->Type = And;
            GatherJunctors( currentNode->RightChild, currentNode );
            break

        case  And :

            if ( centerNode->Type == And )
            {
                GatherJunctors( currentNode->LeftChild, centerNode );
                GatherJunctors( currentNode->RightChild, centerNode );
                delete currentNode;
            }
            else
            {
                centerNode->Children.Append( currentNode );
                GatherJunctors( currentNode->LeftChild, currentNode );
                GatherJunctors( currentNode->RightChild, currentNode );
            }
            break;

        case  Or :

            if ( centerNode->Type == And )
            {
                centerNode->Children.Append( currentNode );
                GatherJunctors( currentNode->LeftChild, currentNode );
                GatherJunctors( currentNode->RightChild, currentNode );
            }
            else  // centerNode->Type == Or
            {
                GatherJunctors( currentNode->LeftChild, centerNode );
                GatherJunctors( currentNode->RightChild, centerNode );
                delete currentNode;
            }
            break;

        case  Literal :

            if ( centerNode->Type == And )
            {
                centerNode->Constraints.AddElement( currentNode->Identifier, 
                                                     currentNode->TruthValue );
                delete currentNode;
            }
            else
            {
                currentNode->Type = And;

                centerNode->Children.Append( currentNode );

                centerNode->Constraints.AddElement( currentNode->Identifier, 
                                                     currentNode->TruthValue );
            }
            break;
    }
}

The Transform Tree Into Graph Algorithm

void
BooleanExpression::
TransformTreeIntoGraph()
{
    _root = TransformTreeIntoGraph( _root, NULL );
}

void
BooleanExpression::
TransformTreeIntoGraph( Node *   currentNode,
                        Node *   nextBlock )
{
    if ( currentNode->Type == And )
    {
        Node *   tempNext  =  nextBlock;

        foreach ( Node *  child in currentNode->Children )
        {
            tempNext = TransformTreeIntoGraph( child, tempNext );
        } 

        currentNode->Next = tempNext;
    }
    else
    {
        foreach ( Node *  child in currentNode->Children )
        {
            TransformTreeIntoGraph( child, nextBlock );
        }
    }

    return currentNode;
}

The Traverse Graph Algorithm

void
BooleanExpression::
TraverseGraph()
{
    _modelGenerators.RemoveAll();

    ConstraintSet   constraints;

    FullyTraverseGraph( _root, constraints );
}

void
BooleanExpression::
TraverseGraph( Node *             currentNode,
               Constraint set &   incomingConstraints )
{
    if ( currentNode == NULL )
    {
        //  this condition stands in for having reached the Stop node

        if ( incomingConstraints.IsConsistent() )
        {
            _modelGenerators.Append( incomingConstraints );
        }
    }
    else
    {
        switch ( currentNode->Type )
        {
            case  And :

                {
                    ConstraintSet   constraints  =  incomingConstraints;

                    constraints.UnionWith( currentNode->Constraints );

                    if ( constraints.IsConsistent() )
                    {
                        TraverseGraph( currentNode->Next, constraints );
                    }
                }
                break;

            case  Or :

                {
                    foreach ( Node *  child in currentNode->Children )
                    {
                        TraverseGraph( child, incomingConstraints );
                    }
                }
                break;
        }
    }
}

          First in thread      Previous in thread      Next in thread

Copyright and Legal Notices

All Rights Reserved.