#include <iostream>

using namespace std;

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

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

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

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

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


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

	}

	return;
}


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

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

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

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


	if (tmp == NULL)
	{
		*myStack = modStack(val); // создание стека с текущим элементом

	}
	else
	{
		do
		{
			tmpPrev = tmp; // присвоение указателю на предыдущий элемент указателя на текущий элемент
			tmp = tmp->next; // присвоение указателю на текущий элемент указателя на следующий элемент
		} while (tmp != NULL); // указатель на текущий элемент NULL

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

	return;
}


// функция топологичесской сортировки графа
void topological_s(int(*matrix)[n], int inf, stack** 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]++;
			}
		}
	}

	// запись в стек next вершин со степенью захода 0
	for (i = 0; i < n; i++)
	{
		if (in_degree[i] == 0)
		{
			PushStack(next, i);
		}
	}

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

		// поиск вершин с входящей степенью 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) 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];
				}
			}
		}
	}


	cout << "\n\nМассив предшествующих элементов pred"<< endl;
	for (i = 0; i < n; i++)
	{
		if (pred[i] == -1)
		{
			cout << "-("<< i <<")[null]";
		}
		else
		{
			cout << "-(" << i << ")" << "[" << pred[i] << "]";
			//cout << pred[i] << " ";
		}


	}
	return shortest;
}

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

	int s = 0; // вершина для поиска критического пути
	int inf = 10000; // бесконечно большая величина
	int* shrt; // указатель на массив кратчайших путей
	int i = 0; // счетчик
	int* sorted = new int[n] { 0 }; // массив элементов, возвращаемых топологической сортировкой
	stack* next = NULL; // указатель на стек next

	int matrix[][n] =
	{
		{ inf, 3, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
		{ inf, inf, 4, inf, inf, inf, inf, inf, inf, inf, inf, inf },
		{ inf, inf, inf, 15, 6, inf, inf, inf, inf, inf, inf, inf },
		{ inf, inf, inf, inf, inf, 34, inf, inf, inf, inf, inf, inf },
		{ inf, inf, inf, inf, inf, 9, inf, inf, inf, inf, inf, inf },
		{ inf, inf, inf, inf, inf, inf, 8, inf, inf, inf, inf, inf },
		{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 19, inf },
		{ inf, inf, inf, inf, inf, inf, inf, inf, 12, inf, inf, inf },
		{ inf, inf, inf, inf, 11, inf, inf, inf, inf, inf, inf, inf },
		{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 11, inf },
		{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 10 },
		{ inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf }
	};


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

	cout << "\nПроцесс топологической сортировки... ";
	topological_s(matrix, inf, &next, &sorted);

	// форматированный вывод массива, возвращаемого топологической сортировкой
	cout << "\n\nЛинейный список вершин графа возвращаемый топологической сортировкой: "<<endl;

	for (i = 0; i < n; i++)
	{
		cout << sorted[i] << " ";
	}


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

	cout << "\n\nСписок кратчайших путей из вершины " << s << " :" << endl;

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

}