<commit_before>% Created 2013-11-12 Tue 20:00
\documentclass[12pt, a4paper]{article}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage[polish]{babel} 
\usepackage{geometry}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage[numbers]{natbib}
\usepackage{algorithm}
\usepackage{algpseudocode}
\author{<NAME>, <NAME>}
\date{}
\title{Porównanie algorytmów znajdowania maksymalnej kliki w grafie}
\begin{document}

\maketitle

\section{Problem maksymalnej kliki}
\label{sec-1}
Kliką nazywamy spójny podgraf, taki że nie jest on zawarty w żadnym innym spójnym podgrafie. Maksymalna klika to klika składająca się z największej liczby wierzchołków. Problem znajdowania maksymalnej kliki w grafie jest problemem NP-zupełnym.

\section{Algorytm}
\label{sec-2}
Do zaimplementowania został wybrany algorytm \ref{basicmc} przechodzący graf w głąb i używający techniki branch-and-bound w celu znalezienia maksymalnej kliki. Algorytm został opisany w \citep{bioinf} (Fig. 2). Zostanie on porównany z dostępną implementacją algorytmu Brona-Kerboscha w bibliotece JGraphT\citep{jgrapht}.

\subsection{Struktury danych}

W algorytmie \ref{basicmc} wykorzystywane są zbiory $Q$ i $Q_{max}$. $Q$ przechowuje wierzchołki aktualnie rozpatrywanej kliki. $Q_{max}$ zawiera wierzchołki największej kliki jaką dotąd udało się znaleźć. $R \subseteq V $ zawiera listę wierzchołków które mogą zostać dodane do $Q$.

\subsection{Opis Algorytmu}

Początkowo $Q := \emptyset, Q_{max} := \emptyset, R := V$. Wybieramy wierzchołek $p$ z dostępnych wierzchołków w $R$ i dodajemy go do $Q$ \algref{basicmc}{addPToQ}. Następnie obliczamy $R_{p} := R \cap \text{adj(}p\text{)}$ który staje się nowym zbiorem wierzchołków do przejrzenia. Procedura EXPAND() jest wywoływana rekursywnie do wyczerpania zbioru wierzchołków $R_{p}$. Jeśli $|Q|+|R| \leq |Q_{max}|$ to $Q \cup R$ może zawierać jedynie klikę niewiększą od $|Q_{max}|$, w tym przypadku algorytm pomija zbędne obliczenia.\algref{basicmc}{skip}

\subsection{Warunek Stopu}

W momencie osiągnięcia $R_{p} = \emptyset$, Zbiór $Q$ jest maksymalną kliką. Jeśli $|Q| > |Q_{max}|$ zbiór $Q$ zastępuje zbiór $Q_{max}$. Po usunięciu wierzchołka początkowego $p$ z $Q$ i $R$ wybieramy go z wierzchołków pozostałych w $R$ i powtarzamy do przejrzenia wszystkich wierzchołków ($R = \emptyset$)

\subsection{Złożoność Obliczeniowa}
W grafie o $n$ wierzchołkach może być nie więcej niż $3^{\frac{n}{3}}$ maksymalnych klik. Złożoność obliczeniowa algorytmu Brona-Kerboscha wynosi $O(3^{\frac{n}{3}})$.
Jest to także dolne ograniczenie dla złożoności obliczeniowej implementowanego algorytmu. Faktyczne zachowanie algorytmu w zależności od rozmiaru grafu wejściowego zostanie wyznaczone empirycznie.

\subsection{Złożoność pamięciowa}
\label{memory_complexity}

Złożoność pamięciowa implementowanego algorytmu to $O(|V|)$. Ilość pamięci potrzebnej jest wprost proporcjonalna do liczby wierzchołków grafu. Wynika to bezpośrednio z definicji i sposobu użycia zbiorów $Q$, $Q_{max}$ i $R$.

\begin{algorithm}
\caption{BasicMC}\label{basicmc}
\begin{algorithmic}[1]
  
\Procedure{BasicMC}{$V,E$}
\State $Q\gets \emptyset$;
\State $Q_{max}\gets \emptyset$;
\State \Call{EXPAND}{V};
\EndProcedure
\Statex

\Procedure{expand}{$R$}
\While{$R \not= \emptyset$}
  \State $p\gets v\in R$
  \If{$|Q|+|R| > |Q_{max}|$}
    \State $Q \gets Q \cup {p}$\label{addPToQ}
    \State $R_p \gets R \cap adj(p)$
    \If{$R_p \not= \emptyset$}
      \State \Call{EXPAND}{$R_{P}$}
    \ElsIf{$|Q| > |Q_{max}|$}
      \State $Q_{max} \gets Q$
    \EndIf
    \State $Q \gets Q - {p}$
  \Else
    \textbf{ return}\label{skip}
  \EndIf
  \State $R \gets R - p$
\EndWhile
\EndProcedure

\end{algorithmic}
\end{algorithm}

\section{Program}
\label{sec-3}
Program zostanie zaimplementowany w języku Scala. Jest to statycznie typowany język działający na JVM, w pełni kompatybilny z językiem Java.

Program będzie plikiem wykonywalnym wczytującym reprezentację grafu ze standardowego wejścia i wypisującym żądane informacje na standardowe wyjście.

\subsection{Wejście Programu}

Wejściem programu są pliki tekstowe ASCII. Wejście zawiera $|E|+1$ linii nie licząc linii zawierających komentarzy. Pierwsza linijka nie będąca komentarzem jest postaci 
\begin{verbatim}
p col |V| |E|
\end{verbatim}
Gdzie $|V|$ i $|E|$ to odpowiednio liczba węzłów i krawędzi grafu. Następne $|E|$ linijek odpowiada $|E|$ krawędziom grafu. Krawędź $(v, w)$ zapisywana jest jako 
\begin{verbatim}
e W V
\end{verbatim}
i występuje tylko raz. Krawędź $(w, v)$ stanowi części reprezentacji tekstowej grafu. Opisany format jest podzbiorem formatu DIMACS opisanego w \cite{dimacs_format}

\subsection{Opcje Programu}

\subsubsection{Wybór algorytmu}
Program będzie posiadał opcję, która pozwala zmienić algorytm wyszukiwania największej kliki w celu porównania obu algorytmów.

\begin{verbatim}
-j użyj gotowego algorytmu biblioteki JGraph
\end{verbatim}
Przykładowe wywołanie programu:

\begin{verbatim}
./prog < input.txt >> results.txt
./prog -max 600 < input.txt >> results.txt
./prog -j < input.txt >> results.txt
\end{verbatim}

\subsubsection{Ograniczenie czasowe}
Program będzie posiadał opcję, która pozwala określić maksymalny czas działania algorytmu.

\begin{verbatim}
-max N maksymalna liczba sekund na działanie algorytmu
\end{verbatim}
Przykładowe wywołanie programu:

\begin{verbatim}
./prog -max 600 < input.txt >> results.txt
\end{verbatim}

\subsubsection{Ograniczenia na pamięć}
Ograniczenia na pamięć można ustawić z poziomu maszyny wirtualnej Javy korzystając z parametru $-Xmx$

\subsection{Wyjście Programu}

Wyjście programu jest postaci.

\begin{verbatim}
w(g) TIME
\end{verbatim}
Gdzie $\omega(g)$ to rozmiar największej znalezionej kliki a $\text{TIME}$ - czas wykonania algorytmu.

\subsection{Sytuacje awaryjne}
Możliwe sytuacje awaryjne to:

\begin{itemize}
\item zły format wejścia - program będzie zgłaszał błąd, w przypadku wykrycia niewłaściwego formatu wejściowego
\item brak pamięci - błąd obsługiwany przez JVM
\end{itemize}

\section{Projekt testów}
\label{sec-4}

\subsection{Projekt Testów}
Projekt testów został podzielony na 3 części, każda odpowiedzialna za inny aspekt programu.

\subsection{Testy funkcjonane}
Mają na celu pokazanie, że zaimplementowany algorytm jak i reszta aplikacji pozbawiona jest błędów. W ramach tych testów przetestowane zostaną przypadki:

\begin{itemize}
\item grafu pustego z różną liczbą wierzchołków - maksymalna klika powinna wynosić $1$
\item grafu pełnego $K_{n}$ - maksymalna klika wynosi $n$
\item grafu niespójnego zawierającego podgrafy $K_{n_{1}}$ $K_{n_{2}}$ - maksymalna klika wynosi $max(n_{1}, n_{2})$
\item grafu, które jest drzewem - maksymalna klika powinna wynosić $2$
\item kół $W_{n}$ - maksymalna klika powinna wynosić $3$
\end{itemize}

Dla pozostałej części programu - obsługi wejścia, wyjścia, opcji i innych - zostaną wykonane odpowiednie testy.

\subsection{Testy złożoności}
\subsubsection{Złożoność pamięciowa}
Złożoność pamięciowa zostanie ustalona empirycznie na podstawie pomiarów pamięci zużytej przez program dla grafów o różnej wielkości. Oczekiwana złożoność pamięciowa programu to $O(|V|)$ (\ref{memory_complexity}). 

\subsubsection{Złożoność obliczeniowa}
W celu sprawdzenia, że przewidywana złożoność obliczeniowa jest wartością prawdziwą, zostaną wygenerowne grafy losowe z coraz większą liczbą wierzchołków. Następnie program zostanie uruchomiony dla tych grafów. Zebrane wyniki poddane zostaną analizie statystycznej, która pozwoli określić czy wartości empiryczne zgadzają się z planowaną złożonością.

\subsection{Testy porównawcze}
W celu empirycznego porównania wydajności algorytmów zostanie użyty DIMACS Benchmark Set\citep{dimacs}. Jest to zbiór nietrywialnych grafów dla których znana jest liczba wierzchołków tworzących maksymalną klikę w grafie.


\nocite{*}
\bibliographystyle{plainnat}
\bibliography{bibliography}
\end{document}<commit_msg>Testing time complexity<commit_after>% Created 2013-11-12 Tue 20:00
\documentclass[12pt, a4paper]{article}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage[polish]{babel} 
\usepackage{geometry}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage[numbers]{natbib}
\usepackage{algorithm}
\usepackage{algpseudocode}
\author{<NAME>, <NAME>}
\date{}
\title{Porównanie algorytmów znajdowania maksymalnej kliki w grafie}
\begin{document}

\maketitle

\section{Problem maksymalnej kliki}
\label{sec-1}
Kliką nazywamy spójny podgraf, taki że nie jest on zawarty w żadnym innym spójnym podgrafie. Maksymalna klika to klika składająca się z największej liczby wierzchołków. Problem znajdowania maksymalnej kliki w grafie jest problemem NP-zupełnym.

\section{Algorytm}
\label{sec-2}
Do zaimplementowania został wybrany algorytm \ref{basicmc} przechodzący graf w głąb i używający techniki branch-and-bound w celu znalezienia maksymalnej kliki. Algorytm został opisany w \citep{bioinf} (Fig. 2). Zostanie on porównany z dostępną implementacją algorytmu Brona-Kerboscha w bibliotece JGraphT\citep{jgrapht}.

\subsection{Struktury danych}

W algorytmie \ref{basicmc} wykorzystywane są zbiory $Q$ i $Q_{max}$. $Q$ przechowuje wierzchołki aktualnie rozpatrywanej kliki. $Q_{max}$ zawiera wierzchołki największej kliki jaką dotąd udało się znaleźć. $R \subseteq V $ zawiera listę wierzchołków które mogą zostać dodane do $Q$.

\subsection{Opis Algorytmu}

Początkowo $Q := \emptyset, Q_{max} := \emptyset, R := V$. Wybieramy wierzchołek $p$ z dostępnych wierzchołków w $R$ i dodajemy go do $Q$ \algref{basicmc}{addPToQ}. Następnie obliczamy $R_{p} := R \cap \text{adj(}p\text{)}$ który staje się nowym zbiorem wierzchołków do przejrzenia. Procedura EXPAND() jest wywoływana rekursywnie do wyczerpania zbioru wierzchołków $R_{p}$. Jeśli $|Q|+|R| \leq |Q_{max}|$ to $Q \cup R$ może zawierać jedynie klikę niewiększą od $|Q_{max}|$, w tym przypadku algorytm pomija zbędne obliczenia.\algref{basicmc}{skip}

\subsection{Warunek Stopu}

W momencie osiągnięcia $R_{p} = \emptyset$, Zbiór $Q$ jest maksymalną kliką. Jeśli $|Q| > |Q_{max}|$ zbiór $Q$ zastępuje zbiór $Q_{max}$. Po usunięciu wierzchołka początkowego $p$ z $Q$ i $R$ wybieramy go z wierzchołków pozostałych w $R$ i powtarzamy do przejrzenia wszystkich wierzchołków ($R = \emptyset$)

\subsection{Złożoność Obliczeniowa}
W grafie o $n$ wierzchołkach może być nie więcej niż $3^{\frac{n}{3}}$ maksymalnych klik. Złożoność obliczeniowa algorytmu Brona-Kerboscha wynosi $O(3^{\frac{n}{3}})$.
Jest to także dolne ograniczenie dla złożoności obliczeniowej implementowanego algorytmu. Faktyczne zachowanie algorytmu w zależności od rozmiaru grafu wejściowego zostanie wyznaczone empirycznie.

\subsection{Złożoność pamięciowa}
\label{memory_complexity}

Złożoność pamięciowa implementowanego algorytmu to $O(|V|)$. Ilość pamięci potrzebnej jest wprost proporcjonalna do liczby wierzchołków grafu. Wynika to bezpośrednio z definicji i sposobu użycia zbiorów $Q$, $Q_{max}$ i $R$.

\begin{algorithm}
\caption{BasicMC}\label{basicmc}
\begin{algorithmic}[1]
  
\Procedure{BasicMC}{$V,E$}
\State $Q\gets \emptyset$;
\State $Q_{max}\gets \emptyset$;
\State \Call{EXPAND}{V};
\EndProcedure
\Statex

\Procedure{expand}{$R$}
\While{$R \not= \emptyset$}
  \State $p\gets v\in R$
  \If{$|Q|+|R| > |Q_{max}|$}
    \State $Q \gets Q \cup {p}$\label{addPToQ}
    \State $R_p \gets R \cap adj(p)$
    \If{$R_p \not= \emptyset$}
      \State \Call{EXPAND}{$R_{P}$}
    \ElsIf{$|Q| > |Q_{max}|$}
      \State $Q_{max} \gets Q$
    \EndIf
    \State $Q \gets Q - {p}$
  \Else
    \textbf{ return}\label{skip}
  \EndIf
  \State $R \gets R - p$
\EndWhile
\EndProcedure

\end{algorithmic}
\end{algorithm}

\section{Program}
\label{sec-3}
Program zostanie zaimplementowany w języku Scala. Jest to statycznie typowany język działający na JVM, w pełni kompatybilny z językiem Java.

Program będzie plikiem wykonywalnym wczytującym reprezentację grafu ze standardowego wejścia i wypisującym żądane informacje na standardowe wyjście.

\subsection{Wejście Programu}

Wejściem programu są pliki tekstowe ASCII. Wejście zawiera $|E|+1$ linii nie licząc linii zawierających komentarzy. Pierwsza linijka nie będąca komentarzem jest postaci 
\begin{verbatim}
p col |V| |E|
\end{verbatim}
Gdzie $|V|$ i $|E|$ to odpowiednio liczba węzłów i krawędzi grafu. Następne $|E|$ linijek odpowiada $|E|$ krawędziom grafu. Krawędź $(v, w)$ zapisywana jest jako 
\begin{verbatim}
e W V
\end{verbatim}
i występuje tylko raz. Krawędź $(w, v)$ stanowi części reprezentacji tekstowej grafu. Opisany format jest podzbiorem formatu DIMACS opisanego w \cite{dimacs_format}

\subsection{Opcje Programu}

\subsubsection{Wybór algorytmu}
Program będzie posiadał opcję, która pozwala zmienić algorytm wyszukiwania największej kliki w celu porównania obu algorytmów.

\begin{verbatim}
-j użyj gotowego algorytmu biblioteki JGraph
\end{verbatim}
Przykładowe wywołanie programu:

\begin{verbatim}
./prog < input.txt >> results.txt
./prog -max 600 < input.txt >> results.txt
./prog -j < input.txt >> results.txt
\end{verbatim}

\subsubsection{Ograniczenie czasowe}
Program będzie posiadał opcję, która pozwala określić maksymalny czas działania algorytmu.

\begin{verbatim}
-max N maksymalna liczba sekund na działanie algorytmu
\end{verbatim}
Przykładowe wywołanie programu:

\begin{verbatim}
./prog -max 600 < input.txt >> results.txt
\end{verbatim}

\subsubsection{Ograniczenia na pamięć}
Ograniczenia na pamięć można ustawić z poziomu maszyny wirtualnej Javy korzystając z parametru $-Xmx$

\subsection{Wyjście Programu}

Wyjście programu jest postaci.

\begin{verbatim}
w(g) TIME
\end{verbatim}
Gdzie $\omega(g)$ to rozmiar największej znalezionej kliki a $\text{TIME}$ - czas wykonania algorytmu.

\subsection{Sytuacje awaryjne}
Możliwe sytuacje awaryjne to:

\begin{itemize}
\item zły format wejścia - program będzie zgłaszał błąd, w przypadku wykrycia niewłaściwego formatu wejściowego
\item brak pamięci - błąd obsługiwany przez JVM
\end{itemize}

\section{Projekt testów}
\label{sec-4}

\subsection{Projekt Testów}
Projekt testów został podzielony na 3 części, każda odpowiedzialna za inny aspekt programu.

\subsection{Testy funkcjonane}
Mają na celu pokazanie, że zaimplementowany algorytm jak i reszta aplikacji pozbawiona jest błędów. W ramach tych testów przetestowane zostaną przypadki:

\begin{itemize}
\item grafu pustego z różną liczbą wierzchołków - maksymalna klika powinna wynosić $1$
\item grafu pełnego $K_{n}$ - maksymalna klika wynosi $n$
\item grafu niespójnego zawierającego podgrafy $K_{n_{1}}$ $K_{n_{2}}$ - maksymalna klika wynosi $max(n_{1}, n_{2})$
\item grafu, które jest drzewem - maksymalna klika powinna wynosić $2$
\item kół $W_{n}$ - maksymalna klika powinna wynosić $3$
\end{itemize}

Dla pozostałej części programu - obsługi wejścia, wyjścia, opcji i innych - zostaną wykonane odpowiednie testy.

\subsection{Testy złożoności}
\subsubsection{Złożoność pamięciowa}
Złożoność pamięciowa zostanie ustalona empirycznie na podstawie pomiarów pamięci zużytej przez program dla grafów o różnej wielkości. Oczekiwana złożoność pamięciowa programu to $O(|V|)$ (\ref{memory_complexity}). 

\subsubsection{Złożoność obliczeniowa}
Testy mają na celu empiryczne zmierzenie złożoności obliczeniowej. W tym celu zostaną wygenerowane grafy losowe z różnym prawdopodobieństwem krawędzi i różną liczbą wierzchołków. Dla każdego z wygenerowanych grafów uruchomiony zostanie algorytm. Zebrane wyniki poddane zostaną analizie statystycznej, która pozwoli określić złożoność obliczeniową.

\subsection{Testy porównawcze}
W celu empirycznego porównania wydajności algorytmów zostanie użyty DIMACS Benchmark Set\citep{dimacs}. Jest to zbiór nietrywialnych grafów dla których znana jest liczba wierzchołków tworzących maksymalną klikę w grafie.


\nocite{*}
\bibliographystyle{plainnat}
\bibliography{bibliography}
\end{document}
{'fraction_non_alphanumeric': 0.09869458283407959, 'fraction_numerical': 0.005171217758718547, 'mean_word_length': 5.376357056694813, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '44870', 'n_tokens_mistral': 6637, 'n_tokens_neox': 6874, 'n_words': 1752}