content: module Data.Graph.Inductive.Query.MST (msTreeAt, msTree, msPath)
         where
  { import Data.Graph.Inductive.Graph;
    import Data.Graph.Inductive.Internal.RootPath;
    import qualified Data.Graph.Inductive.Internal.Heap as H;
     
    newEdges ::
             (Ord b) => LPath b -> Context a b -> [H.Heap b (LPath b)];
    newEdges (LP p) (_, _, _, s)
      = map (\ (l, v) -> H.unit l (LP ((v, l) : p))) s;
     
    prim ::
         (Graph gr, Real b) => H.Heap b (LPath b) -> gr a b -> LRTree b;
    prim h g | H.isEmpty h || isEmpty g = [];
    prim h g
      = case match v g of
            { (Just c, g') -> p : prim (H.mergeAll (h' : newEdges p c)) g';
              (Nothing, g') -> prim h' g'}
      where { (_, p@(LP ((v, _) : _)), h') = H.splitMin h};
     
    msTreeAt :: (Graph gr, Real b) => Node -> gr a b -> LRTree b;
    msTreeAt v g = prim (H.unit 0 (LP [(v, 0)])) g;
     
    msTree :: (Graph gr, Real b) => gr a b -> LRTree b;
    msTree g = msTreeAt v g
      where { ((_, v, _, _), _) = matchAny g};
     
    msPath :: (Real b) => LRTree b -> Node -> Node -> Path;
    msPath t a b = joinPaths (getLPathNodes a t) (getLPathNodes b t);
     
    joinPaths :: Path -> Path -> Path;
    joinPaths p q = joinAt (head p) p q;
     
    joinAt :: Node -> Path -> Path -> Path;
    joinAt _ (v : vs) (w : ws) | v == w = joinAt v vs ws;
    joinAt x p q = reverse p ++ (x : q)}
  