% Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
\noindent
\mbox{}\texttt{001:} \textit{/*\ File\ \ \ \ \ \ \ \ :\ ga.cpp} \\
\mbox{}\texttt{002:} \textit{\ *\ Authors\ \ \ \ \ :\ Rick\ van\ der\ Zwet\ \&\ Thomas\ Steenbergen} \\
\mbox{}\texttt{003:} \textit{\ *\ S-number\ \ \ \ :\ 0433373\ /\ 0117544\ } \\
\mbox{}\texttt{004:} \textit{\ *\ Version\ \ \ \ \ :\ \$Id:\ ga.cpp\ 610\ 2008-05-13\ 07:25:13Z\ rick\ \$} \\
\mbox{}\texttt{005:} \textit{\ *\ Licence\ \ \ \ \ :\ BSD} \\
\mbox{}\texttt{006:} \textit{\ *\ Description\ :\ 4th\ Assignment\ AI\ 2008:\ Genetic\ Algoithm} \\
\mbox{}\texttt{007:} \textit{\ */} \\
\mbox{}\texttt{008:}  \\
\mbox{}\texttt{009:} \textbf{\#include}\ \texttt{$<$iostream$>$} \\
\mbox{}\texttt{010:} \textbf{\#include}\ \texttt{$<$climits$>$} \\
\mbox{}\texttt{011:} \textbf{\#include}\ \texttt{$<$ctime$>$} \\
\mbox{}\texttt{012:} \textbf{\#include}\ \texttt{$<$cstdlib$>$} \\
\mbox{}\texttt{013:} \textbf{\#include}\ \texttt{$<$fstream$>$} \\
\mbox{}\texttt{014:} \textbf{\#include}\ \texttt{$<$math.h$>$} \\
\mbox{}\texttt{015:} \textbf{\#include}\ \texttt{$<$string$>$} \\
\mbox{}\texttt{016:} \textbf{\#include}\ \texttt{$<$sysexits.h$>$} \\
\mbox{}\texttt{017:}  \\
\mbox{}\texttt{018:} \textbf{using}\ \textbf{namespace}\ std; \\
\mbox{}\texttt{019:}  \\
\mbox{}\texttt{020:} \textit{/*NOTE:\ Graph\ can\ only\ have\ this\ many\ nodes\ */} \\
\mbox{}\texttt{021:} \textbf{\#define}\ MAX$\_$NODES\ 50 \\
\mbox{}\texttt{022:} \textbf{\#define}\ MAX$\_$ARCHS\ 250 \\
\mbox{}\texttt{023:}  \\
\mbox{}\texttt{024:} \textit{/*NOTE:\ Maximum\ numbers\ of\ newly\ generated\ children\ */} \\
\mbox{}\texttt{025:} \textbf{\#define}\ MAX$\_$POP\ 20 \\
\mbox{}\texttt{026:}  \\
\mbox{}\texttt{027:} \textit{/*NOTE:\ The\ chance\ to\ which\ we\ mutate\ a\ given\ point\ */} \\
\mbox{}\texttt{028:} \textbf{\#define}\ MUT$\_$LEV\ 50 \\
\mbox{}\texttt{029:}  \\
\mbox{}\texttt{030:} \textit{/*NOTE:\ The\ maximum\ number\ of\ generations\ that\ the\ algorithm\ runs\ */} \\
\mbox{}\texttt{031:} \textbf{\#define}\ DEFAULT$\_$LOOPS\ 100000 \\
\mbox{}\texttt{032:}  \\
\mbox{}\texttt{033:} \textbf{\#define}\ DEFAULT$\_$FILENAME\ \texttt{"{}input.txt"{}} \\
\mbox{}\texttt{034:} \textbf{\#define}\ MAX$\_$COORDINATES\ 1000 \\
\mbox{}\texttt{035:}  \\
\mbox{}\texttt{036:}  \\
\mbox{}\texttt{037:} \textbf{struct}\ arch\ \{ \\
\mbox{}\texttt{038:} \ \ \ \ int\ a,\ b; \\
\mbox{}\texttt{039:} \ \ \ \ double\ distance; \\
\mbox{}\texttt{040:}  \\
\mbox{}\texttt{041:} \ \ \ \ \textbf{arch}()\ \{ \\
\mbox{}\texttt{042:} \ \ \ \ a\ =\ -1; \\
\mbox{}\texttt{043:} \ \ \ \ b\ =\ -1; \\
\mbox{}\texttt{044:} \ \ \ \ distance\ =\ -1; \\
\mbox{}\texttt{045:} \ \ \ \ \} \\
\mbox{}\texttt{046:} \}; \\
\mbox{}\texttt{047:}  \\
\mbox{}\texttt{048:} \textit{/*\ Coordinate\ of\ point\ in\ graph\ */} \\
\mbox{}\texttt{049:} \textbf{struct}\ point\ \{ \\
\mbox{}\texttt{050:} \ \ \ \ int\ x,\ y;\ \ \ \ \ \ \ \textit{/*\ X,Y\ coordinates\ */} \\
\mbox{}\texttt{051:} \ \ \ \  \\
\mbox{}\texttt{052:} \ \ \ \ \textbf{point}()\{ \\
\mbox{}\texttt{053:} \ \ \ \ \ \ x\ =\ -1; \\
\mbox{}\texttt{054:} \ \ \ \ \ \ y\ =\ -1; \\
\mbox{}\texttt{055:} \ \ \ \ \} \\
\mbox{}\texttt{056:} \}; \\
\mbox{}\texttt{057:}  \\
\mbox{}\texttt{058:} \textit{/*\ Comparision\ between\ 2\ points\ */} \\
\mbox{}\texttt{059:} bool\ \textbf{operator}==(point\ \&a,\ point\ \&b)\ \{ \\
\mbox{}\texttt{060:} \ \ \ \ \textbf{if}\ (\ (a.x\ ==\ b.x)\ \&\&\ (a.y\ ==\ b.y)) \\
\mbox{}\texttt{061:} \ \ \ \ \ \ \ \ \textbf{return}\ \textbf{true}; \\
\mbox{}\texttt{062:} \ \ \ \ \textbf{else} \\
\mbox{}\texttt{063:} \ \ \ \ \ \ \ \ \textbf{return}\ \textbf{false}; \\
\mbox{}\texttt{064:} \} \\
\mbox{}\texttt{065:}  \\
\mbox{}\texttt{066:} \textbf{struct}\ graph\ \{ \\
\mbox{}\texttt{067:} \ \ \ \ point\ nodes[MAX$\_$NODES];\ \ \ \textit{/*\ Location\ of\ nodes\ */} \\
\mbox{}\texttt{068:} \ \ \ \ int\ fitness;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Overall\ fitness\ graph\ */} \\
\mbox{}\texttt{069:} \ \ \ \ int\ fitnessDistance; \\
\mbox{}\texttt{070:} \ \ \ \ int\ fitnessIntersection; \\
\mbox{}\texttt{071:} \ \ \ \  \\
\mbox{}\texttt{072:} \ \ \ \ \textbf{graph}()\ \{ \\
\mbox{}\texttt{073:} \ \ \ \ \ \ fitness\ =\ -1; \\
\mbox{}\texttt{074:} \ \ \ \ \ \ fitnessDistance\ =\ -1; \\
\mbox{}\texttt{075:} \ \ \ \ \ \ fitnessIntersection\ =\ -1; \\
\mbox{}\texttt{076:} \ \ \ \ \} \\
\mbox{}\texttt{077:} \}; \\
\mbox{}\texttt{078:}  \\
\mbox{}\texttt{079:} \textit{/*} \\
\mbox{}\texttt{080:} \textit{\ *\ BEGIN\ Global\ variables\ } \\
\mbox{}\texttt{081:} \textit{\ */} \\
\mbox{}\texttt{082:}  \\
\mbox{}\texttt{083:} arch\ archs[MAX$\_$ARCHS];\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ arch\ listing\ in\ graph\ */} \\
\mbox{}\texttt{084:} int\ num$\_$archs\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Number\ of\ archs\ in\ graph\ */} \\
\mbox{}\texttt{085:} int\ num$\_$nodes\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Number\ of\ nodes\ in\ graph\ */} \\
\mbox{}\texttt{086:} int\ max$\_$cord\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Domain\ e.g.\ maximum\ coord\ of\ X,\ Y*/} \\
\mbox{}\texttt{087:} int\ lon$\_$con\ =\ -1;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Longest\ connection\ of\ two\ points\ */} \\
\mbox{}\texttt{088:} int\ distances\ [MAX$\_$NODES][MAX$\_$NODES];\ \textit{/*\ Distances\ between\ node\ i\ and\ j\ */} \\
\mbox{}\texttt{089:} graph\ population[MAX$\_$POP];\ \ \ \ \ \ \ \ \ \ \ \ \textit{/*\ Graph\ list\ */} \\
\mbox{}\texttt{090:}  \\
\mbox{}\texttt{091:} \textit{/*} \\
\mbox{}\texttt{092:} \textit{\ *\ END\ Global\ variables} \\
\mbox{}\texttt{093:} \textit{\ */} \\
\mbox{}\texttt{094:}  \\
\mbox{}\texttt{095:}  \\
\mbox{}\texttt{096:}  \\
\mbox{}\texttt{097:} \textit{/*\ Calculates\ the\ distance\ between\ two\ points} \\
\mbox{}\texttt{098:} \textit{\ *\ Distance\ (A,B)\ =\ d((x1,y1),(x2,y2))=SQRT((x1-x2)\textasciicircum{}2+(y1-y2)\textasciicircum{}2)} \\
\mbox{}\texttt{099:} \textit{\ */} \\
\mbox{}\texttt{100:} double\ \textbf{calcDistance}(point\ A,\ point\ B)\ \{ \\
\mbox{}\texttt{101:} \ \ double\ dist\ =\ 0; \\
\mbox{}\texttt{102:} \ \ dist\ =\ \textbf{sqrt}(\textbf{pow}((A.x\ -\ B.x),2)\ +\ \textbf{pow}((A.y\ -\ B.y),2)); \\
\mbox{}\texttt{103:} \ \ \textbf{return}\ dist; \\
\mbox{}\texttt{104:} \} \\
\mbox{}\texttt{105:}  \\
\mbox{}\texttt{106:} \textit{/*\ How\ well\ is\ the\ scaling\ of\ the\ branches\ ofthis\ graph\ weel\ } \\
\mbox{}\texttt{107:} \textit{\ *\ versus\ the\ input\ graph.\ The\ more\ it\ deviates\ of\ the\ orginal\ the\ higher} \\
\mbox{}\texttt{108:} \textit{\ *\ the\ fitness\ number.} \\
\mbox{}\texttt{109:} \textit{\ */} \\
\mbox{}\texttt{110:} int\ \textbf{fitnessDistance}(graph\&\ A)\ \{ \\
\mbox{}\texttt{111:} \ \ int\ i,j; \\
\mbox{}\texttt{112:} \ \ int\ org$\_$dist\ =\ 0;\ \ \textit{//\ distance\ between\ 2\ points\ in\ input\ graph} \\
\mbox{}\texttt{113:} \ \ double\ new$\_$dist\ =\ 0;\ \ \textit{//\ distance\ between\ 2\ points\ in\ population\ graph} \\
\mbox{}\texttt{114:} \ \ double\ diff$\_$dist\ =\ 0;\ \textit{//\ absolute\ difference} \\
\mbox{}\texttt{115:} \ \ int\ tmp$\_$fitness\ =\ 0; \\
\mbox{}\texttt{116:}  \\
\mbox{}\texttt{117:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
\mbox{}\texttt{118:} \ \ \ \ \textbf{for}\ (j=i+1;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
\mbox{}\texttt{119:} \ \ \ \ \ \ org$\_$dist\ =\ distances[i][j]; \\
\mbox{}\texttt{120:} \ \ \ \ \ \ \textbf{if}\ (org$\_$dist\ !=\ 0)\{ \\
\mbox{}\texttt{121:} \ \ \ \ \ \ \ \ new$\_$dist\ =\ \textbf{calcDistance}(A.nodes[i],A.nodes[j]); \\
\mbox{}\texttt{122:} \ \ \ \ \ \ \ \ diff$\_$dist\ =\ \textbf{fabs}(new$\_$dist\ -\ org$\_$dist); \\
\mbox{}\texttt{123:} \ \ \ \ \ \ \ \ tmp$\_$fitness\ +=\ diff$\_$dist; \\
\mbox{}\texttt{124:} \ \ \ \ \ \ \} \\
\mbox{}\texttt{125:} \ \ \ \ \} \\
\mbox{}\texttt{126:} \ \ \} \\
\mbox{}\texttt{127:}  \\
\mbox{}\texttt{128:} \ \ \textbf{return}(tmp$\_$fitness); \\
\mbox{}\texttt{129:} \} \\
\mbox{}\texttt{130:}  \\
\mbox{}\texttt{131:} \textit{/*\ Output\ point\ itself\ */} \\
\mbox{}\texttt{132:} void\ \textbf{printPoint}(point\ \&A)\ \{ \\
\mbox{}\texttt{133:} \ \ \ \ cerr\ $<$$<$\ \ A.x\ $<$$<$\ \texttt{"{},"{}}\ $<$$<$\ A.y; \\
\mbox{}\texttt{134:} \} \\
\mbox{}\texttt{135:}  \\
\mbox{}\texttt{136:} \textit{/*\ Calculates\ whether\ the\ line\ A-B\ crosses\ with\ line\ C-D\ and\ wether\ in} \\
\mbox{}\texttt{137:} \textit{\ *\ domain\ if\ so\ a\ it\ returns\ the\ point\ of\ intersection\ else\ return\ point} \\
\mbox{}\texttt{138:} \textit{\ *\ [-1,-1]\ All\ explained\ in:} \\
\mbox{}\texttt{139:} \textit{\ *\ }\underline{\texttt{http://www.topcoder.com/tc}}\textit{?module=Static\&d1=tutorials\&d2=geometry2} \\
\mbox{}\texttt{140:} \textit{\ *\ }\underline{\texttt{http://en.wikipedia.org/wiki/Line-line$\_$intersection}} \\
\mbox{}\texttt{141:} \textit{\ */} \\
\mbox{}\texttt{142:} bool\ \textbf{calcIntersection}(point\ A,\ point\ B,\ point\ C,\ point\ D,\ point\&\ tmp)\ \{ \\
\mbox{}\texttt{143:} \ \ double\ K,\ L,\ M; \\
\mbox{}\texttt{144:} \ \ double\ S,\ T,\ R; \\
\mbox{}\texttt{145:} \ \ double\ det; \\
\mbox{}\texttt{146:} \ \ bool\ result; \\
\mbox{}\texttt{147:} \ \ double\ distance$\_$a$\_$b; \\
\mbox{}\texttt{148:}  \\
\mbox{}\texttt{149:} \ \ \textit{//\ rewrite\ line\ A-B\ into\ formula\ form:\ Kx\ +\ Ly\ =\ M} \\
\mbox{}\texttt{150:} \ \ K\ =\ B.y\ -\ A.y; \\
\mbox{}\texttt{151:} \ \ L\ =\ A.x\ -\ B.x; \\
\mbox{}\texttt{152:} \ \ M\ =\ K\ *\ A.x\ +\ L\ *\ A.y; \\
\mbox{}\texttt{153:} \ \  \\
\mbox{}\texttt{154:} \ \ \textit{//\ rewrite\ line\ C-D\ into\ formula\ form:\ Sx\ +\ Ty\ =\ R} \\
\mbox{}\texttt{155:} \ \ S\ =\ D.y\ -\ C.y; \\
\mbox{}\texttt{156:} \ \ T\ =\ C.x\ -\ D.x; \\
\mbox{}\texttt{157:} \ \ R\ =\ S\ *\ C.x\ +\ T\ *\ C.y; \\
\mbox{}\texttt{158:}  \\
\mbox{}\texttt{159:} \ \ \textit{//\ Now\ we\ calculate\ the\ intersection\ between\ the\ lines} \\
\mbox{}\texttt{160:} \ \ det\ =\ K*T\ -\ S*L; \\
\mbox{}\texttt{161:}  \\
\mbox{}\texttt{162:} \ \ \textbf{if}(det\ ==\ 0)\{ \\
\mbox{}\texttt{163:} \ \ \ \ \textit{/*\ Lines\ A-B\ \&\ C-D\ are\ parallel,\ checking\ wether\ they\ are\ on\ top\ of} \\
\mbox{}\texttt{164:} \textit{\ \ \ \ \ *\ each\ other} \\
\mbox{}\texttt{165:} \textit{\ \ \ \ \ */} \\
\mbox{}\texttt{166:} \ \ \ \ tmp.x\ =\ -1; \\
\mbox{}\texttt{167:} \ \ \ \ tmp.y\ =\ -1; \\
\mbox{}\texttt{168:} \ \ \ \ result\ =\ \textbf{false}; \\
\mbox{}\texttt{169:}  \\
\mbox{}\texttt{170:} \ \ \ \ distance$\_$a$\_$b\ =\ \textbf{calcDistance}(A,B); \\
\mbox{}\texttt{171:} \ \ \ \ \textbf{if}\ ((\textbf{calcDistance}(A,C)\ +\ \textbf{calcDistance}(B,C)\ ==\ distance$\_$a$\_$b))\ \{ \\
\mbox{}\texttt{172:} \ \ \ \ \ \ tmp.x\ =\ C.x; \\
\mbox{}\texttt{173:} \ \ \ \ \ \ tmp.y\ =\ C.y; \\
\mbox{}\texttt{174:} \ \ \ \ \ \ result\ =\ \textbf{false}; \\
\mbox{}\texttt{175:} \ \ \ \ \}\ \textbf{else}\ \textbf{if}\ ((\textbf{calcDistance}(A,D)\ +\ \textbf{calcDistance}(B,D)\ ==\ distance$\_$a$\_$b))\ \{ \\
\mbox{}\texttt{176:} \ \ \ \ \ \ tmp.x\ =\ D.x; \\
\mbox{}\texttt{177:} \ \ \ \ \ \ tmp.y\ =\ D.y; \\
\mbox{}\texttt{178:} \ \ \ \ \ \ result\ =\ \textbf{false}; \\
\mbox{}\texttt{179:} \ \ \ \ \} \\
\mbox{}\texttt{180:}  \\
\mbox{}\texttt{181:} \ \ \}\ \textbf{else}\ \{ \\
\mbox{}\texttt{182:} \ \ \ \ tmp.x\ =\ (T*M\ -\ L*R)/det; \\
\mbox{}\texttt{183:} \ \ \ \ tmp.y\ =\ (K*R\ -\ S*M)/det; \\
\mbox{}\texttt{184:} \ \ \ \ result\ =\ \textbf{true}; \\
\mbox{}\texttt{185:}  \\
\mbox{}\texttt{186:} \ \ \ \ \textit{/*\ Verify\ intersection\ in\ domain\ */} \\
\mbox{}\texttt{187:} \ \ \ \ \textbf{if}\ (tmp.x\ $<$\ 0\ $|$$|$\ tmp.x\ $>$=\ max$\_$cord\ $|$$|$\ tmp.y\ $<$\ 0\ $|$$|$\ tmp.y\ $>$=\ max$\_$cord)\ \{ \\
\mbox{}\texttt{188:} \ \ \ \ \ \ \ \ result\ =\ \textbf{false}; \\
\mbox{}\texttt{189:} \ \ \ \ \} \\
\mbox{}\texttt{190:}  \\
\mbox{}\texttt{191:} \ \ \ \ \textit{/*\ Verify\ intersection\ not\ a\ actual\ end\ point\ */} \\
\mbox{}\texttt{192:} \ \ \ \ \textbf{if}\ ((tmp\ ==\ A\ $|$$|$\ tmp\ ==\ B)\ \&\&\ (tmp\ ==\ C\ $|$$|$\ tmp\ ==\ D))\ \{ \\
\mbox{}\texttt{193:} \ \ \ \ \ \ \ \ result\ =\ \textbf{false}; \\
\mbox{}\texttt{194:} \ \ \ \ \} \\
\mbox{}\texttt{195:} \ \ \} \\
\mbox{}\texttt{196:}  \\
\mbox{}\texttt{197:} \ \ \textbf{return}\ result; \\
\mbox{}\texttt{198:} \} \\
\mbox{}\texttt{199:}  \\
\mbox{}\texttt{200:} bool\ \textbf{calcIntersection}(point\ A,\ point\ B,\ point\ C,\ point\ D)\ \{ \\
\mbox{}\texttt{201:} \ \ \ \ point\ tmp; \\
\mbox{}\texttt{202:} \ \ \ \ \textbf{return}\ \textbf{calcIntersection}(A,\ B,\ C,\ D,\ tmp); \\
\mbox{}\texttt{203:} \} \\
\mbox{}\texttt{204:}  \\
\mbox{}\texttt{205:} \textit{/*} \\
\mbox{}\texttt{206:} \textit{\ *\ The\ number\ of\ intersections\ a\ graph.\ How\ more\ intersections\ the\ higher} \\
\mbox{}\texttt{207:} \textit{\ *\ the\ fitness\ number.} \\
\mbox{}\texttt{208:} \textit{\ */} \\
\mbox{}\texttt{209:} int\ \textbf{fitnessIntersection}(graph\&\ A)\ \{ \\
\mbox{}\texttt{210:} \ \ int\ i,j; \\
\mbox{}\texttt{211:} \ \ int\ tmp$\_$fitness\ =\ 0; \\
\mbox{}\texttt{212:}  \\
\mbox{}\texttt{213:} \ \ \textbf{for}\ (i\ =\ 0;\ i\ $<$\ num$\_$archs;\ i++)\ \{ \\
\mbox{}\texttt{214:} \ \ \ \ \textbf{for}\ (j\ =\ i\ +\ 1;\ j\ $<$\ num$\_$archs;\ j++)\ \{ \\
\mbox{}\texttt{215:} \ \ \ \ \ \ \textbf{if}\ (\ \textbf{calcIntersection}(A.nodes[archs[i].a], \\
\mbox{}\texttt{216:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.nodes[archs[i].b], \\
\mbox{}\texttt{217:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.nodes[archs[j].a], \\
\mbox{}\texttt{218:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A.nodes[archs[j].b]))\ \{ \\
\mbox{}\texttt{219:} \ \ \ \ \ \ \ \ \ tmp$\_$fitness++; \\
\mbox{}\texttt{220:} \ \ \ \ \ \ \} \\
\mbox{}\texttt{221:} \ \ \ \ \} \\
\mbox{}\texttt{222:} \ \ \} \\
\mbox{}\texttt{223:} \ \ \textbf{return}(tmp$\_$fitness); \\
\mbox{}\texttt{224:} \} \\
\mbox{}\texttt{225:}  \\
\mbox{}\texttt{226:}  \\
\mbox{}\texttt{227:} \textit{/*\ Calculates\ the\ fitness\ of\ every\ graph\ in\ the\ population\ */} \\
\mbox{}\texttt{228:} void\ \textbf{calcFitness}(graph\&\ A)\ \{ \\
\mbox{}\texttt{229:} \ \ \ \ A.fitnessIntersection\ =\ \textbf{fitnessIntersection}(A); \\
\mbox{}\texttt{230:} \ \ \ \ A.fitnessDistance\ =\ \textbf{fitnessDistance}(A); \\
\mbox{}\texttt{231:} \ \ \ \ A.fitness\ =\ A.fitnessDistance\ +\ A.fitnessIntersection; \\
\mbox{}\texttt{232:} \} \\
\mbox{}\texttt{233:}  \\
\mbox{}\texttt{234:} void\ \textbf{crossover}(graph\&\ A,\ graph\&\ B)\{ \\
\mbox{}\texttt{235:} \ \ \ \ \textit{/*\ XXX:\ Find\ clever\ way\ to\ combine\ the\ different\ graphs\ to\ be\ able} \\
\mbox{}\texttt{236:} \textit{\ \ \ \ \ *\ to\ make\ new\ ones.\ Three\ to\ expiriment\ with:} \\
\mbox{}\texttt{237:} \textit{\ \ \ \ \ *\ -\ uniform\ crossover} \\
\mbox{}\texttt{238:} \textit{\ \ \ \ \ *\ -\ single-point\ crossover} \\
\mbox{}\texttt{239:} \textit{\ \ \ \ \ *\ -\ partially\ mapped\ crossover} \\
\mbox{}\texttt{240:} \textit{\ \ \ \ \ *\ All\ explained\ in:\ }\underline{\texttt{http://www.liacs.nl/}}\textit{\textasciitilde{}kosters/AI/genetisch.pdf} \\
\mbox{}\texttt{241:} \textit{\ \ \ \ \ */} \\
\mbox{}\texttt{242:}  \\
\mbox{}\texttt{243:} \} \\
\mbox{}\texttt{244:}  \\
\mbox{}\texttt{245:} \textit{//\ Combine\ two\ graphs\ using\ single\ point\ crossover} \\
\mbox{}\texttt{246:} \textit{//\ A\ single\ random\ point\ is\ chosen\ in\ a\ graph's\ node} \\
\mbox{}\texttt{247:} \textit{//\ array\ dividing\ it\ into\ two\ halves\ e.g.\ the\ head\ and\ the\ tail.} \\
\mbox{}\texttt{248:} \textit{//\ Then\ heads\ are\ swapped\ between\ parents\ A\ \&\ B} \\
\mbox{}\texttt{249:} void\ \textbf{crossSingle}(graph\&\ A,\ graph\&\ B)\{ \\
\mbox{}\texttt{250:} \ \ \ point\ tmp; \\
\mbox{}\texttt{251:} \ \ \ unsigned\ int\ cut; \\
\mbox{}\texttt{252:} \ \ \ unsigned\ int\ i; \\
\mbox{}\texttt{253:}  \\
\mbox{}\texttt{254:} \ \ \ cut\ =\ \textbf{rand}()\ \%\ num$\_$nodes; \\
\mbox{}\texttt{255:} \ \ \ \textbf{for}\ (i=0;\ i$<$\ cut;i++)\ \{ \\
\mbox{}\texttt{256:} \ \ \ \ \ \ \ tmp\ =\ A.nodes[i]; \\
\mbox{}\texttt{257:} \ \ \ \ \ \ \ A.nodes[i]\ =\ B.nodes[i]; \\
\mbox{}\texttt{258:} \ \ \ \ \ \ \ B.nodes[i]\ =\ tmp; \\
\mbox{}\texttt{259:} \ \ \ \} \\
\mbox{}\texttt{260:} \} \\
\mbox{}\texttt{261:}  \\
\mbox{}\texttt{262:} \textit{//\ Combine\ two\ graphs\ using\ uniform\ crossover} \\
\mbox{}\texttt{263:} \textit{//\ The\ points\ are\ swapped\ with\ a\ fixed\ probability\ of\ 0.5.} \\
\mbox{}\texttt{264:} void\ \textbf{crossUniform}(graph\&\ A,\ graph\&\ B)\{ \\
\mbox{}\texttt{265:} \ \ \ point\ tmp; \\
\mbox{}\texttt{266:} \ \ \ int\ i,\ rnd; \\
\mbox{}\texttt{267:}  \\
\mbox{}\texttt{268:} \ \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;i++)\ \{ \\
\mbox{}\texttt{269:} \ \ \ \ \ rnd\ =\ \textbf{rand}()\%\ 2; \\
\mbox{}\texttt{270:} \ \ \ \ \ \textbf{if}\ (rnd\ ==\ 1)\{ \\
\mbox{}\texttt{271:} \ \ \ \ \ \ \ tmp.x\ =\ A.nodes[i].x; \\
\mbox{}\texttt{272:} \ \ \ \ \ \ \ A.nodes[i].x\ =\ B.nodes[i].x; \\
\mbox{}\texttt{273:} \ \ \ \ \ \ \ B.nodes[i].x\ =\ tmp.x; \\
\mbox{}\texttt{274:} \ \ \ \ \ \} \\
\mbox{}\texttt{275:} \ \ \ \ \ rnd\ =\ \textbf{rand}()\%\ 2; \\
\mbox{}\texttt{276:} \ \ \ \ \ \textbf{if}\ (rnd\ ==\ 1)\{ \\
\mbox{}\texttt{277:} \ \ \ \ \ \ \ tmp.y\ =\ A.nodes[i].y; \\
\mbox{}\texttt{278:} \ \ \ \ \ \ \ A.nodes[i].y\ =\ B.nodes[i].y; \\
\mbox{}\texttt{279:} \ \ \ \ \ \ \ B.nodes[i].y\ =\ tmp.y; \\
\mbox{}\texttt{280:} \ \ \ \ \ \} \\
\mbox{}\texttt{281:} \ \ \ \} \\
\mbox{}\texttt{282:} \} \\
\mbox{}\texttt{283:}  \\
\mbox{}\texttt{284:}  \\
\mbox{}\texttt{285:} \textit{//\ Copies\ the\ contents\ of\ graph\ A\ to\ graph\ B} \\
\mbox{}\texttt{286:} void\ \textbf{copyGraph}(graph\ \&\ A,\ graph\&\ B)\{ \\
\mbox{}\texttt{287:} \ \ int\ i; \\
\mbox{}\texttt{288:}  \\
\mbox{}\texttt{289:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;i++)\ \{ \\
\mbox{}\texttt{290:} \ \ \ \ B.nodes[i]\ =\ A.nodes[i]; \\
\mbox{}\texttt{291:} \ \ \} \\
\mbox{}\texttt{292:} \ \ B.fitness\ =\ A.fitness; \\
\mbox{}\texttt{293:} \ \ B.fitnessIntersection\ =\ A.fitnessIntersection; \\
\mbox{}\texttt{294:} \ \ B.fitnessDistance\ =\ A.fitnessDistance; \\
\mbox{}\texttt{295:} \} \\
\mbox{}\texttt{296:}  \\
\mbox{}\texttt{297:} \textit{/*\ Mutate\ random\ point\ in\ a\ graph\ and\ change\ it\ to\ random\ value} \\
\mbox{}\texttt{298:} \textit{\ *\ within\ the\ domain\ of\ points} \\
\mbox{}\texttt{299:} \textit{\ */} \\
\mbox{}\texttt{300:} void\ \textbf{mutateGraph\ }(int\ mutationLevel,\ graph\&\ A)\{ \\
\mbox{}\texttt{301:} \ \ int\ i,x,y; \\
\mbox{}\texttt{302:}  \\
\mbox{}\texttt{303:} \ \ \textbf{if}\ ((\textbf{rand}()\ \%\ 100)\ $>$\ mutationLevel)\ \{ \\
\mbox{}\texttt{304:} \ \ \ \ \textbf{return}; \\
\mbox{}\texttt{305:} \ \ \} \\
\mbox{}\texttt{306:}  \\
\mbox{}\texttt{307:} \ \ i\ =\ \textbf{rand}()\ \%\ num$\_$nodes; \\
\mbox{}\texttt{308:} \ \ x\ =\ (\textbf{rand}()\%\ max$\_$cord)+1; \\
\mbox{}\texttt{309:} \ \ y\ =\ (\textbf{rand}()\%\ max$\_$cord)+1; \\
\mbox{}\texttt{310:}  \\
\mbox{}\texttt{311:} \ \ A.nodes[i].x\ =\ x; \\
\mbox{}\texttt{312:} \ \ A.nodes[i].y\ =\ y; \\
\mbox{}\texttt{313:} \} \\
\mbox{}\texttt{314:}  \\
\mbox{}\texttt{315:} \textit{/*\ To\ do\ selection\ we\ use\ roulettewheel\ selection,\ only\ we\ } \\
\mbox{}\texttt{316:} \textit{\ *\ invert\ adjust\ the\ regular\ algorithm\ so\ it\ prefers} \\
\mbox{}\texttt{317:} \textit{\ *\ the\ lowest\ fitness\ numbers\ e.g.\ the\ biggest\ slice\ of} \\
\mbox{}\texttt{318:} \textit{\ *\ piece\ is\ now\ the\ least\ attractive.} \\
\mbox{}\texttt{319:} \textit{\ */} \\
\mbox{}\texttt{320:} int\ \textbf{selectGraph}()\ \{ \\
\mbox{}\texttt{321:} \ \ int\ i; \\
\mbox{}\texttt{322:} \ \ int\ choice\ =\ -1; \\
\mbox{}\texttt{323:} \ \ int\ combined$\_$fitness; \\
\mbox{}\texttt{324:} \ \ int\ fitness$\_$reverse[MAX$\_$POP]; \\
\mbox{}\texttt{325:} \ \ int\ max$\_$fitness\ =\ INT$\_$MIN; \\
\mbox{}\texttt{326:} \ \ int\ min$\_$fitness\ =\ INT$\_$MAX; \\
\mbox{}\texttt{327:} \ \ int\ total$\_$fitness\ =\ 0; \\
\mbox{}\texttt{328:} \ \ int\ wheelnumber; \\
\mbox{}\texttt{329:}  \\
\mbox{}\texttt{330:} \ \ \textit{/*\ Find\ minimum/maximum\ */} \\
\mbox{}\texttt{331:} \ \ min$\_$fitness\ =\ population[0].fitness; \\
\mbox{}\texttt{332:} \ \ max$\_$fitness\ =\ population[MAX$\_$POP\ -\ 1].fitness; \\
\mbox{}\texttt{333:}  \\
\mbox{}\texttt{334:} \ \ \textit{/*\ Set\ balanced\ fitness\ */} \\
\mbox{}\texttt{335:} \ \ combined$\_$fitness\ =\ min$\_$fitness\ +\ max$\_$fitness; \\
\mbox{}\texttt{336:} \ \ \textbf{for}(i=0;\ i$<$\ MAX$\_$POP;\ i++)\ \{ \\
\mbox{}\texttt{337:} \ \ \ \ fitness$\_$reverse[i]\ =\ combined$\_$fitness\ -\ population[i].fitness; \\
\mbox{}\texttt{338:} \ \ \ \ total$\_$fitness\ +=\ fitness$\_$reverse[i]; \\
\mbox{}\texttt{339:} \ \ \} \\
\mbox{}\texttt{340:}  \\
\mbox{}\texttt{341:} \ \textit{/*\ Get\ random\ number\ of\ wheel\ */} \\
\mbox{}\texttt{342:} \ \ wheelnumber\ =\ \textbf{rand}()\ \%\ total$\_$fitness; \\
\mbox{}\texttt{343:}  \\
\mbox{}\texttt{344:} \ \ \textit{/*\ Find\ matching\ graph\ */} \\
\mbox{}\texttt{345:} \ \ total$\_$fitness\ =\ 0; \\
\mbox{}\texttt{346:} \ \ \textbf{for}(i=0;\ i$<$\ MAX$\_$POP;\ i++)\ \{ \\
\mbox{}\texttt{347:} \ \ \ \ total$\_$fitness\ +=\ fitness$\_$reverse[i]; \\
\mbox{}\texttt{348:} \ \ \ \ \textbf{if}\ (total$\_$fitness\ $>$\ wheelnumber)\ \{ \\
\mbox{}\texttt{349:} \ \ \ \ \ \ \ \ choice\ =\ i; \\
\mbox{}\texttt{350:} \ \ \ \ \ \ \ \ \textbf{break}; \\
\mbox{}\texttt{351:} \ \ \ \ \} \\
\mbox{}\texttt{352:} \ \ \} \\
\mbox{}\texttt{353:}  \\
\mbox{}\texttt{354:} \ \ \textbf{return}\ (choice); \\
\mbox{}\texttt{355:} \} \\
\mbox{}\texttt{356:}  \\
\mbox{}\texttt{357:} \textit{/*\ Set\ the\ values\ of\ a\ \ given\ graph\ to\ random\ numbers} \\
\mbox{}\texttt{358:} \textit{\ *\ In\ other\ word\ those\ graphs\ who\ aint\ fit\ enough\ } \\
\mbox{}\texttt{359:} \textit{\ *\ for\ the\ next\ round\ will\ be\ discarded.\ } \\
\mbox{}\texttt{360:} \textit{\ */} \\
\mbox{}\texttt{361:} void\ \textbf{setRandGraph}(graph\&\ A)\ \{ \\
\mbox{}\texttt{362:} \ \ int\ i; \\
\mbox{}\texttt{363:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;i++)\ \{ \\
\mbox{}\texttt{364:} \ \ \ \ \ A.nodes[i].x\ =\ (\textbf{rand}()\%max$\_$cord)+1; \\
\mbox{}\texttt{365:} \ \ \ \ \ A.nodes[i].y\ =\ (\textbf{rand}()\%max$\_$cord)+1; \\
\mbox{}\texttt{366:} \ \ \ \} \\
\mbox{}\texttt{367:} \ \  \\
\mbox{}\texttt{368:} \ \ \textbf{calcFitness}(A); \\
\mbox{}\texttt{369:} \} \\
\mbox{}\texttt{370:}  \\
\mbox{}\texttt{371:} \textit{/*\ Create\ a\ graph\ and\ set\ nodes\ to\ certain\ location\ */} \\
\mbox{}\texttt{372:} graph\ \textbf{initGraph}()\ \{ \\
\mbox{}\texttt{373:} \ \ \ graph\ A; \\
\mbox{}\texttt{374:} \ \ \ \textbf{setRandGraph}(A); \\
\mbox{}\texttt{375:} \ \ \ \textbf{return}\ A; \\
\mbox{}\texttt{376:} \} \\
\mbox{}\texttt{377:}  \\
\mbox{}\texttt{378:} \textit{//\ Generates\ a\ population\ of\ MAX$\_$POP\ graphs\ with\ random\ coordinates} \\
\mbox{}\texttt{379:} void\ \textbf{initPopulation\ }()\ \{ \\
\mbox{}\texttt{380:} \ \ int\ i; \\
\mbox{}\texttt{381:}  \\
\mbox{}\texttt{382:} \ \ \textbf{for}\ (i=0;\ i$<$\ MAX$\_$POP;i++)\ \{ \\
\mbox{}\texttt{383:} \ \ \ \ population[i]\ =\ \textbf{initGraph}(); \\
\mbox{}\texttt{384:} \ \ \} \\
\mbox{}\texttt{385:} \} \\
\mbox{}\texttt{386:} \textit{//\ Using\ bubblesort\ we\ sort\ the\ graphs\ in\ the\ population\ on\ fitness} \\
\mbox{}\texttt{387:} void\ \textbf{sortPopulation\ }()\ \{ \\
\mbox{}\texttt{388:} \ graph\ tmp; \\
\mbox{}\texttt{389:} \ int\ i,\ j; \\
\mbox{}\texttt{390:} \ \textbf{for}\ (j\ =\ 1;\ j\ $<$\ MAX$\_$POP;\ j++\ )\ \{ \\
\mbox{}\texttt{391:} \ \ \textbf{for}\ (i\ =\ 0;\ i\ $<$\ MAX$\_$POP-j;\ i++\ )\ \{ \\
\mbox{}\texttt{392:} \ \ \ \ \textbf{if}\ (population[i].fitness\ $>$\ population[i+1].fitness)\ \{ \\
\mbox{}\texttt{393:} \ \ \ \ \ \ tmp\ =\ population[i]; \\
\mbox{}\texttt{394:} \ \ \ \ \ \ population[i]\ =\ population[i+1]; \\
\mbox{}\texttt{395:} \ \ \ \ \ \ population[i+1]\ =\ tmp; \\
\mbox{}\texttt{396:} \ \ \ \ \} \\
\mbox{}\texttt{397:} \ \ \} \\
\mbox{}\texttt{398:} \ \} \\
\mbox{}\texttt{399:} \} \\
\mbox{}\texttt{400:}  \\
\mbox{}\texttt{401:} \textit{/*\ Opens\ input\ file\ with\ adjacency-matrix\ which\ contains\ data\ about\ the} \\
\mbox{}\texttt{402:} \textit{\ *\ number\ of\ nodes\ (N)\ on\ the\ first\ line\ and\ the\ values\ of\ the} \\
\mbox{}\texttt{403:} \textit{\ *\ connections\ between\ those\ nodes\ in\ a\ N\ x\ N\ matrix\ in\ the\ following} \\
\mbox{}\texttt{404:} \textit{\ *\ lines} \\
\mbox{}\texttt{405:} \textit{\ */} \\
\mbox{}\texttt{406:} void\ \textbf{openFile}(char\ *\ inputFile)\ \{ \\
\mbox{}\texttt{407:} \ \ ifstream\ input; \\
\mbox{}\texttt{408:} \ \ int\ i,\ j; \\
\mbox{}\texttt{409:} \ \ input.\textbf{open}(inputFile,\ ios::in); \\
\mbox{}\texttt{410:}  \\
\mbox{}\texttt{411:} \ \ \textbf{if}\ (input)\ \{ \\
\mbox{}\texttt{412:} \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Opening\ "{}}$<$$<$\ inputFile\ $<$$<$\ \texttt{"{}..."{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{413:} \ \ \ \ input\ $>$$>$\ num$\_$nodes; \\
\mbox{}\texttt{414:} \ \ \ \ \textbf{if}\ (num$\_$nodes\ $<$=\ 0)\ \{ \\
\mbox{}\texttt{415:} \ \ \ \ \ \ \ \ input.\textbf{close}(); \\
\mbox{}\texttt{416:} \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Invalid\ data\ format!"{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{417:} \ \ \ \ \ \ \ \ \textbf{exit}(EX$\_$DATAERR); \\
\mbox{}\texttt{418:} \ \ \ \ \}\ \textbf{else}\ \textbf{if}\ (num$\_$nodes\ $<$\ MAX$\_$NODES)\ \{ \\
\mbox{}\texttt{419:} \ \ \ \ \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
\mbox{}\texttt{420:} \ \ \ \ \ \ \ \ \textbf{for}\ (j=0;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
\mbox{}\texttt{421:} \ \ \ \ \ \ \ \ \ \ input\ $>$$>$\ distances[i][j]; \\
\mbox{}\texttt{422:} \ \ \ \ \ \ \ \ \ \ \textbf{if}\ (input.\textbf{eof}())\ \{ \\
\mbox{}\texttt{423:} \ \ \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Invalid\ data\ format!"{}}\ $<$$<$endl; \\
\mbox{}\texttt{424:} \ \ \ \ \ \ \ \ \ \ \ \ \textbf{exit}(EX$\_$DATAERR); \\
\mbox{}\texttt{425:} \ \ \ \ \ \ \ \ \ \ \} \\
\mbox{}\texttt{426:} \ \ \ \ \ \ \ \ \ \ \textbf{if}\ (distances[i][j]\ $>$\ lon$\_$con)\{ \\
\mbox{}\texttt{427:} \ \ \ \ \ \ \ \ \ \ \ \ lon$\_$con\ =\ distances[i][j]; \\
\mbox{}\texttt{428:} \ \ \ \ \ \ \ \ \ \ \} \\
\mbox{}\texttt{429:} \ \ \ \ \ \ \ \ \} \\
\mbox{}\texttt{430:} \ \ \ \ \ \ \} \\
\mbox{}\texttt{431:} \ \ \ \ \}\ \textbf{else}\ \{ \\
\mbox{}\texttt{432:} \ \ \ \ \ \ \ \ input.\textbf{close}(); \\
\mbox{}\texttt{433:} \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Number\ of\ nodes\ in\ "{}}$<$$<$\ inputFile; \\
\mbox{}\texttt{434:} \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}\ exceeds\ maximum\ number\ of\ nodes"{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{435:} \ \ \ \ \ \ \ \ \textbf{exit}(EX$\_$DATAERR); \\
\mbox{}\texttt{436:} \ \ \ \ \} \\
\mbox{}\texttt{437:} \ \ \}\ \textbf{else}\ \{ \\
\mbox{}\texttt{438:} \ \ \ \ \ \ input.\textbf{close}(); \\
\mbox{}\texttt{439:} \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Error:\ Couldn't\ open\ file\ "{}}\ $<$$<$\ inputFile\ $<$$<$\ endl; \\
\mbox{}\texttt{440:} \ \ \ \ \ \ \textbf{exit}(EX$\_$NOINPUT); \\
\mbox{}\texttt{441:} \ \ \} \\
\mbox{}\texttt{442:}  \\
\mbox{}\texttt{443:} \ \ \textit{/*\ Transform\ 2d\ structure\ to\ 1d\ archs\ to\ allow\ easy\ computations\ */} \\
\mbox{}\texttt{444:} \ \ num$\_$archs\ =\ 0; \\
\mbox{}\texttt{445:} \ \ \textbf{for}\ (i\ =\ 0;\ i\ $<$\ num$\_$nodes;\ i++)\ \{ \\
\mbox{}\texttt{446:} \ \ \ \ \textbf{for}\ (j\ =\ i+1;\ j\ $<$\ num$\_$nodes;\ j++)\ \{ \\
\mbox{}\texttt{447:} \ \ \ \ \ \ \textbf{if}\ (distances[i][j]\ $>$\ 0)\ \{ \\
\mbox{}\texttt{448:} \ \ \ \ \ \ \ \ archs[num$\_$archs].a\ =\ i; \\
\mbox{}\texttt{449:} \ \ \ \ \ \ \ \ archs[num$\_$archs].b\ =\ j; \\
\mbox{}\texttt{450:} \ \ \ \ \ \ \ \ archs[num$\_$archs].distance\ =\ distances[i][j]; \\
\mbox{}\texttt{451:} \ \ \ \ \ \ \ \ num$\_$archs++; \\
\mbox{}\texttt{452:} \ \ \ \ \ \ \} \\
\mbox{}\texttt{453:} \ \ \ \ \} \\
\mbox{}\texttt{454:} \ \ \} \\
\mbox{}\texttt{455:} \} \\
\mbox{}\texttt{456:}  \\
\mbox{}\texttt{457:} \textit{//\ Prints\ the\ adjacency-matrix\ of\ openFile()\ to\ the\ screen} \\
\mbox{}\texttt{458:} void\ \textbf{printDistances}()\ \{ \\
\mbox{}\texttt{459:} \ \ int\ i,\ j; \\
\mbox{}\texttt{460:}  \\
\mbox{}\texttt{461:} \ \ cout\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{462:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
\mbox{}\texttt{463:} \ \ \ \ \textbf{for}\ (j=0;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
\mbox{}\texttt{464:} \ \ \ \ \ \ \ \ \ \ \ \ cout\ $<$$<$\ distances[i][j]$<$$<$\ \texttt{"{}\ "{}}; \\
\mbox{}\texttt{465:} \ \ \ \ \} \\
\mbox{}\texttt{466:} \ \ \ \ cout\ $<$$<$\ endl;\ \ \ \ \  \\
\mbox{}\texttt{467:} \ \ \} \\
\mbox{}\texttt{468:} \ \ cout\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{469:} \} \\
\mbox{}\texttt{470:}  \\
\mbox{}\texttt{471:} \textit{/*\ Prints\ the\ coordinates\ of\ every\ point\ in\ a\ graph\ to\ the\ screen\ in} \\
\mbox{}\texttt{472:} \textit{\ *\ graphviz\ compatible\ output} \\
\mbox{}\texttt{473:} \textit{\ *\ cat\ $<$$<$EOF\ $|$\ neato\ \ -Tpng\ -oga.png\ \ \&\&\ open\ ga.png} \\
\mbox{}\texttt{474:} \textit{\ */} \\
\mbox{}\texttt{475:} void\ \textbf{printGraph}(graph\&\ A)\ \{ \\
\mbox{}\texttt{476:} \ \ int\ i; \\
\mbox{}\texttt{477:}  \\
\mbox{}\texttt{478:} \ \ cout\ $<$$<$\ \texttt{"{}graph\ G\ \{\ node\ [shape=circle,"{}} \\
\mbox{}\texttt{479:} \ \ \ \ \ \ \ $<$$<$\ \texttt{"{}fontname=}\texttt{\textbackslash{}"{}}\texttt{Lucida\ Console}\texttt{\textbackslash{}"{}}\texttt{,margin=0,0];"{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{480:} \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
\mbox{}\texttt{481:} \ \ \ \ \ cout\ $<$$<$\ \texttt{"{}C"{}}\ $<$$<$\ i\ $<$$<$\ \texttt{"{}[pos=}\texttt{\textbackslash{}"{}}\texttt{"{}}\ $<$$<$\ A.nodes[i].x\ *\ 28\ $<$$<$\ \texttt{"{},"{}}\ $<$$<$ \\
\mbox{}\texttt{482:} \ \ \ \ \ A.nodes[i].y\ *\ 28\ $<$$<$\ \texttt{"{}!}\texttt{\textbackslash{}"{}}\texttt{,\ label=}\texttt{\textbackslash{}"{}}\texttt{C"{}}\ $<$$<$\ i\ $<$$<$\ \texttt{"{}}\texttt{\textbackslash{}"{}}\texttt{];"{}}\ $<$$<$\ endl;\  \\
\mbox{}\texttt{483:} \ \ \} \\
\mbox{}\texttt{484:} \ \ \textbf{for}\ (i=0;\ i\ $<$\ num$\_$archs;\ i++)\ \{ \\
\mbox{}\texttt{485:} \ \ \ \ cout\ $<$$<$\ \texttt{"{}C"{}}\ $<$$<$\ archs[i].a\ $<$$<$\ \texttt{"{}\ -\/-\ C"{}}\ $<$$<$\ archs[i].b\ $<$$<$\ \texttt{"{};"{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{486:} \ \ \} \\
\mbox{}\texttt{487:} \ \ cout\ $<$$<$\ \texttt{"{}\}"{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{488:} \} \\
\mbox{}\texttt{489:}  \\
\mbox{}\texttt{490:}  \\
\mbox{}\texttt{491:} \textit{//\ Prints\ every\ graph\ stored\ in\ array\ population} \\
\mbox{}\texttt{492:} void\ \textbf{printPopulation\ }()\ \{ \\
\mbox{}\texttt{493:} \ \ int\ i; \\
\mbox{}\texttt{494:} \ \ cerr\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{495:} \ \ \textbf{for}\ (i=0;\ i$<$\ MAX$\_$POP;\ i++)\ \{ \\
\mbox{}\texttt{496:} \ \ \ \ cerr\ $<$$<$\ i\ $<$$<$\ \texttt{"{}\ =$>$\ "{}}; \\
\mbox{}\texttt{497:} \ \ \ \ \textbf{printGraph}(population[i]); \\
\mbox{}\texttt{498:} \ \ \} \\
\mbox{}\texttt{499:} \ \ cerr\ $<$$<$\ \texttt{"{}\ "{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{500:} \} \\
\mbox{}\texttt{501:}  \\
\mbox{}\texttt{502:}  \\
\mbox{}\texttt{503:} \textit{/*\ Implementation\ of\ Steady\ State\ Evolution\ Algorithm\ based\ on\ p.119\ AI} \\
\mbox{}\texttt{504:} \textit{\ *\ Book\ */} \\
\mbox{}\texttt{505:} int\ \textbf{main}(int\ argc,\ char\ *\ argv[])\ \{ \\
\mbox{}\texttt{506:} \ \ int\ i,j; \\
\mbox{}\texttt{507:} \ \ int\ org$\_$dist,\ new$\_$dist; \\
\mbox{}\texttt{508:} \ \ int\ select$\_$one,\ select$\_$two; \\
\mbox{}\texttt{509:} \ \ int\ loopCounter; \\
\mbox{}\texttt{510:} \ \ unsigned\ int\ randomSeed; \\
\mbox{}\texttt{511:}  \\
\mbox{}\texttt{512:} \ \ graph\ min; \\
\mbox{}\texttt{513:} \ \ graph\ child$\_$one,\ child$\_$two; \\
\mbox{}\texttt{514:}  \\
\mbox{}\texttt{515:} \ \ \textit{//\ use\ random\ seed\ to\ create\ x,y\ coordinates\ of\ a\ point} \\
\mbox{}\texttt{516:} \ \ randomSeed\ =\ (unsigned)\textbf{time}(0); \\
\mbox{}\texttt{517:} \ \ randomSeed\ =\ 0; \\
\mbox{}\texttt{518:} \ \ \textbf{srand}(randomSeed); \\
\mbox{}\texttt{519:} \ \ \textit{/*\ Debug\ static\ seed\ */} \\
\mbox{}\texttt{520:} \ \ \textit{//\ srand(0);} \\
\mbox{}\texttt{521:} \ \  \\
\mbox{}\texttt{522:} \ \ \textit{//\ Open\ the\ file\ that\ \ contains\ data\ about} \\
\mbox{}\texttt{523:} \ \ \textit{//\ the\ number\ odf\ branches\ and\ which\ branches\ are\ } \\
\mbox{}\texttt{524:} \ \ \textit{//\ connected\ with\ each\ other} \\
\mbox{}\texttt{525:} \ \ \textbf{if}\ (argc\ $>$=\ 2)\ \{ \\
\mbox{}\texttt{526:} \ \ \ \ \textbf{openFile}(argv[1]); \\
\mbox{}\texttt{527:} \ \ \}\ \textbf{else}\ \{ \\
\mbox{}\texttt{528:} \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Usage:\ "{}}\ $<$$<$\ argv[0]\ $<$$<$\ \texttt{"{}\ $<$filename$>$\ $<$loopCount$>$"{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{529:} \ \ \ \ \textbf{exit}(EX$\_$USAGE); \\
\mbox{}\texttt{530:} \ \ \} \\
\mbox{}\texttt{531:}  \\
\mbox{}\texttt{532:} \ \ \textbf{if}\ (argc\ ==\ 3)\ \{ \\
\mbox{}\texttt{533:} \ \ \ \ loopCounter\ =\ \textbf{atoi}(argv[2]); \\
\mbox{}\texttt{534:} \ \ \}\ \textbf{else}\ \{ \\
\mbox{}\texttt{535:} \ \ \ \ loopCounter\ =\ DEFAULT$\_$LOOPS; \\
\mbox{}\texttt{536:} \ \ \} \\
\mbox{}\texttt{537:}  \\
\mbox{}\texttt{538:} \ \ \textit{/*\ To\ optimize\ the\ speed\ of\ the\ genetic\ algoritm\ we\ limit\ the\ domain} \\
\mbox{}\texttt{539:} \textit{\ \ \ *\ of\ the\ points\ */} \\
\mbox{}\texttt{540:} \ \ \textbf{if}\ ((lon$\_$con\ *\ num$\_$nodes)\ $<$\ MAX$\_$COORDINATES)\{ \\
\mbox{}\texttt{541:} \ \ \ \ max$\_$cord\ =\ lon$\_$con\ *\ num$\_$nodes; \\
\mbox{}\texttt{542:} \ \ \}\ \textbf{else}\ \{ \\
\mbox{}\texttt{543:} \ \ \ \ max$\_$cord\ =\ MAX$\_$COORDINATES; \\
\mbox{}\texttt{544:} \ \ \} \\
\mbox{}\texttt{545:} \ \ cerr\ $<$$<$\ \texttt{"{}Domain\ of\ points\ is\ set\ to\ "{}} \\
\mbox{}\texttt{546:} \ \ \ \ \ \ \ $<$$<$\ max$\_$cord\ $<$$<$\ \texttt{"{}\ x\ "{}}\ $<$$<$\ max$\_$cord\ $<$$<$\ endl; \\
\mbox{}\texttt{547:} \ \  \\
\mbox{}\texttt{548:} \ \ \textit{//\ Minimum\ graph\ to\ store\ best\ found\ solution} \\
\mbox{}\texttt{549:} \ \ min.fitness\ =\ INT$\_$MAX; \\
\mbox{}\texttt{550:} \ \  \\
\mbox{}\texttt{551:} \ \ \textit{/*\ Populate\ population,\ with\ random\ values\ */} \\
\mbox{}\texttt{552:} \ \ \textbf{initPopulation}(); \\
\mbox{}\texttt{553:} \ \  \\
\mbox{}\texttt{554:} \ \ \textbf{for}\ (i=0;\ i$<$\ loopCounter;\ i++)\ \{ \\
\mbox{}\texttt{555:} \ \ \ \ \ \textit{//\ Sort\ the\ population\ of\ graphs\ so\ that\ graph} \\
\mbox{}\texttt{556:} \ \ \ \ \ \textit{//\ with\ smallest\ fitness\ is\ placed\ in\ population[0]} \\
\mbox{}\texttt{557:} \ \ \ \ \ \textbf{sortPopulation}(); \\
\mbox{}\texttt{558:} \ \ \ \ \  \\
\mbox{}\texttt{559:} \ \ \ \ \ \textit{//\ Store\ the\ lowest\ found\ fitness\ if\ it\ is\ better} \\
\mbox{}\texttt{560:} \ \ \ \ \ \textit{//\ then\ the\ fitness\ we\ already\ had\ stored} \\
\mbox{}\texttt{561:} \ \ \ \ \ \textbf{if}\ (min.fitness\ $>$\ population[0].fitness)\{ \\
\mbox{}\texttt{562:} \ \ \ \ \ \ \ \ \textbf{copyGraph}(population[0],min); \\
\mbox{}\texttt{563:} \ \ \ \ \ \} \\
\mbox{}\texttt{564:} \ \ \ \ \ \ \ \ \ \  \\
\mbox{}\texttt{565:} \ \ \ \ \ \textit{//\ Stop\ if\ optimal\ is\ found\ e.g\ fitness\ equals\ zero} \\
\mbox{}\texttt{566:} \ \ \ \ \ \textbf{if}(population[0].fitness\ ==\ 0)\{ \\
\mbox{}\texttt{567:} \ \ \ \ \ \ \textbf{break}; \\
\mbox{}\texttt{568:} \ \ \ \ \ \} \\
\mbox{}\texttt{569:} \ \ \ \ \ \ \ \ \ \  \\
\mbox{}\texttt{570:} \ \ \ \ \ \textit{//\ Selection\ reproducing\ parents\ via\ roulette\ wheel} \\
\mbox{}\texttt{571:} \ \ \ \ \ \textit{//\ fittest\ parents\ get\ selected\ } \\
\mbox{}\texttt{572:} \ \ \ \ \ select$\_$one\ =\ \textbf{selectGraph}(); \\
\mbox{}\texttt{573:} \ \ \ \ \ \textbf{do}\ \{ \\
\mbox{}\texttt{574:} \ \ \ \ \ \ \ select$\_$two\ =\ \textbf{selectGraph}(); \\
\mbox{}\texttt{575:} \ \ \ \ \ \}\textbf{while}\ (select$\_$one\ ==\ select$\_$two); \\
\mbox{}\texttt{576:} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \\
\mbox{}\texttt{577:} \ \ \ \ \ \textit{//\ set\ points\ in\ children\ with\ crossover\ result\ of\ parents\ } \\
\mbox{}\texttt{578:} \ \ \ \ \ \textbf{copyGraph}(population[select$\_$one],\ child$\_$one); \\
\mbox{}\texttt{579:} \ \ \ \ \ \textbf{copyGraph}(population[select$\_$two],\ child$\_$two);\  \\
\mbox{}\texttt{580:} \ \ \ \ \  \\
\mbox{}\texttt{581:} \ \ \ \ \ \textit{//\ Crossover\ the\ selected\ parents\ \ } \\
\mbox{}\texttt{582:} \ \ \ \ \ \textbf{crossUniform}(child$\_$one,\ child$\_$two); \\
\mbox{}\texttt{583:} \ \ \ \ \  \\
\mbox{}\texttt{584:} \ \ \ \ \ \textit{//\ mutate\ childs\ with\ small\ random\ probability\ usually\ 50\%} \\
\mbox{}\texttt{585:} \ \ \ \ \ \textbf{mutateGraph}(99,\ child$\_$one); \\
\mbox{}\texttt{586:} \ \ \ \ \ \textbf{mutateGraph}(99,\ child$\_$two); \\
\mbox{}\texttt{587:} \ \ \ \ \  \\
\mbox{}\texttt{588:} \ \ \ \ \ \textit{//\ Calculate\ fitness\ of\ both\ children} \\
\mbox{}\texttt{589:} \ \ \ \ \ \textbf{calcFitness}(child$\_$one); \\
\mbox{}\texttt{590:} \ \ \ \ \ \textbf{calcFitness}(child$\_$two); \\
\mbox{}\texttt{591:} \ \ \ \ \  \\
\mbox{}\texttt{592:} \ \ \ \ \ \textit{//\ Least\ fittest\ graphs\ in\ population\ get\ replaced} \\
\mbox{}\texttt{593:} \ \ \ \ \ \textbf{copyGraph}(child$\_$one,population[MAX$\_$POP\ -2]); \\
\mbox{}\texttt{594:} \ \ \ \ \ \textbf{copyGraph}(child$\_$two,population[MAX$\_$POP\ -1]); \\
\mbox{}\texttt{595:} \ \ \} \\
\mbox{}\texttt{596:} \ \  \\
\mbox{}\texttt{597:} \ \ cerr\ $<$$<$\ \texttt{"{}Best\ found\ coordinates\ after\ "{}}$<$$<$\ i\ $<$$<$ \\
\mbox{}\texttt{598:} \ \ \texttt{"{}\ epochs\ for\ given\ input\ graph:\ "{}}\ $<$$<$\ endl;\  \\
\mbox{}\texttt{599:} \ \ \textbf{printGraph}(min); \\
\mbox{}\texttt{600:} \ \  \\
\mbox{}\texttt{601:} \ \ \textbf{if}(min.fitness\ !=\ 0)\{ \\
\mbox{}\texttt{602:} \ \ \ \ \textbf{for}\ (i=0;\ i$<$\ num$\_$nodes;\ i++)\ \{ \\
\mbox{}\texttt{603:} \ \ \ \ \ \ \textbf{for}\ (j=i+1;\ j$<$\ num$\_$nodes;\ j++)\ \{ \\
\mbox{}\texttt{604:} \ \ \ \ \ \ \ \ org$\_$dist\ =\ distances[i][j]; \\
\mbox{}\texttt{605:} \ \ \ \ \ \ \ \ \textbf{if}\ (org$\_$dist\ !=\ 0)\{ \\
\mbox{}\texttt{606:} \ \ \ \ \ \ \ \ \ \ new$\_$dist\ =\ \textbf{calcDistance}(min.nodes[i],min.nodes[j]); \\
\mbox{}\texttt{607:} \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}Distance\ between\ point\ C"{}}$<$$<$\ i\ $<$$<$\ \texttt{"{}\ -\ C"{}}\ $<$$<$\ j\ $<$$<$\ \texttt{"{}\ =\ "{}}; \\
\mbox{}\texttt{608:} \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \textbf{calcDistance}(min.nodes[i],min.nodes[j])\ $<$$<$\ \texttt{"{}\ "{}}; \\
\mbox{}\texttt{609:} \ \ \ \ \ \ \ \ \ \ \textbf{if}\ (new$\_$dist\ !=\ org$\_$dist)\{ \\
\mbox{}\texttt{610:} \ \ \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}SHOULD\ BE\ "{}}\ $<$$<$\ org$\_$dist\ $<$$<$\ endl; \\
\mbox{}\texttt{611:} \ \ \ \ \ \ \ \ \ \ \}\ \textbf{else}\ \{ \\
\mbox{}\texttt{612:} \ \ \ \ \ \ \ \ \ \ \ \ cerr\ $<$$<$\ \texttt{"{}CORRECT"{}}\ $<$$<$\ endl; \\
\mbox{}\texttt{613:} \ \ \ \ \ \ \ \ \ \ \} \\
\mbox{}\texttt{614:} \ \ \ \ \ \ \ \ \} \\
\mbox{}\texttt{615:} \ \ \ \ \ \ \} \\
\mbox{}\texttt{616:} \ \ \ \ \} \\
\mbox{}\texttt{617:} \ \ \ \} \\
\mbox{}\texttt{618:} \ \ cerr\ $<$$<$\ \texttt{"{}Fitness\ Intersection\ :\ "{}}\ $<$$<$\ min.fitnessIntersection\ $<$$<$\ endl; \\
\mbox{}\texttt{619:} \ \ cerr\ $<$$<$\ \texttt{"{}Fitness\ Distance\ \ \ \ \ :\ "{}}\ $<$$<$\ min.fitnessDistance\ $<$$<$\ endl; \\
\mbox{}\texttt{620:} \ \ cerr\ $<$$<$\ \texttt{"{}Fitness\ Overall\ \ \ \ \ \ :\ "{}}\ $<$$<$\ min.fitness\ $<$$<$\ endl; \\
\mbox{}\texttt{621:} \ \ cerr\ $<$$<$\ \texttt{"{}Random\ seed\ \ \ \ \ \ \ \ \ \ :\ "{}}\ $<$$<$\ randomSeed\ $<$$<$\ endl; \\
\mbox{}\texttt{622:} \ \ \textbf{return}(EX$\_$OK); \\
\mbox{}\texttt{623:} \} \\