Cypher BFS с несколькими отношениями в пути

Question

Я хотел бы моделировать автономные системы и их отношения в базе данных Graph (memgraph-db)

Между узлами могут существовать два разных типа отношений:

• ненаправленные одноранговые отношения (ребра без стрелок на изображении)
• направленные отношения между поставщиком и клиентом (стрелки, указывающие на поставщика на изображении)

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

<img alt="допустимые пути (источник: caida.org)" src="https://i.stack.imgur.com/9ktV3.png"/>

Их можно описать как

      (s)-[:provider*0..n]->()-[:peer*0..n]—()<-[:provider*0..n]-(d)

или другими словами

0-n ребер c2p, за которыми следуют 0-n ребер p2p, за которыми следуют 0-n ребер p2c

Я могу исправить первый и последний узел и хотел бы найти (кратчайший/самый дешевый) путь. Как я понимаю, я могу сделать BFS, если на пути есть ОДНО отношение.

Есть ли способ запросить пути такой формы в Cypher?

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

то есть

      MATCH (s)<-[]->(d)                            // All one hop paths
MATCH (s)-[:provider]->()-[:peer]-(d)         
MATCH (s)-[:provider]->()<-[:provider]-(d)
...

Answer 1

Поскольку можно иметь 7 разных участков пути, я не понимаю, как 3 шаблона BFS ( ... BFS*0..n) даст правильное решение. Путь не может быть пустым, потому что шаблон содержит несколько узлов между ними (я должен перепроверить это).

Писать отдельные паттерны не очень хорошо.

Вот некоторые варианты:

• MATCH path=(s)-[:BFS*0.n]-(d) WHERE {{filter_expression}}-> Выражение должно быть довольно сложным, чтобы получить допустимые пути.
• MATCH path=(s)-[:BFS*0.n]-(d) CALL module.filter_procedure(path)-> module.procedure(path)может быть реализован на Python или C/C++. Пожалуйста, посмотрите здесь . Я бы рекомендовал начать с Python, так как это намного проще. Python для PoC должен подойти. Я бы также рекомендовал начать с этого варианта, потому что я уверен, что решение будет работать, + оно модульное. В конце концов, filter_procedureможет быть легко расширен, а запрос останется прежним.

Не могли бы вы предоставить пример набора данных в формате запроса Cypher (пара узлов и ребер/небольшой график)? Я рад найти решение.