Neo4j - Finding the nearby node set

Question

I would like to obtain a node close to a certain node using Neo4j.

Techniques that take edge costs into account are popular, but the method using node cost is not.

For example, in this sample Graph, the nodes in the vicinity of node A are B, C, E, G, H, I.

The total cost is within 15.
The cost of A is not included.
The edge direction can be ignored.

The minimum cost between nodes of the sample graph is expected as follows.

A<->B : 3
A<->C : 8
A<->D : 50
A<->E : 10
A<->F : 16
A<->G : 11
A<->H : 13
A<->I : 14

The sample graph can be created with the following query.

CREATE
(a:Node{name:"A",cost:10}),
(b:Node{name:"B",cost:3}),
(c:Node{name:"C",cost:5}),
(d:Node{name:"D",cost:50}),
(e:Node{name:"E",cost:10}),
(f:Node{name:"F",cost:8}),
(g:Node{name:"G",cost:1}),
(h:Node{name:"H",cost:2}),
(i:Node{name:"I",cost:1}),
(a)-[:Edge]->(b),
(b)-[:Edge]->(c),
(a)-[:Edge]->(d),
(a)-[:Edge]->(e),
(c)-[:Edge]->(f),
(d)-[:Edge]->(f),
(e)-[:Edge]->(g),
(g)-[:Edge]->(h),
(h)-[:Edge]->(i),
(f)-[:Edge]->(i);

In response to comments, I rebuilt the graph. Added edge to calculate cost.

MATCH (n)-[]-(m)
MERGE (n)-[r:COST{cost:m.cost}]->(m)

And I executed the following query.

MATCH(startNode:Node{name:"A"}),(endNode:Node)
CALL algo.shortestPath(startNode, endNode, "cost",{relationshipQuery:'COST', defaultValue:1.0,write:false,direction:'OUTGOING'})
YIELD nodeCount, totalCost
WITH nodeCount, totalCost, endNode
WHERE totalCost <= 15
RETURN nodeCount, totalCost, endNode
ORDER BY totalCost ASC;

Then I got the results I expected.

╒═══════════╤═══════════╤══════════════════════╕
│"nodeCount"│"totalCost"│"endNode"             │
╞═══════════╪═══════════╪══════════════════════╡
│0          │-1         │{"name":"A","cost":10}│
├───────────┼───────────┼──────────────────────┤
│2          │3          │{"name":"B","cost":3} │
├───────────┼───────────┼──────────────────────┤
│3          │8          │{"name":"C","cost":5} │
├───────────┼───────────┼──────────────────────┤
│2          │10         │{"name":"E","cost":10}│
├───────────┼───────────┼──────────────────────┤
│3          │11         │{"name":"G","cost":1} │
├───────────┼───────────┼──────────────────────┤
│4          │13         │{"name":"H","cost":2} │
├───────────┼───────────┼──────────────────────┤
│5          │14         │{"name":"I","cost":1} │
└───────────┴───────────┴──────────────────────┘

However, when I executed a similar query in the database I actually use, I could not do it due to a huge amount of computation...

Failed to invoke procedure `algo.shortestPath`: Caused by: java.lang.ArrayIndexOutOfBoundsException: -1340037571

Does anyone have an idea to search nearby node set efficiently?

Why not run a cypher query to update all incoming edges to the node and set the weight of the edge to be the weight of the node? Then the standard edge-weighted approaches should work just as you want. — FrobberOfBits
Thanks for your comment. When I rebuilt the sample graph, it worked properly in the graph. However, the computational complexity has become enormous on the database that I actually want to apply... For details, look the edited questions. — tekunikaruza

logisima logisima · Accepted Answer · 2017-12-19T16:46:08

You can do it with this cypher query :

MATCH p=(start {name:"A"})-[r*..10]-(end {name:"I"})
RETURN reduce(x=0, n IN tail(nodes(p)) | x + n.cost) AS cost
ORDER BY cost ASC
LIMIT 1

But in this case, Neo4j will search all existing paths between start and end, then it will compute the global cost. So it's an expensive query ...

If you want performances, you should take a look a the implementation of the algo.shortestPath function from the graph-algo to create your own procedure/algo.

Neo4j - Finding the nearby node set

1 Answers