\appendix
%!
%!
\hyphenation{kon-\v st\'a-nt me-dzi opa-\v cnom}
%!
%!
\chapter{Kr\'atky manu\'al k implementovan\'emu programu}
%!
%!
Program bol implementovan\'y nad kni\v znicou algoritmov \texttt{LEDA 5.0}, verzia pre \texttt{Mandrake~10.0}, kompil\'ator \texttt{g++~3.2.2}. 
Vyu\v z\'iva existuj\'uce prostredie na pracovanie s grafmi \texttt{GraphWin}. Implementovali sme do tohoto prostredia funkcie, ktor\'e sl\'u\v zia
na vytv\'aranie, zobrazovanie, a kreslenie dvojfarebn\'ych grafov. Tieto funkcie sme rozdelili do dvoch podmenu, 
\emph{2 farebn\'e grafy} (obr\'azok \ref{fig:menu}) a \emph{Nakreslenie 2-farebn\'eho grafu} (obr\'azok \ref{fig:menu2}).
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.6\textwidth]{obrazky/manual/menu1.eps}
\caption{Menu : 2-farebn\'e grafy}
\label{fig:menu}
\end{center}
\end{figure}
%!
\newline
Pri kreslen\'i 2-farebn\'ych grafov si m\^o\v zeme vybra\v t z viacer\'ych met\'od. Podmenu \emph{Jednoduch\'e nakreslenie} obsahuje n\'ahodn\'e
a kruhov\'e nakreslenie. Podmenu \emph{Nakreslenie naraz} obsahuje plan\'arne nakreslenie, spring nakreslenie a nakreslenie spring 2. Podmenu 
\emph{Dokres\v lovan\'im vrcholov} (obr\'azok \ref{fig:menu2}) obsahuje algoritmy zalo\v zen\'e na dokres\v lovan\'i 
vrcholov. Vo\v lba \emph{Na\v sk\'alovanie} roztiahne nakreslenie grafu na rozmery otvoren\'eho \texttt{GraphWin} okna.
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.7\textwidth]{obrazky/manual/menu2.eps}
\caption{Menu : Nakreslenie 2-farebn\'ych grafov}
\label{fig:menu2}
\end{center}
\end{figure}
%!
%!
\newline
Pri vytv\'aran\'i n\'ahodn\'eho 2-farebn\'eho grafu mus\'i u\v z\'ivate\v l nastavi\v t parametre, pod\v la ktor\'ych 
sa graf vytvor\'i. Tieto parametre s\'u po\v cet vrcholov grafu, percentu\'alny podiel vrcholov z prvej skupiny, percentu\'alny podiel hr\'an medzi 
vrcholmi z prvej skupiny, medzi vrcholmi z druhej skupiny a percentu\'alny podiel hr\'an medzi vrcholmi z r\^oznych skup\'in (obr\'azok \ref{fig:vytvorenie}). 
U\v z\'ivate\v l m\^o\v ze za\v skrtn\'u\v t mo\v znos\v t \emph{Otestova\v t nakreslenie algoritmami}, \v co sp\^osob\'i \v ze vytvoren\'y graf sa 
postupne nakresl\'i testovan\'ymi algoritmami a nakoniec zobraz\'i nakreslenie s najmen\v s\'im dvojfarebn\'ym kr\'i\v zov\'ym \v c\'islom.
%!
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/manual/vytvorenie.eps}
\caption{Vytvorenie n\'ahodn\'eho 2-farebn\'eho grafu}
\label{fig:vytvorenie}
\end{center}
\end{figure}
%!
%!
\newpage
Ak m\'ame 2-farebn\'y graf nakreslen\'y, tak si m\^o\v zeme necha\v t zobrazi\v t jeho jednotliv\'e \v casti (obr\'azok \ref{fig:zobrazenie}). M\^o\v zeme
zobrazi\v t skupiny vrcholov ktor\'e chceme, alebo hrany sp\'ajaj\'uce len niektor\'e typy vrcholov. Aby sa hrana zobrazila, tak musia by\v t zobrazen\'e
oba jej koncov\'e vrcholy. 
%!
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/manual/zobrazenie.eps}
\caption{Zobrazenie 2-farebn\'eho grafu}
\label{fig:zobrazenie}
\end{center}
\end{figure}
%!
%!
\newpage
Ak m\'ame nakreslen\'y graf a nevieme, \v ci je 2-farebn\'y, tak si m\^o\v zeme otestova\v t, ktor\'e podmienky 2-farebnosti sp\'l\v na alebo 
nesp\'l\v na (obr\'azok \ref{fig:testovanie}). 2-farebn\'y graf nesmie ma\v t paraleln\'e hrany, slu\v cky, mus\'i ma\v t aspo\v n jeden vrchol a ka\v zd\'y
nakreslen\'y vrchol mus\'i patri\v t do jednej z dvoch skup\'in, \v co znamen\'a, \v ze vrchol mus\'i by\v t \v cervenej (prv\'a skupina) alebo
\v zltej (druh\'a skupina) farby.
%!
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/manual/testovanie.eps}
\caption{Testovanie \v ci je graf 2-farebn\'y}
\label{fig:testovanie}
\end{center}
\end{figure}
%!
%!
\newpage
Ak chceme 2-farebn\'y graf nakresli\v t algoritmom zalo\v zen\'ym na dokres\v lovan\'i vrcholov, tak mus\'ime najprv nastavi\v t parametre, pod\v la ktor\'ych
sa bude dan\'y graf kresli\v t. Nastavovanie t\'ychto parametrov je na obr\'azku \ref{fig:kreslenie}.
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/manual/kreslenie.eps}
\caption{Kreslenie 2-farebn\'ych grafov dokres\v lovan\'im vrcholov.}
\label{fig:kreslenie}
\end{center}
\end{figure}
%!
%!
\chapter{Preh\v lad niektor\'ych implementovan\'ych funkci\'i}
Program bol implementovan\'y pomocou viacer\'ych zdrojov\'ych s\'uborov : 
\begin{description}
\item[]\texttt{2f\_grafy.cpp} : je to z\'akladn\'y zdrojov\'y s\'ubor, v \v nom s\'u implementovan\'e z\'akladn\'e 
funkcie a includovan\'e ostatn\'e zdrojov\'e s\'ubory
%\newline
\item[]\texttt{\_create.c} : obsahuje funkciu na vytvorenie n\'ahodn\'eho grafu podla zvolen\'ych parametrov
%\newline
\item[]\texttt{\_drawing.c} : obsahuje v\v setky implementovan\'e funkcie na kreslenie dvojfarebn\'ych grafov a k nim pomocn\'e funkcie 
\end{description}
%
%
E\v ste boli implementovan\'e aj \v dal\v sie programy sl\'u\v ziace na vytv\'aranie tabuliek z nameran\'ych \'udajov :
\begin{description}
%\newline
\item[]\texttt{udaje.c} : na\v c\'ita otestovan\'e \'udaje zo s\'uboru \texttt{test.out} a pod\v la hodnoty kon\v stanty \texttt{ALGORITMUS} vytvor\'i z nameran\'ych
\'udajov tabu\v lku a zap\'i\v se ju do s\'uboru (pod\v la kon\v stanty \texttt{ALGORITMUS} : \texttt{heu1.tex}, \texttt{heu2.tex}, \texttt{spring.tex} alebo 
\texttt{spring\_nar.tex})
%\newline
\item[]\texttt{udaje\_naj.c} : na\v c\'ita otestovan\'e \'udaje zo s\'uboru \texttt{test.out} a pod\v la kon\v st\'ant \texttt{ALG\_1}, \texttt{ALG\_2}, \dots 
\texttt{ALG\_8} vytvor\'i z nameran\'ych \'udajov tabu\v lku a zap\'i\v se ju do s\'uboru \texttt{spolu.tex}
%\newline
\end{description}
%!
%!
%\newline
Niektor\'e vybrat\'e funkcie z \texttt{2f\_grafy.cpp} : 
%!
%!
\begin{description}
%\newline
%\newline
\item[]\texttt{int crossing\_number(GraphWin\& GW);}
\newline 
vr\'ati dvojfarebn\'e kr\'i\v zov\'e \v c\'islo grafu nakreslen\'eho na ploche \texttt{GW}
%%
\item[]\texttt{int crossings(GraphWin\& GW);}
\newline
vr\'ati po\v cet kr\'i\v zen\'i grafu nakreslen\'eho na ploche \texttt{GW}
%%
\item[]\texttt{void zobraz\_graf(GraphWin\& GW, int vrcholy, int hrany1,\\int hrany2, int hrany3);}
\newline
zobraz\'i dvojfarebn\'y graf na ploche \texttt{GW} pod\v la zvolen\'ych parametrov (ktor\'e vrcholy/hrany s\'u zobrazen\'e alebo skryt\'e)
%
\item[]\texttt{void vypis\_cr\_number(GraphWin\& GW);}
\newline
na plochu \texttt{GW} v\v lavo hore vyp\'i\v se dvojfarebn\'e kr\'i\v zov\'e \v c\'islo a po\v cet kr\'i\v zen\'i grafu
%
\item[]\texttt{int testuj\_2f(GraphWin\& GW,int tabulka);}
\newline
otestuje, \v ci graf na ploche \texttt{GW} je dvojfarebn\'y, pod\v la hodnoty parametra vyp\'i\v se o tom info do tabu\v lky
%
\item[]\texttt{void change\_node(GraphWin\& GW, const point\&);}
\newline
zmen\'i typ vrchola, ktor\'y obsahuje bod \texttt{point}
%
\item[]\texttt{void zobraz\_graf\_2f(GraphWin\& GW);}
\newline
vykresl\'i tabu\v lku, v ktorej si u\v z\'ivate\v l navol\'i parametre pre zobrazenie dvojfarebn\'eho grafu, n\'asledne graf 
pod\v la nastaven\'ych parametrov vykresl\'i
%
\item[]\texttt{void random2f(GraphWin\& GW);}
\newline
vykresl\'i tabu\v lku, v ktorej si u\v z\'ivate\v l navol\'i parametre pre n\'ahodn\'y dvojfarebn\'y graf, n\'asledne tak\'yto graf vytvor\'i
%
\item[]\texttt{int nakresli\_graf(GraphWin\& GW, int metoda, \ldots );}
% param1=0, int param2=0, int param3=0, int param4=0, int param5=0, int param6=3);}
\newline
graf na ploche \texttt{GW} vykresl\'i pod\v la zvolenej met\'ody a pod\v la dan\'ych parametrov
%
\item[]\texttt{int velke\_testovanie(GraphWin\& GW, int poc\_vrcholov,\\int poc\_hran, int vrch1, int hran1, int hran2, int hran3);}
\newline
na grafe z plochy \texttt{GW} spust\'i postupn\'e testovanie v\v setk\'ych testovan\'ych algoritmov
%
\item[]\texttt{void pustaj\_testy(GraphWin\& GW,int random);}
\newline
na ploche \texttt{GW} postupne vytv\'ara n\'ahodn\'e dvojfarebn\'e grafy a testuje na nich algoritmy
%!
%!
\end{description}
%\newline
%\newline
Niektor\'e vybrat\'e funkcie z \texttt{\_create.c} : 
%
%!\newline
%!\newline
\begin{description}
\item[]\texttt{void create\_2f\_graph(ugraph \&G1, int poc\_vrcholov,\\int poc\_hran, int vrcholy\_1, int hrany\_1, int hrany\_2);}
\newline
%\newline
pod\v la parametrov do objektu \texttt{G1} vytvor\'i nahodn\'y dvojfarebn\'y graf 
\end{description}
%\newline
%\newline
\newpage
Niektor\'e vybrat\'e funkcie z \texttt{\_drawing.c} : 
\begin{description}
%\newline
%\newline
\item[]\texttt{void RANDOM(graph\& G, node\_array<double>\& xpos, \\node\_array<double>\& ypos, \dots );}
%\newline
\item[]\texttt{void CIRCLE(graph\& G, node\_array<double>\& xpos, \\node\_array<double>\& ypos, \dots );}
%\newline
\item[]\texttt{void PLANAR\_NAK(graph\& G, node\_array<double>\& xpos, \\node\_array<double>\& ypos, \dots );}
%\newline
\item[]\texttt{void VYTVOR\_DOKRESLOVANIM(graph\& G, list<node>\& fixed, \\list<node>\& nonfixed, node\_array<double>\& xpos, \\node\_array<double>\& ypos, \dots );}
\end{description}
%\newline
%\newline
Pod\v la met\'ody a parametrov vytvor\'i nakreslenie grafu \texttt{G} a s\'uradnice jeho vrcholov zap\'i\v se do objektov \texttt{xpos}, 
\texttt{ypos}. Vo funkcii 
\texttt{VYTVOR\_DOKRESLOVANIM} s\'u implementovan\'e v\v setky kresliace algoritmy zalo\v zen\'e na dokres\v lovan\'i vrcholov, to ktorou met\'odou ho nakresl\'i z\'ale\v z\'i na hodnote jeho parametrov.
%
%
\begin{description}
%\newline
%\newline
\item[]\texttt{void HEURISTIKA\_1(graph \&G,list<node> fixed, node\& vrch, \\node\_array<double>\& xpos, node\_array<double>\& ypos, \dots , \\
double \&pos\_x, double \&pos\_y, \dots);}
%\newline
\item[]\texttt{void HEURISTIKA\_1(graph \&G,list<node> fixed, node\& vrch, \\node\_array<double>\& xpos, node\_array<double>\& ypos, \dots , \\
double \&pos\_x, double \&pos\_y, \dots);}
\end{description}
%\newline
%\newline
Do grafu \texttt{G}, ktor\'y m\'a nakreslen\'e vrcholy z \texttt{fixed} na poz\'ici\'ach z \texttt{xpos}, \texttt{ypos} 
vypo\v c\'ita pod\v la zvolenej heuristiky poz\'iciu pre vrchol \texttt{vrch} a zap\'i\v se ju do premenn\'ych \texttt{pos\_x}, \texttt{pos\_y}.
%\newline
%\newline
\begin{description}
\item[]\texttt{void NASKALUJ(graph \&G,node\_array<double>\& xpos, \\node\_array<double>\& ypos, double xleft, double xright,\\ double ybottom, double ytop);}
\end{description}
%\newline
%\newline
Nakreslenie grafu \texttt{G}, ktor\'eho vrcholy s\'u na poz\'ici\'ach z \texttt{xpos}, \texttt{ypos} roztiahne do 
obd\'l\v znika ohrani\v cen\'eho premenn\'ymi \texttt{xleft}, \texttt{ytop}, \texttt{xright}, \texttt{ybottom}.
%!
%!
%!
%!
\chapter{Probl\'emy pri implement\'acii v LEDA 5.0}
%!
%!
V tejto \v casti pr\'ilohy uvedieme niektor\'e probl\'emy, ktor\'e nastali pri implementovan\'i nad kni\v znicou 
\texttt{LEDA}. \v Cas\v t z nich bolo ve\v lmi \v ta\v zk\'e odhali\v t a n\'ajs\v t pre ne uspokojuj\'uce rie\v senie. 
T\'ato sekcia by mala pom\^oc\v t \v dal\v s\'im \v lu\v dom, ktor\'i bud\'u implementova\v t nad kni\v znicou 
\texttt{LEDA}, u\v setri\v t \v cas straten\'y pri h\v ladan\'i a odstra\v novan\'i ch\'yb.
%!
%!
%!
\begin{description}
\item[Probl\'em :] pri vytv\'aran\'i objektu \texttt{Polygon} pomocou mno\v ziny bodov m\^o\v ze by\v t vytvoren\'y polyg\'on presne opa\v cn\'y ako sme chceli
vytvori\v t, to znamen\'a \v ze bude jeho doplnkom (met\'ody \texttt{.inside} a \texttt{.outside} funguj\'u presne opa\v cne) 
%!
\item[Rie\v senie :] zist\'ime \v ci vzdialen\'y bod patr\'i vytvoren\'emu polyg\'onu, ak \'ano, tak polyg\'onu prirad\'ime jeho komplement :
\newline
\texttt{if (P.inside(point(-10000,-10000))) P=P.complement();}
\end{description}
%!
%!
\begin{description}
\item[Probl\'em :] niekedy pri vytv\'aran\'i objektu \texttt{Polygon} pomocou mno\v ziny bodov vyhl\'asi kritick\'u chybu \textbf{Segmentation fault} a ukon\v c\'i program
%!
\item[Rie\v senie :] pred vytvoren\'im polyg\'onu body otestujeme tak, \v ze cyklicky medzi ka\v zd\'ymi dvoma vytvor\'ime \'use\v cku (segment), zist\'ime
prieniky t\'ychto \'use\v ciek, ak sa mno\v zina bodov z prieniku rovn\'a mno\v zine bodov, pomocou ktor\'ych vytv\'arame 
polygon, tak ho m\^o\v zeme vytvori\v t
\end{description}
%!
%!
\begin{description}
\item[Probl\'em :] pri vyu\v z\'ivan\'i funkci\'i \texttt{LEDA} na r\'atanie priese\v cn\'ikov medzi geometrick\'ymi \'utvarmi (ray's, segment's, line's) 
vznikaj\'u vo v\'ysledku odch\'ylky
%!
\item[Rie\v senie :] treba da\v t pozor k \v comu je v\'ysledok ur\v cen\'y, ak chceme zisti\v t \v ci nejak\'y priese\v cn\'ik le\v z\'i na najekom 
geometrickom \'utvare (alebo \v ci je toto\v zn\'y s bodom) tak pou\v zijeme met\'odu \texttt{.distance()} na zistenie vzdialenosti od \'utvaru a 
porovn\'ame s nami zvolenou geometrickou odch\'ylkou (my sme zvolili odch\'ylku 0.002)
\end{description}
%!
%!
\begin{description}
\item[Probl\'em :] pri volan\'i funkci\'i, kde parametrom s\'u \texttt{LEDA} objekty ako \texttt{Graph} alebo \texttt{list<type>} musia by\v t tieto
parametre referencovan\'e cez ich adresu, (teda cez oper\'ator \texttt{\&}), v opa\v cnom pr\'ipade funkcia dostane pri jej volan\'i pr\'azdne objekty 
(napr\'iklad funkcia bude definovan\'a takto :  \texttt{int testuj(Graph \&G, list<node> \&vrcholy, int pocet);} )
%!
\item[Rie\v senie :] ak chceme vo volanej funkcii k\'opiu objektu modifikova\v t, tak si ju mus\'ime vytvori\v t a pracova\v t s \v nou 
(prira\v denie typu \texttt{Graph G1=G;} nefunguje !)
\end{description}
%!
%!
\begin{description}
\item[Probl\'em :] ak s\'u niektor\'e elementy grafu (vrcholy, hrany) skryt\'e (hidden), tak pri pou\v zit\'i iter\'atorov \texttt{for\_all\_nodes} 
(\texttt{for\_all\_edges}) s\'u dod\'avan\'e aj niektor\'e skryt\'e vrcholy namiesto neskryt\'ych
%!
\item[Rie\v senie :] ak chceme pou\v zi\v t iter\'ator cez v\v setky neskryt\'e vrcholy (hrany) grafu, tak pou\v zijeme tak\'uto kon\v strukciu :\\
\texttt{node v=G.first\_node();}\\
\texttt{  ~~while(v!=nil)}\\
\texttt{~~\{}\\
\texttt{~~~~~\dots}\\
\texttt{~~~~v=G.succ\_node(v);}\\
\texttt{~~\}}   \\
\end{description}
%!
%!
\begin{description}
\item[Probl\'em :] pri volan\'i funkcie \texttt{STRAIGHT\_LINE\_EMBEDDING}, ktor\'a sl\'u\v zi na plan\'arne nakreslenie grafu, mus\'i by\v t vstupn\'y graf orientovan\'y, v opa\v cnom pr\'ipade program vyhl\'asi chybu 
%!
\item[Rie\v senie :] pred volan\'im funkcie pou\v zijeme na vstupn\'y graf met\'odu\\
\texttt{G.make\_directed();}, po skon\v cen\'i 
funkcie \texttt{STRAIGHT\_LINE\_EMBEDDING} pou\v zijeme na graf met\'odu \texttt{G.make\_undirected();}
\end{description}
%!
%!
\chapter{Uk\'a\v zky nakreslenia niektor\'ych grafov}
%!
%!
V tejto \v casti pr\'ilohy uk\'a\v zeme v\'ysledn\'e nakreslenie dvoch grafov v implementovanom programe na kreslenie dvojfarebn\'ych
grafov. Ka\v zd\'y z t\'ychto grafov bol nakreslen\'y pomocou troch algoritmov : Heuristika~1, Heuristika~2 a 
spring met\'oda.
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/priloha_d/heu1_1.eps}
\caption{Nakreslenie grafu, ktor\'y m\'a 20 vrcholov a 43 hr\'an Heuristikou~1, \texttt{Cr2f : 64 cross : 21}.}
\end{center}
\end{figure}
%!/
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/priloha_d/heu2_1.eps}
\caption{Nakreslenie grafu, ktor\'y m\'a 20 vrcholov a 43 hr\'an Heuristikou~2, \texttt{Cr2f : 65 cross : 22}.}
\end{center}
\end{figure}
%!/
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/priloha_d/spring_1.eps}
\caption{Nakreslenie grafu, ktor\'y m\'a 20 vrcholov a 43 hr\'an spring met\'odou, \texttt{Cr2f : 155 cross : 48}.}
\end{center}
\end{figure}
%!/
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/priloha_d/heu1_2.eps}
\caption{Nakreslenie grafu, ktor\'y m\'a 30 vrcholov a 100 hr\'an Heuristikou~1, \texttt{Cr2f : 804 cross : 245}.}
\end{center}
\end{figure}
%!/
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/priloha_d/heu2_2.eps}
\caption{Nakreslenie grafu, ktor\'y m\'a 30 vrcholov a 100 hr\'an Heuristikou~2, \texttt{Cr2f : 955 cross : 291}.}
\end{center}
\end{figure}
%!/
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/priloha_d/spring_2.eps}
\caption{Nakreslenie grafu, ktor\'y m\'a 30 vrcholov a 100 hr\'an spring met\'odou, \texttt{Cr2f : 1212 cross : 341}.}
\end{center}
\end{figure}
%!/

%! 