Data.Graph.Inductive.Query.GVD

Graph Voronoi Diagram

These functions can be used to create a shortest path forest where the roots are specified.

Documentation

type Voronoi a = LRTree a

Representation of a shortest path forest.

type LRTree a = [LPath a]

gvdIn :: (DynGraph gr, Real b) => [Node] -> gr a b -> Voronoi b

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).

gvdOut :: (Graph gr, Real b) => [Node] -> gr a b -> Voronoi b

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).

voronoiSet :: Node -> Voronoi b -> [Node]

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).

nearestNode :: Node -> Voronoi b -> Maybe Node

Try to determine the nearest root node to the one specified in the shortest path forest.

nearestDist :: Node -> Voronoi b -> Maybe b

The distance to the nearestNode (if there is one) in the shortest path forest.

nearestPath :: Node -> Voronoi b -> Maybe Path

Try to construct a path to/from a specified node to one of the root nodes of the shortest path forest.