«Топологическая» сортировка графа с циклами

[asakhabiev]

Спасибо за статью. Вот описание алгоритма Тарьяна на русском. И почему вы вспомнили про сортировку подсчетом когда сортируете вершины, но забыли когда сортируете ребра? Можно например завести массив пар (из, в) и отсортировать подсчетом (по 2 элементу) все за O(|V| + |E|) времени. Потом их всех запихать назад. Также непонятно почему у вас O(|V|) памяти (ребра не храним?)?

[slonopotamus]

1. Классический алгоритм Тарьяна меня не устраивал по причине его рекурсивности, это указано в тексте. Хотя ссылка полезная, в той же русскоязычной Википедии алгоритмы над графами описаны довольно слабо.
2. Про сортировку рёбер подумаю. Пока непонятно почему то что вы говорите должно сработать.
3. Память под рёбра я не считаю потому что они уже где-то хранятся откуда их мне подали на вход. Если в реальном применении граф совсем нельзя будет менять (ни сохранить в вершине её индекс, ни переупорядочить рёбра), то будут проблемы и некоторые big-O подрастут. Здесь же предполагается что граф можно портить, при условии что его структура не нарушается (не добавляются/удаляются вершины/рёбра).
4. Другое вот подумал. Нет необходимости в отдельном этапе «считаем сколько вершин в каждом из компонентов» в рамках сортировки подсчётом. Это прекрасно можно сделать в процессе Тарьяна.

[asakhabiev]

Да, про алгоритм Тарьяна я написал чтобы те кто не могут в английский прочитали на русском. Действительно ваш алгоритм можно реализовать так что-бы ребра не хранились в памяти. Но если их сохранить то можно отсортировать за O(|V| + |E|). Например так.

std::vector<std::vector<size_t>> graph(n);
std::vector<std::vector<size_t>> transponed(n);
for (size_t from = 0; from < n; from++)
	for (size_t to: graph[from])
		transponed[to].push_back(from);
graph.clear();
for (size_t to = 0; to < n; to++)
	for (size_t from: transponed[to])
		graph[from].push_back(to);

[asakhabiev]

Так же можно заметить что, то чего вы хотите добиться в практической части это не стабильная сортировка, а одинаковое поведение в не зависимости от того в каком порядке стоят ребра в вершине графа(в представлении графа). А это как раз алгоритм Тарьяна с предварительной сортировкой рёбер.

[slonopotamus]

Я не просто так взял слово «топологическая» в кавычки, потому что насколько мне известно, никакого термина для того что я делаю нет. Да, по условиям задачи важен порядок вершин, а не рёбер.

Алгоритм пытается решить две проблемы: неоднозначность топологической сортировки плюс её несуществование для графов с циклами. К математике это имеет слабое отношение. Оно решает проблемы несовершенного мира, пытаясь среди неооднозначности топологической сортировки выбрать единственный вариант, удобный на практике и (надеюсь) легко вычисляемый в голове.

[asakhabiev]

То что вы хотите, называется топологическая сортировка сконденсированного графа. Алгоритм Тарьяна это алгоритм конденсации. И он детерминированный. Разница в работе может быть вызвана только тем в каком порядке лежат ребра в вершине(в представлении графа)

[slonopotamus]

Вектора — это фрагментация, cache miss'ы, аллокация памяти в heap'е и вот это вот всё. Напомню что предметная область для которой придумывался алгоритм — C плюс крайне низкоуровневый код (ld.so), выполняемый очень часто — любой вызов exec(3). А если ограничиться только массивами, то памяти O(|e|^2), для стэка это уже неприемлемо. Бенчмаркать надо. Но до решения практической задачи руки идут медленно и тяжко.

[asakhabiev]

Я не согласен, все можно реализовать на массивах. Как в старые добрые паскалевские времена, например можно хранить массив «голов» и массив ребер. Головы указывают где начинается кусок памяти ребер данной вершины.Я переписал свой код без векторов.

void transpose_graph(size_t vsize, size_t *graph, size_t *heads, size_t *tgraph, size_t *theads)
{
	for (size_t from = 0; from < vsize; ++from)
		for (size_t j = heads[from]; j < heads[from]; ++j)
			if (graph[j] != 0)
				++theads[graph[j] + 1];
	for (size_t i = 1; i < vsize; i++)
		theads[i + 1] += theads[i];
	for (size_t from = 0; from < vsize; ++from)
		for (size_t j = heads[from]; j < heads[from]; ++j)
		{
			tgraph[theads[graph[j]]] = from;
			++theads[graph[j]];
		}
}

int main()
{
	size_t vsize, esize;
	size_t graph[esize];
	size_t heads[vsize + 1];
	//  заполняем граф
	size_t tgraph[esize];
	size_t theads[vsize + 1];
	transpose_graph(vsize, graph, heads, tgraph, theads);
        for (size_t i = 0; i < vsize + 1; i++)
              heads[i] = 0;
	transpose_graph(vsize, tgraph, theads, graph, heads);
}

[slonopotamus]

Согласен. Ваше кунг-фу сильнее моего кунг-фу :) Не хотите патч в glibc запилить?)

[asakhabiev]

Можете скинуть то место которое надо поменять?

[slonopotamus]

sourceware.org/git/?p=glibc.git;a=blob;f=elf/dl-sort-maps.c;h=26b3fd93a387ba1314df1b98dc1d54cb44cd3594;hb=HEAD

Пояснения особенностей предметной области:

• maps — это массив вершин размером nmaps
• maps[i]->l_initfini — null-terminated массив рёбер
• maps[i]->l_idx — место куда можно запомнить индекс вершины. Если там -1, его портить нельзя и эту вершину нужно пропустить
• maps[i]->l_reldeps — еще рёбра, так называемые «dynamic». Обращать на них внимание только если на входе for_fini=true. Суть этих рёбер в рамках задачи в том что если цикл образован с их участием, то на них можно забить. Товарищ который заходил на эту тему в 2015-ом (и я с ним согласен) пришли к мысли что сортировать надо дважды. Сначала с учётом всех ребер, потом (если обнаружены циклы), повторно но уже только учитывая l_initfini и игнорируя l_reldeps
• used — некий массив, элементы которого надо расставить в том же порядке в котором в результате расставлены вершины. Т.е. maps[i] связан с used[i]

[asakhabiev]

Спасибо, если что-то выйдет, то напишу статью на хабр.

[asakhabiev]

Вопрос про maps[i]->l_reldeps. Что значит что на них можно забить? Можно ли не забивать? Просто не сильно понятно как строго сформулировать задачу с этими ребрами.

[slonopotamus]

Формально:

1. Выполняем сортировку
2. Если были циклы, то повторно выполняем сортировку того что получилось на предыдущем шаге делая вид что l_reldeps не существует.

Это просто некий hint из предметной области относительно того какие рёбра пойдут «под нож» в ситуации когда мы не можем удовлетворить их все. Задачи минимизации количества нарушенных рёбер не стоит, ибо там подстерегает NP.

Думаю, имеет смысл посмотреть релевантные багрепорты:

sourceware.org/bugzilla/show_bug.cgi?id=15310
sourceware.org/bugzilla/show_bug.cgi?id=15311
sourceware.org/bugzilla/show_bug.cgi?id=17645

[vintage]

Я делал бандлер js модулей, где, опять же, могут быть циклические зависимости. К сожалению, просто оставить в порядке поступления — не вариант, так как поступают модули вразнобой. А, например, если исполнить модуль, расширяющий базовый класс, до модуля, где этот базовый класс определяется, то это приведёт к падению. Поэтому для каждой зависимости задаётся её вес. 0 — максимальный вес, жёсткая зависимость. минус бесконечность — самая слабая зависимость. Алгоритм получился такой: https://github.com/eigenmethod/mol/blob/master/graph/graph.ts
cut_cycles разрезает циклы в наиболее слабом месте за O(число узлов + число связей), а sorted — сериализует ациклический граф за O(число узлов), если поменять массивы на хеш-сеты, конечно.
У меня используется рекурсия, она ни чем не хуже ручной реализации стека так-то.
Суть алгоритма проста: идём от узла по зависимостям в глубину, запоминая путь. Обнаружив цикл, смотрим где в пути был наименьший вес, раскручиваем стек до него, разрезаем, и переходим к следующей его зависимости. Если мы прошли по всем зависимостям узла, то помечаем его проверенным и не заходим в него больше. И так для всех узлов в качестве стартовых.

[cy6erGn0m]

Спасибо большое за статью: алгоритм с вашими дополнениями отлично работает!