-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Directed Graphs
--   
--   Directed graphs implementation that is based on unordered-containers
@package digraph
@version 0.1.0.0


-- | TODO
module Data.DiGraph.FloydWarshall

-- | Adjacency matrix representation of a directed graph.
type DenseAdjMatrix = Array U Ix2 Int

-- | Adjacency set representation of a directed graph.
type AdjacencySets = HashMap Int (HashSet Int)

-- | Assumes that the input is an undirected graph and that the vertex set
--   is a prefix of the natural numbers.
fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix

-- | Converts an adjacency matrix into a graph in adjacnency set
--   representation.
toAdjacencySets :: DenseAdjMatrix -> AdjacencySets

-- | Shortest path matrix of a graph.
newtype ShortestPathMatrix
ShortestPathMatrix :: Array U Ix2 (Double, Int) -> ShortestPathMatrix

-- | Shortest path computation for integral matrixes.
floydWarshall :: Unbox a => Real a => Array U Ix2 a -> ShortestPathMatrix

-- | Compute a shortest path between two vertices of a graph from the
--   shortest path matrix of the graph.
shortestPath :: ShortestPathMatrix -> Int -> Int -> Maybe [Int]

-- | Compute the distance between two vertices of a graph from the shortest
--   path matrix of the graph.
distance :: ShortestPathMatrix -> Int -> Int -> Maybe Double

-- | Compute the diameter of a graph from the shortest path matrix of the
--   graph.
diameter :: ShortestPathMatrix -> Maybe Double

-- | Floyd Warshall Without Paths (more efficient, by factor of 2).
distMatrix_ :: Source r Ix2 Int => Array r Ix2 Int -> Array D 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.
floydWarshall_ :: Array U Ix2 Double -> Array U Ix2 Double

-- | Diameter of a graph.
diameter_ :: Array U Ix2 Int -> Maybe Natural

-- | Shortest path matrix.
--   
--   All entries of the result matrix are either whole numbers or
--   <tt>Infinity</tt>.
shortestPaths_ :: Array U Ix2 Int -> Array U Ix2 Double
instance Control.DeepSeq.NFData Data.DiGraph.FloydWarshall.ShortestPathMatrix
instance GHC.Generics.Generic Data.DiGraph.FloydWarshall.ShortestPathMatrix
instance GHC.Classes.Ord Data.DiGraph.FloydWarshall.ShortestPathMatrix
instance GHC.Classes.Eq Data.DiGraph.FloydWarshall.ShortestPathMatrix
instance GHC.Show.Show Data.DiGraph.FloydWarshall.ShortestPathMatrix


-- | Directed graphs in adjacency set representation. The implementation is
--   based on <a>Data.HashMap.Strict</a> and <a>Data.HashSet</a> from the
--   <a>unordered-containers package</a>
--   
--   Undirected graphs are represented as symmetric, irreflexive directed
--   graphs.
module Data.DiGraph

-- | Adjacency set representation of directed graphs.
--   
--   It is assumed that each target of an edge is also explicitly a vertex
--   in the graph.
--   
--   It is not generally required that graphs are irreflexive, but all
--   concrete graphs that are defined in this module are irreflexive.
--   
--   Undirected graphs are represented as symmetric directed graphs.
data DiGraph a

-- | Directed Edge.
type DiEdge a = (a, a)

-- | The adjacency sets of a graph.
adjacencySets :: DiGraph a -> HashMap a (HashSet a)

-- | The set of vertices of the graph.
vertices :: DiGraph a -> HashSet a

-- | The set edges of the graph.
edges :: Eq a => Hashable a => DiGraph a -> HashSet (DiEdge a)

-- | The set of adjacent pairs of a graph.
adjacents :: Eq a => Hashable a => a -> DiGraph a -> HashSet a

-- | The set of incident edges of a graph.
incidents :: Eq a => Hashable a => a -> DiGraph a -> [(a, a)]

-- | Insert an edge. Returns the graph unmodified if the edge is already in
--   the graph. Non-existing vertices are added.
insertEdge :: Eq a => Hashable a => DiEdge a -> DiGraph a -> DiGraph a

-- | Construct a graph from a foldable structure of edges.
fromEdges :: Eq a => Hashable a => Foldable f => f (a, a) -> DiGraph a

-- | Insert a vertex. Returns the graph unmodified if the vertex is already
--   in the graph.
insertVertex :: Eq a => Hashable a => a -> DiGraph a -> DiGraph a

-- | Map a function over all vertices of a graph.
mapVertices :: Eq b => Hashable b => (a -> b) -> DiGraph a -> DiGraph b

-- | The union of two graphs.
union :: Eq a => Hashable a => DiGraph a -> DiGraph a -> DiGraph a

-- | Transpose a graph, i.e. reverse all edges of the graph.
transpose :: Eq a => Hashable a => DiGraph a -> DiGraph a

-- | Symmetric closure of a graph.
symmetric :: Eq a => Hashable a => DiGraph a -> DiGraph a

-- | Construct a graph from adjacency lists.
fromList :: Eq a => Hashable a => [(a, [a])] -> DiGraph a

-- | Unsafely construct a graph from adjacency lists.
--   
--   This function assumes that the input includes a adjacency list of each
--   vertex that appears in a adjacency list of another vertex. Generally,
--   <a>fromList</a> should be preferred.
unsafeFromList :: Eq a => Hashable a => [(a, [a])] -> DiGraph a

-- | A predicate that asserts that every target of an edge is also a vertex
--   in the graph. Any graph that is constructed without using unsafe
--   methods is guaranteed to satisfy this predicate.
isDiGraph :: Eq a => Hashable a => DiGraph a -> Bool

-- | Return whether two vertices are adjacent in a graph.
isAdjacent :: Eq a => Hashable a => a -> a -> DiGraph a -> Bool

-- | Return whether a graph is regular, i.e. whether all vertices have the
--   same out-degree. Note that the latter implies that all vertices also
--   have the same in-degree.
isRegular :: DiGraph a -> Bool

-- | Return whether a graph is symmetric, i.e. whether for each edge
--   &lt;math&gt; there is also the edge &lt;math&gt; in the graph.
isSymmetric :: Hashable a => Eq a => DiGraph a -> Bool

-- | Return whether a graph is irreflexive. A graph is irreflexive if for
--   each edge &lt;math&gt; it holds that &lt;math&gt;, i.e there are no
--   self-loops in the graph.
isIrreflexive :: Eq a => Hashable a => DiGraph a -> Bool

-- | Return whether an edge is contained in a graph.
isEdge :: Eq a => Hashable a => DiEdge a -> DiGraph a -> Bool

-- | Return whether a vertex is contained in a graph.
isVertex :: Eq a => Hashable a => a -> DiGraph a -> Bool

-- | The order of a graph is the number of vertices.
order :: DiGraph a -> Natural

-- | Directed Size. This the number of edges of the graph.
size :: Eq a => Hashable a => DiGraph a -> Natural

-- | Directed Size. This the number of edges of the graph.
diSize :: Eq a => Hashable a => DiGraph a -> Natural

-- | Undirected Size of a graph. This is the number of edges of the
--   symmetric closure of the graph.
symSize :: Eq a => Hashable a => DiGraph a -> Natural

-- | The number of outgoing edges of vertex in a graph.
outDegree :: Eq a => Hashable a => DiGraph a -> a -> Natural

-- | The number of incoming edges of vertex in a graph.
inDegree :: Eq a => Hashable a => DiGraph a -> a -> Natural

-- | The maximum out-degree of the vertices of a graph.
maxOutDegree :: Eq a => Hashable a => DiGraph a -> Natural

-- | The maximum in-degree of the vertices of a graph.
maxInDegree :: Eq a => Hashable a => DiGraph a -> Natural

-- | The minimum out-degree of the vertices of a graph.
minOutDegree :: Eq a => Hashable a => DiGraph a -> Natural

-- | The minimum in-degree of the vertices of a graph.
minInDegree :: Eq a => Hashable a => DiGraph a -> Natural

-- | The shortest path matrix of a graph.
--   
--   The shortest path matrix of a graph can be used to efficiently query
--   the distance and shortest path between any two vertices of the graph.
--   It can also be used to efficiently compute the diameter of the graph.
--   
--   Computing the shortest path matrix is expensive for larger graphs. The
--   matrix is computed using the Floyd-Warshall algorithm. The space and
--   time complexity is quadratic in the <i>order</i> of the graph. For
--   sparse graphs there are more efficient algorithms for computing
--   distances and shortest paths between the nodes of the graph.
data ShortestPathCache a

-- | Compute the shortest path matrix for a graph. The result can be used
--   to efficiently query the distance and shortest path between any two
--   vertices of the graph. It can also be used to efficiently compute the
--   diameter of the graph.
shortestPathCache :: Eq a => Hashable a => DiGraph a -> ShortestPathCache a

-- | Compute the shortest path between two vertices of a graph.
--   
--   | This is expensive for larger graphs. If more than one path is needed
--   one should use <a>shortestPathCache</a> to cache the result of the
--   search and use <a>shortestPath_</a> to query paths from the cache.
--   
--   The algorithm is optimized for dense graphs. For large sparse graphs a
--   more efficient algorithm should be used.
shortestPath :: Eq a => Hashable a => a -> a -> DiGraph a -> Maybe [a]

-- | Compute the shortest path between two vertices from the shortest path
--   matrix of a graph.
--   
--   The algorithm is optimized for dense graphs. For large sparse graphs a
--   more efficient algorithm should be used.
shortestPath_ :: Eq a => Hashable a => a -> a -> ShortestPathCache a -> Maybe [a]

-- | Compute the distance between two vertices of a graph.
--   
--   | This is expensive for larger graphs. If more than one distance is
--   needed one should use <a>shortestPathCache</a> to cache the result of
--   the search and use <a>distance_</a> to query paths from the cache.
--   
--   The algorithm is optimized for dense graphs. For large sparse graphs a
--   more efficient algorithm should be used.
distance :: Eq a => Hashable a => a -> a -> DiGraph a -> Maybe Natural

-- | Compute the distance between two vertices from the shortest path
--   matrix of a graph.
--   
--   The algorithm is optimized for dense graphs. For large sparse graphs a
--   more efficient algorithm should be used.
distance_ :: Eq a => Hashable a => a -> a -> ShortestPathCache a -> Maybe Natural

-- | Compute the Diameter of a graph, i.e. the maximum length of a shortest
--   path between two vertices in the graph.
--   
--   This is expensive to compute for larger graphs. If also the shortest
--   paths or distances are needed, one should use <a>shortestPathCache</a>
--   to cache the result of the search and use the <a>diameter_</a>,
--   <a>shortestPath_</a>, and <a>distance_</a> to query the respective
--   results from the cache.
--   
--   The algorithm is optimized for dense graphs. For large sparse graphs a
--   more efficient algorithm should be used.
diameter :: Eq a => Hashable a => DiGraph a -> Maybe Natural

-- | Compute the Diameter of a graph from a shortest path matrix. The
--   diameter of a graph is the maximum length of a shortest path between
--   two vertices in the graph.
diameter_ :: ShortestPathCache a -> Maybe Natural

-- | The empty graph on <tt>n</tt> nodes. This is the graph of <a>order</a>
--   <tt>n</tt> and <a>size</a> <tt>0</tt>.
emptyGraph :: Natural -> DiGraph Int

-- | The (irreflexive) singleton graph.
singleton :: DiGraph Int

-- | Undirected clique.
clique :: Natural -> DiGraph Int

-- | Undirected pair.
pair :: DiGraph Int

-- | Undirected triangle.
triangle :: DiGraph Int

-- | Undirected cycle.
cycle :: Natural -> DiGraph Int

-- | Directed cycle.
diCycle :: Natural -> DiGraph Int

-- | Undirected line.
line :: Natural -> DiGraph Int

-- | Directed line.
diLine :: Natural -> DiGraph Int

-- | The Peterson graph.
petersonGraph :: DiGraph Int

-- | The "twenty chain" graph.
twentyChainGraph :: DiGraph Int

-- | Hoffman-Singleton Graph.
--   
--   The Hoffman-Singleton graph is a 7-regular graph with 50 vertices and
--   175 edges. It's the largest graph of max-degree 7 and diameter 2. Cf.
--   [https:/<i>en.wikipedia.org</i>wiki/Hoffman–Singleton_graph]()
hoffmanSingleton :: DiGraph Int
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.DiGraph.ShortestPathCache a)
instance GHC.Generics.Generic (Data.DiGraph.ShortestPathCache a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.DiGraph.ShortestPathCache a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.DiGraph.ShortestPathCache a)
instance GHC.Show.Show a => GHC.Show.Show (Data.DiGraph.ShortestPathCache a)
instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Data.DiGraph.DiGraph a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.DiGraph.DiGraph a)
instance GHC.Generics.Generic (Data.DiGraph.DiGraph a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.DiGraph.DiGraph a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.DiGraph.DiGraph a)
instance GHC.Show.Show a => GHC.Show.Show (Data.DiGraph.DiGraph a)
instance (Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => GHC.Base.Semigroup (Data.DiGraph.DiGraph a)
instance (Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => GHC.Base.Monoid (Data.DiGraph.DiGraph a)


-- | Throughout the module an undirected graph is a directed graph that is
--   symmetric and irreflexive.
module Data.DiGraph.Random

-- | Type of a random number generator that uniformily chooses an element
--   from a range.
type UniformRng m = (Int, Int) -> m Int

-- | Undirected, irreflexive random regular graph.
--   
--   The algorithm here is incomplete. For a complete approach see for
--   instance
--   <a>https://users.cecs.anu.edu.au/~bdm/papers/RandRegGen.pdf</a>
rrgIO :: Natural -> Natural -> IO (Maybe (DiGraph Int))

-- | Undirected, irreflexive random regular graph.
--   
--   The algorithm here is incomplete. For a complete approach see for
--   instance
--   <a>https://users.cecs.anu.edu.au/~bdm/papers/RandRegGen.pdf</a>
rrg :: Monad m => UniformRng m -> Natural -> Natural -> m (Maybe (DiGraph Int))

-- | Undirected irreflexive random graph in the &lt;math&gt; model.
gnp :: forall m. Monad m => UniformRng m -> Natural -> Double -> m (DiGraph Int)