Sal is president of Man Machine Interfaces. He can be reached at 555 Broad Hollow Road, Suite 230, Melville, NY 11747 or on CompuServe at 72053,2032.
Directed graphs underlie any tool that displays a tree diagram, class-relationship diagram, or entity-relationship diagram. As such, you might expect a CASE tool to provide an optimized directed-graph drawer. However, most CASE tools I'm familiar with punt when addressing this problem. Although an algorithm for drawing a directed graph like that shown in Figure 1 is straightforward, a general-purpose graph drawer that draws graphs in an aesthetically pleasing format is difficult to create and computationally expensive. So, CASE tools usually use a few simple rules to get an initial layout and then allow the user to clean things up by dragging objects around. Putting the burden of "pretty drawing" on the user wastes time better spent on the design.
This article looks at a novel solution to this problem using the emerging technology of genetic algorithms (GAs). Specifically, I'll use EOS, my company's C++ GA application framework, and Microsoft's Visual C++ to develop a module for optimizing the aesthetic layout of directed graphs. I'll create a Windows-hosted test application that exercises this module on randomly created graphs. The intent of this article is not to produce a commercial-grade graph drawer, but rather to demonstrate the use of GA technology on a nontrivial and unique problem. Since most programmers' first exposure to GAs is usually on a function-optimization problem, this article provides some insights on the advanced use of GA techniques.
A GA is an algorithm that works with a population of potential solutions to a problem. Through means analogous to biological natural selection, it evolves better and better solutions to the problem. To accomplish this, the user of a GA must first find a way to encode the problem into a string of bits. The bits are analogous to genes and the strings to chromosomes. The encoding of a solution as bit strings is often called the "genotype" and the decoded solution, the "phenotype." The genotype is mapped to the phenotype by the decoding function. The next step after the encoding is the measure of fitness. Fitness is one of the core elements that appear in every variation of a GA. Calculation of fitness involves mapping a solution onto a positive number such that greater numbers correspond to better solutions. This mapping is accomplished by the fitness or objective function.
The second core feature of every genetic algorithm is a population of individuals. At any time during the execution of a genetic algorithm, there exists a population of candidate solutions to the problem (individuals consisting of a genotype and a phenotype). The initial population is usually generated randomly. The process of transforming this initial, mediocre population into a population containing near-optimal solutions is the heart of the GA. It proceeds by iterations of the following genetic operators: selection, reproduction, crossover, and mutation.
Selection is the process by which candidate individuals from the current generation are chosen to produce the next generation. Selection is a survival-of-the-fittest strategy. After two individuals are selected, a weighted coin is flipped to determine if the individuals will mate to produce two new offspring or simply be placed in the next generation as is. Mating is accomplished by the crossover operation. The probability of mating is called the "crossover probability" (pc). The simplest form of crossover, called "single point," is shown in Figure 2. As each bit is copied from parent to child, it is subject to mutation based on the mutation probability (pm). Pm is usually very small, relative to pc. Iterations of selection, reproduction, and mating are repeated until a new population is created. At this point, the fitness values of the new population are recalculated, and the process repeats until either some acceptable solution is found or an upper time limit has been reached. The GA described above can be summarized by the procedure shown in Figure 3.
A GA framework is useful due to the large number of GA variants that can be produced by altering one or many of the steps in the basic algorithm. GA researchers have invented several variations on selection, reproduction, crossover, and mutation. Each variation can be mixed and matched to produce a unique GA variant. Object orientation turns out to be an ideal technique for expressing these variations. Through an adept combination of inheritance and composition, all the GA variants can be expressed. This ultimately allows you to code a GA using the basic technique and then try variations by instantiating different classes.
Although EOS consists of over 80 classes, I'll restrict this discussion to a small relevant subset--TBasicGA, TPopulation, TEnvironment, TBinaryIndividual, TGenotype, TPhenotype, TBinaryCrossoverFunctor, and TBinaryMutation- Functor. These bases consist of many derived classes that implement variants of the basic GA. Other classes exist to implement special-purpose features. Each of the classes listed encapsulates a different behavior of the overall GA. TBasicGA is the genetic-algorithm interface class. TPopulation is a collection class that holds instances of TIndividual. TPopulation encapsulates the selection operation. TEnvironment encapsulates the GA's parameters--pc, pm, the random-number generator, and other statistical information. TBinaryIndividual is an interface class that unifies instances of TGenotype and TPhenotype into a single object. TBinaryGenotype encapsulates the binary genetic coding of the problem as strings, and it provides an interface to the crossover and mutation classes. TPhenotype encapsulates the decoding function and the fitness function. It is the main class from which you derive to build a GA-based application. TBinaryCrossoverFunctor and TBinaryMutationFunctor are classes that encapsulate the operations of crossover and mutation. These classes are called functors because they are functional objects. Functors are used so various flavors of crossover and mutation can be plugged in or out of a genotype without recoding any of the genotype's methods. Figure 4 shows the relationship between these classes.
To derive a genetic encoding, I'll formalize the problem we are attempting to solve. We are given some arbitrary directed graph, as well as a grid where each cell represents a potential home for the graphical depiction of a node in the graph. The goal is to find an assignment of nodes to cells such that when the arcs are drawn, we get an aesthetically pleasing picture. Stating the problem in this way makes some crucial assumptions that may not be true in a real situation. First, I assume that the nodes, when drawn, are of equal size. Second, I assume that once I have assigned nodes to cells, the arcs can easily be drawn to complete the best possible drawing. (In other words, we need not optimize the drawing of arcs.) Third, I assume that the nodes are equally spaced in a grid and not arbitrarily placed on the output screen. I make these assumptions to simplify the example and the code. A more general solution is certainly possible using GAs.
If each node in the graph is assigned a sequential number, then the problem can be viewed as a mapping of each node number onto an (x, y) coordinate in the grid. The mapping that keeps connected nodes close together and produces the fewest arc crossings will yield more aesthetically pleasing drawings. Other domain-dependent criteria may come into play when determining better drawings, but I ignore this possibility to expedite the solution.
Given the above formalism, the encoding treats the bit string as a series of (x, y) pairs. The first pair assigns node0 to grid cell (x0, y0). The second assigns node1 to (x1, y1), and so on. This encoding allows collisions (two or more nodes are assigned to a single cell), so I need a collision-resolution procedure. A problem like this often arises in GAs, and there are several approaches to handling it. Some programmers assign very low fitness values to illegal genotypes. Others attempt to repair illegal genotypes before decoding them. Still others create special-purpose crossover and mutation operators that do not allow illegal genotypes to arise in the first place. In this case, I'll resolve a collision by searching for the closest empty cell to the one assigned, according to a fixed procedure. This is similar to a repair technique, but we are repairing the phenotype instead of the genotype.
Given that I have a graph with N nodes and a grid that is X cells wide and Y cells high, I can calculate the required length of the bit string using the equation in Figure 5. If X and Y are not powers of 2, then it is possible that (x, y) pairs can be encoded such that either x or y is greater then X or Y. I resolve this problem by always decoding x modulo X and y modulo Y. The decoding is implemented by a TPhenotype derived class called CGraphDrawingPheno. This class contains a two-dimensional matrix that will represent the grid. The genotype will be decoded so that each entry in the matrix will receive the node number of the node assigned to that grid position. Empty positions will be assigned a value of 0. The decoding of the genotype is implemented by CGraphDrawingPheno::Decode() member function; see Listings One and Two, page 106. This function uses a reference to a graph drive class to determine the number of bits in each component in the encoding. It copies these bits to buffers to be converted to integers by the utility functions AllelesToInt(). "Allele," a term borrowed from biology, refers to the value expressed by a gene. Once the node, its row, and column in the grid are decoded, the member function GetNearestEmptyCell() is called to resolve the possibility of a node already existing at the desired location.
Now that I have a way to encode the placement of a graph's nodes on a grid, I need a technique for evaluating each placement's fitness. There are many ways to do this, depending on what you consider to be an aesthetically pleasing layout. When deriving this fitness function, I let intuition guide me in the initial derivation and then experiment to tweak the function so it works well for a variety of graphs. The function I ultimately arrived at can be seen in the CGraphDrawingPheno class's CalcFitness() member function; see Listing Two. The idea behind this function is to reward genotypes that decode into drawings where nodes connected by an arc are adjacent or close and to penalize when nodes are adjacent but not connected. This is done on a node-by-node basis so the resulting fitness value is a measure of how well nodes of the entire graph were assigned to grid locations. Notice that I completely ignore arc drawing for simplicity. The remaining members of CGraphDrawingPheno implement construction, destruction and copying. I also include some private-utility functions that encapsulate the testing for adjacency and the calculation of distance between grid cells. These can be used in experimenting with variations of the fitness function.
I include three other classes in this module: CGAGraphDriver, CGraphDrawerGA, and CWordMatrix. CGAGraphDriver is an interface class that collects information (such as number of nodes in the graph and the size of the grid) before the GA and its associated objects are initialized; see Listings Three and Four (page 107). A very important function in this class is CalcChromosomeLength(), which, based on the number of nodes and the size of the grid, determines the number of bits necessary in a chromosome to encode the problem. Also included in this class are functions for drawing the optimized and unoptimized views of the graph. These use Windows-specific functions, but the logic can be easily ported to other graphics systems.
CGraphDrawerGA is derived from the EOS class TBasicGA. It overrides the population-creation function and several reporting functions useful for testing the GA's performance before it is embedded into a larger application. Listings Five and Six (page 147) show the class declaration and implementation of CGraphDrawerGA. The important function here is CreatePopulation(). This function determines the characteristics of the genotype, phenotype, and the population. I use a two-point crossover-operator genotype (instead of single point) because this tends to work better with longer chromosomes. I also use a population technique known as Elitism, which ensures that a certain number (in our case, two) of the best individuals from the previous generation make it to the next generation. This improves performance on some types of problems.
The utility class CWordMatrix implements a 2-D matrix of WORDS. Its implementation makes use of the MFC's CObArray and CWordArray to create
an array of CWordArrays.
To test the graph-optimizing GA, I created a simple Windows-hosted application using Visual C++. I used AppStudio, AppWizard, and ClassWizard to automate the creation of this program. The program uses two dialog boxes. The first dialog box allows me to specify the graph logically in terms of the number of nodes and their connections. The second allows me to specify the bounds of the grid and trigger the GA optimization of the graph on the grid. I also include options for displaying the optimized and unoptimized views of the graph. The optimized view is the best solution found by the GA; the unoptimized view is an arbitrary drawing of the graph from first node to the last. Due to the length of the test program, the complete listings for this project are available electronically; see "Availability," page 3.
Experiments that I have conducted using the GA-based graph-drawing module demonstrate that GAs present a viable solution to the problem. By improving the fitness function and by possible use of custom genetic operators, I believe that this technique will also work in commercial CASE tools.
Coplien, James O. Advanced C++: Programming Styles and Idioms. Reading, MA: Addison-Wesley, 1992.
Goldberg, David E. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.
Michalewicz, Zbigniew. Genetic Algorithms + Data Structures = Evolution Programs. New York, NY: Springer-Verlag, 1992.
Initialize a random population and measure its fitness.
WHILE (stopping criteria has not been reached)
BEGIN
WHILE (next generation is not full)
BEGIN
Select 2 parents randomly based on fitness.
IF (Flip(pc)) THEN
Cross parents (mutating with probability pm)
and place children in next generation.
ELSE
Place parents into next generation untouched.
END
END
Solution with highest fitness is the answer.
//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
};
//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 ;
}
//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 ;
} ;
//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 ;
}
//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
//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 ;
}
Copyright © 1994, Dr. Dobb's Journal