digraph-0.2: Directed Graphs

CopyrightCopyright © 2018 Kadena LLC.
LicenseMIT
MaintainerLars Kuhtz <lars@kadena.io>
Stabilityexperimental
Safe HaskellNone
LanguageHaskell2010

Data.DiGraph.FloydWarshall

Contents

Description

TODO

Synopsis

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

Ord ShortestPathMatrix Source # 
Instance details

Defined in Data.DiGraph.FloydWarshall

Show ShortestPathMatrix Source # 
Instance details

Defined in Data.DiGraph.FloydWarshall

Generic ShortestPathMatrix Source # 
Instance details

Defined in Data.DiGraph.FloydWarshall

Associated Types

type Rep ShortestPathMatrix :: Type -> Type #

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

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.