7 module Types.Data.Graph.Dijkstra
15 import qualified Types.Data.Heap as H
16 import qualified Types.Data.List as L
17 import qualified Types.Data.List.Ops as L
18 import qualified Types.Data.Map as M
20 import Types.Data.Bool
21 import Types.Data.Graph
22 import Types.Data.Graph.RootPath
23 import Types.Data.Maybe
27 type family Expand distance lPath context
28 type instance Expand d (LPath p) (Context ps n l ss)
29 = L.Map (Expand' d p) (M.Assocs ss)
31 data Expand' distance path
32 type instance L.App (Expand' d p) (L.Cons n d')
34 (LPath (L.Cons (LNode n (d :+: d')) p))
38 = If (H.IsEmpty h :||: IsEmpty g)
40 (Dijkstra' h g (H.SplitMin h))
42 type family Dijkstra' heap graph min
43 type instance Dijkstra' h g (L.Cons d (L.Cons (LPath (L.Cons (LNode n d') ps)) h'))
44 = Dijkstra'' n d' (LPath (L.Cons (LNode n d) ps)) h' (Match n g)
46 type family Dijkstra'' node distance lPath heap' decomp
47 type instance Dijkstra'' n d p h' (Decomp Nothing g') = Dijkstra h' g'
48 type instance Dijkstra'' n d p h' (Decomp (Just c) g')
49 = L.Cons p (Dijkstra (H.MergeAll (L.Cons h' (Expand d p c))) g')
52 type SpTree node graph
53 = Dijkstra (H.Unit D0 (LPath (L.Cons (LNode node D0) L.Null))) graph
56 type SpLength node1 node2 graph
57 = GetDistance node2 (SpTree node1 graph)
60 type Sp node1 node2 graph
61 = GetLPathNodes node2 (SpTree node1 graph)
65 test :: SpTree D2 (InsNode (LNode D1 False)
66 (InsNode (LNode D0 True) Empty))