Query for reachability matrix using neo4j

Hello all.

I am trying to find the reachability matrix for a graph.

Reachability matrix (is a N*N matrix) implies ---> If a directed edge from node i to node j in the reachability graph (i.e., reachability matrix element R ij = 1) indicates that one can reach node j from node i either directly or indirectly.

I used the below query:

match (n:Operator ), (m:Operator )
return n.id, m.id,
case
when n.id = m.id then 1
when (n)-->(m) then 1
else 0
end as value

Output which I am getting using above code is:

In line 5- It gives a output value of 1 if an edge exists between the nodes n & m , else gives 0.

But instead I'm trying to get output value 1 if a path exists to reach node n from node m either directly or indirectly .

How can I satisfy this condition?

Thank you.

Hello @munavath.2001077 :slight_smile:

This query should do the job:

MATCH (n)
WITH collect(n) AS nodes
UNWIND nodes AS a
UNWIND nodes AS b
RETURN a.id AS n1, b.id AS n2, 
CASE 
WHEN a.id = b.id THEN 1 
WHEN EXISTS((a)-[*]->(b)) THEN 1 
ELSE 0 
END AS value

You can also use EXISTS((a)-[*]-(b)) if you don't want to restrict the direction.

Regards,
Cobra

1 Like

Thank you @Cobra for the reply. I have run the query, but it keeps on running but not showing the output? What would be the issue ?

How many nodes do you have?
Do there is only Operator nodes or do you have other types?

Below is the query which I have been using and I have 6 nodes, also has additional label only on start & end node:

LOAD CSV WITH HEADERS from "file:///C:/Process.csv" AS line
WITH collect(line.`Operator ID`) AS ids, collect(line.`Activity Done`) AS activities, collect(line.path) AS path
UNWIND ids AS id
MERGE (n:Operator {id: id})
WITH DISTINCT ids, activities, path
UNWIND range(0, size(ids)-1) AS i
WITH ids[i] AS a, ids[i+1] AS b, i, activities, path
WHERE a IS NOT null AND b IS NOT null
MATCH (n:Operator {id: a})
MATCH (m:Operator {id: b})
CALL apoc.merge.relationship(n, activities[i], {path: path[i]}, {path: path[i]}, m, {path: path[i]})
YIELD rel
WITH apoc.coll.flatten(collect([startNode(rel), endNode(rel)])) AS nodes
WITH [head(nodes), last(nodes)] AS startEnd
UNWIND startEnd AS n
MATCH (n)
SET n:StartEnd

This query tooks 4ms on my database:

MATCH (n:Operator)
WITH collect(n) AS nodes
UNWIND nodes AS a
UNWIND nodes AS b
WITH a, b, CASE WHEN a = b THEN 1 WHEN EXISTS((a)-[*]->(b)) THEN 1 ELSE 0 END AS value
RETURN a.id, b.id, value

It is working @Cobra , Thank you.

But in one case I had 10 nodes and 28 relationship there it keeps on running but not showing the output. I am assuming it takes time as the number of nodes & relationship increase?

That's weird, can you send me the file?

Sorry my mistake, Here is the file @Cobra :

New Text Document.txt (406 Bytes)

You can upload the file directly but you must replace the .csv by .txt.

I got the same problem :slight_smile:

Here is the solution:

MATCH (n:Operator)
WITH collect(n) AS nodes
UNWIND nodes AS a
UNWIND nodes AS b
WITH a, b
RETURN a.id, b.id,
CASE
WHEN a = b THEN 1 
WHEN length(shortestPath((a)-[*]->(b))) IS NOT NULL THEN 1 ELSE 0 
END AS value
1 Like

Its working perfectly now @Cobra , Thank you.

1 Like