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