-- (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]