Match Only Full Paths in Neo4J with Cypher (not sub-paths)

Question

If I have a graph like the following (where the nesting could go on for an arbitrary number of nodes):

(a)-[:KNOWS]->(b)-[:KNOWS]->(c)-[:KNOWS]->(d)-[:KNOWS]->(e)
               |             |
               |            (i)-[:KNOWS]->(j)
               |
              (f)-[:KNOWS]->(g)-[:KNOWS]->(h)-[:KNOWS]->(n)
                             |
                            (k)-[:KNOWS]->(l)-[:KNOWS]->(m)

How can I retrieve all of the full-length paths (in this case, from (a)-->(m), (a)-->(n) (a)-->(j) and (a)-->(e)? The query should also be able to return the nodes with no relationships of the given type.

So far I am just doing the following (I only want the id property):

MATCH path=(a)-[:KNOWS*]->(b)
RETURN collect(extract(n in nodes(path) | n.id)) as paths

I need the paths so that in the programming language (in this case clojure) I can create a nested map like this:

{"a" {"b" {"f" {"g" {"k" {"l" {"m" nil}}
                     "h" {"n" nil}}}
           "c" {"d" {"e" nil}
                "i" {"j" nil}}}}}

Is it possible to generate the map directly with the query?

Answer 1

Just had to do something similar, this worked on your example, finds all nodes which do not have outgoing [:KNOWS]:

match p=(a:Node {name:'a'})-[:KNOWS*]->(b:Node)
optional match (b)-[v:KNOWS]->()
with p,v
where v IS NULL
return collect(extract(n in nodes(p) | n.id)) as paths

Answer 2

Here is one query that will get you started. This query will return just the longest chain of nodes when there is a single chain without forks. It matches all of the paths like yours does but only returns the longest one by using limit to reduce the result.

MATCH p=(a:Node {name:'a'})-[:KNOWS*]->(:Node)
WITH length(p) AS size, p
ORDER BY size DESC
LIMIT 1
RETURN p AS Longest_Path

I think this gets the second part of your question where there are multiple paths. It looks for paths where the last node does not have an outbound :KNOWS relationship and where the starting node does not have an inbound :KNOWS relationship.

MATCH p=(a:Node {name:'a'})-[:KNOWS*]->(x:Node)
WHERE NOT x-[:KNOWS]->()
AND NOT ()-[:KNOWS]->(a)
WITH length(p) AS size, p
ORDER BY size DESC
RETURN reduce(node_ids = [], n IN nodes(p) | node_ids + [id(n)])