\chapter{Kreslenie dvojfarebn\'ych grafov}
%!
%! teraz\MPI-I-96-1-025.ps
%! bipartitny graf, skupiny vrcholov oproti sebe, jedna skupina je fixovana, crossing
%! minimalizacia je NP-tazka, tu je heuristika, ktora pracuje velmi dobre
%!
%!
\hyphenation{na-kre-sle-nie heu-ri-st-\'ik bu-de-me na-pr\'i-klad pr\'i-\v ta-\v zli-v\'e}
%!
%!
V tejto kapitole najprv zadefinujeme \v co je to dvojfarebn\'y graf a navhneme metriku, ktor\'a bude sl\'u\v zi\v t na 
ur\v cenie, ako dobre je nakreslen\'y dan\'y dvojfarebn\'y graf. Metrika bude postaven\'a na kr\'i\v zen\'i hr\'an a na 
v\'ahach t\'ychto kr\'i\v zen\'i. 
\v Ziadna dostupn\'a literat\'ura sa kreslen\'im dvojfarebn\'ych grafov nezaoberala.
Uvedieme algoritmy, ktor\'e sme implementovali na kreslenie tejto mno\v ziny grafov, \v ci u\v z to bud\'u algoritmy, ktor\'e 
nakreslia graf priamo, alebo algoritmy, ktor\'e s\'u zalo\v zen\'e na prid\'avan\'i vrcholov do existuj\'uceho 
nakreslen\'eho grafu pomocou heurist\'ik uveden\'ych v predch\'adzaj\'ucej kapitole, alebo pomocou inej met\'ody. 
V\v setky tieto algoritmy boli naprogramovan\'e nad kni\v znicou algoritmov \texttt{LEDA 5.0}, verzia pre 
\texttt{Mandrake~10.0}, kompil\'ator \texttt{g++~3.2.2}. 
\newline
\newline
%!
%!
Dvojfarebn\'y graf je graf, ktor\'eho ka\v zd\'y vrchol patr\'i do jednej z dvoch mno\v z\'in vrcholov. 
Prv\'a mno\v zina obsahuje prim\'arne vrcholy, druh\'a sekund\'arne. Nakreslenie dvojfarebn\'eho grafu m\^o\v ze by\v t 
u\v zito\v cn\'e, ak chceme zobrazi\v t objekty a spojenia medzi t\'ymito objektami, pri\v com objekty patria do dvoch 
skup\'in. Raz n\'as m\^o\v ze zauj\'ima\v t nakreslenie jednotliv\'ych skup\'in grafu, inokedy zasa celkov\'e nakreslenie 
grafu, preto by malo by\v t nakreslenie grafu dobr\'e v r\'amci jednotliv\'ych skup\'in ako aj v r\'amci cel\'eho grafu.
%!
\newtheorem{dvojfareb}{Defin\'icia}[section]
\begin{dvojfareb}
Dvojfarebn\'y graf $G$ nazveme tak\'y graf, ktor\'eho vrcholy patria do dvoch disjunktn\'ych mno\v z\'in, 
t.j. $(V(G)=V_1\cup  V_2)$$\wedge$$(V_1\cap V_2=\epsilon)$. Vrcholy z mno\v ziny $V_1$ naz\'yvame prim\'arne, vrcholy z 
mno\v ziny $V_2$ sekund\'arne.
\end{dvojfareb}
%!
%!
Na ur\v cenie, \v ci je nakreslenie dvojfarebn\'eho grafu dobr\'e, potrebujeme zadefinova\v t metriku, pod\v la ktorej by 
sme to mohli zmera\v t. T\'ato metrika je zalo\v zen\'a na po\v cte kr\'i\v zen\'i hr\'an, kde ka\v zd\'e kr\'i\v zenie 
m\'a nejak\'u v\'ahu, pod\v la toho, na ak\'ych hran\'ach le\v z\'i. Hrany rozdel\'ime do troch disjunktn\'ych mno\v z\'in, 
pod\v la toho z ak\'ych mno\v z\'in s\'u ich koncov\'e  vrcholy. 
Za ka\v zd\'e kr\'i\v zenie na hrane prirad\'ime tejto hrane penaliz\'aciu pod\v la toho, do ktorej mno\v ziny hr\'an patr\'i.
%!
%!
\newtheorem{hranvaha}[dvojfareb]{Defin\'icia}
\begin{hranvaha}
Nech G je dvojfarebn\'y graf, funkciu $m_{2fh}$ nazveme hranovou metrikou na grafe $G$, ak $\forall e\in E(G)$ s koncov\'ymi vrcholmi $v_1$, $v_2$ plat\'i~:
\newline
~~~~$m_{2fh}(e) = 3$~,~ak~~~$v_1,v_2\in V_1(G)$
\newline
~~~~$m_{2fh}(e) = 2$~,~ak~~~$v_1,v_2\in V_2(G)$
\newline
~~~~$m_{2fh}(e) = 1$~,~ak~~~$v_1\in V_1(G) \Longleftrightarrow v_2 \notin V_1(G)$
\end{hranvaha}

\newtheorem{bodvaha}[dvojfareb]{Defin\'icia}
\begin{bodvaha}
M\'ame dan\'y graf $G$ a jeho zakreslenie do roviny $D$. Funkciu $m_{2fb}$ nazveme bodovou metrikou na grafe $G$, ak $\forall v\in D$ plat\'i :
\newline
~~~~$m_{2fb}(v) = \sum_{i=1}^k m_{2fh}(e_i)$ ,~kde $\{e_1,e_2,\ldots ,e_k\}$ je mno\v zina v\v setk\'ych hr\'an, na ktor\'ych bod $v$ le\v z\'i ($v\in e_i ,\forall i=1..k$).
\end{bodvaha}

Z defin\'icie hranovej metriky je jasn\'e, \v ze najviac sa bude prihliada\v t na hrany, ktor\'e ved\'u medzi prim\'arnymi vrcholmi a najmenej na hrany, ktor\'e ved\'u medzi vrcholmi z r\^oznych mno\v z\'in. Teraz zadefinujeme body kr\'i\v zenia grafu, bud\'u to tie body, ktor\'e vznikn\'u na kr\'i\v zen\'i hr\'an.
%!
%!
\newtheorem{body_krizenia}[dvojfareb]{Defin\'icia}
\begin{body_krizenia}
M\'ame dan\'y graf $G$ a jeho zakreslenie do roviny $D$. Mno\v zinu bodov $Crp_{G,D}=\{v \in D | \exists e_1,e_2 \in E(G), e_1\neq e_2, v\in e_1 \wedge v\in e_2 \wedge v \notin V(G)\}$ budeme naz\'yva\v t 
body kr\'i\v zenia grafu $G$ pri zakreslen\'i $D$.
\end{body_krizenia}
%!
%!
Teraz u\v z m\^o\v zeme zadefinova\v t kr\'i\v zov\'e \v c\'islo pre dvojfarebn\'y graf. Toto \v c\'islo je ur\v cen\'e 
bodmi kr\'i\v zenia grafu a hranami, na ktor\'ych tieto kr\'i\v zenia le\v zia. Toto \v c\'islo bude z\'arove\v n na\v sou metrikou na dobr\'e zakreslenie dvojfarebn\'eho grafu.
%!
%!
\newtheorem{krizove_cislo}[dvojfareb]{Defin\'icia}
\begin{krizove_cislo}
Kr\'i\v zov\'e \v c\'islo dvojfarebn\'eho grafu $G$ pri
zakreslen\'i $D$ do roviny je $Cr2f_{G,D} = \sum_{i=1}^k m_{2fb}(b_i)$, kde $\{b_1,b_2,\ldots ,b_k \} = Crp_{G,D}$.
\end{krizove_cislo}
%!
%!
\section{Dokres\v lovanie vrcholov, modifik\'acia heurist\'ik}
%!
%!
Navrhneme modifik\'acie heurist\'ik uveden\'ych v predch\'adzaj\'ucej kapitole na dokres\v lovanie vrcholov do u\v z 
nakreslen\'eho dvojfarebn\'eho grafu. Tieto modifik\'acie by mali sl\'u\v zi\v t na to, aby kr\'i\v zov\'e \v c\'islo 
nakreslen\'eho dvojfarebn\'eho grafu bolo \v co najmen\v sie. 
\newline
\newline
V Heuristike 1 m\^o\v zeme navrhn\'u\v t tak\'eto modifik\'acie : 
\begin{itemize}
\item pri r\'atan\'i vrcholovej vzdialenosti budeme za ka\v zd\'y vrchol z inej skupiny prir\'atava\v t penaliz\'aciu
\item pri r\'atan\'i vrcholovej vzdialenosti bude ma\v t ka\v zd\'a hrana in\'u v\'ahu (napr\'iklad pod\v la funkcie $m_{2fh}$, t\'ato funkcia m\'a iba kladn\'e hodnoty, teda m\^o\v zeme pou\v zi\v t Dijkstrov algoritmus na r\'atanie vrcholovej vzdialenosti)
\item pri dokres\v lovan\'i nov\'eho vrcholu do grafu budeme uva\v zova\v t iba susedov z rovnakej skupiny ako je 
dokres\v lovan\'y vrchol
\item pri h\v ladan\'i umiestnenia vrchola vo vybratej oblasti m\^o\v zeme ka\v zd\'e kr\'i\v zenie zapo\v c\'itava\v t 
inak (napr\'iklad pod\v la funkcie $m_{2fb}$)
\end{itemize}
%!
%!
V heuristike 2 m\^o\v zeme navrhn\'u\v t tak\'eto modifik\'acie :
\begin{itemize}
\item pri zis\v tovan\'i l\'u\v cov\'eho \v c\'isla m\^o\v zeme ka\v zd\'u hranu zapo\v c\'itava\v t inak (napr\'iklad pod\v la funkcie $m_{2fh}$)
\item pri h\v ladan\'i vhodn\'eho prieniku m\^o\v zeme uva\v zova\v t iba oblasti vytvoren\'e susedmi z rovnakej skupiny ako je dop\'l\v nan\'y vrchol
\item pri h\v ladan\'i umiestnenia vrchola vo vybranom prieniku m\^o\v zeme ka\v zd\'e kr\'i\v zenie zapo\v c\'itava\v t 
inak (napr\'iklad pod\v la funkcie $m_{2fb}$)
\end{itemize}
%!
%!
\v Dal\v sia modifik\'acia heurist\'ik m\^o\v ze by\v t zalo\v zen\'a na tom, v akom porad\'i budeme vrcholy do grafu 
vklada\v t. Pre ka\v zd\'y vkladan\'y vrchol m\^o\v zeme ur\v ci\v t jeho d\^ole\v zitos\v t pod\v la toho, s 
ko\v lk\'ymi vrcholmi z prim\'arnej a sekund\'arnej skupiny sused\'i a pomocou toho ur\v ci\v t poradie vrcholov pri 
vkladan\'i do grafu.
\newline 
\newline
%!
%!
Ot\'azne ale je, ktor\'e z t\'ychto modifik\'aci\'i naozaj pom\^o\v zu zmen\v si\v t kr\'i\v zov\'e \v c\'islo 
dvojfarebn\'eho grafu. Pri h\v ladan\'i umiestnenia vrchola vo vybratej oblasti (prieniku) n\'am modifik\'acia naozaj 
pom\^o\v ze, preto\v ze vych\'adza z defin\'icie dvojfarebn\'eho kr\'i\v zov\'eho \v c\'isla. Tak isto pom\^o\v ze aj 
modifik\'acia pri r\'atan\'i l\'u\v cov\'eho \v c\'isla, t\'a je tie\v z zalo\v zen\'a na defin\'icii kr\'i\v zov\'eho 
\v c\'isla dvojfarebn\'eho grafu, ostatn\'e modifik\'acie treba experiment\'alne overi\v t. \v C\'im viac budeme pri 
dokres\v lovan\'i vrcholu znev\'yhod\v nova\v t kr\'i\v zenie medzi vrcholmi z tej istej skupiny, t\'ym bude v\'ysledn\'e nakreslenie hor\v sie ale zlep\v s\'i sa skupinov\'e nakreslenie. 
%!
\section{Kreslenie dvojfarebn\'ych grafov existuj\'ucimi algoritmami}
%!
%!
Tu uvedieme niektor\'e z\'akladn\'e algoritmy, ktor\'e sme pou\v zili na kreslenie dvojfarebn\'ych grafov. 
Vstupom algoritmov je graf $G$, mno\v zina jeho vrcholov, pre ka\v zd\'y vrchol jeho typ (\v ci je prim\'arny alebo 
sekund\'arny), mno\v zina hr\'an nad t\'ymito vrcholmi, s\'uradnice \v lav\'eho horn\'eho a prav\'eho doln\'eho bodu plochy, do ktorej m\'a by\v t dan\'y graf nakreslen\'y. 
\begin{itemize}
\item \textbf{N\'ahodn\'e nakreslenie -} ka\v zd\'y vrchol umiestnime na n\'ahodn\'u poz\'iciu tak, aby bol vn\'utri plochy ur\v cenej na nakreslenie grafu
\item \textbf{Kruhov\'e nakreslenie -} vrcholy s\'u rozmiestnen\'e pravidelne po kru\v znici okolo stredu plochy, do 
ktorej sa m\'a graf nakresli\v t. S\'u tri varianty tohoto nakreslenia, pod\v la toho v akom porad\'i s\'u vrcholy na 
kru\v znici rozmiestnen\'e (n\'ahodn\'e poradie vrcholov, najprv vrcholy z prim\'arnej skupiny potom zo sekund\'arnej, 
tretie nakreslenie vrcholov je pod\v la toho ako s\'u ulo\v zen\'e vo vstupnom grafe). 
\item \textbf{Plan\'arne nakreslenie -} otestuje vstupn\'y graf, ak je plan\'arny, tak vygeneruje jeho plan\'arne nakreslenie,
ak nie je plan\'arny, tak zobraz\'i o tom spr\'avu
\item \textbf{Spring nakreslenie -} medzi susedn\'ymi vrcholmi s\'u definovan\'e pr\'i\v ta\v zliv\'e sily, medzi nesusedn\'ymi
odpudiv\'e, algoritmus m\'a e\v ste ako vstup po\v cet iter\'aci\'i, v ka\v zdej iter\'acii zmen\'i polohu vrchola vzh\v ladom
na ostatn\'e vrcholy a sily medzi nimi
\item \textbf{Spring 2 nakreslenie -} spring met\'oda kreslenia grafu, len pred jej spusten\'im odstr\'ani z grafu hrany,
ktor\'e sp\'ajaj\'u vrcholy z r\^oznych skup\'in, po nakreslen\'i ich do grafu znovu prid\'a
\end{itemize} 
Pred spusten\'im \v lubovoln\'eho z t\'ychto algoritmov program najprv otestuje, \v ci vstupn\'y graf je naozaj dvojfarebn\'y,
to znamen\'a \v ci neobsahuje slu\v cky, paraleln\'e hrany, \v ci m\'a aspo\v n jeden vrchol a \v ci ka\v zd\'y zo vstupn\'ych 
vrcholov patr\'i do jednej zo skup\'in. Po nakreslen\'i grafu sa v \v lavom hornom rohu zobrazia dve \v c\'isla,  
znamenaj\'uce kr\'i\v zov\'e \v c\'islo dvojfarebn\'eho grafu a po\v cet kr\'i\v zen\'i tohoto grafu. Tieto dve \v 
c\'isla sa pravidelne updatuj\'u ak sa graf nejako zmen\'i (prid\'a/odoberie hrana, prid\'a/odoberie vrchol, posunie vrchol).
%!
%!
\section{Kreslenie dvojfarebn\'ych grafov dokres\v lovan\'im vrcholov}
Pri dokres\v lovan\'i vrcholov m\'ame na v\'yber \v styri z\'akladn\'e algoritmy, ktor\'ymi m\^o\v zeme vrchol do grafu 
dokres\v lova\v t. Tieto algoritmy maj\'u rovnak\'e vstupy ako u\v z uveden\'e algoritmy a naviac e\v ste obsahuj\'u aj 
vstupn\'e parametre, ktor\'e sl\'u\v zia na ur\v cenie ako dan\'y graf nakresli\v t.
\newline
Algoritmy zalo\v zen\'e na dokres\v lovan\'i vrcholov do grafu : 
\begin{itemize}
\item \textbf{Heuristika 1 -} Do grafu dokresl\'i vrchol pod\v la heuristiky uvedenej v predch\'adzaj\'ucej kapitole, parametre
heuristiky s\'u : $r=10$, $k=30$
\item \textbf{Heuristika 2 -} Do grafu dokresl\'i vrchol pod\v la heuristiky uvedenej v predch\'adzaj\'ucej kapitole, parametre
heuristiky s\'u : $r=10$, $k=30$, $t=2$
\item \textbf{Spring -} Do grafu dokresl\'i vrchol spring met\'odou, u\v z nakreslen\'e  vrcholy maj\'u fixovan\'u polohu
\item \textbf{Spring naraz -} Do grafu dokresl\'i v\v setky ch\'ybaj\'uce vrcholy naraz, u\v z nakreslen\'e vrcholy maj\'u 
fixovan\'u polohu
\end{itemize}
Pred spusten\'im t\'ychto algoritmov mus\'i e\v ste u\v  z\'ivate\v l nastavi\v t parametre nakreslenia :
\begin{itemize}
\item \textbf{Z\'akladn\'e nakreslenie -} Ak\'ym algoritmom sa m\'a nakresli\v t z\'akladn\'y graf, s\'u na v\'yber tri 
mo\v znosti - n\'ahodn\'e nakreslenie, plan\'arne nakreslenie, spring nakreslenie
\item \textbf{Maxim\'alny po\v cet kr\'i\v zen\'i -} Ko\v lko maxim\'alne kr\'i\v zen\'i bude ma\v t z\'akladn\'y graf 
\item \textbf{Met\'oda spravenia z\'akladu -} \v Ci sa m\'a spravi\v t z\'akladn\'y graf z pr\'azdneho grafu prid\'avan\'im 
vrcholov, alebo z cel\'eho grafu $G$ postupn\'ym odoberan\'im jeho vrcholov
\item \textbf{Priorita vrcholov pri roben\'i z\'akladn\'eho grafu -} Ke\v d kon\v struujeme z\'akladn\'y graf, tak ktor\'e 
vrcholy m\'ame uprednost\v nova\v t aby boli v tomto grafe, parametre vrcholov s\'u~: stupe\v n vrchola v celom grafe $G$, 
stupe\v n vrchola v tomto z\'akladnom grafe (nakreslenom), stupe\v n vrchola v jeho skupine, n\'ahodn\'e \v c\'islo vrchola
\item \textbf{Priorita vrcholov pri dokres\v lovan\'i do grafu -} V akom porad\'i m\'ame prid\'ava\v t vrcholy do nakreslen\'eho
grafu, parametre vrcholov s\'u~: stupe\v n vrchola v celom grafe $G$, stupe\v n vrchola v tomto nakreslenom grafe (teda 
ko\v lko jeho susedov je u\v z nakreslen\'ych), stupe\v n vrchola v jeho skupine, n\'ahodn\'e \v c\'islo vrchola
\end{itemize}
Nakreslenie grafu sa kon\v struuje nasledovne : Za\v c\'iname s pr\'azdnym grafom alebo cel\'ym grafom $G$, pod\v la toho
\v ci z\'akladn\'e nakreslenie kon\v struujeme prid\'avan\'im alebo odoberan\'im vrcholov. Ak odober\'ame vrcholy, tak v\v zdy
odoberieme vrchol s najni\v z\v sou prioritou, a\v z dok\'ym nie je splnen\'y parameter na po\v cet kr\'i\v zen\'i. Ak 
prid\'avame vrcholy do z\'akladn\'eho grafu, tak prid\'avame vrcholy s najvy\v s\v sou prioritou, pokia\v l z\'akladn\'y 
graf sp\'l\v na parameter na po\v cet kr\'i\v zen\'i. Ak u\v z m\'ame z\'akladn\'y graf nakreslen\'y, tak vrcholy do\v n 
prid\'avame pod\v la ich priority (od najvy\v s\v sej) a dokres\v lujeme pod\v la zvolenej met\'ody.
%\newline
%\newline
%Rovnako ako pri predch\'adzaj\'ucich algoritmoch program najprv otestuje \v ci vstupn\'y graf je dvojfarebn\'y a po jeho 
%nakreslen\'i alebo updatovan\'i zobraz\'i v \v lavom hornom rohu dvojfarebn\'e kr\'i\v zov\'e \v c\'islo ako aj po\v cet 
%kr\'i\v zen\'i v tomto grafe. 