A10

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <windows.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>

using namespace std;
#define MAX 21

// string wczytujacy z pliku
string wcz;

// wyswietla liste
void wyswietlListe(vector<vector<int>> lista, int liczbaWierzcholkow)
{
    cout << endl;
    for (int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        cout << i;

        if (lista[i].size() == 0)
        {
            cout << " -";
        }
        else
        {
            for (int j : lista[i])
            {
                cout << " -> " << j;
            }
        }
        cout << endl;
    }
    cout << endl;
}

// wyswietla macierz
void wyswietlMacierz(vector<vector<int>> macierz, int liczbaWierzcholkow)
{
    cout << endl << "    ";

    for(int i = 1; i < 10; i++)
    {
        cout << i << "   ";
    }

    for(int i = 10; i <= liczbaWierzcholkow; i++)
    {
        cout << i << "  ";
    }

    cout << endl << "   -";

    for(int i = 0; i < liczbaWierzcholkow; i++)
    {
        cout << "----";
    }

    cout << endl;

    for (int i = 1; i < liczbaWierzcholkow+1; i++)
    {
        if(i >= 10)
        {
            cout << i << "| ";
        }
        else
        {
        cout << i << " | ";
        }

        for (int j = 1; j < liczbaWierzcholkow+1; j++)
        {
            cout << macierz[i][j] << "   ";
        }
        cout << endl;
    }
    cout << endl;
}

// dlugosc stringa
int len(string wcz)
{
    int dlugosc = 0;
    for (int i = 0; wcz[i] != '\0'; i++)
    {
        dlugosc++;
    }
    return dlugosc;
}

// dzielenie stringa
vector<int> dzielenie(string wcz, char separator)
{
    vector <int> temp;
    int obecnyIndex = 0, i = 0;
    int poczIndex = 0, koncowyIndex = 0;
    while (i <= len(wcz))
    {
        if (wcz[i] == separator || i == len(wcz))
        {
            koncowyIndex = i;
            string dodatkowystring = "";
            dodatkowystring.append(wcz, poczIndex, koncowyIndex - poczIndex);
            temp.push_back(stoi(dodatkowystring));
            obecnyIndex++;
            poczIndex = koncowyIndex + 1;
        }
        i++;
    }
    return temp;
}

vector<vector<int>> wczytaj(char separator, vector<vector<int>> &macierz, vector<vector<int>> &lista, int &liczbaWierzcholkow)
{
    string fileName;
    string fullFileName;
    liczbaWierzcholkow = 0;

    cout << endl << "PODAJ NAZWE PLIKU: ";
    getline(cin >> ws, fileName);
    //fullFileName = "C:\\Users\\Patryk\\Desktop\\" + fileName + ".txt";
    fullFileName =  fileName + ".txt";
    // fullFileName =  "3.txt";

    ifstream file;
	file.open(fullFileName, ios::in);

    if (file.is_open() == false)
	{
		cout << "TAKI PLIK NIE ISTNIEJE" << endl;
        cout << "ZAKONCZONO PRACE PROGRAMU";
		exit(0);
	}

    while (!file.eof())
	{
		getline(file, wcz);
        liczbaWierzcholkow++;
        vector<int> wczytane = dzielenie(wcz, separator);

        for (int i = 1; i < wczytane.size(); i++ )
        {
            lista[wczytane[0]].push_back(wczytane[i]);
            macierz[wczytane[0]][wczytane[i]]++;
        }
	}
    file.close();
    return macierz;
}

void zapisz(vector<vector<int>> lista, int liczbaWierzcholkow)
{
    string fileName;
    string fullFileName;

    cout << endl << "PODAJ NAZWE PLIKU: ";
    getline(cin >> ws, fileName);
  //fullFileName = "C:\\Users\\Patryk\\Desktop\\" + fileName + ".txt";
    fullFileName = fileName + ".txt";

    fstream file;
	file.open(fullFileName, ios::out);

    for (int i = 1; i < liczbaWierzcholkow+1; i++)
    {
        file << i;

        for (auto j : lista[i])
        {
            file << "," << j;
        }

        if(i == liczbaWierzcholkow)
        {
            break;
        }
        else
        {
            file << endl;
        }
    }
    file.close();
}

bool jedenGraf(vector<vector<int>> macierz, int liczbaWierzcholkow)
{
    for(int i = 1; i < liczbaWierzcholkow +1; i++)
    {
        for(int j= 1; j< liczbaWierzcholkow + 1; j++)
        {
            if(macierz[i][j] > 1)
            {
                return false;
            }
        }
    }
    return true;
}

bool sprzezenie(vector<vector<int>> macierz, int liczbaWierzcholkow)
{
    for(int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        for(int j = i+1; j < liczbaWierzcholkow + 1; j++)
        {
            if(!(macierz[i] == macierz[j]))
            {
                for(int k = 1; k < liczbaWierzcholkow + 1; k++)
                {
                    if(macierz[i][k] && macierz[j][k])
                    {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

void wyswietlWektor(const vector<int> &macierz)
{
    for (auto wartosc : macierz)
    {
        cout << wartosc << " ";
    }
    cout << endl;
}

bool liniowy(vector<vector<int>> macierz, int liczbaWierzcholkow)
{
    for(int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        for(int j = i + 1; j < liczbaWierzcholkow + 1; j++)
        {
            bool A = true;
            bool B = false;
            bool C = true;

            if(macierz[i] == macierz[j])
            {
                B = true;
            }

            for(int k = 1; k <liczbaWierzcholkow + 1; k++)
            {
                if(macierz[i][k] && macierz[j][k])
                {
                    A = false;
                }
                if(macierz[k][i] && macierz[k][j])
                {
                    C = false;
                }
            }
            if(!(A || (B && C)))
            {
                return false;
            }
        }
    }
    return true;
}

vector<vector<int>> transformacja(vector<vector<int>> macierz, int liczbaWierzcholkow)
{
    int licznik = 1;
    int licznikIndexowania = 1;
    int licznikSortowania = 0;
    int tempC = 0;
    vector<int> tablicaDoSortowania;
    vector<vector<int>> tablicaWierzcholkow(MAX);
    vector<vector<int>> listaTransformacja(MAX);
    vector<vector<int>> kopiaListy(MAX);

    // tworzy luki dotyczace wierzcholkow

    for(int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        tablicaWierzcholkow[i].push_back(licznik);
        tablicaWierzcholkow[i].push_back(licznik + 1);
        licznik += 2;
    }

    for(int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        for(int j = 1; j < liczbaWierzcholkow + 1; j++)
        {
            if(macierz[i][j] ==  1)
            {
                int tempA = tablicaWierzcholkow[j][0]; // zawiera liczbe jaka mial wierzcholek przed zmiana
                int tempB = tablicaWierzcholkow[i][1]; // zawiera liczbe na jaka musi zmienic sie wierzcholek

                tablicaWierzcholkow[j][0] = tablicaWierzcholkow[i][1];

                for(int k = 1; k < liczbaWierzcholkow + 1; k++)
                {
                    if(tablicaWierzcholkow[k][0] == tempA)
                    {
                        tablicaWierzcholkow[k][0] = tempB;
                    }

                    if(tablicaWierzcholkow[k][1] == tempA)
                    {
                        tablicaWierzcholkow[k][1] = tempB;
                    }
                }
            }
        }
    }

    kopiaListy = tablicaWierzcholkow;

    for(int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        tablicaDoSortowania.push_back(tablicaWierzcholkow[i][0]);
        tablicaDoSortowania.push_back(tablicaWierzcholkow[i][1]);
    }

    sort(tablicaDoSortowania.begin(), tablicaDoSortowania.end());
    tablicaDoSortowania.erase(unique(tablicaDoSortowania.begin(), tablicaDoSortowania.end()), tablicaDoSortowania.end());

    for(int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        for(int j = 1; j < liczbaWierzcholkow + 1; j++)
        {
            if(tablicaWierzcholkow[j][0] == tablicaDoSortowania[licznikSortowania])
            {
                tablicaWierzcholkow[j][0] = licznikIndexowania;
            }
            if(tablicaWierzcholkow[j][1] == tablicaDoSortowania[licznikSortowania])
            {
                tablicaWierzcholkow[j][1] = licznikIndexowania;
            }
        }
        licznikSortowania++;
        licznikIndexowania++;
    }

    for(int i = 1; i < liczbaWierzcholkow + 1; i++)
    {
        listaTransformacja[tablicaWierzcholkow[i][0]].push_back(tablicaWierzcholkow[i][1]);
    }

    return listaTransformacja;
}


int main()
{
    // liczenie wierzcholkow
    int liczbaWierzcholkow = 0;

    char separator = ',';
    char menu = '1';
    char menuwpis[5];
    int dlugoscmenu;

    vector<vector<int>> listsasiedztwa(MAX);
    vector<vector<int>> macierzsasiedztwa(MAX);
    vector<vector<int>> listasasiedztwaTransformacja(MAX);

    // uzupelnienie macierzy 0

    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            macierzsasiedztwa[i].push_back(0);
        }
    }

    while (menu != 'X')
    {

        cout << endl << "----------------------------------------" << endl;
        cout << "MENU GLOWNE:" << endl << endl;
        cout << "1 - WCZYTAJ GRAF" << endl;
        cout << "2 - ZAPISZ GRAF" << endl;
        cout << "3 - WYSWIETL LISTE NASTEPNIKOW" << endl;
        cout << "4 - WYSWIETL MACIERZ SASIEDZTWA" << endl;
        cout << "5 - ALGORYTM" << endl;
        cout << "X - ZAKONCZ DZIALANIE PROGRAMU" << endl;
        cout << "----------------------------------------" << endl << endl;

        fflush(stdin);
        cin >> menuwpis;

        dlugoscmenu = strlen(menuwpis);

        if (dlugoscmenu > 1)
        {
            cout << "WYBRANO NIEISTNIEJACY TRYB - SPROBUJ PONOWNIE";
            continue;
        }
        else
        {
            menu = menuwpis[0];
        }

        switch (menu)
        {
            case '1':
                wczytaj(separator, macierzsasiedztwa, listsasiedztwa, liczbaWierzcholkow);
                cout << endl << "WCZYTANO POMYSLNIE GRAF" << endl;
                break;

            case '2':
                zapisz(listsasiedztwa, liczbaWierzcholkow);
                cout << endl << "POMYSLNIE ZAPISANO GRAF" << endl;
                break;

            case '3':
                cout << endl << "LISTA NASTEPNIKOW:" << endl;
                wyswietlListe(listsasiedztwa, liczbaWierzcholkow);
                break;

            case '4':
                cout << endl << "MACIERZ SASIEDZTWA:" << endl;
                wyswietlMacierz(macierzsasiedztwa, liczbaWierzcholkow);
                break;

            case '5':
                if(jedenGraf(macierzsasiedztwa, liczbaWierzcholkow))
                {
                    cout << endl << "TEN GRAF JEST 1-GRAFEM";
                    if(sprzezenie(macierzsasiedztwa, liczbaWierzcholkow))
                    {
                        cout << endl << "TEN GRAF JEST SPRZEZONY ";
                        if(liniowy(macierzsasiedztwa,liczbaWierzcholkow))
                        {
                            cout << "I LINIOWY";
                        }
                        else
                        {
                            cout << "I NIE JEST LINIOWY";
                        }

                        listasasiedztwaTransformacja = transformacja(macierzsasiedztwa, liczbaWierzcholkow);
                        cout << endl << "TRANSFORMACJA PRZEBIEGLA POMYSLNIE";

                        cout << endl << "GRAF ORYGINALNY:"; // POPRAWIC ZAPIS
                        wyswietlListe(listasasiedztwaTransformacja, liczbaWierzcholkow);
                    }
                    else
                    {
                        cout << endl << "TEN GRAF NIE JEST SPRZEZONY I NIE JEST LINIOWY";
                    }
                }
                else
                {
                    cout << endl << "TEN GRAF NIE JEST 1-GRAFEM, WIEC NIE JEST SPRZEZONY I NIE JEST LINIOWY";
                }
                break;

            case 'X':
                printf("\nZAKONCZONO PRACE PROGRAMU\n");
                break;

            case 'x':

                printf("\nZAKONCZONO PRACE PROGRAMU\n");
                return 0;

            default:
                printf("\nWYBRANO NIEISTNIEJACY TRYB - SPROBUJ PONOWNIE\n");
                break;
        }
    }

	return 0;
}