digraph-0.2: Directed Graphs

Data.DiGraph.FloydWarshall

Description

TODO

Synopsis

# Graph Representations

Adjacency matrix representation of a directed graph.

Adjacency set representation of a directed graph.

# Conversions

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

# FloydWarshall Algorithm

newtype ShortestPathMatrix Source #

Shortest path matrix of a graph.

Constructors

 ShortestPathMatrix (Array U Ix2 (Double, Int))
Instances
 Source # Instance detailsDefined in Data.DiGraph.FloydWarshall Methods Source # Instance detailsDefined in Data.DiGraph.FloydWarshall Methods Source # Instance detailsDefined in Data.DiGraph.FloydWarshall MethodsshowList :: [ShortestPathMatrix] -> ShowS # Source # Instance detailsDefined in Data.DiGraph.FloydWarshall Associated Typestype Rep ShortestPathMatrix :: Type -> Type # Methods Source # Instance detailsDefined in Data.DiGraph.FloydWarshall Methodsrnf :: ShortestPathMatrix -> () # Source # Instance detailsDefined in Data.DiGraph.FloydWarshall type Rep ShortestPathMatrix = D1 (MetaData "ShortestPathMatrix" "Data.DiGraph.FloydWarshall" "digraph-0.2-DK3LAmRnjUBOfDwDBVrNf" 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 Source #

Shortest path computation for integral matrixes.

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

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

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

# Legacy exports

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

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 of a graph.

Shortest path matrix.

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