[FIXED] How to find all nodes connected to certain nodes in a directed graph in Neo4j without infinite loops?

Issue

I'm using Neo4j. I want to find all nodes that connect (by one direction) to certain nodes targets in a one-way directed graph (maybe with loops). For example:

targets: [4]
1->2->3->[4]->2->...
1->5->6->7->5->...

Now 4 is the target node, but there can be more than one target node. I want to find 1,2,3,4 as the result, since they can connect with target node t, while 5,6,7 cannot.

I would like to know how to make it by Cypher in Neo4j.

My first thought was:

MATCH (target) WHERE id(target) IN [4]
MATCH p=(a)-[:Rel*]->(target)
MATCH (a)-[r:Rel]->(c) WHERE a IN nodes(p) AND c IN nodes(p)
RETURN a,c

It worked well when there was no loop, but when there're loops the [:Rel*] will run infinitely, for example finding paths to 4 in 5,6,7.

I had an idea (inspired by Label Propagation) to solve it:

1. Mark target nodes 'red'.
2. Mark all nodes which has a outgoing relationship to 'red' nodes 'red', too.
3. Repeat Step 2 until there're no more new 'red' nodes.
4. All 'red' nodes (including target nodes) are in the same result subgraph now.

But I cannot figure out how to write it in Cypher, as it contains recursions, and I'm having difficulties writing those Java User-defined procedures for Neo4j.

Can it be written in Cypher, or are there already any solutions for tasks like this one? I didn't find useful tools in Apoc or Graph Data Science libraries.

Any help would be appreciated, thanks!

Solution

One way is using apoc.path.expandConfig. This is part of the apoc plugin that you can easily enable on your neo4j db. Using it, you can run something like:

MATCH (target) WHERE id(target) IN [4]
CALL apoc.path.expandConfig(target, {
    relationshipFilter: "<Rel",
    maxLevel: 10 //This is optional
})
YIELD path
RETURN path

On the first line you find your target nodes, as you did. The relationshipFilter "<REL" will allow traversing only on nodes pointing at the target direction.

Answered By - nimrod serok

Answer Checked By - Candace Johnson (PHPFixing Volunteer)