\chapter{Porovnanie algoritmov kreslenia dvojfarebn\'ych grafov}
\label{sec:kapitola6}
%!
%!
\hyphenation{vy-tv\'a-ra-li vr-cho-lov pa-ra-me-tre}
%!
%!
V tejto kapitole porovn\'ame niektor\'e algoritmy uveden\'e v predch\'adzaj\'ucej kapitole. V programe sme implementovali
aj funkciu na testovanie grafu. Pri funkcii vytv\'aranie dvojfarebn\'eho grafu, je mo\v znos\v t za\v skrtn\'u\v t 
pol\'i\v cko otestova\v t graf kresliacimi algoritmami. Ke\v d sa graf vytvor\' i, tak sa postupne spustia algoritmy na 
kreslenie dvojfarebn\'ych grafov a nakoniec sa graf nakresl\'i algoritmom, pri ktorom mal najmen\v sie dvojfarebn\'e kr\'i\v zov\'e
\v c\'islo.
\newline
Pri komplexnom testovan\'i sme postupovali nasledovne, n\'ahodne sme vytv\'arali dvojfarebn\'e grafy a na ka\v zdom 
vytvorenom grafe sme spustili testovan\'e algoritmy. V\'ysledok ka\v zd\'eho algoritmu sme potom zap\'isali do s\'uborov
(kompletn\'y textov\'y protokol o testovan\'i \texttt{test.txt} a s\'ubor ur\v cen\'y na \v dal\v sie spracovanie \texttt{test.out}).
Testovan\'e grafy sme potom rozdelili do skup\'in, pod\v la po\v ctu ich vrcholov a hustoty hr\'an : 
\begin{itemize}
\item \textbf{G1 -} po\v cet vrcholov 8-10~~~~~~     hustota hr\'an $\leq$ 50\%
\item \textbf{G2 -} po\v cet vrcholov 11-14~~~~~    hustota hr\'an $\leq$ 25\%
\item \textbf{G3 -} po\v cet vrcholov 11-14~~~~~    25\% < hustota hr\'an $\leq$ 50\%
\item \textbf{G4 -} po\v cet vrcholov 15-19~~~~~    hustota hr\'an $\leq$ 25\%
\item \textbf{G5 -} po\v cet vrcholov 15-19~~~~~    25\% < hustota hr\'an $\leq$ 50\%
\item \textbf{G6 -} po\v cet vrcholov 20-30~~~~~    hustota hr\'an $\leq$ 20\%
\item \textbf{G7 -} po\v cet vrcholov 31-50~~~~~    hustota hr\'an $\leq$ 12\%
\end{itemize}
Pre ostatn\'e typy grafov sme implementovan\'e algoritmy netestovali, preto\v ze ak m\'a graf ve\v la hr\'an, tak vznik\'a ve\v lmi ve\v la 
kr\'i\v zen\'i a nakreslenie je nepreh\v ladn\'e. Takisto \v casov\'a zlo\v zitos\v t niektor\'ych algoritmov (zalo\v zen\'ych na Heuristik\'ach 1,2) je ve\v lmi ve\v lk\'a a testovanie by trvalo pr\'ili\v s dlho.
\newline
\newline
Ka\v zd\'y z testovan\'ych grafov sme otestovali pomocou viacer\'ych algoritmov a nastaven\'i parametrov : \label{params}
\begin{itemize}
\item Dokres\v lovanie postupne Heuristika 1 (\textbf{A1}) - 8 r\^oznych nastavan\'i parametrov
\item Dokres\v lovanie postupne Heuristika 2 (\textbf{A2}) - 8 r\^oznych nastavan\'i parametrov
\item Dokres\v lovanie postupne Spring (\textbf{A3}) - 8 r\^oznych nastavan\'i parametrov
\item Dokres\v lovanie naraz Spring (\textbf{A4}) - 8 r\^oznych nastavan\'i parametrov
\item Kruhov\'e nakreslenie - v porad\'i (\textbf{A5}), nahodn\'e (\textbf{A6})
\item Spring nakreslenie (\textbf{A7}), Spring 2 nakreslenie (\textbf{A8})
\item N\'ahodn\'e nakreslenie (\textbf{A9})
\end{itemize}
Pri dokres\v lovan\'i, kde sme pre ka\v zd\'y algoritmus testovali 8 r\^oznych nastaven\'i parametrov, boli tieto parametre 
rovnak\'e :
\begin{itemize}
\item Z\'akladn\'e nakreslenie : Plan\'arne(1) / Spring(2)
\item Z\'akladn\'e nakreslenie spravi\v t : Prid\'avan\'im(3) / Odoberan\'im(4) vrcholov
\item Pri kon\v struovan\'i z\'akladn\'eho grafu s\'u priority vrcholov : Deg v celom > Deg v nakreslenom > Deg v skupine (5) / 
Deg v nakreslenom > Deg v celom > Deg v skupine (6)
\end{itemize}
\v C\'isla v z\'atvork\'ach sl\'u\v zia na ozna\v cenie ako boli nastaven\'e parametre pri testovan\'i. Napr\'iklad 
algoritmus ozna\v cen\'y ako \textbf{A2}$_{145}$ je dokres\v lovanie vrcholov pomocou Heuristiky 2, z\'akladn\'y graf 
je nakreslen\'y plan\'arne odoberan\'im vrcholov z grafu $G$, vrcholy s\'u v z\'akladnom grafe s prioritou Deg v celom grafe, 
potom Deg v nakreslenom grafe, potom Deg v skupine, potom n\'ahodne.
\newline
\v Dal\v sie nastavenie parametrov je nasledovn\'e : maxim\'alny po\v cet kr\'i\v zen\'i je 0, priorita pri dokres\v lovan\'i 
vrcholov je Deg v celom > Deg v nakreslenom > Deg v skupine. Ak bol z\'akladn\'y graf kreslen\'y spring met\'odou, tak sme 
parameter maxim\'alny po\v cet kr\'i\v zen\'i v z\'akladnom nakreslen\'i testovali pre hodnoty 0, 5 a 10, relat\'ivne 
najlep\v sie v\'ysledky dosahovali kresliace algoritmy pri nastaven\'i tohoto parametra na hodnotu 0. 
\newline
\newline
Pri testovan\'i algoritmov pre r\^ozne parametre s\'u v nasleduj\'ucich tabu\v lk\'ach pre ka\v zd\'e nastavenie parametrov a ka\v zd\'y typ grafu 3 
nameran\'e hodnoty. \textbf{P\%} ud\'ava pre ko\v lko \% grafov bolo nakreslenie grafu s t\'ymito parametrami najlep\v sie 
spomedzi ostatn\'ych nastaven\'i vzh\v ladom na dvojfarebn\'e kr\'i\v zov\'e \v c\'islo (s\'u\v cet \% m\^o\v ze by\v t 
v\"a\v c\v s\'i ako 100\% preto\v ze niektor\'e nakreslenia m\^o\v zu ma\v t rovnak\'e dvojfarebn\'e kr\'i\v zov\'e 
\v c\'islo). \textbf{Cr} ud\'ava priemern\'y po\v cet kr\'i\v zen\'i nameran\'y na testovan\'ych grafoch, \textbf{2F} 
priemern\'e dvojfarebn\'e kr\'i\v zov\'e \v c\'islo. Najlep\v sie nameran\'e hodnoty s\'u v tabu\v lke ozna\v cen\'e 
\textbf{bold} p\'ismom. 
%!
%!
\section{Heuristika 1 - testovanie pre r\^ozne parametre}
%!
%!
Pomocou Heuristiky 1 sme testovali nakreslenie dvojfarebn\'ych grafov na 8 r\^oznych nastaven\'i parametrov.
\newline
\newline
\input{heu1.tex}
\newline
\newline
Z tabu\v lky je vidie\v t, \v ze ak z\'akladn\'y graf kresl\'ime plan\'arne, tak je to ove\v la efekt\'ivnej\v sie vzh\v ladom
na po\v cet kr\'i\v zen\'i aj dvojfarebn\'e kr\'i\v zov\'e \v c\'islo. 
Tak isto sa zd\'a by\v t efekt\'ivnej\v sie z\'akladn\'y graf kon\v struova\v t prid\'avan\'im vrcholov do pr\'azdneho
grafu. Pri postupnom 
kon\v struovan\'i z\'akladn\'eho grafu sa ned\'a poveda\v t, ktor\'a priorita vrcholov d\'ava lep\v sie v\'ysledky. 
\newline
Relat\'ivne najlep\v sie v\'ysledky dosahuje algoritmus \textbf{A1}$_{135}$.
%!
%!
%\newpage
\section{Heuristika 2 - testovanie pre r\^ozne parametre}
%!
%!
Pomocou Heuristiky 2 sme testovali nakreslenie dvojfarebn\'ych grafov na 8 r\^oznych nastaven\'i parametrov.
\newline
\newline
\input{heu2.tex}
\newline
\newline
Z tabu\v lky je vidie\v t, \v ze ak z\'akladn\'y graf kresl\'ime plan\'arne, tak je to ove\v la efekt\'ivnej\v sie 
vzh\v ladom
na po\v cet kr\'i\v zen\'i aj dvojfarebn\'e kr\'i\v zov\'e \v c\'islo. 
Ak pou\v z\'ivame ako z\'akladn\'e nakreslenie plan\'arne, tak je lep\v sie z\'akladn\'y graf spravi\v t prid\'avan\'im vrcholov, 
ak pou\v zijeme ako z\'akladn\'e nakreslenie spring, tak je ho lep\v sie kon\v struova\v t odoberan\'im vrcholov. 
Pri postupnom kon\v struovan\'i z\'akladn\'eho grafu sa ned\'a poveda\v t, ktor\'a priorita vrcholov d\'ava lep\v sie 
v\'ysledky. 
\newline 
Relat\'ivne najlep\v sie v\'ysledky dosahuje algoritmus \textbf{A2}$_{135}$ a podobn\'e v\'ysledky \textbf{A2}$_{136}$.
%!
%!
\newpage
\section{Spring postupne - testovanie pre r\^ozne parametre}
%!
%!
Pomocou spring met\'ody postupn\'eho dokres\v lovania vrcholov sme testovali nakreslenie dvojfarebn\'ych grafov pre 
8 r\^oznych nastaven\'i parametrov.
\newline
\newline
\input{spring.tex}
\newline
\newline
Relat\'ivne najlep\v sie v\'ysledky dosahuj\'u algoritmy \textbf{A3}$_{135}$ a \textbf{A3}$_{136}$. Ostatn\'e nastavenia
parametrov dosiahli pribli\v zne rovnak\'e v\'ysledky.
%!
%!
\newpage
\section{Spring naraz - testovanie pre r\^ozne parametre}
%!
%!
Pomocou spring met\'ody dokreslenia vrcholov naraz sme testovali nakreslenie dvojfarebn\'ych grafov pre 
8 r\^oznych nastaven\'i parametrov.
\newline
\newline
\input{spring_nar.tex}
\newline
\newline
Pri tomto testovan\'i sme dostali ve\v lmi nejednozna\v cn\'e v\'ysledky. Pre r\^ozne typy grafov dosiahlo
najlep\v sie v\'ysledky in\'e nastavenie parametrov. Pre mal\'e grafy to bol algoritmus  \textbf{A4}$_{135}$, pre stredn\'e 
grafy to boli \textbf{A4}$_{136}$ a \textbf{A4}$_{145}$, pre v\"a\v c\v sie grafy \textbf{A4}$_{245}$.
%!
%!
\newpage
\section{Porovnanie najlep\v s\'ich algoritmov}
\label{porov}
V tejto podkapitole vz\'ajomne porovn\'ame r\^ozne typy algoritmov, ktor\'e sme testovali. Tam, kde sme testovali algoritmus 
pre viacero nastaven\'i parametrov, sme vybrali to nastavenie parametrov, ktor\'e d\'avalo relat\'ivne najlep\v sie 
v\'ysledky. Pri dokres\v lovan\'i vrcholov to bol zvy\v cajne plan\'arny z\'aklad a kon\v struovanie z\'akladn\'eho grafu 
prid\'avan\'im vrcholov. Vysvetlenie \v c\'iseln\'ych parametrov pri dokres\v lovac\'ich algoritmov n\'ajdeme na strane~\pageref{params}.
\newline
\newline
\input{spolu.tex}
\newline
\newline
Z tabu\v lky je vidie\v t, \v ze najefekt\'ivnej\v s\'i algoritmus z h\v ladiska po\v ctu kr\'i\v zen\'i ako aj dvojfarebn\'eho 
kr\'i\v zov\'eho \v c\'isla je jednozna\v cne algoritmus zalo\v zen\'y na Heuristike 1. Druh\'ym najlep\v s\'im algoritmom
v t\'ychto krit\'eri\'ach je ten zalo\v zen\'y na Heuristike 2. Vo v\v seobecnosti algoritmy zalo\v zen\'e na dokres\v lovan\'i
vrcholov dosiahli lep\v sie v\'ysledky ako tie ostatn\'e. Zauj\'imav\'e je, \v ze n\'ahodn\'e nakreslenie dosiahlo
lep\v sie v\'ysledky ako nakreslenie kruhov\'e a pre v\"a\v c\v sie grafy bolo spring dokres\v lovanie vrcholov naraz
efekt\'ivnej\v sie ako spring dokres\v lovanie postupne. 
\newline
\newline
Pri testovan\'i sme z\'arove\v n merali aj \v casy, za ktor\'e ka\v zd\'y algoritmus testovan\'e grafy nakreslil. V\v setky testy boli roben\'e na 
po\v c\'ita\v ci AMD 1GHz, 256 MB RAM, pod syst\'emom \texttt{Mandrake Linux 10.0}. Priemern\'y \v cas v sekund\'ach na nakreslenie 
jedn\'eho grafu pre ka\v zd\'y algoritmus je v Tabu\v lke 2. Ako je vidie\v t, \v casovo najn\'aro\v cnej\v s\'i je algoritmus zalo\v zen\'y na Heuristike 2, graf z mno\v ziny \textbf{G7} nakreslil v 
priemere za 68.20 sek\'und. \v Casovo n\'aro\v cn\'y je aj algoritmus zalo\v zen\'y na Heuristike 1, ostatn\'e algoritmy v tomto meran\'i dosiahli 
dobr\'e v\'ysledky. To, \v ze algoritmy zalo\v zen\'e na Heuristik\'ach 1 a 2 boli \v casovo na tom hor\v sie sa dalo o\v cak\'ava\v t
pod\v la anal\'yzy ich zlo\v zitosti, ktor\'a sa nach\'adza na strane~\pageref{analyza}. Prekvapilo ale, \v ze pri v\"a\v c\v s\'ich grafoch bol algoritmus 
zalo\v zen\'y na Heuristike 1 viac ako 8-kr\'at r\'ychlej\v s\'i ako ten zalo\v zen\'y na Heuristike 2. 
\newline
\newline
\input{cas.tex}\\
Tabu\v lka 2: Priemern\'y \v cas na nakreslenie jedn\'eho grafu v sec.
\newline
\newline
\newline
Celkovo, algoritmus zalo\v zen\'y na Heuristike 1 dosiahol ove\v la lep\v sie v\'ysledky z h\v ladiska po\v ctu kr\'i\v zen\'i,
dvojfarebn\'eho kr\'i\v zov\'eho \v c\'isla ako aj r\'ychlosti nakreslenia oproti algoritmu zalo\v zen\'emu na Heuristike 2.
%!
%!
%!
%! 