Каковы хорошие способы организации данных ориентированного графа? - PullRequest
1 голос
/ 03 апреля 2012

Вот моя ситуация.У меня есть график, который имеет разные наборы данных, добавляемых в разное время.Например, set1 может иметь несколько тысяч узлов, а затем set2 приходит позже, и мы применяем бизнес-логику для создания ребер из set1 в set2 (и игнорируем любые вершины из set1, у которых нет ребер для set2).Затем на более позднем этапе мы получаем set3, set4 и т. Д., И один и тот же процесс применяется между каждым набором и его предыдущим набором.

Вопрос, как лучше организовать это?То, что я делал раньше, называло узлы set1-xx, set2-xx и т. Д. Проблема, с которой я столкнулся, заключалась в том, что когда я пытался запустить аналитику между текущим набором и предыдущим набором, мне пришлось бы выполнить цикл по всему графику.и найдите все узлы, которые начинаются с 'setx'.Рост графика занял много времени, поэтому я подумал о другом решении, которое заключалось в создании узла с именем 'set1' и подключении его ко всем узлам для этого конкретного набора.Я тестирую его, но мне было интересно, есть ли более эффективный способ или способ обработки таких структур данных?Есть ли способ как-то сегментировать данные?

Я думаю, что общим решением будет применение, но если это поможет, я использую neo4j (так что любое конкретное решение для этой базы данных также будет хорошо).

Ответы [ 2 ]

3 голосов
/ 03 апреля 2012

У вас есть особый тип ориентированного графа, называемый слоистый граф .

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

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

«Идентификатор вершины» может принимать разные формы. Например, это может быть индекс в массиве вершин следующего слоя.

1 голос
/ 03 апреля 2012

Ваше второе решение - это то, что я хотел бы сделать - создать узел setX и подключить все узлы, принадлежащие этому набору, к setX.Таким образом, ваши данные будут разделены, и запрос будет проще.

...