переходный алгоритм сокращения: псевдокод?
Я бы порекомендовал ZipLib .
Личные причины, по которым я люблю этот проект:
- построены на потоках c ++ 11 stl (например, распаковывает в потоки STL!)
- облегченный ( никакие зависимости, кроме zlib)
- не могут использоваться в обоих окнах & amp; linux
Мне понадобилось много времени, чтобы найти этот проект - надеюсь, это кому-нибудь поможет.
2 ответа
Статья Википедии о транзитивной редукции указывает на реализация в GraphViz (с открытым исходным кодом). Не совсем псевдокод, но, может быть, с чего начать?
LEDA включает в себя алгоритм транзитивного сокращения . Я не У меня больше нет копии книги LEDA , и эта функция могла быть добавлена после публикации книги. Но если он там есть, то будет хорошее описание алгоритма.
Google указывает на алгоритм , который кто-то предложил для включения в Boost. Я не пытался его читать, так что, может быть, неверно?
Кроме того, это , возможно, стоит посмотреть.
Основная суть используемого мной алгоритма транзитивной редукции
foreach x in graph.vertices
foreach y in graph.vertices
foreach z in graph.vertices
delete edge xz if edges xy and yz exist
Алгоритм транзитивного замыкания, который я использовал в том же сценарии, очень похож, но последняя строка
add edge xz if edges xy and yz OR edge xz exist