Comments 16
Спасибо за статью. Вот описание алгоритма Тарьяна на русском. И почему вы вспомнили про сортировку подсчетом когда сортируете вершины, но забыли когда сортируете ребра? Можно например завести массив пар (из, в) и отсортировать подсчетом (по 2 элементу) все за O(|V| + |E|) времени. Потом их всех запихать назад. Также непонятно почему у вас O(|V|) памяти (ребра не храним?)?
- Классический алгоритм Тарьяна меня не устраивал по причине его рекурсивности, это указано в тексте. Хотя ссылка полезная, в той же русскоязычной Википедии алгоритмы над графами описаны довольно слабо.
- Про сортировку рёбер подумаю. Пока непонятно почему то что вы говорите должно сработать.
- Память под рёбра я не считаю потому что они уже где-то хранятся откуда их мне подали на вход. Если в реальном применении граф совсем нельзя будет менять (ни сохранить в вершине её индекс, ни переупорядочить рёбра), то будут проблемы и некоторые big-O подрастут. Здесь же предполагается что граф можно портить, при условии что его структура не нарушается (не добавляются/удаляются вершины/рёбра).
- Другое вот подумал. Нет необходимости в отдельном этапе «считаем сколько вершин в каждом из компонентов» в рамках сортировки подсчётом. Это прекрасно можно сделать в процессе Тарьяна.
Да, про алгоритм Тарьяна я написал чтобы те кто не могут в английский прочитали на русском. Действительно ваш алгоритм можно реализовать так что-бы ребра не хранились в памяти. Но если их сохранить то можно отсортировать за 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);
Так же можно заметить что, то чего вы хотите добиться в практической части это не стабильная сортировка, а одинаковое поведение в не зависимости от того в каком порядке стоят ребра в вершине графа(в представлении графа). А это как раз алгоритм Тарьяна с предварительной сортировкой рёбер.
Я не просто так взял слово «топологическая» в кавычки, потому что насколько мне известно, никакого термина для того что я делаю нет. Да, по условиям задачи важен порядок вершин, а не рёбер.
Алгоритм пытается решить две проблемы: неоднозначность топологической сортировки плюс её несуществование для графов с циклами. К математике это имеет слабое отношение. Оно решает проблемы несовершенного мира, пытаясь среди неооднозначности топологической сортировки выбрать единственный вариант, удобный на практике и (надеюсь) легко вычисляемый в голове.
Алгоритм пытается решить две проблемы: неоднозначность топологической сортировки плюс её несуществование для графов с циклами. К математике это имеет слабое отношение. Оно решает проблемы несовершенного мира, пытаясь среди неооднозначности топологической сортировки выбрать единственный вариант, удобный на практике и (надеюсь) легко вычисляемый в голове.
Вектора — это фрагментация, cache miss'ы, аллокация памяти в heap'е и вот это вот всё. Напомню что предметная область для которой придумывался алгоритм — C плюс крайне низкоуровневый код (ld.so), выполняемый очень часто — любой вызов
exec(3). А если ограничиться только массивами, то памяти O(|e|^2), для стэка это уже неприемлемо. Бенчмаркать надо. Но до решения практической задачи руки идут медленно и тяжко.Я не согласен, все можно реализовать на массивах. Как в старые добрые паскалевские времена, например можно хранить массив «голов» и массив ребер. Головы указывают где начинается кусок памяти ребер данной вершины.Я переписал свой код без векторов.
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);
}
Согласен. Ваше кунг-фу сильнее моего кунг-фу :) Не хотите патч в glibc запилить?)
Можете скинуть то место которое надо поменять?
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]
Спасибо, если что-то выйдет, то напишу статью на хабр.
Вопрос про maps[i]->l_reldeps. Что значит что на них можно забить? Можно ли не забивать? Просто не сильно понятно как строго сформулировать задачу с этими ребрами.
Формально:
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
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
Я делал бандлер js модулей, где, опять же, могут быть циклические зависимости. К сожалению, просто оставить в порядке поступления — не вариант, так как поступают модули вразнобой. А, например, если исполнить модуль, расширяющий базовый класс, до модуля, где этот базовый класс определяется, то это приведёт к падению. Поэтому для каждой зависимости задаётся её вес. 0 — максимальный вес, жёсткая зависимость. минус бесконечность — самая слабая зависимость. Алгоритм получился такой: https://github.com/eigenmethod/mol/blob/master/graph/graph.ts
cut_cycles разрезает циклы в наиболее слабом месте за O(число узлов + число связей), а sorted — сериализует ациклический граф за O(число узлов), если поменять массивы на хеш-сеты, конечно.
У меня используется рекурсия, она ни чем не хуже ручной реализации стека так-то.
Суть алгоритма проста: идём от узла по зависимостям в глубину, запоминая путь. Обнаружив цикл, смотрим где в пути был наименьший вес, раскручиваем стек до него, разрезаем, и переходим к следующей его зависимости. Если мы прошли по всем зависимостям узла, то помечаем его проверенным и не заходим в него больше. И так для всех узлов в качестве стартовых.
Спасибо большое за статью: алгоритм с вашими дополнениями отлично работает!
Sign up to leave a comment.
«Топологическая» сортировка графа с циклами