---
title: 'Algorytmy i struktury danych II - projekt'
disqus: hackmd

---

# Algorytmy i struktury danych II - projekt

## Spis treści

[TOC]

## Skład grupy

1. Dominik Dylewski :pouting_cat:
2. Paweł Charysz :scream_cat:
3. Natalia Rutkowska :smile_cat:
4. Urszula Wróblewska :cat:

## Uruchamianie programu

Do uruchomienia programu potrzebujemy komputera z systemem operacyjnym Windows oraz zainstalowaną biblioteką [graphviz](https://graphviz.org/documentation/).

# Dokumentacja

### Klasa Graph
Podstawowe metody obłsugujące graf.
Kontynuacja tej klasy(jasność punktów, strażnicy oraz ich harmonogram) znajduje się [tutaj](#Harmonogram-pracy-strażników).
Kontynuacja tej klasy(zastosowanie algorytmu Edmondsa-Karpa) znajduje się [tutaj](#Maksymalny-przep%C5%82yw).

#### Atrybuty
* `int n`
Liczba wierzchołków w grafie

* `std::vector<Vertex> v`
Wektor zawierający wszystkie wierzchołki grafu (obiekty klasy Vertex) .

* `int factory`
Identyfikator wierzchołka w którym znajduje się fabryka.

* `std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, queueComparator> guards`
Kolejka priorytetowa par typu `int` opisująca dostępnych strażników. Jest ona sortowana za pomocą komparatora `queueComparator`.
Składa się z:
* `int `
Identyfikator danego strażnika.
* `int`
Energia danego strażnika.

* `struct queueComparator`
Komparator do kolejki `guards` sortujący ją malejąco po energii poszczególnych strażników.

#### Metody

* `int getFactoryId()`
Metoda zwraca ID wierzchołka, który jest fabryką.

* `void generateGraph()`
Metoda generuje graf. Dla czytelności przykładowego grafu zakładamy że dla każdego wierzchołka generowane jest maksymalnie 5 krawędzi z niego wychodzących.

* `void fixGeneratedGraph()`
Metoda sprawdza czy z fabryki można dojść do każdego wierzchołka w grafie, a jeśli nie to łączy niedostępne wierzchołki (wcześniej pogrupowane by zminimalizować ilość krawędzi) z fabryką.

* `void dfsForFix(int id, int groupid)`
Metoda używana przez `fixGeneratedGraph()` wyszukująca w grafie wszystkie wierzchołki do których można dojść z wierzchołka z podanym `id` i przypisuje im podane `groupid`.

Jako argumenty metoda przyjmuje liczbę całkowitą `id` identyfikującą wierzchołek oraz liczbę całkowitą `groupid`, która identyfikuje grupę, do której należy wierzchołek.

* `int ifConnected()`
Metoda używana przez `fixGeneratedGraph()` szukająca wśród wierzchołków pierwszego który nie jest przydzielony do żadnej grupy (jego `groupid` jest równe 0) i zwracająca jego `id`.

* `void outputGraph()`
Metoda wyświetla graf na ekran.

* `void inputGraph()`
Metoda pozwala ręcznie wprowadzić graf.

* `std::vector<Vertex> getV()`
Metoda zwraca wektor obiektów typu `Vertex`, który jest zbiorem wierzchołków w grafie.
Więcej o klasie `Vertex` znajduje się [tutaj](#Klasa-Vertex).

* `void drawGraph()`
Metoda jest odpowiedzialna za rysowanie grafu w formacie DOT i zapisanie go do pliku *rysunek.dot*, a następnie, za pomocą narzędzia Graphviz, generowany jest plik graficzny *rysunek.png*, który jest otwierany automatycznie.

### Klasa Vertex
Klasa przechowująca informacje o wierzchołkach.

#### Atrybuty

* `int id`
Unikalny identyfikator wierzchołka.

* `int groupid`
Identyfikator grupy, do której należy wierzchołek (potrzebne do metody `fixGeneratedGraph` w klasie `Graph`).

* `bool isLeader`
Wskazuje, czy wierzchołek jest liderem w swojej grupie.

* `float x`
Współrzędna x wierzchołka.

* `float y`
Współrzędna y wierzchołka.

* `int brightness`
Reprezentuje poziom jasności związany z wierzchołkiem.

* `std::vector<std::tuple<int, float, float>> edges`
Wektor zawierający krotki, z których każda reprezentuje krawędź wierzchołka. Składa się z:
* `int `
ID połączonego wierzchołka.
* `float`
Maksymalny przepływ krawędzi.
* `float`
Aktualny przepływ krawędzi.

#### Metody
* `void setCoords(float x, float y)`
Ustawia współrzędne x i y wierzchołka.

Jako argument przyjmuje`float x` oraz `float y`, które są kolejno współrzędną x oraz y.

* `std::vector<std::tuple<int, float, float>>* getEdges()`
Zwraca wskaźnik do wektora krawędzi połączonych z wierzchołkiem.

* `float getx()`
Zwraca współrzędną x wierzchołka.

* `float gety()`
Zwraca współrzędną y wierzchołka.

* `int getid()`
Zwraca id wierzchołka.

* `bool getIsLeader()`
Sprawdza czy wierzchołek jest liderem.

* `int getGroupid()`
Zwraca ID grupy wierzchołka.

* `int getBrightness()`
Zwraca poziom jasności wierzchołka.

* `void setid(int id)`
Ustawia ID wierzchołka.

Jako argument przyjmuje `int id`, które jest nowym ID wierzchołka.

* `void setGroupid(int groupid)`
Ustawia ID grupy wierzchołka.

Jako argument przyjmuje `int groupid`, które jest nowym ID grupy wierzchołka.

* `void setIsLeader(bool isLeader)`
Ustawia status lidera wierzchołka.

Jako argument przyjmuje `bool isLeader`, które jest nowym statusem lidera.

* `void setBrightness(int brightness)`
Ustawia poziom jasności wierzchołka.

Jako argument przyjmuje `int brightness`, które reprezentuje poziom jasności związany z wierzchołkiem.

## Tragarze

### Klasa Pairs

#### Atrybuty

* `std::vector <Carrier> carriers`
Wektor zawiera obiekty klasy `Carrier`, które reprezentują tragarzy.

* `int r`
Liczba tragarzy z rękami skierowanymi w prawo.

* `int l`
Liczba tragarzy z rękami skierowanymi w lewo.

#### Metody

* `void generatePairs()`
Generuje tragarzy oraz to, który kogo lubi, pytając się użytkownika o ilość praworęcznych i leworęcznych tragarzy.

* `void inputPairs()`
Wczytuje pary tragarzy.

* `void outputPairs()`
Wypisuje pary tragarzy.

* `void connectingPairs()`
Łączy w pary tragarzy.

* `float maximumFlow(int factory, int endnodeId, std::vector<Vertex>* v, std::vector<std::pair<int, int>>* examplePairs)`
Oblicza i zwraca maksymalny przepływ w grafie od wierzchołka reprezentującego fabrykę do wierzchołka reprezentującego końcowy punkt. Składa się z:
* `int factory`
ID wierzchołka reprezentującego fabrykę.
* `int endnodeId`
ID wierzchołka reprezentującego końcowy punkt.
* `std::vector<Vertex>* v`
Wskaźnik do wektora wierzchołków grafu.
* `std::vector<std::pair<int, int>>* examplePairs`
Wskaźnik do wektora par tragarzy.

* `std::vector<Vertex> getShortestPathBFS(int factory, int endnode, std::vector<Vertex>* v)`
Znajduje i zwraca najkrótszą ścieżkę w grafie od wierzchołka reprezentującego fabrykę do wierzchołka reprezentującego punkt końcowy, korzystająć z algorytmu BFS (Breadth-First Search). Składa się z:
* `int factory`
ID wierzchołka reprezentującego fabrykę.
* `int endnode`
ID wierzchołka reprezentującego końcowy punkt.
* `std::vector<Vertex>* v`
Wskaźnik do wektora wierzchołków grafu.

### Klasa Carrier
Klasa przechowująca informacje o tragarzach.

#### Atrybuty

* `int id`
Identyfikator tragarza.

* `int numberOfLikes`
Liczba tragarzy, których lubi dany tragarz.

* `std::vector<int> likes`
Wektor `int`, gdzie każda para składa się z identyfikatora tragarza, którego lubi dany tragarz.

#### Metody

* `std::vector<int>* getLikes()`
Zwraca wskaźnik do wektora par reprezentujących tragarzy lubianych przez danego tragarza.

* `void setid(int id)`
Ustawia identyfikator tragarza.

Jako argument przyjmuje `int id`, który jest identyfikatorem tragarza.

* `void setNumberOfLikes(int l)`
Ustawia liczbę tragarzy, których lubi dany tragarz.

Jako argument przyjmyje `int l`, który jest liczbą tragarzy lubianych przez danego tragarza.

* `int getid()`
Zwraca identyfikator tragarza.

* `int getNumberOfLike()`
Zwraca liczbę tragarzy, których lubi dany tragarz.

## Otoczka wypukła
Do utworzenia otoczki wypukłej został użyty algorytm Jarvisa.

### Klasa ConvexHull
Klasa służy do tworzenia otoczki wypukłej oraz obliczania jej obwodu.

#### Metody
* `std::vector<Vertex> calculateConvexHull(std::vector<Vertex> v)`
Metoda służy do obliczenia otoczki wypukłej.

Jako argument przyjmuje wektor obiektów typu `Vertex`, które reprezentują punkty w przestrzeni dwuwymiarowej.

Zwraca wektor obiektów `Vertex`, które tworzą otoczkę wypukłą.

* `float crossProduct(Vertex p, Vertex q, Vertex r)`
Metoda oblicza iloczyn wektorowy trzech punktów(p, q, r). Zostaje to wykorzystane w metodzie `calculateConvexHull`.

Jako argument przyjmuje trzy obiekty klasy `Vertex` będące punktami w przestrzeni dwuwymiarowej.

Zwraca:

* 0 - iloczyn wektorowy wynosi 0, punkty p, q, r są wspóliniowe
* 1 - iloczyn wektorowy jest dodatni, punkt r leży po lewej stronie odcinka pq
* 2 - iloczyn wektorowy jest ujemny, punkt r leży po prawej stronie odcinka pq

* `float perimeter(std::vector<Vertex>& v)`

Metoda służy do obliczenia obwodu otoczki wypukłej.

Jako argument metoda przyjmuje wektor obiektów `Vertex`, które tworzą otoczkę wypukłą.

Zwraca obwód otoczki wypukłej.
* `float distance(Vertex p, Vertex q)`
Metoda służy do obliczania długości odcinka pq.

Jako argument metoda przyjmuje dwa obiekty typu `Vertex`.

Zwraca długość odcinka pq.

## Maksymalny przepływ
Do znalezienia maksymalnego przepływu między fabryką a punktem budowy płotu został użyty algorytm Edmondsa-Karpa.

### Klasa Graph
Kontynuacja tej klasy(podstawowe metody) znajduje się [tutaj](#Klasa-Graph).
Kontynuacja tej klasy(jasność punktów, straznicy oraz ich harmonogram) znajduje się [tutaj](#Harmonogram-pracy-strażników).

#### Atrybuty
* `std::vector<Vertex> v`
Wektor przechowujący zbiór wierzchołków grafu.

* `int factory`
Przechowuje identyfikator wierzchołka, który jest fabryką.

#### Metody
* `std::vector<Vertex> getShortestPathBFS(int endnode)`
Metoda znajduje najkrótszą drogę między fabryką a punktem `endnode`.

Jako argument metoda przyjmuje liczbę całkowitą `endnode`, która jest identyfikatorem wierzchołka docelowego.

Zwraca wektor obiektów typu `Vertex` zawierający wszystkie punkty na znalezionej drodze.
Więcej o klasie `Vertex` znajduje się [tutaj](#Klasa-Vertex).

* `float maximumFlow(int endnodeId)`
Metoda oblicza maksymalny przepływ między fabryką a punktem na otoczce.

Jako argument metoda przyjmuje liczbę całkowitą `endondeId`, która jest identyfikatorem wierzchołka docelowego.

Zwraca liczbę zmiennoprzecinkową reprezentującą maksymalny przepływ między fabryką a punktem o identyfikatorze `endnode`. Jeśli nie ma dojścia do `endnode` zwracana jest wartość 0.

* `void flowCleaner()`
Metoda zeruje aktualny przepływ na wszystkich krawędziach.

## Harmonogram pracy strażników
Tworzenie oraz wyświetlanie tygodniowego harmonogramu pracy strażników.

### Klasa Graph
Kontynuacja tej klasy(podstawowe metody) znajduje się [tutaj](#Klasa-Graph).
Kontynuacja tej klasy(zastosowanie algorytmu Edmondsa-Karpa) znajduje się [tutaj](#Maksymalny-przep%C5%82yw).

#### Metody
* `void guardShedule(std::vector<Vertex> convexHull)`
Metoda tworzy oraz wyświetla harmonogram pracy strażników.

Jako argument metoda przyjmuje wektor obiektów typu `Vertex`, który zawiera punkty znajdujące się na otoczce.
Więcej o klasie `Vertex` znajduje się [tutaj](#Klasa-Vertex).

* `void generateBrightness(std::vector<Vertex>* convexHull)`
Metoda generuje poziom jasności dla każdego punktu znajdującego się na otoczce.

Jako argument metoda przyjmuje wskaźnik na wektor obiektów typu `Vertex`, który zawiera punkty znajdujące się na otoczce.
Więcej o klasie `Vertex` znajduje się [tutaj](#Klasa-Vertex).

* `void inputBrightness(std::vector<Vertex>* convexHull)`
Metoda pozwala ręcznie wprowadzić jasność dla każdego punktu znajdującego się na otoczce.

Jako argument metoda przyjmuje wskaźnik na wektor obiektów typu `Vertex` , który zawiera punkty znajdujące się na otoczce.
Więcej o klasie `Vertex` znajduje się [tutaj](#Klasa-Vertex).

* `void generateGuards(int maxSize)`
Metoda generuje 20 strażników wraz z ich energią.

Jako argument metoda przyjmuje liczbę całkowitą `maxSize`, która określa maksymalną wartość energii strażników ().

* `void inputGuards()`
Metoda pozwala ręcznie wprowadzić strażników wraz z ich energią.

* `void outputGuards()`
Metoda wypisuje na ekran wszystkich strażników wraz z ich energią.

## Melodia
Generowanie, wyświetlanie oraz ustawianie melodii.

### Klasa Melody
Kontynuacja tej klasy(zastosowanie algorytmu Huffmana) znajduje się [tutaj](#Algorytm-Huffmana).
#### Atrybuty
* `std::string s`
Przechowuje melodię.

* `int sSize`
Długość melodii.

#### Metody
* `void generateMelody(int len)`
Metoda generuje losową melodię o długości `len`.

Jako argument przyjmuje liczbę całkowitą `len`, która określa długość generowanej melodii.

* `void outputMelody()`
Metoda wypisuje melodię.

* `void setMelody(std::string s)`
Metoda ustawia melodię.

Jako argument przyjmuje `string s`, który reprezentuje melodię.

* `std::string getMelody()`
Metoda zwraca `string`, który reprezentuje melodię.
## Algorytm Huffmana
### Klasa Melody
Kontynuacja tej klasy(generowanie melodii) znajduje się [tutaj](#Melodia).
#### Atrybuty
* `std::string encrypted`
Przechowuje zaszyfrowaną melodię.

* `std::string decrypted`
Przechowuje odszyfrowaną melodię.

* `TreeNode* root`
Wskaźnik na korzeń drzewa Huffmana.
Więcej o klasie `TreeNode` znajduje się [tutaj](#Klasa-TreeNode).
* `std::map<char, std::string> mp`
Mapa do kodowania Huffmana, przechowuje kodowanie liter.

* `std::string mapTemp = ""`
Pomocniczy `string` do tworzenia kodów dla liter podczas budowania mapy Huffmana.
#### Metody
* `void outputEncryptedMelody()`
Metoda wypisuje zaszyfrowaną melodię.

* `void outputDecryptedMelody()`
Metoda wypisuje odszyfrowaną melodię.

* `void encryptHuffman()`
Metoda szyfruje melodię algorytmem Huffmana. Tworzy drzewo Huffmana na podstawie częstości występowania liter w melodii, tworzy mapę na podstawie tego drzewa, a następnie generuje zakodowaną melodię używając tej mapy.
* `void decryptHuffman()`
Metoda odszyfrowuje zaszyfrowaną melodię algorytmem Huffmana.
Używa drzewa Huffmana do konwersji zaszyfrowanej melodii z powrotem na oryginalną melodię.
* `void makeHuffmanMap(TreeNode* temp)`
Metoda pomocnicza wywoływana przez `encryptHuffman()` tworząca mapę zawierającą Huffmana.

Jako argument przyjmuje wskaźnik na obecnie przetwarzany węzeł Huffmana.
Więcej o klasie `TreeNode` znajduje się [tutaj](#Klasa-TreeNode).
* `void deleteHuffmanTree(TreeNode* del)`
Metoda do usuwania drzewa Huffmana.

Jako argument przyjmuje wskaźnik na obecnie usuwany węzeł drzewa Huffmana.
Więcej o klasie `TreeNode` znajduje się [tutaj](#Klasa-TreeNode).

* `~Melody()`
Destruktor klasy Melody. Usuwa drzewo Huffmana zwalniając zajmowaną przez nie pamięć.
### Klasa TreeNode
Klasa pomocnicza służąca do tworzenia węzłów drzewa Huffmana.
#### Atrybuty
* `TreeNode* left`
Wskaźnik na lewe dziecko węzła.

* `TreeNode* right`
Wskaźnik na prawe dziecko węzła.
* `char c`
Przechowuje literę, którą reprezentuje dany węzeł lub '-' jeśli to węzeł wewnętrzny.
* `int n`
Liczba wystąpień litery przechowywanej w węźle.
#### Metody
* `TreeNode* getLeft()`
Metoda zwraca wskaźnik na lewe dziecko węzła.

* `TreeNode* getRight()`
Metoda zwraca wskaźnik na prawe dziecko węzła.

* `char getc()`
Metoda zwraca literę przechowywaną w węźle.

* `int getn()`
Metoda zwraca liczbę wystąpień litery przechowywanej w węźle.
* `void setLeft(TreeNode* left)`
Metoda ustawia wskaźnik na lewe dziecko węzła.

Jako argument przyjmuje wskaźnik na lewe dziecko węzła.
* `void setRight(TreeNode* right)`
Metoda ustawia wskaźnik na prawe dziecko węzła.

Jako argument przyjmuje wskaźnik na prawe dziecko węzła.
* `void setc(char c)`
Metoda ustawia literę przechowywaną w węźle.

Jako argument przyjmuje literę przechowywaną w węźle.
* `void setn(int n)`
Metoda ustawia liczbę wystąpień litery przechowywanej w węźle.

Jako argument przyjmuje liczbę wystąpień litery przechowywanej w węźle.

## Wyszukiwanie wzorca w tekście
By wyszukać wzorzec w tekście został użyty algorytm Boyera-Moore'a.
Obsługiwane są tylko małe litery alfabetu angielskiego.
### Klasa PatternSearching
Służy do wyszukiwania wzorca w tekście.
#### Atrybuty
* `std::string pattern`
Przechowuje wzorzec, który ma być wyszukiwany.

* `std::vector<int> last`
Wektor przechowujący ostatnie położenie każdego znaku alfabetu we wzorcu.

* `std::vector<int> bmnext`
Wektor zawierający wartości przesunięć dla poszczególnych sufiksów wzorca.
#### Metody
* `void fillLast()`
Metoda wypełnia wektor 'last', który przechowuje ostatnie położenie każdego znaku wzorca.

* `void fillBMNext()`
Metoda wypełnia wektor bmnext, który jest wykorzystywany do obliczania przesunięć wzorca.
* `void setPattern(const std::string& pat)`
Metoda ustawia wzorzec do wyszukiwania i inicjalizuje struktury pomocnicze: `fillLast()` oraz `fillBMNext()`.

Jako argument przyjmuje wzorzec, który ma byc wyszukany.

* `std::vector<int> search(const std::string& text)`
Metoda wyszukuje wzorzec w podanym tekście.

Jako argument przyjmuje tekst, w którym ma wyszukać wzorzec.

Zwraca wektor zawierający wszystkie indeksy pierwszych liter wystąpień wzorca w tekście.

### Zamiana wzorca
Aby podmienić wzorzec na inny należy wykonać następujące kroki.

Ustawienie wzorca, który będzie wyszukiwany w tekście.

std::string pattern = "abc";
ps.setPattern(pattern);

Wyszukiwanie wzorca w tekście.

std::string text = "abctextabc";
std::vector<int> result = ps.search(text);

Zamiana wzorca.

if (!result.empty())
{
    std::string newPattern = "xyz";
    for (int i = 0; i < result.size(); i++)
    {
        for (int j = 0; j < pattern.size(); j++)
        {
            text[result[i] + j] = newPattern[j];
        }
    }
}