#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <list>
#include <iomanip>

using namespace std;


int inputIntegerNumber(const int MIN_NUMBER, const int MAX_NUMBER) {
    bool IsIncorrect;
    int Number;
    string Input = "";

    do {
        getline(cin, Input);
        IsIncorrect = false;
        try {
            Number = stoi(Input);
        }
        catch (invalid_argument ex) {
            cout << "Введите число:\n";
            IsIncorrect = true;
        }
        catch (out_of_range ex) {
            cout << "Число не должно быть меньше " << MIN_NUMBER << " и больше, чем "
                << MAX_NUMBER << "\n";
            IsIncorrect = true;
        }
        if (!IsIncorrect && (Number <  MIN_NUMBER || Number > MAX_NUMBER)) {
            cout << "Число не должно быть меньше " << MIN_NUMBER << " и больше, чем "
                << MAX_NUMBER << "\n";
            IsIncorrect = true;
        }
    } while (IsIncorrect);

    return Number;
}

bool checkFile(const string PathToFile) {
    bool Flag = true;
    int CurrentNumber, NumberOfLines;
    NumberOfLines = 0;
    string Buffer;
    ifstream InputFile(PathToFile);
    while ((Flag) && (!InputFile.eof())) {
        getline(InputFile, Buffer);
        for (int i = 0; (i < Buffer.length()) && (Flag); i++)
            if ((Buffer[i] != ' ') && (Buffer[i] != '(') && (Buffer[i] != ')') && (((int)Buffer[i] < (int)'0') || (int)Buffer[i] > (int)'9')) {
                Flag = false;
                cout << "Некорректные символы в файле.\n";
            }
        NumberOfLines++;
    }
    if (Flag) {
        InputFile.seekg(0, ios_base::beg);
        InputFile >> CurrentNumber;
        if (CurrentNumber != (NumberOfLines - 1)) {
            cout << "Неверное количество вершин.\n";
            Flag = false;
        }
    }
    InputFile.close();
    return Flag;
}

bool checkPermissionForWriting(const string& PathToFile) {
    bool Flag;
    ofstream FileOut(PathToFile);

    if (FileOut.is_open()) {
        FileOut.close();
        Flag = true;
    }
    else {
        cout << "Файл не доступен для записи.\n";
        Flag = false;
    }

    return Flag;
}


bool checkExtension(const string& PathToFile) {
    const string extension = "txt";
    bool Flag;

    if (PathToFile.length() > 4 && PathToFile.substr(PathToFile.length() - 3) == extension) {
        Flag = true;
    }
    else {
        cout << "Неверное расширение.\n";
        Flag = false;
    }

    return Flag;
}

bool checkPermissionForReading(const string& PathToFile) {
    bool Flag;
    ifstream FileIn(PathToFile);
    if (FileIn.is_open()) {
        FileIn.close();
        Flag = true;
    }
    else {
        cout << "Файл не доступен для чтения.\n";
        Flag = false;
    }
    return Flag;
}

const string inputPathToFileForReading() {
    string PathToFile;
    do {
        cout << "Введите путь к файлу для чтения:\n";
        getline(cin, PathToFile);
    } while (!checkExtension(PathToFile) || !checkPermissionForReading(PathToFile) || !checkFile(PathToFile));
    return PathToFile;
}

const string inputPathToFileForWriting() {
    string PathToFile;
    do {
        cout << "Введите путь к файлу для записи: \n";
        getline(cin, PathToFile);
    } while (!checkExtension(PathToFile) || !checkPermissionForWriting(PathToFile));
    return PathToFile;
}

struct TVertex {
    int number;
    int dist;
};

typedef vector<list<TVertex>> TListArray;
typedef vector<vector<int>> TMatrix;


void printListArray(TListArray& ListArray) {
    cout << "Списки инцидентности:\n";
    for (int i = 0; i < ListArray.size(); i++) {
        cout << i + 1 << ": ";
        for (auto Iterator : ListArray[i])
            cout << "->" << Iterator.number << '(' << Iterator.dist << ')';
        cout << '\n';
    }
}

void printIncidentMatrix(TMatrix& IncidentMatrix) {
    cout << "Матрица инциденций:\n" << "   ";
    for (int i = 0; i < IncidentMatrix[0].size(); i++) {
        cout << setw(2) << (char)(i + 97) << ' ';
    }
    cout << '\n';
    for (int i = 0; i < IncidentMatrix.size(); i++) {
        cout << i + 1 << ": ";
        for (int j = 0; j < IncidentMatrix[i].size(); j++)
            cout << setw(2) << IncidentMatrix[i][j] << " ";
        cout << '\n';
    }
    cout << '\n';
}

void addVertex(TListArray &ListArray, TVertex CurrentVertex, int Index) {
    ListArray[Index].push_back(CurrentVertex);
}

vector<TVertex> getVertices(string Buffer) {
    vector<TVertex> Vertices;
    TVertex CurrentVertex;
    string Number, Dist;
    int j;
    for (int i = 1; i < Buffer.size(); i++) {
        if (Buffer[i] != ' ') {
            j = i;
            while ((Buffer[j] != '(') && j < Buffer.size())
                Number += Buffer[j++];
            j++;
            while (Buffer[j] != ')' && j < Buffer.size())
                Dist += Buffer[j++];
            if (Number != "") {
                CurrentVertex.number = stoi(Number);
                CurrentVertex.dist = stoi(Dist);
                Vertices.push_back(CurrentVertex);
            }
            i = j;
            i++;
            Number = "";
            Dist = "";
        }
    }
    return Vertices;
}

void readFormFile(TListArray& ListArray, string PathToFile) {
    int NumberOfVertices, VertexNumber, i;
    string Buffer = "";
    vector<TVertex> Vertices;
    i = -1;
    ifstream FileIn(PathToFile);
    FileIn >> NumberOfVertices;
    ListArray.resize(NumberOfVertices);
    while (!FileIn.eof()) {
        getline(FileIn, Buffer);
        Vertices = getVertices(Buffer);
        for (int j = 0; j < Vertices.size(); j++)
            addVertex(ListArray, Vertices[j], i);
        i++;
    }
    FileIn.close();
}

TVertex inputVertex(int WrongNumber, int MaxIndexOfVertices) {
    TVertex CurrentVertex;
    bool IsIncorrect = true;
    int VertexNumber, Dist;
    do {
        cout << "Введите номер следующей инцидентной вершины: ";
        VertexNumber = inputIntegerNumber(1, MaxIndexOfVertices);
        if (VertexNumber == WrongNumber) {
            IsIncorrect = true;
            cout << "Текущая вершина не может быть инцидентна данной.\n";
        }
        else{
            IsIncorrect = false;
            cout << "Введите расстояние до данной вершины: ";
            Dist = inputIntegerNumber(-30, 30);
            CurrentVertex.number = VertexNumber;
            CurrentVertex.dist = Dist;
        }
        cout << '\n';
    } while (IsIncorrect);
    return CurrentVertex;
}

void receiveListReprezentation(TListArray& ListArray) {
    int NumberOfVertices, VertexNumber, CurrentNumberOfVertices;
    TVertex Vertex;
    cout << "Введите количество вершин:\n";
    NumberOfVertices = inputIntegerNumber(1, 15);
    ListArray.resize(NumberOfVertices);
    for (int i = 0; i < NumberOfVertices; i++) {
        cout << "Введите количество вершин, смежных с вершиной " << i + 1 << ":\n";
        CurrentNumberOfVertices = inputIntegerNumber(0, NumberOfVertices - 1);
        for (int j = 0; j < CurrentNumberOfVertices; j++) {
            Vertex = inputVertex(i + 1, NumberOfVertices);
            addVertex(ListArray, Vertex,  i);
        }
    }
}

void receiveGraph(TListArray& ListArray) {
    char Answer = 'q';
    cout << "Введите '1', если хотите считать из файла. '2' - из консоли.\n";
    do {
        cin >> Answer;
        cin.ignore(256, '\n');
        if (Answer == '1') {
            string PathToFile = inputPathToFileForReading();
            readFormFile(ListArray, PathToFile);
            cout << "Граф получен.\n";
        }
        else
            if (Answer == '2') {
                receiveListReprezentation(ListArray);
                cout << "Граф получен.\n";
            }
            else
                cout << "Введите '1' или '2'.\n";
    } while ((Answer != '1') && (Answer != '2'));
}


void receiveAdjacencyMatrix(TListArray& ListArray, TMatrix& AdjacencyMatrix){
    for (int i = 0; i < ListArray.size(); i++) {
        for (auto const& Iterator : ListArray[i]) {
            AdjacencyMatrix[i][Iterator.number - 1] = Iterator.dist;
        }
    }
}

void receiveResultMatrices(TMatrix& AdjacencyMatrix, TMatrix& DistMatrix, TMatrix& PrecMatrix) {
    int NewDist;
    for (int i = 0; i < AdjacencyMatrix.size();  i++) {
        DistMatrix[i][i] = 0;
        for (int j = 0; j < AdjacencyMatrix.size(); j++)
            if (AdjacencyMatrix[i][j]) {
                DistMatrix[i][j] = AdjacencyMatrix[i][j];
                PrecMatrix[i][j] = i;
            }
    }
    for (int t = 0; t < AdjacencyMatrix.size(); t++) {
        for (int i = 0; i < AdjacencyMatrix.size(); i++) {
            for (int j = 0; j < AdjacencyMatrix.size(); j++) {
                if (DistMatrix[i][t] < INT_MAX && DistMatrix[t][j] < INT_MAX) {
                    NewDist = DistMatrix[i][t] + DistMatrix[t][j];
                    if (NewDist < DistMatrix[i][j]) {
                        DistMatrix[i][j] = NewDist;
                        PrecMatrix[i][j] = PrecMatrix[t][j];
                    }
                }
            }
        }
    }
}

void receiveGraphText(string& GraphText, TMatrix& AdjacencyMatrix, TMatrix& DistMatrix, TMatrix& PrecMatrix) {
    cout << "Введите номер вершины, для которой нужно найти кратчайшие пути:\n";
    int VertexNumber = inputIntegerNumber(0, (AdjacencyMatrix.size()) - 1);
    VertexNumber--;
    GraphText += "digraph G {";
    GraphText += "  node [shape=circle]";
    GraphText += "  {node [style=filled] ";
    GraphText += to_string(VertexNumber + 1);
    GraphText += "}";
    for (int i = 0; i < AdjacencyMatrix.size(); i++)
        for (int j = 0; j < AdjacencyMatrix.size(); j++)
            if (AdjacencyMatrix[i][j]) {
                GraphText += "  ";
                GraphText += to_string(i + 1);
                GraphText += " -> ";
                GraphText += to_string(j + 1);
                GraphText += " [label=";
                GraphText += "\"";
                GraphText += to_string(AdjacencyMatrix[i][j]) + "\"";
                if (i == PrecMatrix[VertexNumber][j])
                    GraphText += ",color=red";
                GraphText += "];";
            }
    GraphText += "}";
}

void receiveGraphImage(string& GraphText) {
    const char* COMAND_TEXT = " \"C:\\graphviz\\bin\\dot.exe\" - Tpng C:\\t\\k.gv - o C:\\Users\\user\\Desktop\\71с++\\Project1\\GraphsFiles\\picture.png";
    ofstream fout("C:\\t\\k.gv");
    fout << GraphText;
    fout.close();
    system(COMAND_TEXT);
    cout << "Изображение графа получено. Программа завершена.";
}

int main() {
    system("chcp 1251");
    TListArray ListArray;
    receiveGraph(ListArray);
    printListArray(ListArray);
    TMatrix AdjacencyMatrix(ListArray.size(), vector<int>(ListArray.size(), 0));
    receiveAdjacencyMatrix(ListArray, AdjacencyMatrix);
    TMatrix DistMatrix(AdjacencyMatrix.size(), vector<int>(AdjacencyMatrix.size(), INT_MAX));
    TMatrix PrecMatrix(AdjacencyMatrix.size(), vector<int>(AdjacencyMatrix.size(), INT_MAX));
    receiveResultMatrices(AdjacencyMatrix, DistMatrix, PrecMatrix);
    string GraphText;
    receiveGraphText(GraphText, AdjacencyMatrix, DistMatrix, PrecMatrix);
    receiveGraphImage(GraphText);
    return 0;
}