    -- (c) 2000-2005 by Martin Erwig [see file COPYRIGHT]
    -- | Graph Voronoi Diagram

    module Data.Graph.Inductive.Query.GVD (
        Voronoi,
        gvdIn,gvdOut,
        voronoiSet,nearestNode,nearestDist,nearestPath,
    --    vd,nn,ns,
    --    vdO,nnO,nsO
    ) 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

    -- vd = gvdIn [4,5] vor
    -- vdO = gvdOut [4,5] vor
    -- nn = map (flip nearestNode vd) [1..8]
    -- nnO = map (flip nearestNode vdO) [1..8]
    -- ns = map (flip voronoiSet vd) [1..8]
    -- nsO = map (flip voronoiSet vdO) [1..8]