\lstdefinelanguage{dot}
{keywords={node,edge,digraph,->},
sensitive=false,
morecomment=[l]{//},
morecomment=[s]{/*}{*/},
morestring=[b]",
}

\lstset{
    language=dot,
    frame=,
    framesep=8pt,
    backgroundcolor=\color{VeryLightGray},
    basicstyle=\small,
    keywordstyle=\rmfamily\color{DarkGray}\bfseries,
    identifierstyle=\rmfamily \color{RealGray},
    commentstyle=\rmfamily\color{LightGray}\itshape,
    stringstyle=\rmfamily\color{RealGray}\itshape,
    showstringspaces=false,
    escapechar=\#
}

\chapter{Vizualizace MBD}
\label{kap_vizualizace}
Tato část práce vznikla jako vedlejší produkt celého projektu.
Nicméně by byla škoda, kdyby zde nebyla o této záležitosti žádná zmínka.\\

\noindent V průběhu práce vyvstala potřeba načtený MBD vizualizovat. Důvodu
bylo několik, ale tím hlavním bylo ověření, že celý systém pracuje, jak má -
tj. že načítání MBD a operace nad ním fungují správně. Na první pohled nejde o
nijak triviální úkol, a tak možnost, že by se obrázky grafu generovaly přímo z
MBD, nepřicházela v úvahu. Bylo tedy nutné najít nějaký metaformát, do kterého
by se vnitřní struktura MBD uložila a tu by pak převedl do vizuální
podoby\footnote{obrázek typu PNG či SVG} specializovaný program. Tím
metaformátem se stal programovací jazyk \emph{DOT} a vizualizačním programem
\emph{Graphviz} \cite{grpvz}. Následují řádky jsou lehkým manuálem k programu
Graphviz a~k~jazyku DOT. Nakonec je určitě vhodné připomenout, že
\emph{všechny} obrázky MBD v této práci byly vytvořeny pomocí jazyku DOT a
balíku Graphviz.

\section{Jazyk DOT}
Jazyk \emph{DOT} je určen přímo na popis grafů, a proto se s ním velmi snadno a
příjemně pracuje. Příklad jednoduchého grafu je na obrázku \ref{dot_example}.\\
\indent Podobně jako v jazyce C se i v DOTu používají složené závorky (\uv{\{}
a \uv{\}}) na uzavření určitého bloku příkazů či deklarací. Z obrázku
\ref{dot_example} je patrné jejich použití: celý graf
MBD je uzavřen do bloku, stejně jako několik dalších položek.\\
\indent V definici grafu se používají pouze dva elementy - uzly a hrany. Uzel
se definuje tak, že se napíše jeho identifikátor\footnote{musí být unikátní} a
za něj se vloží středník.
\smallskip
\begin{lstlisting}
        uzel1;
\end{lstlisting}
\smallskip
Jedním příkazem je možné deklarovat i více uzlů najednou. Mezi jednotlivé
identifikátory se vkládá mezera.
\smallskip
\begin{lstlisting}
        uzel1 uzel2 uzel3 uzel4;
\end{lstlisting}
\smallskip
Hrana se definuje tak, že se napíší identifikátory uzlů a mezi ně se vloží
klíčové slovo pro hranu \uv{->} a za celou tuto sekvenci se opět vloží středník.
\smallskip
\begin{lstlisting}
        uzel1 -> uzel1;
\end{lstlisting}
\smallskip
Kromě uzlů a hran lze nastavit i různé vlastnosti jak jednotlivých elementů
grafu, tak i grafu samotného. Jako úvod do programování v jazyce DOT těchto pár
řádek jistě stačí. Pro úplné pochopení následuje seznam důležitých klíčových
slov a jejich popis.

\bfig
\begin{multicols}{2}{
~\\
~\\
~\\
~\\
~\\
~\\
\includegraphics[width=4.5cm]{img/dot-example.png}\\
\pagebreak
\begin{lstlisting}
digraph BDD
{
size="7,11"

node [fontname="Helvetica",
     fontsize="20", height="0.3",
     width="0.6", color=black,
     style=unfilled, shape=box];

    { rank=same;
        uzel1 [label="1"];
        uzel2 [label="0"]; }

node [fontname="Helvetica",
     fontsize="20", height="0.3",
     width="0.5", style=unfilled,
     color=black, shape=circle];

    { rank=same;
        uzel3 [label="x0"]; }

    { rank=same;
        uzel4 [label="x1"];
        uzel5 [label="x1"]; }

    { rank=same;
        uzel6 [label="x2"]; }

edge [arrowsize="1.0"];
    uzel3 -> uzel5 [style=dotted];
    uzel3 -> uzel4 [style=solid];
    uzel4 -> uzel6 [style=dotted];
    uzel4 -> uzel2 [style=solid];
    uzel5 -> uzel2 [style=dotted];
    uzel5 -> uzel6 [style=solid];
    uzel6 -> uzel1 [style=dotted];
    uzel6 -> uzel2 [style=solid];
}
\end{lstlisting}
}\end{multicols}%
\caption[MBD a jeho popis pomocí jazyka DOT] { \textbf{MBD a jeho popis pomocí
jazyka DOT.}} \label{dot_example} \efig

\paragraph{digraph} Označuje blok, v němž deklarované
uzly a hrany spadají do jednoho grafu. Předpona \uv{di} říká, že jde o
orientovaný (anglicky \emph{di}rected) graf. Je možné použít i klíčové slovo
\textbf{graph}, což označuje graf neorientovaný. Jelikož MBD je orientovaný
graf, je pro jeho správné zobrazení třeba použít příkaz \textbf{digraph}.

\paragraph{size} Nejde o klíčové slovo, ale o atribut bloku s grafem.
Udává maximální šířku a výšku výsledného obrázku v palcích.

\paragraph{node} Pomocí tohoto klíčového slova se přednastavují
atributy všech uzlů. Atributy se vkládají do hranatých závorek hned za klíčové
slovo. Všechny uzly uvedené po tomto klíčovém slovu mají atributy těchto
hodnot. Atributy lze změnit novou sekvencí node nebo za každým
uzlem uvést je vlastní atributy.\\
\indent Atributy uzlů určují jeho velikost, tvar, barvu nebo
nadpis\footnote{všech atributů je samozřejmě mnohem více}. Z obrázku
\ref{dot_example} je patrné, že každému uzlu je přiřazen jeho vlastní název
(label), a zároveň je možné si všimnout, jak se pomocí druhého příkazu mění
atributy pro vnitřní uzly MBD \footnote{První příkaz \textbf{node} stanovuje
atributy terminálních uzlů.}.

\paragraph{rank} Jedná se o atribut bloku, ve kterém je vložen. Určuje
způsob, jakým budou zobrazeny uzly v daném bloku. Hodnota \uv{same} říká, že
všechny uzly v bloku mají být zobrazeny ve stejné vertikální hladině (stejně
vysoko). Jen díky tomuto příkazu je možné nakreslit MBD tak, že uzly patřící
stejným proměnným jsou na stejné úrovni. Místo \uv{same} je možné například
použít \uv{min} - uzly v bloku by pak byly umístěny na co nejnižší úroveň.

\paragraph{edge} Tento příkaz je obdobou příkazu node pro hrany. Pro všechny
hrany deklarované po něm přednastavuje jejich parametry. Ty lze opět změnit
nebo doplnit pomocí atributů vložených za deklaraci každé hrany. Jediný atribut
v příkazu na obrázku \ref{dot_example} je \emph{arrowsize}, který určuje
velikost šipky na konci každé hrany. Zároveň je možné u každé hrany explicitně
určit, jaký má styl - \emph{tečkované} (dotted) pro záporné hrany a \emph{plné}
(solid) pro kladné hrany. Určitě je vhodné zde zmínit, že i hrany mohou mít
svůj název, čehož na vizualizaci MBD využito nebylo.

\section{Graphviz}
Graphviz je program nebo lépe řečeno sada programů, jejichž vývoj
podporují laboratoře firmy AT\&T\footnote{velká telekomunikační firma z USA}.
Jde o bezplatný software, který je možno dostat jak v podobě binárních
souborů pro platformu Windows, Linux a MacOS, tak i jako zdrojové soubory
jazyka C++.\\
\indent Použití toho programu je veskrze jednoduché. Na příkazový řádek se zadá
program, který se má spustit, název vstupního a výstupního souboru a typ
výstupního souboru. Nejsložitějším úkonem je zde výběr programu, který má
vstupní DOT soubor zpracovat. Graphviz nabízí celkem čtyři různé aplikace, z
nichž každá má jiný účel (všechny však mění grafy specifikované ve vstupních
souborech na grafické formáty souborů výstupních).\\

\newpage%
\noindent Programy Graphvizu jsou:
\begin{itemize}
    \item \textbf{dot}: Vytváří hierarchické orientované grafy.
    \item \textbf{neato}: Vytváří neorientované grafy.
    \item \textbf{twopi}: Vytváří radiální grafy (se středem).
    \item \textbf{circo}: Vytváří cyklické grafy.
\end{itemize}

\noindent Pro potřeby vizualizace MBD je vhodný jedině program \textbf{dot}.
Proto by příkazový řádek vypadal takto:
\smallskip
\begin{lstlisting}
    c:\dot -Tsvg -ooutputfile.svg inputfile.dot
\end{lstlisting}
\smallskip

\noindent Parametrem \uv{-T} se specifikuje formát výstupního
souboru\footnote{v případě příkladu je použit formát SVG - Scalable Vector
Graphics}. Graphviz podporuje okolo třiceti různých formátů, mezi nimiž nechybí
důležité bitmapové formáty jako \emph{jpg} nebo \emph{png} nebo vektorové
formáty jako \emph{svg} či \emph{ps}.

\section{Nic není dokonalé}%
Graphviz je bezpochyby vynikají praktická pomůcka, ovšem ani těm nejlepším se
nevyhnou menší problémy či nedotaženosti. Graphviz má poměrně velké problémy s
vytvářením bitmapových formátů. Soubory PNG či JPG jdou jedním slovem popsat
jako \uv{ošklivé}. Naštěstí program podporuje i vektorové formáty jako SVG, ze
kterých je možné pěkné bitmapové soubory vytvořit pomocí některého z
nespočetných vektorových editorů jako \emph{Inscape} či \emph{Adobe
Illustrator} nebo pomocí grafických konvertorů jako \emph{Batik}\footnote{možná
nejlepší konvertor z SVG na PNG}.\\
\indent Určitě závažnější komplikací je špatná podpora formátování textu
jazykem DOT. Jak je možné si všimnout ze všech obrázků MBD v této práci,
všechna jména uzlů jsou tvořena znakem \uv{x} a číselným dolním indexem (např.
$x_4$). Dolní indexy však DOT nepodporuje \footnote{DOT nepodporuje ani jiné
druhy formátování textu.}. MBD na obrázku \ref{dot_example} je přímým výstupem
z formátu DOT (DOT$\rightarrow$SVG$\rightarrow$PNG). Do ostatních MBD bylo
složitější formátování textu doplněno až díky speciálnímu filtru.

%\newpage
\section{Jiné způsoby vizualizace}
Pochopitelně, že ukládání MBD do souboru typu DOT a jeho převod pomocí Graphviz
není jediným způsobem, jak vytvořit grafické znázornění jeho vnitřní struktury.
Nicméně je to cesta nejschůdnější a nejsnáze aplikovatelná.\\
\indent Jiným přístupem je generování obrázků grafů přímo z programu. Například
samotný Graphviz nabízí C++ knihovnu, kterou je možné použít ve vlastním programu.
Vedle Graphvizu má podobné schopnosti i knihovna BGL \cite{boost} (Boost Graphic Library),
vyvíjená skupinou nadšenců.\\
\indent Pro úplnost je nutné připomenout, že vizualizovat MBD je možné i
manuálně pomocí nějakého softwaru na kreslení diagramů jako je Visio, SmartDraw
a řady dalších. Ovšem nakreslit s těmito nástroji graf s více jak dvaceti uzly
je poměrně pracné.
