_ALGORITHMS FOR DIRECTED GRAPHS_
by Salvatore R. Mangano

Listing One

//File: GRPHPHEN.H

#ifndef __GRPHPHEN_H
#define __GRPHPHEN_H

//Header for EOS class representing a phenotype. 
//You need EOS v1.1 to compile this code
#ifndef __PHENO_H
#include "pheno.h"
#endif //__PHENO_H
                                                        
class CGraphDrawingPheno : public TPhenotype
{
   public:         
    CGraphDrawingPheno(CGAGraphDriver &driver,int width, int height) ;
    ~CGraphDrawingPheno() ;
    double CalcFitness() ;
    void Decode(PTGenotype geno) ;
    PTPhenotype Copy()  ;
    void GetPhenoInfo(void *pInfoStruct)  ;
    void GetNearestEmptyCell(const int row, const int col, int &actualRow,
                                                             int &actualCol) ;
    BOOL Adjacent(WORD node1, WORD node2) ;
    BOOL Diagonal(WORD node1, WORD node2) ;
    BOOL FindNode(const WORD node, int &row, int &col) ;
    double Distance(WORD node1, WORD node2) ;
    double RectDistance(WORD node1, WORD node2) ;
private:
    int m_Width  ;
    int m_Height ;
    CWordMatrix *m_pGrid ;      //grid where each entry is a node 
                                    //                 number or EMPTY_CELL
    CGAGraphDriver &m_Driver ;  //interface to the graph driver class
    int * m_GridIndex[2] ;      //index into grid to quickly locate nodes
};

Listing Two

//File: GRPHPHEN.CPP

#include "stdafx.h"
//eos headers
#include "eos.h"
#include "eosutil.h"
#include "geno.h"

//graph GA headers
#include "grphphen.h"
#include "wmatrix.h"
#include "gdriver.h"
#include "grphutil.h"

const HIGHEST_REWARD = 10 ;
const MEDIUM_REWARD = 5 ;
const SMALLEST_REWARD = 1 ;
const HIGHEST_PENALTY = 10 ;
const MEDIUM_PENALTY = 5;
const SMALLEST_PENALTY = 1;

CGraphDrawingPheno::CGraphDrawingPheno(CGAGraphDriver &driver, int width, int height) 
    : m_Driver(driver) 
{
    m_Width = width ;
    m_Height = height ;
    m_pGrid = new CWordMatrix(height,width,EMPTY_CELL) ;  
    m_GridIndex[0] = new int [m_Driver.GetNumNodes()];
    m_GridIndex[1] = new int [m_Driver.GetNumNodes()];
}
CGraphDrawingPheno::~CGraphDrawingPheno() 
{
    delete m_pGrid ;
    delete [] m_GridIndex[0] ;      
    delete [] m_GridIndex[1] ;
}
double CGraphDrawingPheno::CalcFitness() 
{
    WORD numNodes = (WORD) m_Driver.GetNumNodes() ;
    long maxDist = (m_Width + m_Height) ;
    maxDist*=maxDist;                               
    //set base fitness so even the worst case phenotype 
        //           will not bring fitness below 0
    int connectivity = m_Driver.GetConnectivity() ; 
    double base_fitness = numNodes*(numNodes-1) * maxDist ; 
                                                            //* connectivity; 
    double fitness = base_fitness ;
    for (WORD node1=0;node1<numNodes;node1++) {
        int node1Connections=Max(m_Driver.GetNumConnections(node1),1);
        for (WORD node2=0;node2<numNodes;node2++) {    
            if (node1 == node2)
                continue ;
            BOOL bConnected = m_Driver.Connected(node1,node2) ;
            int node2Connections = 
                                      Max(m_Driver.GetNumConnections(node2),1);
            double distance = Distance(node1,node2) ;
            distance*=distance; 
            if (bConnected && distance > 4)  {
                fitness -= distance ; 
                                       //(node1Connections+node2Connections) ;
                continue ;
                }
            if (!bConnected && distance <= 4)  {
                fitness -= 4/distance ; 
                                        //(node1Connections+node2Connections) ; 
                continue ;
                }
            }                                   
        }
    ASSERT(fitness >= 0);   
    return fitness ;
}
void CGraphDrawingPheno::Decode(PTGenotype pGeno) 
{  
    WORD numNodes = (WORD) m_Driver.GetNumNodes() ;
    int rowAlleleLen =  m_Driver.CalcRowAlleleLength() ;
    int colAlleleLen =  m_Driver.CalcColAlleleLength() ;
    int offset = 0 ;
    for (WORD node=0;node<numNodes;node++) {
        char rowAllele[16], colAllele[16] ;     
                           //we know that these are no bigger than sizeof(WORD)
        for(int bit=0;bit<rowAlleleLen;bit++)
            rowAllele[bit] = 
                                     pGeno->GetExpressedGeneValue(offset++,0) ;
        for(bit=0;bit<colAlleleLen;bit++)
            colAllele[bit] = 
                                     pGeno->GetExpressedGeneValue(offset++,0) ;
        int codedRow = AllelesToInt(rowAllele,0, rowAlleleLen-1) ;
        int codedCol = AllelesToInt(colAllele,0, colAlleleLen-1) ;
        int actualRow, actualCol ;
        GetNearestEmptyCell(codedRow,codedCol,actualRow,actualCol) ;
        m_pGrid->SetAt(actualRow, actualCol, node) ;
        m_GridIndex[0][node] = actualRow ;
        m_GridIndex[1][node] = actualCol ;
        }
}
PTPhenotype CGraphDrawingPheno::Copy()  
{
    CGraphDrawingPheno * pPheno = 
                            new CGraphDrawingPheno(m_Driver,m_Height,m_Width) ;
    return pPheno ; 
       //don't copy values because these are derived by the genotype via Decode
}
void CGraphDrawingPheno::GetPhenoInfo(void *pInfoStruct)  
{
    *((CWordMatrix **)pInfoStruct) = m_pGrid ;
}
//Algorithm resolves collisions by searching around the neighborhood of 
// (row,col) in the grid for an empty cell. The row and col of the empty cell 
// is returned in actualRow and actualCol.       
void CGraphDrawingPheno::GetNearestEmptyCell(const int row, const int col, 
                                                 int &actualRow,int &actualCol)
{
    //insure we are in range!
    actualRow = row % m_Height ; 
    actualCol = col % m_Width ; 
    //if we find and empty cell then no search necessary
    if (m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL)
        return ;
    else { //search for "nearest" empty cell
        int maxDist=Max(m_Height,m_Width) ;
        int actualRow2 = actualRow ; //save actuals
        int actualCol2 = actualCol ;
         //start at a distance of 1 and search outward
        for (int dist=1;dist<maxDist;dist++) { 
            //First check "sides"
            for(int i=-dist; i<=dist;i++) {
                for(int j=-dist;j<=dist;j++) {
                         if (i!=j && (j==dist || j==-dist || 
                                                        i==dist || i==-dist)) {
                        actualCol = actualCol2+j ;
                        actualRow = actualRow2+i ;
                        if(actualCol >= 0 && actualCol 
                                                                 < m_Width && 
                           actualRow >= 0 && actualRow
                                                                 < m_Height && 
                    m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL) 
                            return ;
                        } //if
                    } // for j             
                } //for i
                //Now check 4 corner cells
                actualCol = actualCol2+dist ;
                actualRow = actualRow2+dist ;
                if(actualCol < m_Width && 
                    actualRow < m_Height && 
                        m_pGrid->GetAt(actualRow,actualCol) ==
                                                                   EMPTY_CELL) 
                    return ;
                actualCol = actualCol2-dist ;
                actualRow = actualRow2+dist ;
                if(actualCol >= 0 && 
                    actualRow < m_Height && 
                    m_pGrid->GetAt(actualRow,actualCol) ==
                                                                    EMPTY_CELL)
                    return ;
                actualCol = actualCol2+dist ;
                actualRow = actualRow2-dist ;
                if(actualCol < m_Width && 
                    actualRow >= 0 && 
                    m_pGrid->GetAt(actualRow,actualCol) == 
                                                                    EMPTY_CELL)
                    return ;
                actualCol = actualCol2-dist ;
                actualRow = actualRow2-dist ;
                if(actualCol >= 0 && 
                    actualRow >= 0 && 
                    m_pGrid->GetAt(actualRow,actualCol) == 
                                                                    EMPTY_CELL)
                    return ;
            } //for dist
        } //else    
    return ;
}
//Return TRUE if node1 is adjacent to node2 on the grid
BOOL CGraphDrawingPheno::Adjacent(WORD node1, WORD node2) 
{            
    int row1, col1 ;
    if (!FindNode(node1,row1,col1))
        return FALSE ;
    int row2, col2 ;
    //look up
    row2=row1-1 ; 
    if (row2 >= 0 && m_pGrid->GetAt(row2,col1) == node2)
        return TRUE ; 
    //look down
    row2=row1+1 ; 
    if (row2 < m_Height && m_pGrid->GetAt(row2,col1) == node2)
        return TRUE ; 
    //look left 
    col2=col1-1 ; 
    if (col2 >= 0 && m_pGrid->GetAt(row1,col2) == node2)
        return TRUE ; 
    //look right
    col2=col1+1 ; 
    if (col2 < m_Width && m_pGrid->GetAt(row1,col2) == node2)
        return TRUE ; 
    return FALSE ;
}
//Return TRUE if node1 is diagonal to node2 on the grid
BOOL CGraphDrawingPheno::Diagonal(WORD node1, WORD node2) 
{
    int row1, col1 ;
    if (!FindNode(node1,row1,col1))
        return FALSE ;
    int row2, col2 ;
    //look upper left
    row2=row1-1 ; 
    col2=col1-1 ;
    if (row2 >= 0 && col2 >= 0 && m_pGrid->GetAt(row2,col2) == node2)
        return TRUE ; 
    //look lower left
    row2=row1+1 ; 
    col2=col1-1 ;
    if (row2 < m_Height && col2 >= 0 && m_pGrid->GetAt(row2,col1) == node2)
        return TRUE ; 
    //look lower right  
    row2=row1+1 ; 
    col2=col1+1 ; 
    if (row2 < m_Height && col2 < m_Width && m_pGrid->GetAt(row1,col2) == 
                                                                         node2)
        return TRUE ; 
    //look upper left
    row2=row1-1 ; 
    col2=col1+1 ; 
    if (row2 >= 0 && col2 < m_Width && m_pGrid->GetAt(row1,col2) == node2)
        return TRUE ; 
    return FALSE ;
}
//Return the Euclidean distance between nodes on the grid
double CGraphDrawingPheno::Distance(WORD node1, WORD node2) 
{
    int row1, col1, row2, col2 ;
    if (FindNode(node1,row1,col1) && FindNode(node2,row2,col2)) {
        double diffRow = row1 - row2 ;
        double diffCol = col1 - col2 ;
        return sqrt(diffRow*diffRow + diffCol*diffCol) ;
        }
    else
        return sqrt(m_Height*m_Height + m_Width*m_Width) ; 
}
//Return the recti-linear distance between nodes on the grid
double CGraphDrawingPheno::RectDistance(WORD node1, WORD node2) 
{
    int row1, col1, row2, col2 ;
    if (FindNode(node1,row1,col1) && FindNode(node2,row2,col2)) {
        double diffRow = row1 - row2 ;
        double diffCol = col1 - col2 ;
        return Abs(diffRow) + Abs(diffCol) ;
        }
    else
        return m_Height + m_Width ; //really an error ?!?
}
//Use an index to quickly locate a node on the grid
BOOL CGraphDrawingPheno::FindNode(const WORD node, int &row, int &col) 
{   
    if (node >= m_Driver.GetNumNodes())
        return FALSE ;
    row = m_GridIndex[0][node] ;
    col = m_GridIndex[1][node] ;
    return TRUE ;
}


Listing Three

//File: GDRIVER.H

#ifndef __GDRIVER_H__
#define __GDRIVER_H__
//flag an empty cell in the grid    
const EMPTY_CELL = 0xFFFF ;

class CGAGraphDriver
{           
    //Interface
public:
    CGAGraphDriver(int numNodes, int width, int height) ;
    ~CGAGraphDriver() ;
    void SetGraph(CWordMatrix &graph) ;
    void Optimize(int numGenrations) ;
    void DrawOptimized(CDC &dc) ;
    void DrawUnOptimized(CDC &dc) ;
    //Query members (const)
    //Calc the length of a chromosome
    //needed based on the graph and grid
    UINT CalcChromosomeLength() const ;                         
    UINT CalcRowAlleleLength() const ; ;
    UINT CalcColAlleleLength() const ; ;
    int GetWidth() const ;
    int GetHeight() const ;
    int GetNumNodes() const ;
    BOOL Connected(WORD node1, WORD node2)  const;  
    int GetNumConnections(WORD node) const ;
    int GetConnectivity() ; 
    void Stop() ;
    PTIndividual m_pBest ;
    PTIndividual m_pWorst ;
    BOOL m_Stop ;
    //Implementation
private:
    //Draw the graph in this grid
    void Draw(CDC &dc, CWordMatrix &Grid) ;
    //num nodes in the graph
    int m_NumGraphNodes ;                   
    //width of grid to draw on (in cells)
    int m_GridWidth ;           
    //height of grid to draw on (in cells)          
    int m_GridHeight ;           
    //connection table representation of a graph
    CWordMatrix *m_pGraph ;      
    //GA that will find the "optimal" drawing   
    //of the graph on the grid
    TBasicGA  *m_pTheGA ;         
} ;

Listing Four

//File: GDRIVER.CPP

//Used as an interface class to the GA.
//Stores the representation of the graph as
//a connection grid.
                            
//required headers                            
#include "stdafx.h"

//Headers needed for EOS programs
//You need EOS v1.1 to compile this code
#include "eos.h"   
#include "eosutil.h"   
#include "geno.h"
#include "individ.h"
#include "gaenviro.h"

//headers specific to graph GA
#include "wmatrix.h"
#include "gdriver.h"
#include "grphutil.h"
#include "graphga.h"

//GA parameters used, these need not be
//hard coded in advanced implementations
const int POP_SIZE = 20 ;
const double PX = 0.7 ;
const double PM = 0.03 ;
const double RAND_SEED=0.76451 ;

//DRAWING parameters used, these need not be
//hard coded in advanced implementations
const int CELL_WIDTH = 30 ;
const int CELL_HEIGHT = 30  ;
const int CELL_SPACE = 30 ;

//Driver constructor initializes a graph with  numNodes and a 
//grid that the graph will be optimized to draw on (width x height)
CGAGraphDriver::CGAGraphDriver(int numNodes, int width, int height) 
{           
    m_NumGraphNodes = numNodes;        
    m_GridWidth = width ;                       
    m_GridHeight = height ;
    //graph represented as boolean connection matrix
    m_pGraph = new CWordMatrix(m_NumGraphNodes,m_NumGraphNodes) ; 
    //The Graph GA object
    m_pTheGA = new CGraphDrawerGA(*this) ;
    m_pBest = NULL ;
    m_pWorst = NULL ;
    m_Stop = FALSE ;
}   
//Clean up in the destructor     
CGAGraphDriver::~CGAGraphDriver() 
{
    delete m_pGraph ;
    delete m_pTheGA ;
}
//set the conections from graph into the member m_pGraph
void CGAGraphDriver::SetGraph(CWordMatrix &graph) 
{
    for (int row = 0 ; row < m_NumGraphNodes; row++)
        for (int col = 0 ; col < m_NumGraphNodes; col++)
            m_pGraph->SetAt(row,col,graph[row][col]) ;  
}
// Optimize the drawing of the graph by first initializing the GA's population 
// and environment. Then execute the GA for numGenerations generations
void CGAGraphDriver::Optimize(int numGenerations) 
{
    m_pTheGA->CreatePopulation(POP_SIZE) ;
    m_pTheGA->CreateEnvironment(PX,PM,RAND_SEED) ;
    m_pTheGA->Evolve(numGenerations) ;
}
//Draw the optimized graph on the Windows DC
void CGAGraphDriver::DrawOptimized(CDC &dc) 
{
    CWordMatrix *pGrid ;
    m_pBest->GetPhenoInfo(&pGrid) ;
    Draw(dc,*pGrid) ;
}
//Draw the un-optimized graph on the Windows DC
void CGAGraphDriver::DrawUnOptimized(CDC &dc)
{
    CWordMatrix *pGrid ;
    m_pWorst->GetPhenoInfo(&pGrid) ;
    Draw(dc,*pGrid) ;
}
void CGAGraphDriver::Draw(CDC &dc, CWordMatrix &Grid)
{   
    CPen *pPen = (CPen *) dc.SelectStockObject(BLACK_PEN) ;
    for (int row = 0 ; row < m_GridHeight; row++)
        for (int col = 0 ; col < m_GridWidth; col++) {
           if (Grid[row][col] != EMPTY_CELL)  {
              int x1 = col * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
              int x2 = x1 + CELL_WIDTH    ;
              int y1 = row * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
              int y2 = y1 + CELL_HEIGHT   ;
              dc.Ellipse(x1,y1,x2,y2) ;                   
              char buffer[4] ;
              sprintf(buffer,"%d",Grid[row][col]) ;
              dc.TextOut(x1+CELL_WIDTH/4,y1+CELL_HEIGHT/4,buffer,
                                                              strlen(buffer)) ;
              }
           }       
    //draw arcs     
    for (int node1 = 0 ; node1 < m_NumGraphNodes; node1++)
        for (int node2 = 0 ; node2 < m_NumGraphNodes; node2++)
            if (m_pGraph->GetAt(node1,node2)) {
               int row1, col1 ;
               Grid.Find(node1, row1, col1) ;
               int row2, col2 ;
               Grid.Find(node2, row2, col2) ;
               int x1 = col1 * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
               int x2 = col2 * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
             int y1 = row1 * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
             int y2 = row2 * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
             if (x1 < x2)
             x1 += CELL_WIDTH ;
             else   
                if (x2 < x1)
                    x2 += CELL_WIDTH ;
                else    
                if (x1 == x2) {
                    if (Abs(row1 - row2) > 1) { //route around!
                        y1 += CELL_WIDTH/2 ;
                        y2 += CELL_WIDTH/2 ;
                        int x3 = x1 - CELL_WIDTH/2 ;
                        dc.MoveTo(x1,y1) ;
                        dc.LineTo(x3,y1) ;
                        dc.LineTo(x3,y2) ;  
                        dc.LineTo(x2,y2) ;
                        continue ;
                        }
                    x1 += CELL_WIDTH/2 ;
                    x2 += CELL_WIDTH/2 ;
                    }
                if (y1 < y2)
                    y1 += CELL_HEIGHT ;
                else    
                if (y2 < y1)
                    y2 += CELL_HEIGHT ;
                else
                if (y1 == y2) {          
                    if (Abs(col1 - col2) > 1) { //route around!
                        if (x1 < x2) {
                            x1 -= CELL_WIDTH/2 ;
                            x2 += CELL_WIDTH/2 ;
                            }
                        else {
                            x1 += CELL_WIDTH/2 ;
                            x2 -= CELL_WIDTH/2 ;
                            }
                        int y3 = y1 - CELL_HEIGHT/2 ;
                        dc.MoveTo(x1,y1) ;
                        dc.LineTo(x1,y3) ;
                        dc.LineTo(x2,y3) ;  
                        dc.LineTo(x2,y2) ;
                        continue ;
                        }
                    y1 += CELL_HEIGHT/2 ;
                    y2 += CELL_HEIGHT/2 ;
                    }
                            
                dc.MoveTo(x1,y1) ;
                dc.LineTo(x2,y2) ;
                }   
                
    dc.SelectObject(pPen ) ;
}
//Calculate the length of the chromosome needed to encode
//a drawing of the graph in a grid  
UINT CGAGraphDriver::CalcChromosomeLength() const                          
{
       return m_NumGraphNodes*(GetNumBitsToEncode(m_GridHeight) + 
                                              GetNumBitsToEncode(m_GridWidth));
}
UINT CGAGraphDriver::CalcRowAlleleLength() const  
{   
    return (UINT) GetNumBitsToEncode(m_GridWidth) ;
}

UINT CGAGraphDriver::CalcColAlleleLength() const  
{
    return (UINT) GetNumBitsToEncode(m_GridHeight) ;
}
//Return TRUE if node1 is connected to node2
BOOL CGAGraphDriver::Connected(WORD node1, WORD node2) const 
{
    return  m_pGraph->GetAt(node1,node2) ;
}
//Returns the  number of connection leaving node
int CGAGraphDriver::GetNumConnections(WORD node) const 
{                                    
    int count = 0 ;
    for (WORD i=0;i<m_NumGraphNodes;i++)
        if (i != node && m_pGraph->GetAt(node,i))
            count++ ;
    return count ;
}
//Returns the total number of connections in the graph
int CGAGraphDriver::GetConnectivity() 
{
    int count = 0 ;
    for (WORD node1=0;node1<m_NumGraphNodes;node1++)
        for (WORD node2=0;node2<m_NumGraphNodes;node2++)
            if (node1 != node2 && m_pGraph->GetAt(node1,node2))
                count ++ ;
    return count ;
}
void CGAGraphDriver::Stop() 
{
    m_Stop = TRUE ;
}

Listing Five

//File: GRAPHGA.H

#ifndef __GRAPHGA_H__
#define __GRAPHGA_H__

//Headers needed for EOS programs
//You need EOS v1.1 to compile this code
#ifndef __BASICGA_H
#include "basicga.h"
#endif

class CGraphDrawerGA : public TBasicGA
{
public:
    CGraphDrawerGA(CGAGraphDriver &driver) ;
    void CreatePopulation(long size, PTIndividual prototype = NULL) ;
    void ExitReport() ;

private:
    BOOL Stop() ;
    void InterGeneration(ulong, PTIndividual, PTIndividual, PTIndividual, PTIndividual) ;
    CGAGraphDriver & m_Driver ;
};
#endif


Listing Six

//File: GRAPHGA.CPP

#include "stdafx.h"

//Headers needed for EOS programs
//You need EOS v1.1 to compile this code
#include "eos.h"
#include "geno.h"
#include "basicga.h"
#include "nptxgeno.h"
#include "genrepop.h"
#include "gaenviro.h"

//headers specific to graph GA
#include "gdriver.h"
#include "graphga.h"
#include "graphind.h"
#include "grphphen.h"
#include "wmatrix.h"

CGraphDrawerGA::CGraphDrawerGA(CGAGraphDriver &driver) 
    : m_Driver(driver)
{
}
//Create the population of individuals
//We use 2 Point Crossover and Elitism
void CGraphDrawerGA::CreatePopulation(long size, PTIndividual prototype) 
{
    //Create a genotype with 1 chromosome and 2 point crossover 
    //The graph driver is queried to determine the chromosome length
    PTNPtCrossGenotype pGeno = 
                   new TNPtCrossGenotype(m_Driver.CalcChromosomeLength(),1,2) ;
    CGraphDrawingPheno * pPheno = 
        new CGraphDrawingPheno(m_Driver,m_Driver.GetWidth(),
                                m_Driver.GetHeight()) ;
    CGraphDrawingInd indiv(pGeno,pPheno);
    m_pPopulation = new TGenReplacePopulation(size,&indiv) ;
    m_pPopulation->SetElitism(2) ;
}
//When the GA is done set the best and worst individuals in the driver
void CGraphDrawerGA::ExitReport() 
{   
    m_Driver.m_pBest = m_pEnvironment->GlobalFittestIndivid ;
    m_Driver.m_pWorst = m_pEnvironment->GlobalWorstIndivid ;
}
//allow for windows processing!
void CGraphDrawerGA::InterGeneration(ulong, PTIndividual, PTIndividual, 
                                                   PTIndividual, PTIndividual) 
{
    MSG msg ;            
    //while there are msgs for status window
    while (PeekMessage(&msg,AfxGetApp()->m_pMainWnd->
                                                    m_hWnd,0,0,PM_REMOVE)) {
        TranslateMessage(&msg) ;
        DispatchMessage(&msg) ;
        }
    SetCursor(LoadCursor(NULL, IDC_WAIT));
}
//GA calls this function to determine if it should stop    
BOOL CGraphDrawerGA::Stop() 
{
    return m_Driver.m_Stop ;
}