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