Возвращение самого тяжелого пути (с наибольшей суммой данного свойства во всех его отношениях) от узла ко всем его листьям - PullRequest
Новая
       21

Возвращение самого тяжелого пути (с наибольшей суммой данного свойства во всех его отношениях) от узла ко всем его листьям

0 голосов
/ 30 апреля 2019

Есть ли способ написать запрос Cypher, который возвращает путь с наибольшей суммой всех (выбранных) свойств отношения среди всех существующих путей от данного узла к его дочерним элементам?

Здравствуйте, сначала я хотел бы указать, как я создал график: 

CREATE CONSTRAINT ON (j:JOB) ASSERT j.order_id IS UNIQUE

USING PERIODIC COMMIT 1000
//EXPLAIN
LOAD CSV WITH HEADERS FROM "file:///jobs.csv" AS row
MERGE (j:JOB {order_id: row.child_order_id})
SET j.job_name = row.child_job_name,
    j.job_owner = row.child_job_owner,
    j.group_name = row.child_group_name,
    j.order_time = row.child_order_time,
    j.start_time = row.child_start_time,
    j.end_time = row.child_end_time;

USING PERIODIC COMMIT 1000
LOAD CSV WITH HEADERS FROM "file:///child_father.csv" AS row
MATCH (c:JOB {order_id: row.child_order_id})
MATCH (f:JOB {order_id: row.father_order_id})
MERGE (c)-[d:DEPENDS_ON]->(f)
SET d.elapsed_min = row.elapsed_min;

Теперь моя цель - вернуть путь с наибольшей суммой свойства отношений elapsed_min из заданного идентификатора заказа всемконечные узлы, от которых это зависит.

, так как я не смог найти способ сделать это в Cypher, я попробовал на python использовать библиотеку py2neo.Сначала я попытался использовать обычный алгоритм Дейкста, чтобы вернуть самый легкий путь, и после того, как я смог сделать это, я изменил алгоритм, чтобы вернуть самый тяжелый путь

, поэтому я сделал это: 

import py2neo
from py2neo import Graph
from py2neo import Node, Relationship

NEO4J_URI = "bolt://127.0.0.1:7687"
NEO4J_USER = "neo4j"
NEO4J_PASSWORD = "neo4j"

graph = Graph(NEO4J_URI, auth = (NEO4J_USER, NEO4J_PASSWORD), bolt = True)

def dijkstra(graph,start,goal):
    shortest_distance = {}
    predecessor = {}
    unseenNodes = graph
    infinity = 999999
    path = []

    for node in unseenNodes:
        shortest_distance[node] = infinity
    shortest_distance[start] = 0

    while unseenNodes:
        minNode = None
        for node in unseenNodes:
            if minNode is None:
                minNode = node
            elif shortest_distance[node] < shortest_distance[minNode]:
                minNode = node

        for childNode, weight in graph[minNode].items():
            if weight + shortest_distance[minNode] < shortest_distance[childNode]:
                shortest_distance[childNode] = weight + shortest_distance[minNode]
                predecessor[childNode] = minNode

        unseenNodes.pop(minNode)

    # get the path
    currentNode = goal
    while currentNode != start:
        try:
            path.insert(0,currentNode)
            currentNode = predecessor[currentNode]
        except KeyError:
            print("Path not reachable")
            break

    if shortest_distance[goal] != infinity:
        print('Shortest distance is: ' + str(shortest_distance[goal]))
        print('And the path is: ' + str(path))

теперь мне нужно найти способ вернуть пути в этом формате json, чтобы я мог запустить алгоритм Дейкстры на нем, например: 

testGraph = {'a':{'b':10,'c':3},'b':{'c':1,'d':2},'c':{'b':4,'d':8,'e':2},'d':{'e':7},'e':{'d':9}}
#the relation property that means the distance from node: a to b is 10, a to c is 3, b to c is 1 and so on...

dijkstra(testGraph, 'a', 'd')

#the output is: Shortest distance is: 9
#               And the path is: ['c', 'b', 'd']

Но я не уверен, как вернуть правильный путь и какиеформат подойдет лучше всего .. это то, что у меня есть, и я не могу отправить это в мой алгоритм: 

testGraph = graph.run(   "MATCH (c:JOB)-[d:DEPENDS_ON*]->(f:JOB) "
                    "WHERE c.order_id = '4p0ta' "
                    "RETURN * "
                    "LIMIT 50").to_table()#data() #to_subgraph #to_data_frame()

1 Ответ

0 голосов
/ 30 апреля 2019

Этот запрос Cypher должен возвращать путь (заканчивающийся на листовом узле) с наибольшей суммой: 

MATCH p=(c:JOB)-[:DEPENDS_ON*]->(f:JOB)
WHERE c.order_id = '4p0ta' AND NOT (f)-[:DEPENDS_ON]->()
RETURN p, REDUCE(s = 0, d IN RELATIONSHIPS(p) | s + d.elapsed_min) AS total
ORDER BY total DESC
LIMIT 1

Обратите внимание, что отношения переменной длины могут быть очень дорогими (т. Е. Занимать очень много времени или даже исчерпывать память), если ваши пути длинные и / или ваши узлы имеют много связей. Вам может потребоваться установить верхнюю границу длины, чтобы можно было использовать этот запрос.

...