\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}.





\medskip
Počas \textbf{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}






\medskip
Počas \textbf{letného semestra} sa podarilo:

\begin{enumerate}

\item
 Upraviť dátové struktúry aby boli použiteľné v \verb|std::map|, \verb|std::set|

\item
 Rozšírenie triedy \verb|Coloring| o rôzne druhy prístupu k jej dátam
 (napr: ``akú farbu má hrana medzi`` (u,v)) a tiež o nové konštruktory.

\item 
 Vytvorenie podporných procedúr pre konštrukciu grafu farbení -- \verb|clrhelp_.cpp|

\item
 Vytvorenie triedy reprezentujúcej graf farbení zadaného grafu (alebo multipólu). -- \verb|clrgraph.hpp|

\item
 Finalizácia výstupného formátu pre každú triedu (multipól, farbenie, graf farbení)

\item
 Spustenie algoritmu na veľa malých grafoch a vytvorenie štatistiky 
 -- \verb|run.cpp|, \verb|run.sh|, \verb|parse.sh|, 
    výstup=\verb|output.7z|

 *Program je pripravený na tvorbu grafov farbení pre multipóly. \\
 *Korektnosť bola testovaná iba pre kubické grafy.

\end{enumerate}

















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


\medskip
Náš 
\href{https://bitbucket.org/pegro2/rp_repo/src/master/}{projekt}
je použiteľný ako knižnica pre jazyk C++, alebo hotový program tvoriaci grafy farbení ( \verb|run/run.cpp| )

Na použitie ako knižnice je potrebné naprogamovať si vlastný program využívajúci
naše triedy, a následne použiť všemožné predprogramované metódy tried. 
(napr. print())

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





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


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

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


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

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


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

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

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


\bigskip
\verb|  |
Tvorba Grafu farbení vytvoreného grafu(tvorba multipólov zatiaľ nepodporovaná):

(1) Vytvorte graf/multipól;
(2) Vytvorte graf farbení volaním konštruktora;

\verb|const CubicMultipole m_twistedCube( "GKh]@c" );   //priklad grafu farbeni| \\
\verb|const ColoringGraph clrgraph( m_twistedCube );   // pre tzv. twistedcube|


\bigskip
\verb|run/run.cpp|:

\smallskip
\verb|  |
Predpripravený program (na skompilovanie \verb|make run|)
ktorý zo štandardného vstupu číta grafy v g6-formáte a vypisuje:

Na \verb|stdout| graf farbení
(iba* tvar grafu, nie ktoré farbenie zodpovedá vrcholu)

Na \verb|stderr| trojice 
\verb|<g6string> <počet vrcholov> <počet komponentov súvislosti>| 

*Dá sa zmeniť, zakomentovaním makra v \verb|run.cpp|

\medskip
\verb|run/run.sh| a \verb|run/parse.sh|:

\smallskip
\verb|run/run.sh| spustí paralelne v pozadí 4x \verb|run.out| na grafy v 
\verb|girthX/| pre $X \in \{3,4,5,6\}$

Treba počkať kým napíše na terminál že \verb|"FINISHED graphs/girthX"| pre každý.

Potom spustiť \verb|run/parse.sh| ktorý vytvorí tabuľky.








\bigskip
\textbf{Implementačné detaily} 

Sú popísané v zrojovom súbore pomocou komentárov, zväšča v hlavičke (na začiatku zdrojového súboru).

\smallskip
Za poznámku môže stáť že používame makrá.

\verb|#define DEBUG|
\verb|  |
Zapne veľa interných assert()-ov.

\verb|#define DUMMY_COLORING|\\
Spôsobí sprístupnenie konštruktora triedy \verb|Coloring(ba_literal)|,
ktorý vytvorí coloring BEZ podkladového grafu. Jediné definované použitie
tejto triedy je na operácie \verb| ==,<,[],print()|.
Ostatné je tzv. ``Undefined behaviour`` (spadne so \verb|SIGSEGV|).

















\newpage
\textbf{Formát kubického grafu/multipólu}

Graf: 
g6 formát kubického grafu

Multipól: 
g6 formát grafu so stupňami vrcholov $3$ alebo $1$.
Stupeň vrcholu=3 reprezentuje vrchol multipólu. 
Stupeň vrcholu=1 reprezentuje visiacu hranu.



\bigskip
\textbf{Formát farbenia}

Veľmi sa podobná tzv. `bratislavskému formátu` reprezentácie grafu.
No na ``pochopenie`` je potrebné mať zároveň aj reprezentáciu podkladového grafu/multipólu.


\medskip
Nech máme nasledovné:
\smallskip

\begin{tabular}{l p{0.5\linewidth}}
Farbenie:			&\verb|   |	Graf:			\\
\verb|N|			&\verb|   |	\verb|N|		\\
\verb|col_1 col_2 col_3|	&\verb|   |	\verb|v_1 v_2 v_3|	\\
\verb|col_1 col_2 col_3|	&\verb|   |	\verb|v_1 v_2 v_3|	\\
\verb|...| 			&\verb|   |	\verb|...|		\\
\verb|col_1 col_2 col_3|	&\verb|   |	\verb|v_1 v_2 v_3|
\end{tabular}


\medskip
Potom toto reprezentuje farbenie grafu 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|).
Ak \verb|v_i < 0|, znamená že to je visiaca hrana
//viď. makrá v \verb|types.hpp|

\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{Formát grafu farbení}

Veľmi jednoduchý, nieje nič iné než oddelené výpisy grafov a farbení:

\verb|GRAPH OF COLORINGS|			\\
\verb|#COMPONENTS=1|				\\
<<graf farbení v bratislavskom formáte>>	\\
\verb|END|					\\
\verb|COLORING #0|				\\
<<výpis farbenia vo formáte vyššie popísanom>>	\\
\verb|END|					\\
\vdots						\\
\verb|COLORING #|[N-1]				\\
<<výpis farbenia vo formáte vyššie popísanom>>	\\
\verb|END|					\\
\verb|UNDERLAYING GRAPH|			\\
<<podkladový graf v bratislavskom formáte>>	\\
\verb|END|


\medskip
Kde i-ty vrchol grafu farbení zodpovedá farbeniu \verb|#i|.

Ak žiadne farbenie neexistuje vypíše iba počet komponentov $\leadsto$ \verb|0|

Ak poklad nebol graf ale multipól napíše sa \verb|UNDERLAYING MULTIPOLE|.

















\newpage
\textbf{[Menšia] štatistika}

\verb|  |
Pre všetky grafy získané z ``House of Graphs`` do (vrátane) 20 vrcholov sme spustili náš algoritmus.
Vstup, a výstup je delený do priečinkov 
\verb|girth3,girth4,girth5,girth6|
(očakávateľne podľa toho či obvod-grafu $\ge$ X pre girthX)


\medskip
Pre každý súbor grafov (cub<stupeň>.<obvod>.g6) sme vytvorili 3 výstupné súbory.
(run.sh)

\verb|<stare_meno>.graph|\\
Obsahuje grafy farbení (iba grafy, nie priradenia vrchol$\leftrightarrow$farbenie)


\smallskip
\verb|<stare_meno>.stats|\\
Obsahuje trojice:
\verb|<g6string> <počet vrcholov> <počet komponentov súvislosti>|


\smallskip
\verb|<stare_meno>.summary|\\
Trojice:
\verb|<počet grafov ktoré majú> <N vrcholov> <K komponentov súvislosti>|

\bigskip
Potom sme pre každú skupinu grafov (\verb|girth3,...,girth6|) vytvorili štatistiku(parse.sh).

\smallskip
\verb|summary.order.csv|\\
CSV (Comma separated values) súbor obsahujúci počty grafov ktoré mali práve N vrcholov(farbení) kde N je číslo v hlavičke daného stĺpca.

\smallskip
\verb|summary.no_components.csv|\\
Obdobne ako pri \verb|summary.order.csv|, len s počtami komponentov súvislosti.


\bigskip
Toto všetko sme skomprimovali do \verb|output.7z|. \\
*Veľkosť je 92MB ale odkomprimované to je 882MB 

\smallskip
Preto zmenšená verzia (bez grafov, iba štatistiky) je skompromovaná v \verb|stats.7z| \\
*Veľkosť 2.3MB odkomprimovaná 24.7MB


\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}
