fgl-5.5.2.3: Martin Erwig's Functional Graph Library

Safe HaskellSafe-Inferred
LanguageHaskell98

Data.Graph.Inductive.Query.GVD

Description

Graph Voronoi Diagram

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

Synopsis

Documentation

type Voronoi a = LRTree a Source

Representation of a shortest path forest.

type LRTree a = [LPath a] Source

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

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 Source

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

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 :: Real b => Node -> Voronoi b -> Maybe Node Source

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

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

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

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

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