Лучший способ хранения / доступа к ориентированному графу

StackOverflow https://stackoverflow.com/questions/191897

Вопрос

У меня есть около 3500 средств борьбы с наводнениями, которые я хотел бы представить в виде сети для определения путей стока (по сути, ориентированный граф).В настоящее время я использую SQLServer и CTE для рекурсивной проверки всех узлов и их вышестоящих компонентов, и это работает до тех пор, пока вышестоящий путь не сильно разветвляется.Однако некоторые запросы занимают экспоненциально больше времени, чем другие, даже если физически они не намного дальше по пути (т. е.два или три сегмента "вниз по течению") из-за дополнительной сложности восходящего потока;в некоторых случаях я оставляю это более чем на десять минут, прежде чем завершить выполнение запроса.Я использую простую таблицу с двумя столбцами, один столбец которой является самим объектом, а другой - объектом, расположенным выше по потоку от того, который указан в первом столбце.

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

Конечно, возможно, что в данных есть циклы, но я еще не нашел хорошего способа проверить это (кроме случая, когда запрос CTE сообщил о достижении максимального рекурсивного количества;это было легко исправить).

Итак, мой вопрос в том, правильно ли я храню эту информацию?Есть ли лучший способ, отличный от CTE, запросить вышестоящие точки?

Это было полезно?

Решение

Я ничего не знаю о средствах борьбы с наводнениями.Но я бы выбрал первое средство.И используйте временную таблицу и цикл while для генерации пути.

-- Pseudo Code
TempTable (LastNode, CurrentNode, N)



ОБЪЯВЛЯЕМ @intN INT
УСТАНАВЛИВАЕМ @intN = 1



ВСТАВИТЬ ВО временную таблицу (lastNode, currentNode, N)
  -- Вставить первый элемент в списке без элементов восходящего потока...вызовите это начальное условие
  ВЫБЕРИТЕ lastNode, currentNode, @intN
  ИЗ вашей таблицы
  ГДЕ у узла нет ничего выше по течению



В ТО ВРЕМЯ КАК @intN <= 3500
НАЧАТЬ
     Установите @intN = @intN + 1
    ВСТАВЬТЕ Во временную таблицу (lastNode, currentNode, N)
      ВЫБЕРИТЕ lastNode, currentNode, @intN
      ИЗ вашей таблицы
      ГДЕ lastNode IN (ВЫБЕРИТЕ currentNode ИЗ TempTable, ГДЕ N = @intN-1)



IF @@ROWCOUNT = 0
     BREAK




КОНЕЦ

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

ВЫБЕРИТЕ lastNode, currentNode, N Из TempTable УПОРЯДОЧИТЬ ПО N

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

Другие советы

Лучший способ хранения графиков - это, конечно, использовать собственный граф db: -)

Посмотрите neo4j . Он реализован на Java, а также имеет привязки Python и Ruby.

Я написал две вики-страницы с простыми примерами моделей доменов, представленных в виде графиков с использованием neo4j: сборка и роли . Дополнительные примеры можно найти на галерее моделирования доменов .

Традиционно графы представлены либо матрицей, либо вектором. Матрица занимает больше места, но ее легче обрабатывать (3500x3500 записей в вашем случае); вектор занимает меньше места (3500 записей, у каждого есть список тех, к кому они подключаются).

Это тебе поможет?

Я думаю, что у вас хорошая структура данных (для SQL Server), но CTE может быть не самым эффективным решением для ваших запросов. Вы можете попробовать создать хранимую процедуру, которая обходит график, используя вместо этого временную таблицу в качестве очереди, это должно быть более эффективным.

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

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

Что касается формата на диске, DOT является довольно переносимым / популярным среди других. Также кажется довольно распространенным хранить список ребер в формате плоского файла, например: 

vertex1 vertex2 {edge_label1}+

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

vertex1 vertex2
vertex2 vertex1

Мой опыт хранения чего-либо подобного вам описан в базе данных SQL Server:

Я хранил матрицу расстояний, рассказывая, сколько времени требуется для перемещения из точки A в точку B. Я сделал наивное представление и сохранил их непосредственно в таблице, называемой расстояниями со столбцами A, B, расстоянием, временем.

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

Я мог бы предоставить некоторый код, но это был бы C #.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top