**********************************************
*	Marcin Szulc                         *
*	nr indeksu: 277342                   *
*	email: mszulc2@mion.elka.pw.edu.pl   *
**********************************************

K- domknięcie grafu

##############################################

Problem:
Znalezienie takiego podzbioru wierzcholków grafu skierowanego G, z którego nie
wychodzą żadne krawędzie poza ten podzbiór.

##############################################

Uruchomianie programu:

---------------------
Tryb wczytywania z pliku:
---------------------
python3 closure.py -m 1 -k 6 -c bf < infile.txt > outfile.txt
gdzie:
	-m -> tryb
	-k -> wielkość domknięcia (domyślnie- maksymalne)
	-c -> wybrany algorytm (patrz niżej)

Dane wejściowe jako macierz sąsiedztwa, wierzchołki oddzielone spacjami, wiersze to nowe linie, np:

marcin@marcin-Lenovo-Y50-70:~/git/k-closure$ cat test.txt
0 0 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
marcin@marcin-Lenovo-Y50-70:~/git/k-closure$

Prezentacja wyników:
Wejściowa macierz sąsiedztwa + tabela z wynikiem, tzn: użyty algorytm, znalezione domknięcie, czas + graficzne przedstawienie znalezionego domknięcia

---------------------
Tryb generowania z parametryzacją
---------------------
python3 closure.py -m 2 -c bf -v 10 -e 20 -k 5
gdzie:
	-m -> tryb
	-k -> wielkość domknięcia (domyślnie- maksymalne)
	-c -> wybrany algorytm (patrz niżej)
	-v -> ilość wierzchołków generowanego grafu
	-e -> ilość krawędzi generowanego grafu

Prezentacja wyników:
Wejściowa macierz sąsiedztwa + tabela z wynikiem, tzn: użyty algorytm, znalezione domknięcie, czas + graficzne przedstawienie znalezionego domknięcia


---------------------
Tryb generowania z parametryzacją (zawsze szukamy największego domknięcia)
---------------------
python3 closure.py -m 3 -v 10 -step 5 -er 1 -r 1 -steps 40 -c h1

gdzie:
	-m -> tryb
	-c -> wybrany algorytm (patrz niżej)
	-v -> ilość wierzchołków startowych
	-step -> wielkość kroku
	-steps -> ilość kroków
	-r -> liczba pomiarów dla danego n
	-er -> wartość 0.0-1.0 określająca współczynnik "wypełnienia" krawędzi (0 - brak krawędzi, 1 - graf pełny)

Prezentacja wyników:
Tabela (generowana "online") z wynikami:
n, czas zmierzony t(n) w sekundach, złożoność T(n), współczynnik q(n)

---------------------
Tryb porównania algorytmów
---------------------
python3 closure.py -m 4 -v 20 -e 50 -k 5

gdzie:
	-m -> tryb
	-v -> ilość wierzchołków generowanego grafu
	-e -> ilość krawędzi generowanego grafu
	-k -> wielkość domknięcia (domyślnie- maksymalne)

Prezentacja wyników:
Tabela z wynikami:
algorytm, znalezione domknięcie, czas w sekundach, dokładność rozwiązania (porównanie z rozwiązaniem brutalnym)

##############################################

Struktury danych:
klasa Graph: obudowana macierz sąsiedztwa (lista list)

Opis użytych algorytmów:

----------------------
bf - metoda brutalna, sprawdza wszystkie możliwe kombinacje wierzchołków, jeśli nie znajdzie dla danego k- zmniejsza k
----------------------
h1 - metoda heurystyczna, wywoluje sie rekurencyjnie na każdym dziecku danego wierzchołka i dodaje je do aktualnego domnięcia
----------------------
h2 - metoda heurystyczna (dokładna dla grafów bez cykli), dla każdego wierzchołka grafu tworzymy listę (docelowe domknięcie),
	w której na początku jest tylko ten wierzchołek. Sprawdzamy każdy inny wierzchołek grafu, dodajemy go do domknięcia
	jeśli nie wychodzą z niego żadne krawędzie lub wychodzą krawędzie do wierzchołów znajdujących
	się w domknięciu. Jeśli w danym obrocie pętli dodaliśmy jakiś wierzchołek, procedurę powtarzamy.
	Gdy nie dodano żadnego wierzchołka domknięcie zapisujemy i tworzymy nowe domknięcie
	startując od kolejnego wierzchołka.
	Finalnie wybieramy największe domknięcie.
----------------------
random - dla każdego i od k do 0 losujemy 10*|V| razy i wierzchołków i sprawdzamy czy tworzą one domknięcie

Pliki źródłowe:
wszystkie użyte funkcje w pliku closure.py

##############################################

Informacje dodatkowe:
- metoda bf działa długie sekundy juz od n > 25
- metoda h2 ma niską dokładność
- generator w trybach m2, m3, m4 losuje wybraną liczbę krawędzi z wszystkich potencjalnych; jeśli jest to tryb m3,
	liczba krawędzi jest zaokrągleniem er * |V| * (|V| - 1)