Data.DiGraph.FloydWarshall

TODO

Graph Representations

type DenseAdjMatrix = Array U Ix2 Int

Adjacency matrix representation of a directed graph.

type AdjacencySets = HashMap Int (HashSet Int)

Adjacency set representation of a directed graph.

Conversions

fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix

Assumes that the input is an undirected graph and that the vertex set is a prefix of the natural numbers.

toAdjacencySets :: DenseAdjMatrix -> AdjacencySets

Converts an adjacency matrix into a graph in adjacnency set representation.

FloydWarshall Algorithm

newtype ShortestPathMatrix

Shortest path matrix of a graph.

Constructors

ShortestPathMatrix (Array U Ix2 (Double, Int))

Instances

Eq ShortestPathMatrix

Defined in Data.DiGraph.FloydWarshall

Methods

(==) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool

(/=) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool

Ord ShortestPathMatrix

Defined in Data.DiGraph.FloydWarshall

Methods

compare :: ShortestPathMatrix -> ShortestPathMatrix -> Ordering

(<) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool

(<=) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool

(>) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool

(>=) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool

max :: ShortestPathMatrix -> ShortestPathMatrix -> ShortestPathMatrix

min :: ShortestPathMatrix -> ShortestPathMatrix -> ShortestPathMatrix

Show ShortestPathMatrix

Defined in Data.DiGraph.FloydWarshall

Methods

showsPrec :: Int -> ShortestPathMatrix -> ShowS

show :: ShortestPathMatrix -> String

showList :: [ShortestPathMatrix] -> ShowS

Generic ShortestPathMatrix

Defined in Data.DiGraph.FloydWarshall

Associated Types

type Rep ShortestPathMatrix :: Type -> Type

Methods

from :: ShortestPathMatrix -> Rep ShortestPathMatrix x

to :: Rep ShortestPathMatrix x -> ShortestPathMatrix

NFData ShortestPathMatrix

Defined in Data.DiGraph.FloydWarshall

Methods

rnf :: ShortestPathMatrix -> ()

type Rep ShortestPathMatrix

Defined in Data.DiGraph.FloydWarshall

type Rep ShortestPathMatrix = D1 (MetaData "ShortestPathMatrix" "Data.DiGraph.FloydWarshall" "digraph-0.1.0.0-8w9BfID4Lt02wYn7iWxOIQ" True) (C1 (MetaCons "ShortestPathMatrix" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Array U Ix2 (Double, Int)))))

floydWarshall :: Unbox a => Real a => Array U Ix2 a -> ShortestPathMatrix

Shortest path computation for integral matrixes.

shortestPath :: ShortestPathMatrix -> Int -> Int -> Maybe [Int]

Compute a shortest path between two vertices of a graph from the shortest path matrix of the graph.

distance :: ShortestPathMatrix -> Int -> Int -> Maybe Double

Compute the distance between two vertices of a graph from the shortest path matrix of the graph.

diameter :: ShortestPathMatrix -> Maybe Double

Compute the diameter of a graph from the shortest path matrix of the graph.

Legacy exports

distMatrix_ :: Source r Ix2 Int => Array r Ix2 Int -> Array D Ix2 Double

Floyd Warshall Without Paths (more efficient, by factor of 2).

floydWarshall_ :: Array U Ix2 Double -> Array U Ix2 Double

Floyd Warshall Without Paths (more efficient, by factor of 2).

TODO: use a mutable array? TODO: implement Dijkstra's algorithm for adj matrix representation.

diameter_ :: Array U Ix2 Int -> Maybe Natural

Diameter of a graph.

shortestPaths_ :: Array U Ix2 Int -> Array U Ix2 Double

Shortest path matrix.

All entries of the result matrix are either whole numbers or Infinity.