Trovare il percorso più breve con FGL

Question

Uso la libreria di grafici funzionale (FGL) di Martin Erwig per rappresentare il seguente grafico ponderato diretto semplice.

genLNodes :: [LNode String] 
genLNodes = zip [1..5] ["A","B","C","D","E"] 

genLEdges :: [LEdge Int] 
genLEdges = [(1,2,4),(1,3,1),(2,4,2),(3,4,2),(2,5,1),(4,5,1), 
      (2,1,4),(3,1,1),(4,2,2),(4,3,2),(5,2,1),(5,4,1)] 

mygraph :: Gr String Int 
mygraph = mkGraph genLNodes genLEdges 

Ora voglio trovare il percorso più breve da un nodo all'altro per esempio A a E usando l'algoritmo di dijkstra. Sembra che ci sia una funzione di farlo in Data.Graph.Inductive.Query.SP:

dijkstra :: (Graph gr, Real b) => Heap b (LPath b) -> gr a b -> LRTree b 

ma non sono in grado di capire come usarlo dall'interfaccia fornita. Qualsiasi aiuto sarebbe molto apprezzato. Mi piacerebbe anche sentire altri suggerimenti, se sto creando il grafico ponderato diretto nel modo giusto, o se c'è qualche altro (migliore) pacchetto per farlo?

Answer 1

per ottenere il percorso più breve tra due nodi, il modulo fornisce una funzione speciale, sp (abbreviazione di "percorso più breve", presumibilmente), quindi il modo più semplice per ottenere il percorso più breve è

sp 1 5 mygraph 

sp utilizza dijkstra:

spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b 
spTree v = dijkstra (H.unit 0 (LP [(v,0)])) 

sp :: (Graph gr, Real b) => Node -> Node -> gr a b -> Path 
sp s t = getLPathNodes t . spTree s 

e da che si può vedere come si potrebbe produrre la spanning tree e ottenere il percorso più breve da quella da soli, ma se non hai una buona ragione per non utilizzare la funzione fornita, dovresti attenervisi.