    -- (c) 2000-2005 by Martin Erwig [see file COPYRIGHT]
    -- | Graph Voronoi Diagram
    --
    --   These functions can be used to create a /shortest path forest/
    --   where the roots are specified.
    module Data.Graph.Inductive.Query.GVD (
        Voronoi,LRTree,
        gvdIn,gvdOut,
        voronoiSet,nearestNode,nearestDist,nearestPath,
    --    vd,nn,ns,
    --    vdO,nnO,nsO
    ) where

    import Data.List  (nub)
    import Data.Maybe (listToMaybe)

    import qualified Data.Graph.Inductive.Internal.Heap as H

    import Data.Graph.Inductive.Basic
    import Data.Graph.Inductive.Graph
    import Data.Graph.Inductive.Internal.RootPath
    import Data.Graph.Inductive.Query.SP          (dijkstra)

    -- | Representation of a shortest path forest.
    type Voronoi a = LRTree a

    -- | Produce a shortest path forest (the roots of which are those
    --   nodes specified) from nodes in the graph /to/ one of the root
    --   nodes (if possible).
    gvdIn :: (DynGraph gr, Real b) => [Node] -> gr a b -> Voronoi b
    gvdIn vs g = gvdOut vs (grev g)

    -- | Produce a shortest path forest (the roots of which are those
    --   nodes specified) from nodes in the graph /from/ one of the root
    --   nodes (if possible).
    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)))

    -- | Return the nodes reachable to/from (depending on how the
    --   'Voronoi' was constructed) from the specified root node (if the
    --   specified node is not one of the root nodes of the shortest path
    --   forest, an empty list will be returned).
    voronoiSet :: Node -> Voronoi b -> [Node]
    voronoiSet v = nub . concat . filter (\p->last p==v) . map (map fst . unLPath)

    -- | Try to construct a path to/from a specified node to one of the
    --   root nodes of the shortest path forest.
    maybePath :: Node -> Voronoi b -> Maybe (LPath b)
    maybePath v = listToMaybe . filter ((v==) . fst . head . unLPath)

    -- | Try to determine the nearest root node to the one specified in the
    --   shortest path forest.
    nearestNode :: Node -> Voronoi b -> Maybe Node
    nearestNode v = fmap (fst . last . unLPath) . maybePath v

    -- | The distance to the 'nearestNode' (if there is one) in the
    --   shortest path forest.
    nearestDist :: Node -> Voronoi b -> Maybe b
    nearestDist v = fmap (snd . head . unLPath) . maybePath v

    -- | Try to construct a path to/from a specified node to one of the
    --   root nodes of the shortest path forest.
    nearestPath :: Node -> Voronoi b -> Maybe Path
    nearestPath v = fmap (map fst . unLPath) . 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]