\documentclass[12pt, a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[slovak]{babel}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,gensymb,mathrsfs}
\usepackage{amsthm}
\usepackage{enumitem}
\usepackage{fancyhdr}
\usepackage{multicol}
\renewcommand{\headrulewidth}{0pt}
\setlength{\parindent}{0pt}
\renewcommand{\baselinestretch}{1.2}

\usepackage{hyperref}

\begin{document}

\centerline{\LARGE\bf{Report}}
\medskip
\centerline{\large{Grochal Peter}}
\bigskip\hrule\bigskip





Na programovanie riešenia problému sme sa rozhodli použiť progamovací jazyk C++

Používame knižniciu vytvorenú na našej fakulte:
\href{https://bitbucket.org/relatko/ba-graph/src/master/}{ba-graph}.

Kubické grafy či snarky sme získali z 
\href{https://hog.grinvin.org/}{House of Graphs}.





\bigskip
\textbf{\large{Zimný semester:}}


\medskip
Počas zimného semestra sa podarilo:

\begin{enumerate}

\item
 Zoznámiť sa s tým ako sa (ne)inštalujú, testujú či používajú knižnice (C++),
 najmä ba\_graph.

\item
 Vymyslieť a naprogramovať štruktúru schopnú reprezentovať zároveň
 kubický graf aj multipól -- \verb|multipol.hpp|

 S pomocou knižnice ba-graph vyriešiť načítavanie kubického grafu.

\item
 Naprogramovať algoritmus generujúci všetky legálne farbenia grafu/multipólu
 (a následne vytvoriť testy na overenie korektnosti) -- \verb|colorgen.hpp|

 *Korektnosť funkcii bola zatiaľ otestovaná, iba pre kubické grafy.

\item
 Aby sa nám jednoduchšie programovali testy, vytvorili sme funkcie overujúce
 podobnosť dvoch Farbení -- \verb|coloreqv.hpp|

 - kôli efektivite zväčša predpokladáme že sú to farbenia toho istého grafu,
 no máme aj funkciu na overenie či sú farbenia toho istého grafu.

\item
 Vytvorili sme provizórny formát farbenia a provizórny výpis.

\end{enumerate}





\bigskip
\textbf{Práca s projektom:}


\medskip
V terajšej verzii je náš 
\href{https://bitbucket.org/pegro2/rp_repo/src/master/}{projekt}
akoby knižnica pre jazyk C++

Na jej použitie je potrebné naprogamovať si vlastný program
používajúci naše funkcie, alebo využiť a upraviť testy.

Stačí mať správne includenutý/upravený \verb|"project.hpp"|
ktorý includuje celý náš projekt.





\bigskip
\bigskip
Terajšia použiteľnosť:


\medskip
\verb|  |
Vytvorenie Kubického Grafu z graph6 formátu:

\verb|CubicMultipole m("graph6 format string")|


\medskip
\verb|  |
Vytvorenie Kubického Grafu z iného formátu podporovaného ba-graph knižnicou:

\verb|ba_graph::Graph g = ... ; CubicMultipole m(g);|



\bigskip
\verb|  |
Generovanie všetkých možných farbení grafu/multipólu:

\verb|CubicMultipole m = ... ; auto farbenia = all_colorings(m); |

\smallskip
\verb|all_colorings()| vracia pointer na vektor farbení 

(taký `unique\_ptr` čo sa sám uprace keď vyjde zo scope-u)



\bigskip
\verb|  |
Overenie podobnosti dvoch farbení:

\verb|color_equivalent(c1, c2, f)| \\
\verb|color_equivalent_with(c1, c2, f)|

Tieto funkcie použijú transformačnú funkciu f na transformáciu
zadaných farbení  \\
(napr. nejaký druh normalizácie -- premenovanie farieb?)

\smallskip
Líšia sa v tom, že verzia \verb|_with| aplikuje transformáciu iba na c1

(existuje hlavne kôli efektivite, napr. pri testoch overujeme podobnosť
veľa farbení s tým istým c2 $\leadsto$ bolo by zbytočné stále normalizovať c2 )


\medskip
Predprogramovaná transformačná funkcia je:

\verb|normalize(Coloring& c)| \\
ktorá premenuje farby tak, aby z vertexu 0 vychádzali v takomto poradí 
$01$ $10$ $11$.

\smallskip
(Vďaka nej nám napríklad počas testovania stačí vytvoriť jedno farbenie na 
porovnanie pre každých 6, ktoré sa dajú získať jednoduchým premenovaním farieb)





\bigskip
\textbf{Implementačné detaily} 

Sú popísané vždy v zrojovom súbore, zväšča v hlavičke (komente na začiatku zdrojového súboru).





\bigskip
\textbf{Formát farbenia}

Provizórna verzia:

Veľmi sa podobná tzv. `bratislavskému formátu` reprezentácie grafu.

\verb|N|\\
\verb|v_1 col_1 v_2 col_2 v_3 col_3|\\
\verb|v_1 col_1 v_2 col_2 v_3 col_3|\\
\verb|...|\\
\verb|v_1 col_1 v_2 col_2 v_3 col_3|

\smallskip
reprezentuje graf o N vrcholoch, 
kde i-tý riadok reprezentuje i-tý vrchol, tak že:

i-tý vrchol susedí s vrcholom \verb|v_1| a spája ich hrana farby \verb|col_1|
(analogicky pre \verb|v_2, v_3|)

\smallskip
Všimnime si že informácia o farbe hrany je duplikovaná, 
(oba vrcholy si ju pamätajú), 
no ono to nieje príliž veľký problém, a navyše nám to uľahčilo programovanie 
algoritmu generujúceho všetky farbenia.





\bigskip
\textbf{Zdroje:}

%House of Graphs:%
G. Brinkmann, K. Coolsaet, J. Goedgebeur, H. Mélot, House of Graphs: a database of interesting graphs, Discrete Applied Mathematics, 161(1-2):311-314, 2013. Available at http://hog.grinvin.org 

\end{document}
