Алгоритм нарезки динамического графа

Question

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

[ОБНОВЛЕНИЕ]

Извините за неясность, и я обновляю свой вопрос. Позвольте мне сначала раскрыть контекст.

В MDE (Model Driven Engineering) в крупномасштабных промышленных системах в настоящее время задействованы сотни разработчиков, которые работают над сотнями моделей, представляющих компоненты всей спецификации системы. В таком контексте общепринятым подходом является использование центрального хранилища. Решение, которое я предоставляю для своего проекта (в настоящее время я работаю в исследовательской лаборатории), является решением, ориентированным на одноранговую сеть, что означает, что каждый разработчик имеет свою собственную репликацию спецификации системы.

Моя главная проблема - как воспроизвести эти данные, модели. Например, представьте, что Алиса и Боб работают над этой UML-диаграммой , и у Алисы есть полная диаграмма в его хранилище. Боб хочет иметь элементы {FeedOrEntry, Entry}, как я могу нарезать эту диаграмму UML? Я ищу термины "моделирование нарезки". Я нашел одну бумагу , которая дает подход для нарезки диаграмм классов UML, но проблема этого алгоритма в том, что он работает только для статического графа. В нашем контексте разработчики постоянно добавляют / обновляют / удаляют элементы, и общие элементы должны соответствовать другим репликам.

Поскольку UML-модели также можно рассматривать как график, я также ищу термины «разрезание графика» или «фрагмент графика», но я не нашел ничего полезного. И мне хотелось бы знать, существует ли такой алгоритм нарезки динамического графа

Answer 1

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

Однако, из-за ваших ограничений согласованности, я считаю, что ваш подход p2p несовместим. Альтернативой является операция слияния, но я понятия не имею, как будет работать эта операция. Это, вероятно, хотя бы частично, должно быть сделано вручную.

Answer 2

Как насчет нормализации графа к модели смежного дерева?Тогда вы можете использовать DFS или BFS, чтобы нарезать график?

Answer 3

Звучит так, как будто вам нужна графическая база данных NoSQL, например Neo4J или FlockDB .Они могут хранить миллиарды вершин и ребер.