#include <iostream>
#include <ctime>
#include <fstream>
#include <cstdlib>
//#include <windows.h>
#include "Main.h"

using namespace std;

int main()
{
	int n,l;

	//Wczytujemy liczbe krawedzi i wierzchlkow
	cout<<"Podaj liczbe wierzcholkow: "; cin>>n;
	cout<<"Podaj liczbe krawedzi: "; cin>>l;
	
	//Sprawdzamy czy moza w ogole zrobic graf
	if(n*(n-1)/2 < l)
	{
		cout<<"Zbyt duza ilosc krawedzi!\n";
		exit(1);
	}
	if(l < n -1 || l == 0 || n == 0)
	{
		cout<<"Nie da sie wygenerowac spojnego grafu :(\n";
		exit(-1);
	}

	Graf graf(n);
	int skladowa = 0;
	int krawedz;

	srand(time(NULL));

	//Macierz sasiedztwa
	int **MS = new int *[n];
	for(int i = 0; i < n; i++)
	{
		MS[i] = new int [n];
	}
	//Dopoki graf nie jest spojny
	//losowo ustaiwmy macierz sasiedztwa
	while(skladowa != 1)
	{
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			MS[i][j] = 0;
		}
		krawedz = l;
		while(krawedz)
		{
			int k1 = rand() % n;
			int k2 = rand() % n;
			while (k1 == k2 || MS[k1][k2] == 1)
			{
				k1 = rand() % n;
				k2 = rand() % n;
			}
			MS[k1][k2] = 1;
			MS[k2][k1] = 1;
			krawedz--;	
		}
		//Algorytm sprawdzajacy spojna skladowa
		//Zwolnij() usuwa dane z pamieci gdyby cos zostalo (w poprzedniej
		//iteracji skladowa != 1)
		skladowa = 0;
		graf.Zwolni();
		//Ustaiwa graf wedlug danych z macierzy sasiedztwa
		graf.UstawGraf(MS,n);
		//Przygotowuje wierzcholki pod sprawdzanie spojnej skladowej
		graf.UstawNieodwiedzone();

		//Tu sprawdzamy
		for(int i = 0; i < n; i++)
		{
			if(graf.CzyOdwiedzony(i) == -1)
			{
				skladowa++;
				graf.DFS(i,skladowa);
			}
		}

	}

	cout<<"\nMACIERZ SASIEDZTWA\n";
	 for(int i = 0; i < n; i++)
	 {
	 	for(int j = 0; j < n; j++)
	 		cout<<MS[i][j]<<"  ";
	 	cout<<endl;
	 }


	 //Numerujemy wierzcholki
	 graf.Ponumeruj();

	 //Tworzymy macierz incydencji i przypisujemy losowe wagi kazdej krawedzi
	 int **MI;
	 S_to_L_to_I(MS,n,MI);
	 for(int i = 0; i < n; i++)
	 {
	 	for(int j = 0; j < l; j++)
	 	{
	 		cout<<MI[i][j];
	 		if(MI[i][j] >=10) std::cout<<" ";
	 		else std::cout<<"  ";
	 	}
	 	cout<<endl;
	 }


	 //To jest pod skrypt z Pythona z zestawu 1 ktory KAMIL MARKS,
	 //KAMIL MARKS mial poprawic zeby ladnie rysowalo
	 fstream plik;
	 plik.open("dane.txt",ios::out | ios::trunc);
	 if(plik.good())
	 {
	 	plik << "N\r\n";
	 	for(int i = 0; i < n; i++)
	 	{
	 		for(int j = 0; j < n; j++)
	 		{
	 			plik << MS[i][j];
	 			if(j < n - 1) plik << " ";
	 		}
	 		plik<<"\r\n";
	 	}
	 	plik.close();
	 }

	 cout<<endl<<endl<<endl;
	 graf.UstawWszystko(MI,n,l);
	 graf.Wypisz();
	 int zrodlo;

	 //Podajemy wierzcholek z ktorego zaczynamy algorytm Dijkstry
	 do
	 {
	 	cout<<"Podaj wierzcholek poczatkowy (zakres 0-"<<n-1<<"): "; cin>>zrodlo;
	 }while(zrodlo >=n);

	 graf.Dijkstra(zrodlo,graf.ZwrocWagi());
	 graf.Johnson();
	 graf.Kruskal(MI,l);

	 for(int i = 0; i < n; i++)
	 {
	 	delete [] MS[i];
	 	delete [] MI[i];
	 }
	 delete [] MS;
	 delete [] MI;



	return 0;
}



/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////







#pragma once

#include "Graf.h"

//Algorytmy z zestawu 1

int krawedz( int *&rozmiar,  int **&dane,  int &ilosc)
{
    int max_elem = 0;
    for(int i = 0; i < ilosc; i++)
    {
        for(int j = 0; j < rozmiar[i]; j++)
            max_elem++;
    }
    return max_elem;
}

void L_to_I(int *rozmiar,  int**dane,  int &ilosc, int **&MI)
{
    const int max = krawedz(rozmiar, dane, ilosc) / 2;
    MI = new int *[ilosc];
    for(int i = 0; i < ilosc; i++)
    {
        MI[i] = new int [max];
        for(int j = 0; j < max; j++)
            MI[i][j] = 0;
    }
    int x = 0;
    int k = 1;
   for(int i = 0; i < ilosc; i++)
    {
        for(int j = 0; j < rozmiar[i]; j++)
        {  
            if(k < dane[i][j])
            {
            	int los = rand()%10 + 1;
                MI[i][x] = los;
                MI[dane[i][j] - 1][x] = los;
                x++;
            } 
        }
        k++;
        if(x == max) break;
    }

     std::cout<<"MACIERZ INCYDENCJI\n";
   /* for(int i = 0; i < ilosc; i++)
    {
        for(int j = 0; j < max; j++)
            {
                std::cout<<MI[i][j]<<" ";
            }
            std::cout<<std::endl;
    }
   for(int i = 0; i < ilosc; i++)
    {
        delete [] MI[i];
    }
    delete [] MI;*/
}

void S_to_L_to_I(int **&dane, int &rozmiar, int **&MI)
{
    int **L = new int *[rozmiar];
    int *wielkoscL = new int [rozmiar];
    //Ustawianie tablica na wlasniwe rozmiary
    for(int i = 0; i < rozmiar; i++)
    {
        int ilosc_w_wierszu = 0;
        for(int j = 0; j < rozmiar; j++)
        {
            if(dane[i][j]) ilosc_w_wierszu++;
        }
        wielkoscL[i] = ilosc_w_wierszu;
        L[i] = new int [ilosc_w_wierszu];
    }
    //Uzupelnianie listy sasiedztwa
    for(int i = 0; i < rozmiar; i++)
    {
        int k = 0;
        for(int j = 0; j < rozmiar; j++)
        {
            if(dane[i][j])
            {
                L[i][k++] = j + 1;
            }
            if(k == wielkoscL[i]) break;
        }
    }
    //Wypisywanie listy sasiedztwa
  /*  std::cout<<"LISTA SASIEDZTWA\n";
    for(int i = 0; i < rozmiar; i++)
    {
        std::cout<<i + 1<<": ";
        for(int j = 0;  j< wielkoscL[i]; j++)
        {
            std::cout<<L[i][j]<<" ";
        }
        std::cout<<std::endl;
    }*/
    L_to_I(wielkoscL, L, rozmiar, MI);

    //Zwalnianie pamieci
    for(int i = 0; i < rozmiar; i++)
        delete [] L[i];
    delete [] L;
    delete [] wielkoscL;
}