| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Graph.DijkstraSimple
Contents
Synopsis
- lightestPaths :: forall v e a. (Ord v, Ord a) => Graph v e -> v -> Weighter v e a -> Paths v e a
- findPath :: forall v e a. (Ord v, Ord a) => Graph v e -> v -> Weighter v e a -> v -> Maybe (Path v e a)
- dijkstraSteps :: forall v e a. (Ord v, Ord a) => Graph v e -> v -> Weighter v e a -> NonEmpty (Paths v e a)
- data EdgeTo v e = EdgeTo {
- edgeTo :: v
- edgeToWeight :: e
- newtype Graph v e = Graph {
- graphAsMap :: Map v [EdgeTo v e]
- data Weighter v e a = Weighter {
- initialWeight :: a
- weight :: EdgeTo v e -> Path v e a -> a
- data Path v e a = Path {
- pathVertices :: NonEmpty v
- pathWeight :: a
- newtype Paths v e a = Paths {
- pathsAsMap :: Map v (Path v e a)
How to use this library
This section contains basic step-by-step usage of the library.
The first step is to build a direct graph:
exampleGraph :: Graph Char Int
exampleGraph = Graph $ M.fromList [
('A', [EdgeTo 'B' 3, EdgeTo 'C' 1])
, ('B', [EdgeTo 'A' 3, EdgeTo 'C' 7, EdgeTo 'D' 5, EdgeTo 'E' 1])
, ('C', [EdgeTo 'A' 1, EdgeTo 'B' 7, EdgeTo 'D' 2])
, ('D', [EdgeTo 'B' 5, EdgeTo 'C' 2, EdgeTo 'E' 5])
, ('E', [EdgeTo 'B' 1, EdgeTo 'D' 7])
]Then pick or create a weighter (see Graph.DijkstraSimple.Weighters)
and apply it all:
lightestPaths exampleGraph 'C' weighter
It will give all the reacheable vertices from C
Paths $ M.fromList [
('A', Path (fromList "AC") 1)
, ('B', Path (fromList "BAC") 3)
, ('C', Path (fromList "CAC") 1)
, ('D', Path (fromList "DC") 2)
, ('E', Path (fromList "EBAC") 3)
]lightestPaths :: forall v e a. (Ord v, Ord a) => Graph v e -> v -> Weighter v e a -> Paths v e a Source #
Explore all the reachable edges
findPath :: forall v e a. (Ord v, Ord a) => Graph v e -> v -> Weighter v e a -> v -> Maybe (Path v e a) Source #
Find the eventual path between two edges
dijkstraSteps :: forall v e a. (Ord v, Ord a) => Graph v e -> v -> Weighter v e a -> NonEmpty (Paths v e a) Source #
Details each step of the Dijkstra algorithm
Edge to an arbitrary vertex and the associated input weight
Constructors
| EdgeTo | |
Fields
| |
All vertices and outgoing edges
Constructors
| Graph | |
Fields
| |
Convert an input weight (edge-dependant) to an output weight (path-dependant) for the algorithm work.
Constructors
| Weighter | |
Fields
| |
The lightest found path with reverse ordered list of traversed vertices and output weight.
Constructors
| Path | |
Fields
| |