"Appendix" sub-graph detection

[nissimsan]

Hey Neo4j! 

I'm looking for a way from a given "start" node to find all sub graphs which does not lead to a particular type of "end" node. I've attached a diagram of the kind of picture I want to produce, the "appendix" is marked in red, the rest in green. 

GDS allShortestPaths at first seemed applicable, but
1) will not find longer-than-the-shortest-but-valid paths,
2) does not return the nodes and relationships along the way which I want to .write. 

Can you hint at what would be the approach I should take with this, pls? Am I overlooking this algorithm (in GDS or APOC), or do I need to write my own custom algo for this?

Thanks a ton in advance! 

Nis

Bonus question (for extra credit!):
Ideally I would want this not just as boolean values, but multiply a factor from the edges and store on nodes as the traversal progresses from start to end. 

[glilienfield · Accepted solution]

Look at apoc path methods:

https://neo4j.com/labs/apoc/4.1/overview/apoc.path/

you should be able to achieve this in cypher, but it may not be efficient for a large graph. Something like this: 

match(s:Label{id:0})

match p=(s)-[*]->(e)

where not exists ( (e)—>() )

and not e:Appendix 

with nodes(p) as n, relationships(p) as rels

unwind n as node 

with collect ( distinct n) as nodes, rels

unwind rels as rel

return nodes, collect (distinct rel) as relationships 

Your extra credit answer would be to write your own custom procedure to traverse and update nodes in any manor you need. 

[nissimsan]

match p=(s)-[*]-(e)  does the trick. Indeed, it won't scale, but that's fine, I have other ways of running it just on subgraphs. 

Also, good to know that there isn't a traversal algo I am overlooking. 

Cheers!

[glilienfield]

Glad the worked.  Writing a custom procedure is not difficult if you are java developer. The biggest hurdle is just getting a working unit test working for a shell procedure.  Once that is done, writing the logic is not difficult. the code is compiled to a jar, which is then deployed to the server. The procedure is then available in your cypher queries. I can provide you with an example if this is something you are interested in. 

[nissimsan]

I'd actually appreciate an example to get me started on that! I do know Java, and the idea of calling procedures from cypher is very appealing! Thanks!

[glilienfield]

I will put something together. 

[nissimsan]

https://medium.com/@nis.jespersen/the-united-nations-trust-graph-d65af7b0b678

^ Here's the result of what I was building