fgl-5.5.2.3: Martin Erwig's Functional Graph Library

Safe HaskellSafe-Inferred
LanguageHaskell98

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.

sp Source

Arguments

:: (Graph gr, Real b) 
=> Node

Start

-> Node

Destination

-> gr a b 
-> Path 

Shortest path between two nodes.

spLength Source

Arguments

:: (Graph gr, Real b) 
=> Node

Start

-> Node

Destination

-> gr a b 
-> b 

Length of the shortest path between two nodes.

dijkstra Source

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.

type LRTree a = [LPath a] Source

data Heap a b Source

Instances

(Eq a, Eq b) => Eq (Heap a b) 
(Read a, Read b) => Read (Heap a b) 
(Show a, Show b) => Show (Heap a b) 
(NFData a, NFData b) => NFData (Heap a b)