AISD_Grafy_v1

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

// do listy krawedzi
struct Krawedz
{
    // wierzcholek ktory jest poprzednikiem
    int wierzcholek_p;
    // wierzcholek ktory jest nastepnikiem
    int wierzcholek_n;
};

// do listy nastepnikow
struct Nastepniki
{
    int wierzcholek;
    int ilosc_nastepnikow = 0;
    Nastepniki** tablica_nastepnikow;
};

void laduj_graf(int &liczba_wierzch, int &liczba_krawedzi, Krawedz *&lista_krawedzi)
{
    std::string nazwa_pliku;
    std::ifstream wczytaj;
    std::cout << "Podaj nazwe pliku: ";
    std::cin >> nazwa_pliku;
    wczytaj.open(nazwa_pliku);
    if(!wczytaj.good())
    {
        std::cout << "Blad przy otwieraniu pliku!" << std::endl;
        wczytaj.close();
        exit(0);
    }
    // wczytuje dwie pierwsze wartosci z pliku
    wczytaj >> liczba_wierzch;
    wczytaj >> liczba_krawedzi;
    // zajmuje pamiec
    lista_krawedzi = new Krawedz[liczba_krawedzi];
    // wczytywanie krawedzi
    for(int i = 0; i < liczba_krawedzi; i++)
    {
        int wartosc1, wartosc2;
        wczytaj >> wartosc1;
        wczytaj >> wartosc2;
        if(wartosc1 > liczba_wierzch || wartosc2 > liczba_wierzch)
        {
            std::cout << "Podano wierzcholek o blednym kluczu!" << std::endl;
            wczytaj.close();
            delete lista_krawedzi;
            exit(0);
        }
        else
        {
            // wykluczam istnienie grafu cyklicznego
            for(int j = 0; j < i; j++)
            {
                if(lista_krawedzi[j].wierzcholek_p == wartosc1 && lista_krawedzi[j].wierzcholek_n == wartosc2)
                {
                    std::cout << "Blad! Wystapienie powtorne danej krawedzi!" << std::endl;
                    wczytaj.close();
                    delete lista_krawedzi;
                    exit(0);
                }
            }
            for(int j = 0; j < i; j++)
            {
                if(lista_krawedzi[j].wierzcholek_p == wartosc2 && lista_krawedzi[j].wierzcholek_n == wartosc1)
                {
                    std::cout << "Blad! Graf jest cykliczny!" << std::endl;
                    wczytaj.close();
                    delete lista_krawedzi;
                    exit(0);
                }
            }
            lista_krawedzi[i].wierzcholek_p = wartosc1;
            lista_krawedzi[i].wierzcholek_n = wartosc2;
        }
    }
    std::cout << "Wczytywanie sie powiodlo!" << std::endl;
    wczytaj.close();
}

void generuj_graf(int liczba_wierzcholkow, int nasycenie, Krawedz *&lista_krawedzi, int &liczba_krawedzi)
{
    // oblicza procent nasycenia
    double mnoznik = double(nasycenie)/100;
    // oblicza ilosc krawedzi jaka trzeba wygenerowac
    liczba_krawedzi = ((liczba_wierzcholkow * (liczba_wierzcholkow - 1))/2)*mnoznik;
    // zajmuje pamiec
    lista_krawedzi = new Krawedz[liczba_krawedzi];
    srand(time(0));
    // generowanie krawedzi
    for(int i = 0; i < liczba_krawedzi; i++)
    {
        int wartosc1 = rand()%liczba_wierzcholkow + 1;
        int wartosc2 = wartosc1;
        while(wartosc1 == wartosc2)
        {
            wartosc2 = rand()%liczba_wierzcholkow + 1;
        }
        bool czy_wstawiamy = true;
        for(int j = 0; j < i; j++)
        {
            // warunek czy na pewno nie stworzymy cyklu w grafie
            if(lista_krawedzi[j].wierzcholek_p == wartosc2 && lista_krawedzi[j].wierzcholek_n == wartosc1)
            {
               czy_wstawiamy = false;
               i--;
            }
            // warunek czy na pewno juz dana krawedz nie istnieje
            else if(lista_krawedzi[j].wierzcholek_p == wartosc1 && lista_krawedzi[j].wierzcholek_n == wartosc2)
            {
                czy_wstawiamy = false;
                i--;
            }
        }
        if(czy_wstawiamy == true)
        {
            lista_krawedzi[i].wierzcholek_p = wartosc1;
            lista_krawedzi[i].wierzcholek_n = wartosc2;
        }
    }
    std::cout << "Generowanie grafu przebieglo pomyslnie!" << std::endl;
}

// NIE JESTEM PEWNY CZY TO W PELNI DZIALA
void krawedzie_do_nastepniki(int liczba_wierzcholkow, int liczba_krawedzi, Krawedz lista_krawedzi[], Nastepniki *&lista_nastepnikow)
{
    lista_nastepnikow = new Nastepniki[liczba_wierzcholkow];
    for(int i = 0; i < liczba_wierzcholkow; i++)
    {
        lista_nastepnikow[i].wierzcholek = i+1;
    }
    for(int i = 0; i < liczba_krawedzi; i++)
    {
        // tymczasowa tablica do podmiany
        Nastepniki** tmp_tablica = new Nastepniki*[lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].ilosc_nastepnikow];
        // zwieksza o jeden ilosc nastepnikow dla danego wierzcholka na liscie nastepnikow
        lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].ilosc_nastepnikow++;
        //std::cout << "PO ZWIEKSZENIU LICZBY NASTEPNIKOW" << std::endl;
        for(int j = 0; j < lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].ilosc_nastepnikow - 1; j++)
        {
            //std::cout << "CZY TU WYWALA?" << std::endl;
            tmp_tablica[j] = lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].tablica_nastepnikow[j];
        }
        //std::cout << "PO PRZEPISANIU DO TMP" << std::endl;
        // alokoawnie tablica_nastepnikow od nowa (nie wiem co sie dzieje z tymi wartosciami co tam byly wczesniej)
        //std::cout << lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].tablica_nastepnikow << std::endl;
        //delete [] lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].tablica_nastepnikow;
        //std::cout << "CZY TU?" << std::endl;
        lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].tablica_nastepnikow = new Nastepniki*[lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].ilosc_nastepnikow];
        //std::cout << "PO TU?" << std::endl;
        // przepisywanie starych wskaznikow
        for(int j = 0; j < lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].ilosc_nastepnikow - 1; j++ )
        {
            lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].tablica_nastepnikow[j] = tmp_tablica[j];
        }
        // dodawanie nowego wskaznika
        lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].tablica_nastepnikow[lista_nastepnikow[lista_krawedzi[i].wierzcholek_p - 1].ilosc_nastepnikow - 1] = &lista_nastepnikow[lista_krawedzi[i].wierzcholek_n - 1];
        delete [] tmp_tablica;
    }
    std::cout << "Stworzenie listy nastepnikow przebieglo pomyslnie!" << std::endl;
}

void krawedzie_do_macierz(int liczba_wierzcholkow, int liczba_krawedzi, Krawedz lista_krawedzi[], int**& macierz_sasiedztwa)
{
    // tworzymy pusta macierz sasiedztwa wypelniona zerami
    macierz_sasiedztwa = new int*[liczba_wierzcholkow];
    for(int i = 0; i < liczba_wierzcholkow; i++)
    {
        macierz_sasiedztwa[i] = new int[liczba_wierzcholkow];
    }
    for(int i = 0; i < liczba_wierzcholkow; i++)
    {
        for(int j = 0; j < liczba_wierzcholkow; j++)
        {
            macierz_sasiedztwa[i][j] = 0;
        }
    }
    // wstawiamy jedynki w odpowiednich miejscach krawedzi
    for(int i = 0; i < liczba_krawedzi; i++)
    {
        macierz_sasiedztwa[lista_krawedzi[i].wierzcholek_p - 1][lista_krawedzi[i].wierzcholek_n - 1] = 1;
    }
    std::cout << "Stworzenie macierzy sasiedztwa przebieglo pomyslnie!" << std::endl;
}

// funkcje testowe sluzace do wyswietlania grafu w roznych reprezentacjach
void wyswietl_graf(int liczba_krawedzi, Krawedz lista_krawedzi[])
{
    for(int i = 0; i < liczba_krawedzi; i++)
    {
        std::cout << "[" << i << "]: " << lista_krawedzi[i].wierzcholek_p << " -> " << lista_krawedzi[i].wierzcholek_n << std::endl;
    }
}

void wyswietl_graf_2(int liczba_wierzcholkow, Nastepniki lista_nastepnikow[])
{
    for(int i = 0; i < liczba_wierzcholkow; i++)
    {
        std::cout << "[" << i << "]: " << lista_nastepnikow[i].wierzcholek;
        for(int j = 0; j < lista_nastepnikow[i].ilosc_nastepnikow; j++)
        {
           std::cout << " -> " << lista_nastepnikow[i].tablica_nastepnikow[j]->wierzcholek;
        }
        std::cout << std::endl;
    }
}

void wyswietl_graf_3(int liczba_wierzcholkow, int** macierz_sasiedztwa)
{
    for(int i = 0; i < liczba_wierzcholkow; i++)
    {
        for(int j = 0; j < liczba_wierzcholkow; j++)
        {
            std::cout << macierz_sasiedztwa[i][j] << "\t";
        }
        std::cout << std::endl;
    }
}



int main()
{
    int wybor;
    int liczba_wierzch = 0;
    int liczba_krawedzi = 0;
    int nasycenie = 0;
    struct Krawedz* lista_krawedzi;
    struct Nastepniki* lista_nastepnikow;
    int** macierz_sasiedztwa;
    while(wybor != 1 && wybor != 2)
    {
        std::cout << "1)Laduj graf z pliku, 2)Generuj graf: ";
        std::cin >> wybor;
        if(!std::cin)
        {
            std::cout << "Podano zle dane wejsciowe!" << std::endl;
            exit(0);
        }
    }
    if(wybor == 1)
    {
        laduj_graf(liczba_wierzch, liczba_krawedzi, lista_krawedzi);
    }
    else
    {
        std::cout << "Podaj liczbe wierzcholkow grafu: ";
        std::cin >> liczba_wierzch;
        if(!std::cin || liczba_wierzch <= 0)
        {
            std::cout << "Podano zle dane wejsciowe!" << std::endl;
            exit(0);
        }
        std::cout << "Podaj poziom nasycenia grafu (1-100%): ";
        std::cin >> nasycenie;
        if(!std::cin || nasycenie < 1 || nasycenie > 100)
        {
            std::cout << "Podano zle dane wejsciowe!" << std::endl;
            exit(0);
        }
        generuj_graf(liczba_wierzch, nasycenie, lista_krawedzi, liczba_krawedzi);
    }
    wyswietl_graf(liczba_krawedzi, lista_krawedzi);
    krawedzie_do_nastepniki(liczba_wierzch, liczba_krawedzi, lista_krawedzi, lista_nastepnikow);
    wyswietl_graf_2(liczba_wierzch, lista_nastepnikow);
    krawedzie_do_macierz(liczba_wierzch, liczba_krawedzi, lista_krawedzi, macierz_sasiedztwa);
    wyswietl_graf_3(liczba_wierzch, macierz_sasiedztwa);
    delete [] *macierz_sasiedztwa;
    delete [] lista_krawedzi;
    delete [] lista_nastepnikow;
    return 0;
}