neo4j: Return all nodes on the longest matching patch

Question

Using neo4j 1.9.4 and py2neo 1.6, I have a binary tree like structure in my graph, where each node has up to two children. However, the graph is not complete, so it might look like this, where "(x)" represents nodes and "[y]" represents relations.

                     (root)
                     /     \
                   [0]     [1]
                   /         \
                 (0)         (1)
                /   \          \
              [0]   [1]        [1]
              /       \          \
            (00)      (01)       (11)
            /
          [0]
          /
       (000)

I made up some similar example here: http://console.neo4j.org/r/ni6t5b (If it is not working for some reason, you can create the graph using the following command:

CREATE (node1 { name: '1' }),(node2 { name: '11' }),(node3 { name: '10' }),(node4 { name: '0' }),(node5 { name: '01' }),(node6 { name: '00' }),(node7 { name: '10' }),(root { name:'root' }), root-[:`1`]->node1, node1-[:`1`]->node2, node1-[:`0`]->node7, node2-[:`0`]->node3, root-[:`0`]->node4, node4-[:`1`]->node5, node4-[:`0`]->node6

I would like to return all nodes that exist on a (single) specific path.

START root=node(1) 
MATCH path = root-[?:`0`]-()-[?:`0`]-()-[?:`0`]-() 
RETURN NODES(path)

(Note: let ID(root) = 1) This will return all nodes that are in the path, namely (0), (00) and (000) However, as I don't know what depth each branch has, I also want to query something like this:

START root=node(1) 
MATCH path = root-[?:`1`]-()-[?:`1`]-()-[?:`0`]-()-[?:`0`]-() 
RETURN NODES(path)

This should return all nodes that are on the longest possible path, i.e. (1) and (11). In fact, this query does not return anything. How can I achieve that? Note: For each path, I don't know beforehand, if this path has an existing end node or not. I only want to return all nodes on that path that exist.

Additionally, whats the best way to automatically construct such a query using py2neo (python). For example, I have a list containing several paths of which I need to query each of them. Each path just existing out of '0's and '1's ?

list_of_paths = ["0010", "101", "11", "101110"]

Thank you, guys!

EDIT: Here (http://wes.skeweredrook.com/cypher-longest-path/) I could find a similar problem. However, the relation type is always the same, which does not hold for my scenario. So I think I can't adopt this solution from there.

EDIT2: The suggestions of Wes does not solve my problem:

START root=node(1)
MATCH path=root-[:`1`|`0`*]->leaf
RETURN path

This query returns all possible paths starting from the root-node. What I want is the nodes of one specific path.

EDIT3: The updated suggestion of Wes does not solve my problem either. It only returns the longest existing Path of the whole graph. But I want to query a specific path and return all nodes up to the point where the path does not exist in the graph anymore. So I could want to query a really long path, but in fact the path already stops at the first node, e.g. root-[1]->()-[0]->()-... This query should only return node (1) as the path stops at that point. (Node (1) has no outgoing relation of type 0)

EDIT4: I tried to figure out a solution which works, but it is quite dirty.

tree_root, = graph_db.create({"name": "root"}) # create a root

node_list = []
my_path = [1, 1, 0, 1, 1, 1] # path to query
len_of_path = len(my_path)

# add the corresponding number of nodes to the list and name them n0,..nX
for i in range(0,len_of_path):
    node_list.append("n"+str(i))


# construct the query string
my_query_start = 'START root=node({root_id}) MATCH (root)'
my_query_return = ' RETURN'

for i in range(0, len(node_list)):
    my_query_start += '-[?:`' + str(my_path[i]) + '`]->(' + str(node_list[i]) + ')'
    if i == len(node_list)-1:
        my_query_return += ' ' + str(node_list[i])
    else:
        my_query_return += ' ' + str(node_list[i]) + ','

# concatenate the query
complete_query = my_query_start + my_query_return
#print "complete_query:", complete_query

# execute the query
query_paths = neo4j.CypherQuery(graph_db, complete_query)
params = {"root_id" : tree_root._id}
my_list_of_nodes = query_paths.execute(**params)

#output results
print "data of my_list_of_nodes:", my_list_of_nodes.data
print "columns of my_list_of_nodes:", my_list_of_nodes.columns

Please guys, don't tell me that this is supposed to be the final solution ;-)

Answer 1

Can you possibly use a variable length path with an OR for the reltype?

MATCH path=root-***put your partial pattern here***->[:`1`|`0`*]->leaf
WHERE NOT (leaf)-[:`0`|`1`]->()
RETURN path
ORDER BY length(path) DESC
LIMIT 1

I think it solves your example... but is it more complicated than that?