Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач. Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует. Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети.
↑ Пример ориентированного неотсортированного графа, к которому применима топологическая сортировка
Приветствую всех читателей Хабра! Решив написать эту статью, я обнаружил на Хабре много материалов по графам и, в частности, по топологической сортировке. Например, здесь довольно подробно описана теоретическая часть и приведены примеры основных алгоритмов. Поэтому не буду повторяться, а расскажу о практической области применения Topological sorting, а точнее, хочу поделиться личным опытом применения этого метода при разработке продуктов DevExpress. Из статьи станут понятны мотивы и причины, побудившие к использованию этого алгоритма. В конце я приведу наш вариант реализации алгоритма для сортировки зависимых объектов.
При разработке бизнес-приложений постоянно стоит проблема хранения данных в репозитории совместно с проектом. Особенно эта тема актуальна для корпоративных ERP, CRM, многабукав и так далее систем.
Для чего это нужно:
Для целей тестирования
Для совместной разработки
Для каких-то программных алгоритмов, оперирующих этими данными
Также, не менее остро стоит проблема надежного обновления данных на рабочем проекте, совместно с обновлением модели.
В нашей системе мы применили подход, который позволяет контролировать целостность данных, их загрузку и обновление, хранит данные в репозитории и при этом работает быстро и надежно.
В начале июля Teamlab переименовался в ONLYOFFICE и полностью открыл исходный код своего приложения, включая онлайн редакторы документов, совместное редактирование, диаграмму Ганта и функционал выставления счетов.
За две недели мы получили массу вопросов на эту тему, поэтому на правах сотрудника компании возьмусь разъяснить, что к чему. Если у вас нет времени читать пост, просто скачайте инсталляцию ONLYOFFICE с Sourceforge. Разверните на своем сервере. Готово! У вас есть свой облачный офис. Вы великолепны.
Как синхронизировать параллельные шелл-процессы, используя named pipes (FIFO-файлы) в качестве условных переменных. Как выполнить параллельно зависимые задач в топологическом порядке с минимумом средств: POSIX shell, mkfifo, POSIX kernel. Как параллельный запуск ускоряет загрузку встраиваемых систем и *BSD (rc-этап FreeBSD с 27 до 7 секунд) или старт приложений в пользовательских контейнерах Docker, LXC и jail. Как это повышает аптайм в отказоустойчивых кластерах Jet9.
