ToySolver.Graph.ShortestPath

This module provides functions for shotest path computation.

Reference:

• Friedrich Eisenbrand. “Linear and Discrete Optimization”. https://www.coursera.org/course/linearopt

Graph data types

type Graph vertex cost label = HashMap vertex [OutEdge vertex cost label]

Graph represented as a map from vertexes to their outgoing edges

type Edge vertex cost label = (vertex, vertex, cost, label)

Edge data type

type OutEdge vertex cost label = (vertex, cost, label)

Outgoing edge data type (source vertex is implicit)

type InEdge vertex cost label = (vertex, cost, label)

Incoming edge data type (target vertex is implicit)

Fold data type

data Fold vertex cost label r

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.

Constructors

Fold (vertex -> a) (Edge vertex cost label -> a) (a -> a -> a) (a -> r)

Instances

Functor (Fold vertex cost label)

Defined in ToySolver.Graph.ShortestPath

Methods

fmap :: (a -> b) -> Fold vertex cost label a -> Fold vertex cost label b

(<$) :: a -> Fold vertex cost label b -> Fold vertex cost label a

Applicative (Fold vertex cost label)

Defined in ToySolver.Graph.ShortestPath

Methods

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

Project Edge into a monoid value and fold using monoidal operation.

monoid :: Monoid m => Fold vertex cost m m

Similar to monoid' but a label is directly used as a monoid value.

unit :: Fold vertex cost label ()

Ignore contents and return a unit value.

pair :: Fold vertex cost label a -> Fold vertex cost label b -> Fold vertex cost label (a, b)

Pairs two Fold into one that produce a tuple.

path :: (Eq vertex, Num cost) => Fold vertex cost label (Path vertex cost label)

Construct a Path value.

firstOutEdge :: Fold vertex cost label (First (OutEdge vertex cost label))

Get the first OutEdge of a path.

lastInEdge :: Fold vertex cost label (Last (InEdge vertex cost label))

Get the last InEdge of a path. This is useful for constructing a parent map of a spanning tree.

cost :: Num cost => Fold vertex cost label cost

Compute cost of a path.

Path data types

data Path vertex cost label

path data type.

Constructors

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

Instances

(Eq vertex, Eq cost, Eq label) => Eq (Path vertex cost label)

Defined in ToySolver.Graph.ShortestPath

Methods

(==) :: Path vertex cost label -> Path vertex cost label -> Bool

(/=) :: Path vertex cost label -> Path vertex cost label -> Bool

(Show vertex, Show cost, Show label) => Show (Path vertex cost label)

Defined in ToySolver.Graph.ShortestPath

Methods

showsPrec :: Int -> Path vertex cost label -> ShowS

show :: Path vertex cost label -> String

showList :: [Path vertex cost label] -> ShowS

pathFrom :: Path vertex cost label -> vertex

Source vertex

pathTo :: Path vertex cost label -> vertex

Target vertex

pathCost :: Num cost => Path vertex cost label -> cost

Cost of a path

pathEmpty :: vertex -> Path vertex cost label

Empty path

pathAppend :: (Eq vertex, Num cost) => Path vertex cost label -> Path vertex cost label -> Path vertex cost label

Concatenation of two paths

pathEdges :: Path vertex cost label -> [Edge vertex cost label]

Edges of a path

pathEdgesBackward :: Path vertex cost label -> [Edge vertex cost label]

Edges of a path, but in the reverse order

pathEdgesSeq :: Path vertex cost label -> Seq (Edge vertex cost label)

Edges of a path, but as Seq

pathVertexes :: Path vertex cost label -> [vertex]

Vertexes of a path

pathVertexesBackward :: Path vertex cost label -> [vertex]

Vertexes of a path, but in the reverse order

pathVertexesSeq :: Path vertex cost label -> Seq vertex

Vertex of a path, but as Seq

pathFold :: Fold vertex cost label a -> Path vertex cost label -> a

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

Shortest-path algorithms

bellmanFord

Arguments

:: (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 vs

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

dijkstra

Arguments

:: (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.

floydWarshall

Arguments

:: (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

Arguments

:: (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 bellmanFord lastInEdge vs

-> Maybe a

Utility function for detecting a negative cycle.