Недавно я натолкнулся на интересный случай использования путей на графике, где мы хотели вычислить частоту общения между двумя людьми, показывая, как часто каждый из них отправляет электронное письмо другому.
Модель выглядела так:
который мы можем создать с помощью следующих шифровальных выражений:
CREATE (email1 { name: 'Email 1', title: 'Some stuff' })
CREATE (email2 { name: 'Email 2', title: "Absolutely irrelevant" })
CREATE (email3 { name: 'Email 3', title: "Something else" })
CREATE (person1 { name: 'Mark' })
CREATE (person2 { name: 'Jim' })
CREATE (person3 { name: 'Alistair' })
CREATE (person1)-[:SENT]->(email1)
CREATE (person2)-[:RECEIVED]->(email1)
CREATE (person3)-[:RECEIVED]->(email1)
CREATE (person1)-[:SENT]->(email2)
CREATE (person2)-[:RECEIVED]->(email2)
CREATE (person2)-[:SENT]->(email3)
CREATE (person1)-[:RECEIVED]->(email3)
Мы хотим вернуть список, содержащий пары людей и сколько раз они писали друг другу по электронной почте, поэтому в этом случае мы хотим вернуть таблицу, показывающую следующее:
+-------------------------------------------+ | Person 1 | Person 2 | P1 -> P2 | P2 -> P1 | |-------------------------------------------| | Alistair | Mark | 0 | 1 | | Jim | Mark | 1 | 2 | +-------------------------------------------+
Я начал со следующего запроса, который находит все электронные письма, а затем переходит к поиску отправителя и получателя и объединяет их вместе:
START email = node:node_auto_index('name:"Email 1" name:"Email 2" name: "Email 3"')
MATCH sender-[:SENT]->email<-[:RECEIVED]-receiver
RETURN sender.name, receiver.name, COUNT(email) AS count
который возвращает следующее:
==> +-------------------------------------+ ==> | sender.name | receiver.name | count | ==> +-------------------------------------+ ==> | "Mark" | "Jim" | 2 | ==> | "Jim" | "Mark" | 1 | ==> | "Mark" | "Alistair" | 1 | ==> +-------------------------------------+
Это дает нам все пары, которые отправляли электронные письма друг другу, но не группирует их вместе, что немного раздражает.
Поняв, что довольно сложно получить эту группу людей, если я начну с писем, я изменил запрос, чтобы начать с людей, а затем перебирать письма, которые они писали друг другу:
START personA = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"'),
personB = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"')
MATCH personA-[s:SENT]->email<-[r:RECEIVED]-personB
WHERE personA <> personB
WITH personA, personB, LENGTH(COLLECT(s)) AS AToB
MATCH personB-[s?:SENT]->email<-[r:RECEIVED]-personA
RETURN personA.name, personB.name, AToB, LENGTH(COLLECT(s)) AS BToA
Здесь мы начнем с нашего списка людей, а затем найдем все комбинации, в которых personA отправил электронное письмо, полученное personB.
Если мы выполним только первую половину этого, мы увидим комбинации отправленных / полученных писем:
START personA = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"'),
personB = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"')
MATCH personA-[s:SENT]->email<-[r:RECEIVED]-personB
WHERE personA <> personB
RETURN personA, personB, email
==> +---------------------------------------------------------------------------------------------------------+
==> | personA | personB | email |
==> +---------------------------------------------------------------------------------------------------------+
==> | Node[4]{name:"Mark"} | Node[5]{name:"Jim"} | Node[1]{name:"Email 1",title:"Some stuff"} |
==> | Node[4]{name:"Mark"} | Node[5]{name:"Jim"} | Node[2]{name:"Email 2",title:"Absolutely irrelevant"} |
==> | Node[5]{name:"Jim"} | Node[4]{name:"Mark"} | Node[3]{name:"Email 3",title:"Something else"} |
==> | Node[4]{name:"Mark"} | Node[6]{name:"Alistair"} | Node[1]{name:"Email 1",title:"Some stuff"} |
==> +---------------------------------------------------------------------------------------------------------+
Во второй половине запроса мы находим обратные отношения, но мы также хотим указать, не отправил ли один человек какие-либо электронные письма другому (например, Алистер Марку), поэтому я ввел необязательные отношения «ОТПРАВЛЕНО». Если мы запустим это, мы получим следующее:
==> +-------------------------------------------+ ==> | personA.name | personB.name | AToB | BToA | ==> +-------------------------------------------+ ==> | "Jim" | "Mark" | 1 | 2 | ==> | "Mark" | "Alistair" | 1 | 0 | ==> | "Mark" | "Jim" | 2 | 1 | ==> +-------------------------------------------+
Немного лучше, поскольку теперь мы получаем электронные письма, отправленные парами людей в одной строке, но у нас все еще есть дубликаты, например, Jim / Mark и Mark / Jim отображаются в виде отдельных строк, даже если они показывают одну и ту же информацию.
Мы также не увидим строку, если Лицо А не отправило электронное письмо Персоне Б, даже если Лицо Б отправило Лицу А.
На этом этапе я немного застрял, но Макс указал, что мы можем использовать алгоритм всех кратчайших путей для решения проблемы.
Мы начали со следующего запроса:
START personA = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"'),
personB = node:node_auto_index('name:"Mark" name: "Jim" name: "Alistair"')
WITH personA,personB
MATCH p = AllShortestPaths(personA-[:SENT|RECEIVED*..2]-personB)
RETURN p
который возвращает:
==> +------------------------------------------------------------------------------------------------------------------------------+
==> | p |
==> +------------------------------------------------------------------------------------------------------------------------------+
==> | [Node[4]{name:"Mark"}] |
==> | [Node[4]{name:"Mark"},:SENT[0] {},Node[1]{name:"Email 1",title:"Some stuff"},:RECEIVED[1] {},Node[5]{name:"Jim"}] |
==> | [Node[4]{name:"Mark"},:SENT[3] {},Node[2]{name:"Email 2",title:"Absolutely irrelevant"},:RECEIVED[4] {},Node[5]{name:"Jim"}] |
==> | [Node[4]{name:"Mark"},:RECEIVED[6] {},Node[3]{name:"Email 3",title:"Something else"},:SENT[5] {},Node[5]{name:"Jim"}] |
==> | [Node[4]{name:"Mark"},:SENT[0] {},Node[1]{name:"Email 1",title:"Some stuff"},:RECEIVED[2] {},Node[6]{name:"Alistair"}] |
==> | [Node[5]{name:"Jim"},:RECEIVED[1] {},Node[1]{name:"Email 1",title:"Some stuff"},:SENT[0] {},Node[4]{name:"Mark"}] |
==> | [Node[5]{name:"Jim"},:RECEIVED[4] {},Node[2]{name:"Email 2",title:"Absolutely irrelevant"},:SENT[3] {},Node[4]{name:"Mark"}] |
==> | [Node[5]{name:"Jim"},:SENT[5] {},Node[3]{name:"Email 3",title:"Something else"},:RECEIVED[6] {},Node[4]{name:"Mark"}] |
==> | [Node[5]{name:"Jim"}] |
==> | [Node[5]{name:"Jim"},:RECEIVED[1] {},Node[1]{name:"Email 1",title:"Some stuff"},:RECEIVED[2] {},Node[6]{name:"Alistair"}] |
==> | [Node[6]{name:"Alistair"},:RECEIVED[2] {},Node[1]{name:"Email 1",title:"Some stuff"},:SENT[0] {},Node[4]{name:"Mark"}] |
==> | [Node[6]{name:"Alistair"},:RECEIVED[2] {},Node[1]{name:"Email 1",title:"Some stuff"},:RECEIVED[1] {},Node[5]{name:"Jim"}] |
==> | [Node[6]{name:"Alistair"}] |
==> +------------------------------------------------------------------------------------------------------------------------------+
Поскольку нас действительно интересуют только те электронные письма, которые люди посылают друг другу, мы сузим набор результатов, включив в него только эти пути:
START personA = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"'),
personB = node:node_auto_index('name:"Mark" name: "Jim" name: "Alistair"')
WITH personA,personB
MATCH p = AllShortestPaths(personA-[:SENT|RECEIVED*..2]-personB)
WHERE ANY (x IN relationships(p) WHERE TYPE(x)= 'SENT')
RETURN p
==> +------------------------------------------------------------------------------------------------------------------------------+
==> | p |
==> +------------------------------------------------------------------------------------------------------------------------------+
==> | [Node[4]{name:"Mark"},:SENT[0] {},Node[1]{name:"Email 1",title:"Some stuff"},:RECEIVED[1] {},Node[5]{name:"Jim"}] |
==> | [Node[4]{name:"Mark"},:SENT[3] {},Node[2]{name:"Email 2",title:"Absolutely irrelevant"},:RECEIVED[4] {},Node[5]{name:"Jim"}] |
==> | [Node[4]{name:"Mark"},:RECEIVED[6] {},Node[3]{name:"Email 3",title:"Something else"},:SENT[5] {},Node[5]{name:"Jim"}] |
==> | [Node[4]{name:"Mark"},:SENT[0] {},Node[1]{name:"Email 1",title:"Some stuff"},:RECEIVED[2] {},Node[6]{name:"Alistair"}] |
==> | [Node[5]{name:"Jim"},:RECEIVED[1] {},Node[1]{name:"Email 1",title:"Some stuff"},:SENT[0] {},Node[4]{name:"Mark"}] |
==> | [Node[5]{name:"Jim"},:RECEIVED[4] {},Node[2]{name:"Email 2",title:"Absolutely irrelevant"},:SENT[3] {},Node[4]{name:"Mark"}] |
==> | [Node[5]{name:"Jim"},:SENT[5] {},Node[3]{name:"Email 3",title:"Something else"},:RECEIVED[6] {},Node[4]{name:"Mark"}] |
==> | [Node[6]{name:"Alistair"},:RECEIVED[2] {},Node[1]{name:"Email 1",title:"Some stuff"},:SENT[0] {},Node[4]{name:"Mark"}] |
==> +------------------------------------------------------------------------------------------------------------------------------+
В настоящее время есть некоторое дублирование, потому что у нас есть пути, идущие в обоих направлениях между людьми. например
[Node[4]{name:"Mark"},:SENT[0] {},Node[1]{name:"Email 1",title:"Some stuff"},:RECEIVED[1] {},Node[5]{name:"Jim"}]
и:
[Node[5]{name:"Jim"},:RECEIVED[1] {},Node[1]{name:"Email 1",title:"Some stuff"},:SENT[0] {},Node[4]{name:"Mark"}]
ссылаются на то же самое.
Мы отфильтруем, сохранив начальный узел с более высоким идентификатором узла — мы можем использовать любое свойство для этого сравнения, но идентификатор будет делать:
START personA = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"'),
personB = node:node_auto_index('name:"Mark" name: "Jim" name: "Alistair"')
WITH personA,personB
MATCH p = AllShortestPaths(personA-[:SENT|RECEIVED*..2]-personB)
WHERE ANY (x IN relationships(p) WHERE TYPE(x)= 'SENT')
AND ID(head(nodes(p))) > ID(head((tail(tail(nodes(p))))))
RETURN p
==> +------------------------------------------------------------------------------------------------------------------------------+
==> | p |
==> +------------------------------------------------------------------------------------------------------------------------------+
==> | [Node[5]{name:"Jim"},:RECEIVED[1] {},Node[1]{name:"Email 1",title:"Some stuff"},:SENT[0] {},Node[4]{name:"Mark"}] |
==> | [Node[5]{name:"Jim"},:RECEIVED[4] {},Node[2]{name:"Email 2",title:"Absolutely irrelevant"},:SENT[3] {},Node[4]{name:"Mark"}] |
==> | [Node[5]{name:"Jim"},:SENT[5] {},Node[3]{name:"Email 3",title:"Something else"},:RECEIVED[6] {},Node[4]{name:"Mark"}] |
==> | [Node[6]{name:"Alistair"},:RECEIVED[2] {},Node[1]{name:"Email 1",title:"Some stuff"},:SENT[0] {},Node[4]{name:"Mark"}] |
==> +------------------------------------------------------------------------------------------------------------------------------+
Теперь нам просто нужно немного больше манипулировать этими путями, и у нас есть именно то, что нам нужно:
START personA = node:node_auto_index('name:"Mark" name:"Jim" name:"Alistair"'),
personB = node:node_auto_index('name:"Mark" name: "Jim" name: "Alistair"')
WITH personA,personB
MATCH p = AllShortestPaths(personA-[:SENT|RECEIVED*..2]-personB)
WHERE ANY (x IN relationships(p) WHERE TYPE(x)= 'SENT')
AND ID(head(nodes(p))) > ID(head((tail(tail(nodes(p))))))
RETURN HEAD(NODES(p)) AS personA,
HEAD((TAIL(TAIL(NODES(p))))) AS personB,
LENGTH(FILTER(y IN COLLECT(HEAD(RELS(p))): TYPE(y)= 'SENT')) as AToB,
LENGTH(FILTER(y IN COLLECT(HEAD(TAIL(RELS(p)))): TYPE(y)= 'SENT')) as BToA
То, что мы здесь сделали, — это подсчитали количество «ОТПРАВЛЕННЫХ» отношений со стороны пути человека А, а затем проделали то же самое для стороны пути человека В.
В настоящее время нет способа сделать нарезку коллекции в cypher, иначе нам не понадобятся эти вложенные вызовы TAIL!
Однако мы получаем желаемый результат:
==> +---------------------------------------------------------------+
==> | personA | personB | AToB | BToA |
==> +---------------------------------------------------------------+
==> | Node[6]{name:"Alistair"} | Node[4]{name:"Mark"} | 0 | 1 |
==> | Node[5]{name:"Jim"} | Node[4]{name:"Mark"} | 1 | 2 |
==> +---------------------------------------------------------------+
Я понятия не имею, насколько хорошо этот запрос будет работать для любого значительно большего размера набора данных, но, тем не менее, это интересный запрос.