Кратчайший взвешенный путь с Neo4j.rb и Ruby On Rails - PullRequest
Новая
       27

Кратчайший взвешенный путь с Neo4j.rb и Ruby On Rails

0 голосов
/ 14 октября 2018

Я пытаюсь вычислить кратчайший взвешенный путь между двумя узлами.Вот мой класс User: 

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

Пользователи - это узлы, и отношения между ними: 

class Friendship
  include Neo4j::ActiveRel

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

  def set_weight
    ...
  end

Вес свойства - это значение расстояния haversine между обоими узлами.

Я выяснил, как написать запрос, чтобы получить все пути, которые связывают user_a с user_b: 

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

И я уверен, что могу связать методы с этим запросом, чтобы получить кратчайший путь на основена вес, но я не смог найти правильный синтаксис Cypher, поэтому я закончил итерацию каждого пути и вычисление общего веса для каждого пути, чтобы получить самый короткий из них: 

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

Погуглив еще немного, я нашел и примерКак рассчитать кратчайший путь с помощью 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

Итак, мой вопрос: как я могу написать этот запрос для Neo4j.rb на основе моего примера User-Friendship?

...