#include <iostream>

using namespace std;

const int n = 12; // кол-во вершин графа

// определение структуры для элемента стека
struct cell
{
	double value; // значение в элемента
	struct cell* next; // указатель на следующий элемент
};

// определение имени list для типа cell
typedef struct cell list;

// функция создания списка
list* modStack(double val)
{
	list* newStack; // создание указателя на новый список
	newStack = new list; // выделение памяти под новый список
	newStack->value = val; // запись в ячейку значения элемента списка
	newStack->next = NULL; // запись в ячейку указателя NULL на следующий элемент
	return(newStack);
}

// функция вывода содержимого стека на экран
void outputScreen(list* myStack)
{
	int pos = 0; // индекс позиции элемента в стеке
	list* tmp = myStack; // указатель на стек
	if (tmp == NULL)
	{
		std::cout << "Стек пустой или не создан\n";
	}
	else
	{
		std::cout << "\n";
		do
		{
			pos++; // увеличение индекса позиции на 1
			std::cout << "-[" << pos << "]" << "(" << tmp->value << ")-"; // форматированный вывод элементов стека
			tmp = tmp->next; //присвоение tmp указателя на следующий элемент стека
		} while (tmp != NULL);
	}

	std::cout << "\n";
	return;
}


// функция очистки стека
void clearList(list** myStack)
{
	list* tmp = *myStack; // указатель на первый элемент стека
	list* tmpNext = NULL; // указатель на следующий элемент стека
	if (tmp == NULL)
	{
		std::cout << "Невозможно очистить пустой или не созданный стек\n";
	}
	else
	{
		do
		{
			tmpNext = tmp->next; // присвоение указателя на следующий элемент
			delete tmp; // удаление указателя на текущий элемент
			tmp = tmpNext; // присвоение текущему указателю указателя на следующий элемент
		} while (tmp != NULL);
		*myStack = NULL; // обнуление указателя на стек
		std::cout << "Стек успешно очищен\n";
	}

	return;
}



// функция извлечения элемента стека на заданной позиции
int PopStack(list** myStack)
{
	int val;
	list* tmp = *myStack; // указатель на первый элемент стека
	list* tmpPrev = NULL; // указатель на предыдущий элемент стека
	int i = 1; // индексная переменная

	if (tmp == NULL) // указатель на первый элемент стека NULL
	{
		std::cout << "Невозможно извлечь элемент из пустого или не созданного стека\n";
	}
	else
	{
		if (tmp->next == NULL) // указатель на следующий элемент NULL
		{
			clearList(myStack); // удаление всего стека из 1 элемента
		}
		else
		{
			do
			{
				i++; // увеличение счетчика на 1
				tmpPrev = tmp; // присвоение указателю на предыдущий элемент указателя на текущий элемент
				tmp = tmp->next; // присвоение указателю на текущий элемент указателя на следующий элемент
			} while (tmp->next != NULL);
			val = tmp->value;

			tmpPrev->next = NULL; // указателю на следующий элемент для i-1 элемента присвоить указатель NULL
			delete tmp; // удаление указателя на извлеченный элемент
		}
	}
	return val;
}

// функция добавления элемента в стек
void PushStack(list** myStack, double val)
{
	list* tmp = *myStack; // указатель на первый элемент стека
	list* tmpPrev = NULL; // указатель на предыдущий элемент стека


	if (tmp == NULL)
	{
		*myStack = modStack(val); // создание стека с текущим элементом
		std::cout << "Новый стек успешно создан\n";
	}
	else
	{
		do
		{
			tmpPrev = tmp; // присвоение указателю на предыдущий элемент указателя на текущий элемент
			tmp = tmp->next; // присвоение указателю на текущий элемент указателя на следующий элемент
		} while (tmp != NULL); // указатель на текущий элемент NULL

		tmpPrev->next = modStack(val); // присвоение указателю предыдущего элемента на следующий элемент указателя на введенный элемент
	}

	std::cout << "Новый элемент со значением " << val << " добавлен в конец стека\n";
	return;
}


// функция топологичесской сортировки графа
void topological_s(int(*matrix)[n], int inf, list** next, int*& sorted)
{

	int i,j, k; // индексные переменные
	int u = 0; // номер рассматриваемой вершины
	int in_degree[n] = { 0 }; // массив входящих степеней вершин

	// заполнение массива входящих степеней вершин
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (matrix[i][j] != inf)
			{
				in_degree[j]++;
			}
		}
	}

	for (i = 0; i < n; i++)
	{
		if (in_degree[i] == 0)
		{
			PushStack(next, i);
		}
	}

	k = 0;
	// пока существую вершины с входящей степенью 0
	while (next != NULL)
	{
		u = PopStack(next); // выбор вершины для обработки из начала списка next
		sorted[k] = u; // запись вершины u в список sorted
		k++;

		// поиск вершин с входящей степенью 0 после ослабления графа
		for (i = 0; i < n; i++)
		{
			if (matrix[u][i] != inf)
			{
				in_degree[i]--;
				if (in_degree[i] == 0)
				{
					PushStack(next, i);
				}
			}
		}

	}
	return;
}


// поиск кратчайших путей
int* dag_shortest_path(int(*matrix)[n], int s, int inf, int *sorted)
{
	int* shortest = new int[n]; // массив весов кратчайших путей
	int* pred = new int[n]; // массив предыдущих вершин
	int i, j; // индексные переменные

	// инициализация массива shortest и pred
	for (i = 0; i < n; i++)
	{
		pred[i] = -1;
		if (i != s-1) shortest[i] = inf;
		else shortest[i] = 0;
	}

	// вычисление кратчайших путей из заданной вершины s
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if(matrix[sorted[i]][j] != inf) // если путь существует
			{
				if ((shortest[sorted[i]] + matrix[sorted[i]][j]) < shortest[j]) // новый вес пути меньше текущего
				{
					shortest[j] = shortest[sorted[i]] + matrix[sorted[i]][j]; // присвоить новый вес кратчайшего пути
					pred[j] = sorted[i];
				}
			}
		}
	}
	return shortest;
}

int main()
{
	setlocale(LC_ALL, "RUS");

	int s = 0; // вершина для поиска критического пути
	int inf = 10000; // бесконечно большая величина
	int* shrt; // указатель на массив кратчайших путей
	int i = 0; // счетчик
	bool print_f = 1; // флаг печати доп. информации
	int* sorted = new int [n];
	list* next = NULL;


	int matrix[][n] =
	{
	{ inf, 4, 21, 7, inf, 9, 13, inf, inf, inf, inf, inf },
	{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
	{ inf, inf, inf, 18, inf, inf, inf, inf, inf, inf, inf, inf },
	{ inf, inf, inf, inf, 5, 31, inf, inf, inf, inf, inf, inf },
	{ inf, inf, inf, inf, inf, inf, inf, inf, inf, 2, inf, inf },
	{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
	{ inf, inf, inf, inf, inf, inf, inf, inf, inf, 33, inf, inf },
	{ inf, inf, inf, inf, inf, inf, 24, inf, inf, inf, inf, inf },
	{ inf, inf, inf, inf, inf, inf, inf, 36, inf, inf, inf, inf },
	{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 16, 29 },
	{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 14 },
	{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf }
	};

	cout << "Введите начальную вершину " << endl;
	cin >> s; // исходная вершина

	// форматированный вывод массива, возвращаемого топологической сортировкой
	cout << "Линейный список вершин графа возвращаемый топологической сортировкой: " << endl;
	for (i = 0; i < n; i++)
	{
		cout << sorted[i] + 1 << " ";
	}

	topological_s(matrix, inf, &next, sorted);

	shrt = dag_shortest_path(matrix, s, inf, sorted);// массив кратчайших путей из вершины s



	cout << "\n\n";

	// форматированный вывод массива кратчайших путей
	for (i = 0; i < n; i++)
	{
		if (shrt[i] == inf)
		{
			cout << "(" << s << ", " << i + 1 << ") не существует  "<< endl;
		}
		else
		{
			cout << "(" << s <<", "<< i + 1<< ") = " << shrt[i] << endl;
		}
	}
	cout << endl;

	print_f = 0; // смена флага печати доп. информации

	system("pause");

}