author Matt Renaud Thu, 8 Mar 2018 00:26:05 +0000 (16:26 -0800) committer David Feuer Thu, 8 Mar 2018 00:26:05 +0000 (19:26 -0500)
* Improve module docs
* Re-orders function documentation order
* Don't use Table type alias, use Array Vertex a instead.

 Data/Graph.hs patch | blob | history

-- Portability :  portable
--
--- A version of the graph algorithms described in:
+-- = Finite Graphs
--
---   /Structuring Depth-First Search Algorithms in Haskell/,
---   by David King and John Launchbury.
+-- The @'Graph'@ type is an adjacency list representation of a finite, directed
+-- graph with vertices of type @Int@.
+--
+-- The @'SCC'@ type represents a
+-- <https://en.wikipedia.org/wiki/Strongly_connected_component strongly-connected component>
+-- of a graph.
+--
+-- == Implementation
+--
+-- The implementation is based on
+--
+--   * /Structuring Depth-First Search Algorithms in Haskell/,
+--     by David King and John Launchbury.
--
-----------------------------------------------------------------------------

-module Data.Graph(
-
-        -- * External interface
+module Data.Graph (

-        -- At present the only one with a "nice" external interface
-        stronglyConnComp, stronglyConnCompR, SCC(..), flattenSCC, flattenSCCs,
+    -- * Graphs
+      Graph
+    , Bounds
+    , Edge
+    , Vertex
+    , Table

-        -- * Graphs
+    -- ** Graph Construction
+    , graphFromEdges
+    , graphFromEdges'
+    , buildG

-        Graph, Table, Bounds, Edge, Vertex,
+    -- ** Graph Properties
+    , vertices
+    , edges
+    , outdegree
+    , indegree

-        -- ** Building graphs
+    -- ** Graph Transformations
+    , transposeG

-        graphFromEdges, graphFromEdges', buildG, transposeG,
-        -- reverseE,
+    -- ** Graph Algorithms
+    , dfs
+    , dff
+    , topSort
+    , components
+    , scc
+    , bcc
+    , reachable
+    , path

-        -- ** Graph properties

-        vertices, edges,
-        outdegree, indegree,
+    -- * Strongly Connected Components
+    , SCC(..)

-        -- * Algorithms
+    -- ** Construction
+    , stronglyConnComp
+    , stronglyConnCompR

-        dfs, dff,
-        topSort,
-        components,
-        scc,
-        bcc,
-        -- tree, back, cross, forward,
-        reachable, path,
+    -- ** Conversion
+    , flattenSCC
+    , flattenSCCs

-        module Data.Tree
+    -- * Trees
+    , module Data.Tree

) where

@@ -69,7 +95,6 @@ module Data.Graph(
#endif

--- Extensions
import Data.Array.ST (STUArray, newArray, readArray, writeArray)
@@ -108,7 +133,7 @@ import Data.Typeable

-------------------------------------------------------------------------
--                                                                      -
---      External interface
+--      Strongly Connected Components
--                                                                      -
-------------------------------------------------------------------------

@@ -246,31 +271,58 @@ stronglyConnCompR edges0
-- | Abstract representation of vertices.
type Vertex  = Int
-- | Table indexed by a contiguous set of vertices.
+--
+-- /Note: This is included for backwards compatibility./
type Table a = Array Vertex a
-- | Adjacency list representation of a graph, mapping each vertex to its
-- list of successors.
-type Graph   = Table [Vertex]
--- | The bounds of a 'Table'.
+type Graph   = Array Vertex [Vertex]
+-- | The bounds of an @Array@.
type Bounds  = (Vertex, Vertex)
-- | An edge from the first vertex to the second.
type Edge    = (Vertex, Vertex)

--- | All vertices of a graph.
+-- | Returns the list of vertices in the graph.
+--
+-- ==== __Examples__
+--
+-- > vertices (buildG (0,-1) []) == []
+--
+-- > vertices (buildG (0,2) [(0,1),(1,2)]) == [0,1,2]
vertices :: Graph -> [Vertex]
vertices  = indices

--- | All edges of a graph.
+-- | Returns the list of edges in the graph.
+--
+-- ==== __Examples__
+--
+-- > edges (buildG (0,-1) []) == []
+--
+-- > edges (buildG (0,2) [(0,1),(1,2)]) == [(0,1),(1,2)]
edges    :: Graph -> [Edge]
edges g   = [ (v, w) | v <- vertices g, w <- g!v ]

-mapT    :: (Vertex -> a -> b) -> Table a -> Table b
+mapT    :: (Vertex -> a -> b) -> Array Vertex a -> Array Vertex b
mapT f t = array (bounds t) [ (,) v (f v (t!v)) | v <- indices t ]

-- | Build a graph from a list of edges.
+--
+-- Warning: This function will cause a runtime exception if a vertex in the edge
+-- list is not within the given @Bounds@.
+--
+-- ==== __Examples__
+--
+-- > buildG (0,-1) [] == array (0,-1) []
+-- > buildG (0,2) [(0,1), (1,2)] == array (0,1) [(0,),(1,)]
+-- > buildG (0,2) [(0,1), (0,2), (1,2)] == array (0,2) [(0,[2,1]),(1,),(2,[])]
buildG :: Bounds -> [Edge] -> Graph
buildG bounds0 edges0 = accumArray (flip (:)) [] bounds0 edges0

-- | The graph obtained by reversing all edges.
+--
+-- ==== __Examples__
+--
+-- > transposeG (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,[]),(1,),(2,)]
transposeG  :: Graph -> Graph
transposeG g = buildG (bounds g) (reverseE g)

@@ -278,12 +330,24 @@ reverseE    :: Graph -> [Edge]
reverseE g   = [ (w, v) | (v, w) <- edges g ]

-- | A table of the count of edges from each node.
-outdegree :: Graph -> Table Int
+--
+-- ==== __Examples__
+--
+-- > outdegree (buildG (0,-1) []) == array (0,-1) []
+--
+-- > outdegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,1),(1,1),(2,0)]
+outdegree :: Graph -> Array Vertex Int
outdegree  = mapT numEdges
where numEdges _ ws = length ws

-- | A table of the count of edges into each node.
-indegree :: Graph -> Table Int
+--
+-- ==== __Examples__
+--
+-- > indegree (buildG (0,-1) []) == array (0,-1) []
+--
+-- > indegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,0),(1,1),(2,1)]
+indegree :: Graph -> Array Vertex Int
indegree  = outdegree . transposeG

-- | Identical to 'graphFromEdges', except that the return value
@@ -298,8 +362,60 @@ graphFromEdges' x = (a,b) where

-- | Build a graph from a list of nodes uniquely identified by keys,
-- with a list of keys of nodes this node should have edges to.
--- The out-list may contain keys that don't correspond to
--- nodes of the graph; they are ignored.
+--
+-- This function takes an adjacency list representing a graph with vertices of
+-- type @key@ labeled by values of type @node@ and produces a @Graph@-based
+-- representation of that list. The @Graph@ result represents the /shape/ of the
+-- graph, and the functions describe a) how to retrieve the label and adjacent
+-- vertices of a given vertex, and b) how to retrive a vertex given a key.
+--
+-- @(graph, nodeFromVertex, vertexFromKey) = graphFromEdges edgeList@
+--
+-- * @graph :: Graph@ is the raw, array based adjacency list for the graph.
+-- * @nodeFromVertex :: Vertex -> (node, key, [key])@ returns the node
+--   associated with the given 0-based @Int@ vertex; see /warning/ below.
+-- * @vertexFromKey :: key -> Maybe Vertex@ returns the @Int@ vertex for the
+--   key if it exists in the graph, @Nothing@ otherwise.
+--
+-- To safely use this API you must either extract the list of vertices directly
+-- from the graph or first call @vertexFromKey k@ to check if a vertex
+-- corresponds to the key @k@. Once it is known that a vertex exists you can use
+-- @nodeFromVertex@ to access the labelled node and adjacent vertices. See below
+-- for examples.
+--
+-- Note: The out-list may contain keys that don't correspond to nodes of the
+-- graph; they are ignored.
+--
+-- Warning: The @nodeFromVertex@ function will cause a runtime exception if the
+-- given @Vertex@ does not exist.
+--
+-- ==== __Examples__
+--
+-- An empty graph.
+--
+-- > (graph, nodeFromVertex, vertexFromKey) = graphFromEdges []
+-- > graph = array (0,-1) []
+--
+-- A graph where the out-list references unspecified nodes (@'c'@), these are
+-- ignored.
+--
+-- > (graph, _, _) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c'])]
+-- > array (0,1) [(0,),(1,[])]
+--
+--
+-- A graph with 3 vertices: ("a") -> ("b") -> ("c")
+--
+-- > (graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])]
+-- > graph == array (0,2) [(0,),(1,),(2,[])]
+-- > nodeFromVertex 0 == ("a",'a',"b")
+-- > vertexFromKey 'a' == Just 0
+--
+-- Get the label for a given key.
+--
+-- > let getNodePart (n, _, _) = n
+-- > (graph, nodeFromVertex, vertexFromKey) = graphFromEdges [("a", 'a', ['b']), ("b", 'b', ['c']), ("c", 'c', [])]
+-- > getNodePart . nodeFromVertex <\$> vertexFromKey 'a' == Just "A"
+--
graphFromEdges
:: Ord key
=> [(node, key, [key])]
@@ -452,10 +568,10 @@ preorderF' ts = foldr (.) id \$ map preorder' ts
preorderF :: Forest a -> [a]
preorderF ts = preorderF' ts []

-tabulate        :: Bounds -> [Vertex] -> Table Int
+tabulate        :: Bounds -> [Vertex] -> Array Vertex Int
tabulate bnds vs = array bnds (zipWith (,) vs [1..])

-preArr          :: Bounds -> Forest Vertex -> Table Int
+preArr          :: Bounds -> Forest Vertex -> Array Vertex Int
preArr bnds      = tabulate bnds . preorderF

------------------------------------------------------------
@@ -525,12 +641,26 @@ forward g tree' pre = mapT select g
-- Algorithm 6: Finding reachable vertices
------------------------------------------------------------

--- | A list of vertices reachable from a given vertex.
-reachable    :: Graph -> Vertex -> [Vertex]
+-- | Returns the list of vertices reachable from a given vertex.
+--
+-- ==== __Examples__
+--
+-- > reachable (buildG (0,0) []) 0 == 
+--
+-- > reachable (buildG (0,2) [(0,1), (1,2)]) 0 == [0,1,2]
+reachable :: Graph -> Vertex -> [Vertex]
reachable g v = preorderF (dfs g [v])

--- | Is the second vertex reachable from the first?
-path         :: Graph -> Vertex -> Vertex -> Bool
+-- | Returns @True@ if the second vertex reachable from the first.
+--
+-- ==== __Examples__
+--
+-- > path (buildG (0,0) []) 0 0 == True
+--
+-- > path (buildG (0,2) [(0,1), (1,2)]) 0 2 == True
+--
+-- > path (buildG (0,2) [(0,1), (1,2)]) 2 0 == False
+path :: Graph -> Vertex -> Vertex -> Bool
path g v w    = w `elem` (reachable g v)

------------------------------------------------------------
@@ -545,7 +675,7 @@ bcc g = (concat . map bicomps . map (do_label g dnum)) forest
where forest = dff g
dnum   = preArr (bounds g) forest

-do_label :: Graph -> Table Int -> Tree Vertex -> Tree (Vertex,Int,Int)
+do_label :: Graph -> Array Vertex Int -> Tree Vertex -> Tree (Vertex,Int,Int)
do_label g dnum (Node v ts) = Node (v,dnum!v,lv) us
where us = map (do_label g dnum) ts
lv = minimum ([dnum!v] ++ [dnum!w | w <- g!v]