//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 */