CODEWITHSUNDEEP
graphneo4jcyphergraph-databasesshortest-path
tekunikaruza
tekunikaruza

Reputation: 109

Neo4j - Finding the nearby node set

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 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?

Upvotes: 1

Views: 166

Answers (1)

logisima
logisima

Reputation: 7458

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.

Upvotes: 1

Related Questions