Copyright	Thodoris Papakonstantinou 2017-2026
License	LGPL-3
Maintainer	dev@tpapak.com
Stability	experimental
Portability	POSIX
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.AdjacencyList.WFI

Description

Implementation of the Floyd-Warshall algorithm for computing all-pairs shortest path distances on a weighted or unweighted directed graph. Complexity: O(V^3).

Synopsis

newtype Distances = Distances IMArray
type Weight = Rational
type IMArray = IntMap (IntMap Weight)
shortestDistances :: Graph -> Distances -> Distances
unweightedShortestDistances :: Graph -> Distances
adjacencyArray :: Graph -> Distances

Documentation

newtype Distances Source #

The array containing the distances from vertex to vertex

Constructors

Distances IMArray

Instances

Instances details

Read Distances Source #
Instance details Defined in Data.Graph.AdjacencyList.WFI Methods readsPrec :: Int -> ReadS Distances # readList :: ReadS [Distances] # readPrec :: ReadPrec Distances # readListPrec :: ReadPrec [Distances] #
Show Distances Source #
Instance details Defined in Data.Graph.AdjacencyList.WFI Methods showsPrec :: Int -> Distances -> ShowS # show :: Distances -> String # showList :: [Distances] -> ShowS #
Eq Distances Source #
Instance details Defined in Data.Graph.AdjacencyList.WFI Methods (==) :: Distances -> Distances -> Bool # (/=) :: Distances -> Distances -> Bool #
Ord Distances Source #
Instance details Defined in Data.Graph.AdjacencyList.WFI Methods compare :: Distances -> Distances -> Ordering # (<) :: Distances -> Distances -> Bool # (<=) :: Distances -> Distances -> Bool # (>) :: Distances -> Distances -> Bool # (>=) :: Distances -> Distances -> Bool # max :: Distances -> Distances -> Distances # min :: Distances -> Distances -> Distances #

type Weight = Rational Source #

In an unweighted graph the weight is 1 for each edge

type IMArray = IntMap (IntMap Weight) Source #

Two-dimensional distance matrix: vertex → vertex → Weight.

shortestDistances :: Graph -> Distances -> Distances Source #

Get all shortest distances given initial weights on edges

unweightedShortestDistances :: Graph -> Distances Source #

Get all shortest unweighted distances

adjacencyArray :: Graph -> Distances Source #

Build the initial distance matrix from a graph's edges (unit weights). Self-distances are 0; direct edges have distance 1; all others are absent (infinite). Pass the result to shortestDistances to run Floyd-Warshall.