content: module Data.Graph.Inductive.Query.SP
         (spTree, spLength, sp, dijkstra) where
  { import qualified Data.Graph.Inductive.Internal.Heap as H;
    import Data.Graph.Inductive.Graph;
    import Data.Graph.Inductive.Internal.RootPath;
     
    expand ::
           (Real b) => b -> LPath b -> Context a b -> [H.Heap b (LPath b)];
    expand d (LP p) (_, _, _, s)
      = map (\ (l, v) -> H.unit (l + d) (LP ((v, l + d) : p))) s;
     
    dijkstra ::
             (Graph gr, Real b) => H.Heap b (LPath b) -> gr a b -> LRTree b;
    dijkstra h g | H.isEmpty h || isEmpty g = [];
    dijkstra h g
      = case match v g of
            { (Just c, g') -> p : dijkstra (H.mergeAll (h' : expand d p c)) g';
              (Nothing, g') -> dijkstra h' g'}
      where { (_, p@(LP ((v, d) : _)), h') = H.splitMin h};
     
    spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b;
    spTree v = dijkstra (H.unit 0 (LP [(v, 0)]));
     
    spLength :: (Graph gr, Real b) => Node -> Node -> gr a b -> b;
    spLength s t = getDistance t . spTree s;
     
    sp :: (Graph gr, Real b) => Node -> Node -> gr a b -> Path;
    sp s t = getLPathNodes t . spTree s}
  