Как удалить все пути, проходящие через конкретный документ или вершину во время обхода графа в ArangoDB

Я пытаюсь выполнить обход графа здесь

Пример графика

Я создал две коллекции в ArangoDB: коллекцию документов "Node" и коллекцию краев "Path". Все мои узлы имеют атрибут name (метки) и соединены ребрами (линиями), как показано на рисунке выше.

Я попытался найти пути, заканчивающиеся узлом end или error:

FOR v, e, p IN 1..10 OUTBOUND 'Node/start_0' Path     
OPTIONS { bfs: true}     
FILTER (v.name == "end" OR v.name == "error")     
RETURN CONCAT_SEPARATOR(' - ', p.vertices[*].name)

Вышеупомянутый запрос работает так, как ожидалось, и возвращает мне два пути:

["start - decide - execute1 - error"
 "start - decide - execute2 - end"]

Но я изучаю, как исключить все соответствующие пути, проходящие через конкретный узел. Например, я хочу удалить все пути, проходящие через execute1. Я пробовал этот запрос:

 FOR v, e, p IN 1..10 OUTBOUND 'Node/start_0' Path     
 OPTIONS { bfs: true}     
 FILTER ((v.name == "end" OR v.name == "error") AND v.name != "execute1")     
 RETURN CONCAT_SEPARATOR(' - ', p.vertices[*].name)

Но это не работает - он все равно возвращает мне два пути.

Может ли кто-нибудь помочь мне переосмыслить этот запрос, чтобы он возвращал только один путь, то есть «начало - решение - выполнение2 - конец»?


graph-traversal arangodb
person krishna    schedule 30.08.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ваш обход имеет переменную глубину 1..10, что позволяет найти следующие пути:

  1. начать - решить
  2. начать - решить - выполнить1
  3. начать - решить - выполнить2
  4. начать - решить - выполнить1 - ошибка
  5. начало - решить - выполнить2 - конец

Обратите внимание, как также возвращаются пути с одним переходом (1) и двумя переходами (2, 3). Они находятся в пределах от одного до десяти прыжков. Вы могли ожидать, что при обходе будут отправлены только листовые узлы (4, 5). Однако он дает вам все пять путей.

Условия ФИЛЬТРА атрибута name проверяются на v, который представляет последнюю вершину каждого из этих путей.

  • "decide" не равно "end" или "error", поэтому путь 1 отфильтрован.
  • "execute1" и "execute2" не равны "end" или "error", поэтому пути 2 и 3 также отфильтровываются.
  • "error" и "end" равны любому из этих значений, но они также удовлетворяют условию != "execute1" - вы тестируете стоповые узлы, а не все узлы на пути здесь, поэтому поведение правильное, но не то, что вы хотите

Возможны следующие варианты:

  • отфильтровать все пути, содержащие вершину с именем "execute1":
    FILTER p.vertices[*].name NONE == "execute1" AND v.name IN ["end", "error"]
  • не позволяйте проходящему пройти мимо "execute1", используя PRUNE (доступно с v3.4.5 и v3.5.0):
    PRUNE v.name == "execute1" … FILTER v.name IN ["end", "error"]
  • не позволяйте проходящему пройти мимо "execute1", "end" или "error" (оптимизация для вышеуказанного запроса):
    PRUNE v.name IN ["execute1", "end", "error"] … FILTER v.name IN ["end", "error"]

Обратите внимание, что PRUNE будет включать вершину, для которой выполняются условия, т.е. путь 2 обнаружен, но затем отфильтрован FILTER условиями. PRUNE сам по себе не фильтрует путь 2. Однако это предотвратит продолжение обхода с "execute1", что означает, что путь 4 не будет обнаружен. FILTER удаляет пути 1, 2 и 3 из результата, оставляя только путь 5.

Также обратите внимание, что предложение PRUNE должно быть помещено перед OPTIONS!

FOR v, e, p IN 1..10 OUTBOUND 'Node/start_0' Path
PRUNE v.name IN ["execute1", "end", "error"]
OPTIONS { bfs: true }
FILTER v.name IN ["end", "error"]
RETURN CONCAT_SEPARATOR(' - ', p.vertices[*].name)

Результат: [ "start - decide - execute2 - end" ]

Документы: Обрезка при обходе графа

person CodeManX    schedule 30.08.2019