Collecting conditional data as you traverse a graph

[James Newton]

I do not have much experience with Neo4j. For the project that I am just starting I am hoping that Neo4j will provide a good solution to the following problem.

Imagine a maze with rooms (nodes) and doors (relationships) between the rooms. The doors to some rooms are locked and their keys are held in other rooms (as properties).

In the attached image, you can reach room D by following the path A->B->C->A, picking up the key for room D in room B. However it is not possible to reach room F, since the key to room F is in room E, and the key to room E is in room D, and there is no way back from room D to room A, so room E is inaccessible (Creating a new door from room D to room C would make this possible).

I understand how I can use Neo4j to trace a path from room to room, but is it possible to create queries which take into account the keys that can be picked up on the way? For example:

• Is it possible to get from room X to room Y?
• What are all the paths that lead from room A to room Z?
  
• I'm in room N with these keys. Have I come to a dead end?
• What keys do I need to get from the Library to the Conservatory?

I can imagine ways of doing this that make multiple queries to the database, with each new query being dependent on the result of the previous ones, but this is likely to be laborious.

I can also imagine a single Cypher query that creates a temporary node, adds keys to this node as it traverses the graph, and checks at each door-relationship whether it has the appropriate key to continue in that direction. However, I don't know enough about Cypher to know whether this can be done.

I'm more than happy to solve this problem myself, if you can confirm that Neo4j can do this.

[Michael Hunger]

something like this?

create index on :Room(id)

// find the two rooms and all paths between them

match path = (:Room {id:1})-[:DOOR*0..]->(:Room {id:10})

// take path, keys and doors as collections

with path, extract(room IN nodes(path) | coalesce(room.key,-1)) as keys, rels(path) as doors

// condition for all doors

// either no lock or the lock-number is in the collection of keys collected so far

where all(idx in range(0,size(doors)-1) WHERE NOT doors[idx].lock OR doors[idx].lock IN keys[0..idx])

// return the path(s)

return path;

Perhaps you can provide a sample graph, then this could become a fun graphgist (graphgist.neo4j.com) and a really good blog post. WDYT ?

Cheers, Michael

--
You received this message because you are subscribed to the Google Groups "Neo4j" group.
To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
<map.png>

[Michael Hunger]

Cool, please add your picture and prose from the email too

Put the index stmt in front of your create and place a semicolon at the end.

Von meinem iPhone gesendet

Am 26.08.2015 um 16:47 schrieb James Newton <james.l...@gmail.com>:

Thanks, Michael.

All this is new to me. I've created a graphgist of the mini-maze that I used in my example:

http://gist.neo4j.org/?9f6627661d370dac98ea

May the fun begin!

James

[James Newton]

Thanks, Michael.

All this is new to me. I've created a graphgist of the mini-maze that I used in my example:

http://gist.neo4j.org/?9f6627661d370dac98ea

I've modified your query but in 'cargo cult code' fashion, since I'm out of my depth here... for now

[Michael Hunger]

I forked your gist and fixed it, hope you like it.

http://gist.neo4j.org/?43c6ee500e6fe97868df

Except the last thing which doesn't work due to Cyphers default relationship-uniqueness (a relationship has to be unique per path) approach. It's possible with Neo4j's traversal & Java APIs though.

[James Newton]

I do like it!

Thank you so much for this Michael! It's a great help. You have given me plenty to think about. It's good to see confirmation that a single Cypher query can do so much. It's also good to know about the limitations.

I have checked out Neo4j's Traversal Framework. I am going to be creating my app in Meteor and Google tells me that there is not much available, but perhaps there is a Node.js module that I can use to look for paths on the server. Does that sound feasible?

The app that I am creating will run in both Author mode and Reader mode. These circuitous queries will only be needed in Author mode, to allow the author to check the integrity of the network of paths s/he is creating. For this reason, performance will not be critical.