1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
-- (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]
|
