-- 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.3.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 directed 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 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 -- Infinity. 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 Data.HashMap.Strict and Data.HashSet from the -- unordered-containers package -- -- 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, -- fromList 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 -- <math> there is also the edge <math> 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 <math> it holds that <math>, 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 order 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 shortestPathCache to cache the result of the -- search and use shortestPath_ 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 shortestPathCache to cache the result of -- the search and use distance_ 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 shortestPathCache -- to cache the result of the search and use the diameter_, -- shortestPath_, and distance_ 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 n nodes. This is the graph of order -- n and size 0. 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:/en.wikipedia.orgwiki/Hoffman–Singleton_graph]() hoffmanSingleton :: DiGraph Int pentagon :: DiGraph Int ascendingCube :: DiGraph (Int, Int, Int) 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 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, 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 -- https://users.cecs.anu.edu.au/~bdm/papers/RandRegGen.pdf rrgIO :: Natural -> Natural -> IO (Maybe (DiGraph Int)) -- | Undirected, irreflexive random regular graph. -- -- The algorithm here is incomplete. For a complete approach see for -- instance -- https://users.cecs.anu.edu.au/~bdm/papers/RandRegGen.pdf rrg :: Monad m => UniformRng m -> Natural -> Natural -> m (Maybe (DiGraph Int)) -- | Undirected irreflexive random graph in the <math> model. gnp :: forall m. Monad m => UniformRng m -> Natural -> Double -> m (DiGraph Int)