Celestin Apprentice 7/Apprentice-Release7.iso/Source Code/C ++/Applications/TimGA 1.2.1/.cp/CGraphNodes.cp

Text File | 1997-07-16 | 31.2 KB | 1,091 lines | [TEXT/CWIE]

// ===========================================================================
//    CGraphNodes.cp        ©1995-97 Timo Eloranta        All rights reserved.
// ===========================================================================
//    This class takes care of storing the nodes of a single graph drawing
//    (i.e. instances of this class are owned by CGraphDrawing objects...).
//    Since almost all of the mutation and crossover operations manipulate
//    the positions of the nodes, you can find the code for those operations
//    from this class.

#include <PP_Constants.h>

#include "CFitness.h"
#include "CGraphNodes.h"

#include "MyUtils.h"

// ---------------------------------------------------------------------------
//        • CGraphNodes
// ---------------------------------------------------------------------------
//    Constructor.

CGraphNodes::CGraphNodes()
{
    mNodeCount    = 0;
}

// ---------------------------------------------------------------------------
//        • Initialize
//
//          Called by:    CGraphDrawing::Initialize
// ---------------------------------------------------------------------------

void
CGraphNodes::Initialize(
        Int16     inNodeCount,
        Int16     inGridSize,
        Boolean    inFirstTime)
{
    Int16    theIndex, theNodeX, theNodeY;

    mGridSize    = inGridSize;

    if ( inNodeCount != mNodeCount ) {
        mNodesArray.erase( mNodesArray.begin(), mNodesArray.end() );
        mNodesArray.reserve( inNodeCount + 1 );

        for ( theIndex = 0; theIndex <= inNodeCount; ++theIndex )
            mNodesArray.push_back( CNode() );

        mNodeCount = inNodeCount;
    }

    if ( ! inFirstTime )
        ClearAll();

    theIndex = 1;
    while ( theIndex <= mNodeCount ) {

        // Choose random coordinates
        theNodeX = RangedRdm( 1, mGridSize );
        theNodeY = RangedRdm( 1, mGridSize );

        // Test if the square is already taken...
        if (! NodeInSquare( theNodeX, theNodeY ) ) {
            SetNode( theIndex, theNodeX, theNodeY );    // Add it ...
            theIndex++;                                 // ... and advance
        }
    }
}

// ---------------------------------------------------------------------------
//        • NodeInSquare    (PRIVATE)
//
//          Called by:    CGraphNodes::Initialize
//                        CGraphNodes::SingleMutate
//                        CGraphNodes::MoveEdge
//                        CGraphNodes::Move3ConnectedNodes etc.
// ---------------------------------------------------------------------------
//  Returns a pointer to the node in a given location or nil if square empty.

CNodePtr
CGraphNodes::NodeInSquare( Int16 inX, Int16 inY ) const
{
    NodeVector::const_iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        if ( theIter -> HasPosition( inX, inY ) )
            return (CNodePtr) theIter;
        ++theIter;
    }
    return nil;        // The square is empty...
}

// ---------------------------------------------------------------------------
//        • ClearAll        (PRIVATE)
//
//          Called by:    CGraphNodes::Initialize
//                        CGraphNodes::RectCrossover
// ---------------------------------------------------------------------------

void
CGraphNodes::ClearAll( )
{
    // Clear out the old stuff

    NodeVector::iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        theIter -> Set( 0, 0, 0 );
        ++theIter;
    }
}

// ---------------------------------------------------------------------------
//        • SingleMutate
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations.
//        Move a single node to a random new position (square must be empty...).

void
CGraphNodes::SingleMutate()
{
    Int16    theNodeNbr, theNewNodeX, theNewNodeY;

    theNodeNbr    = RangedRdm( 1, mNodeCount );    // Random node nbr

    do {
        theNewNodeX = RangedRdm( 1, mGridSize );
        theNewNodeY = RangedRdm( 1, mGridSize );

    } while ( NodeInSquare( theNewNodeX, theNewNodeY ));

    SetNodePos( theNodeNbr, theNewNodeX, theNewNodeY );
}

// ---------------------------------------------------------------------------
//        • TinyMutate
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations. Move a single node just a bit.

Boolean
CGraphNodes::TinyMutate()
{
    Int16    theNodeNbr, theX, theY, theNewX, theNewY, theFails = 0;

    theNodeNbr    = RangedRdm( 1, mNodeCount );    // Random node nbr

    mNodesArray[ theNodeNbr ].GetNodePos( theX, theY );

    do {
        theNewX    = RangedRdm( theX - 1, theX + 1 );
        theNewY = RangedRdm( theY - 1, theY + 1 );

        if ( InsideAndFree( theNewX, theNewY ) ) {
             SetNodePos( theNodeNbr, theNewX, theNewY );
             return true;
        }
        else ++theFails;

    } while ( theFails < 3 );    // Try max 3 times before giving up...

    return false;    // We were unsuccessful in placing the node!
}

// ---------------------------------------------------------------------------
//        • TinyMoveEdge
//
//          Called by:    CGraphDrawing::EdgeMutation
// ---------------------------------------------------------------------------
//      One of the mutation variations. Move a single edge just a bit.

Boolean
CGraphNodes::TinyMoveEdge(
    CNodePtr inNode1,
    CNodePtr inNode2 )
{
    Int16    theNodeNbr1, theNodeNbr2,
            theX1, theY1, theX2, theY2,
            theNewX1, theNewY1, theNewX2, theNewY2,
            thePreferredX2, thePreferredY2, theFails = 0;
    Boolean theNode1Moved = false;

    theNodeNbr1    = inNode1 -> GetNodeNbr();
    theNodeNbr2    = inNode2 -> GetNodeNbr();

    inNode1        -> GetNodePos( theX1, theY1 );
    inNode2        -> GetNodePos( theX2, theY2 );

    // First we try to relocate the    other end of the edge

    do {

        theNewX1 = RangedRdm( theX1 - 1, theX1 + 1 );
        theNewY1 = RangedRdm( theY1 - 1, theY1 + 1 );

        if ( InsideAndFree( theNewX1, theNewY1 )) {
             SetNodePos( theNodeNbr1, theNewX1, theNewY1 );
             theNode1Moved = true;
             break;
        }
        else ++theFails;

    } while ( theFails < 3 );    // Try max 3 times before giving up...

    if ( theNode1Moved )
        theFails = 0;
    else
        return false;    // If we couldn't move the first node,
                        // we'll leave the other node untouched as well
    theFails = 0;

    // We'll try to keep the edge in its original length and form.

    theNewX2 = thePreferredX2 = theNewX1 + ( theX2 - theX1 );
    theNewY2 = thePreferredY2 = theNewY1 + ( theY2 - theY1 );

    do {

        if (! ( InsideAndFree( theNewX1, theNewY1 ))) {

            ++theFails;

            theNewX2 = RangedRdm( thePreferredX2 - 1, thePreferredX2 + 1 );
            theNewY2 = RangedRdm( thePreferredY2 - 1, thePreferredY2 + 1 );
        }
        else {
             SetNodePos( theNodeNbr2, theNewX2, theNewY2 );
             return true;
        }

    } while ( theFails < 3 );    // Try max 3 times before giving up...

    return true;    // The 2nd node didn't move but the 1st did!
}

// ---------------------------------------------------------------------------
//        • MoveEdge
//
//          Called by:    CGraphDrawing::EdgeMutation
//                        CGraphDrawing::TwoEdgeMutation
// ---------------------------------------------------------------------------
//      One of the mutation variations.

void
CGraphNodes::MoveEdge(
    CNodePtr    inNode1,
    CNodePtr    inNode2,
    Boolean        inPreserveLength )
{
    Int16    theNodeNbr1, theNodeNbr2,
            theX1, theY1, theX2, theY2, theXdiff, theYdiff,
            theNewX1, theNewY1, theNewX2, theNewY2;

    theNodeNbr1    = inNode1 -> GetNodeNbr();
    theNodeNbr2    = inNode2 -> GetNodeNbr();

    inNode1    -> GetNodePos( theX1, theY1 );
    inNode2    -> GetNodePos( theX2, theY2 );

    do {
        theNewX1 = RangedRdm( 1, mGridSize);
        theNewY1 = RangedRdm( 1, mGridSize);
    } while ( NodeInSquare( theNewX1, theNewY1 ) );

    SetNodePos( theNodeNbr1, theNewX1, theNewY1 );

    // We have now moved the other end (= node1) of the edge. We now move
    // the other end. If the boolean parameter inPreserveLength is true,
    // we try to place the other node to an equal location in relation to
    // the first node. If that cannot be done (if the wanted square is
    // outside the grid or already taken) we try the other three squares
    // in the original distance before giving up and placing the other end
    // to a random free square...

    if ( inPreserveLength ) {

        theXdiff = ( RandomBool() ) ? theX2 - theX1 : theX1 - theX2;
        theYdiff = ( RandomBool() ) ? theY2 - theY1 : theY1 - theY2;

        theNewX2 = theNewX1 + theXdiff;
        theNewY2 = theNewY1 + theYdiff;

        if ( ! InsideAndFree( theNewX2, theNewY2 )) {
            theNewX2 = theNewX1 - theXdiff;

            if ( ! InsideAndFree( theNewX2, theNewY2 )) {
                theNewY2 = theNewY1 - theYdiff;

                if ( ! InsideAndFree( theNewX2, theNewY2 )) {
                    theNewX2 = theNewX1 + theXdiff;

                    if ( ! InsideTheGrid( theNewX2, theNewY2 )) {
                        theNewX2 = RangedRdm( 1, mGridSize );
                        theNewY2 = RangedRdm( 1, mGridSize );
                    }

                    while ( NodeInSquare( theNewX2, theNewY2 ) ) {
                        theNewX2 = RangedRdm( 1, mGridSize );
                        theNewY2 = RangedRdm( 1, mGridSize );
                    }
                }
            }
        }

    } else {

        do {
            theNewX2 = RangedRdm( 1, mGridSize );
            theNewY2 = RangedRdm( 1, mGridSize );
        } while ( NodeInSquare( theNewX2, theNewY2 ) );
    }

    SetNodePos( theNodeNbr2, theNewX2, theNewY2 );
}

// ---------------------------------------------------------------------------
//        • Move3ConnectedNodes
//
//          Called by:    CGraphDrawing::TwoEdgeMutation
// ---------------------------------------------------------------------------
//      One of the mutation variations.
//        Moves two edges which share one of their endpoints.
//        For comments see MoveEdge. This is very similar...

void
CGraphNodes::Move3ConnectedNodes(
    CNodePtr    inNode1,
    CNodePtr    inNode2,
    CNodePtr    inNode3 )
{
    Int16    theX1, theY1, theX2, theY2, theX3, theY3,
            theNewX1, theNewY1, theNewX2, theNewY2, theNewX3, theNewY3;

    Int16    theNodeNbr1    = inNode1 -> GetNodeNbr();
    Int16    theNodeNbr2    = inNode2 -> GetNodeNbr();
    Int16    theNodeNbr3    = inNode3 -> GetNodeNbr();

    inNode1    -> GetNodePos( theX1, theY1 );
    inNode2    -> GetNodePos( theX2, theY2 );
    inNode3    -> GetNodePos( theX3, theY3 );

    do {
        theNewX1 = RangedRdm( 1, mGridSize);
        theNewY1 = RangedRdm( 1, mGridSize);
    } while ( NodeInSquare( theNewX1, theNewY1 ) );

    SetNodePos( theNodeNbr1, theNewX1, theNewY1 );

    // One node done. Two to go...

    Int16    theX12diff = ( RandomBool() ) ? theX2 - theX1 : theX1 - theX2;
    Int16    theY12diff = ( RandomBool() ) ? theY2 - theY1 : theY1 - theY2;

    theNewX2 = theNewX1 + theX12diff;
    theNewY2 = theNewY1 + theY12diff;

    if ( ! InsideAndFree( theNewX2, theNewY2 )) {
        theNewX2 = theNewX1 - theX12diff;

        if ( ! InsideAndFree( theNewX2, theNewY2 )) {
            theNewY2 = theNewY1 - theY12diff;

            if ( ! InsideAndFree( theNewX2, theNewY2 )) {
                theNewX2 = theNewX1 + theX12diff;

                if ( ! InsideTheGrid( theNewX2, theNewY2 )) {
                    theNewX2 = RangedRdm( 1, mGridSize );
                    theNewY2 = RangedRdm( 1, mGridSize );
                }

                while ( NodeInSquare( theNewX2, theNewY2 ) ) {
                    theNewX2 = RangedRdm( 1, mGridSize );
                    theNewY2 = RangedRdm( 1, mGridSize );
                }
            }
        }
    }

    SetNodePos( theNodeNbr2, theNewX2, theNewY2 );

    // And one more...

    Int16    theX13diff = ( RandomBool() ) ? theX3 - theX1 : theX1 - theX3;
    Int16    theY13diff = ( RandomBool() ) ? theY3 - theY1 : theY1 - theY3;

    theNewX3 = theNewX1 + theX13diff;
    theNewY3 = theNewY1 + theY13diff;

    if ( ! InsideAndFree( theNewX3, theNewY3 )) {
        theNewX3 = theNewX1 - theX13diff;

        if ( ! InsideAndFree( theNewX3, theNewY3 )) {
            theNewY3 = theNewY1 - theY13diff;

            if ( ! InsideAndFree( theNewX3, theNewY3 )) {
                theNewX3 = theNewX1 + theX13diff;

                if ( ! InsideTheGrid( theNewX3, theNewY3 )) {
                    theNewX3 = RangedRdm( 1, mGridSize );
                    theNewY3 = RangedRdm( 1, mGridSize );
                }

                while ( NodeInSquare( theNewX3, theNewY3 ) ) {
                    theNewX3 = RangedRdm( 1, mGridSize );
                    theNewY3 = RangedRdm( 1, mGridSize );
                }
            }
        }
    }

    SetNodePos( theNodeNbr3, theNewX3, theNewY3 );
}

// ---------------------------------------------------------------------------
//        • SwapRows
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations.

void
CGraphNodes::SwapRows()
{
    Int16    theRowNbr1, theRowNbr2,
            theNodeX, theNodeY;

    theRowNbr1 = GetRdmRowOrColWithNode( true );
    theRowNbr2 = GetRdmRowOrColWithException( theRowNbr1 );

    NodeVector::iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        theIter -> GetNodePos( theNodeX, theNodeY );

        if ( theNodeY == theRowNbr1 )
            theIter -> SetNodePos( theNodeX, theRowNbr2 );
        else if ( theNodeY == theRowNbr2 )
            theIter -> SetNodePos( theNodeX, theRowNbr1 );

        ++theIter;
    }
}

// ---------------------------------------------------------------------------
//        • SwapCols
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations.

void
CGraphNodes::SwapCols()
{
    Int16    theColNbr1, theColNbr2,
            theNodeX, theNodeY;

    theColNbr1 = GetRdmRowOrColWithNode( false );
    theColNbr2 = GetRdmRowOrColWithException( theColNbr1 );

    NodeVector::iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        theIter -> GetNodePos( theNodeX, theNodeY);

        if ( theNodeX == theColNbr1 )
            theIter -> SetNodePos( theColNbr2, theNodeY );
        else if ( theNodeX == theColNbr2 )
            theIter -> SetNodePos( theColNbr1, theNodeY );

        ++theIter;
    }
}

// ---------------------------------------------------------------------------
//        • SwapInRowOrCol
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      Two of the mutation variations (SwapInRow & SwapInCol combined).

Boolean
CGraphNodes::SwapInRowOrCol( Boolean inRowSwap )
{
    Int16    theRowOrColNbr,
            theNodeNbr1        = 0, theNodeNbr2    = 0,
            theColOrRow1     = 0, theColOrRow2    = 0;

    theRowOrColNbr = GetRdmRowOrColWithAtLeast2Nodes( inRowSwap );
    if ( theRowOrColNbr == 0 )
        return false;        // No row/col with at least 2 nodes was found!

    GetRdmTwoFromRowOrCol(    inRowSwap, theRowOrColNbr,
                            theNodeNbr1, theNodeNbr2,
                            theColOrRow1, theColOrRow2 );

    if ( inRowSwap ) {
        mNodesArray[ theNodeNbr1 ].SetNodePos( theColOrRow2, theRowOrColNbr );
        mNodesArray[ theNodeNbr2 ].SetNodePos( theColOrRow1, theRowOrColNbr );
    } else {
        mNodesArray[ theNodeNbr1 ].SetNodePos( theRowOrColNbr, theColOrRow2 );
        mNodesArray[ theNodeNbr2 ].SetNodePos( theRowOrColNbr, theColOrRow1 );
    }

    return true;
}

// ---------------------------------------------------------------------------
//        • SmallMutate
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations.
//        Similar to SingleMutate, but with the possibility of a swap.

void
CGraphNodes::SmallMutate()
{
    Int16        theMoverNbr, theOtherNbr,
                theNewNodeX, theNewNodeY,
                theFromX, theFromY;
    CNodePtr    theOtherNode = nil;
    Boolean        theDone = false;

    theMoverNbr    = RangedRdm( 1, mNodeCount );    // This one will move!

    while (! theDone ) {

        theNewNodeX    = RangedRdm( 1, mGridSize);
        theNewNodeY    = RangedRdm( 1, mGridSize);

        // Test if the square is free.
        // If it is, move there, if not, swap places...

        if (! ( theOtherNode = NodeInSquare( theNewNodeX, theNewNodeY )) ) {
            SetNodePos( theMoverNbr, theNewNodeX, theNewNodeY);
            theDone = true;
        } else {    // The square we picked is occupied by "theOtherNode"...

            // If we are unlucky enough to pick the square our
            // "original" node is in, then we'll start over...

            theOtherNode -> GetNodeNbr( theOtherNbr );
            if ( theMoverNbr != theOtherNbr ) {
                mNodesArray[ theMoverNbr ].GetNodePos( theFromX, theFromY );

                SetNodePos( theMoverNbr, theNewNodeX, theNewNodeY);
                SetNodePos( theOtherNbr, theFromX,    theFromY);

                theDone = true;
            }
        }
    }
}

// ---------------------------------------------------------------------------
//        • LargeContMutate
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations.

Boolean
CGraphNodes::LargeContMutate()
{
    Rect    theR1, theR2;            // rects 1 and 2
    Int16    theW, theH;                // width and height
    Boolean    theMovedSomething = false;

    // We need two rects with equal size
    // First we'll deside the width of the rect.
    // We'll restrict both width and height of the rect to half-a-grid.

    theW = RangedRdm( 1, mGridSize / 2 );
    theH = RangedRdm( 1, mGridSize / 2 );

    // Now we know the size. Next we'll determine the places
    // of our two equal sized rects. Lots of random ahead...

    theR1.left     = RangedRdm( 1, mGridSize - theW + 1 );
    theR1.right     = theR1.left + theW - 1;
    theR2.left     = RangedRdm( 1, mGridSize - theW + 1 );
    theR2.right     = theR2.left + theW - 1;

    // So, we didn't restrict the horizontal placement in any
    // way. Next we'll check if we got some overlapping and
    // make sure the rects won't intersect...

    if ( ( theR2.left >= theR1.left && theR2.left <= theR1.right ) ||
         ( theR2.right >= theR1.left && theR2.right <= theR1.right ) ) {

         // Yep, they overlap horizontally. We'll play it safe
         // and position rect 1 high enough so that rect 2 can
         // be placed under it.

        theR1.top     = RangedRdm( 1, mGridSize - ( 2*theH ) + 1 );
        theR1.bottom = theR1.top  + theH - 1;
        theR2.top     = RangedRdm( theR1.bottom + 1, mGridSize - theH + 1 );
        theR2.bottom = theR2.top  + theH - 1;
    }
    else {    // No horizontal overlapping.
            // Vertical placement is unrestricted!

        theR1.top     = RangedRdm( 1, mGridSize - theH + 1 );
        theR1.bottom = theR1.top  + theH - 1;
        theR2.top     = RangedRdm( 1, mGridSize - theH + 1 );
        theR2.bottom = theR2.top  + theH - 1;
    }

    Int16    theX, theY, theDeltaX, theDeltaY;

    theDeltaX = theR2.left - theR1.left;
    theDeltaY = theR2.top  - theR1.top;

    NodeVector::iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        theIter -> GetNodePos( theX, theY );

        if ( MyPtInRect( theX, theY, &theR1 )) {
            theIter -> SetNodePos( theX + theDeltaX, theY + theDeltaY );
            theMovedSomething = true;
        }
        else if ( MyPtInRect( theX, theY, &theR2 )) {
            theIter -> SetNodePos( theX - theDeltaX, theY - theDeltaY );
            theMovedSomething = true;
        }

        ++theIter;
    }

    return theMovedSomething;
}

// ---------------------------------------------------------------------------
//        • InvertRow
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations.
//        Note: returns false only if
//                - the grid has 2N+1 columns AND
//                - we select a row with exactly one node AND
//                - the only node is in column N+1.
//        In other words, returns usually true...

Boolean
CGraphNodes::InvertRow()
{
    return InvertPartRow( true );
}

// ---------------------------------------------------------------------------
//        • InvertPartRow
//
//          Called by:    CGraphDrawing::Mutate
//                        CGraphNodes::InvertRow
// ---------------------------------------------------------------------------
//      One of the mutation variations.
//        Also used by InvertRow

Boolean
CGraphNodes::InvertPartRow( Boolean inInvertWholeRow )
{
    Int16        theRowNbr, theColMin, theColMax;
    Boolean        theMovedSomething = false;

    // Let's pick a row with at least one node so we at least
    // have a *chance* of changing something (doing inversions
    // on an empty row would be sort of useless, right? :-).

    theRowNbr = GetRdmRowOrColWithNode( true );

    // Variables theColMin and theColMax define the part
    // of the row that we'll invert.

    if ( inInvertWholeRow ) {
        theColMin = 1;
        theColMax = mGridSize;
    } else {
        theColMin = RangedRdm( 1, mGridSize - 1 );
        theColMax = RangedRdm( theColMin + 1, mGridSize );
    }

    Int16    theX, theY, theNewX;

    // We now go through the array and change some node positions...

    NodeVector::iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        theIter -> GetNodePos( theX, theY );
        if ( theY == theRowNbr && ( inInvertWholeRow ||
             (theX >= theColMin && theX <= theColMax) ) ) {
                theNewX = theColMax - theX + theColMin;
                theIter -> SetNodePos( theNewX, theY );
                theMovedSomething = true;
        }
        ++theIter;
    }

    return theMovedSomething;
}

// ---------------------------------------------------------------------------
//        • InvertCol
//
//          Called by:    CGraphDrawing::Mutate
// ---------------------------------------------------------------------------
//      One of the mutation variations.
//        Note: returns false only if
//                - the grid has 2N+1 rows AND
//                - we select a column with exactly one node AND
//                - the only node is in row N+1.
//        In other words, returns usually true...

Boolean
CGraphNodes::InvertCol()
{
    return InvertPartCol( true );
}

// ---------------------------------------------------------------------------
//        • InvertPartCol
//
//          Called by:    CGraphDrawing::Mutate
//                        CGraphNodes::InvertCol
// ---------------------------------------------------------------------------
//      One of the mutation variations.
//        Also used by InvertCol
//        For comments see the *very* similar InvertPartRow

Boolean
CGraphNodes::InvertPartCol( Boolean inInvertWholeCol )
{
    Int16        theColNbr, theRowMin, theRowMax;
    Boolean        theMovedSomething = false;

    theColNbr = GetRdmRowOrColWithNode( false );

    if ( inInvertWholeCol ) {
        theRowMin = 1;
        theRowMax = mGridSize;
    } else {
        theRowMin = RangedRdm( 1, mGridSize - 1 );
        theRowMax = RangedRdm( theRowMin + 1, mGridSize );
    }

    Int16    theX, theY, theNewY;

    NodeVector::iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        theIter -> GetNodePos( theX, theY );
        if ( theX == theColNbr && ( inInvertWholeCol ||
             (theY >= theRowMin && theY <= theRowMax) ) ) {
                theNewY = theRowMax - theY + theRowMin;
                theIter -> SetNodePos( theX, theNewY );
                theMovedSomething = true;
        }
        ++theIter;
    }

    return theMovedSomething;
}

// ---------------------------------------------------------------------------
//        • ThreeNodeCrossover
//
//          Called by:    CGraphDrawing::ThreeNodeCrossover
// ---------------------------------------------------------------------------

Boolean
CGraphNodes::ThreeNodeCrossover(
    Int16 inNbr1,    Int16 inNbr2,    Int16 inNbr3,
    Point &inTo1,    Point &inTo2,    Point &inTo3 )
{
    Boolean    theEarthMoved = false;

    if (! NodeInSquare(  inTo1.h, inTo1.v ) ) {
        SetNodePos( inNbr1, inTo1.h, inTo1.v );
        theEarthMoved = true;
    }

    if (! NodeInSquare(  inTo2.h, inTo2.v ) ) {
        SetNodePos( inNbr2, inTo2.h, inTo2.v );
        theEarthMoved = true;
    }

    if ( inNbr3 && (! NodeInSquare( inTo3.h, inTo3.v )) ) {
        SetNodePos( inNbr3, inTo3.h, inTo3.v );
        theEarthMoved = true;
    }

    return theEarthMoved;
}

// ---------------------------------------------------------------------------
//        • RectCrossover
//
//          Called by:    CGraphDrawing::RectCrossover
// ---------------------------------------------------------------------------

void
CGraphNodes::RectCrossover(
    const Rect             &inSourceRect,
    const Rect            &inDestRect,
    const CGraphNodes    &inBaseNodes,
    const CGraphNodes    &inRectNodes )
{
    Int16    theNbr, theX, theY, theAddCount = 0;

    Int16    theXoffset    = inDestRect.left - inSourceRect.left;
    Int16    theYoffset    = inDestRect.top - inSourceRect.top;

    ClearAll();    // We'll want to start with a clear table

    // There are four (4) ways a node can get placed
    // in the graph in this crossover operation:
    //
    //  #1 - If the node is inside the "source rect" in inRectNodes,
    //       it takes the equalent position also in the new graph,
    //         but in the "destination rect"...

    for ( theNbr = 1; theNbr <= mNodeCount; ++theNbr ) {
        inRectNodes.mNodesArray[ theNbr ].GetNodePos( theX, theY );
        if ( MyPtInRect( theX, theY, &inSourceRect ) ) {
            SetNode( theNbr, theX + theXoffset, theY + theYoffset);    // #1
            ++theAddCount;
        }
    }

    //  #2 - If node nbr X didn't get placed in phase #1 and the
    //       position of X is outside the "destination rect" in
    //       inBaseNodes, put it on the same position in the new graph

    for ( theNbr = 1; theNbr <= mNodeCount; ++theNbr ) {
        inBaseNodes.mNodesArray[ theNbr ].GetNodePos( theX, theY );
        if ( (! (mNodesArray[ theNbr ].GetNodeNbr()) ) &&
             (! MyPtInRect( theX, theY, &inDestRect )) ) {
            SetNode( theNbr, theX, theY );                // #2
            ++theAddCount;
        }
    }

    if ( theAddCount == mNodeCount ) return;    // All nodes placed?

    //  #3 - If node X still hasn't got placed and the square in
    //       which X is in inRectNodes is still empty, put X in this
    //         same place in the new graph. Note that if this happens,
    //         then the node X is an "extra crosser" outside of the
    //         actual crossover rect (= inSourceRect) !

    for ( theNbr = 1; theNbr <= mNodeCount; ++theNbr ) {
        inRectNodes.mNodesArray[ theNbr ].GetNodePos( theX, theY );
        if ( (! (mNodesArray[ theNbr ].GetNodeNbr()) ) &&
             (! NodeInSquare( theX, theY )) ) {
            SetNode( theNbr, theX, theY );                // #3
            ++theAddCount;
        }
    }

    if ( theAddCount == mNodeCount ) return;    // All nodes placed?

    //  #4 - The final stage for the nodes that have MAJOR TROUBLE
    //         finding a place in the new graph... In this phase we
    //       select the new place by random, but naturally still
    //         check that the place is free for our node to land into...

    for ( theNbr = 1; theNbr <= mNodeCount; ++theNbr ) {
        if (! (mNodesArray[ theNbr ].GetNodeNbr()) ) {
            while (1) {
                theX = RangedRdm( 1, mGridSize );
                theY = RangedRdm( 1, mGridSize );
                if (! NodeInSquare( theX, theY )) {
                    SetNode( theNbr, theX, theY );
                    ++theAddCount;
                    break;
                }
            }

            if ( theAddCount == mNodeCount ) return;    // Done yet?
        }
    }
}

// ---------------------------------------------------------------------------
//        • GetRdmRowOrColWithNode    (PRIVATE)
//
//          Called by:    CGraphNodes::SwapRows
//                        CGraphNodes::SwapCols
//                        CGraphNodes::InvertPartRow
//                        CGraphNodes::InvertPartCol
// ---------------------------------------------------------------------------
//  We want a random row (or column) with at least one node. What do we do?
//  Well, we take a random node from the array and return its row or column.
//  Note that the number of nodes on a particular row/column determines also
//  the probability of it getting selected! In other words, for example a
//  row with 5 nodes has 5 times as big a chance of getting selected as a row
//  with just one node. This means, that the selection is biased (= not
//  purely random), but on the other hand this method is faster than picking
//  random rows/columns until we find one with at least one node...

Int16
CGraphNodes::GetRdmRowOrColWithNode( Boolean inRowWanted ) const
{
    Int16     theNodeNbr, theRow, theCol;

    theNodeNbr = RangedRdm( 1, mNodeCount );
    mNodesArray[ theNodeNbr ].GetNodePos( theCol, theRow);

    return ( inRowWanted ) ? theRow : theCol;
}

// ---------------------------------------------------------------------------
//        • GetRdmRowOrColWithException    (PRIVATE)
//
//          Called by:    CGraphNodes::SwapRows
//                        CGraphNodes::SwapCols
// ---------------------------------------------------------------------------

Int16
CGraphNodes::GetRdmRowOrColWithException( Int16 inNotThis ) const
{
    Int16    theNbr;

    do    {
        theNbr = RangedRdm( 1, mGridSize );
    } while ( theNbr == inNotThis );

    return theNbr;
}

// ---------------------------------------------------------------------------
//        • GetRdmRowOrColWithAtLeast2Nodes    (PRIVATE)
//
//          Called by:    CGraphNodes::SwapInRowOrCol
// ---------------------------------------------------------------------------

Int16
CGraphNodes::GetRdmRowOrColWithAtLeast2Nodes( Boolean inRowWanted ) const
{
    Int16                theFirst, theRowOrCol,
                        theNodeNbr,
                        theCol, theRow;
    Boolean                theLoopComplete = false;

    vector<bool, allocator<bool> >    theMarkerArray( mGridSize + 1, false );

    theNodeNbr = theFirst = RangedRdm( 1, mNodeCount);

    do {
        mNodesArray[ theNodeNbr ].GetNodePos( theCol, theRow );
        theRowOrCol = ( inRowWanted ) ? theRow : theCol;

        if ( theMarkerArray[ theRowOrCol ] )            // Is this 2nd?
            return theRowOrCol;
        else
            theMarkerArray[ theRowOrCol ] = true;        // Chalk up one!

        ++theNodeNbr;                        // Advance to the next node
        if ( theNodeNbr > mNodeCount )        // Possibly jump to the
            theNodeNbr = 1;                    // beginning of the array

        theLoopComplete = ( theNodeNbr == theFirst );    // Gone around?

    } while ( ! theLoopComplete );

    return 0;    // A row/col with at least two nodes couldn't be found...
}

// ---------------------------------------------------------------------------
//        • GetRdmTwoFromRowOrCol    (PRIVATE)
//
//          Called by:    CGraphNodes::SwapInRowOrCol
// ---------------------------------------------------------------------------

void
CGraphNodes::GetRdmTwoFromRowOrCol(
    Boolean inColsWanted,
    Int16    inFixedRowOrCol,
    Int16    &outNodeNbr1, Int16    &outNodeNbr2,
    Int16     &outRC1,       Int16 &outRC2 ) const
{
    Int16    theNodeNbr, theFirst,
            theCol, theRow,
            theComparator, theHunted;
    Boolean    theLoopComplete = false;

    theNodeNbr = theFirst = RangedRdm( 1, mNodeCount );

    do {
        mNodesArray[ theNodeNbr ].GetNodePos( theCol, theRow );

        theComparator    = ( inColsWanted ) ? theRow : theCol;
        theHunted         = ( inColsWanted ) ? theCol : theRow;

        if ( inFixedRowOrCol == theComparator ) {
            if (! outRC1) {
                outRC1 = theHunted;            // First one found
                outNodeNbr1 = theNodeNbr;
            } else {
                outRC2 = theHunted;            // Second one found
                outNodeNbr2 = theNodeNbr;
                return;                        // We are done...
            }
        }

        ++theNodeNbr;                        // Advance to the next node
        if ( theNodeNbr > mNodeCount )        // Possibly jump to the
            theNodeNbr = 1;                    // beginning of the array

        theLoopComplete = ( theNodeNbr == theFirst );    // Gone around?

    } while ( ! theLoopComplete );
}

// ---------------------------------------------------------------------------
//        • DrawAll
//
//          Called by:    CGraphDrawing::DrawNodes
// ---------------------------------------------------------------------------

void
CGraphNodes::DrawAll( const Rect &inOneOneRect, Int16 inSquareSize) const
{
    NodeVector::const_iterator    theIter = mNodesArray.begin() + 1;

    while ( theIter != mNodesArray.end() ) {
        theIter -> Draw( inOneOneRect, inSquareSize);
        ++theIter;
    }
}

// ---------------------------------------------------------------------------
//        • operator=
//
//          Called by:    CGraphDrawing::BestCopy
// ---------------------------------------------------------------------------

CGraphNodes & CGraphNodes::operator=( const CGraphNodes & inGN )
{
    mNodeCount        = inGN.mNodeCount;
    mGridSize        = inGN.mGridSize;

    mNodesArray        = inGN.mNodesArray;

    return *this;
}

// ---------------------------------------------------------------------------
//        • BruteForceClosestPairs
//
//          Called by:    CGraphDrawing::Evaluate
// ---------------------------------------------------------------------------

void
CGraphNodes::BruteForceClosestPairs( CFitness &inFitness ) const
{
    Int16        theDex1, theDex2, theDist;
    Int32        theMin = max_Int32,
                theMinDistSum = 0L;
    CNodePtr    theNode;

    vector<UInt16, allocator<UInt16> > theDists( mNodeCount + 1, max_Int16 );

    for ( theDex1 = 1; theDex1 <= mNodeCount - 1; theDex1++ ) {
        theNode = (CNodePtr) &mNodesArray[ theDex1 ];

        for ( theDex2 = theDex1 + 1; theDex2 <= mNodeCount; theDex2++ ) {
            theDist    = theNode -> DistanceTo( mNodesArray[ theDex2 ] );

            if ( theDist < theMin )
                theMin = theDist;

            if ( theDist < theDists[ theDex1 ] )
                theDists[ theDex1 ] = theDist;
            if ( theDist < theDists[ theDex2 ] )
                theDists[ theDex2 ] = theDist;
        }
    }

    for ( theDex1 = 1; theDex1 <= mNodeCount; theDex1++ )
        theMinDistSum += theDists[ theDex1 ];

    inFitness.SetMinDistance( theMin, theMinDistSum, mNodeCount, mGridSize );
}