Finding leaf nodes in a Neo4J database

Question

We have a project where we use Spring Data Neo4J. One of the important entities is shown below:

@NodeEntity
public class Category {
    @GraphId
    Long id;

    String name;

    @RelatedTo(direction = Direction.INCOMING, type = "CHILD")
    Category parent;

    @RelatedTo(direction = Direction.OUTGOING, type = "CHILD")
    Set<Category> children;
}

We have a requirement to find out all the leaf categories (that is, categories without any children) starting from a specific category whose name is known. For example, given the hierarchy shown below:

Electronics
    Camera
        Point and Shoot
        SLR
    Computing
        Desktop
        Laptop
        Tablet
        Netbook
Furniture
    Tables
        Office tables
        Home tables
    Chairs
        Lounge chairs
        Office chairs

a search for "Furniture" should return "Office tables", "Home tables", "Lounge chairs" and "Office chairs". Similarly, a search for "Computing" should return "Desktop", "Laptop", "Tablet" and "Netbook".

Need help in creating a cypher query that can be placed on a Spring Data repository method to give me all the leaf nodes starting from the specified node.

EDIT The following query (with the associated Spring Data repository method) worked after help from Wes:

@Query(
"START  category=node:__types__(className='org.example.domain.Category') " +
"MATCH  category-[:CHILD*0..]->child " +
"WHERE  category.name={0} AND NOT(child-[:CHILD]->()) " +
"RETURN child")
List<Category> findLeaves(String name);

Eve Freeman · Accepted Answer · 2017-01-07T19:05:47.080

This is the simplest way I've found with cypher: http://console.neo4j.org/r/cgrndo

start n=node(*) // you can specify a single node here if you want
match n-[r*]->m
where not(m-->()) // this limits m to be only leaf nodes 
return distinct m; // this returns the distinct leaf nodes (not necessary if there are only simple paths)

Edit: (since people are recently upvoting this... here's an update using 3.x cypher)

match (n) 
where not (n)-->() 
return distinct n

score -1 · Answer 2 · answered Jan 06 '17 at 18:35

-1

If you are looking to find all the leaf nodes in cypher 3.0
http://console.neo4j.org/r/leaf-nodes

match (n)-[r]-() with n, count(r) as c where c = 1 return n

answered Jan 06 '17 at 18:35

Scott

1,648
13
21

This only works if relationship direction isn't a factor in the graph's parent/child relationship (where both nodes in a 2-node subgraph would be considered leaf nodes). Otherwise this won't work, as the query will also match on the parent of a 2-node subgraph (as well as its child). By definition a leaf node is a node without any child nodes (but at least one parent node), and that is not what this query is checking. This query will also fail to identify leaf nodes in a non-tree graph, where there are multiple incoming relationships but no outgoing relationships. – InverseFalcon Jan 06 '17 at 23:55
Yes for an undirected graph – Scott Jan 07 '17 at 01:10

Finding leaf nodes in a Neo4J database

2 Answers2