Shortests weighted path with Neo4j.rb and Ruby On Rails

130 Views Asked by At

I am trying to calculate the shortest weighted path between two nodes. Here's my User class:

class User
  include Neo4j::ActiveNode
  property :name, type: String
  has_many :both, :friends, rel_class: :Friendship, model_class: :User
end

Users are nodes and the relationship between them is:

class Friendship
  include Neo4j::ActiveRel

  before_save :set_weight
  from_class :User
  to_class :User
  type 'FRIENDSHIP'
  property :weight

  def set_weight
    ...
  end

The property weight is the value of the haversine distance between both nodes.

I figured out how to write the query to get all the paths that conect user_a with user_b:

all_paths = a.query_as(:a).match_nodes(b: b).match('p=((a)-[*]-(b))').pluck(:p)

And I'm sure that I can chain methods to this query to get the shortest path based on the weight but I couldn't find the right Cypher syntax so I ended iterating every path and calculating the total weight for each path to get the shortest one:

def shortest_weighted_path(start_user_id, end_user_id)
  a = User.find(start_user_id)
  b = User.find(end_user_id)

  all_paths = a.query_as(:a).match_nodes(b: b).match('p=((a)-[*]-(b))').pluck(:p)
  paths_and_weights = {}
  all_paths.each_with_index do |path, index|
    total_weight = 0
    path.relationships.each { |relationship| total_weight = total_weight + relationship.properties[:weight] }
    paths_and_weights[index] = total_weight
  end
  paths_and_weights = paths_and_weights.sort_by {|_key, value| value}.to_h
  shortest_path_index = paths_and_weights.keys.first
  shortest_path = all_paths[shortest_path_index]

  nodes_in_path = []
  shortest_path.nodes.each { |node| nodes_in_path << node.properties[:uuid] }
  nodes_in_path
end

Googling some more I found and example on how to calculate the shortest path with Cypher:

START  startNode=node:node_auto_index(name={startNode}),
   endNode=node:node_auto_index(name={endNode})
MATCH  p=(startNode)-[:CONNECTED_TO*1..4]->(endNode)
RETURN p AS shortestPath, 
       reduce(weight=0, r in relationships(p) : weight+r.weight) AS   totalWeight
     ORDER BY totalWeight ASC
     LIMIT 1

So my question is: how can I write this query for Neo4j.rb based in my User-Friendship example?

0

There are 0 best solutions below