paths - Neo4j Cypher: comprueba los atributos de los nodos consecutivos en la ruta

relationship in neo4j

Question

Tengo un gráfico que representa varias paradas de autobús / tren en diferentes ciudades. Supongamos que quiero ir desde la ciudad A (con paradas a1, a2, a3 ...) a la ciudad Z (con paradas z1, z2 ...)

Hay varias rutas (relaciones) entre los nodos y quiero obtener todas las rutas entre el nodo inicial y el nodo final. Mi vector de costos sería complejo (tiempo de viaje y tiempo de espera y precio yy ...) en realidad, por lo tanto no puedo usar shortestpaths, etc. Pude escribir una consulta (bastante compleja) que hace lo que quiero: en general, está buscando cada coincidencia con inicio A y final Z que está disponible.

Intento evitar el bucle mediante resultados de filtrado con características especiales, por ejemplo

MATCH (from{name:''a1''}), (to{name:''z1''}),
path = (from)-[:CONNECTED_TO*0..8]->(to)
WHERE ALL(b IN NODES(path) WHERE SINGLE(c IN NODES(path) WHERE b = c))

Ahora quiero evitar la posibilidad de visitar una ciudad más de una vez, por ejemplo, en lugar de a1 -> a2 -> d2 -> d4 -> a3 -> a4 -> z1 Quiero obtener a1-- > a4 -> z1.

Por lo tanto, tengo que verificar todos los nodos en la ruta. Si el valor de n.city es el mismo para nodos consecutivos, todo está bien. Pero si obtuve un camino con nodos de la misma ciudad que no son consecutivos, p. Ej. CityA -> cityB -> cityA, quiero desechar esa ruta.

¿Cómo puedo hacer eso? ¿Es posible algo?

Lo sé, ese no es realmente un enfoque hermoso, pero he invertido bastante tiempo en encontrar uno mejor sin tirar toda la estructura de datos, pero no pude encontrar uno. Es solo un prototipo y Neo4j no es mi enfoque. Quiero probar algunas herramientas y productos para construir algunos conocimientos. Voy a seguir adelante con un mejor enfoque la próxima vez.

Answer 1

Interesante pregunta. Lo importante a observar aquí es que un camino que nunca vuelve a visitar una ciudad (después de dejarlo) debe tener menos transiciones entre ciudades que el número de ciudades distintas. Por ejemplo:

• AABBC (una "buena" ruta) tiene 3 ciudades distintas y 2 transiciones
• ABBAC (un "mal" camino) también tiene 3 ciudades distintas pero 3 transiciones

Con esta observación en mente, la siguiente consulta debería funcionar (incluso si los nodos de inicio y fin son los mismos):

MATCH path = ({name:''a1''})-[:CONNECTED_TO*0..8]->({name:''z1''})
WITH path, NODES(path) as ns
WITH path, ns,
REDUCE(s = {cnt: 0, last: ns[0].city}, x IN ns[1..] |
CASE WHEN x.city = s.last THEN s ELSE {cnt: s.cnt+1, last: x.city} END).cnt AS nTransitions
UNWIND ns AS node
WITH path, nTransitions, COUNT(DISTINCT node.city) AS nCities
WHERE nTransitions < nCities
RETURN path;

La función REDUCE se utiliza para calcular el número de transiciones en una ruta.