Graphs(3 sem.)

//1. в заголовках создать два файла - Paths.h и Graph.h, закинуть в них код
//2. создать исходные файлы Paths.cpp и Graph.cpp, закинуть в них код
//3. создать файл GraphLab.cpp, закинуть в него код. Это файл с main
// лаба готова :)

                                                        /* Paths.h file start */

#pragma once
#include <vector>

class Paths
{
public:
    struct DistancePoint
    {
        int m_point;
        int m_distancePrev;
    };

    struct Path
    {
        std::vector<DistancePoint> m_points;
        int m_length;
    };

private:
    std::vector<Path> m_paths;

public:
    static void printPath(const Path& path);

    Paths(const Paths& paths);

    Paths();

    const Paths& operator=(const Paths& paths);

    Path& operator[](const int index);

    void addPath(const Path& path);

    void clear();

    int getLength();

    void insertInFront(const int pathIndex, const DistancePoint& distancePoint);

    void sort();

    void printPaths();

};

                                                /* Paths.h file end */


                                                /* Graph.h file start */

#pragma once
#include <vector>
#include <algorithm>
#include "Paths.h"
#define INFINITY_GRAPH INT_MAX

class Graph
{
private:
    std::vector<std::vector<int>> m_adjacencyMatrix;

    //Recursive function which returns all paths from point v to point x
    Paths findPathPrivate(const std::vector<std::vector<int>>& a, std::vector<bool>& visited, int n, int v, int x, int currentPathLength, Paths& paths, Paths::Path& currentPath);

    //Returns minimum distance from all unvisited vertices to current
    int minDist(const std::vector<int>& dist, const std::vector<bool>& tSet);

public:
    //Initialize adjacency matrix from parameter with 0(MACHINE INFINITY)
    static void initGraph(std::vector<std::vector<int>>& adjacencyMatrix);

    //Constructor copy adjacency matrix from parameter to class field
    Graph(const std::vector<std::vector<int>>& adjacencyMatrix);

    //This function calls recursive function findPathPrivate, but prepare all parameters to simplify usage for developer
    Paths findAllPaths(const int startPoint, const int finishPoint);

    //Function finds shortest path between two points
    Paths::Path findShortestPath(const int startPoint, const int finishPoint);

    //Function finds longest path between two points
    Paths::Path findLongestPath(const int startPoint, const int finishPoint);

    //Finds graph center
    int findCenter();

    //Prints adjacency matrix, that represents graph
    void print_adjacencyMatrix();
};

                                                    /* Graph.h file end */


                                                    /* Paths.cpp file start */

#include "Paths.h"

void Paths::printPath(const Path& path)
{
    if (path.m_points.size())
    {
        printf("<%d>", path.m_points[0].m_point + 1);
        for (int j = 1; j < path.m_points.size(); ++j)
            printf("  (%d)->  <%d>", path.m_points[j].m_distancePrev, path.m_points[j].m_point + 1);
        printf("  Количество точек: %d, Длина: %d", (int)path.m_points.size(), path.m_length);
        printf("\n");
    }
}

Paths::Paths(const Paths& paths)
{
    this->m_paths = paths.m_paths;
}

Paths::Paths()
{
    m_paths.resize(0);
}

const Paths& Paths::operator=(const Paths& paths)
{
    this->m_paths = paths.m_paths;
    return *this;
}

Paths::Path& Paths::operator[](const int index)
{
    return m_paths[index];
}

void Paths::addPath(const Path& path)
{
    m_paths.push_back(path);
}

void Paths::clear()
{
    m_paths.resize(0);
}

int Paths::getLength()
{
    return m_paths.size();
}

void Paths::insertInFront(const int pathIndex, const DistancePoint& distancePoint)
{
    m_paths[pathIndex].m_points.insert(m_paths[pathIndex].m_points.begin(), distancePoint);
}

void Paths::sort()
{
    for (int i = 1; i < m_paths.size(); ++i)
        for (int j = 0; j < m_paths.size() - i; ++j)
            if (m_paths[j].m_length > m_paths[j + 1].m_length)
            {
                Path temp = m_paths[j];
                m_paths[j] = m_paths[j + 1];
                m_paths[j + 1] = temp;
            }
}

void Paths::printPaths()
{
    int i{ 1 };
    for (const Path& path : m_paths)
    {
        printf("Path #%d: ", i);
        this->printPath(path);
        ++i;
    }
}

                                                    /* Paths.cpp file end */

                                                    /* Graph.cpp file start */

#include "Graph.h"

Paths Graph::findPathPrivate(const std::vector<std::vector<int>>& a, std::vector<bool>& visited, int n, int v, int x, int currentPathLength, Paths& paths, Paths::Path& currentPath)
{
    //static Paths paths;
    //static Paths::Path currentPath;
    if (v == x) {
        currentPath.m_length = currentPathLength;
        paths.addPath(currentPath);
        return paths;
    }

    visited[v] = true;
    for (int i = 0; i < n; ++i)
        if (/*a[v][i]*/ a[v][i] != INFINITY_GRAPH && !visited[i])
        {
            currentPath.m_points.push_back({i, a[v][i]});
            currentPathLength += a[v][i];
            findPathPrivate(a, visited, n, i, x, currentPathLength, paths, currentPath);
            currentPath.m_points.pop_back();
            currentPathLength -= a[v][i];
        }
    visited[v] = false;
    return paths;
}

int Graph::minDist(const std::vector<int>& dist, const std::vector<bool>& tSet)
{

    int min = INT_MAX, index{ 0 };

    for (int i = 0; i < m_adjacencyMatrix.size(); ++i)
    {
        if (tSet[i] == false && dist[i] <= min)
        {
            min = dist[i];
            index = i;
        }

    }

    return index;
}

void Graph::initGraph(std::vector<std::vector<int>>& adjacencyMatrix)
{
    for (int i = 0; i < adjacencyMatrix.size(); ++i)
    {
        std::fill(adjacencyMatrix[i].begin(), adjacencyMatrix[i].end(), INFINITY_GRAPH);
        adjacencyMatrix[i][i] = 0;
    }
}

Graph::Graph(const std::vector<std::vector<int>>& adjacencyMatrix)
{
    m_adjacencyMatrix = adjacencyMatrix;
}

Paths Graph::findAllPaths(const int startPoint, const int finishPoint)
{
    std::vector<bool> visited{};
    visited.resize(m_adjacencyMatrix.size());
    Paths paths;
    Paths::Path currentPath;
    paths = this->findPathPrivate(m_adjacencyMatrix, visited, visited.size(), startPoint, finishPoint, 0, paths, currentPath);
    for (int i = 0; i < paths.getLength(); ++i)
        paths.insertInFront(i, { startPoint, 0});
    paths.sort();
    return paths;
}

Paths::Path Graph::findShortestPath(const int startPoint, const int finishPoint)
{
    std::vector<int> dist; // integer array to calculate minimum distance for each node.
    dist.resize(m_adjacencyMatrix.size());
    std::fill(dist.begin(), dist.end(), /*INT_MAX*/INFINITY_GRAPH);
    std::vector<bool> tSet;// boolean array to mark visted/unvisted for each node.
    tSet.resize(m_adjacencyMatrix.size());
    std::fill(tSet.begin(), tSet.end(), false);

    dist[startPoint] = 0;

    for (int i = 0; i < dist.size(); ++i)
    {
        int m = minDist(dist, tSet); // vertex not yet included.
        tSet[m] = true;// m with minimum distance included in Tset.
        for (int i = 0; i < dist.size(); ++i)
        {
            // Updating the minimum distance for the particular node.
            if (!tSet[i] && /*m_adjacencyMatrix[m][i]*/ m_adjacencyMatrix[m][i] != INFINITY_GRAPH && dist[m] != /*INT_MAX*/INFINITY_GRAPH && dist[m] + m_adjacencyMatrix[m][i] < dist[i])
                dist[i] = dist[m] + m_adjacencyMatrix[m][i];
        }
    }

    Paths::Path path;
    if (dist[finishPoint] != /*INT_MAX*/INFINITY_GRAPH)
    {
        int current{ finishPoint };
        while (current != startPoint)
            for (int i = 0; i < m_adjacencyMatrix.size(); ++i)
                if (dist[current] - m_adjacencyMatrix[i][current] == dist[i] && m_adjacencyMatrix[i][current] != 0)
                {
                    path.m_points.push_back({ current, m_adjacencyMatrix[i][current] });
                    current = i;
                    break;
                }
        path.m_points.push_back({ startPoint, 0 });
        path.m_length = dist[finishPoint];
        reverse(path.m_points.begin(), path.m_points.end());
    }
    return path;
}

Paths::Path Graph::findLongestPath(const int startPoint, const int finishPoint)
{
    Paths paths = findAllPaths(startPoint, finishPoint);
    if (paths.getLength())
        return paths[paths.getLength() - 1];
    return Paths::Path();
}

int Graph::findCenter()
{
    std::vector<std::vector<int>> m_adjacencyMatrixCopy{ m_adjacencyMatrix };
    //Floyd algorithm
    for (int k = 0; k < m_adjacencyMatrixCopy.size(); ++k)
        for (int i = 0; i < m_adjacencyMatrixCopy.size(); ++i)
            for (int j = 0; j < m_adjacencyMatrixCopy.size(); ++j)
                if (m_adjacencyMatrixCopy[i][k] != INFINITY_GRAPH && m_adjacencyMatrixCopy[k][j] != INFINITY_GRAPH)
                    m_adjacencyMatrixCopy[i][j] = std::min(m_adjacencyMatrixCopy[i][j], m_adjacencyMatrixCopy[i][k] + m_adjacencyMatrixCopy[k][j]);

    //Find eccentricitys
    std::vector<int> eccentricitys;
    for (int i = 0; i < m_adjacencyMatrixCopy.size(); ++i)
    {
        int max{ 0 };
        for (int j = 0; j < m_adjacencyMatrixCopy.size(); ++j)
            if (m_adjacencyMatrixCopy[j][i] > max)
                max = m_adjacencyMatrixCopy[j][i];
        eccentricitys.push_back(max);
    }

    //Return lowest eccentricity
    //return *std::min_element(eccentricitys.begin(), eccentricitys.end());
    int minIndex{ 0 };
    for (int i = 1; i < eccentricitys.size(); ++i)
        if (eccentricitys[i] < eccentricitys[minIndex])
            minIndex = i;
    return minIndex;
}

void Graph::print_adjacencyMatrix()
{
    for (int i = 0; i < m_adjacencyMatrix.size(); ++i)
    {
        for (int j = 0; j < m_adjacencyMatrix.size(); ++j)
        {
            if (m_adjacencyMatrix[i][j] == INFINITY_GRAPH)
                printf("%7s", " inf");
            else
                printf(" %5d ", m_adjacencyMatrix[i][j]);
        }
        printf("\n");
    }
}

                                                    /* Graph.cpp file end */

                                                    /* GraphLab.cpp(main) file start */

#include <iostream>
#include "Graph.h"
#include "Paths.h"

void createGraph1(std::vector<std::vector<int>>& mtrx1)
{
    const int verticesNum{ 5 };
    mtrx1.resize(verticesNum);
    for (int i = 0; i < verticesNum; ++i)
        mtrx1[i].resize(verticesNum);
    Graph::initGraph(mtrx1);
    mtrx1[0][1] = 10;
    mtrx1[0][3] = 30;
    mtrx1[0][4] = 100;
    mtrx1[1][2] = 50;
    mtrx1[2][4] = 10;
    mtrx1[3][2] = 20;
    mtrx1[3][4] = 60;
}

void createGraph2(std::vector<std::vector<int>>& mtrx2)
{
    const int verticesNum{ 7 };
    mtrx2.resize(verticesNum);
    for (int i = 0; i < verticesNum; ++i)
        mtrx2[i].resize(verticesNum);
    Graph::initGraph(mtrx2);


    mtrx2[0][1] = 10;
    mtrx2[1][2] = 1;
    mtrx2[1][4] = 10;
    mtrx2[2][5] = 2;
    mtrx2[3][0] = 10;
    mtrx2[3][1] = 10;
    mtrx2[3][2] = 10;
    mtrx2[4][6] = 4;
    mtrx2[5][4] = 3;
    mtrx2[5][3] = 10;
    mtrx2[6][5] = 10;
}

void createGraph3(std::vector<std::vector<int>>& mtrx3)
{
    const int verticesNum{ 5 };
    mtrx3.resize(verticesNum);
    for (int i = 0; i < verticesNum; ++i)
        mtrx3[i].resize(verticesNum);
    Graph::initGraph(mtrx3);


    mtrx3[0][1] = 1;
    mtrx3[1][2] = 2;
    mtrx3[3][1] = 1;
    mtrx3[3][2] = 3;
    mtrx3[4][3] = 5;
    mtrx3[2][4] = 4;
    mtrx3[2][3] = 2;
}

int main()
{
    setlocale(LC_ALL, "Russian");
    int mtrxNum{ 0 };
    std::cout << "Введите номер графа для загрузки(доступно 3): ";
    std::cin >> mtrxNum;
    std::vector<std::vector<int>> mtrx;
    switch (mtrxNum)
    {
    case 1:
        createGraph1(mtrx);
        break;
    case 2:
        createGraph2(mtrx);
        break;
    case 3:
        createGraph3(mtrx);
        break;
    default:
        exit(0);
    }

    Graph graph{ mtrx };

    int start{ 0 };
    int finish{ 0 };
    std::cout << "Введите начальную точку: ";
    std::cin >> start;
    std::cout << "Введите конечную точку: ";
    std::cin >> finish;
    --start;
    --finish;

    printf("Матрица смежности графа:\n");
    graph.print_adjacencyMatrix();

    Paths paths;

    paths = graph.findAllPaths(start, finish);
    if (paths.getLength())
    {
        printf("\n\n\n");
        printf("Все пути в графе от точки %d до точки %d по возрастанию длины:\n", start + 1, finish + 1);
        paths.printPaths();
        printf("\n\n");


        printf("\n");
        Paths::Path path;

        printf("Кратчайший путь: ");
        path = graph.findShortestPath(start, finish);
        Paths::printPath(path);

        printf("\n");
        printf("Длиннейший путь: ");
        path = graph.findLongestPath(start, finish);
        Paths::printPath(path);
    }
    else
        printf("\nВершина %d недостижима из вершины %d", finish + 1, start + 1);

    printf("\n");
    printf("\nЦентр графа: %d\n",graph.findCenter() + 1);
}

                                                        /* GraphLab main file end */