6 module Types.Data.Graph.Dijkstra
14 import qualified Types.Data.Heap as H
15 import qualified Types.Data.List as L
16 import qualified Types.Data.List.Ops as L
17 import qualified Types.Data.Map as M
19 import Types.Data.Bool
20 import Types.Data.Graph
21 import Types.Data.Graph.RootPath
22 import Types.Data.Maybe
26 type family Expand distance lPath context
27 type instance Expand d (LPath p) (Context ps n l ss)
28 = L.Map (Expand' d p) (M.Assocs ss)
30 data Expand' distance path
31 type instance L.App (Expand' d p) (L.Cons n d')
33 (LPath (L.Cons (LNode n (d :+: d')) p))
37 = If (H.IsEmpty h :||: IsEmpty g)
39 (Dijkstra' h g (H.SplitMin h))
41 type family Dijkstra' heap graph min
42 type instance Dijkstra' h g (L.Cons d (L.Cons (LPath (L.Cons (LNode n d') ps)) h'))
43 = Dijkstra'' n d' (LPath (L.Cons (LNode n d) ps)) h' (Match n g)
45 type family Dijkstra'' node distance lPath heap' decomp
46 type instance Dijkstra'' n d p h' (Decomp Nothing g') = Dijkstra h' g'
47 type instance Dijkstra'' n d p h' (Decomp (Just c) g')
48 = L.Cons p (Dijkstra (H.MergeAll (L.Cons h' (Expand d p c))) g')
51 type SpTree node graph
52 = Dijkstra (H.Unit D0 (LPath (L.Cons (LNode node D0) L.Null))) graph
55 type SpLength node1 node2 graph
56 = GetDistance node2 (SpTree node1 graph)
59 type Sp node1 node2 graph
60 = GetLPathNodes node2 (SpTree node1 graph)