Примеры топологической сортировки на больших DAG

Question

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

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

Даже если данные/ project может быть недоступен для публичного доступа, любые подсказки (и оценки порядка потенциальных размеров графов) могут оказаться полезными.

Answer 1

Вот несколько примеров топологической сортировки, которые я видел до сих пор:

• При планировании графиков задач в распределенной системе обычно необходимо отсортировать задачи топологически, а затем назначить их Ресурсы. Мне известны графики задач, содержащие более 100 000 задачи должны быть отсортированы в топологическом порядке. См. this в этом контексте.

• Когда-то я работал над Системой управления документами. каждый документ в этой системе имеет своего рода ограничение приоритета набор других документов, например его тип содержимого или ссылка на поле. Затем система должна иметь возможность генерировать порядок документов с сохраненным топологическим порядком. Насколько я помню, там были около 5 000 000 документов, доступных два года назад !!!

• В области социальных сетей существует известный запрос, чтобы узнать самая большая дистанция дружбы в сети. Эта проблема должна пересечь график методом BFS, равным стоимости топологическая сортировка. Рассмотрите членов Facebook и найдите свой Ответ.

Если вам нужны более реальные примеры, не стесняйтесь спрашивать меня. Я работал во многих проектах, работающих над большими графиками.

P.S. для больших наборов данных DAG вы можете взглянуть на страницу Stanford Large Network DataSat Collection и Graphics @ Illinois .

Answer 2

Я не уверен, соответствует ли это тому, что вы ищете, но знаете ли вы Bio4j проект?

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

Answer 3

Компания , в которой я работаю , управляет (собственной) базой данных об уязвимостях программного обеспечения и исправлениях.Патчи обычно выпускаются поставщиком программного обеспечения (например, Microsoft, Adobe и т. Д.) Через регулярные промежутки времени, и «новые и улучшенные» патчи «заменяют» более старые, в том смысле, что если вы применяете более новый патч к хосту, то старыйисправление больше не требуется.

Это приводит к созданию группы обеспечения доступности баз данных, где каждое программное исправление является узлом с дугами, указывающими на узел для каждого «заменяющего» исправления.В настоящее время в графе имеется около 10 тыс. Узлов, и каждую неделю добавляются новые исправления.

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

Answer 4

TopoR - коммерческий топологический маршрутизатор на печатной плате, который сначала работает, маршрутизируя печатную плату как топологическую проблему, а затем переводя топологию в физическое пространство. Они поддерживают до 32 электрических слоев, поэтому он должен поддерживать тысячи соединений (скажем, 10 ^ 4).

Я подозреваю, что интегральные схемы могут использовать аналогичные методы.