Data.Graph.Inductive.Query.SP

Shortest path algorithms

Documentation

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

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

Arguments

:: (Graph gr, Real b)

=> Node

Start

-> Node

Destination

-> gr a b

-> Path

Shortest path between two nodes.

spLength

Arguments

:: (Graph gr, Real b)

=> Node

Start

-> Node

Destination

-> gr a b

-> b

Length of the shortest path between two nodes.

dijkstra

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]

data Heap a b

Instances

(Eq b, Eq a) => Eq (Heap a b)

Methods

(==) :: Heap a b -> Heap a b -> Bool

(/=) :: Heap a b -> Heap a b -> Bool

(Read b, Read a) => Read (Heap a b)

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)

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)

Methods

rnf :: Heap a b -> ()