Znajdź najkrótszą ścieżkę i do domu

Magiczna komenda jaką daje nam silnik i pozamiatane. Nie no co wy, zwróci nam najkrótszą drogę ale po ilości relacji.

MATCH (s:Point),(e:Point),
p = shortestpath((s)-[*]-(e))
WHERE s.name = 'JASŁO' AND e.name = 'RZESZÓW'
return p

No ale nam chodzi o odległość, a posiadamy strukturę punktów osadzonych na kawałkach drogi, a poruszamy się między punktami, droga to tylko medium. Więc w głowie pojawia się pomysł bezpośredniego połączenia punktów.

MATCH (s:Point)-[r:Stay]-(t:Segment)
where  r.lineNo = t.lineNo
with distinct s,r.km as km, t.lineNo as  lineNo
order by km 
with collect({s:s,km:km,lineNo:lineNo}) as one , collect({s:s,km:km,lineNo:lineNo}) as two
UNWIND one as ss 
with  ss  , filter(next IN two WHERE ss.lineNo = next.lineNo and next.km >= ss.km and NOT next.s.name = ss.s.name)[0] as nss
with  ss.s as fi,  nss.km-ss.km as distance , ss.lineNo as lineNo, nss.s as se
where se is not null
merge (fi)-[:Connect{distance: distance ,lineNo: lineNo}]-(se)

Przy tym skrypcie się już trochę rozpoznałem Cypher'a, ale jeśli ktoś ma inny pomysł na połączenie tego to proszę bardzo :).

Mając na połączone punkty no to tylko sumować odległości dzieki reduce i dawaj najkrótszą. 

START  startNode=node:node_auto_index(name="Start"),
             endNode=node:node_auto_index(name="Finish")
MATCH  p=(startNode)-[:NAVIGATE_TO*]->(endNode)
RETURN p AS shortestPath,
                reduce(distance=0, r in relationships(p) :  distance+r.distance) AS totalDistance
                ORDER BY totalDistance ASC
                LIMIT 1;

I lepiej tego nie puszczać jeśli się ma więcej niż 100 nodów. XD Gdy rozpoczeła się walka z brakiem RAM i mając już 5 min zastanawiania się dlaczego to tak długo, zrozumiałem że gość tak naprawdę robi iloczyn kartezjański i wszystko próbuje obliczyć... Porażka, Jak takie zajefajne grafy i na 25k Pointów i 60k odcinów się wysypuje. 

No ale 90% problemu to brak zrozumienia jak to działa. I oczywiście każdy miał na studiach algorytmy i było o takim na D, co tak szybko szuka. 

Daleko szukać i głowić się nie trzeba, jest już zaimplementowany jako plugin do neo, neo4j-apoc-procedures. 

MATCH (s:Point{name:'JASŁO'}),(e:Point{name:'RZESZÓW'})
CALL apoc.algo.dijkstra(s, e, 'Connect', 'distance') YIELD path, weight
RETURN path, weight

No i to już jest faktyczna prawdziwa najkrótsza ścieżka.

Teraz temat co jeśli nie możemy jechać przez np Czudec.  Na szybko mam tylko taki pomysł żeby skopiować relacje które są dostępne czyli bez Czudca, a następnie wyszukać połączenie, i oczywiście pamiętać żeby to chwilowe powiązanie usunąć.

MATCH (s:Point)-[c:Connect]-(t:Point)
where s.name <> 'Czudec' and t.name <> 'Czudec' 
merge (s)-[:Connect_tempWOCzud{distance: c.distance ,lineNo: c.lineNo}]-(t)

Jak sprawdziłem skopiowanie 2k relacji bez 2 bo akurat tyle miał Czudec to 450ms, więc jeszcze nie tak źle. Gorsza jest trasa bez przejazdu przez Czudec gdzie okazuje się że muszę nadgonić 100km aby go ominąć. Taką mamy mapę :)

MATCH (s:Point{name:'JASŁO'}),(e:Point{name:'RZESZÓW'})
CALL apoc.algo.dijkstra(s, e, 'Connect_tempWOCzud', 'distance') YIELD path, weight
RETURN path, weight

Próbując wytyczyć alternatywne ścieżki okazało się że dane są nie dokładne a najlepszy błąd to stworzenie punktu Granica Państwa gdzie z odległością 0 można się teleportować z Zgorzelca do Cieszyna :) 

Tyle eksperymentów z czystym Neo, następny krok to kawałek, który będzie miał za zadanie obsługę obsługę całej transakcji bez wyłączonych odcinków itd.

I DO DOMU :D