Copyright | (c) Masahiro Sakai 2016-2017 |
---|---|
License | BSD-style |
Maintainer | masahiro.sakai@gmail.com |
Stability | provisional |
Portability | non-portable |
Safe Haskell | None |
Language | Haskell2010 |
This module provides functions for shotest path computation.
Reference:
- Friedrich Eisenbrand. “Linear and Discrete Optimization”. https://www.coursera.org/course/linearopt
Synopsis
- type Graph vertex cost label = HashMap vertex [OutEdge vertex cost label]
- type Edge vertex cost label = (vertex, vertex, cost, label)
- type OutEdge vertex cost label = (vertex, cost, label)
- type InEdge vertex cost label = (vertex, cost, label)
- data Fold vertex cost label r = Fold (vertex -> a) (Edge vertex cost label -> a) (a -> a -> a) (a -> r)
- monoid' :: Monoid m => (Edge vertex cost label -> m) -> Fold vertex cost label m
- monoid :: Monoid m => Fold vertex cost m m
- unit :: Fold vertex cost label ()
- pair :: Fold vertex cost label a -> Fold vertex cost label b -> Fold vertex cost label (a, b)
- path :: (Eq vertex, Num cost) => Fold vertex cost label (Path vertex cost label)
- firstOutEdge :: Fold vertex cost label (First (OutEdge vertex cost label))
- lastInEdge :: Fold vertex cost label (Last (InEdge vertex cost label))
- cost :: Num cost => Fold vertex cost label cost
- data Path vertex cost label
- pathFrom :: Path vertex cost label -> vertex
- pathTo :: Path vertex cost label -> vertex
- pathCost :: Num cost => Path vertex cost label -> cost
- pathEmpty :: vertex -> Path vertex cost label
- pathAppend :: (Eq vertex, Num cost) => Path vertex cost label -> Path vertex cost label -> Path vertex cost label
- pathEdges :: Path vertex cost label -> [Edge vertex cost label]
- pathEdgesBackward :: Path vertex cost label -> [Edge vertex cost label]
- pathEdgesSeq :: Path vertex cost label -> Seq (Edge vertex cost label)
- pathVertexes :: Path vertex cost label -> [vertex]
- pathVertexesBackward :: Path vertex cost label -> [vertex]
- pathVertexesSeq :: Path vertex cost label -> Seq vertex
- pathFold :: Fold vertex cost label a -> Path vertex cost label -> a
- pathMin :: (Num cost, Ord cost) => Path vertex cost label -> Path vertex cost label -> Path vertex cost label
- bellmanFord :: (Eq vertex, Hashable vertex, Real cost) => Fold vertex cost label a -> Graph vertex cost label -> [vertex] -> HashMap vertex (cost, a)
- dijkstra :: forall vertex cost label a. (Eq vertex, Hashable vertex, Real cost) => Fold vertex cost label a -> Graph vertex cost label -> [vertex] -> HashMap vertex (cost, a)
- floydWarshall :: forall vertex cost label a. (Eq vertex, Hashable vertex, Real cost) => Fold vertex cost label a -> Graph vertex cost label -> HashMap vertex (HashMap vertex (cost, a))
- bellmanFordDetectNegativeCycle :: forall vertex cost label a. (Eq vertex, Hashable vertex, Real cost) => Fold vertex cost label a -> Graph vertex cost label -> HashMap vertex (cost, Last (InEdge vertex cost label)) -> Maybe a
Graph data types
type Graph vertex cost label = HashMap vertex [OutEdge vertex cost label] Source #
Graph represented as a map from vertexes to their outgoing edges
type OutEdge vertex cost label = (vertex, cost, label) Source #
Outgoing edge data type (source vertex is implicit)
type InEdge vertex cost label = (vertex, cost, label) Source #
Incoming edge data type (target vertex is implicit)
Fold data type
data Fold vertex cost label r Source #
Operations for folding edge information along with a path into a r
value.
Fold vertex cost label r
consists of three operations
vertex -> a
corresponds to an empty path,Edge vertex cost label -> a
corresponds to a single edge,a -> a -> a
corresponds to path concatenation,
and a -> r
to finish the computation.
Instances
Functor (Fold vertex cost label) Source # | |
Applicative (Fold vertex cost label) Source # | |
Defined in ToySolver.Graph.ShortestPath pure :: a -> Fold vertex cost label a # (<*>) :: Fold vertex cost label (a -> b) -> Fold vertex cost label a -> Fold vertex cost label b # liftA2 :: (a -> b -> c) -> Fold vertex cost label a -> Fold vertex cost label b -> Fold vertex cost label c # (*>) :: Fold vertex cost label a -> Fold vertex cost label b -> Fold vertex cost label b # (<*) :: Fold vertex cost label a -> Fold vertex cost label b -> Fold vertex cost label a # |
monoid' :: Monoid m => (Edge vertex cost label -> m) -> Fold vertex cost label m Source #
Project Edge
into a monoid value and fold using monoidal operation.
monoid :: Monoid m => Fold vertex cost m m Source #
Similar to monoid'
but a label is directly used as a monoid value.
pair :: Fold vertex cost label a -> Fold vertex cost label b -> Fold vertex cost label (a, b) Source #
Pairs two Fold
into one that produce a tuple.
path :: (Eq vertex, Num cost) => Fold vertex cost label (Path vertex cost label) Source #
Construct a Path
value.
firstOutEdge :: Fold vertex cost label (First (OutEdge vertex cost label)) Source #
Get the first OutEdge
of a path.
lastInEdge :: Fold vertex cost label (Last (InEdge vertex cost label)) Source #
Get the last InEdge
of a path.
This is useful for constructing a parent map of a spanning tree.
Path data types
data Path vertex cost label Source #
path data type.
Empty vertex | empty path |
Singleton (Edge vertex cost label) | path with single edge |
Append (Path vertex cost label) (Path vertex cost label) !cost | concatenation of two paths |
pathAppend :: (Eq vertex, Num cost) => Path vertex cost label -> Path vertex cost label -> Path vertex cost label Source #
Concatenation of two paths
pathEdgesBackward :: Path vertex cost label -> [Edge vertex cost label] Source #
Edges of a path, but in the reverse order
pathEdgesSeq :: Path vertex cost label -> Seq (Edge vertex cost label) Source #
Edges of a path, but as Seq
pathVertexes :: Path vertex cost label -> [vertex] Source #
Vertexes of a path
pathVertexesBackward :: Path vertex cost label -> [vertex] Source #
Vertexes of a path, but in the reverse order
pathFold :: Fold vertex cost label a -> Path vertex cost label -> a Source #
Fold a path using a given Fold
operation.
pathMin :: (Num cost, Ord cost) => Path vertex cost label -> Path vertex cost label -> Path vertex cost label Source #
Shortest-path algorithms
:: (Eq vertex, Hashable vertex, Real cost) | |
=> Fold vertex cost label a | Operation used to fold shotest paths |
-> Graph vertex cost label | |
-> [vertex] | List of source vertexes |
-> HashMap vertex (cost, a) |
Bellman-Ford algorithm for finding shortest paths from source vertexes to all of the other vertices in a weighted graph with negative weight edges allowed.
It compute shortest-paths from given source vertexes, and folds edge
information along shortest paths using a given Fold
operation.
:: (Eq vertex, Hashable vertex, Real cost) | |
=> Fold vertex cost label a | Operation used to fold shotest paths |
-> Graph vertex cost label | |
-> [vertex] | List of source vertexes |
-> HashMap vertex (cost, a) |
Dijkstra's algorithm for finding shortest paths from source vertexes to all of the other vertices in a weighted graph with non-negative edge weight.
It compute shortest-paths from given source vertexes, and folds edge
information along shortest paths using a given Fold
operation.
:: (Eq vertex, Hashable vertex, Real cost) | |
=> Fold vertex cost label a | Operation used to fold shotest paths |
-> Graph vertex cost label | |
-> HashMap vertex (HashMap vertex (cost, a)) |
Floyd-Warshall algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
It compute shortest-paths between each pair of vertexes, and folds edge
information along shortest paths using a given Fold
operation.
Utility functions
bellmanFordDetectNegativeCycle Source #
:: (Eq vertex, Hashable vertex, Real cost) | |
=> Fold vertex cost label a | Operation used to fold a cycle |
-> Graph vertex cost label | |
-> HashMap vertex (cost, Last (InEdge vertex cost label)) | Result of |
-> Maybe a |
Utility function for detecting a negative cycle.