#pragma once
#include "Wierzcholek.h"
#include "Krawedz.h"

class Graf
{
public:
	Graf(const int ile);
	void UstawGraf(int **MS,const int n);
	void DFS(int v,  int &skladowa);
	void UstawNieodwiedzone();
	int CzyOdwiedzony(const int i);
	void Zwolni();
	void Ponumeruj();
	void UstawLiczbeKrawedzi(const int l);
	void UstawWszystko(int **MI,int n, int l);
	void Wypisz();
	void Dijkstra(int s, int **wagi);
	void InitG(int s, int rozmiar);
	int Minimum();
	void Relax(int u, int v, int w);
	void Wypisz_d_p();
	int **ZwrocWagi();
	void ADD_S();
	bool Bellman_Ford(int **wagi,int zrodlo);
	void Johnson();
	void Kruskal(int **MI,int l);
	void make(int x);
	void polacz(int x, int y);
	int znajdz_i_ustaw(int x);
	~Graf();
	static bool wypisz;
private:
	//Glowny graf
	std::vector<Wierzcholek> G_graf;
	//Graf o jeden wierzcholek wiekszy od G_graf uzywany w Johnosnie
	std::vector<int> G_prim;
	//Wektor wag
	std::vector<int> d;
	//Wektor wag, uzywany w Johnsoie
	std::vector<int> d_prim;
	//to w suemie nie jest potrzebne
	std::vector<int> p_prim;
	//Wektor poprzedikow
	std::vector<int> p;
	//Wektor gotowych wierzcholow w algorytmie Dijkstry
	//(tego szpiega z Wiedzmina)
	std::vector<int> S;
	//Wektor wierzcholkow ktore jescze musimy odwiedzic (do algorytmu Dijkstry)
	std::vector<int> Niegotowe;
	//wektor reprezentantow danego wierzcholka
	std::vector<int> ojciec;
	//okresla ilosc zbiorow polaczonych
	std::vector<int> ranga;
	//tablica wag laczacych dana krawedz
	int **G_wagi;
	//tablica wag dla grafu G_prim
	int **G_wagi_prim;
	//std::vector<Krawedz> G_krawedz;
	//rozmiar oryginalnego grafu
	int G_rozmiar;
 
	//int G_rozmiarK;

};
  
  
  

  ///////////////////////////////////////  
  
  ////////////////////////////////////
  
  ////////////////////////////////////
  
  ////////////////////////////////////
  
  
  #include "Graf.h"
#include <limits>
//Zmienna uzywana w algorytmie DIjkstry(uzywamy go wieloktornie,
//a chcemy wypisac dane tyklko do zad2)
bool Graf::wypisz = true;

//Konstukotr ustaiwajacy rozmiar grafu
Graf::Graf(const int ile)
{
	G_graf.resize(ile);
	G_rozmiar = ile;
}

//Szukamy spojnej skladowej
void Graf::DFS(int v,int &skladowa)
{
	G_graf[v].W_skladowa = skladowa;
	G_graf[v].W_odwiedzony = 1;
	for(int i = 0; i < G_graf[v].W_ilosc_sasiadow; i++)
	{
		if(G_graf[v].W_sasiedzi[i]->W_odwiedzony == -1)
		{
			G_graf[v].W_sasiedzi[i]->WDFS(i,skladowa);
		}
	}
}

//Do ustawiania ze kazdy wierzcholek jest nieodiwedziony
void Graf::UstawNieodwiedzone()
{
	for(int i = 0; i < G_rozmiar; i++)
	{
		G_graf[i].W_odwiedzony = -1;
	}
}

//Ustawia graf wedlug macierzy sasiedztaw, n - liczba wierzcholkow
void Graf::UstawGraf(int **MS, const int n)
{
	for(int i = 0; i < n; i++)
	{
		int ilosc = 0;
		for (int j = 0; j< n; j++)
		{
			if(MS[i][j] == 1) ilosc++;
		}
		G_graf[i].W_sasiedzi = new Wierzcholek *[ilosc];
		G_graf[i].W_ilosc_sasiadow = ilosc;
		G_graf[i].W_free = 1;
	}


	for(int i = 0; i < n; i++)
	{
		int k = 0;
		for (int j = 0; j< n; j++)
		{
			if(MS[i][j] == 1)
			{
				G_graf[i].W_sasiedzi[k] = &G_graf[j];
				k++;
			}
		}
	}
}


//Sprawdza czy dany wierzcholek jest odwiedzony
int Graf::CzyOdwiedzony(const int i)
{
	return G_graf[i].W_odwiedzony;
}

//Main.cpp
void Graf::Zwolni()
{
	for(int i = 0; i < G_rozmiar; i++)
	{
		if(G_graf[i].W_free) delete [] G_graf[i].W_sasiedzi;
	}
}

//Numeruje wierzcholki od 0!
void Graf::Ponumeruj()
{
	for(int i = 0; i < G_rozmiar; i++)
	{
		G_graf[i].W_nr_wierzcholka = i;
	}
}

//Ustawia wagi i sasiadow kazdego wierzcholka
void Graf::UstawWszystko(int **MI,int n, int l)
{
	for(int i = 0; i < l; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(MI[j][i] != 0)
			{
				G_graf[j].W_waga.push_back(MI[j][i]);
			}
		}
	}

	G_wagi = new int *[n];
	for(int i = 0; i < n; i++)
	{
		G_wagi[i] = new int [n];
		for(int j = 0; j< n; j++)
		{
			G_wagi[i][j] = 0;
		}
		G_wagi[i][i] = 0;
	}

	for(int i = 0; i < G_rozmiar; i++)
	{
		for(int j = 0; j < G_graf[i].W_ilosc_sasiadow; j++)
		{
			G_wagi[i][G_graf[i].W_sasiedzi[j]->W_nr_wierzcholka] = G_graf[i].W_waga[j];
		}
	}

	std::cout<<"\nMACIERZ WAG\n";
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			std::cout<<G_wagi[i][j];
			if(G_wagi[i][j] >= 10 || G_wagi[i][j] < 0) std::cout<<" ";
			else std::cout<<"  ";
		}
		std::cout<<"\n";
	}

	std::cout<<"\n\n";

}

//Wypisuje dane w formie NR_wierzcholka: NR_sasiada(waga_krawedzi)
void Graf::Wypisz()
{
	for(int i = 0; i < G_rozmiar; i++)
	{
		std::cout<<G_graf[i].W_nr_wierzcholka<<": ";
		for(int j = 0; j < G_graf[i].W_ilosc_sasiadow; j++)
		{
			std::cout<<G_graf[i].W_sasiedzi[j]->W_nr_wierzcholka<<"("<<G_graf[i].W_waga[j]<<")";
			if(j != G_graf[i].W_ilosc_sasiadow -1) std::cout<<", ";
		}
		std::cout<<"\n";
	}
}

int** Graf::ZwrocWagi()
{
	return G_wagi;
}

//Alorytm do zestawu 3
//iniciuje tablice(vector) wag i poprzednikow
void Graf::InitG(int s, int rozmiar)
{
	d.resize(G_rozmiar);
	d_prim.resize(rozmiar);
	p_prim.resize(rozmiar);
	p.resize(G_rozmiar);
	for(int i = 0; i < G_rozmiar; i++)
	{
		d[i] = std::numeric_limits<int>::max();
		p[i] = -1;
		d_prim[i] = std::numeric_limits<int>::max();
		p_prim[i] = -1;
	}
	if(s < G_rozmiar)
		d[s] = 0;

	d_prim[s] = 0;
	if(rozmiar > G_rozmiar) d_prim[G_rozmiar] = 0;
}

//Wyszukuje minimum w vectorze d w tych wierzcholkach
//ktore jeszcze sa nieodowiedzone (Przechowywane w tablicy Niegotowe)
int Graf::Minimum()
{
	//Inicjalizacja minimum i numeru indeksu pod ktorym sie to minimum znajduej
	int min = std::numeric_limits<int>::max();
	int index= - 1;
	for(int i = 0; i < G_rozmiar; i++)
	{
		bool test = false;
		if(min > d[i])
		{
			for(int j = 0; j < G_rozmiar; j++)
			{
				//Jesli znalezlismy wierzcholek nieodiwedzony(o numerze i)
				if(i == Niegotowe[j])
				{
					test = true;
					break;
				}
			}
			//to zmieniamy minimum
			//i ustalami pod ktorym indeksem sie zajduje
			if(test)
			{
				min = d[i];
				index = i;
			}
		}
	}
	//tu zmieniami wartosc w tablicy NIegotowe aby miec pewnosc, ze 
	//juz nie zostanie ponownie uzyta
	if(index != -1) Niegotowe[index] = std::numeric_limits<int>::max();
	return index;
}

//Relaksacja krawedzi
//u - poprzednik
//v - obecny wierzcholek
//w - waga krawedzi u--v
void Graf::Relax(int u, int v, int w)
{
	//Sprawdzamy czy obecny koszt jest wiekszy od nowego
	// jesli tak to zaminiemy i zmieniamy poprzednika 
	if(d[v] > d[u] + w)
	{
		d[v] = d[u] + w;
		p[v] = u;
	}
	if(d_prim[v] > d_prim[u] + w)
	{
		d_prim[v] = d_prim[u] + w;
		//p[v] = u;
	}
}

//Wypisuje wektor d - koszt, p -poprzezdnik
void Graf::Wypisz_d_p()
{
	for(int i = 0; i < G_rozmiar; i++)
		std::cout<<"d("<<i<<")"<<"="<<d[i]<<"\n";
	std::cout<<"\n\n";
	for(int i = 0; i < G_rozmiar; i++)
		std::cout<<"p["<<i<<"]"<<" = "<<p[i]<<"\n";
}

//ALgorytm Dijkstry
void Graf::Dijkstra(int s,int **wagi)
{
	//Inicjalizacja wektorow d i p
	InitG(s,G_rozmiar);
	if(int(Niegotowe.size()) > 0) Niegotowe.resize(0);
	if(int(S.size()) > 0) S.resize(0);
	//Wstawiamy do Niegotwoe numer kazdego wierzcholka
	for(int i = 0; i < G_rozmiar; i++)
	{
		Niegotowe.push_back(i);
		//std::cout<<Niegotowe[i]<<" ";
	}
	//std::cout<<"\n";
	//Dopkoki S nie zawiera wszystkich wierzcholkow
	while (int(S.size()) != G_rozmiar)
	{
		//Szukamu indeksu minimum(rownoczesnie numer wierzcholka)
		int u = Minimum();
		//std::cout<<"u="<<u<<"\n";
		//Wstawiamu gotowy numer do S
		S.push_back(u);
		std::vector<int> Sasiedzi;
		for(int i = 0; i < G_graf[u].W_ilosc_sasiadow; i++)
		{
			bool sprawdz = true;
			//W sumie nie pamietam co to mialo robic
			//ale cos waznego
			//jak sobie przypomne do dopisze
			//a tak zostawiam dla waszej interpretacji
			for(int j = 0; j < int(S.size()); j++)
			{
				//std::cout<<S[j]<<"-"<<G_graf[u].W_sasiedzi[i]->W_nr_wierzcholka<<" ";
				if(S[j] == G_graf[u].W_sasiedzi[i]->W_nr_wierzcholka)
				{
					sprawdz = false;
					break;
				}
			}
			if(sprawdz) Sasiedzi.push_back(G_graf[u].W_sasiedzi[i]->W_nr_wierzcholka);
		}

		//Obliczamy koszty do wszystkich sasiadow daneg wierzcholka u
		for(int i = 0; i < int(Sasiedzi.size()); i++)
		{
			int v = Sasiedzi[i];
			Relax(u,v,wagi[u][v]);
		}
		//Wypisz_d_p();
	}

	//std::cout<<"\nOSTATECZNIE\n";

	//Wypisujemu tablice d i p
	//drogi do kazdego wierzcholka(od wierzcholka zrodlowego s)
	//i ich koszty
	if(wypisz)
	{
		Wypisz_d_p();
		wypisz = false;
		std::cout<<"\n";
		for(int i = 0; i < G_rozmiar; i++)
		{	
			int new_i = i;
			std::cout<<i<<"<--"; 
			while(new_i != s)
			{
				new_i = p[new_i];
				std::cout<<new_i;
				if(new_i != s) std::cout<<"<--";

			}
			std::cout<<"  koszt: "<<d[i]<<"\n";
		}
	}
}

//Sluzy do ustawiania nowego grafu ktory zaweiera staary graf
// powiekszony o 1 wierzcholek ktory jest polaczony krawedzia o koszcie 0
// z kazdym innym wierzcholkiem grafu
void Graf::ADD_S()
{
	for(int i = 0; i <= G_rozmiar; i++)
	{
		G_prim.push_back(i);
	}

	G_wagi_prim = new int *[int(G_prim.size())];
	for(int i = 0; i < int(G_prim.size());i++)
	{
		G_wagi_prim[i] = new int[int(G_prim.size())];
		for(int j = 0; j < int(G_prim.size()); j++)
		{
			G_wagi_prim[i][j] = 0;
		}
	}

	for(int i = 0; i < G_rozmiar; i++)
	{
		for(int j = 0; j < G_rozmiar; j++)
		{
			G_wagi_prim[i][j] = G_wagi[i][j];
		}
	}

}

//Sluzy do sprawdzania czy jest ujemna waga w grafie
//jesli tak do wyrzca false
bool Graf::Bellman_Ford(int **wagi,int zrodlo)
{
	int rozmiar = (G_prim.size());
	InitG(zrodlo,rozmiar);
	for(int i = 0; i < rozmiar - 1;i++)
	{
		for(int u = 0; u < rozmiar - 1; u++)
		{
			for(int v = 0; v< rozmiar - 1; v++)
			{
				if(wagi[u][v] != 0)
				{
					Relax(u,v,wagi[u][v]);
				}
			}
		}
	}

	for(int  u = 0; u< rozmiar - 1; u++)
	{
		for(int v = 0; v < rozmiar - 1; v++)
		{
			if(wagi[u][v] != 0)
			{
				if(d_prim[v] > d_prim[u] + wagi[u][v]) return false;
			}
		}
	}

	return true;
}

//Sluzy do wyznaczania macierzy odleglosci
//zobaczcie na algorytmy ze strony Pani Wach
void Graf::Johnson()
{
	ADD_S();
	std::vector<int> h;
	int rozmiar = int(G_prim.size());
	bool tryb = Bellman_Ford(G_wagi,G_rozmiar);
	//Jesli nie ma ujemnej krawdzi
	if(tryb)
	{
		
		for(int i = 0; i < rozmiar; i++)
		{
			h.push_back(d_prim[i]);
		}
		for( int u = 0; u < rozmiar; u++)
		{
			for(int v = 0; v < rozmiar; v++)
			{
				if(G_wagi_prim[u][v] != 0)
				{
					G_wagi_prim[u][v] = G_wagi[u][v] + h[u] - h[v];
				}
			}
		}
		//D - macierz odleglosci
		int **D = new int *[G_rozmiar];
		for(int i = 0; i < G_rozmiar; i++)
		{
			D[i] = new int [G_rozmiar];
		}

		for(int u = 0; u < G_rozmiar; u++)
		{
			Dijkstra(u,G_wagi_prim);
			for(int v= 0; v < G_rozmiar; v++)
			{
				D[u][v] = d[v] - h[u] + h[v];
			}
		}

		std::cout<<"\nMacierz odleglosci\n";
		for(int i = 0; i < G_rozmiar; i++)
		{
			for (int j = 0; j < G_rozmiar; j++)
			{
				std::cout<<D[i][j];
				if(D[i][j] >= 10) std::cout<<" ";
				else std::cout<<"  ";
			}
			std::cout<<"\n";
		}
		//Szukamu centrum grafu tj. wierzcholka dla ktorego suma
		//wag w wierszu macierzy D jest najmniejsza
		int min = std::numeric_limits<int>::max();
		int centrum_grafu;

		for(int i = 0; i < G_rozmiar; i++)
		{
			int suma = 0;
			for(int j = 0; j < G_rozmiar; j++)
			{
				suma += D[i][j];
			}
			if(suma < min)
			{
				min = suma;
				centrum_grafu = i;
			}
		}

		std::cout<<"\nCentrum grafu: "<<centrum_grafu<<"\n\n";

		//Szukamy wierzcholka minmax.
		//do wektora minmax zapisujemy kolejno najwieksze wagi z kazdego wiersza
		//indeks pod ktorym znajduje sie najmniejsza waga w wektorze minmax jest naszym
		//szukanym wierzcholkiem
		std::vector<int> minmax;
		minmax.resize(G_rozmiar);

		for(int i = 0; i < G_rozmiar; i++)
		{
			int max = D[i][0];
			minmax[i] = max;
			for(int j = 1; j < G_rozmiar; j++)
			{
				if(max < D[i][j])
				{
					max = D[i][j];
					minmax[i] = max;
				}
			}
			//std::cout<<minmax[i]<<" ";
		}
		min = minmax[0];
		int idx = 0;
		for( int i = 1; i < G_rozmiar; i++)
		{
			if(min > minmax[i])
			{
				min = minmax[i];
				idx = i;
			}
		}

		std::cout<<"\nCentrum minimax: "<<idx<<"\n";

		for(int i = 0; i < G_rozmiar; i++)
		{
			delete [] D[i];
		}
		delete [] D;
	}
	else
	{
		std::cout<<"\n Graf zawiera krawedz o ujemnej wadze.\n";
		exit(-1);
	}

	
}

//Ustawiamy, ze reprezentantem kazdego wierzcholka jest od sam
//wiec mamy las w ktorym znajduja sie wszystkie nasze wierzcholki
//kazdy jest osobnym grafem
void Graf::make(int x)
{
	ojciec[x] = x;
	ranga[x] = 0;
}

//Laczymy dwa wierzcholki
//Jesli x nie jest reprezentantem swojego zbioru (wczesniej juz byl polaczony z innym wierzcholkiem)
//to y staje sie tez czescia tego zbioru
//w przeciwnym wypadku to x staje sie czescia zbioru do ktorego nalezy y
void Graf::polacz(int x, int y)
{
	x = znajdz_i_ustaw(x);
	y = znajdz_i_ustaw(y);
	if(ranga[x] > ranga[y])
	{
		ojciec[y] = x;
	}
	else
	{
		ojciec[x] = y;	
	}
	if(ranga[x] == ranga[y]) ranga[y]++;

}

//Szukamy reprezentanta zbioru do ktorego nalezy x
int Graf::znajdz_i_ustaw(int x)
{
	if(x != ojciec[x])
	{
		ojciec[x] = znajdz_i_ustaw(ojciec[x]);
	}

	return  ojciec[x];
}

//Szukamy najmniejszego drzewa rozpinajacego
//MI -macierz incydencji
//l - liczba krawdzi
void Graf::Kruskal(int **MI, int l)
{	
	//Tworzymy l tablic 3 elementowych
	//[i][0] - waga danej krawedzi
	//[i][1], [i][2] - numery wierzcholkow, ktore dana krawedz laczy 
	int **krawedzie = new int *[l];
	for(int i = 0; i < l; i++)
	{
		krawedzie[i] = new int [3];
	}

	//Tu uzupelniamy tablice krawedzi danymi z macierz MI
	for(int i = 0; i < l; i++)
	{
		bool sprawdz = true;
		for(int j = 0; j < G_rozmiar; j++)
		{
			if(MI[j][i] != 0)
			{
				if(sprawdz)
				{
					krawedzie[i][0] = MI[j][i];
					krawedzie[i][1] = j;
					sprawdz = false;
				}
				else
				{
					krawedzie[i][2] = j;
				}
			}
		}
	}
	
	//Sortujemy krawedzie wedlug wag
	for(int i = 0; i < l-1; i++)
	{
		int index = i;
		int min = krawedzie[i][0];
		for(int j = i+1; j < l; j++)
		{
			if(min > krawedzie[j][0])
			{
				min = krawedzie[j][0];
				index = j;
			}
		}

		if(index != i)
		{
			int waga = krawedzie[i][0];
			int v1 = krawedzie[i][1];
			int v2 = krawedzie[i][2];
			krawedzie[i][0] = krawedzie[index][0];
			krawedzie[i][1] = krawedzie[index][1];
			krawedzie[i][2] = krawedzie[index][2];
			krawedzie[index][0] = waga;
			krawedzie[index][1] = v1;
			krawedzie[index][2] = v2;
		}
	}

	ojciec.resize(G_rozmiar);
	ranga.resize(G_rozmiar);

	for(int i = 0; i< G_rozmiar; i++) make(i);


	//Algorytm do wyznaczania minimalnego drzewa rozpinajacego
	//zobaczcie czy to rzzeczywiscie dziala
	//troche zmienialem przy tym i wydaje sie ok
	//ale tak dla pewnosci to mozecie odpalic program
	//i zobaczyc czy rzeczywiscie laczy prawidlowo
	std::vector<int> T;
	//Wektor W chyba jest juz nie potrzebny
	//ale zostawiam jak cos nie bezdie dzialalo to mam drugi pomysl
	//do ktorego go wykorzystam
	std::vector<int> W;
	for(int i = 0; i < G_rozmiar; i++) W.push_back(1);
	for(int i = 0; i < l; i++)
	{
		//Szukamy reprezentantow danych wierzcholkow
		//jesli sa rozne to znaczy ze nie moze powstac cykl
		//wiec mozemy taka krawedz dodac
		int u = znajdz_i_ustaw(krawedzie[i][1]);
		int v = znajdz_i_ustaw(krawedzie[i][2]);
		if(u != v)
		{
			T.push_back(krawedzie[i][1]);
			T.push_back(krawedzie[i][2]);
			polacz(krawedzie[i][1],krawedzie[i][2]);
			W[krawedzie[i][1]] = 0;
			W[krawedzie[i][2]] = 0;
		}
		//bool wszystkie = false;
		//int sum = 0;
		//for(int k = 0; k < G_rozmiar; k++) sum += W[k];
		//if(sum == 0) wszystkie = true;
		if(int(T.size())/2 == G_rozmiar - 1 /*&& wszystkie*/) break;
	}

	for(int i = 0; i < l; i++)
	{
		for(int j = 0; j < 3; j++)
			std::cout<<krawedzie[i][j]<<" ";
		std::cout<<"\n";
	}
	for(int i = 0; i < G_rozmiar; i++) std::cout<<ojciec[i]<<" ";
		std::cout<<"\n";
	for(int i = 0; i < G_rozmiar; i++)
		std::cout<<ranga[i]<<" ";

	std::cout<<"\n\nMinimalne drzewo rozpinajace\n";
	for(int i = 0; i < int(T.size()); i+= 2)
	{
		std::cout<<T[i]<<" "<<T[i+1]<<"\n";
	}

	for(int i = 0; i < l; i++)
		delete [] krawedzie[i];
	delete [] krawedzie;
}


Graf::~Graf()
{
	for(int i = 0; i < G_rozmiar; i++)
	{
		delete [] G_graf[i].W_sasiedzi;
		delete [] G_wagi[i];
		delete [] G_wagi_prim[i];
	}
	delete [] G_wagi_prim[G_rozmiar];
	delete [] G_wagi;
	delete [] G_wagi_prim;
}