content: module Data.Graph.Inductive.Query.GVD
         (Voronoi, gvdIn, gvdOut, voronoiSet, nearestNode, nearestDist,
          nearestPath)
         where
  { import Data.Maybe (listToMaybe);
    import Data.List (nub);
    import qualified Data.Graph.Inductive.Internal.Heap as H;
    import Data.Graph.Inductive.Graph;
    import Data.Graph.Inductive.Query.SP (dijkstra);
    import Data.Graph.Inductive.Internal.RootPath;
    import Data.Graph.Inductive.Basic;
     
    type Voronoi a = LRTree a;
     
    gvdIn :: (DynGraph gr, Real b) => [Node] -> gr a b -> Voronoi b;
    gvdIn vs g = gvdOut vs (grev g);
     
    gvdOut :: (Graph gr, Real b) => [Node] -> gr a b -> Voronoi b;
    gvdOut vs
      = dijkstra
          (H.build (zip (repeat 0) (map (\ v -> LP [(v, 0)]) vs)));
     
    voronoiSet :: (Real b) => Node -> Voronoi b -> [Node];
    voronoiSet v
      = nub . concat . filter (\ p -> last p == v) .
          map (\ (LP p) -> map fst p);
     
    maybePath :: (Real b) => Node -> Voronoi b -> Maybe (LPath b);
    maybePath v = listToMaybe . filter (\ (LP ((w, _) : _)) -> w == v);
     
    nearestNode :: (Real b) => Node -> Voronoi b -> Maybe Node;
    nearestNode v = fmap (\ (LP ((w, _) : _)) -> w) . maybePath v;
     
    nearestDist :: (Real b) => Node -> Voronoi b -> Maybe b;
    nearestDist v = fmap (\ (LP ((_, l) : _)) -> l) . maybePath v;
     
    nearestPath :: (Real b) => Node -> Voronoi b -> Maybe Path;
    nearestPath v = fmap (\ (LP p) -> map fst p) . maybePath v}
  