Safe Haskell	Safe
Language	Haskell98

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

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

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.

Instances

(Eq b, Eq a) => Eq (Heap a b) Source #
Methods (==) :: Heap a b -> Heap a b -> Bool # (/=) :: Heap a b -> Heap a b -> Bool #
(Read b, Read a) => Read (Heap a b) Source #
Methods readsPrec :: Int -> ReadS (Heap a b) # readList :: ReadS [Heap a b] # readPrec :: ReadPrec (Heap a b) # readListPrec :: ReadPrec [Heap a b] #
(Show b, Show a) => Show (Heap a b) Source #
Methods showsPrec :: Int -> Heap a b -> ShowS # show :: Heap a b -> String # showList :: [Heap a b] -> ShowS #
(NFData a, NFData b) => NFData (Heap a b) Source #
Methods rnf :: Heap a b -> () #