У меня большой ориентированный ациклический граф, и я хотел бы вычислить транзитивное сокращение этого графа.
В настоящее время я вычисляю транзитивное сокращение, используя наивный поиск в глубину, но этот алгоритмслишком медленно для моего варианта использования.Тем не менее, эффективные алгоритмы, которые мне удалось найти, работают с представлением смежности matrix , тогда как мое представление примерно эквивалентно списку смежности .(На самом деле он представлен в виде набора объектов C ++, каждый из которых имеет указатели на своих детей и родителей).
Я, очевидно, мог бы преобразовать свой DAG в матрицу смежности, выполнить сокращение и преобразовать его обратно;но это кажется немного расточительным, и я хотел бы по возможности более простой алгоритм.
Мой график содержит ~ 100 000 узлов.