ArangoDB: самый длинный кратчайший путь - не только расстояние - PullRequest
Новая
       11

ArangoDB: самый длинный кратчайший путь - не только расстояние

0 голосов
/ 04 января 2019

Я пытаюсь решить проблему с поиском самого длинного кратчайшего пути в моем графике. Я использую arangosh function _diameter, но она даст мне только числовое значение диаметра графика. Мне нужно знать, каков фактический путь. Возможно ли это?

1 Ответ

0 голосов
/ 07 января 2019

Следующий запрос AQL возвращает самый длинный кратчайший путь. 

LET ids = UNION(
(FOR x IN vertices1 RETURN x),
(FOR x IN vertices2 RETURN x)
)
FOR source IN ids
  FOR target IN ids
    FILTER source._id < target._id
      LET path = (FOR v, e IN ANY SHORTEST_PATH source TO target GRAPH @graphName RETURN [v, e]) 
      /* ==> [ [source, null], [v1, source->v1], .... [ target, vn -> target] ] */
  SORT LENGTH(path) DESC
  LIMIT 1
 RETURN path

L. 1-4 хранить все вершины в одном массиве, просматривая каждую коллекцию вершин. Если вы используете только одну коллекцию вершин, вы можете удалить эти строки и заменить "идентификаторы" вашей коллекцией вершин.

L. 5-8 вычисляют все комбинации кратчайших путей между перечисленными вершинами и обеспечивают выходной путь в виде [ [source, null], [v1, source->v1], .... [ target, vn -> target] ].

L.7 FILTER source._id < target._id следует использовать только в том случае, если вы используете ненаправленные ребра с ANY, поскольку путь vertex1 -> vertex2 равен vertex2 -> vertex1, когда направления не используются. Удалите эту строку, если вы используете INBOUND/OUTBOUND указания вместо.

L. 10-11 сортируйте все пути в порядке убывания (самый длинный путь в начале) и ограничьте результирующий набор 1 объектом.

L. 12 наконец возвращает путь самого длинного кратчайшего пути.

Этот запрос очень дорог, хотя, итерация по всем вершинам дважды и вычисление кратчайшего пути для каждой пары вершин приводит к O (n³ log n). Поэтому этот запрос можно использовать только для небольшого набора вершин.

...