relaciones - Neo4j: búsqueda de la ruta más corta entre dos nodos según la propiedad de la relación

neo4j downloads

Question

Estoy tratando de averiguar si hay alguna forma de obtener la distancia más corta entre dos nodos basada en una suma de relación, dado este ejemplo: neo4j image example

Código para la imagen de arriba:

CREATE (some_point_1:Point {title:''Some Point 1''})
CREATE (some_point_2:Point {title:''Some Point 2''})
CREATE (some_point_3:Point {title:''Some Point 3''})
CREATE (some_point_4:Point {title:''Some Point 4''})
CREATE (some_point_5:Point {title:''Some Point 5''})
CREATE (some_point_6:Point {title:''Some Point 6''})

CREATE (some_point_1)-[:distance {value:100}]->(some_point_2)
CREATE (some_point_2)-[:distance {value:150}]->(some_point_4)
CREATE (some_point_1)-[:distance {value:200}]->(some_point_3)
CREATE (some_point_3)-[:distance {value:300}]->(some_point_4)
CREATE (some_point_2)-[:distance {value:500}]->(some_point_5)
CREATE (some_point_4)-[:distance {value:300}]->(some_point_5)
CREATE (some_point_5)-[:distance {value:300}]->(some_point_6)
CREATE (some_point_6)-[:distance {value:300}]->(some_point_1)

En este ejemplo, la ruta más corta debería ser: some_point_1> some_point_2> some_point_4> some_point_5 (100 + 150 + 300 = 550)

¿Es posible algo así con Cypher?

Answer 1

Cypher tiene una función de PATH () más corta, que combinada con predicados y un poco de prueba y error probablemente hará lo que usted desea.

Sin embargo, para ahorrar tiempo, es más fácil usar los procedimientos de NEOC de neo4j , que incluye un algoritmo de ruta más corta dijkstra ponderado que debería ser el ajuste perfecto para lo que desea.

No lo he usado todavía, pero creo que la sintaxis (después de la coincidencia en startNode y endNode, usando el nombre de su relación y la propiedad utilizada para el peso) es algo así como

CALL apoc.algo.dijkstra(startNode, endNode, ''distance'', ''value'') 
YIELD path, weight

En cuanto a tomar en cuenta la dirección, la documentación wiki no lo dice abiertamente, pero parece que <o> se agrega al final apropiado de la etiqueta de relación, creo, así que ''distancia>'' es probablemente el parámetro más correcto, si quieres que respete la dirección

Answer 2

La función de shortestPath en Cypher no tiene en cuenta la acumulación de propiedades de relación, así que esto:

MATCH (start:Point {title: ''Some Point 1''}), (end:Point {title: ''Some Point 5''})
MATCH p=shortestPath((start)-[:distance*]->(end))
RETURN p

encontraría el camino más corto de start a end según el número de relaciones en la ruta.

Podría reducir las sumas de las distancias:

MATCH (start:Point {title: ''Some Point 1''}), (end:Point {title: ''Some Point 5''})
MATCH p=(start)-[:distance*]->(end)
WITH p,reduce(s = 0, r IN rels(p) | s + r.value) AS dist
RETURN p, dist ORDER BY dist DESC

Pero el problema aquí es que necesita calcular la distancia total para todas las rutas de start a end . Para ser más eficiente, desea utilizar un algoritmo de búsqueda de gráficos como el algoritmo de Dijkstra o A *, ambos implementados en la API Java de Neo4j .

En Neo4j 3.0 estos algoritmos están expuestos en Cypher a través de la biblioteca de procedimientos APOC . Una vez que instale APOC puede llamar al procedimiento desde Cypher:

MATCH (start:Point {title: ''Some Point 1''}), (end:Point {title: ''Some Point 5''})
CALL apoc.algo.dijkstra(start, end, ''distance'', ''value'') YIELD path, weight
RETURN path, weight