digraph-0.1.0.0: Directed Graphs

Copyright	Copyright © 2018 Kadena LLC.
License	MIT
Maintainer	Lars Kuhtz <lars@kadena.io>
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Data.DiGraph.FloydWarshall

Contents

Graph Representations
Conversions
FloydWarshall Algorithm
Legacy exports

Description

TODO

Synopsis

type DenseAdjMatrix = Array U Ix2 Int
type AdjacencySets = HashMap Int (HashSet Int)
fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix
toAdjacencySets :: DenseAdjMatrix -> AdjacencySets
newtype ShortestPathMatrix = ShortestPathMatrix (Array U Ix2 (Double, Int))
floydWarshall :: Unbox a => Real a => Array U Ix2 a -> ShortestPathMatrix
shortestPath :: ShortestPathMatrix -> Int -> Int -> Maybe [Int]
distance :: ShortestPathMatrix -> Int -> Int -> Maybe Double
diameter :: ShortestPathMatrix -> Maybe Double
distMatrix_ :: Source r Ix2 Int => Array r Ix2 Int -> Array D Ix2 Double
floydWarshall_ :: Array U Ix2 Double -> Array U Ix2 Double
diameter_ :: Array U Ix2 Int -> Maybe Natural
shortestPaths_ :: Array U Ix2 Int -> Array U Ix2 Double

Graph Representations

type DenseAdjMatrix = Array U Ix2 Int Source #

Adjacency matrix representation of a directed graph.

type AdjacencySets = HashMap Int (HashSet Int) Source #

Adjacency set representation of a directed graph.

Conversions

fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix Source #

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

toAdjacencySets :: DenseAdjMatrix -> AdjacencySets Source #

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

FloydWarshall Algorithm

newtype ShortestPathMatrix Source #

Shortest path matrix of a graph.

Constructors

ShortestPathMatrix (Array U Ix2 (Double, Int))

Instances

Eq ShortestPathMatrix Source #
Instance details Defined in Data.DiGraph.FloydWarshall Methods (==) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool # (/=) :: ShortestPathMatrix -> ShortestPathMatrix -> Bool #
Ord ShortestPathMatrix Source #
Instance details 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 Source #
Instance details Defined in Data.DiGraph.FloydWarshall Methods showsPrec :: Int -> ShortestPathMatrix -> ShowS # show :: ShortestPathMatrix -> String # showList :: [ShortestPathMatrix] -> ShowS #
Generic ShortestPathMatrix Source #
Instance details 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 Source #
Instance details Defined in Data.DiGraph.FloydWarshall Methods rnf :: ShortestPathMatrix -> () #
type Rep ShortestPathMatrix Source #
Instance details 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 Source #

Shortest path computation for integral matrixes.

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

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

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

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

diameter :: ShortestPathMatrix -> Maybe Double Source #

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 Source #

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

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

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 Source #

Diameter of a graph.

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

Shortest path matrix.

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