1

I'm using Memgraph (but open to using Neo4j) and need some help on building a recursive query to build out a tree. I'm new to Cypher so my attempts so far haven't been successful. I've played around with the CALL subqueries but can't seem to get the format and ordering right.

My goals are:

  1. Be able to fetch a Node, and its direct edges - but the edges should be limited to a certain number sorted by a edge property value. E.g. Get Node A and 3 of its edges ordered by property X.
  2. Be able to fetch a Node, and based on some variable be able to specify the depth to "walk" to tree. E.g. Get Node A, and for each of its 3 edges (sorted by X), get those edge's edges the using the same filter function, up to the depth limit. Bonus points if it can filter out the parent node so it's only a directed tree.

Some concrete examples - given the following graph. Note this is not real data and I'm aware the "age" property is not symmetrical between Nodes. Just threw it together for the question.

CREATE (n0:Node {name: "a"}) CREATE (n1:Node {name: "b"}) CREATE (n2:Node {name: "c"}) CREATE (n3:Node {name: "d"}) CREATE (n4:Node {name: "e"}) CREATE (n5:Node {name: "f"}) CREATE (n6:Node {name: "g"}) CREATE (n7:Node {name: "h"}) CREATE (n8:Node {name: "i"}) CREATE (n9:Node {name: "j"});
CREATE (n0)-[:KNOWN_FOR {age: 20} ]->(n2) CREATE (n0)-[:KNOWN_FOR {age: 7} ]->(n1) CREATE (n0)-[:KNOWN_FOR {age: 15} ]->(n4) CREATE (n0)-[:KNOWN_FOR {age: 23} ]->(n3) CREATE (n0)-[:KNOWN_FOR {age: 5} ]->(n7) CREATE (n1)-[:KNOWN_FOR {age: 10} ]->(n6) CREATE (n1)-[:KNOWN_FOR {age: 14} ]->(n2) CREATE (n1)-[:KNOWN_FOR {age: 24} ]->(n3) CREATE (n1)-[:KNOWN_FOR {age: 19} ]->(n5) CREATE (n2)-[:KNOWN_FOR {age: 24} ]->(n8) CREATE (n2)-[:KNOWN_FOR {age: 25} ]->(n3) CREATE (n2)-[:KNOWN_FOR {age: 17} ]->(n1) CREATE (n3)-[:KNOWN_FOR {age: 7} ]->(n4) CREATE (n3)-[:KNOWN_FOR {age: 10} ]->(n7) CREATE (n3)-[:KNOWN_FOR {age: 25} ]->(n6) CREATE (n3)-[:KNOWN_FOR {age: 22} ]->(n1)CREATE (n4)-[:KNOWN_FOR {age: 21} ]->(n0) CREATE (n4)-[:KNOWN_FOR {age: 24} ]->(n6) CREATE (n4)-[:KNOWN_FOR {age: 17} ]->(n8) CREATE (n5)-[:KNOWN_FOR {age: 14} ]->(n9) CREATE (n5)-[:KNOWN_FOR {age: 8} ]->(n0) CREATE (n5)-[:KNOWN_FOR {age: 15} ]->(n8) CREATE (n5)-[:KNOWN_FOR {age: 18} ]->(n6) CREATE (n5)-[:KNOWN_FOR {age: 22} ]->(n4) CREATE (n6)-[:KNOWN_FOR {age: 7} ]->(n4) CREATE (n6)-[:KNOWN_FOR {age: 21} ]->(n2) CREATE (n7)-[:KNOWN_FOR {age: 25} ]->(n3) CREATE (n8)-[:KNOWN_FOR {age: 18} ]->(n7) CREATE (n8)-[:KNOWN_FOR {age: 12} ]->(n3) CREATE (n9)-[:KNOWN_FOR {age: 14} ]->(n4) CREATE (n9)-[:KNOWN_FOR {age: 15} ]->(n3) CREATE (n9)-[:KNOWN_FOR {age: 7} ]->(n2) CREATE (n9)-[:KNOWN_FOR {age: 14} ]->(n8);

Example Graph

Examples

Get Node A and 3 of its children ordered by KNOWN_FOR age desc, where age > 5. Should return:

A ->
  - D (age: 23)
  - C (age: 20)
  - E (age: 15)

Get Node A, and its children to a depth of 3, where its children have a limit of 2 order by age desc. Should return:

A 
  -> D (age: 23)
    -> G (age: 25)
      -> C (age: 21)
      -> E (age: 7)
    -> B (age: 22)
      -> D (age: 24)
      -> F (age: 19)
  -> C (age: 20)
    -> D (age: 25)
      -> G (age: 25)
      -> B (age: 22)
    -> I (age: 24)
      -> H (age: 18)
      -> D (age: 12)
  -> E (age: 15)
    -> G (age: 24)
      -> C (age: 21)
      -> E (age: 7)
    -> A (age: 21)
      -> D (age: 23)
      -> C (age: 20)

I don't mind to much on the format of the return data, as long as it includes the nodes and relationship value between them. Something as simple as this is ideal:

A, D, 23
D, G, 25

But if its a nested array, I can parse it out on the function that wraps the query.

cybersam
  • 63,203
  • 6
  • 53
  • 76
NathanS
  • 163
  • 2
  • 10

1 Answers1

1

from what I understood that you are looking for bfs traversal. On Memgraph you can check it out here: https://memgraph.com/docs/memgraph/reference-guide/built-in-graph-algorithms#breadth-first-search

For the first question ("Get Node A and 3 of its children ordered by KNOWN_FOR age desc, where age > 5."), this should be a query:

MATCH path=(n:Node {name:"a"})-[rels *bfs..1]->(m)
WITH n, m,  rels[0] as rel0
WHERE rel0.age > 5
RETURN n.name, m.name, rel0.age
ORDER BY rel0.age DESC;

Basically, here, you get a node with property name "a", then do bfs of up to max 1 step to some node m. Now, in variable rels you will have all the relationships that bfs visits. In bfs it will visit relationships at some order, but to get data sorted on output you will need ORDER BY and then reference rel0's property age. Also, I am getting different output here, I think you are missing node "B" with value 7.

For the second question () if I understood correctly you want to expand from node A up to 3 steps and then order by age property in a way that you first compare all relationships on the first expansion, and then on second.

There are two options for that as I see it in Memgraph:

MATCH path=(n:Node {name:"a"})-[rels *bfs..3]->(m)
WITH path, n, m,  rels[0] as rel0, rels[1] as rel1, rels[2] as rel2
RETURN n.name ,m.name, rel0.age, rel1.age, rel2.age, extract(p IN nodes(path) | p.name) as nodes
ORDER BY rel0.age DESC, rel1.age DESC, rel2.age DESC;

and second one:

MATCH path=(n:Node {name:"a"})-[rels *bfs..3]->(m)
WITH n, m,  extract(r IN rels | r.age) as ages_list, rels
WHERE ages_list[0] > 5
RETURN n.name ,m.name, ages_list
ORDER BY ages_list[0] DESC, ages_list[1] DESC;

The idea behind the second option is to extract properties in the list and then compare the values of the list. There is no error thrown if there is no value in the list, it will return null. Basically, it will first compare all age values on first expansion, and then on second, etc...

Let me know if you have any more questions. Also, a good tutorial on BFS can be found on Memgraph's Playground: https://playground.memgraph.com/topic/cypher-breadth-first-search.

For more docs, check Memgraph's site I linked, it should be helpful.

Antonio Filipovic
  • 11
  • 1