fgl-5.7.0.1: Martin Erwig's Functional Graph Library

Data.Graph.Inductive.Query.SP

Description

Shortest path algorithms

Synopsis

# Documentation

spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b Source #

Tree of shortest paths from a certain node to the rest of the (reachable) nodes.

Corresponds to dijkstra applied to a heap in which the only known node is the starting node, with a path of length 0 leading to it.

The edge labels of type b are the edge weights; negative edge weights are not supported.

Arguments

 :: (Graph gr, Real b) => Node Start -> Node Destination -> gr a b -> Maybe Path

Shortest path between two nodes, if any.

Returns Nothing if the destination is not reachable from the start node, and Just path otherwise.

The edge labels of type b are the edge weights; negative edge weights are not supported.

Arguments

 :: (Graph gr, Real b) => Node Start -> Node Destination -> gr a b -> Maybe b

Length of the shortest path between two nodes, if any.

Returns Nothing if there is no path, and Just length otherwise.

The edge labels of type b are the edge weights; negative edge weights are not supported.

Arguments

 :: (Graph gr, Real b) => Heap b (LPath b) Initial heap of known paths and their lengths. -> gr a b -> LRTree b

Dijkstra's shortest path algorithm.

The edge labels of type b are the edge weights; negative edge weights are not supported.

type LRTree a = [LPath a] Source #

data Heap a b Source #

Instances