LINUX.ORG.RU
Форум — Development  

Топологическая сортировка подграфа


0

1

Нужен алгоритм топологической сортировки подграфа ориентированного графа.

Неформально, задача стоит такая:

Есть большой ориентированный(циклов нет) граф, скажем, граф зависимостей между ячейками в табличном процессоре.

Некая ячейка изменяет состояние. Необходимо построить список всех ячеек, от нее зависящих, и последовательно применить правила преобразования данных, согласно формулам, заданным в ячейках.

Граф может быть очень большим, поэтому затрагивать его весь крайне нежелательно - старые значения ячеек кешируются, не нужно перевычислять внешние, по отношению к подграфу, зависимости.

Также, очень нежелателен рекурсивный алгоритм - сам подграф тоже может быть достаточно большим, и рекурсия может вызвать переполнение стека.


Это нужно для моего нового dataflow фреймворка для Common Lisp.

Вот часть исходников: http://paste.lisp.org/display/119136
Пример: http://paste.lisp.org/display/119137

То что там сейчас это non-solution, потому что ячейки в выбранном списке повторяются, так как та вариация алгоритма сортировки не учитывает «стоки» в ячейку.


← Как в базах данных принято делать ссылки внутри таблицы?
[from archlinux to gentoo] где живет hook на lvm2 ? →

Чтобы расчитать зависимости между вершинами подграфа, нужно знать весь подграф, состоящий из вершин, достижимых из подграфа (т.е. потенциально весь большой граф).

Это нужно для моего нового dataflow фреймворка для Common Lisp.

Lisp

Nice try.

anonymous
()

вобще не трогать весь граф можно только в двух случаях:

1. Если ограничить глубину обхода графа(константой).

2. Если рассматриваемый подграф является отдельной компонентой свзяности.

Иначе, прийдется обходить весь граф.

Вобще, на счет реализации reactive programming советую посмотреть статьи Connal Eliot. Там он рассматривает различные варианты релизации, и предлагает свою. Правда там варианты для Haskell, но думаю сможете транслировать(CL ведь метаязык, верно?).

anonymous
()
Ответ на: комментарий от anonymous

> CL ведь метаязык, верно?

Настолько тонко, что даже толсто.

anonymous
()

А что, в педивикии на эту тему ничего нет?

ilias
()

Я может не до конца понял задачу, но вообще то алгоритм представляется несложным:

1) заводим список L (очередь) ячеек на обработку, изначально он состоит из списка прямых зависимостей первой измененной ячейки (каждая ячейка ведь знает тех кто от нее непосредственно зависит?)

2) пока L не пуст: 2.1) извлекаем из L ячейку 2.2) обрабаываем ячейку соогласно правилам 3.3) добавляем в L список зависимостей извлеченной ячейки

Меняя местами п 2.3 и 2.3 и звлекая разные ячейки (первую или последнюю п.2.1) можем получить желаемый порядок обхода и пр.

Что бы исключить возможность повторной обработки той же ячейки (если это не исключено структурой исходного графа), моэно либо завести хэш-таблицу (или ее аналог - что то с быстрым посиком) и отмечать в ней уже обработанные ячейки, либо маркировать сами ячейки. Первый вариант проще (но мб медленней - от параметров задачи зависит), второй мб быстрей, но надо подумать как маркировать.

AIv ★★★★★
()
Ответ на: комментарий от AIv

вопрос был как раз в исключении повторений.
я решил оставлять повторения, соответственно вопрос неактуален, ну а с повторениями алгоритм элементарен.

Doug
() автор топика
Ответ на: комментарий от Doug

Ну я знаю два ответа - либо таблица обработанных ячеек (если можно для ячейки однозначно генерировать ключ), и при извлечении ячейки из L (или помещении в L) проверяться по этой таблице, либо фактически в каждой ячейке держать таблицу совершенных над ней правок.

AIv ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Как в базах данных принято делать ссылки внутри таблицы?
Development
[from archlinux to gentoo] где живет hook на lvm2 ? →