#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;
}