fgl-5.5.4.0: Martin Erwig's Functional Graph Library

Safe HaskellSafe
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.

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

sp Source #

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.

spLength Source #

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.

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.

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

(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 -> () #