Neo4J/Cypher: как фильтровать узлы пути?

Question

Я хочу получить все simple cycles/circuits на графике, проходящем через данный узел. Я могу так с этим шифровальщика запроса:

MATCH p=(n)-[*]->(n) 
WHERE n.postId = 71 //postId is a node property 
RETURN nodes(p) 

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

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

// In this example the length of the path is hardcoded to 4 
MATCH p= 
    (n)-[:RELATES_TO]-> 
    (p2)-[:RELATES_TO]-> 
    (p3)-[:RELATES_TO]-> 
    (p4)-[:RELATES_TO]->(n) 
WHERE n.postId = 71 
    AND p2.postId <> 71 
    AND p3.postId <> 71 
    AND p4.postId <> 71 
RETURN nodes(p) 

Есть ли способ фильтровать узлы между отношениями в первом запросе?

MATCH p=(n)-[*]->(n) 
WHERE n.postId = 71 //postId is a node property 
RETURN nodes(p) 

Важные примечания:

• Я знаю, как ограничить длину пути (через длину WHERE() ограничение или с variable length relationships)

Answer 1

Вы можете захотеть попробовать Библиотека процедур APOC, в частности функция allSimplePaths в разделе «Алгоритмы графа». Простые пути не должны иметь повторяющихся узлов.

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

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

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

Answer 2

Хотя это может быть не так быстро, как с помощью использования процедуры allSimplePaths АПБО, как это было предложено @InverseFalcon (я не пробовал), здесь далеко, чтобы получить простые пути в чистом Cypher:

MATCH p=(n)-[*]->(n) 
WHERE n.postId = 71 
WITH NODES(p) AS nds 
UNWIND nds AS nd 
WITH nds, COUNT(DISTINCT nd) AS dnd 
WHERE dnd = LENGTH(nds)-1 
RETURN nds; 

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

Answer 3

Вы пытались использовать filter() или none()? Я думаю, что я правильно понял вашу проблему, но вот как я использую вышеуказанные функции. (Если это, как раз downwote.)

Суть: нужно http://console.neo4j.org/?id=99xkcu

CREATE 
    (g:Person {name: 'Gorduin'}), (a:Person {name: 'Alvaro'}), 
    (pn:PhoneNumber {number: '555-512-2017'}), 
    (e11:Extension {extension: 11}), 
    (e27:Extension {extension: 27}), 
    (e19:Extension {extension: 19}), 

    (e11)-[:extension_of]->(pn)<-[:extension_of]-(e27), 
    (e19)-[:extension_of]->(pn), 

    (g)<-[:phone_number_of]-(e11), 
    (g)<-[:phone_number_of]-(e27), 
    (a)<-[:phone_number_of]-(e19), 
    (a)<-[:phone_number_of]-(pn); 

переменной запроса длины, которые будут использоваться, поскольку :phone_number_of указатель может исходить от расширения (привязка к номер телефона) или номер телефона. Стрелки направления не имеют значения, вы можете отменить любой из них и попробовать запросы ниже.

(Ограничение длины запроса будет очевидным решением в моей случае, например,

MATCH path = (p:Person)-[*1..3]-(n:PhoneNumber) 
RETURN nodes(path); 

, но это не вопрос Ор в.)

---

(1) Получение всех возможных путей от человека к номеру телефона (редактируется для удобства чтения):

MATCH path = (p:Person)-[*]-(n:PhoneNumber) 
RETURN nodes(path) as every_possible_path_from_a_Person_to_a_PhoneNumber; 

╒══════════════════════════════════════════════════════════════════════╕ 
│"every_possible_path_from_a_Person_to_a_PhoneNumber"     │ 
╞══════════════════════════════════════════════════════════════════════╡ 
│[a,pn]                │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[g,e11,pn,e19,a,pn]             │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[g,e27,pn,e19,a,pn]             │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[g,e11,pn]               │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[a,pn,e27,g,e11,pn]             │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[a,e19,pn,e27,g,e11,pn]            │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[a,e19,pn]               │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[g,e11,pn,a,e19,pn]             │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[g,e27,pn,a,e19,pn]             │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[g,e27,pn]               │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[a,pn,e11,g,e27,pn]             │ 
├──────────────────────────────────────────────────────────────────────┤ 
│[a,e19,pn,e11,g,e27,pn]            │ 
└──────────────────────────────────────────────────────────────────────┘ 

---

(2) С помощью none(), чтобы удалить избыточность путем фильтрации путей, которые содержат конкретный узел (узел с определенными свойствами или метки):

MATCH path = (p:Person)-[*]-(n:PhoneNumber) 
WITH nodes(path) as ns 
WHERE NONE(node IN ns WHERE (exists(node.name) and node.name ='Gorduin')) 
RETURN ns as path_nodes_NOT_containing_a_specific_person; 

╒══════════════════════════════════════════════════════════════╕ 
│"path_nodes_NOT_containing_a_specific_person"     │ 
╞══════════════════════════════════════════════════════════════╡ 
│[a,pn]              │ 
├──────────────────────────────────────────────────────────────┤ 
│[a,e19,pn]             │ 
└──────────────────────────────────────────────────────────────┘ 

---

(3) Используя filter() для удаления определенного узла из возвращенных путей:

MATCH path = (p:Person)-[*]-(n:PhoneNumber) 
WITH nodes(path) as ns 
WHERE NONE(node IN ns WHERE (exists(node.name) and node.name ='Gorduin')) 
RETURN filter(node in ns WHERE NOT node:Person) as personless_nodelist; 

╒══════════════════════════════════════════════════════════════╕ 
│"personless_nodelist"           │ 
╞══════════════════════════════════════════════════════════════╡ 
│[pn]               │ 
├──────────────────────────────────────────────────────────────┤ 
│[e19,pn]              │ 
└──────────────────────────────────────────────────────────────┘