Непересекающиеся подграфы в ArangoDB AQL - PullRequest
Новая
       67

Непересекающиеся подграфы в ArangoDB AQL

2 голосов
/ 13 января 2020

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

У меня возникают проблемы при создании запроса, в котором я могу выбрать все непересекающиеся подграфы, а именно: учитывая подграфы A и B в базе данных, нет грани (OUTBOUND или INBOUND), соединяющей подграф A с подграфом B.

Из этого AQL: 

FOR actor IN actors
FOR v, e, p IN 1..1 ANY actor._id acts_in_scenes
    RETURN e

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

all-subgraphs

Я сделал несколько попыток, используя подзапросы и сборы, я думаю, что лучший результат до этого момента - запрос ниже, но все же он просто возвращает мне сцены: 

FOR actor IN actors
    LET sub_result = (FOR v, e, p IN 1..1 ANY actor._id acts_in_scenes RETURN DISTINCT v._id) // this just returns me scenes
    FILTER LENGTH(sub_result) > 0
    RETURN DISTINCT sub_result

Кто-нибудь знает, возможно ли это решить с помощью запроса AQL?

РЕДАКТИРОВАТЬ: Итак, я ' мы увеличили глубину до 5 (1..5) в подзапросе обхода графа, и теперь я могу получить вершины актеров. Теперь проблема заключается в том, что при проверке результата json я вижу повторяющиеся ключи сцены в группах, это не должно быть возможно, если этот результат будет представлять непересекающиеся подграфы: 

FOR actor IN actors
    LET sub_result = (
        FOR v, e, p IN 1..5 ANY actor._id acts_in_scenes 
        SORT v._id
        RETURN DISTINCT v._id
    )
    FILTER LENGTH(sub_result) > 0
    SORT COUNT(sub_result) DESC
    RETURN DISTINCT { 'count': COUNT(sub_result), result: sub_result }

РЕДАКТИРОВАТЬ 2:

Мне пришлось решить эту проблему путем создания графика на стороне приложения с использованием библиотеки networkx и использования функции nx.connected_components () . Но я действительно мог бы sh решить эту проблему, используя только графические функции базы данных, поскольку это усложняет приложение и требует от меня создания графа в памяти на стороне приложения.

...