fgl-5.7.0.1: Martin Erwig's Functional Graph Library

Safe Haskell | Safe
Language | Haskell98

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

- type Voronoi a = LRTree a
- type LRTree a = [LPath a]
- gvdIn :: (DynGraph gr, Real b) => [Node] -> gr a b -> Voronoi b
- gvdOut :: (Graph gr, Real b) => [Node] -> gr a b -> Voronoi b
- voronoiSet :: Node -> Voronoi b -> [Node]
- nearestNode :: Node -> Voronoi b -> Maybe Node
- nearestDist :: Node -> Voronoi b -> Maybe b
- nearestPath :: Node -> Voronoi b -> Maybe Path

# 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 :: 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.