Hackage :: [Package]

dijkstra-simple: A simpler Dijkstra shortest paths implementation

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

Provides a simplistic Dijkstra implementation with some useful variations and generalizations.

[Skip to Readme]

Properties

Versions 0.1.0, 0.1.0
Change log changelog.md
Dependencies base (>=4.7 && <5), containers (>=0.6.2.1 && <0.7), fingertree (>=0.1.4.0 && <0.1.5) [details]
License BSD-3-Clause
Copyright Gautier DI FOLCO
Author Gautier DI FOLCO
Maintainer gautier.difolco@gmail.com
Category graph, dijkstra
Home page https://github.com/blackheaven/dijkstra-simple#readme
Bug tracker https://github.com/blackheaven/dijkstra-simple/issues
Source repo head: git clone https://github.com/blackheaven/dijkstra-simple
Uploaded by gdifolco at 2020-06-24T17:18:56Z

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Readme for dijkstra-simple-0.1.0

[back to package description]

dijkstra-simple

A simpler Dijkstra shortest paths implementation

Basic usage

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' and associated shortest path:

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)
                   ]